From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 24559 invoked by alias); 3 Jul 2012 03:36:14 -0000 Received: (qmail 24528 invoked by uid 22791); 3 Jul 2012 03:36:14 -0000 X-SWARE-Spam-Status: No, hits=-4.3 required=5.0 tests=ALL_TRUSTED,AWL,BAYES_00,KHOP_THREADED 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, 03 Jul 2012 03:36:01 +0000 From: "blelbach at cct dot lsu.edu" To: gcc-bugs@gcc.gnu.org Subject: [Bug libstdc++/49561] [C++0x] std::list::size complexity Date: Tue, 03 Jul 2012 03:36:00 -0000 X-Bugzilla-Reason: CC X-Bugzilla-Type: changed X-Bugzilla-Watch-Reason: None X-Bugzilla-Product: gcc X-Bugzilla-Component: libstdc++ X-Bugzilla-Keywords: X-Bugzilla-Severity: normal X-Bugzilla-Who: blelbach at cct dot lsu.edu X-Bugzilla-Status: REOPENED X-Bugzilla-Priority: P3 X-Bugzilla-Assigned-To: unassigned at gcc dot gnu.org X-Bugzilla-Target-Milestone: 4.7.0 X-Bugzilla-Changed-Fields: Message-ID: In-Reply-To: References: X-Bugzilla-URL: http://gcc.gnu.org/bugzilla/ Auto-Submitted: auto-generated Content-Type: text/plain; charset="UTF-8" MIME-Version: 1.0 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: 2012-07/txt/msg00313.txt.bz2 http://gcc.gnu.org/bugzilla/show_bug.cgi?id=49561 --- Comment #14 from Bryce Lelbach (wash) 2012-07-03 03:35:31 UTC --- (In reply to comment #13) > Patch reverted, thus in C++11 mode size() is back to O(n) but std::list can > interoperate with the C++98 version of it. Why has this been reverted? If std::list<>::size() is not O(1), then GCC's C++11 standard library is not compliant with the C++11 international standard. I have personally spoken with multiple members of the standard body and confirmed that this behavior is REQUIRED by the C++11 standard. Please re-apply this patch for C++11 mode, or state somewhere in the GCC docs that GCC is not compliant with the C++11 standard. In the C++03 and C++98 standards, it was highly suggested that compiler vendors implement std::list<>::size() as O(1). I understand this is a breaking change, but honestly, the C++ standard has been suggesting the O(1) implementation for over a decade, and the GCC standard library developers have chosen to implement different behavior. You've had many years of warning about this. (In reply to comment #10) > I can confirm it was just luck, really. ^ Paolo, this is correct. I think it's a really, really bad idea for any particular vendor to cherrypick elements of an ISO standard to implement. If you feel that the C++11 standard is wrong to require an O(1) implementation, please file a standard defect (I'm afraid you can expect me to fight it). Otherwise, I'd like to ask that you please reconsider applying this patch.