Contiguous-array AVL tree used by jh::ordered_map and jh::ordered_set. More...

#include <jh/core/ordered_map.h>

Classes
struct	iterator
	Bidirectional iterator providing in-order traversal. More...
struct	const_iterator
	Const bidirectional iterator for in-order traversal. More...

Public Types
using	vector_type = detail::node_vector_type<K, V, Alloc>
	Vector storage type for all nodes.
using	value_type = detail::value_t<K, V>
	Public value type (`K` for set, `std::pair<const K, V>` for map).
using	reverse_iterator = std::reverse_iterator<iterator>
	Reverse iterator type.
using	const_reverse_iterator = std::reverse_iterator<const_iterator>
	Const reverse iterator type.

Public Member Functions
	tree_map () noexcept(noexcept(alloc_type()))
	Default constructor creating an empty tree with default allocator.
	tree_map (const Alloc &alloc)
	Construct an empty tree with a specified allocator.
template<typename K_, typename V_, typename Alloc_>
	tree_map (const tree_map< K_, V_, Alloc_ > &other)
	Copy-construct from another tree whose canonical key/value types match this tree and whose allocator type is identical.
template<typename K_, typename V_, typename Alloc_>
	tree_map (const tree_map< K_, V_, Alloc_ > &other)
	Copy-construct from another tree whose canonical key/value types match this tree, using a rebound default allocator.
template<typename K_, typename V_, typename Alloc_>
	tree_map (const tree_map< K_, V_, Alloc_ > &other, const Alloc &alloc)
	Copy-construct from another tree whose canonical key/value types match this tree, using a user-supplied allocator.
template<typename K_, typename V_, typename Alloc_>
	tree_map (tree_map< K_, V_, Alloc_ > &&other) noexcept
	Move-construct from another tree whose canonical key/value types match this tree and whose allocator type is identical.
template<typename K_, typename V_, typename Alloc_>
	tree_map (tree_map< K_, V_, Alloc_ > &&other)
	Move-construct from another tree whose canonical key/value types match this tree, using a rebound default allocator.
template<typename K_, typename V_, typename Alloc_>
	tree_map (tree_map< K_, V_, Alloc_ > &&other, const Alloc &alloc)
	Move-construct from another tree whose canonical key/value types match this tree, using a user-supplied allocator.
iterator	begin ()
	Return an iterator to the smallest element.
iterator	end ()
	Return the past-the-end iterator.
const_iterator	begin () const
	Return a const iterator to the smallest element.
const_iterator	end () const
	Return the const past-the-end iterator.
const_iterator	cbegin () const
	Return a const iterator to the first element.
const_iterator	cend () const
	Return the const past-the-end iterator.
reverse_iterator	rbegin ()
	Return a reverse iterator to the last element.
reverse_iterator	rend ()
	Return the reverse past-the-end iterator.
const_reverse_iterator	rbegin () const
	Return a const reverse iterator to the last element.
const_reverse_iterator	rend () const
	Return the const reverse past-the-end iterator.
const_reverse_iterator	crbegin () const
	Return a const reverse iterator to the last element.
const_reverse_iterator	crend () const
	Return the const reverse past-the-end iterator.
iterator	find (const node_type::key_type &key)
	Locate the element with the specified key.
const_iterator	find (const node_type::key_type &key) const
	Locate the element with the specified key (const overload).
std::pair< iterator, bool >	insert (const value_type &key)
	Insert a key into the set.
std::pair< iterator, bool >	insert (value_type &key)
	Insert a key into the set (non-const reference overload).
template<typename... Args> requires (jh::typed::monostate_t<V>)
std::pair< iterator, bool >	emplace (Args &&... args)
	Construct a key and insert it into the set.
template<typename P> requires (!jh::typed::monostate_t<V>)
std::pair< iterator, bool >	insert (P &&p)
	Insert a key-value pair into the map.
template<typename KArg, typename VArg> requires (!jh::typed::monostate_t<V>)
std::pair< iterator, bool >	insert_or_assign (KArg &&k, VArg &&v)
	Insert a key-value pair or assign to the mapped value.
template<typename... Args> requires (!jh::typed::monostate_t<V>)
std::pair< iterator, bool >	emplace (Args &&... args)
	Insert a key-value pair by constructing it from arbitrary arguments.
node_type::value_type &	at (const node_type::key_type &key)
	Access the mapped value associated with a key.
const node_type::value_type &	at (const node_type::key_type &key) const
	Access the mapped value associated with a key (const overload).
node_type::value_type &	operator[] (const node_type::key_type &key)
	Access or insert the mapped value associated with a key.
std::size_t	count (const node_type::key_type &key) const
	Count the number of elements with the specified key.
iterator	erase (iterator pos)
	Erase the element referenced by the given iterator.
iterator	erase (const_iterator pos)
	Erase the element referenced by the given const iterator.
std::size_t	erase (const node_type::key_type &key)
	Erase the element whose key compares equal to the given key.
iterator	lower_bound (const node_type::key_type &key)
	Return an iterator to the first element whose key is not less than the given key.
const_iterator	lower_bound (const node_type::key_type &key) const
	Const overload of lower_bound.
iterator	upper_bound (const node_type::key_type &key)
	Return an iterator to the first element whose key is greater than the given key.
const_iterator	upper_bound (const node_type::key_type &key) const
	Const overload of upper_bound.
std::pair< iterator, iterator >	equal_range (const node_type::key_type &key)
	Return the range of elements equivalent to the given key.
