[Bug libstdc++/13537] std::deque Is Not Conformant

["skirby at acm dot org" <gcc-bugzilla at gcc dot gnu dot org>]

------- 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