Compressed prefix tree mapping std::basic_string<Char> keys to values of type T. More...

#include <tpl_radix_tree.H>

Collaboration diagram for Aleph::RadixTree< T, Char >:

Classes
struct	Node

Public Types
using	Key = std::basic_string< Char >
	Key type: strings over `Char`.

Public Member Functions
	RadixTree ()
	Construct an empty tree.

	~RadixTree ()=default
	Destructor.

	RadixTree (RadixTree &&other)
	Move constructor: `other` is left as a valid, empty tree.

RadixTree &	operator= (RadixTree &&other)
	Move assignment operator: `other` is left as a valid, empty tree.

	RadixTree (const RadixTree &other)
	Deep-copy constructor: every node is cloned independently.

RadixTree &	operator= (const RadixTree &other)
	Deep-copy assignment operator.

size_t	size () const noexcept
	Return the number of keys currently stored.

bool	is_empty () const noexcept
	Check whether the tree holds no keys.

bool	insert (const Key &key, const T &value)
	Insert `key` with a copy of `value`, only if `key` is absent.

bool	insert (const Key &key, T &&value)
	Insert `key` with `value` moved in, only if `key` is absent.

void	insert_or_assign (const Key &key, T value)
	Insert `key` with `value`, or overwrite the existing value if `key` is already present.

bool	erase (const Key &key)
	Remove `key` if present, merging any resulting single-child, valueless node back into a compressed edge.

bool	contains (const Key &key) const noexcept
	Check whether `key` is present.

const T *	find (const Key &key) const noexcept
	Look up `key`.

T *	find (const Key &key) noexcept
	Non-`const` overload of find(const Key&).

std::optional< Key >	longest_prefix (const Key &key) const
	Find the longest stored key that is a prefix of `key`.

Array< Key >	keys_with_prefix (const Key &prefix) const
	Return every stored key that starts with `prefix`.

bool	verify () const
	Recursively verify the tree's structural invariants.

Private Member Functions
template<typename U >
bool	insert_impl (const Key &key, U &&value, const bool assign_if_present=false)
	Shared implementation for `insert()`'s copy/move overloads and for `insert_or_assign()`: `U` is deduced as `const T&` or `T&&` at the call site.

const Node *	find_node (const Key &key) const noexcept

Static Private Member Functions
static const Node *	find_child (const Node *node, const Char c) noexcept

static size_t	find_child_slot (Node *node, const Char c) noexcept

static void	add_child (Node *node, const Char c, std::unique_ptr< Node > child)

static void	remove_child_at (Node *node, const size_t idx)
	Remove the child at `idx` in O(1) by swapping with the last slot; the (unordered) children array does not need to preserve position.

static size_t	common_prefix_length (const Key &label, const Key &key, const size_t key_off) noexcept
	Length of the common prefix between `label` and `key[key_off..)`.

static void	collect_keys (const Node *node, Key &prefix_acc, Array< Key > &out)

static std::unique_ptr< Node >	clone_node (const Node *src)

static bool	verify_rec (const Node *node, const bool is_root, size_t &counted_values)

Private Attributes
std::unique_ptr< Node >	root_

size_t	size_ = 0

Static Private Attributes
static constexpr size_t	npos = static_cast<size_t>(-1)

Detailed Description

template<typename T, typename Char = char>
class Aleph::RadixTree< T, Char >

Compressed prefix tree mapping std::basic_string<Char> keys to values of type T.

See the file-level documentation in tpl_radix_tree.H for the full design rationale, complexity, and ownership/invalidation contract.

Template Parameters

T	Mapped value type. Must be move-constructible; copy- constructible only if `RadixTree` itself is copied.
Char	Character type of keys (default `char`). Keys are `std::basic_string<Char>`.

Definition at line 119 of file tpl_radix_tree.H.

Member Typedef Documentation

◆ Key

template<typename T , typename Char = char>

using Aleph::RadixTree< T, Char >::Key = std::basic_string<Char>

Key type: strings over Char.

Definition at line 123 of file tpl_radix_tree.H.

Constructor & Destructor Documentation

