tpl_flat_set.H File Reference

Sorted-array set (Aleph::FlatSet), a cache-friendly ordered set. More...

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

Include dependency graph for tpl_flat_set.H:

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

Go to the source code of this file.

Classes
class	Aleph::FlatSet< Key, Compare >
	Ordered set stored as a sorted contiguous array. More...

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

Detailed Description

Sorted-array set (Aleph::FlatSet), a cache-friendly ordered set.

FlatSet<Key, Compare> keeps its keys sorted inside a single contiguous MemArray<Key>. Lookups are binary searches over contiguous memory (O(log n) with excellent cache behavior); insertions and removals shift elements (O(n)). It is the classic flat container trade-off, in the spirit of C++23 std::flat_set and boost::container::flat_set:

Operation	FlatSet	DynSetTree (AVL/RB)
find / contains	O(log n), contiguous	O(log n), pointer chasing
insert / erase	O(n) shift	O(log n)
iteration	O(n), sequential memory	O(n), pointer chasing
memory per element	sizeof(Key)	sizeof(Key) + node overhead

Prefer FlatSet for lookup- and iteration-heavy workloads whose modification phase is bulk or infrequent. Prefer DynSetTree when insertions and removals are frequent and interleaved with lookups.

Note

This is a native Aleph implementation and is used under every supported standard (C++17/20/23). It deliberately does not alias std::flat_set when available: the standard adaptor has different reference/iterator semantics, and aliasing would make the container's exact behavior depend on -std. The detection macro ALEPH_HAS_STD_FLAT_MAP (see ah-cpp-compat.H) remains available for consumers that want the standard adaptor itself.

See also

tpl_flat_map.H Sorted-array map counterpart.

tpl_dynSetTree.H Balanced-tree sets (fast mutation).

Author

Leandro Rabindranath Leon

Definition in file tpl_flat_set.H.