std::pair< const_iterator, const_iterator >	equal_range (const node_type::key_type &key) const
	Return the range of elements equivalent to the given key (const overload).
std::size_t	size () const noexcept
	Const overload of equal_range.
bool	empty () const noexcept
	Check whether the container contains no elements.
void	clear () noexcept
	Remove all elements from the container.
void	reserve (std::size_t n) noexcept(noexcept(nodes_.reserve(n)))
	Reserve space for at least n elements.
void	shrink_to_fit () noexcept(noexcept(nodes_.shrink_to_fit()))
	Request that the container reduce its capacity.
template<std::input_iterator It>
	tree_map (It first, It last)
	Construct a tree by inserting elements from an input iterator range.
template<std::ranges::input_range R>
	tree_map (R &&r)
	Construct a tree by inserting elements from an input range.

Static Public Member Functions
template<std::ranges::sized_range R>
static tree_map	from_sorted (R &&r)
	Construct an AVL tree from an already sorted and unique range.

Friends
template<typename, typename, typename>
class	tree_map
	Allow cross-instantiation friendship for different K,V,Alloc parameterizations.

Detailed Description

template<typename K, typename V, typename Alloc = std::allocator<detail::value_t<K, V>>>
class jh::avl::tree_map< K, V, Alloc >

Contiguous-array AVL tree used by jh::ordered_map and jh::ordered_set.

Overview

jh::avl::tree_map<K, V, Alloc> is the underlying container powering jh::ordered_map and jh::ordered_set. It implements a contiguous-array AVL tree in which all nodes are stored inside a single dynamic buffer (typically std::vector or a PMR-aware equivalent). Node linkage uses indices instead of pointers, enabling relocatable, fragmentation-free storage with excellent cache locality.

Purpose & Design Philosophy

This structure aims to provide an STL-like ordered associative container with performance and predictability guarantees that are difficult to achieve using the traditional node-based red-black tree employed by std::map and std::set. It is not intended as a drop-in replacement, but rather a complementary tool focused on:

Engineering stability in long-running systems
Zero fragmentation through contiguous storage
Predictable latency with no per-node allocations
High traversal speed due to cache-friendly layout
O(1) clear() behavior, especially with PMR resources
Optional O(N) construction from strictly sorted, unique input

Unlike the standard library's node-based trees, tree_map behaves partially like a std::vector: it exposes reserve(), shrink_to_fit(), and provides a clear() operation that simply resets the vector and does not deallocate individual nodes. This makes large-scale clearing and repopulation extremely efficient and stable under PMR allocators.

Performance Notes

This contiguous-array AVL tree has distinct performance behavior depending on whether the workload is insertion-heavy or access-heavy.

Insertion / Construction Cost

When constructing the tree via repeated insert() (i.e. the equivalent of default-constructing and inserting N elements), AVL rebalancing introduces a measurable overhead at small scales. For data sets around 10 k, construction is typically ≈ 1.3-1.6× the cost of std::map. As N grows, this overhead rapidly diminishes due to contiguous storage and negligible per-rotation cost; by 500 k elements the difference is only ~5-10%, and by 1 million elements insertion cost becomes effectively comparable to std::map.

For strictly sorted and unique input, from_sorted() bypasses all rotations and achieves near O(N) construction, outperforming any repeated-insert approach (including the standard library).

Lookup / Traversal Cost

Access-related operations—find(), in-order traversal, iteration—benefit strongly from contiguous memory layout and the smaller height of AVL trees. Beyond ~5 k elements, these operations are consistently faster than std::map, and remain faster at every larger scale tested. Across the 5 k-1 M range, typical speedups fall in the ≈ 15-30% faster range due to improved cache locality and stable successor cost.

Thus, although insertion may introduce some AVL-specific overhead at small scales, access performance dominates for large workloads, making the contiguous AVL structure an advantageous choice for systems where traversal, lookup, or iteration cost is critical.

O(N) Construction

For strictly sorted, strictly unique input ranges, tree_map::from_sorted() constructs a perfectly balanced AVL tree in near-linear time with no rotations and no repeated comparisons. This offers a fast, predictable path for bulk construction workflows.

Iteration Cost

The tree produced by from_sorted() is a perfectly balanced AVL laid out in a contiguous array. This structure has a remarkable property: the average cost of advancing an in-order iterator (operator++) is extremely close to a constant.

For a perfectly balanced binary search tree with N nodes, the expected number of pointer hops performed by operator++ converges to:


    E[successor steps] → 2.0  as N → ∞

This comes from the fact that more than half of all nodes are leaves, and their successor is simply the parent. Only a vanishingly small fraction of nodes require walking down a right subtree and then following several left edges. Measured average successor cost [by python3.11] was:

N	avg successor steps
10	1.70
100	1.93
1 000	1.99
10 000	1.9987
100 000	1.9998
1 000 000	2.0000

Therefore, in-order traversal runs in strictly linear time, with a very small constant factor, and does not grow with the height of the tree.

Template Parameters

K	Key type (must be strictly ordered via `operator<`)
V	Value type (use `jh::typed::monostate` for set semantics)
Alloc	Allocator for node storage; defaults to vector-compatible allocator

Member Typedef Documentation

◆ const_reverse_iterator

template<typename K, typename V, typename Alloc = std::allocator<detail::value_t<K, V>>>

using jh::avl::tree_map< K, V, Alloc >::const_reverse_iterator = std::reverse_iterator<const_iterator>

