deque::push_back/pop_front are not amortized constant time

[leni536]

Observed behavior

deque::push_back() and deque::pop_front() don't have amortized O(1)
complexity when they are called in any arbitrary order.

Through analyzing the source of deque, I found the following access problematic pattern:

• The deque can be initialized to a state where its buffer of pointers to chunks is almost
  full.
• After this push_back and pop_front called alternately.
• Every time a chunk worth of elements are pushed back and popped from the front then all
  of the chunk pointers (around size/chunk_size worth) are moved together one place to the
  front in their buffer. The average number of pointer copies in one iteration of push_back + pop_front is around size/(chunk_size^2).

To demonstrate, I tested this with a custom allocator with a fancy pointer that tracks the
number of pointer copies:

https://godbolt.org/z/esTovP1Tb

output:

n, #ptr copies per (push_back + pop_front)
31, 6.16129
95, 6.65263
223, 7.49776
479, 8.63466
991, 10.6963
2015, 14.7256
4063, 22.7398
8159, 38.7469
16351, 70.7504
32735, 134.752
65503, 262.753
131039, 518.753
262111, 1030.75
524255, 2054.75

Expected behavior

The standard wording leaves out the number of pointer copies in the complexity requirements of deque. There were some recent discussions on the isocpp-lib reflector on specifying amortized constant time for the pointer operations: thread starts on https://lists.isocpp.org/lib/2025/03/30825.php

Arguably alternating push_back and pop_front is a typical access pattern for deque, therefore slowdowns for this pattern at particular deque sizes are undesirable, even if there is no standard wording (yet) to mandate complexity here.

Possible fix

One possible direction is to ensure that there is O(size()) space in the front and the back after reallocation, instead of a fixed number of chunks.

[frederick-vs-ja]

Looks like that we're still conforming until the DR is accepted.

[zygoloid]

The complexity is currently mandated as being constant for these operations (not even amortized, simply "constant").

push_back is required to "take constant time": https://eel.is/c++draft/deque#modifiers-2
pop_front constrains element operations rather than time: https://eel.is/c++draft/deque#modifiers-6

... but push_back doesn't take constant time, or even amortized constant time, in libc++, which seems decidedly non-conforming.

Presumably a better thing to do here would be to use a ring buffer of pointers to chunks instead of shuffling the chunk pointers around in their block, but I suppose that would be an ABI break. Ensuring there's O(size()) space on both sides after reallocation is probably the cleanest fix within the current ABI.