Deque containers: vec_deque<T>, inline_vec_deque, outline_vec_deque, sso_vec_deque, and the ring-buffer engine
vec_deque<T> (include/reloco/vec_deque.hpp) is a move-only,
allocator-backed double-ended queue: push/pop/insert/erase at either end run
in amortized O(1), and index access is O(1). It is the fallible,
allocator-explicit analogue of std::deque (though, unlike std::deque,
it is backed by a single contiguous ring buffer rather than a sequence of
fixed-size chunks – more like Rust’s std::collections::VecDeque).
inline_vec_deque<T, Capacity> (fixed-capacity, allocator-free),
outline_vec_deque<T> (non-owning, over a caller-supplied span), and
sso_vec_deque<T, InlineCapacity> (small-size-optimized) round out the
family, mirroring inline_vector/outline_vector/sso_vector exactly.
If you haven’t already, read
Type-erased base containers first: this
page assumes familiarity with that document’s vector_operations/
type_metadata layering and the “untyped *_base classes operate on
void* + byte offsets” pattern – the deque engine (detail/vector_base.hpp,
out-of-line bodies in vector_base.ipp, right alongside the vector engine)
reuses that same split, just with a ring buffer instead of a flat array.
Why a ring buffer instead of shifting a flat array
A vector<T> used as a queue would need to shift every remaining element
on every pop_front (or waste ever-growing dead space at the front). A
ring buffer avoids both: elements live in [0, cap_) as usual, but a
head_ index marks the logical start, and the logical range wraps around
the end of the buffer back to index 0 once head_ + len_ exceeds cap_.
unowned_deque_base (the deque’s equivalent of unowned_vector_base)
tracks exactly four fields:
void *data_ = nullptr;
std::size_t head_ = 0; // physical index of the logical front
std::size_t len_ = 0; // number of live elements
std::size_t cap_ = 0; // physical buffer size
push_back/push_front/pop_back/pop_front only ever touch head_,
len_, and the one or two elements at the affected end – no other element
moves. Random access (operator[](logical_index)) adds head_ to the
logical index and wraps modulo cap_:
std::size_t physical_index = head_ + logical_index;
if (physical_index >= cap_)
physical_index -= cap_;
as_slices() exposes the two contiguous chunks ([head_, cap_) and, if
wrapped, [0, head_ + len_ - cap_)) as a std::pair<span<T>, span<T>> –
the deque’s equivalent of Rust’s VecDeque::as_slices, and the mechanism
try_clone, try_append, and contains all use to iterate every element
without caring whether the buffer is currently wrapped.
Layer 1: storage policies
Exactly like vector_base.hpp’s vector side, unowned_deque_base’s
non-trivial primitives (try_reserve_base, try_make_contiguous_base,
rotate_left_base, try_erase_at_base) are declared RELOCO_API and
defined once, out-of-line, in vector_base.ipp – they operate on
void*/type_metadata so they compile and link once regardless of how
many vec_deque<T> instantiations a program uses. Only one storage policy
ships today:
| Policy | Backs | Allocator | Growth |
|---|---|---|---|
heap_deque_base |
vec_deque<T> |
allocator_ref |
Unbounded (up to max_capacity) |
inline_deque_base |
inline_vec_deque<T, Capacity> |
none | Fixed at Capacity |
outline_deque_base |
outline_vec_deque<T> |
none | Fixed at the bound span’s capacity |
mixed_deque_base |
sso_vec_deque<T, InlineCapacity> |
allocator_ref (once promoted) |
Inline up to InlineCapacity, unbounded beyond |
inline_deque_base, outline_deque_base, and mixed_deque_base mirror
inline_vector_base/outline_vector_base/mixed_vector_base on the
vector side exactly – same constructors, same
get_inline_storage/is_inline/get_allocator/inline_capacity/
max_capacity surface, same “no move support” rationale for the outline
flavor (see
Type-erased base containers).
Adding a further deque flavor follows the identical “fifth vector flavor”
recipe from
Type-erased base containers,
just against typed_deque_base<T, Base> instead of typed_vector_base<T,
Base>.
try_reserve_base additionally has to keep the ring buffer’s wrap-around
intact across growth: after expand_in_place/reallocate widens the
buffer, if the buffer was wrapped (head_ + len_ > cap_), the head chunk
is shifted right to stay flush against the new, larger capacity, instead of
leaving a hole in the middle of the logical range.
Layer 2: typed_deque_base<T, Base>
typed_deque_base<T, Base> is the thin, T-templated wrapper – the deque
equivalent of typed_vector_base<T, Base> – providing the full typed API:
auto d = reloco::vec_deque<int>::try_create();
if (!d)
return; // d.error() is a reloco::error.
auto ok = d->try_push_back(2);
ok = d->try_push_front(1);
ok = d->try_push_back(3);
assert((*d)[0] == 1 && (*d)[1] == 2 && (*d)[2] == 3);
| Function | Behavior |
|---|---|
try_reserve(new_cap) |
Grows capacity, preserving wrap-around |
try_emplace_front(args...) / try_push_front(value) |
O(1) amortized |
try_emplace_back(args...) / try_push_back(value) |
O(1) amortized |
try_pop_front() / try_pop_back() |
O(1) |
operator[] / try_at / front() / back() |
O(1), same checked/try_* tri-tier convention as vector<T> |
as_slices() |
Splits the logical range into its (up to two) physical contiguous spans |
try_make_contiguous() |
Unwraps the ring buffer (head_ == 0), returning a single span<T> |
rotate_left(mid) / rotate_right(k) |
O(min(mid, len - mid)), zero allocations |
try_erase_at(index) |
Shortest-shift removal, O(min(index, len - index)) |
try_emplace_at(index, args...) / try_insert_at(index, value) |
Shortest-shift insertion (see below) |
try_swap_remove_back(index) / try_swap_remove_front(index) |
O(1) removal that does not preserve order |
contains(value) |
Rust slice::contains equivalent, walks both as_slices() chunks |
try_append(other) |
Moves every element out of other (itself possibly wrapped) |
truncate(new_len) / clear() |
Drop trailing elements / drop everything |
rotate_left/rotate_right: Rust VecDeque::rotate_left/rotate_right
rotate_left(mid) shifts the element at logical index mid to the front,
appending [0, mid) to the back; rotate_right(k) is defined in terms of
it (rotate_left(len() - k)). rotate_left_base picks whichever side is
cheaper to move (mid vs. len - mid) and, in the special case where the
buffer is completely full (len_ == cap_), rotates in true O(1) by only
adjusting head_ – no element is touched at all, since every physical
slot is already live.
try_insert_at/try_emplace_at: Rust VecDeque::insert
Unlike try_erase_at_base, which is a bespoke, hand-shifted ring-buffer
routine (see its .ipp body for the wrap-handling case analysis),
try_emplace_at needs no new low-level primitive at all – it is composed
entirely out of the public building blocks above:
this->rotate_left(index); // bring the future predecessor to front
auto pushed = try_emplace_front(args...); // O(1) amortized
this->rotate_right(index); // restore relative order
rotate_left(index) costs O(min(index, len - index)) (picked
automatically), try_emplace_front places the new element, and
rotate_right(index) restores the original relative order with the new
element now sitting at index. If the emplace itself fails (e.g. T’s
constructor is fallible and reports an error), the first rotation is
undone with a matching rotate_right(index) before returning the error,
so the deque is left exactly as it was found – a strong exception/error
guarantee without any manual rollback bookkeeping.
try_swap_remove_back/try_swap_remove_front: Rust VecDeque::swap_remove_back/swap_remove_front
Both swap the target index with the last (_back) or first (_front)
element via std::swap, then pop that end. This is O(1) instead of
try_erase_at’s O(min(index, len - index)), at the cost of not
preserving the relative order of the remaining elements – use it when
order doesn’t matter and you want the cheapest possible removal.
Shared-library considerations
Exactly as with the vector engine, unowned_deque_base’s non-trivial
bodies and heap_deque_base/mixed_deque_base/inline_deque_base’s
deallocate_elements/move_construct_from_base (where non-trivial) are
declared RELOCO_API and defined out-of-line in vector_base.ipp, guarded
by the same RELOCO_SHARED_PROVIDE_DEFINITIONS macro described in
Shared-library deployments.
See also
- API reference for the full per-type quick reference for
vec_deque<T>/inline_vec_deque<T, Capacity>/outline_vec_deque<T>/sso_vec_deque<T, InlineCapacity>. - Type-erased base containers for the vector side of the same engine, and the recipe for adding a sixth deque flavor.