Const reverse iterator type.

Traverses elements in descending key order. All element access is read-only.

◆ reverse_iterator

template<typename K, typename V, typename Alloc = std::allocator<detail::value_t<K, V>>>

using jh::avl::tree_map< K, V, Alloc >::reverse_iterator = std::reverse_iterator<iterator>

Reverse iterator type.

Traverses elements in descending key order. Provides the same mutability as iterator.

Constructor & Destructor Documentation

◆ tree_map() [1/9]

template<typename K, typename V, typename Alloc = std::allocator<detail::value_t<K, V>>>

jh::avl::tree_map< K, V, Alloc >::tree_map ( const Alloc & alloc )

inlineexplicit

Construct an empty tree with a specified allocator.

Parameters

alloc allocator used for node storage

◆ tree_map() [2/9]

template<typename K, typename V, typename Alloc = std::allocator<detail::value_t<K, V>>>

template<typename K_, typename V_, typename Alloc_>

jh::avl::tree_map< K, V, Alloc >::tree_map ( const tree_map< K_, V_, Alloc_ > & other )

inlineexplicit

Copy-construct from another tree whose canonical key/value types match this tree and whose allocator type is identical.

Template Parameters

K_	Original (possibly cv/ref qualified) key type of the source tree.
V_	Original (possibly cv/ref qualified) value type of the source tree.
Alloc_	Allocator type of the source tree.

Parameters

other The source tree to copy from.

Participates only when the canonical forms of <K,V> and <K_,V_> produce the same internal node type. Thus, trees with different template arguments may still be interoperable if their canonical types coincide. Because the allocator types also match, the internal storage is copied directly without rebinding.

◆ tree_map() [3/9]

template<typename K, typename V, typename Alloc = std::allocator<detail::value_t<K, V>>>

template<typename K_, typename V_, typename Alloc_>

jh::avl::tree_map< K, V, Alloc >::tree_map ( const tree_map< K_, V_, Alloc_ > & other )

inlineexplicit

Copy-construct from another tree whose canonical key/value types match this tree, using a rebound default allocator.

Template Parameters

K_	Original (possibly cv/ref qualified) key type of the source tree.
V_	Original (possibly cv/ref qualified) value type of the source tree.
Alloc_	Allocator type of the source tree.

Parameters

other The source tree to copy from.

Enabled only when the canonical forms of <K,V> and <K_,V_> match. Because allocator types differ, the node buffer is copied into storage owned by a default-constructed allocator rebound to this tree's node type.

◆ tree_map() [4/9]

template<typename K, typename V, typename Alloc = std::allocator<detail::value_t<K, V>>>

template<typename K_, typename V_, typename Alloc_>

jh::avl::tree_map< K, V, Alloc >::tree_map	(	const tree_map< K_, V_, Alloc_ > &	other,
		const Alloc &	alloc )

inline

Copy-construct from another tree whose canonical key/value types match this tree, using a user-supplied allocator.

Template Parameters

K_	Original (possibly cv/ref qualified) key type of the source tree.
V_	Original (possibly cv/ref qualified) value type of the source tree.
Alloc_	Allocator type of the source tree.

Parameters

other	The source tree to copy from.
alloc	Allocator to be used for the new tree.

Enabled when canonical <K,V> and <K_,V_> denote the same node type. The provided allocator determines the new node buffer; node contents are copied from the source tree.

◆ tree_map() [5/9]

template<typename K, typename V, typename Alloc = std::allocator<detail::value_t<K, V>>>

template<typename K_, typename V_, typename Alloc_>

jh::avl::tree_map< K, V, Alloc >::tree_map ( tree_map< K_, V_, Alloc_ > && other )

inlineexplicitnoexcept

Move-construct from another tree whose canonical key/value types match this tree and whose allocator type is identical.

Template Parameters

K_	Source key type (possibly cv/ref qualified).
V_	Source value type (possibly cv/ref qualified).
Alloc_	Allocator type of the source tree.

Parameters

other The source tree to move from.

Enabled only when the canonical node types of <K,V> and <K_,V_> are identical and both trees use the same allocator type.

The underlying storage is transferred directly, producing a constant-time move. After the operation, other remains in a valid but unspecified state, consistent with the standard library's container move semantics.

◆ tree_map() [6/9]

template<typename K, typename V, typename Alloc = std::allocator<detail::value_t<K, V>>>

template<typename K_, typename V_, typename Alloc_>

jh::avl::tree_map< K, V, Alloc >::tree_map ( tree_map< K_, V_, Alloc_ > && other )

inlineexplicit

Move-construct from another tree whose canonical key/value types match this tree, using a rebound default allocator.

Template Parameters

K_	Source key type (possibly cv/ref qualified).
V_	Source value type (possibly cv/ref qualified).
Alloc_	Allocator type of the source tree.

Parameters

other The source tree to move from.

Enabled when canonical forms of <K,V> and <K_,V_> match but the allocator types differ. Node contents are moved element-wise into storage owned by a default-constructed allocator rebound to this tree's node type.

After the operation, other remains valid but unspecified. Its internal structure is not guaranteed (it may be partially moved-from), and callers should clear or reassign it before further use.

◆ tree_map() [7/9]

template<typename K, typename V, typename Alloc = std::allocator<detail::value_t<K, V>>>

template<typename K_, typename V_, typename Alloc_>

jh::avl::tree_map< K, V, Alloc >::tree_map	(	tree_map< K_, V_, Alloc_ > &&	other,
		const Alloc &	alloc )

