public inbox for gcc-bugs@sourceware.org help / color / mirror / Atom feed
From: "skirby at acm dot org" <gcc-bugzilla@gcc.gnu.org> To: gcc-bugs@gcc.gnu.org Subject: [Bug libstdc++/13537] std::deque Is Not Conformant Date: Wed, 28 Jan 2004 22:27:00 -0000 [thread overview] Message-ID: <20040128222755.14602.qmail@sources.redhat.com> (raw) In-Reply-To: <20040101041622.13537.stl@caltech.edu> ------- 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
next prev parent reply other threads:[~2004-01-28 22:27 UTC|newest] Thread overview: 10+ messages / expand[flat|nested] mbox.gz Atom feed top 2004-01-01 4:16 [Bug libstdc++/13537] New: " stl at caltech dot edu 2004-01-01 4:49 ` [Bug libstdc++/13537] " pinskia at gcc dot gnu dot org 2004-01-01 5:33 ` stl at caltech dot edu 2004-01-11 10:08 ` paolo at gcc dot gnu dot org 2004-01-11 10:11 ` paolo at gcc dot gnu dot org 2004-01-11 10:16 ` paolo at gcc dot gnu dot org 2004-01-11 16:45 ` paolo at gcc dot gnu dot org 2004-01-28 22:27 ` skirby at acm dot org [this message] 2004-01-29 1:35 ` stl at caltech dot edu [not found] <20040101041622.13537.stl@nuwen.net> 2004-10-25 14:03 ` pcarlini at suse dot de
Reply instructions: You may reply publicly to this message via plain-text email using any one of the following methods: * Save the following mbox file, import it into your mail client, and reply-to-all from there: mbox Avoid top-posting and favor interleaved quoting: https://en.wikipedia.org/wiki/Posting_style#Interleaved_style * Reply using the --to, --cc, and --in-reply-to switches of git-send-email(1): git send-email \ --in-reply-to=20040128222755.14602.qmail@sources.redhat.com \ --to=gcc-bugzilla@gcc.gnu.org \ --cc=gcc-bugs@gcc.gnu.org \ /path/to/YOUR_REPLY https://kernel.org/pub/software/scm/git/docs/git-send-email.html * If your mail client supports setting the In-Reply-To header via mailto: links, try the mailto: linkBe sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).