You can satisfy the requirememts of a std::deque
with a std::vector<std::unique_ptr<std::array<T,N>>>
roughly. plus a low/high water mark telling you where the first/last elements are. (for an implementation defined N that could vary with T
, and the std::array
s are actually blocks of properly aligned uninitialized memory and not std::array
s, but you get the idea).
Use usual exponential growth, but on both front and back.
Lookup simply does (index+first)/N
and %N
to find the block and sub element.
This is more expensive than a std::vector
lookup, but is O(1).