inline

Move-construct from another tree whose canonical key/value types match this tree, using a user-supplied allocator.

Template Parameters

K_	Source key type (possibly cv/ref qualified).
V_	Source value type (possibly cv/ref qualified).
Alloc_	Allocator type of the source tree.

Parameters

other	The source tree to move from.
alloc	Allocator to be used for this tree.

Enabled when canonical node types match. Elements are moved into storage controlled by the supplied allocator. The source tree is left in a valid but unspecified state afterwards, consistent with standard container move semantics. Callers must clear or overwrite other if reuse is desired.

◆ tree_map() [8/9]

template<typename K, typename V, typename Alloc = std::allocator<detail::value_t<K, V>>>

template<std::input_iterator It>

jh::avl::tree_map< K, V, Alloc >::tree_map	(	It	first,
		It	last )

inline

Construct a tree by inserting elements from an input iterator range.

Template Parameters

It	Input iterator type whose dereferenced value is accepted by `insert()`.

Parameters

first	Iterator to the first element in the input range.
last	Iterator past the last element in the input range.

The tree is first initialized to an empty state via clear(), after which all elements in the range [first, last) are inserted using insert().

If It models std::random_access_iterator, the distance between first and last can be computed in constant time. This allows an implementation to pre-reserve exactly (last - first) nodes before insertion, reducing reallocation overhead.

Warning: Iterators must not falsely claim to be random-access. In particular, a type that is fundamentally bidirectional or forward must not provide random-access operations (e.g., operator[], operator+(int)) by emulating them via repeated operator++ or operator-- steps. Such "pseudo-random-access" iterators degrade performance severely, because the implementation may assume O(1) distance and indexing while the actual cost is O(n). Iterator category tags must accurately reflect the iterator's capabilities.

◆ tree_map() [9/9]

template<typename K, typename V, typename Alloc = std::allocator<detail::value_t<K, V>>>

template<std::ranges::input_range R>

jh::avl::tree_map< K, V, Alloc >::tree_map ( R && r )

inlineexplicit

Construct a tree by inserting elements from an input range.

Template Parameters

R	Input range type whose elements are accepted by `insert()`.

Parameters

r	The input range to consume.

The tree is cleared and each element of r is inserted using insert().

If R models std::ranges::sized_range, the node buffer may reserve space for std::size(r) elements prior to insertion. For random-access ranges this is typically O(1).

Warning: As with iterator-based construction, range types must not provide a misleading random-access iterator category. Emulating random-access semantics atop a non-random-access traversal (e.g., implementing operator[] by repeated increment operations) causes unnecessary O(n) behavior and defeats the intended performance guarantees.

Member Function Documentation

◆ at() [1/2]

template<typename K, typename V, typename Alloc = std::allocator<detail::value_t<K, V>>>

node_type::value_type & jh::avl::tree_map< K, V, Alloc >::at ( const node_type::key_type & key )

inline

Access the mapped value associated with a key.

Returns a reference to the mapped value corresponding to the specified key. Unlike operator[], this function does not insert a new element when the key is not found. Instead, it throws std::out_of_range.

Parameters

key	The key whose associated value is to be accessed.

Returns: A reference to the mapped value.

Exceptions

std::out_of_range Thrown if no element with the specified key exists.

◆ at() [2/2]

template<typename K, typename V, typename Alloc = std::allocator<detail::value_t<K, V>>>

const node_type::value_type & jh::avl::tree_map< K, V, Alloc >::at ( const node_type::key_type & key ) const

inlinenodiscard

Access the mapped value associated with a key (const overload).

Behaves identically to the non-const overload: if the key does not exist, this function throws std::out_of_range. No insertion ever occurs.

Parameters

key	The key whose associated value is to be accessed.

Returns: A const reference to the mapped value.

Exceptions

std::out_of_range Thrown if no element with the specified key exists.

◆ begin() [1/2]

template<typename K, typename V, typename Alloc = std::allocator<detail::value_t<K, V>>>

iterator jh::avl::tree_map< K, V, Alloc >::begin ( )

inline

Return an iterator to the smallest element.

If the container is empty, returns end().

◆ begin() [2/2]

template<typename K, typename V, typename Alloc = std::allocator<detail::value_t<K, V>>>

const_iterator jh::avl::tree_map< K, V, Alloc >::begin ( ) const

inlinenodiscard

Return a const iterator to the smallest element.

Identical to the non-const overload but produces a const_iterator. Returns end() if the container is empty.

◆ cbegin()

template<typename K, typename V, typename Alloc = std::allocator<detail::value_t<K, V>>>

const_iterator jh::avl::tree_map< K, V, Alloc >::cbegin ( ) const

inlinenodiscard

Return a const iterator to the first element.

Equivalent to begin() const.

◆ cend()

template<typename K, typename V, typename Alloc = std::allocator<detail::value_t<K, V>>>

const_iterator jh::avl::tree_map< K, V, Alloc >::cend ( ) const

inlinenodiscard

Return the const past-the-end iterator.

Equivalent to end() const.

◆ clear()

template<typename K, typename V, typename Alloc = std::allocator<detail::value_t<K, V>>>

void jh::avl::tree_map< K, V, Alloc >::clear ( )

inlinenoexcept

Remove all elements from the container.

Resets the container to an empty state by clearing the underlying contiguous storage and resetting the root index. The operation is equivalent to clearing a vector:

