According to C++03 and C++0x, std::rotate has "Complexity: At most last - first
swaps."
The random iterator implementation does not call std::swap at all, but rather
creates a temporary variable and uses the assignment operator to implement
swapping. std::swap often has different complexity than two assignments, so
this is non-conforming. Note that the standard requires that std::swap on any
container take constant time, but assignment will take linear time.
The temporary variable appears to be an optimization for native machine types:
rather than move each object to its final location with a swap operation, move
it with an assignment and avoid performing twice the necessary assignments.
This is a good goal, and perhaps it may be achieved using a special
temporary-variable template type which calls std::swap for all but some subset
of types.
--
Summary: std::rotate on RAI does not conform to ISO complexity
requirement
Product: gcc
Version: 4.2.1
Status: UNCONFIRMED
Severity: major
Priority: P3
Component: libstdc++
AssignedTo: unassigned at gcc dot gnu dot org
ReportedBy: potswa at mac dot com
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=41351
