Comment by Const-me
3 years ago
Generally, std::vector not going to work for allocator backend.
The issue being, std::vector relocates all elements every time it increases the capacity. Therefore, adding an element to std::vector may invalidate addresses of all previously added vector elements.
You gonna have to adjust your higher-level data structures which use that allocator, replacing pointers with offsets relative to the start of that std::vector. This introduces another level of indirection, adds complexity, and in some edge cases may even ruin the performance.
std::vector is fine if you access elements by index, instead of pointer, which can be a perfectly fine approach. Of course this kills the general purpose allocator aspect, since you're not getting back pointers, only offsets.
However, if you combine that with generation numbers, you can make yourself a very handy container with stable and safe references. slotmap [1] comes to mind.
[1]: https://docs.rs/slotmap/latest/slotmap/
Yes, that's true if you need higher-level datastructures, but if your functions are just taking vectors/spans of stuff as input then it works out fine.
std::deque, although it would be nice to use an implementation where you can control the block size.
Here’s a simple non-standard allocator for C++ I used a few times in the past: https://github.com/Const-me/CollectionMicrobench/blob/master...
The block size is controlled with a template argument, the number must be a compile-time constant.