The size becomes zero, but the capacity is preserved.
No reallocation occurs.
Under polymorphic allocators (PMR), no element-by-element destruction or resource release takes place; the buffer is simply marked empty.

This gives clear an effectively constant-time cost. Unlike pointer-based tree structures such as those used by the standard ordered containers, there is no need to traverse and destroy individual nodes; the entire tree is discarded in one step.

Note: All iterators are invalidated.

◆ count()

template<typename K, typename V, typename Alloc = std::allocator<detail::value_t<K, V>>>

std::size_t jh::avl::tree_map< K, V, Alloc >::count ( const node_type::key_type & key ) const

inlinenodiscard

Count the number of elements with the specified key.

Because this container stores unique keys, the result is either 0 (key not present) or 1 (key present).

Parameters

key	The key to search for.

Returns: 1 if the key exists, 0 otherwise.

◆ crbegin()

template<typename K, typename V, typename Alloc = std::allocator<detail::value_t<K, V>>>

const_reverse_iterator jh::avl::tree_map< K, V, Alloc >::crbegin ( ) const

inlinenodiscard

Return a const reverse iterator to the last element.

Convenience wrapper identical to rbegin() const.

◆ crend()

template<typename K, typename V, typename Alloc = std::allocator<detail::value_t<K, V>>>

const_reverse_iterator jh::avl::tree_map< K, V, Alloc >::crend ( ) const

inlinenodiscard

Return the const reverse past-the-end iterator.

Convenience wrapper identical to rend() const. Represents the reverse-iterator view of –begin(), which equals the normal forward end().

◆ emplace() [1/2]

template<typename K, typename V, typename Alloc = std::allocator<detail::value_t<K, V>>>

template<typename... Args>
requires (!jh::typed::monostate_t<V>)

std::pair< iterator, bool > jh::avl::tree_map< K, V, Alloc >::emplace ( Args &&... args )

inline

Insert a key-value pair by constructing it from arbitrary arguments.

This function preserves the usual emplace semantics: the arguments are forwarded into a temporary std::pair<K, V> (note: K is used, not const K). The key and mapped value constructed in this temporary object are then forwarded into the internal insertion logic.

This matches the behavior of standard associative containers, where value_type is not directly constructed for emplacement because std::pair<const K, V> cannot be formed from arbitrary arguments. Only the key and mapped value are used.

If the key already exists in the map, construction still occurs but no insertion is performed; the returned boolean is false.

Parameters

args	Arguments used to construct a temporary `std::pair<K, V>`.

Returns

A pair consisting of:

An iterator to the existing or newly inserted element.
true if a new element was inserted, false otherwise.

◆ emplace() [2/2]

template<typename K, typename V, typename Alloc = std::allocator<detail::value_t<K, V>>>

template<typename... Args>
requires (jh::typed::monostate_t<V>)

std::pair< iterator, bool > jh::avl::tree_map< K, V, Alloc >::emplace ( Args &&... args )

inline

Construct a key and insert it into the set.

The key is constructed from the forwarded arguments and then inserted following standard set semantics. If the key already exists, no modification occurs. This overload exists even though the underlying node type uses only the key; construction is still routed through the key's constructor invoked with Args....

Parameters

args	Constructor arguments for the key.

Returns: A pair as with insert, indicating the inserted or existing position.

◆ empty()

template<typename K, typename V, typename Alloc = std::allocator<detail::value_t<K, V>>>

bool jh::avl::tree_map< K, V, Alloc >::empty ( ) const

inlinenodiscardnoexcept

Check whether the container contains no elements.

Equivalent to testing whether the underlying contiguous storage is empty. Does not modify the container and runs in constant time.

Returns: true if the container has no elements, otherwise false.

◆ end()

template<typename K, typename V, typename Alloc = std::allocator<detail::value_t<K, V>>>

iterator jh::avl::tree_map< K, V, Alloc >::end ( )

inline

Return the past-the-end iterator.

The returned iterator compares equal to all other past-the-end iterators for the same container.

◆ equal_range() [1/2]

template<typename K, typename V, typename Alloc = std::allocator<detail::value_t<K, V>>>

std::pair< iterator, iterator > jh::avl::tree_map< K, V, Alloc >::equal_range ( const node_type::key_type & key )

inline

Return the range of elements equivalent to the given key.

Provides the canonical equal_range semantics for associative containers with unique keys:

If an element with the given key exists, returns a pair {lower_bound(key), upper_bound(key)}.
If no such element exists, both iterators in the returned pair equal lower_bound(key).
The returned range is half-open: the first iterator refers to the element with the key (if present), and the second refers to the element that follows it.
Does not modify the container.

Parameters

key	The key to search for.

Returns: A pair of iterators defining the range of matching elements.

◆ equal_range() [2/2]

template<typename K, typename V, typename Alloc = std::allocator<detail::value_t<K, V>>>

std::pair< const_iterator, const_iterator > jh::avl::tree_map< K, V, Alloc >::equal_range ( const node_type::key_type & key ) const

inlinenodiscard

Return the range of elements equivalent to the given key (const overload).

Behaves identically to the non-const version but returns a pair of const_iterator.

Parameters

key	The key to search for.

Returns: A pair of const iterators defining the range of matching elements.

◆ erase() [1/3]

template<typename K, typename V, typename Alloc = std::allocator<detail::value_t<K, V>>>

std::size_t jh::avl::tree_map< K, V, Alloc >::erase ( const node_type::key_type & key )

inline

Erase the element whose key compares equal to the given key.

