ORorlp·Mar 23, 2025
I made something similar to this ~10 years ago: https://github.com/orlp/devector. I never finished it (writing proper containers in C++ is a nightmare [1] [2] [3]), although I did start a similar project in Rust a year or two ago... which I also haven't finished yet (the repo is still private). The double-ended vector is very similar to a regular vector, it can just have free space on both ends:
<------------ cap_front ------------>
<------------ cap_back ------------>
<----------------- total_capacity ----------------->
<----- len ----->
<-- space_front --> <-- space_back -->
[ [ elements ] ]
^
+--- ptr
In the Rust crate I store 1 pointer and three lengths: len, space_front, sp
Read the rest
ace_back for a total size of 32 bytes compared to the usual 24 bytes of Vec.
---
I don't think you always want to shift to the middle. Rather, I propose the following strategy (which I do in the Rust crate, unsure if I did the same in C++ implementation):
1. When a request is made for more free space on one side, check if there is already enough free space, and if not,
2. Compute an amortized growing capacity (e.g. double the current capacity), and take the maximum of that with the requested capacity. While doing this ensure you only take into account the capacity of the side you want more space on (e.g. cap_back in the above picture when growing the back),
3. Check if halving the free space on the other side is sufficient to satisfy the amortized request, if yes, do not reallocate and just shift the values internally, otherwise,
4. Allocate a new buffer with the computed capacity, plus the same amount of free space on the other side and copy over the values.
The above strategy ensures you will not exceed 3N space (with doubling space on grow) even when the double-ended vector is used in a LIFO pattern. For example a regular Vec which doubles its size has a 2N total space worst-case.
[1] https://stackoverflow.com/questions/26902006/may-the-element...
[2] https://stackoverflow.com/questions/27453230/is-there-any-wa...
[3] https://stackoverflow.com/questions/26744589/what-is-a-prope...