Balanced ordered containers: set and map
include/reloco/set.hpp, include/reloco/map.hpp,
include/reloco/detail/rbtree_base.hpp
Why they exist
reloco already had two ordered containers, each with a catch:
| Container | Catch |
|---|---|
flat_set/flat_map |
sorted vector: O(n) insert/erase, inserts invalidate references |
tree_set/tree_map |
node-based, but a plain unbalanced BST: sorted input (very common!) degrades it to a linked list, O(n) per operation |
reloco::set and reloco::map are the general-purpose choice: a
red-black tree, so insert, erase and lookup are O(log n) in the
worst case, whatever order the data arrives in, and a reference to an
element stays valid while other elements are inserted or erased. If you
do not know which ordered container to use, use these.
How they work (short version)
Every element lives in its own allocator-owned node ([header][payload],
see detail/node_base.hpp). The header’s reserved aux byte stores the
node colour (0 = red, 1 = black). rbtree_base is simply tree_base
parameterised with rb_policy: after linking a leaf it recolours/rotates to
restore the red-black invariants, and erase relinks the in-order successor
node instead of copying values, so T needs no assignment operators.
The header packs the colour into the low bit of the parent pointer, so a node
is 24 bytes of bookkeeping instead of 32. try_clone copies the node structure
and colours directly in O(n) (no comparisons, no rebalancing), which is a
valid red-black tree by construction. The tree height is at most 2 * log2(n + 1). The cheap cases (parent is
black on insert, erasing a red leaf) and the rotation helpers are inline; only
the multi-step rebalancing is out of line. The tree caches its leftmost and
rightmost nodes, so begin(), try_first, try_last, try_pop_first and
try_pop_last are O(1) (draining a queue-like set costs no descent). Lookups
and inserts prefetch both children of each visited node, which cut 100k-element
lookup/insert/churn times by roughly 12-18%.
API
Same shape as tree_set/tree_map. All mutators are fallible and
return reloco::result<...>; there is deliberately no operator[].
set<T, Compare = std::less<T>>: try_create, try_allocate(alloc),
try_insert(value) (error::already_exists on duplicate), contains,
try_find, try_remove, try_first/try_last,
try_pop_first/try_pop_last, retain, append,
is_subset/is_superset/is_disjoint, try_clone, clear, size,
empty, height() (diagnostic, O(n)), read-only iteration.
map<Key, Mapped, Compare = std::less<Key>>: the above (keyed by Key) plus
try_insert(key, mapped), try_at(key), try_entry_or_insert,
try_entry_or_insert_with, try_entry_and_modify,
try_first_key_value/try_last_key_value; retain receives
(const Key &, Mapped &).
Both are trivially relocatable exactly when Compare is, and have
container_ref_traits adapters.
Example
#include <reloco/map.hpp>
#include <reloco/set.hpp>
// A set that is cheap to build from already-sorted ids (a plain BST would
// degenerate here); `try_create` uses the default allocator.
auto ids = reloco::set<int>::try_create();
if (!ids)
return; // allocation failure
for (int i = 0; i < 100000; ++i) {
// Fails with error::already_exists on duplicates; discarding is explicit.
auto added = ids->try_insert(i);
if (!added)
return;
}
// A map from name to score. try_insert takes (key, mapped).
auto scores = reloco::map<std::string, int>::try_create();
if (!scores)
return;
auto first = scores->try_insert("alice", 10);
// Look up and update in place: try_at returns a reference to the mapped
// value; it stays valid across inserts/erases of *other* keys.
if (auto score = scores->try_at("alice"))
score->get() += 5;
// Walk in ascending key order (read-only iteration keeps the order intact).
for (const auto &[name, value] : *scores) {
// use name/value
}
Integration
- Everything allocates through an
allocator_ref(try_allocate(alloc)), so it works withheap_allocator,stack_allocator, arenas, … - Choose
tree_set/tree_maponly if you want the smaller, simpler unbalanced tree and know your input is random. - Choose
flat_set/flat_mapfor read-mostly data where cache locality andtry_reservematter more than insert cost.
Benchmarks
benchmarks/containers/bench_ordered_sets.cpp times tree_set, set and
flat_set on the same workloads, so you can see the trade-off on your own
machine (integer nanoseconds per element, best of 5):
# Build with optimization; benchmarks are off by default.
cmake -S . -B build-bench -DJPLCZ_RELOCO_BUILD_BENCHMARKS=ON -DCMAKE_BUILD_TYPE=Release
cmake --build build-bench --target jplcz_reloco_container_bench
./build-bench/jplcz_reloco_container_bench
Typical shape of the results (one run, 10 000 uint32_t; yours will differ):
| Workload | tree_set |
set |
flat_set |
|---|---|---|---|
| insert, sorted input | ~7000 | ~70 | ~20 |
| insert, random input | ~95 | ~105 | ~150 |
| lookup after sorted build | ~6000 | ~60 | ~60 |
| insert + erase, random | ~145 | ~170 | ~290 |
Takeaways: tree_set is competitive only on random data and collapses on
sorted input (the case set exists for); flat_set wins on lookup and
iteration but its insert/erase cost grows with size (at 100 000 random
elements it is ~6x slower than set to build). tree_set sorted cases are
skipped above 20 000 elements because they take quadratic time.
The same workloads also run on tree_map/map/flat_map with
reloco::string keys (16 chars) and values (24 chars). Strings are move-only,
so each insert clones a prebuilt pair inside the timed region; that cost is
the same for all three maps. One run, 10 000 elements (ns per element):
| Workload | tree_map |
map |
flat_map |
|---|---|---|---|
| insert, sorted input | ~24000 | ~280 | ~170 |
| insert, random input | ~260 | ~265 | ~2260 |
| lookup after sorted build | ~28000 | ~160 | ~160 |
| insert + erase, random | ~375 | ~395 | ~4440 |
With string keys the picture is the same, but comparisons are costlier, so
the balanced tree’s lookup gap to flat_set-style binary search shrinks to
nothing, while flat_map’s insert cost (moving whole strings) grows
quickly with size.
Optimizations that did not pay off
A bounded per-tree freelist of erased nodes (to skip allocator round trips on
insert/erase churn) was prototyped and benchmarked with the churn
(erase+insert) row: the difference was within run-to-run noise, because the
system allocator’s thread cache is already cheap, so it was not kept. Packing
the colour bit also made no measurable speed difference for small payloads
(it reduces memory, not time).