Searches for an element with the specified key and removes it if found. Iterator validity follows the rules of single-element erase:

If an element is erased, all iterators obtained prior to this call become invalid, as element removal and subsequent compaction may relocate nodes.
If no matching key exists, the container is left unmodified and no iterators are invalidated.

Parameters

key	The key of the element to remove.

Returns: 1 if an element was erased, 0 otherwise.

◆ erase() [2/3]

template<typename K, typename V, typename Alloc = std::allocator<detail::value_t<K, V>>>

iterator jh::avl::tree_map< K, V, Alloc >::erase ( const_iterator pos )

inline

Erase the element referenced by the given const iterator.

Removes the element pointed to by pos by delegating to the non-const overload erase(iterator). The behavior, iterator invalidation rules, and returned iterator semantics exactly match those of erase(iterator).

If pos equals end(), no removal occurs and pos is returned unchanged.

Parameters

pos	Const iterator referring to the element to erase.

Returns: An iterator to the in-order successor of the erased element, or end() if no successor exists.

◆ erase() [3/3]

template<typename K, typename V, typename Alloc = std::allocator<detail::value_t<K, V>>>

iterator jh::avl::tree_map< K, V, Alloc >::erase ( iterator pos )

inline

Erase the element referenced by the given iterator.

Removes the element pointed to by pos and returns an iterator to its logical in-order successor. If pos refers to end(), no action is performed and pos is returned unchanged.

Contiguous-array binary trees cannot preserve iterator validity after structural changes: erasing any element may relocate other nodes in the underlying storage. Therefore:

Every iterator obtained prior to this call, except the one returned by the function itself, becomes invalid and must not be used.
The returned iterator refers to the next element in sorted key order. If the erased element was the last in order, the returned iterator equals end().

The operation preserves AVL invariants and performs any required rebalancing after removal.

Parameters

pos	Iterator referring to the element to erase.

Returns: An iterator to the in-order successor of the erased element, or end() if no successor exists.

◆ find() [1/2]

template<typename K, typename V, typename Alloc = std::allocator<detail::value_t<K, V>>>

iterator jh::avl::tree_map< K, V, Alloc >::find ( const node_type::key_type & key )

inlinenodiscard

Locate the element with the specified key.

Performs a standard binary-search-tree lookup. If an element with the given key exists, returns an iterator referring to it. Otherwise returns end().

Parameters

key	The key to search for.

Returns: Iterator to the matching element, or end() if not found.

◆ find() [2/2]

template<typename K, typename V, typename Alloc = std::allocator<detail::value_t<K, V>>>

const_iterator jh::avl::tree_map< K, V, Alloc >::find ( const node_type::key_type & key ) const

inlinenodiscard

Locate the element with the specified key (const overload).

Behaves identically to the non-const version but returns a const_iterator.

Parameters

key	The key to search for.

Returns: Const iterator to the matching element, or end() if not found.

◆ from_sorted()

template<typename K, typename V, typename Alloc = std::allocator<detail::value_t<K, V>>>

template<std::ranges::sized_range R>

tree_map jh::avl::tree_map< K, V, Alloc >::from_sorted ( R && r )

inlinestatic

Construct an AVL tree from an already sorted and unique range.

Purpose

from_sorted() builds a perfectly balanced contiguous AVL tree directly from a sorted, strictly-unique input range. Unlike repeated insert(), which performs O(log N) insertions with rebalancing, this routine constructs the entire tree in near-perfect O(N) time.

The input must satisfy:

strictly increasing keys (already sorted),
no duplicates,
size known (std::ranges::sized_range),
value_type convertible to std::pair<const K, V> for jh::ordered_map or K for jh::ordered_set.

Why This Matters

Many workloads naturally produce ordered batches: log-structured indexing, preprocessing pipelines, analytics results, time-sorted packets, or any domain where data is accumulated in vectors. Constructing the jh::ordered_set/map directly from this monotonic sequence avoids the costly per-node insertion and removes the need for AVL rotations.

Complexity

Construction: O(N) (tree shape derived directly)
Iterator validity: all iterators valid post-construction
Recursion: none (iterative layout)

Performance Characteristics

Benchmarked on an Apple M3 (Clang++20) with 10 000 random or sorted std::string keys:

Operation	Runtime (ns)	Notes
`ordered_set.insert (random)`	1.4 e7 (~14 ms)	AVL rotations + random memory access
`ordered_set.insert (sorted)`	significantly faster	input order strongly affects performance
`stable_sort(10k strings)`	~9.6 e6 (~9.6 ms)	merge sort detects ordered runs
`unique(10k strings)`	~1 e5 (0.1 ms)	linear; negligible vs sorting
`from_sorted (10k strings)`	~8.6 e5 (0.86 ms)	builds perfect AVL directly
Synthesis: `sort + unique + from_sorted`	~1.06 e7 (~10.6 ms)	< `insert` cost even when input is fully random

Interpretation

Even with completely random input, a vector → sort → unique → from_sorted pipeline is faster than 10k random AVL insertions.
For already-sorted or partially-sorted sequences, runtime becomes almost linear and outperforms both ordered_set and std::set.
stable_sort is strongly order-aware; partially sorted sequences reduce its cost dramatically.
unique() cost is negligible compared to sorting.
Memory locality is maximized: all nodes fit in one contiguous vector.

When To Use

Bulk construction from preprocessed or batched data.
Loading on-disk sorted indices.
Temporal/event logs with strictly increasing timestamps.
Any context where std::set/map would require many insertions.
When memory fragmentation must be tightly controlled.

