A header-only C++20 data structure that grows from the midpoint of an internal buffer in both directions, making it a natural primitive for implementing circular buffers and deque-like containers with efficient front and back insertion.
Disclaimer: This README was generated with the assistance of Claude.
bv::bidirectional_vector<T, Alloc> is a sequence container that stores elements in a flat allocation, starting from the midpoint of the buffer. Elements can grow toward the end (forward direction) or toward the beginning (reverse direction), allowing O(1) amortized push_front and push_back without the node allocation overhead of std::deque.
Key properties:
- O(1) amortized
push_backandpush_front - O(1)
pop_backandpop_front - Supports both forward and reverse iterator insertion/erasure semantics
- Elements may wrap around the buffer for efficient reuse of freed space
normalize()makes all elements contiguous when required- Iterators satisfy
random_access_iterator(but notcontiguous_iterator) - Contiguous memory segments are accessible via
std::spanthroughcontiguous_partition() - Standard-compatible allocator support
Buffer: [ _ _ _ _ | F F F F F . . B B B | _ _ _ _ ]
^front ^back
<-- reverse grows forward grows -->
The buffer is allocated once with a sentinel position reserved at allocation time. On construction, front and back are both placed at the midpoint. Elements pushed to the back advance back toward the buffer end; elements pushed to the front retreat front toward the buffer start. When either end reaches the buffer boundary, subsequent pushes wrap around to the opposite end of the allocation, giving the same circular behavior as a ring buffer.
When elements wrap around, the container is in a segmented state: logical order spans two non-contiguous memory regions (a "frontend" segment and a "backend" segment). The normalize() function rearranges the elements in-place so that the entire sequence occupies one contiguous span.
- C++ standard: C++20 or later
C++17 support is theoretically possible but requires removing several C++20 language features (concepts, ranges,std::span, etc.). - Platform: Linux (other platforms untested)
- Compiler: See Compiler Support
bidirectional_vector is a single header-only library. Copy bidirectional_vector.hpp into your project and include it:
#include "bidirectional_vector.hpp"No build system integration or linking is required.
#include "bidirectional_vector.hpp"
#include <iostream>
int main() {
bv::bidirectional_vector<int> v;
// Push to both ends
v.push_back(3);
v.push_back(4);
v.push_front(2);
v.push_front(1);
// v == [1, 2, 3, 4]
// Standard iteration
for (int x : v) {
std::cout << x << ' '; // 1 2 3 4
}
// Random access (supports negative indices)
std::cout << v[0]; // 1
std::cout << v[-1]; // 4 (last element)
// Efficient removal from both ends
v.pop_front();
v.pop_back();
// v == [2, 3]
// Make contiguous if needed
v.normalize();
}The API closely mirrors std::vector, with additional members for reverse/front operations.
| Member | Description |
|---|---|
value_type |
T |
allocator_type |
Alloc |
size_type |
Unsigned integer type |
difference_type |
Signed integer type |
reference / const_reference |
T& / const T& |
pointer / const_pointer |
Allocator pointer types |
iterator |
Forward random-access iterator |
const_iterator |
Const forward random-access iterator |
reverse_iterator |
Reverse random-access iterator |
const_reverse_iterator |
Const reverse random-access iterator |
bidirectional_vector();
explicit bidirectional_vector(allocator_type const& alloc);
explicit bidirectional_vector(size_type count, allocator_type const& alloc = {});
bidirectional_vector(size_type count, const_reference value, allocator_type const& alloc = {});
bidirectional_vector(It first, It last, allocator_type const& alloc = {});
bidirectional_vector(std::initializer_list<T> ilist, allocator_type const& alloc = {});
bidirectional_vector(bidirectional_vector const& other);
bidirectional_vector(bidirectional_vector&& other) noexcept;size_type size() const noexcept;
size_type capacity() const noexcept;
size_type max_size() const noexcept;
bool empty() const noexcept;
void reserve(size_type new_cap);
void shrink_to_fit();reference operator[](difference_type idx) noexcept; // supports negative indexing
const_reference operator[](difference_type idx) const noexcept;
reference at(difference_type idx); // throws std::out_of_range
const_reference at(difference_type idx) const;
reference front() noexcept;
const_reference front() const noexcept;
reference back() noexcept;
const_reference back() const noexcept;operator[] and at() accept negative indices: v[-1] returns the last element, v[-2] the second-to-last, and so on.
iterator begin() / end();
const_iterator cbegin() / cend();
reverse_iterator rbegin() / rend();
const_reverse_iterator crbegin() / crend();These point to the boundary between the two contiguous segments when the container is segmented, or to end()/rend() when it is not:
iterator contiguous_split(); // boundary from forward direction
const_iterator ccontiguous_split() const;
reverse_iterator rcontiguous_split(); // boundary from reverse direction
const_reverse_iterator crcontiguous_split() const;void push_back(const_reference value);
void push_back(value_type&& value);
template <typename... Args>
reference emplace_back(Args&&... args);
void pop_back() noexcept;
void resize(size_type new_size);
void resize(size_type new_size, const_reference value);void push_front(const_reference value);
void push_front(value_type&& value);
template <typename... Args>
reference emplace_front(Args&&... args);
void pop_front() noexcept;
void rresize(size_type new_size);
void rresize(size_type new_size, const_reference value);Both forward (iterator) and reverse (reverse_iterator) overloads are provided. When a forward iterator position is given, behavior matches std::vector: elements at and after the position shift forward on insert and backward on erase. When a reverse iterator position is given, the directions are flipped.
// Single element
iterator insert(const_iterator pos, const_reference value);
iterator insert(const_iterator pos, value_type&& value);
reverse_iterator insert(const_reverse_iterator pos, const_reference value);
reverse_iterator insert(const_reverse_iterator pos, value_type&& value);
// Count
iterator insert(const_iterator pos, size_type count, const_reference value);
reverse_iterator insert(const_reverse_iterator pos, size_type count, const_reference value);
// Iterator range
iterator insert(const_iterator pos, It first, It last);
reverse_iterator insert(const_reverse_iterator pos, It first, It last);
// Initializer list
iterator insert(const_iterator pos, std::initializer_list<T>);
reverse_iterator insert(const_reverse_iterator pos, std::initializer_list<T>);
// Emplace
iterator emplace(const_iterator pos, Args&&... args);
reverse_iterator emplace(const_reverse_iterator pos, Args&&... args);iterator erase(const_iterator pos);
iterator erase(const_iterator first, const_iterator last);
reverse_iterator erase(const_reverse_iterator pos);
reverse_iterator erase(const_reverse_iterator first, const_reverse_iterator last);void assign(size_type count, const_reference value);
void assign(It first, It last);
void assign(std::initializer_list<T>);
void assign_range(R&& range); // C++23-style range overload
void append_range(R&& range);
void prepend_range(R&& range);
void insert_range(const_iterator pos, R&& range);
void insert_range(const_reverse_iterator pos, R&& range);Note
Note on prepend ordering: When prepending an iterator pair or range, elements are inserted in their original order, not reversed. Prepending {0, 1, 2, 3} to {4, 5, 6} produces {0, 1, 2, 3, 4, 5, 6}, not {3, 2, 1, 0, 4, 5, 6}. This applies to prepend_range and the iterator-pair overloads of insert/prepend.
For constructing elements directly without a temporary:
template <typename F, typename... Args>
reference generate_back(F&& func, Args&&... args);
template <typename F, typename... Args>
reference generate_front(F&& func, Args&&... args);The callable func is invoked with args... and the result is placement-constructed directly into the buffer. These functions are non-constexpr and also have not been tested.
void clear() noexcept; // removes all elements, keeps allocation
void rclear() noexcept; // equivalent clear from the reverse endvoid normalize() noexcept(/*conditional*/); // makes all elements contiguous in-place
void swap(bidirectional_vector& other) noexcept;
allocator_type get_allocator() const noexcept;
bool is_segmented() const noexcept;When the container is segmented, elements exist in up to two contiguous spans. Use contiguous_partition() to retrieve them directly:
// Returns std::pair<std::span<T>, std::span<T>>
auto [first_segment, second_segment] = v.contiguous_partition();
// Const version
auto [first_segment, second_segment] = std::as_const(v).contiguous_partition();The second span is empty when the container is not segmented.
bool operator==(bidirectional_vector const& lhs, bidirectional_vector const& rhs);
auto operator<=>(bidirectional_vector const& lhs, bidirectional_vector const& rhs);Lexicographic comparison. <=> is provided when T satisfies std::three_way_comparable or supports operator<.
Iterators satisfy std::random_access_iterator but not std::contiguous_iterator, because elements may wrap around the internal buffer. Arithmetic across the wrap boundary is handled transparently. Iterators from different instances are only comparable in a well-defined sense when pointing into the same container.
Forward and reverse iterators are distinct types (not merely std::reverse_iterator<iterator>), as the reverse iterator must navigate the buffer wrap in the opposite direction.
After several push/pop operations, the container may enter a segmented state where the logical sequence wraps around:
Buffer: [ B B B _ _ _ _ _ _ F F F F F F ]
^tail.back ^front
Here the logical sequence is [F F F F F F B B B] — the frontend segment starts at front and runs to the end of the buffer; the backend segment starts at the beginning of the buffer and ends at back.
In this state:
operator[]andat()still work correctly via index decomposition.- Iterators traverse the logical sequence transparently.
contiguous_partition()returns both segments asstd::spans.contiguous_split()/rcontiguous_split()return iterators pointing at the segment boundary.normalize()rotates elements in-place to make the entire sequence a single contiguous span, without reallocation (for nothrow-moveable types).
bidirectional_vector can serve as the storage layer for a fixed-capacity circular queue:
#include "bidirectional_vector.hpp"
template <typename T>
class ring_queue {
bv::bidirectional_vector<T> buf_;
public:
explicit ring_queue(std::size_t cap) {
buf_.reserve(cap);
}
void push(T value) {
if (buf_.size() == buf_.capacity()) {
buf_.pop_front(); // drop oldest element
}
buf_.push_back(std::move(value));
}
T pop() {
T val = std::move(buf_.front());
buf_.pop_front();
return val;
}
std::size_t size() const { return buf_.size(); }
};Because the buffer wraps naturally, frequent push_back + pop_front cycles do not cause repeated reallocation.
Unit tests are adapted from the std::vector test suite of libc++ (LLVM).
Platform support has been verified on Linux only.
| Compiler | Version(s) tested |
|---|---|
| GCC | 12, 15.2 |
| Clang | 14, 21.1 |
C++20 is the minimum required standard. The code contains a small number of Clang 14 compatibility workarounds (for older std::ranges::shift_left / shift_right behavior).
- Linux only. No testing has been performed on Windows or macOS.
- C++20 minimum. Backporting to C++17 requires removing or substituting concepts,
std::span,std::rangesalgorithms, and other C++20 features.
See source file header for details.