tpl_flat_map.H File Reference

Sorted-array map (Aleph::FlatMap), a cache-friendly ordered map. More...

#include <algorithm>
#include <initializer_list>
#include <iterator>
#include <utility>
#include <ah-errors.H>
#include <ahFunction.H>
#include <htlist.H>
#include <tpl_memArray.H>
#include <tpl_sort_utils.H>

Include dependency graph for tpl_flat_map.H:

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

Go to the source code of this file.

Classes
class	Aleph::FlatMap< Key, T, Compare >
	Ordered map stored as two parallel sorted contiguous arrays. More...
class	Aleph::FlatMap< Key, T, Compare >::basic_iterator< IsConst >
	Random-access proxy iterator over (key, value) entries. More...
struct	Aleph::FlatMap< Key, T, Compare >::basic_iterator< IsConst >::reference
	Proxy returned by operator*: references into the parallel arrays. More...
struct	Aleph::FlatMap< Key, T, Compare >::basic_iterator< IsConst >::pointer
	Proxy returned by operator->, keeps the reference alive. More...

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

Detailed Description

Sorted-array map (Aleph::FlatMap), a cache-friendly ordered map.

FlatMap<Key, T, Compare> keeps two parallel contiguous arrays — one of sorted keys, one of values — mirroring the design of C++23 std::flat_map. Binary searches touch only the key array, so lookups are as cache-friendly as they can get; insertions and removals shift both arrays (O(n)).

Operation	FlatMap	DynMapTree (AVL/RB)
find / at / operator[] (hit)	O(log n), key array only	O(log n), pointer chasing
insert / erase	O(n) shift	O(log n)
iteration	O(n), sequential memory	O(n), pointer chasing
memory per entry	sizeof(Key) + sizeof(T)	+ node overhead

Prefer FlatMap for lookup- and iteration-heavy workloads whose modification phase is bulk or infrequent. Prefer DynMapTree when insertions and removals are frequent.

Note

Like std::flat_map (and unlike node-based maps), dereferencing an iterator yields a proxy {const Key &first; T &second;} rather than a reference to a stored std::pair. Use auto [k, v] = *it; or it->second; do not form std::pair<Key,T> & references.

This is a native Aleph implementation used under every supported standard; it does not alias std::flat_map (see the rationale in tpl_flat_set.H).

See also

tpl_flat_set.H Sorted-array set counterpart (and rationale notes).

tpl_dynMapTree.H Balanced-tree maps (fast mutation).

Author

Leandro Rabindranath Leon

Definition in file tpl_flat_map.H.