Example

std::vector<int> v = {...};
std::stable_sort(v.begin(), v.end());
sorted.erase(std::unique(v.begin(), v.end()), v.end());
auto s = jh::ordered_set<int>::from_sorted(v);
// s is a perfectly balanced AVL using contiguous storage

Template Parameters

R	a sized, sorted, strictly unique input range

Parameters

r	range whose values will be copied/moved into the resulting tree

Returns: a fully constructed, perfectly balanced tree_map

Warning: Input must be sorted and unique. No validation is performed.

◆ insert() [1/3]

template<typename K, typename V, typename Alloc = std::allocator<detail::value_t<K, V>>>

std::pair< iterator, bool > jh::avl::tree_map< K, V, Alloc >::insert ( const value_type & key )

inline

Insert a key into the set.

For set semantics, value_type is simply the key type K. If the key does not already exist, it is inserted and the returned boolean is true. Otherwise the existing element is returned and no modification occurs.

Parameters

key	The key to insert.

Returns

A pair consisting of:

An iterator to the existing or newly inserted key.
true if insertion occurred, false otherwise.

◆ insert() [2/3]

template<typename K, typename V, typename Alloc = std::allocator<detail::value_t<K, V>>>

template<typename P>
requires (!jh::typed::monostate_t<V>)

std::pair< iterator, bool > jh::avl::tree_map< K, V, Alloc >::insert ( P && p )

inline

Insert a key-value pair into the map.

This overload generalizes the traditional std::pair<const K, V>-based insertion interface. Instead of requiring a value_type object, any 2-element tuple-like value is accepted as long as:

get<0>(p) has type K (after remove_cvref)
get<1>(p) has type V (after remove_cvref)

This reflects the actual insertion semantics: the container consumes the key and mapped value directly rather than constructing a std::pair<const K, V> object, which is generally not constructible from user input. Any tuple-like pair (including std::pair, std::tuple, proxy references, and structured-binding-compatible types) is therefore permitted if its element types match exactly.
If the key already exists, no insertion occurs and the boolean return value is false.

Template Parameters

P	The tuple-like type providing key and mapped value.

Parameters

p	A tuple-like value providing key and mapped value.

Returns

A pair containing:

An iterator to the existing or newly inserted element.
true if a new element was inserted, false otherwise.

◆ insert() [3/3]

template<typename K, typename V, typename Alloc = std::allocator<detail::value_t<K, V>>>

std::pair< iterator, bool > jh::avl::tree_map< K, V, Alloc >::insert ( value_type & key )

inline

Insert a key into the set (non-const reference overload).

Behaves identically to the const-reference overload. Provided for completeness and consistency with associative-container interfaces.

◆ insert_or_assign()

template<typename K, typename V, typename Alloc = std::allocator<detail::value_t<K, V>>>

template<typename KArg, typename VArg>
requires (!jh::typed::monostate_t<V>)

std::pair< iterator, bool > jh::avl::tree_map< K, V, Alloc >::insert_or_assign	(	KArg &&	k,
		VArg &&	v )

inline

Insert a key-value pair or assign to the mapped value.

This function provides the combined "insert or assign" behavior used by ordered associative maps. The key and mapped value are accepted as forwarding references, allowing both lvalues and rvalues to be supplied. When rvalues are provided, their contents may be moved into the container.

The behavior is:

If no element with the same key exists, a new element is inserted using the forwarded key and value.
If an element with the same key already exists, its mapped value is replaced by the forwarded value.

This mirrors the semantics of std::map::insert_or_assign.

Parameters

k	The key of the element to insert or update (forwarded).
v	The mapped value to assign or insert (forwarded).

Returns

A pair consisting of:

An iterator to the inserted or updated element.
true if a new element was inserted, false if an existing element was updated.

◆ lower_bound() [1/2]

template<typename K, typename V, typename Alloc = std::allocator<detail::value_t<K, V>>>

iterator jh::avl::tree_map< K, V, Alloc >::lower_bound ( const node_type::key_type & key )

inline

Return an iterator to the first element whose key is not less than the given key.

Provides the standard ordered-container lower-bound semantics:

Returns an iterator referring to the first element whose key is greater than or equal to key.
If no such element exists, returns end().
Does not modify the container.

◆ lower_bound() [2/2]

template<typename K, typename V, typename Alloc = std::allocator<detail::value_t<K, V>>>

const_iterator jh::avl::tree_map< K, V, Alloc >::lower_bound ( const node_type::key_type & key ) const

inlinenodiscard

Const overload of lower_bound.

Behaves identically to the non-const version but returns a const iterator.

◆ operator[]()

template<typename K, typename V, typename Alloc = std::allocator<detail::value_t<K, V>>>

node_type::value_type & jh::avl::tree_map< K, V, Alloc >::operator[] ( const node_type::key_type & key )

inline

Access or insert the mapped value associated with a key.

This operator provides the standard map-style subscript semantics. If an element with the given key already exists, a reference to its mapped value is returned. Otherwise, a new element is created with the specified key and a value-initialized mapped value (V{}), and a reference to that mapped value is returned.

Unlike at(), this function never throws: missing keys always cause insertion. For this reason, it is only available when the mapped type V is default-initializable.

Parameters

key	The key whose associated value is to be accessed.

Returns: A reference to the existing or newly inserted mapped value.

◆ rbegin() [1/2]