◆ RadixTree() [1/3]

template<typename T , typename Char = char>

Aleph::RadixTree< T, Char >::RadixTree ( )

inline

Construct an empty tree.

Exceptions

std::bad_alloc if allocating the root node fails.

Definition at line 328 of file tpl_radix_tree.H.

◆ ~RadixTree()

template<typename T , typename Char = char>

Aleph::RadixTree< T, Char >::~RadixTree ( )

default

Destructor.

Recursively releases every node (via the unique_ptr ownership chain). Recursion depth tracks the number of distinct branch/value-bearing points on the deepest root-to-leaf path, which is bounded by key length in the worst case (compression only removes childless, valueless "wasted" nodes; a chain of nested- prefix keys such as "a", "aa", "aaa", ... each holds its own value and so is never merged away) – an extremely long chain of such keys can in principle exhaust the stack, same as any other unique_ptr-owned recursive tree/list teardown.

◆ RadixTree() [2/3]

template<typename T , typename Char = char>

Aleph::RadixTree< T, Char >::RadixTree ( RadixTree< T, Char > && other )

inline

Move constructor: other is left as a valid, empty tree.

Parameters

[in,out] other Tree to move from.

Exceptions

std::bad_alloc if allocating the replacement empty root for other fails; in that case other is left unchanged.

Definition at line 346 of file tpl_radix_tree.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::RadixTree< T, Char >::root_, and Aleph::RadixTree< T, Char >::size_.

◆ RadixTree() [3/3]

template<typename T , typename Char = char>

Aleph::RadixTree< T, Char >::RadixTree ( const RadixTree< T, Char > & other )

inline

Deep-copy constructor: every node is cloned independently.

Parameters

[in] other Tree to copy.

Exceptions

Whatever T's copy constructor throws, or std::bad_alloc.

Definition at line 375 of file tpl_radix_tree.H.

Member Function Documentation

◆ add_child()

template<typename T , typename Char = char>

static void Aleph::RadixTree< T, Char >::add_child	(	Node *	node,
		const Char	c,
		std::unique_ptr< Node >	child
	)

inlinestaticprivate

Definition at line 166 of file tpl_radix_tree.H.

References Aleph::RadixTree< T, Char >::Node::children.

Referenced by Aleph::RadixTree< T, Char >::insert_impl().

◆ clone_node()

template<typename T , typename Char = char>

static std::unique_ptr< Node > Aleph::RadixTree< T, Char >::clone_node ( const Node * src )

inlinestaticprivate

Definition at line 312 of file tpl_radix_tree.H.

References Aleph::blossom_maximum_cardinality_matching(), and Aleph::RadixTree< T, Char >::clone_node().

Referenced by Aleph::RadixTree< T, Char >::clone_node(), and Aleph::RadixTree< T, Char >::operator=().

◆ collect_keys()

template<typename T , typename Char = char>

static void Aleph::RadixTree< T, Char >::collect_keys	(	const Node *	node,
		Key &	prefix_acc,
		Array< Key > &	out
	)

inlinestaticprivate

Definition at line 299 of file tpl_radix_tree.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::RadixTree< T, Char >::Node::children, Aleph::RadixTree< T, Char >::collect_keys(), out, and Aleph::RadixTree< T, Char >::Node::value.

Referenced by Aleph::RadixTree< T, Char >::collect_keys(), and Aleph::RadixTree< T, Char >::keys_with_prefix().

◆ common_prefix_length()

template<typename T , typename Char = char>

static size_t Aleph::RadixTree< T, Char >::common_prefix_length	(	const Key &	label,
		const Key &	key,
		const size_t	key_off
	)

inlinestaticprivatenoexcept

Length of the common prefix between label and key[key_off..).

Definition at line 182 of file tpl_radix_tree.H.

References Aleph::and, and Aleph::blossom_maximum_cardinality_matching().

Referenced by Aleph::RadixTree< T, Char >::insert_impl(), and Aleph::RadixTree< T, Char >::keys_with_prefix().

◆ contains()

template<typename T , typename Char = char>

