------- Comment #4 from potswa at mac dot com 2009-09-14 16:35 ------- I doubt that stable_partition can't be implemented with std::swap. If I understand you the problem lies in the temporary_buffer, which is uninitialized memory and hence un-swappable. One solution would be simply to initialize it. Already value_type is seeing its constructor called repeatedly, might as well use the default constructor rather than the copy constructor.
Another solution would be to use the temporary_buffer for a parallel vector of iterators, pointers, or indexes rather than values. Insert references to the objects at desired locations in ascending order in [temp, temp+middle-first) and descending order in (temp+last-first,temp+middle-first] (that is, the sequences meet in the middle). Then use the buffer to reorder the sequence in fewer than n std::swaps. (See reorder_destructive() in http://stackoverflow.com/questions/838384/1267878#1267878). This buffer would be smaller than in the present implementation except for tiny structures. -- http://gcc.gnu.org/bugzilla/show_bug.cgi?id=41351
