public inbox for gcc-bugs@sourceware.org help / color / mirror / Atom feed
From: "stl at caltech dot edu" <gcc-bugzilla@gcc.gnu.org> To: gcc-bugs@gcc.gnu.org Subject: [Bug libstdc++/13537] New: std::deque Is Not Conformant Date: Thu, 01 Jan 2004 04:16:00 -0000 [thread overview] Message-ID: <20040101041622.13537.stl@caltech.edu> (raw) 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.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. 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. Looking at the source for 3.3.2: stl_deque.h: push_back() can call _M_push_back_aux(). deque.tcc: _M_push_back_aux() calls _M_reserve_map_at_back() with no arguments. stl_deque.h: _M_reserve_map_at_back() takes __nodes_to_add which is by default 1. It can thus call _M_reallocate_map(1, false). deque.tcc: _M_reallocate_map() gets called with __nodes_to_add = 1 and __add_at_front = false. It can call copy(_M_start._M_node, _M_finish._M_node + 1, __new_nstart). This looks like it is O(N). Admittedly this bug is rather pedantic, but situations could be envisioned where amortized constant time insertions cause total protonic reversal. (This bug was found by ryanm@microsoft.com ; we discussed it, I verified that he wasn't going crazy, and I agreed to submit a PR.) -- Summary: std::deque Is Not Conformant Product: gcc Version: 3.3.2 Status: UNCONFIRMED Severity: normal Priority: P2 Component: libstdc++ AssignedTo: unassigned at gcc dot gnu dot org ReportedBy: stl at caltech dot edu CC: gcc-bugs at gcc dot gnu dot org,ryanm at microsoft dot com http://gcc.gnu.org/bugzilla/show_bug.cgi?id=13537
next reply other threads:[~2004-01-01 4:16 UTC|newest] Thread overview: 9+ messages / expand[flat|nested] mbox.gz Atom feed top 2004-01-01 4:16 stl at caltech dot edu [this message] 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 2004-01-29 1:35 ` stl at caltech dot edu
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=20040101041622.13537.stl@caltech.edu \ --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).