bool Aleph::RadixTree< T, Char >::contains ( const Key & key ) const

inlinenoexcept

Check whether key is present.

Parameters

[in] key Key to look up.

Returns: true if present.

Exceptions

Nothing.

Definition at line 532 of file tpl_radix_tree.H.

References Aleph::RadixTree< T, Char >::find().

Referenced by TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), and TEST().

◆ erase()

template<typename T , typename Char = char>

bool Aleph::RadixTree< T, Char >::erase ( const Key & key )

inline

Remove key if present, merging any resulting single-child, valueless node back into a compressed edge.

Parameters

[in] key Key to remove.

Returns: true if key was present and removed, false otherwise.

Exceptions

std::bad_alloc if merging edge labels cannot allocate; the tree remains valid, though it may be temporarily less compressed.

Definition at line 465 of file tpl_radix_tree.H.

Referenced by TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), and TEST().

◆ find() [1/2]

template<typename T , typename Char = char>

const T * Aleph::RadixTree< T, Char >::find ( const Key & key ) const

inlinenoexcept

Look up key.

Parameters

[in] key Key to look up.

Returns: Pointer to the stored value if key is present, nullptr otherwise. Valid until the next non-const operation on this tree.

Exceptions

Nothing.

Definition at line 544 of file tpl_radix_tree.H.

References Aleph::and, Aleph::RadixTree< T, Char >::find_node(), and Aleph::RadixTree< T, Char >::Node::value.

Referenced by Aleph::RadixTree< T, Char >::contains(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), and TEST().

◆ find() [2/2]

template<typename T , typename Char = char>

T * Aleph::RadixTree< T, Char >::find ( const Key & key )

inlinenoexcept

Non-const overload of find(const Key&).

Parameters

[in] key Key to look up.

Returns: Pointer to the stored value if key is present, nullptr otherwise. Valid until the next non-const operation on this tree.

Exceptions

Nothing.

Definition at line 557 of file tpl_radix_tree.H.

References Aleph::and, Aleph::RadixTree< T, Char >::find_node(), and Aleph::RadixTree< T, Char >::Node::value.

◆ find_child()

template<typename T , typename Char = char>

static const Node * Aleph::RadixTree< T, Char >::find_child	(	const Node *	node,
		const Char	c
	)

inlinestaticprivatenoexcept

Definition at line 150 of file tpl_radix_tree.H.

References Aleph::blossom_maximum_cardinality_matching().

Referenced by Aleph::RadixTree< T, Char >::find_node(), Aleph::RadixTree< T, Char >::keys_with_prefix(), and Aleph::RadixTree< T, Char >::longest_prefix().

◆ find_child_slot()

template<typename T , typename Char = char>

static size_t Aleph::RadixTree< T, Char >::find_child_slot	(	Node *	node,
		const Char	c
	)

inlinestaticprivatenoexcept

Definition at line 158 of file tpl_radix_tree.H.

References Aleph::RadixTree< T, Char >::npos.

Referenced by Aleph::RadixTree< T, Char >::erase(), and Aleph::RadixTree< T, Char >::insert_impl().

◆ find_node()

template<typename T , typename Char = char>

const Node * Aleph::RadixTree< T, Char >::find_node ( const Key & key ) const

inlineprivatenoexcept

Definition at line 277 of file tpl_radix_tree.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::RadixTree< T, Char >::Node::edge_label, Aleph::RadixTree< T, Char >::find_child(), and Aleph::RadixTree< T, Char >::root_.

Referenced by Aleph::RadixTree< T, Char >::find(), and Aleph::RadixTree< T, Char >::find().

◆ insert() [1/2]

template<typename T , typename Char = char>

bool Aleph::RadixTree< T, Char >::insert	(	const Key &	key,
		const T &	value
	)

inline

Insert key with a copy of value, only if key is absent.

Parameters

[in]	key	Key to insert. The empty string is a valid key (mapped to the root's own value slot).
[in]	value	Value to copy in.

Returns: true if inserted, false if key was already present (the existing value is left untouched).

Exceptions

Whatever T's copy constructor throws, or std::bad_alloc.

Definition at line 423 of file tpl_radix_tree.H.

References Aleph::RadixTree< T, Char >::insert_impl(), and value.

Referenced by TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), and TEST().

