<table border="1" cellspacing="0" cellpadding="8">
    <tr>
        <th>Issue</th>
        <td>
            <a href=https://github.com/llvm/llvm-project/issues/141707>141707</a>
        </td>
    </tr>

    <tr>
        <th>Summary</th>
        <td>
            deque::push_back/pop_front are not amortized constant time
        </td>
    </tr>

    <tr>
      <th>Labels</th>
      <td>
            new issue
      </td>
    </tr>

    <tr>
      <th>Assignees</th>
      <td>
      </td>
    </tr>

    <tr>
      <th>Reporter</th>
      <td>
          leni536
      </td>
    </tr>
</table>

<pre>
    ### 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.
</pre>
<img width="1" height="1" alt="" src="http://email.email.llvm.org/o/eJx8Vk1v4zgS_TX0hWiBor6sgw-a2Tawp55D7g2KKlncpkgNWbLj_PpFUbKT9GwWMBKIYr0qvnr1KBWjuTiAE6v-YNW_DmrFyYeTBWeqoj70frifmCy2H__RRwhXGHgPk7oaH5jo6FeLAf5egRUdK7pljdPPXulfTB6ZbFktuHID_22TX36OwTt83zR4x2SDfFJX4Gr2Ac0bDPwHk8ectohO-3mx8Grwzm8TOI4T3LkKwLWyFgZuHFeOVnqDQYU792GAkG1FvkzBr5eJK6fs_c24C4Xz6NeggfuRb8XJP_m_-ehXN6TXo7fW32iz0hpi5EvwvYVZodF8UYgQHB1IdEx2_GWCDYZr5XgP3DiDRtl0DvRc8YgKgYoPwA1G3q_jCIHSL944hBBpn55W9ytyE7mys4_IRDeu1mZ7mm5ECBwnE_mT60Txk9QHIcpSgQrB3h_B368Q7hzNDFxtifjNB5yoBrAwg8OYOCVo6vQH8AUGPgY_b9SkREh9UNYy0fkxrW-Yz-MweVQh8RnNGzB5Tu9_0sOWmMk25Zv9NbF0AZyIEgd8sUoDEYITEAcpo0l9N2HnLkusqysEdQHu1rn_xCfXfjEQKYoQDUJQaLxLW57kMfnHB_KI908lM3l8r5pV3yWT7UNVng8wexcxKNzlgxCRjkINuhmciOg1op-JKK8V-vBYH5XT92etOCnkGJT-Ffcjf3WeXXOimxCX9ERVni9-6L3FzIcLk-c3Js8QX_z1r_yl37b7FZcV9-ha7D_ROaqcyWLBJ2MLBGreFyRtA1nkFFdneZ2n57banutK1gUTnSTb-JM3Wdk2Tc1EVzYtLRyzuihrWmjbBJGLrG63EJEnkLzMGlmlGFEnFCmzpmiPTHTHvEowxTFrypoS53VRJaBGZE0lSqpNNsWGVJRZU0kmurqqxAZVy6ypKF1e5KJIYFV-3NdkLfN8L6sgPCa6SpaySnBSVOW29pHANF0Pm_z-uoDGf9gkCTWicoMKA2l_IF-xoK4QuV_TLP1fAafperfAAH-vJuwT-zCwNA4B-I3-RD8DD6DBIR9M1GuMxrvI_YZlotfL8s2angcYLWgSpnc8LqDNeE-u97RhTRpXNPFkHaMPCeJRpF_2uSItcpwCqIHOGjBl-6xSayLGbMu-S9WansmzFLJi8kw9OhfiKKtsmRYmOs5E14XLqnp7f3oalfeV_dEEc7wvRiv7dO7NrVPpT68nq4HRE1fW3wZ_c3E_m3mPUMgXFdDo1ao9NjnD5pOrGyCaoHqbEOEKjptxQ6ZCnP9n05k83oFmiMxtppf4qbUUm_2uqr98jKa3wEfzur37QR75WB1MAJ2szaRLBFxcA-ye8iiGLtPN1NKtK1seF_LYXV0be2q__DZi02UTYLcu45NVGBeRWuxHMjHzCsMH5W7XV3YYTsXQFq06wClvymPRtrkoD9NJVLrPQbSibgfRjkXRVLo9Fj2UsmhkIQ_mREoQlTwKKStRZmOTt1r09di0Q131mpUCZmVsZu11JgkdTIwrnPIyb0RzsKoHG9MnjZQObjy9ZVLSF044UdC3fr1EVopNi08YNGjh9L8_Zs7v-qK-O49fjcdhDfb0mzMbnNY-034mtdvr49-3Jfj_gEYmz6nIyOR5P8X1JP8bAAD__6N-JZ0">