TODO:

• optimize out multiply operations
• iterators
• implement more methods for better compatability with std::vector
  • resize
  • assign
  • front
  • back
  • reserve (?)
  • capacity (?)
  • shrink_to_fit (?)
  • clear
  • insert
  • emplace
  • erase
  • pop_back

pvector

A header-only, persistent vector for C++17, mimiking std::vector interface. Implemented as a bit-mapped trie (à la Clojure's PersistentVector / Hickey-style HAMT vectors). pvector supports efficient structural sharing between "versions" of the container: operations that would normally require a copy (e.g. updating an element) instead only copy the path from the root to the affected node, reusing the rest of the tree with the original vector.

The whole implementation lives in a single header: pvector.hpp.

Implementation specifics / use-pattern considerations

Thread Safety	This implementation is not thread safe even for persisten operations. It is optimized for maxmal performance in single-threaded applications. Under-the-hood reference counting would require extensive use of atomic operations which would dramatically deteriorate the single-thread performance.
Use Patterns	This implementation is optimized for frequent updates of a single instance of pvector without jeopardizing the true persistent (copy-on-write) operations.
Memory Management	No optimizations for lowering the number of allocate/deallocate cycles are considered, in favour of minimizing the memory usage. It is inherent to the nature of this data structure to trigger many small allocations, thus, if one really needs the maximal performance it is advised to use a dedicated fast allocator. This implementation meets requirements of AllocatorAwareContainer.

Table of Contents

• Overview

• Template Parameters

• Persistence & Structural Sharing

• API Reference

  • Construction
  • Size / Emptiness
  • Accessors
  • front() / back()
  • set() — persistent update
  • emplace_back() / push_back()
  • resize()
  • clear()

• Complexity

• Usage Examples

• Building & Running Tests

Overview

pidhii::pvector<T, BranchFactor, Alloc> is a vector-like container backed by an internal tree of fixed branching factor (2^BranchFactor children per node, 32 by default). Values are stored only in the leaves; internal ("branch") nodes hold pointers to children.

Every pvector instance is reference-counted at the node level: copying a pvector (via the copy constructor or copy-assignment) is O(1) — it merely bumps the root node's reference count. Mutating operations (set(), operator[] (non-const), at() (non-const), emplace_back(), push_back()) check the reference count along the path to the target element and only duplicate nodes that are actually shared, using an in-place update otherwise. This gives pvector "copy-on-write" semantics similar to persistent data structures found in functional languages, while still allowing efficient in-place mutation of a uniquely-owned vector.

Template Parameters

template <typename T, size_t BranchFactor = 5, typename Alloc = std::allocator<T>>
class pvector;

Parameter	Description
T	The element type stored in the vector.
BranchFactor	Log2 of the number of children per internal node. Default 5 → 32-way branching (2^5).
Alloc	Allocator used for the underlying leaf/branch node allocations (rebound internally as needed).

Increasing BranchFactor reduces tree depth (and thus pointer-chasing) at the cost of larger nodes (2^BranchFactor pointers/elements per node) and proportionally larger copies when a node needs to be duplicated during a copy-on-write.

Persistence & Structural Sharing

• Copy construction / copy assignment — O(1). The new pvector shares the same root node as the source; only the root's reference count is incremented.

• Move construction / move assignment — O(1), takes ownership of the source's root and leaves the source empty (root == nullptr).

• set(i, value) (called on an lvalue) — returns a new pvector with the i-th element replaced, leaving the original untouched. Internally this copies only the leaf and branch nodes along the path from the root to index i; every other subtree is shared (its nodes' reference counts are simply incremented).

• set(i, value) (called on an rvalue, e.g. std::move(v).set(i, x)) — same semantics, but since the temporary is uniquely owned by the expression, this is used as an optimization hint; if the vector is not shared with anyone else, the update happens in place instead of copying.

• operator[] (mutable) / at() (mutable) / emplace_back() — these also transparently perform copy-on-write: if the path to the target element is uniquely owned (reference count == 1), the update happens in-place; if it is shared with another pvector instance, only the necessary nodes along that path are duplicated first.

API Reference

Construction

pvector();                          // empty vector
pvector(const pvector &other);      // O(1) — shares structure with `other`
pvector(pvector &&other);           // O(1) — takes ownership from `other`
pvector &operator=(const pvector &other); // O(1) — shares structure with `other`
pvector &operator=(pvector &&other);       // O(1) — takes ownership from `other`

Size / Emptiness

size_t size() const noexcept;   // number of elements
bool   empty() const noexcept;  // size() == 0

Accessors

const T &get(size_t i) const;               // throws std::out_of_range if i >= size()

const T &operator[](size_t i) const noexcept;
T       &operator[](size_t i) noexcept;     // triggers copy-on-write if shared

const T &at(size_t i) const;                // throws std::out_of_range if i >= size()
T       &at(size_t i);                      // throws std::out_of_range; triggers copy-on-write if shared

• get(i) — unambiguous, read-only getter with bounds checking.
• operator[] — equivalent to get() when called on a const vector; otherwise ensures unique ownership of the requested element before returning a mutable reference (same complexity as set()). No bounds checking.
• at(i) — equivalent to operator[] but always bounds-checked, throwing std::out_of_range for indices >= size().

front() / back()

const_reference front() const;   // throws std::out_of_range if empty()
reference       front();         // triggers copy-on-write if shared

const_reference back() const;    // throws std::out_of_range if empty()
reference       back();          // triggers copy-on-write if shared

Access the first / last element of the vector, respectively. Both throw std::out_of_range when called on an empty vector. The mutable overloads behave like operator[] / at(): they transparently perform copy-on-write if the accessed element's path is shared with another pvector instance.

pvector<int> v;
for (int i = 0; i < 10; ++i) v.emplace_back(i * 10);

int first = v.front(); // 0
int last  = v.back();  // 90

v.front() = -1;         // mutate first element (copy-on-write if shared)

set() — persistent update

template <typename U>
pvector set(size_t i, U &&x) const &;  // copy-then-update: original vector is untouched

template <typename U>
pvector set(size_t i, U &&x) &&;       // move-then-update: optimized in-place path

Returns a new pvector with element i replaced by x. Throws std::out_of_range if i >= size().

pvector<int> v;
for (int i = 0; i < 10; ++i) v.emplace_back(i);

pvector<int> v2 = v.set(3, 999);   // v is unchanged; v2[3] == 999

emplace_back() / push_back()

template <typename... Args>
T &emplace_back(Args &&...args);

void push_back(const T &x);
void push_back(T &&x);

emplace_back() constructs a new element in place at the end of the vector (growing the underlying tree as necessary — adding new levels/nodes when the current capacity is exceeded) and returns a reference to it.

push_back() is a thin convenience wrapper implemented in terms of emplace_back() (via copy or move construction of the argument, respectively), provided for familiarity/compatibility with std::vector.

pvector<int> v;
v.push_back(1);         // copies 1 into a new element
int x = 2;
v.push_back(std::move(x)); // moves x into a new element

int &ref = v.emplace_back(3); // constructs in place, returns reference

resize()

void resize(size_t size);                    // new elements are default-constructed
void resize(size_t size, const_reference val); // new elements are copy-constructed from `val`

Grows or shrinks the vector to contain exactly size elements:

• If size == size(), this is a no-op.
• If size > size(), new elements are appended at the end — either default-constructed (resize(size)) or copy-constructed from val (resize(size, val)) — growing the underlying tree with new levels/nodes as necessary.
• If size < size(), trailing elements (indices [size, size())) are destroyed and the tree is optimized to drop any now-unnecessary levels.

Like other mutating operations, resize() respects structural sharing: if the vector's nodes are shared with another pvector instance, only the nodes that actually need to change are copied first, leaving other pvectors referencing the same tree untouched.

Note that there is no variadic/forwarding overload — only these two overloads are provided, mirroring std::vector::resize.

pvector<int> v;
v.resize(10);        // 10 default-constructed ints (== 0)
v.resize(20, -1);     // grow to 20 elements; new ones are -1
v.resize(5);          // shrink to 5 elements, destroying the rest

clear()

void clear();

Empties the vector: all elements are destroyed and size() becomes 0 afterwards. Safe to call on an already-empty vector. Like other mutating operations, this only releases the nodes owned by this pvector instance — if the tree is shared with another pvector, the other instance's view of the data is unaffected (shared nodes are simply dereferenced, not destroyed, until their reference count drops to zero).

pvector<int> v;
for (int i = 0; i < 50; ++i) v.emplace_back(i);

v.clear();
assert(v.empty());

Complexity

Let N be the number of elements and B = 2^BranchFactor the branching factor. The tree has depth O(log_B N).

Operation	Complexity
size(), empty()	O(1)
Copy construction / copy assignment	O(1) (structural sharing)
Move construction / move assignment	O(1)
get(i), at(i) const, operator[] const	O(log_B N)
front(), back() (const)	O(log_B N)
at(i), operator[] (mutable), set(i, x), front()/back() (mutable) — unique ownership	O(log_B N) (in-place update of the path)
at(i), operator[] (mutable), set(i, x), front()/back() (mutable) — shared ownership	O(log_B N) (copy of the path, size proportional to B * log_B N)
emplace_back(), push_back()	Amortized O(log_B N)
resize() (grow or shrink by k elements)	O(k + log_B N) (amortized; may add/drop tree levels)
clear()	O(N) (destroys all owned elements/nodes)

Usage Examples

Basic usage

#include "pvector.hpp"
using pidhii::pvector;

pvector<int> v;
for (int i = 0; i < 100; ++i)
  v.emplace_back(i);

int x = v.at(42);       // bounds-checked read
v[42] = 100;             // mutable access (copy-on-write if shared)

Persistent updates ("functional" style)

pvector<int> original;
for (int i = 0; i < 10; ++i)
  original.emplace_back(i);

pvector<int> updated = original.set(5, -1);

// `original` is completely unaffected:
assert(original.at(5) == 5);
assert(updated.at(5) == -1);

Cheap copies via structural sharing

pvector<int> a;
for (int i = 0; i < 1000; ++i)
  a.emplace_back(i);

pvector<int> b = a;   // O(1): b shares a's internal tree

b[0] = 42;             // triggers copy-on-write only for the path to index 0
assert(a.at(0) == 0);  // `a` remains unaffected
assert(b.at(0) == 42);

Building & Running Tests

pvector is header-only — simply #include "pvector.hpp" and use the pidhii::pvector class template. No separate compilation is required for the library itself.

A GoogleTest-based unit test suite is provided in test_pvector.cpp, covering construction, element access (get()/at()/operator[]/ front()/back()), persistent set(), resize() (growing/shrinking, with and without an explicit value), clear(), copy/move/copy-assignment semantics and structural sharing, multi-level tree behavior at scale, and element lifetime correctness (constructor/destructor balance).

To build and run the tests (requires GoogleTest installed on the system):

g++ -std=c++17 -Wall -Wextra -g test_pvector.cpp -o test_pvector -lgtest -lgtest_main -lpthread
./test_pvector

For extra confidence, the tests can also be built with AddressSanitizer and UndefinedBehaviorSanitizer enabled:

g++ -std=c++17 -Wall -Wextra -g -O0 -fsanitize=address,undefined \
    test_pvector.cpp -o test_pvector_asan -lgtest -lgtest_main -lpthread
./test_pvector_asan