The double-ended vector
A very fast C++17 container combining the best features of
"In Most Cases, Prefer Using deque (Controversial)"
-Herb Sutter, GotW #54
veque is an allocator-aware, efficient container with interface matching both
std::deque. Its data layout is very similar to
std::vector, but with unused storage maintained both before and after the used storage.
std::vector, veque is an ordered container in cache-friendly, array-compatible contiguous memory. That makes the data compatible with C APIs, pointer iteration,
gsl::span, and similar.
std::deque, veque allows fast insertion/deletion from the front of the container
- Because veque can resize from both sides, insertions and erasures from arbitrary locations will be twice as fast, because there are often two choices for what data to shift.
The complete API documentation may be viewed here.
The interface for veque maintains the entire interface for
std::vector, allowing veque to be considered as a drop-in replacement. (See tradeoffs)
In addition, veque provides the following additional functions:
resize(), to match
capacity(), to match
Strong exception guarantee pop-and-return, courtesy C++17:
In the spirit of C++20, it is reasonable to ask for the size as a signed type:
Is veque better than
std::vector in every conceivable way? No. But the tradeoffs are appealing.
- veque is a bit more eager to preallocate memory than a typical
std::vectorimplementation, to anticipate resizing from either end. (New - configurable via traits class!)
erase()function calls should be assumed to invalidate all iterators and references, since the resizing could happen from either direction. By comparison, the same
std::dequeoperations will sometimes only invalidate some of the iterators and references. (New - configurable via traits class!)
veque<bool>is not specialized. Whether that makes it better or worse is up to you.
As a developer, I am not good at naming things.
- Perhaps C++14 support?