This is the mail archive of the
gcc-bugs@gcc.gnu.org
mailing list for the GCC project.
[Bug libstdc++/13537] New: std::deque Is Not Conformant
- From: "stl at caltech dot edu" <gcc-bugzilla at gcc dot gnu dot org>
- To: gcc-bugs at gcc dot gnu dot org
- Date: 1 Jan 2004 04:16:32 -0000
- Subject: [Bug libstdc++/13537] New: std::deque Is Not Conformant
- Reply-to: gcc-bugzilla at gcc dot gnu dot org
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