tpl_radix_tree.H File Reference

Compressed prefix tree (Aleph::RadixTree) mapping string keys to values. More...

#include <algorithm>
#include <memory>
#include <optional>
#include <string>
#include <tuple>
#include <type_traits>
#include <utility>
#include <ah-errors.H>
#include <tpl_array.H>

Include dependency graph for tpl_radix_tree.H:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
class	Aleph::RadixTree< T, Char >
	Compressed prefix tree mapping std::basic_string<Char> keys to values of type T. More...
struct	Aleph::RadixTree< T, Char >::Node

Namespaces
namespace	Aleph
	Main namespace for Aleph-w library functions.

Detailed Description

Compressed prefix tree (Aleph::RadixTree) mapping string keys to values.

RadixTree<T, Char> is a radix tree (a.k.a. compressed trie / PATRICIA- style trie): unlike a classic trie – where every edge is labeled with a single character, so a chain of nodes each having exactly one child wastes a node per character – a radix tree merges any such chain into a single edge labeled with the whole shared substring. Every non-root node either stores a value (a key ends there) or has at least two children (the root is exempt, since it starts and may remain a valueless, childless node representing the empty tree); a node that would otherwise have exactly one child and no value is never created by insert(), and is merged away by erase().

How it differs from prefix-tree.H

Prefix_Tree (in prefix-tree.H) is a classic uncompressed trie: one node per character, which is simple and cheap to reason about but uses O(key length) nodes per distinct branching path even when there is no actual branching. RadixTree uses O(number of branch/leaf points) nodes instead, which is asymptotically smaller for key sets with long shared or unique substrings (e.g. URLs, filesystem paths, IP-prefix-like keys), at the cost of a slightly more involved insert/erase (edge splitting and merging) than a plain trie.

Ownership and iterator/reference invalidation

Every node is owned exactly once, via std::unique_ptr, by its parent (or by the tree itself, for the root); destroying the tree recursively destroys every node. find() returns a raw pointer into the tree: it stays valid until the next non-const operation on the tree (insert, insert_or_assign, erase, copy-assignment, move-assignment, or destruction). This is a conservative rule, not the same guarantee std::map makes: std::map references/iterators stay valid across insertions and non-erasing operations on unrelated keys, but any non-const RadixTree operation – even inserting an unrelated key – can restructure the tree (edge splitting/merging) and invalidate every previously-returned pointer, not just ones touching the same key. RadixTree has no live iteration API; keys_with_prefix() returns an independent Array of copied keys instead.

Complexity

For a key of length n: insert, erase, find, contains, and longest_prefix are O(n) plus, at each of the O(number of edges on the path) branch points visited, a linear scan over that node's children (bounded by the alphabet size, but in practice small for real key sets). keys_with_prefix is O(prefix length) to reach the subtree plus O(size of the matching subtree) to collect it.

Thread-safety

None. RadixTree is an ordinary sequential container; external synchronization is required for concurrent use (see Aleph::ConcurrentHashMap in tpl_concurrent_hash_map.H for a concurrency-safe associative container).

See also

prefix-tree.H for Aleph::Prefix_Tree, the uncompressed character trie this type complements.

Author

Leandro Rabindranath Leon

Definition in file tpl_radix_tree.H.