[Bug libstdc++/41351] std::rotate on RAI does not conform to ISO complexity requirement

[potswa at mac dot com]

------- 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