From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 26723 invoked by alias); 28 Jun 2011 08:18:11 -0000 Received: (qmail 26710 invoked by uid 22791); 28 Jun 2011 08:18:08 -0000 X-SWARE-Spam-Status: No, hits=-2.7 required=5.0 tests=ALL_TRUSTED,AWL,BAYES_00 X-Spam-Check-By: sourceware.org Received: from localhost (HELO gcc.gnu.org) (127.0.0.1) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Tue, 28 Jun 2011 08:17:54 +0000 From: "yoch.melka at gmail dot com" To: gcc-bugs@gcc.gnu.org Subject: [Bug libstdc++/49561] New: gcc does not meet the standard for std::list container X-Bugzilla-Reason: CC X-Bugzilla-Type: new X-Bugzilla-Watch-Reason: None X-Bugzilla-Product: gcc X-Bugzilla-Component: libstdc++ X-Bugzilla-Keywords: X-Bugzilla-Severity: major X-Bugzilla-Who: yoch.melka at gmail dot com X-Bugzilla-Status: UNCONFIRMED X-Bugzilla-Priority: P3 X-Bugzilla-Assigned-To: unassigned at gcc dot gnu.org X-Bugzilla-Target-Milestone: --- X-Bugzilla-Changed-Fields: Message-ID: X-Bugzilla-URL: http://gcc.gnu.org/bugzilla/ Auto-Submitted: auto-generated Content-Type: text/plain; charset="UTF-8" MIME-Version: 1.0 Date: Tue, 28 Jun 2011 08:18:00 -0000 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: 2011-06/txt/msg02694.txt.bz2 http://gcc.gnu.org/bugzilla/show_bug.cgi?id=49561 Summary: gcc does not meet the standard for std::list container Product: gcc Version: 4.5.2 Status: UNCONFIRMED Severity: major Priority: P3 Component: libstdc++ AssignedTo: unassigned@gcc.gnu.org ReportedBy: yoch.melka@gmail.com I realized that the complexity of std::list::size() is O(n), not O(1). This does not conform to standard. The standard states that size() function is in constant time for alls containers. So, the behavior of gcc is not as expected. This also affects parts of std::list::splice() function, as mentioned in the last drat (n3242 - 23.3.5.5): [quote] 1 Since lists allow fast insertion and erasing from the middle of a list, certain operations are provided specifically for them. 2 list provides three splice operations that destructively move elements from one list to another.[...] void splice(const_iterator position, list& x) noexcept; void splice(const_iterator position, list&& x) noexcept; [...] 4 Effects: Inserts the contents of x before position and x becomes empty. Pointers and references to the moved elements of x now refer to those same elements but as members of *this. Iterators referring to the moved elements will continue to refer to their elements, but they now behave as iterators into *this, not into x. 5 Complexity: Constant time. void splice(const_iterator position, list& x, const_iterator i) noexcept; void splice(const_iterator position, list&& x, const_iterator i) noexcept; 6 Effects: Inserts an element pointed to by i from list x before position and removes the element from x. The result is unchanged if position == i or position == ++i. Pointers and references to *i continue to refer to this same element but as a member of *this. Iterators to *i (including i itself) continue to refer to the same element, but now behave as iterators into *this, not into x. [...] 8 Complexity: Constant time. void splice(const_iterator position, list& x, const_iterator first, const_iterator last) noexcept; void splice(const_iterator position, list&& x, const_iterator first, const_iterator last) noexcept; 9 Effects: Inserts elements in the range [first,last) before position and removes the elements from x. [...] 11 Complexity: Constant time if &x == this; otherwise, linear time. [/quote]