Terminology first, since both words are overloaded:
“Concurrency” does not imply threads.
Several transactions can be open on one thread.
“Consistency” does not imply strict serializability. Weaker levels exist, and each store here names the one it targets as a compile-time isolation_k rather than leaving you to infer it.
Headers group as:
basic_* → Cores. Own their memory, no transactions, one thread. ├─ basic_vector<T, Alloc> ├─ basic_avl_tree<T, Comparator, Alloc> ├─ basic_wb_tree<T, Comparator, Alloc> # also `rank` and `select` ├─ basic_hash_table<T, Hash, Equals, Alloc> # grows, iterates, rehashes ├─ basic_flat_set<T, Comparator, Kit, Alloc> # sorted, one allocation, searched a row at a time ├─ basic_ring<T, Alloc> # first-in first-out, capacity fixed at `make` ├─ basic_hash_index<T, Index, Hash, Alloc, Kit> # keys to record positions, capacity fixed, no tombstones ├─ basic_fixed_pool<T, Index, Alloc> # records taken and vacated by index, handles that go stale ├─ basic_growing_pool<T, Index, Alloc> # the same in chunks that never move, read beside its growth └─ intrusive_list<Index> # first-in first-out through the records' own `next` Immutable, built once and never written ├─ immutable_b_tree<T, KeysPerRow, Kit, Alloc> # keys on every level ├─ immutable_splus_tree<T, KeysPerRow, Kit, Alloc> # every key in the leaves, separators above ├─ immutable_elias_fano<T, Alloc> # non-decreasing integers in a few bits apiece └─ immutable_packed_array<T, Alloc> # integers as distances from a base, one width each atomic_* → Pinned core. Fixed capacity, atomic per slot, callback reads. └─ atomic_hash_table<T, Hash, Equals, Alloc> # the one type that runs on a GPU ↑ ::adopt(std::move(growable).release()) ↓ ::adopt(std::move(pinned).release()) atomic_intrusive_stack<T, Ref> → any thread pushes, one takes all, no capacity *_store → 2-phase commit, watch and CAS. ├─ monotonic_store<Core> # one visible version per key ├─ snapshot_store<Core> # every version a live reader can still name └─ reference_store<T, Comparator, Alloc> # the same contract over `std::set`, kept as the oracle ↓ either of the first two wraps a core; either of these wraps a store ├─ locked_store<Store, Mutex> # one lock spans a whole commit └─ partitioned_store<Store, Hash, Mutex, N> # one lock per partition, one shared commit order transaction_group<Stores...> → One 2-phase commit spanning several stores
The Writers column of the table in What’s Inside names how many threads may write, and the reader rule follows from it rather than standing beside it: a core’s const methods are safe from any number of threads only while no thread is writing, since a probe reads slot metadata and node links a write is midway through changing.
The shape that gets this wrong most often is a cache behind a mutable member, filled on what its caller calls a read — a reader-writer lock held in shared mode admits several such calls at once, and each of them is a writer as far as the container is concerned.
Growth is the other half of the rule.
A core that can grow repoints the regions every live slot reference and every node pointer has already cached, so a container a second thread can reach must either be pinned at a capacity nobody exceeds, or reached through a wrapper that excludes. basic_growing_pool is the one core whose growth repoints nothing: it adds chunks and never moves a record, so readers by index or handle need no claim while its one writer takes, vacates and grows.
Both wrappers take their mutex as a template parameter, and that mutex takes two of its own: the reference its word is owned through, and the policy a waiting core follows.
The pinned table takes the same two directly, since its slot lock is the mutex it has.
A deployment that knows its hardware names both: a reference whose conditional add decides an acquire in one instruction, and a stall its cores actually have.
One that does not pays nothing for the question.
Transactions and thread-safety are two independent axes, not one ladder.
A wrapper takes its mutex per call, not across a transaction: stage and commit each take it and drop it in between, and only a group holds it from its validation to its publication.
What carries the inner store’s level across that gap is the reservation staging made, since no other transaction can claim those keys until this one publishes or unwinds.
A store in no order gives its reader no stamp to hold, so a monotonic reader spanning partitions can catch a commit half-applied and only Read Committed survives — but a snapshot reader answers at its own stamp, and every partition belongs to one order, so it keeps Snapshot across all sixteen.
Every container publishes what it promises as isolation_k, so the level is checkable rather than folklore. atomic_hash_table has no transactions at all — it offers per-operation atomicity, which is a different product, and is why it is not a *_store.
status_t reports out_of_memory_heap_k == ENOMEM, invalid_argument_k == EINVAL, key_not_found_k == ENOENT and others, and is [[nodiscard]] on every mutating API.
The baseline reference design, and the yardstick the tree containers are held against — it runs the same test suites they do.
Updates group into transactions that stage and roll back before committing, which is what lets inter-dependent updates span several stores.
Reads are consistent at the Monotonic Atomic View level, so a transaction never sees another’s partial update.
That is weaker than Snapshot Isolation: there is no guarantee that every read within one transaction sees the same snapshot.
It keeps a version per key all the same, dated by a generation rather than by a shared commit stamp, which is why a watch is re-resolved at commit instead of compared against one. snapshot_store is the sibling that does make that guarantee, and the section below states what it costs.
Rarely called by its full name, the AVL tree is the simplest clean self-balancing binary search tree, from 1962. basic_avl_tree<value, comparator, allocator> is an ordered store in the shape of std::set or std::map.
Standard libraries usually pick Red-Black trees; AVL balances more rigidly, trading slightly slower updates for faster lookups.
Its API differs from the STL where exception-free reporting demands it:
insert() returns std::pair<iterator, bool>, as the STL does.
basic_wb_tree balances on subtree sizes rather than heights, using Δ=3 and Γ=2 — the only proven integer solution, per Hirai and Yamamoto.
Storing sizes buys order statistics: select(k) finds the k-th smallest and rank(x) finds a key’s position, both in O(log n).
That is what pagination, percentiles and quantiles need, and it is the one thing the AVL tree cannot offer.
Expect depth around 1.88 log₂(n) against AVL’s 1.44, in exchange for O(1) amortized rotations per update.
basic_flat_set is an ordered set in one contiguous allocation, growable and allocator-aware like basic_avl_tree, differing only in where elements live.
Inserting and erasing shift the tail, so it suits a few hundred elements rather than millions, in exchange for a search that reads adjacent memory and allocates nothing.
That search is the same row search the immutable trees below use, wherever the element is a row_searchable_key ordered by less_t, and a plain binary search otherwise — basic_flat_set takes the kit as its third template argument.
It answers the same ordered_collection surface the trees do — bounds, ranges and half-open erasure — so the shared suites hold it to the same contract.
basic_ring is a first-in first-out queue over one allocation whose capacity is a power of two fixed at make, for batching and read-ahead.
Two 32-bit counters of pushes and pops wrap together, so their difference is the size and a full ring is told from an empty one without a spare slot.
Both are built once from a sorted span and never written again, so any number of threads may read one at once with no synchronization at all.
Both search a row at a time rather than a key at a time — a row being a span wide enough to be worth one vectorized pass, 512 bytes by default, which is default_row_bytes_k. row_layout.hpp says what a key may be and where each one sits in a row; row_search.hpp says how a row is searched.
immutable_b_tree stores nodes breadth-first with implicit children: node i holds one row of B keys and its children are nodes i*(B+1)+j+1.
A lookup reads one row per level and the rank adds up as the descent goes, with no subtree sizes stored.
immutable_splus_tree keeps every key in sorted leaves and copies separators onto the levels above.
A lookup lands on the leaf whose position is the rank, so select is an index into the leaves.
Every kit the compiler can emit is compiled into the same artifact, each under its own target attributes, so no global instruction-set flag is needed. detect_row_kit() probes the processor once and visit_row_kit hands the answer over as a type, so a tree instantiated over it calls its kit with no table and no branch per key.
visit_row_kit(detect_row_kit(), [&](auto kit) { using tree_t = immutable_b_tree<std::uint64_t, 64, decltype(kit)>; // …built once, then read from any number of threads});
Keys may be 32- or 64-bit of either signedness, or 16 bytes ordered as memcmp.
A 16-byte key is stored either interleaved or split into a column of high words and a column of low words, the low column read only where a high word ties.
immutable_b_set and immutable_splus_set hold bare keys; immutable_b_map and immutable_splus_map pair each key with a value.
A map keeps the rows byte-identical to its set twin and puts the values in one array the rank indexes, so every kit still loads a row of nothing but keys, and mapped_at(rank) costs one further cache line.
immutable_elias_fano keeps non-decreasing integers - the offsets of variable-length rows, say - in at most 2 + ⌈log₂(universe / count)⌉ bits apiece, and select(i) reads the i-th one back in constant time.
The low bits of every value are packed side by side and the high bits are stored in unary, with every 256th set bit’s position sampled, so a select jumps to a sample and counts a handful of words. make takes the values whole, or pulls them in order through a callback, so a column of offsets streams in from storage without ever sitting in memory at full width.
immutable_packed_array keeps unsigned integers between a base and a maximum as their distance from the base, in bit_width(maximum - base) bits apiece, and array[i] reads the i-th one back in constant time.
Values that all equal the base cost no words at all, so a column of commit stamps coded against the oldest live snapshot is free once nobody reads below it. immutable_elias_fano keeps its low parts in one, based at zero. save writes a three-word header and the packed words, and immutable_packed_array_view reads them in place from borrowed bytes at any alignment, so a memory-mapped file is read without a copy.
monotonic_store<Core> adds two-phase commit, watches and CAS on top of any key-addressable core. monotonic_avl_set, monotonic_avl_map, monotonic_wb_set and monotonic_wb_map are the aliases you’ll name directly. monotonic_hash_set and monotonic_hash_map back the same store with the open-addressed table, which supplies no ordering, so bounds, ranges and order statistics are gated out of those instantiations at compile time.
Which version a reader sees is decided by one number, stamped when a transaction commits.
A version that has not committed carries no stamp, so it is invisible to readers and cannot make anyone else’s validation fail — a transaction that stages and then rolls back costs its peers nothing.
Two writers on one key are ordered by their stamps, and the later one wins.
That is a lost update, which this level permits: Monotonic Atomic View constrains what a reader observes, not what two writers do to each other, and a level that is available under partition provably cannot prevent it.
A writer that needs the first commit to win must watch() the key, or use a snapshot container, where the write set is validated whether you ask or not.
find never records what it read, here.
A read set is memory, and a read that allocates is a read that can fail, so on this engine the recording variant is a different name:
_ = transaction.find(key, on_found, on_missing); // answers, and records nothing_ = transaction.find_and_watch(key, on_found, on_missing); // records, and can report out of memory
Both return status_t, because a read that cannot write down what it read has to say so where it happened rather than poisoning the transaction silently until commit. snapshot_store at serializable_k and above needs no second name: every read records, and every read reports.
An erase leaves a tombstone that readers skip, and vacuum() is what returns that space:
expected<std::size_t> const reclaimed = store.vacuum(); // everything no reader can nameexpected<std::size_t> const window = store.vacuum(lower, upper); // ordered cores, one slice at a time
snapshot_store<Core> is the sibling that fixes a transaction’s reads to one instant, and it is where multi-version concurrency control is at its most literal here: a transaction draws a snapshot when it opens, every read is answered from the newest version at or below that snapshot, and a writer never overwrites what a reader can still name.
It rebinds the same cores, exports snapshot_avl_set, _avl_map, _wb_set, _wb_map, _hash_set and _hash_map, and publishes isolation_k == snapshot_k.
A repeated read returns what it first saw, a repeated range admits no phantoms, and neither holds in its sibling.
The same template answers at three levels, selected by a second parameter rather than by a second implementation, and each has aliases of its own:
snapshot_store<Core> // isolation_k == snapshot_kserializable_store<Core> // reads validated toostrict_serializable_store<Core> // and a commit waits for its own publicationserializable_avl_map<Key, Value> // and `_avl_set`, `_wb_*`, `_hash_*`strict_serializable_avl_map<Key, Value> // the same six for the top rung
Versions are kept as ordinary entries keyed by (key, generation) rather than chained off one entry, on ordered and unordered cores alike.
The hash core still hashes the bare key, so every version of a key shares one probe run and a lookup walks that run instead of stopping at the first match.
Reclamation is the other half of multi-version concurrency control, and the whole of it here: old versions are freed against a low-water mark that sits at the oldest open snapshot, so it can never pass a snapshot somebody still holds, and it advances as soon as the oldest reader leaves rather than waiting for the last.
Pruning happens on every commit, and vacuum() reaches the keys nobody writes again.
There is no background thread and no epoch registry. clear() refuses while a reader is open rather than dropping versions out from under it.
Range writes publish under one stamp, so a reader on an older snapshot sees all of a range erase or none of it. update_range builds new versions rather than rewriting the visible one, which is what open readers make unsound. select and rank descend on the weight-balanced tree’s augmented count, exact at the newest commit — a reader at an older snapshot gets the merged walk instead, because one number per node cannot answer for an unbounded parameter.
What it costs, on an AVL core over mapping<key, int>:
monotonic_store
snapshot_store
Resident per key, one version
80 B
72 B
Each retained older version
48 B chain node
72 B, a full entry
Read of one key
one chain head
the key’s whole run
At rest it is the cheaper of the two, because a key carries no chain-head pointer and no per-entry allocator.
It becomes the more expensive one exactly when a long-lived reader pins history — and on the hash core a pinned version occupies a real slot, so it lengthens the probe runs of its neighbours as well.
With no transaction open the low-water mark sits at the newest commit and the whole version tail is freed on the next write, so a store nobody is reading costs what its sibling costs.
hash_set<key> and hash_map<key, value> are open-addressing containers with linear probing.
They differ from google::dense_hash_map and tsl::robin_map by not reserving sentinel key values for tombstones, by unpacking keys and values into disjoint arrays, and by carrying two bits of metadata per slot rather than a byte.
Keys and values live in separate regions, so a lookup that only compares keys never pulls values into cache — which is most of them, since a miss touches no value at all.
Thirty-two slots share one 64-bit header holding two parallel bitmasks, encoding free, deleted, populated and locked in two bits each.
Sixty-four bits is the widest atomic every target supports, which is what lets a whole bucket header move in one instruction.
Growing repoints the key, value and header regions that every live slot reference has cached, so a table that can grow can never be read concurrently.
The type system enforces that rather than a sentence: two types, neither of which includes the other’s header. basic_hash_table grows, iterates and rehashes; atomic_hash_table is pinned and atomic over the slot each operation touches.
What passes between them is the allocation itself — a hash_storage — so the hand-off is a move of a value rather than one table reaching into the other:
_ = growable.reserve(1u << 20); // pin the capacity firstauto pinned = atomic_hash_map<key_t, value_t>::adopt(std::move(growable).release());_ = pinned.find(key, [](auto const &slot) noexcept { use(slot.value()); });if (failed(pinned.emplace(key, value))) report_full(); // a pinned table can fill upauto compacted = hash_map<key_t, value_t>::adopt(std::move(pinned).release()); // iterators return
Every operation on the pinned table is atomic over the slot it touches: it takes that slot by setting both its bits with a fetch_or and releases it by posting the xor of the difference to the desired state, which reads nothing back, so neither path needs a compare-and-swap loop.
It is not lock-free, though — fetch_or spins until it wins the slot, so a thread descheduled while holding one blocks every other prober that walks onto it.
No global lock and no reallocation is what the pinning buys; a stalled thread stalling its neighbours is what it does not.
Reads take a callback rather than returning a reference or an iterator, since both would dangle the moment another thread erased the slot.
Tombstones only accumulate while pinned, because compaction needs a rehash — deleted_count() is what says it is time to hand the storage back.
Readers take the slot lock like writers do.
A reader that merely loaded the header would be unsound, and measurably so: the two bits per slot cannot distinguish “untouched” from “locked, rewritten and unlocked”, because a completed write cycle restores exactly the bits the reader first saw.
Adding a per-bucket version counter would fix it and would cost half the slots per bucket, which is not worth breaking the one-warp-per-bucket geometry for.
Order-dependent operations are absent by construction: there is no range, erase_range, lower_bound or select.
smashtable/basic_hash_index.hpp
basic_hash_index is the same layout serving another job: a fixed-capacity map from 4-, 8- or 16-byte keys to the positions of records kept elsewhere, such as a fixed pool’s.
Its keys sit in the keys region, so a probe compares a window of them without loading a record, and a key may repeat, since it is often a hash of something longer: find takes a check that reads the record behind each match, and erase names the exact position.
A tombstone would make every later probe walk past the erased slot until a rehash, which a fixed-capacity index never runs, so an erase shifts the rest of its run back over the hole instead.
Every key stays reachable from its home, the deletion bits stay zero, and capacity is at most half the slots, so a run always ends at a free one and a table under constant churn probes no further than a fresh one.
API
Types
hash_table_iteratorForward iterator for hash tables using simplified slot-based addressing.
Inherits the three region pointers and the slot index from hash_slot_ref, and adds a counter of unvisited slots. Implements std::forward_iterator_tag for sequential traversal.
slots_remaining counts the slots left to visit and reaching zero is the end, which is what is_end and isnt_end report and what the end_sentinel_t comparisons consult. Two iterators compare equal when they name the same slot of the same keys region. advance steps to the next populated slot and must not run at the end, while skip_non_populated walks past free, deleted and locked slots until a populated one or the end is reached.
Fields
slots_remaining
offset_t
no_augmentation_tMarks a tree that keeps only size, leaving nodes byte-identical to an unaugmented build.
std::allocator would serve, and costs <memory>, some fifty thousand preprocessed lines, in headers that want nothing else from it. Exhaustion is reported by returning null, which is the shape every caller here already checks, rather than by an exception nothing would catch.
less_tTransparent ordering and equality, so a container needs no <functional>.
Both are heterogeneous - the is_transparent tag is what lets a lookup compare a key against something merely comparable to it, without materializing a key first - which is the only property the containers here relied on std::less and std::equal_to for.
hashThe hash a container uses unless told otherwise.
Deliberately not a forward to std::hash: that would drag <functional> into every header, and the point of a named trait is that an unhashable key says so at compile time. Hashing the bytes of an arbitrary type instead would be worse than an error - padding, or an equality that ignores some field, would give two equal keys different hashes and quietly lose lookups.
moving_pointerReads a contiguous run as rvalues, so a bulk write moves its staged copies rather than copying them again.
reversed_iteratorWalks a bidirectional iterator_type_ backwards, standing one position past the element it reads, so the reversed begin is the forward end.
Implementation vocabulary rather than a tag: a caller picks between these by naming a verb, and the three verbs share one staging helper that this tells apart.
Values
keeps_the_incumbent_k
The element already stored stays, and the newcomer is dropped.
takes_the_newcomer_k
The newcomer takes the key, overwriting what was stored under it.
refuses_the_newcomer_k
Neither is stored: a key arriving over one already there refuses the whole batch.
algebra_tWhich members of the two sides a walk keeps.
Two parallel 32-bit bitmasks - population, deletion - give each slot two bits, four states.
Slot State Encoding
Each slot's state is determined by corresponding bits in both masks:
00 (populations=0, deletions=0): Free slot, never used or fully freed
01 (populations=0, deletions=1): Deleted slot, tombstone from lazy deletion
10 (populations=1, deletions=0): Populated slot with valid key-value pair
11 (populations=1, deletions=1): Locked slot, temporarily held for atomic operations
lanes exposes the two 32-bit halves separately - populations has a set bit for every populated or locked slot, deletions one for every deleted or locked slot. u64 views both at once, which is what enables atomic operations on the entire header (2 × 32 bits = 64 bits).
Caps the load factor at 75%, through a 4/3 multiplier, so linear probing cannot degenerate, and rounds every slot count up to a power of two so the modulo is a bitwise AND.
The 75% load factor strikes a balance between memory efficiency and probe length:
Too high (>85%): Linear probing degrades into long search chains
Too low (<60%): Wastes memory without significant performance gain
75%: Industry standard, keeps average probe length under 2 hops
raw carries the widened count itself. The primary constructor budgets for a target element count and applies the load factor, while from_slots takes the slot count directly, for callers that already sized the storage. is_addressable reports whether the probe masks can address the count, which requires a power of two.
A request too large to round up to a power of two keeps unrepresentable_k, which is not a power of two and therefore not addressable, so the factories refuse it instead of silently handing back the smallest possible table.
Fields
unrepresentable_k
std::size_t
A count that no power of two covers, and which is_addressable therefore rejects.
Computes element types, sizes and alignment requirements from the element and hasher parameters, and takes the hasher's return type as the offset_t that indexes slots.
Provides three views of a stored element:
value_t: mutable reference pair mapping<key const&, mapped&> for iteration.
value_const_t: immutable reference pair mapping<key const&, mapped const&> for lookups.
value_copy_t: owned pair mapping<key, mapped> for extraction.
Probing advances slot_ by one, so a step costs a single integer increment rather than three pointer recomputations. Sets carry no values region and leave values_ null.
keys_, values_ and headers_ are the bases of the three regions, the first two indexed by the absolute slot_ and the last by the bucket that owns it. The aliases restate the layout's own key, value, element and offset types, plus dereference_t, which is the element view for maps and a key reference for sets.
header_ref and mask_in_bucket resolve the owning header and the single bit inside it; key, key_ref, value and value_ref reach the two payload regions; the is_ and mark_ families read and write the slot's two bits. Locking is what a threaded reference overrides, so here lock, unlock and try_lock collapse to nothing.
Fields
has_values_k
bool
hash_window_slots_tThe slots of a window a probe may still match, and whether a free slot ends the probe there.
icelake_row_kit_tThe Skylake kit plus VPOPCNTQ, counting eight words of a bit vector per instruction, and a PDEP every such core runs in hardware, unlike the microcoded one of the Zen 2 parts the Haswell kit also serves.
v128_row_kit_tWebAssembly SIMD over two 64-bit or four 32-bit keys per load; unsigned 64-bit order by flipping the sign bit, since the instruction set compares 64-bit lanes only as signed.
Classatomic_hash_tableA fixed-capacity open-addressed table whose operations are atomic over the slot they touch, through per-slot spin locks, and over nothing wider.20
Built by adopting an allocation someone else sized, which is what guarantees the capacity was reserved before any thread could observe the table.
Warnings
Not lock-free. A slot is held between lock and unlock, so a thread stopped in between blocks every other prober that reaches that slot; see the file header.
value_tEvery stored element: the key itself for a set, a mapping of both halves for a map.
push_chainPushes the records linked from newest down to oldest, whose next is overwritten, in one step, so the taker meets them together and in that order.
template <typename value_type_,
typename comparator_type_>
class basic_avl_node
Provides static methods for all tree operations: search, insertion, deletion, and traversal. All operations are exception-free and noexcept.
Implementation Notes
AVL trees are self-balancing binary search trees where the height difference between left and right subtrees is at most 1. This "node" class implements the core tree logic including rotations and rebalancing, but doesn't participate in memory management or promise anything all-or-nothing - basic_avl_tree does both.
Features:
Never throws exceptions, even on allocation failure
Supports random sampling within ranges for statistical operations
All methods are static and work on raw node pointers for flexibility
Layout: payload is the stored entry, left, right and parent the links, and height the longest downward path to a leaf. The root carries the biggest height in the tree, a non-NULL node has at least one, and zero occurs only in the uninitialized detached state - which makes 1 << height an upper bound on the branch size.
node_placement_tWhat a walk that may create a node did with the key it was handed.
Not an expected, which holds a value or a reason and never both: a refused build still owns every node it made, and whoever asked for it has to free them.
Fields
root
node_t *
Everything that was built, which the owner frees whether the build finished or not.
Subtree with all elements ordered before the split key.
right
node_t *
Subtree with all elements not ordered before the split key.
Classbasic_avl_treeException-free AVL tree container with ordered storage similar to std::set, managing allocation and providing high-level tree operations with status-based error handling.54
This AVL tree provides an STL-compatible interface:
Bidirectional iterators for in-order traversal (begin/end/rbegin/rend)
Returns status_t for some operations instead of throwing exceptions
Supports heterogeneous lookups when comparator defines is_transparent
Provides both insert (fails if exists) and upsert (always succeeds) semantics
Allows custom allocators for all internal nodes
Iterator invalidation: only iterators to erased elements are invalidated
Callback-based APIs are also provided for convenience (find, range, equal_range). The tree maintains O(log n) height through automatic rebalancing after modifications.
Entry Constraints
Entries stored in the tree must be comparable using the provided comparator. They must also be noexcept move-constructible and assignable to ensure safety. When dealing with bulk-insertions of non-copyable types, make sure to use a moving iterator, like the std::move_iterator.
Insert Strategies
Four distinct modification strategies with different failure handling:
Method
Key Exists
Returns
Use Case
insert()
Fails
invalid_arg_k
Strict, ensure key is new
insert_if_missing()
Skips
success_k
Lenient, insert only if absent
upsert()
Overwrites
success_k
Always succeeds, insert or overwrite
update()
Fails
key_not_found_k
Strict, key must already exist
key_tExtracts a map's key_type through SFINAE, or falls back to value_type for a set.
Upserts elements from initializer list (insert or update semantics).
Overwrites existing entry if key exists (upsert semantics).
Parameters
comparable
in
Entry to upsert (moved into the tree).
first
in
Beginning of range to upsert.
last
in
End of range to upsert.
tags
in
Markers promising something about the range, such as assume_sorted_t.
ilist
in
Initializer list of entries to upsert.
Returns
The node the entry now lives in, and whether it was made or matched.
Statuses
refused_k The key is absent and the allocator refused its node, so nothing was stored.
Any status an element's copy returns passes through unchanged.
Notes
With assume_sorted_t : Range must be sorted (ascending order).
With assume_unique_t : Range must have no duplicate keys with existing tree; violating it is undefined behavior.
Atomicity: every failure happens while the staging tree is built, leaving this tree unchanged; the merge itself only relinks nodes, so it cannot fail part-way. Duplicate keys are UPDATED during the merge, not skipped.
Updates elements from an initializer list (all keys must exist).
Builds a temporary tree from the range, validates all keys exist, then updates in one step. On allocation failure or any missing key, this tree remains unchanged.
Parameters
first
in
Beginning of range to update.
last
in
End of range to update.
tags
in
Markers promising something about the range, such as assume_sorted_t.
Swaps tree structure, size, comparator, and (if propagating) allocators. For non-propagating allocators (when propagate_on_container_swap is false), the allocators must be equal, otherwise invalid_argument_k is returned.
Parameters
other
inout
Tree to swap with.
Statuses
invalid_argument_k The allocators are unequal and do not propagate on swap.
eraseErases a single entry matching the given comparable.
No-op for AVL tree implementation. Provided for API consistency with other containers. Doesn't guarantee subsequent insertions won't fail with "out of memory".
Suggested capacity (ignored for AVL trees).
Notes
This is a no-op because AVL trees don't support reserving capacity efficiently.
clearRemoves all elements from the tree and frees their memory.
Merges a single extracted node into this tree, deallocating it if the key exists.
Elements with keys that already exist in this tree are deallocated (not kept in source).
Parameters
other
inout
Tree to merge from. Will be empty after merge.
Notes
Unlike std::set::merge(), nodes with duplicate keys are deallocated rather than remaining in the source container. This ensures no memory leaks in a noexcept context.
Complexity: O(m log n) where m = other.size(), n = this.size(). For disjoint trees, use merge(other, assume_unique) for faster O(m log(n/m+1)) or O(m+n).
Complexity: O(m log(n/m + 1)) for unbalanced sizes, O(m+n) for similar sizes.
Unlike std::set::merge(), a node with a duplicate key is deallocated rather than being returned. This ensures no memory leaks in a noexcept context.
Warnings
If precondition violated (duplicate keys exist), behavior is undefined.
splitSplits the tree at a given key into two trees.
The rank search goes through row_kit_type_ when the element is a row_searchable_key ordered by less_t, and through a binary search with the comparator otherwise.
key_tThe key half, which for a set is the whole element.
Adds every element of [ first, last ), refusing the batch over any taken key.
All-or-nothing over this set from the first element on, a taken key included: the whole range is staged and checked before the merge absorbing it allocates anything.
Writes every element of [ first, last ), replacing any equivalent element.
All-or-nothing over this set from the first element on; an element already here is overwritten by the merge, which moves rather than copies once its buffer is secured.
Statuses
Any status an element's copy returns passes through unchanged.
insert_if_missingAdds every element of [ first, last ) this set lacks, leaving incumbents alone.
All-or-nothing over this set from the first element on: the staging set holds every element before the merge begins, and the merge makes its one allocation before it moves anything.
Statuses
Any status an element's copy returns passes through unchanged.
Classbasic_growing_poolRecords of value_type_, taken and vacated by index, growing chunk by chunk up to a limit without moving a record, and readable by index or handle from other threads while the one owner grows it.16
takeTakes a free record, as its last holder left it, growing the pool when none is free and it may, or answers absent_k when it may not or the allocator refuses.
makeA pool of at least capacity free records, rounded up to a power of two and clipped to capacity_limit, which a take finding none free grows chunk by chunk up to that limit.
Each later key in the run moves into the hole when the hole lies between its home and its slot, so every key stays reachable from its home without a tombstone.
A store that decorates its elements - wrapping them in version metadata, say - needs the equality restated alongside the hasher, since both must address the decorated shape.
basic_hash_tableDefault constructor, avoiding memory allocations, accepting a pre-constructed hasher functor, an equality operator, and the allocator state.
A table whose equality separates versions of one key files them all in one probe run, because the hasher still peels to the bare key. Finding one of them is not finding the newest one.
Parameters
wanted
in
Hashable and comparable with key object.
call
in
Receives each const_slot_ref_t and returns walk_control_t. Must be noexcept.
probe_to_insertProbe optimized for insert of a unique key.
A hint names a position, and an open-addressed table decides position by hashing the key, so there is nothing a caller could usefully hint at. Declaring it deleted rather than omitting it turns a port from std::unordered_map into a signposted error instead of an unexplained missing member. Use emplace, or probe_to_upsert for finer control.
Inserts every element of [ begin, end ), refusing the batch when a key is already present here.
All-or-nothing over this table from the first element on, a taken key included: every key is checked against the table before the first of them is written.
Files an element under its own key, replacing whatever key compared equal to it.
All-or-nothing over this table from the first element on. Growth is secured before any slot is written, and after it a bounded probe cannot run out: reserve_more leaves at least a quarter of the slots free, and both probes walk every slot before giving up. An element that can refuse its own copy is duplicated in full before the first of them lands, because a slot once written cannot be un-written without leaving a tombstone that moves later probes.
Best-effort, matching the void shape of the standard containers: a refused allocation leaves the table exactly as it was, with every element still reachable. Call force_resize when the outcome has to be known.
deallocateDeallocates all the memory used by the container.
A request too small for what is stored is raised to what the current size needs, so rehash(0) compacts rather than emptying the table into a layout with no slots at all.
Statuses
failed_k The new buffer could not be allocated, leaving this table untouched.
move_to_newCreates a new buffer of the requested capacity and rehashes the present data into it.
Move-constructors are used, avoiding copies, and this table is left deallocated.
Returns
An unallocated table when the allocator refused, nothing was asked for, or the request has fewer slots than this table has elements, leaving this one untouched.
copy_to_newDuplicates the table, reusing the exact bucket layout when the elements are trivial.
position names the stored or the conflicting element, and the end when nothing was stored. outcome says which of the four happened, so a key already taken, a probe with no slot left and an allocation the table could not make are all distinguishable from one another, without comparing the iterator against end().
template <typename value_type_,
allocator_of<value_type_> allocator_type_ = default_allocator<value_type_>>
class basic_vector
Provides RAII memory management with explicit failure handling, unlike std::vector.
Template Requirements
value_type_ must be nothrow move-constructible, and nothrow default-constructible to be resized.
For types with potentially throwing constructors, provide a static .make() method returning expected<value_type_> to enable exception-free construction via emplace_back().
Inserts value at position, shifting the elements at and after it up by one.
Linear in the elements after position, which is what a sorted run of a few hundred entries costs and why an ordered container built on this stays small.
Parameters
position
in
Index the new element takes, at most size().
value
in
Element to insert (moved into the vector).
Returns
Always success, since nothing here can refuse.
eraseRemoves position's element, handing it to callback, then shifts the rest down.
If propagate_on_container_swap is false (e.g., std::allocator), allocators must compare equal. Attempting to swap vectors with unequal non-propagating allocators returns invalid_argument_k and leaves both vectors unchanged.
Stores subtree size for O(log n) order statistics and O(1) amortized rebalancing.
Rebalancing Parameters
Δ = 3 is the rotation threshold: rebalance when weight(left) > 3 × weight(right) or vice versa, with weight = size + 1. Γ = 2 selects the rotation type: a single rotation when weight(heavy.inner) < 2 × weight(heavy.outer).
These are the only valid integer parameters, proven in Coq by Hirai and Yamamoto in 2011, and are exposed as delta_k and gamma_k.
Layout: payload is the stored entry, left and right the links, and size the number of nodes in the subtree rooted here - invariant size=1+size(left)+size(right), which is what makes select and rank logarithmic.
Augmentation
An augmented tree keeps augmented_size next to size, holding the number of entries in the subtree for which augmentation_type_::augmented_count returns 1. Because that count is read off the entry, every rotation, join, and split restores it from the moved node's own entry and its two children. An entry whose count flips while it sits in the tree is repaired by refresh_augmentation, which rewalks only the root-to-entry path and may be called any number of times per write - one wrapper operation is free to retag several entries.
node_placement_tWhat a walk that may create a node did with the key it was handed.
Hirai and Yamamoto state the invariant over size+1; comparing raw sizes makes every node with an empty child look unbalanced and asks for rotations that cannot be performed, since the pivot's child is null.
is_balancedCheck if node satisfies weight-balance invariant.
Uses Δ = 3 and Γ = 2, the only valid integer solution.
When the left side is too heavy, weight(left) > 3 × weight(right), a single right rotation fixes it if weight(left.right) < 2 × weight(left.left), and a double left-right rotation does otherwise. The right-heavy case mirrors this.
Returns
New root after rebalancing (may be unchanged).
extractPops the root replacing it with one of descendants, if present.
Both halves may shed any number of nodes, so the two survivors are re-joined rather than stitched back in place - rotating once could not close a gap of many weight classes.
sample_rangeUniformly samples one node whose key lies in [lower, upper), or nullptr when empty.
Precondition: root is non-null and all(left) < root < all(right).
The two sides may sit many weight classes apart, so hanging root between them and rotating once is not enough. Walking down the heavier side's inner spine until the two pieces are within Δ of each other, then rebalancing on the way back up, is what keeps the invariant - this is what makes split and erase_range produce balanced trees. Runs in O(log n) expected time, where n is the size of the larger tree.
Not an expected, which holds a value or a reason and never both: a refused build still owns every node it made, and whoever asked for it has to free them.
Fields
root
node_t *
Everything that was built, which the owner frees whether the build finished or not.
Inserts [ first, last ), refusing the batch on any key already here.
All-or-nothing over this tree from the first element on, a taken key included: the whole range is staged and checked before the merge absorbing it relinks a single node.
Parameters
payload
in
Entry to insert, moved into the tree only when a node is made for it.
Returns
The node the key lives in, and whether it was made or matched.
Statuses
refused_k The allocator refused the node, so nothing was stored.
key_already_exists_k A key repeats inside an unsorted range or is already in this tree.
Any status an element's copy returns passes through unchanged.
insert_or_assignAtomically inserts or updates an element.
Exact for the counts as they stand now. One scalar per node cannot encode a function of a parameter, so a reader whose predicate differs from the one currently materialized in the entries - an older snapshot, say - gets no answer from this count and none of the descents built on it.
select_augmentedSelect the k-th smallest entry among those the augmentation policy counts, O(log n).
Merges another tree into this one, assuming all keys are unique.
Elements with keys that already exist in this tree are deallocated (not kept in source).
Parameters
other
in
Extracted node to merge.
Notes
Unlike std::set::merge(), a node with a duplicate key is deallocated rather than being returned. This ensures no memory leaks in a noexcept context.
Unlike std::set::merge(), nodes with duplicate keys are deallocated rather than remaining in the source container. This ensures no memory leaks in a noexcept context.
Complexity: O(m log n) where m = other.size(), n = this.size().
Preconditions
All keys in other must be different from keys in this tree.
Warnings
If precondition violated (duplicate keys exist), behavior is undefined.
rangeVisits every element in [lower, upper) in sorted order, or fewer if the callback halts.
Inserts [ first, last ) where the key is free, leaving incumbents alone.
All-or-nothing over this tree from the first element on: a node the allocator refuses and an element refusing its own copy are both met while the staging tree is built, and the merge absorbing it only relinks nodes.
Statuses
Any status an element's copy returns passes through unchanged.
template <typename value_type_,
typename hasher_type_,
waiting_policy<std::uint64_t const *, std::uint64_t> waiting_policy_type_ = bare_waiting_policy_t,
template<typename> class atomic_reference_ = atomic_ref>
class hash_atomic_slot_ref
Ideally, we would want to avoid Compare-And-Swap (CAS) loops for locking individual slots. On the locking path, we can use a fetch_or atomic operation to set both bits (populated + deleted) simultaneously and transition to the locked state. If the previous value indicates the slot was already locked, we retry until we acquire the lock.
The intuition of using the fetch_and for the inverse operation, however, is wrong. When unlocking, we need to restore the previous state (populated/deleted) of the slot or transition to the new one, depending on the mark_populated()/mark_deleted()/mark_free() calls made while the slot was locked.
The bits outside the active ones in each 32-bit word shouldn't be changed. The active ones may have to be flipped. Assuming the value of the relevant bits couldn't have changed, we can use fetch_xor to control the result with one more atomic and no compare-and-swap loop. XOR-is-all-you-need!
Neither path is lock-free in the technical sense: lock() spins until it wins the slot, so a thread stopped between lock() and unlock() blocks every prober that reaches that slot. What the pair buys is that the whole table is never locked, and that no slot state needs a CAS retry. What a losing prober does with its core in the meantime is waiting_policy_type_, which is where a caller that owns the hardware spends a stall instead of an issue slot.
This doesn't resolve false-sharing issues native to such a densely packed design, but still results in very low contention if the duration of atomic operations under the lock is comparable to CPU's memory latency.
header_refThe staged header, not the shared one, so reads under the lock stay private.
On a device this spin only makes progress under independent thread scheduling, since 32 slots share one header and a warp probing one bucket serializes through here.
Notes
The reference is a temporary rather than a named variable because a constexpr function may not define a variable of non-literal type before C++23. It costs nothing - the reference only carries the address it was handed.
unlockDrives the two owned bits from locked_k to whatever was staged, with one posted xor.
Classimmutable_b_treeAn immutable B-tree over value_type_, built once from a sorted span, whose nodes are rows of keys_per_row_ keys searched by row_kit_type_.16
A map walks its keys too, and rank indexes mapped_at for the value beside one.
Classimmutable_elias_fanoAn immutable sequence of non-decreasing unsigned integers, built once from values pulled in order and read back by position - the offsets of variable-length rows, a few bits apiece.6
Answers expected<std::span<value_t const>> for a position, holding the values from that position on - at least one while any remain, possibly all of them.
Classimmutable_packed_arrayAn immutable array of unsigned integers between a base and a maximum, built once from values pulled in order, each kept in the bit width of the maximum less the base.8
Builds the array of values, held whole, based at the least of them and as wide as the greatest needs.
Parameters
count
in
Number of values in the array.
base
in
Smallest value any of them may take.
maximum
in
Largest value any of them may take.
fill
in
Answers expected<std::span<value_t const>> for a position, holding the values from that position on - at least one while any remain, possibly all of them.
invalid_argument_kbytes ends before the words its header names, or the header holds a base or a width that value_t cannot.
Classimmutable_splus_treeAn immutable S+ tree over value_type_, built once from a sorted span, whose nodes are rows of keys_per_row_ keys searched by row_kit_type_.13
Classimmutable_splus_tree_viewAn immutable S+ tree searched in place, over rows and mapped values it does not own: either a saved form in borrowed bytes, or the storage of the tree it was taken from.11
invalid_argument_kbytes is misaligned, ends before the rows and mapped values its header names, or was saved by a tree of another key, row width or mapped value.
iteratorA forward walk over the keys in order, yielding each by value.
A map walks its keys too, and rank indexes mapped_at for the value beside one.
Structbinary_node_searchThe searches every binary node shares, over its left, right and payload, so the AVL and weight-balanced nodes answer bounds identically.
Owns the buffer and the elements inside it, and frees both, so a table holding one needs no destructor of its own. This is also the only thing that passes between a growable table and a pinned one, which is what lets that hand-off be a move of a value rather than one type reaching into the other.
has_values_kWhether the element carries a mapped value, making the table a map rather than a set.
clearDestroys every element and zeroes the headers, keeping the buffer: a slot's state lives in its header alone, so the keys and values left behind are never taken for elements.
The counterpart of no_op_t on the other slot: a concept needs a value of some type to write the call it is asking about, and binding a callback there would leave a swapped generator and callback invisible. Nothing samples through this - draw_below wants min, max and a call operator, and this is the least that satisfies all three.
result_typeWhat a draw hands back, widest so a probe never narrows what a real generator would give.
How many keys of a split row order below wanted, reading a low word only where its high word ties.
mask_equalWhich of keys equal wanted, one bit per key, the lowest for the first: a hash table's window, where slots nobody filled compare too and the caller masks them off.
select_set_bitWhere the remaining -th set bit after set bit sampled of words sits, counting sampled as the zeroth: the scan an Elias-Fano select runs from its sample.
remaining must be positive. A bit words does not hold, which only a corrupted sequence asks for, answers words.size() * 64, past every real bit, rather than reading past the span. Kits scanning several words per instruction finish the span's last few here.
select_onwardContinues a select at word, what remains to count of the word at word_index, never reading past words.
above_untilWhether key orders above until under less, which every key does where until is unbounded, so a descending walk stops on the first key that does not.
Relaxed suffices for a counter read by value - a statistic, or a version stamp compared for identity and recency - because one location has a total modification order. It publishes nothing: a caller needing the data a counter describes to be visible must order that itself.
atomic_loadAtomic read of a counter other threads may be incrementing, relaxed unless order asks for more.
Needed wherever a plain read would race an atomic_add_fetch on the same field.
Warnings
The counter is read through a const path but must not be a constobject - an atomic_ref over one is undefined. Every caller reaches a mutable member of a mutable container through a const member function, which is what makes the cast below sound.
atomic_storeRelaxed atomic write of a counter other threads may be reading.
A plain load may read a stale write; a read-modify-write reads the newest and joins its release sequence, so a store made before this call is visible to whoever reads the word afterwards. That is what an announce-then-re-read protocol needs and what a load cannot give it.
atomic_sub_fetchRelaxed atomic decrement of a plain counter, returning the post-decrement value.
template <template<typename> class atomic_reference_ = atomic_ref, std::integral integral_type_>
void atomic_max_fetch(
integral_type_ & word,
integral_type_ floor) noexcept;
One instruction through a reference that spells fetch_max, and the compare-exchange loop it replaces otherwise. A word only ever raised this way is monotone whoever writes it.
atomic_fetch_maxRaises word to floor unless it stands higher, answering what it held before.
template <template<typename> class atomic_reference_ = atomic_ref, std::integral integral_type_, typename order_type_>
integral_type_ atomic_fetch_max(
integral_type_ & word,
integral_type_ floor,
order_type_ order) noexcept;
One instruction through a reference that spells fetch_max, which std::atomic_ref does not before C++26, and the compare-exchange loop it replaces otherwise. A word only ever raised this way is monotone whoever writes it.
Returns
What word held before, at or above floor exactly when nothing was written.
atomic_post_maxRaises word to floor without reading what was there, which Arm spells stumax.
The bound is the whole point: a predicate a loop would re-check after every failed exchange becomes an argument the instruction decides on, so a refused caller writes nothing and leaves the line where it was. Without the extended form this is the compare-exchange loop it replaces.
Returns
What word held before, which is above limit exactly when nothing was written.
atomic_fetch_sub_if_at_leastSubtracts subtrahend from word only while the difference stays at or above floor.
What word held before, which is below floor exactly when nothing was written.
atomic_fetch_test_and_set_bitSets bit bit of word, below its width, and answers whether it was set before: a claim exactly one of several racing callers wins.
A lost race marks only the bit it lost and tries the next clear one of the same word, so a word costs one load and one claim per bit taken from under the caller. Bits released behind the scan are not seen. Release a claim with atomic_post_clear_bits at release order.
Returns
The claimed bit's position across words, or the total bit count when none was clear.
larger_ofThe larger of two values, and the smaller.
Spelled here rather than pulled from <algorithm>, which costs about ten thousand preprocessed lines for these two. It also sidesteps the Windows headers, which define min and max as function-like macros unless NOMINMAX is set, and would eat an unparenthesized std::max call.
bits_to_holdThe number of bits needed to represent x, so 0 for zero and 1 for one.
Masks to the next power of two and redraws when the value lands above the bound, which is unbiased because every value under the mask is equally likely and the surplus is simply discarded. At least half of the masked range is accepted, so fewer than two draws are expected.
Parameters
generator
in
Any uniform random bit generator, as std::mt19937 and friends are.
bound
in
One past the largest value that may be returned; zero and one draw nothing.
Notes
A generator narrower than the bound, like the 32-bit std::mt19937, is called repeatedly and the results concatenated, since masking a short draw could never reach the high bits.
roundup_to_multipleRounds up a value to the next multiple of a compile-time constant.
The second side is walked only to pick up what the first never had, so both algebras that reach it keep the same members - anything already shared was handed over by the first sweep.
walk_algebraHands callback every member of algebra_ over first and second.
Each side is read through a read transaction opened here, which fixes what that side shows from snapshot_k up; pass transactions to choose the instants yourself, at the cost of the nested walk compare_crossed_ falls back to.
Warnings
The two sides keep separate orders, so the pair is never one stamp, however read.
is_subsetWhether every member of first is also in second.
Settled at the first member second lacks, and the walk of first stops there.
A side with more members than the other cannot be contained in it, which is the whole answer without a walk. Both counts are read before either side is touched, so the pair is a decision about the sizes at one moment, not a size from one moment weighed against a walk from another.
is_disjointWhether the two sides share no member, on the same terms as is_subset.
hash_window_slotsReads the width_ slots starting at slot window of the bucket head describes, for a probe entering them at slot entry: the live slots from entry up to the first free one.
walk_hash_windowsWalks the probe run entered at slot entry a window at a time, handing on_match each populated slot whose key equals wanted until it halts, as hand_over reads its answer.
Each window takes row_kit_type_::mask_equal_width_k keys starting at a multiple of that width, compares them with one mask_equal, and masks the answer down to the live slots before the first free one. A deleted slot hides keys behind it, so only a free one ends the walk, and slots_count bounds it, so a full table ends it too.
Parameters
headers
in
The headers region, indexed by bucket.
keys
in
The keys region, indexed by slot, every key a window_key.
slots_count
in
The slot count, a power of two, at least one window.
entry
in
The home slot of wanted, already masked to the table.
wanted
in
The key to find.
on_match
in
Receives the slot index of each match, in probe order.
for_each_in_hash_bucketIterates over the populated slots of a bucket by scanning its population bitmap.
The generator hands back an expected per element, and a single failure destroys the prefix already built, so no half-populated array is ever observable. The scratch buffer the elements are assembled in is raw storage this function owns, so every element it constructs it also destroys - a moved-from element still has a destructor to run.
row_kit_compiledWhether this build carries kit, whatever the processor running it.
The lower bound of wanted in a sorted split row of any length, by 256 bytes of high words.
A row of up to about 256 bytes of keys goes to the kit whole; a longer one is first narrowed to such a window by branchless halving. Exact only when sorted is sorted.
count_below_in_rowThe lower bound of wanted in the sorted row at row, laid out by format_type_ and searched by row_kit_type_.
A 64-bit integer is only 4-byte aligned by default on a 32-bit target, while atomic_ref needs 8, so a counter that is perfectly well-behaved on x86-64 becomes undefined when built for i386. Every counter the helpers below touch carries this.
size_bits_kHow many bits the size type holds here, which is not 64 everywhere.