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

[Paolo Carlini]

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.