[RFC] libstdc++/18080: deque::push_back & co not O(1)

[Paolo Carlini <pcarlini at suse dot de>]

Hi everyone,

this is a recurring issue (see, f.i., libstdc++/13537): according to
the current standard (I cannot find any open issue, by the way):

"Inserting a single element either at the beginning or end of
a deque always takes constant time..."

People complain that this is not the case for our implementation, due
to the reallocation of the "map" of pointers: in fact, the original
SGI docs only guarantee *amortized* constant time.

What should we reply to those PRs? A few possibilities:

 1- The standard actually requires only amortized constant time
    (DR 139 [TC] seems relevant about this).
 2- We don't have a bug, because, according to 23.1/2, the complexity
    requirements are stated solely in terms of the number of operations
    *on the contained objects* (therefore, not on deque's "map")
 3- We have a bug but the requirements of the standard are basically
    unimplementable.
 4- It's a "normal" bug and we plan to fix it (How? Any ideas?)
 5- It's a "normal" bug and we don't plan to fix it in the short term
    because requires almost complete rewrite of deque ([Suspended]?)
 6- What else?

Some time ago, libstdc++/13537 has been closed by submitter himself basing
on 2-, but I'm not completely convinced...

Thanks for any feedback,
Paolo.