This is the mail archive of the gcc-bugs@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

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


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


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]