◆ insert() [2/2]

template<typename T , typename Char = char>

bool Aleph::RadixTree< T, Char >::insert	(	const Key &	key,
		T &&	value
	)

inline

Insert key with value moved in, only if key is absent.

Parameters

[in]	key	Key to insert.
[in,out]	value	Value to move in.

Returns: true if inserted, false if key was already present.

Exceptions

Whatever T's move constructor throws, or std::bad_alloc.

Warning: On a false return (duplicate key), value is left unmodified: unlike Aleph::ConcurrentHashMap, this implementation checks for the duplicate before touching value (no forwarding-then-discarding path exists here).

Definition at line 439 of file tpl_radix_tree.H.

References Aleph::RadixTree< T, Char >::insert_impl(), and value.

◆ insert_impl()

template<typename T , typename Char = char>

template<typename U >

bool Aleph::RadixTree< T, Char >::insert_impl	(	const Key &	key,
		U &&	value,
		const bool	assign_if_present = `false`
	)

inlineprivate

Shared implementation for insert()'s copy/move overloads and for insert_or_assign(): U is deduced as const T& or T&& at the call site.

When assign_if_present is true (only insert_or_ assign() sets it), an already-present key's value is overwritten in place instead of leaving it untouched – letting insert_or_assign() share this single tree descent instead of calling find() first and then re-descending from the root a second time via this function.

Definition at line 200 of file tpl_radix_tree.H.

References Aleph::RadixTree< T, Char >::add_child(), Aleph::blossom_maximum_cardinality_matching(), Aleph::RadixTree< T, Char >::Node::children, Aleph::RadixTree< T, Char >::common_prefix_length(), Aleph::RadixTree< T, Char >::Node::edge_label, Aleph::RadixTree< T, Char >::find_child_slot(), Aleph::RadixTree< T, Char >::npos, Aleph::RadixTree< T, Char >::root_, Aleph::RadixTree< T, Char >::size_, Aleph::split(), value, and Aleph::RadixTree< T, Char >::Node::value.

Referenced by Aleph::RadixTree< T, Char >::insert(), Aleph::RadixTree< T, Char >::insert(), and Aleph::RadixTree< T, Char >::insert_or_assign().

◆ insert_or_assign()

template<typename T , typename Char = char>

void Aleph::RadixTree< T, Char >::insert_or_assign	(	const Key &	key,
		T	value
	)

inline

Insert key with value, or overwrite the existing value if key is already present.

Parameters

[in]	key	Key to insert or update.
[in]	value	New value.

Exceptions

Whatever T's move/copy constructor or move assignment throws, or std::bad_alloc.

Definition at line 452 of file tpl_radix_tree.H.

References Aleph::RadixTree< T, Char >::insert_impl(), and value.

Referenced by TEST(), TEST(), and TEST().

◆ is_empty()

template<typename T , typename Char = char>

bool Aleph::RadixTree< T, Char >::is_empty ( ) const

inlinenoexcept

Check whether the tree holds no keys.

Returns: true if the tree holds no keys.

Exceptions

Nothing.

Definition at line 409 of file tpl_radix_tree.H.

References Aleph::RadixTree< T, Char >::size_.

Referenced by TEST(), TEST(), TEST(), and TEST().

◆ keys_with_prefix()

template<typename T , typename Char = char>

Array< Key > Aleph::RadixTree< T, Char >::keys_with_prefix ( const Key & prefix ) const

inline

Return every stored key that starts with prefix.

Parameters

[in] prefix Prefix to match (the empty string matches every key).

Returns: An independent Array of matching keys, in an unspecified order.

Exceptions

Whatever allocating the returned keys/array throws.

Definition at line 616 of file tpl_radix_tree.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::RadixTree< T, Char >::collect_keys(), Aleph::RadixTree< T, Char >::common_prefix_length(), Aleph::RadixTree< T, Char >::Node::edge_label, Aleph::RadixTree< T, Char >::find_child(), Aleph::prefix(), and Aleph::RadixTree< T, Char >::root_.

