From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 14656 invoked by alias); 28 Jan 2004 22:27:56 -0000 Mailing-List: contact gcc-bugs-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Archive: List-Post: List-Help: Sender: gcc-bugs-owner@gcc.gnu.org Received: (qmail 14605 invoked by uid 48); 28 Jan 2004 22:27:55 -0000 Date: Wed, 28 Jan 2004 22:27:00 -0000 Message-ID: <20040128222755.14602.qmail@sources.redhat.com> From: "skirby at acm dot org" To: gcc-bugs@gcc.gnu.org In-Reply-To: <20040101041622.13537.stl@caltech.edu> References: <20040101041622.13537.stl@caltech.edu> Reply-To: gcc-bugzilla@gcc.gnu.org Subject: [Bug libstdc++/13537] std::deque Is Not Conformant X-Bugzilla-Reason: CC X-SW-Source: 2004-01/txt/msg03639.txt.bz2 List-Id: ------- Additional Comments From skirby at acm dot org 2004-01-28 22:27 ------- > 23.2.1.3.3 says, "Inserting a single element either at the beginning or end of > a deque always takes constant time". > (Aside: Does the Standard mean true constant time there? 23.1/2 says, "All of the complexity requirements in this clause are stated solely in terms of the number of operations on the contained objects." > 23.2.4.1 says, "A vector is a kind of sequence that supports random access > iterators. In addition, it supports (amortized) constant time insert and > erase operations at the end". So the Standard does recognize the difference > between amortized constant time and true constant time. > > Of course, 23.1.1.12 says, "The operations in Table 68 are provided only for > the containers for which they take constant time", and then goes on to list > push_back for vector. See http://anubis.dkuug.dk/jtc1/sc22/wg21/docs/lwg-defects.html#139 for an updated version. > So the Standard sometimes says "constant time" in places where it really > means "amortized constant time". > > But note the exact phrasing of 23.2.1.3.3. "always takes constant time" > clearly rules out the possibility that it is referring to amortized constant > time.) > > *** Thus, I believe that libstdc++ is not conformant. *** > > It seems (and I am not familiar with deque's implementation at all) that > a "map" of pointers is maintained in the deque, and insertions at the front or > back can cause the map to be reallocated. This takes O(N) time, even if the > map's size is N / 4096 or whatever. You are talking about complexity in terms of the number of operations performed on pointers to the contained objects. -- http://gcc.gnu.org/bugzilla/show_bug.cgi?id=13537