From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 3549 invoked by alias); 13 Sep 2009 22:20:31 -0000 Received: (qmail 3524 invoked by uid 48); 13 Sep 2009 22:20:20 -0000 Date: Sun, 13 Sep 2009 22:20:00 -0000 Subject: [Bug libstdc++/41351] New: std::rotate on RAI does not conform to ISO complexity requirement X-Bugzilla-Reason: CC Message-ID: Reply-To: gcc-bugzilla@gcc.gnu.org To: gcc-bugs@gcc.gnu.org From: "potswa at mac dot com" Mailing-List: contact gcc-bugs-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Archive: List-Post: List-Help: Sender: gcc-bugs-owner@gcc.gnu.org X-SW-Source: 2009-09/txt/msg01278.txt.bz2 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