Referenced by TEST(), TEST(), and TEST().

◆ longest_prefix()

template<typename T , typename Char = char>

std::optional< Key > Aleph::RadixTree< T, Char >::longest_prefix ( const Key & key ) const

inline

Find the longest stored key that is a prefix of key.

Parameters

[in] key Key to match against.

Returns: The longest k such that k is a stored key and a prefix of key (which may be key itself), or std::nullopt if no stored key is a prefix of key. Call find() on the result to get the associated value.

Exceptions

Whatever allocating the returned Key throws.

Note: This walks the same path find() would, so it is well suited to longest-prefix-match use cases (e.g. routing tables, hierarchical settings lookup) without requiring T to be copy-constructible (only Key, always a std::basic_string, is copied).

Definition at line 578 of file tpl_radix_tree.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::RadixTree< T, Char >::Node::edge_label, Aleph::RadixTree< T, Char >::find_child(), and Aleph::RadixTree< T, Char >::root_.

Referenced by TEST(), and TEST().

◆ operator=() [1/2]

template<typename T , typename Char = char>

RadixTree & Aleph::RadixTree< T, Char >::operator= ( const RadixTree< T, Char > & other )

inline

Deep-copy assignment operator.

Parameters

[in] other Tree to copy from.

Returns: Reference to this tree.

Exceptions

Whatever T's copy constructor throws, or std::bad_alloc.

Definition at line 385 of file tpl_radix_tree.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::RadixTree< T, Char >::clone_node(), Aleph::RadixTree< T, Char >::root_, and Aleph::RadixTree< T, Char >::size_.

◆ operator=() [2/2]

template<typename T , typename Char = char>

RadixTree & Aleph::RadixTree< T, Char >::operator= ( RadixTree< T, Char > && other )

inline

Move assignment operator: other is left as a valid, empty tree.

Parameters

[in,out] other Tree to move from.

Returns: Reference to this tree.

Exceptions

std::bad_alloc if allocating the replacement empty root for other fails; in that case both trees are left unchanged.

Definition at line 358 of file tpl_radix_tree.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::RadixTree< T, Char >::root_, and Aleph::RadixTree< T, Char >::size_.

◆ remove_child_at()

template<typename T , typename Char = char>

static void Aleph::RadixTree< T, Char >::remove_child_at	(	Node *	node,
		const size_t	idx
	)

inlinestaticprivate

Remove the child at idx in O(1) by swapping with the last slot; the (unordered) children array does not need to preserve position.

Definition at line 173 of file tpl_radix_tree.H.

References Aleph::RadixTree< T, Char >::Node::children.

Referenced by Aleph::RadixTree< T, Char >::erase().

◆ size()

template<typename T , typename Char = char>

size_t Aleph::RadixTree< T, Char >::size ( ) const

inlinenoexcept

Return the number of keys currently stored.

Returns: The number of keys currently stored.

Exceptions

Nothing.

Definition at line 400 of file tpl_radix_tree.H.

References Aleph::RadixTree< T, Char >::size_.

Referenced by TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), and TEST().

◆ verify()

template<typename T , typename Char = char>

bool Aleph::RadixTree< T, Char >::verify ( ) const

inline

Recursively verify the tree's structural invariants.

Checks, for every node:

No non-root node has an empty edge label.
A child's edge label always starts with the character it is indexed under in its parent's children array.
No two children of the same node have edge labels starting with the same character (the invariant find_child/find_child_slot rely on to unambiguously pick a child from a single character).
No non-root node has exactly one child and no value: such a node is "wasted" (uncompressed) – insert_impl() never creates one, and erase() must merge it back into a single edge.
The number of nodes holding a value equals size() (catches size_ bookkeeping drift independently of the structural checks above).

Returns: true if every invariant holds.

Note: Not part of the type's regular contract: a debug/test-only tool to catch structural corruption that black-box testing (find/contains/keys_with_prefix) might not expose if it happens not to affect the specific operations exercised afterward. Tests/radix_tree_test.cc calls this after every mutation in its randomized parity tests.

