circular_buffer

Header-only C++20 ring buffer: one contiguous allocation, O(1) push/pop at both ends, overwrite-on-full.

#include <eqz/circular_buffer.hpp>

eqz::circular_buffer<int> buf(3); // capacity 3, size 0
buf.write(1);
buf.write(2);
buf.write(3);
buf.write(4);       // overwrites 1; contents are 2, 3, 4
int x = buf.read(); // 2, then pop

Features

• Header-only, C++20, constexpr with std::allocator
• Random-access iterator / const_iterator
• reverse_iterator / const_reverse_iterator
• Wrapping circular_iterator
• Allocator-aware (allocator_traits, POC*)
• Concepts on T and the allocator
• Ranges: begin / end work with std::ranges::sort and views
• std::initializer_list, assign, insert / emplace / erase / erase_if
• clear, resize, set_capacity / rset_capacity, sort, reverse, swap, <=>
• Queue API: write / read / try_*
• fixed_circular_buffer<T, N> — capacity fixed at compile time
• synchronized_circular_buffer<T> — mutex around push/pop/write/read
• C++20 module: import eqz.circular_buffer; (include/eqz/circular_buffer.cppm)

Quick start

./scripts/dev.sh test
./scripts/dev.sh sanitize
./scripts/dev.sh bench
./scripts/dev.sh examples

CMake:

add_subdirectory(circular_buffer)
target_link_libraries(your_app PRIVATE eqz::circular_buffer)

After install:

find_package(eqz-circular_buffer CONFIG REQUIRED)
target_link_libraries(your_app PRIVATE eqz::circular_buffer)

Capacity

eqz::circular_buffer<int> a(10);      // empty, capacity 10
eqz::circular_buffer<int> b(10, 0);   // ten zeros, capacity 10; std::iota works
eqz::circular_buffer<int> c{1, 2, 3}; // size == capacity == 3

push_back does not grow. Use set_capacity, resize, or assign to change capacity.

When full:

• push_back / write overwrite front()
• push_front overwrites back()
• try_push_* return false and leave the buffer unchanged

When capacity() == 0 the buffer is both empty() and full(). try_* fail; emplace_* throw std::length_error.

Layout

buff_ is the start of the allocation; limit_ is one past the end; first_ points at the front element; last_ points at the next write slot. Logical index i is first_ advanced i slots, wrapping at limit_ back to buff_. Unused slots are uninitialized. Empty and full both have first_ == last_; size_ distinguishes them.

capacity = 8, first_ at slot 5, size = 5

  0   1   2   3   4   5   6   7
[ e3  e4  --  --  --  e0  e1  e2 ]
^buff                 ^first     ^limit
            ^last

array_one() / array_two() expose the two contiguous segments (array_one() starts at first_). linearize() reallocates so first_ sits at buff_; then data() points at the first element and [data(), data()+size()) is contiguous. While the ring is wrapped, data() returns null.

Performance

Hot push_* / pop_* bump first_ / last_ around [buff_, limit_). A full push_* assigns in place instead of destroy + construct. Trivially destructible T skips per-element destructors. Trivially copyable T with an empty allocator copies constructed slots with memcpy at runtime.

./scripts/dev.sh bench

If CMake finds Boost, the bench compares eqz::circular_buffer to boost::circular_buffer on the same workloads (best of 5). It prints ns/op and geomean eqz/boost (< 1 means eqz is faster), grouped as hot/slide, scan, and structural. Boost is optional and is not a library or test dependency.

Coverage:

• hot/slide — overwrite window, queue/stack, both ends, slide after erase or set_capacity, fixed_circular_buffer vs the dynamic buffer at the same capacity
• scan — iterate (linear / wrapped / reverse), operator[], array_one / array_two, std::ranges::sort / find on wrapped and linear buffers
• structural — copy, move, mid insert, erase (middle / range / head / tail / erase_if), set_capacity / rset_capacity / resize, assign

fixed_circular_buffer<T, N> is in the suite to show it is not a faster hot path: it is the dynamic buffer with set_capacity deleted. assign/count and assign/iters lose several times on trivial T because fill is emplace_back, not Boost’s uninitialized_fill. That is a known startup/reset gap, not a slide regression — do not treat those ratios as a reason to add a second fill path. See docs/DESIGN.md.

CI job release-bench installs Boost and runs the suite on several compilers (Ubuntu GCC 13/Clang, Ubuntu arm64 GCC, macOS Apple Clang). Shared runners are noisy; those logs are a record, not a pass/fail gate on ratios. Keep-or-revert, how to read GCC vs Clang, and when to push an experiment branch: docs/BENCH.md.

On a Mac, Apple Clang numbers do not predict Ubuntu GCC. Closest local twin:

colima start                 # once
./scripts/dev.sh bench-gcc   # Linux GCC 13 + libstdc++ in Docker
./scripts/dev.sh fetch-ci-bench
./scripts/dev.sh compare-bench build/bench-gcc.txt build/ci-bench/bench-linux-x64-gcc13/bench.txt local-gcc ci-gcc

Iterators

• Linear iterators walk logical indices. end() has index size().
• circular_iterator wraps around size() elements. erase(it, it) is a no-op; use clear() to drop every element.
• push_* while not full keeps existing logical indices valid.
• Overwrite-on-full, insert, erase, set_capacity, and linearize may invalidate all iterators.

Layout of the repo

include/eqz/     public headers and .cppm
tests/           zero-dependency tests
benches/         micro-benchmarks
examples/        usage + Josephus
scripts/dev.sh   configure / build / test / bench / format / sanitize
docs/            coding standards, design, and bench process

See docs/DESIGN.md, docs/CODING_STANDARDS.md, and docs/BENCH.md.

License

MIT. Copyright (c) 2021-2026 equationzhao.