This is the mail archive of the
gcc-bugs@gcc.gnu.org
mailing list for the GCC project.
[Bug libstdc++/41351] New: std::rotate on RAI does not conform to ISO complexity requirement
- From: "potswa at mac dot com" <gcc-bugzilla at gcc dot gnu dot org>
- To: gcc-bugs at gcc dot gnu dot org
- Date: 13 Sep 2009 22:20:20 -0000
- Subject: [Bug libstdc++/41351] New: std::rotate on RAI does not conform to ISO complexity requirement
- Reply-to: gcc-bugzilla at gcc dot gnu dot org
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