Definition at line 678 of file tpl_radix_tree.H.

References Aleph::and, Aleph::blossom_maximum_cardinality_matching(), Aleph::RadixTree< T, Char >::root_, Aleph::RadixTree< T, Char >::size_, and Aleph::RadixTree< T, Char >::verify_rec().

Referenced by TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), and TEST().

◆ verify_rec()

template<typename T , typename Char = char>

static bool Aleph::RadixTree< T, Char >::verify_rec	(	const Node *	node,
		const bool	is_root,
		size_t &	counted_values
	)

inlinestaticprivate

Definition at line 686 of file tpl_radix_tree.H.

References Aleph::and, Aleph::blossom_maximum_cardinality_matching(), Aleph::RadixTree< T, Char >::Node::children, Aleph::RadixTree< T, Char >::Node::edge_label, Aleph::RadixTree< T, Char >::Node::value, and Aleph::RadixTree< T, Char >::verify_rec().

Referenced by Aleph::RadixTree< T, Char >::verify(), and Aleph::RadixTree< T, Char >::verify_rec().

Member Data Documentation

◆ npos

template<typename T , typename Char = char>

constexpr size_t Aleph::RadixTree< T, Char >::npos = static_cast<size_t>(-1)

staticconstexprprivate

Definition at line 140 of file tpl_radix_tree.H.

Referenced by Aleph::RadixTree< T, Char >::erase(), Aleph::RadixTree< T, Char >::find_child_slot(), and Aleph::RadixTree< T, Char >::insert_impl().

◆ root_

template<typename T , typename Char = char>

std::unique_ptr<Node> Aleph::RadixTree< T, Char >::root_

private

Definition at line 142 of file tpl_radix_tree.H.

Referenced by Aleph::RadixTree< T, Char >::RadixTree(), Aleph::RadixTree< T, Char >::erase(), Aleph::RadixTree< T, Char >::find_node(), Aleph::RadixTree< T, Char >::insert_impl(), Aleph::RadixTree< T, Char >::keys_with_prefix(), Aleph::RadixTree< T, Char >::longest_prefix(), Aleph::RadixTree< T, Char >::operator=(), Aleph::RadixTree< T, Char >::operator=(), and Aleph::RadixTree< T, Char >::verify().

◆ size_

template<typename T , typename Char = char>

size_t Aleph::RadixTree< T, Char >::size_ = 0

private

Definition at line 143 of file tpl_radix_tree.H.

Referenced by Aleph::RadixTree< T, Char >::RadixTree(), Aleph::RadixTree< T, Char >::erase(), Aleph::RadixTree< T, Char >::insert_impl(), Aleph::RadixTree< T, Char >::is_empty(), Aleph::RadixTree< T, Char >::operator=(), Aleph::RadixTree< T, Char >::operator=(), Aleph::RadixTree< T, Char >::size(), and Aleph::RadixTree< T, Char >::verify().

The documentation for this class was generated from the following file:

tpl_radix_tree.H

Classes

Public Types

Public Member Functions

Private Member Functions

Static Private Member Functions

Private Attributes

Static Private Attributes

Detailed Description

Member Typedef Documentation

◆ Key

Constructor & Destructor Documentation

◆ RadixTree() [1/3]

◆ ~RadixTree()

◆ RadixTree() [2/3]

◆ RadixTree() [3/3]

Member Function Documentation

◆ add_child()

◆ clone_node()

◆ collect_keys()

◆ common_prefix_length()

◆ contains()

◆ erase()

◆ find() [1/2]

◆ find() [2/2]

◆ find_child()

◆ find_child_slot()

◆ find_node()

◆ insert() [1/2]

◆ insert() [2/2]

◆ insert_impl()

◆ insert_or_assign()

◆ is_empty()

◆ keys_with_prefix()

◆ longest_prefix()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ remove_child_at()

◆ size()

◆ verify()

◆ verify_rec()

Member Data Documentation

◆ npos

◆ root_

◆ size_