template<typename K, typename V, typename Alloc = std::allocator<detail::value_t<K, V>>>

reverse_iterator jh::avl::tree_map< K, V, Alloc >::rbegin ( )

inline

Return a reverse iterator to the last element.

Implemented as reverse_iterator(end()). A reverse iterator constructed from end() yields the position obtained conceptually by –end(), which is the element with the greatest key.

◆ rbegin() [2/2]

template<typename K, typename V, typename Alloc = std::allocator<detail::value_t<K, V>>>

const_reverse_iterator jh::avl::tree_map< K, V, Alloc >::rbegin ( ) const

inlinenodiscard

Return a const reverse iterator to the last element.

Same semantics as the non-const overload: constructed from end(), representing the position produced by the conceptual operation –end().

◆ rend() [1/2]

template<typename K, typename V, typename Alloc = std::allocator<detail::value_t<K, V>>>

reverse_iterator jh::avl::tree_map< K, V, Alloc >::rend ( )

inline

Return the reverse past-the-end iterator.

Implemented as reverse_iterator(begin()). Because reverse_iterator stores the base iterator and defines its past-the-end position as the value conceptually equal to –begin(), this corresponds to the reverse end.

Notably, –begin() is the normal forward end(); therefore this reverse iterator represents the position one step before begin() in reverse traversal.

◆ rend() [2/2]

template<typename K, typename V, typename Alloc = std::allocator<detail::value_t<K, V>>>

const_reverse_iterator jh::avl::tree_map< K, V, Alloc >::rend ( ) const

inlinenodiscard

Return the const reverse past-the-end iterator.

Same semantics as the non-const overload: constructed from begin(), representing the reverse past-the-end position associated with the conceptual –begin(), which equals the normal forward end().

◆ reserve()

template<typename K, typename V, typename Alloc = std::allocator<detail::value_t<K, V>>>

void jh::avl::tree_map< K, V, Alloc >::reserve ( std::size_t n )

inlinenoexcept

Reserve space for at least n elements.

Requests that the underlying contiguous storage grow its capacity to at least n elements. This operation does not change the size of the container or alter any existing node indices.

Since iterators refer to elements by stable indices rather than pointers, increasing capacity does not invalidate any iterators, even if the underlying buffer is reallocated.

Calling reserve with a value smaller than the current size is no-op, according to ISO C++11+ standards for standard containers.

With polymorphic allocators (PMR), reserve typically has minimal overhead, as the resource may enlarge the buffer without a full reallocation.

Parameters

n	Minimum capacity to reserve.

◆ shrink_to_fit()

template<typename K, typename V, typename Alloc = std::allocator<detail::value_t<K, V>>>

void jh::avl::tree_map< K, V, Alloc >::shrink_to_fit ( )

inlinenoexcept

Request that the container reduce its capacity.

Issues a non-binding request to the underlying contiguous storage to reduce its capacity. The behavior matches that of std::vector::shrink_to_fit:

The operation may reduce capacity, but is not required to do so.
There is no guarantee that the resulting capacity equals the size.
Under polymorphic allocators (PMR), the resource may keep the existing buffer unchanged.
Because iterators reference elements by index, not pointer, this operation never invalidates iterators.

◆ upper_bound()

template<typename K, typename V, typename Alloc = std::allocator<detail::value_t<K, V>>>

iterator jh::avl::tree_map< K, V, Alloc >::upper_bound ( const node_type::key_type & key )

inline

Return an iterator to the first element whose key is greater than the given key.

Matches the usual ordered-container semantics:

Returns an iterator referring to the first element for which element.key > key.
If no such element exists, returns end().
Does not modify the container.

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

include/jh/core/ordered_map.h

Classes

Public Types

Public Member Functions

Static Public Member Functions

Friends

Detailed Description

Overview

Purpose & Design Philosophy

Performance Notes

Insertion / Construction Cost

Lookup / Traversal Cost

O(N) Construction

Iteration Cost

Member Typedef Documentation

◆ const_reverse_iterator

◆ reverse_iterator

Constructor & Destructor Documentation

◆ tree_map() [1/9]

◆ tree_map() [2/9]

◆ tree_map() [3/9]

◆ tree_map() [4/9]

◆ tree_map() [5/9]

◆ tree_map() [6/9]

◆ tree_map() [7/9]

◆ tree_map() [8/9]

◆ tree_map() [9/9]

Member Function Documentation

◆ at() [1/2]

◆ at() [2/2]

◆ begin() [1/2]

◆ begin() [2/2]

◆ cbegin()

◆ cend()

◆ clear()

◆ count()

◆ crbegin()

◆ crend()

◆ emplace() [1/2]

◆ emplace() [2/2]

◆ empty()

◆ end()

◆ equal_range() [1/2]

◆ equal_range() [2/2]

◆ erase() [1/3]

◆ erase() [2/3]

◆ erase() [3/3]

◆ find() [1/2]

◆ find() [2/2]

◆ from_sorted()

Purpose

Why This Matters

Complexity

Performance Characteristics

Interpretation

When To Use

Example

◆ insert() [1/3]

◆ insert() [2/3]

◆ insert() [3/3]

◆ insert_or_assign()

◆ lower_bound() [1/2]

◆ lower_bound() [2/2]

◆ operator[]()

◆ rbegin() [1/2]

◆ rbegin() [2/2]

◆ rend() [1/2]

◆ rend() [2/2]

◆ reserve()

◆ shrink_to_fit()

◆ upper_bound()