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

[chris at bubblescope dot net]

------- Comment #7 from chris at bubblescope dot net  2009-09-14 18:11 -------
Only a svn copy of stl_algo.h has the rvalue reference stuff for
stable_partition. We use a number of macros, like _GLIBCXX_MOVE, to wrap
various parts of the algorithms, so they work in both c++03 and c++0x.

It is a requirement of c++0x that algorithms like rotate and stable_partition
work with move-only types, so the current implementations never copy at all. I
believe, without evidence, that these rotate / stable_partition implementations
will be as fast as maintaining a separate pointer list when sorting a range of
vector<int>s, for example. Of course a new implementation of any algorithm
which satisfies all the standard requirements, and is faster than the existing
ones in all cases it was used, would I'm sure be greatfully accepted, modulo
copyright assignments and the like.


Of course this does not help people right now, using C++03. Certainly it is bad
how long rotate takes, but similar problems have long existed, to a greater or
lesser extent, with many other algorithms including sort and stable_sort.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=41351