Ordered set stored as a sorted contiguous array. More...

#include <tpl_flat_set.H>

Collaboration diagram for Aleph::FlatSet< Key, Compare >:

Public Types
using	Item_Type = Key
	Aleph convention: element type.

using	Key_Type = Key
	Aleph convention: key type.

using	key_type = Key
	STL convention: key type.

using	value_type = Key
	STL convention: value type.

using	key_compare = Compare
	STL convention: comparator type.

using	size_type = size_t
	STL convention: size type.

using	iterator = const Key *
	Random-access iterator (immutable).

using	const_iterator = const Key *
	Random-access const iterator.

Public Member Functions
	FlatSet (size_t cap=MemArray< Key >::Min_Dim)
	Construct an empty set.

	FlatSet (const Compare &cmp, size_t cap=MemArray< Key >::Min_Dim)
	Construct an empty set with a specific comparator.

template<std::input_iterator It>
	FlatSet (It first, It last, const Compare &cmp=Compare())
	Construct from an iterator range.

	FlatSet (std::initializer_list< Key > l, const Compare &cmp=Compare())
	Construct from an initializer list.

	FlatSet (const FlatSet &)=default
	Copy constructor (requires copyable `Key`).

	FlatSet (FlatSet &&) noexcept=default
	Move constructor. The source is left valid but unspecified.

FlatSet &	operator= (const FlatSet &)=default
	Copy assignment (requires copyable `Key`).

FlatSet &	operator= (FlatSet &&) noexcept=default
	Move assignment. The source is left valid but unspecified.

	~FlatSet ()=default

void	swap (FlatSet &s) noexcept(std::is_nothrow_swappable_v< Compare >)
	Swap contents with `s` in O(1).

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

bool	is_empty () const noexcept
	Return `true` if the set holds no keys. O(1).

size_t	capacity () const noexcept
	Return the capacity of the backing array. O(1).

void	reserve (size_t cap)
	Reserve capacity for at least `cap` keys.

void	empty () noexcept
	Remove all keys (Aleph convention).

void	clear () noexcept
	Remove all keys. Alias of `empty()`. Capacity is kept.

const_iterator	find (const Key &k) const
	Find a key.

bool	contains (const Key &k) const
	Test membership.

size_t	count (const Key &k) const
	Count occurrences of a key (0 or 1).

const_iterator	lower_bound (const Key &k) const
	First element not less than `k`.

const_iterator	upper_bound (const Key &k) const
	First element greater than `k`.

std::pair< const_iterator, const_iterator >	equal_range (const Key &k) const
	Range of elements equivalent to `k`.

const Key &	nth (size_t i) const
	Positional access to the i-th smallest key (checked).

const Key &	operator() (size_t i) const noexcept
	Positional access without bounds checking.

const Key &	get_first () const
	Smallest key (checked).

const Key &	get_last () const
	Greatest key (checked).

const Key &	min () const
	Smallest key (checked). Alias of `get_first()`.

const Key &	max () const
	Greatest key (checked). Alias of `get_last()`.

std::pair< const_iterator, bool >	insert (const Key &k)
	Insert a copy of `k` if no equivalent key exists.

std::pair< const_iterator, bool >	insert (Key &&k)
	Insert `k` by moving if no equivalent key exists.

template<class... Args>
std::pair< const_iterator, bool >	emplace (Args &&...args)
	Construct a key in place and insert it.

size_t	erase (const Key &k)
	Remove the key equivalent to `k`, if present.

const_iterator	erase (const_iterator it)
	Remove the key at iterator `it`.

const_iterator	begin () const noexcept
	Iterator to the smallest key. O(1).

const_iterator	end () const noexcept
	Iterator past the greatest key. O(1).

const_iterator	cbegin () const noexcept
	Const iterator to the smallest key. O(1).

const_iterator	cend () const noexcept
	Const iterator past the greatest key. O(1).

const Key *	data () const noexcept
	Pointer to the underlying sorted, contiguous storage. O(1).

template<class Operation >
bool	traverse (Operation operation) const
	Traverse keys in sorted order while `operation` returns `true`.

bool	operator== (const FlatSet &s) const
	Equality: same size and pairwise equal elements.

bool	operator!= (const FlatSet &s) const
	Inequality: negation of `operator==`.

Private Member Functions
size_t	lower_idx (const Key &k) const

size_t	upper_idx (const Key &k) const

bool	match_at (size_t pos, const Key &k) const

void	make_room (const size_t pos)

void	remove_at (const size_t pos)

void	sort_and_unique ()

Private Attributes
MemArray< Key >	keys_

Compare	cmp_

Detailed Description

template<typename Key, class Compare = Aleph::less<Key>>
class Aleph::FlatSet< Key, Compare >

Ordered set stored as a sorted contiguous array.

Keys are kept sorted according to Compare inside a MemArray<Key>. All lookup operations are binary searches over contiguous memory; all mutating operations preserve the sorted invariant by shifting elements.

Duplicate keys (keys equivalent under Compare) are not stored: an insertion of an equivalent key leaves the set unchanged.

Template Parameters

Key	Type of the stored keys. Must be default-constructible, move-constructible and move-assignable (requirements inherited from `MemArray`).
Compare	Strict weak ordering over `Key`. Defaults to `Aleph::less<Key>`.

Iterators: Iterators are plain const Key * pointers (contiguous, random access). As with std::set, elements are immutable through iterators: mutating a key in place would break the sorted invariant. Any insertion or removal invalidates all iterators.

Aleph conventions: Following the library convention (see Array), empty() clears the container and is_empty() is the emptiness predicate.

Exception Safety: insert offers the strong guarantee up to the element shift: if the key copy/move assignment throws mid-shift, the guarantee degrades to basic (the container remains valid, contents unspecified). erase always removes the element; a failed shrinking reallocation is ignored.

Thread Safety: Distinct instances may be used from distinct threads. Concurrent access to the same instance requires external synchronization.

Example: FlatSet<int> s = {5, 1, 3, 1}; // builds {1, 3, 5}

s.insert(4); // {1, 3, 4, 5}

if (s.contains(3)) ...

for (int x : s) // sorted iteration

std::cout << x << " ";

Aleph::FlatSet
Ordered set stored as a sorted contiguous array.
Definition tpl_flat_set.H:129

Aleph::FlatSet::contains
bool contains(const Key &k) const
Test membership.
Definition tpl_flat_set.H:359

Aleph::FlatSet::insert
std::pair< const_iterator, bool > insert(const Key &k)
Insert a copy of k if no equivalent key exists.
Definition tpl_flat_set.H:465

std
STL namespace.

Definition at line 128 of file tpl_flat_set.H.

Member Typedef Documentation

◆ const_iterator

template<typename Key , class Compare = Aleph::less<Key>>

using Aleph::FlatSet< Key, Compare >::const_iterator = const Key *

Random-access const iterator.

Definition at line 224 of file tpl_flat_set.H.

◆ Item_Type

template<typename Key , class Compare = Aleph::less<Key>>

using Aleph::FlatSet< Key, Compare >::Item_Type = Key

Aleph convention: element type.

Definition at line 217 of file tpl_flat_set.H.

◆ iterator

template<typename Key , class Compare = Aleph::less<Key>>

using Aleph::FlatSet< Key, Compare >::iterator = const Key *

Random-access iterator (immutable).

Definition at line 223 of file tpl_flat_set.H.

◆ key_compare

template<typename Key , class Compare = Aleph::less<Key>>

using Aleph::FlatSet< Key, Compare >::key_compare = Compare

STL convention: comparator type.

Definition at line 221 of file tpl_flat_set.H.

◆ Key_Type

template<typename Key , class Compare = Aleph::less<Key>>

using Aleph::FlatSet< Key, Compare >::Key_Type = Key

Aleph convention: key type.

Definition at line 218 of file tpl_flat_set.H.

◆ key_type

template<typename Key , class Compare = Aleph::less<Key>>

using Aleph::FlatSet< Key, Compare >::key_type = Key

STL convention: key type.

Definition at line 219 of file tpl_flat_set.H.

◆ size_type

template<typename Key , class Compare = Aleph::less<Key>>

using Aleph::FlatSet< Key, Compare >::size_type = size_t

STL convention: size type.

Definition at line 222 of file tpl_flat_set.H.

◆ value_type

template<typename Key , class Compare = Aleph::less<Key>>

using Aleph::FlatSet< Key, Compare >::value_type = Key

STL convention: value type.

Definition at line 220 of file tpl_flat_set.H.

Constructor & Destructor Documentation

◆ FlatSet() [1/6]

template<typename Key , class Compare = Aleph::less<Key>>

Aleph::FlatSet< Key, Compare >::FlatSet ( size_t cap = MemArray<Key>::Min_Dim )

inlineexplicit

Construct an empty set.

Parameters

cap	Initial capacity hint (rounded up to a power of two by the backing `MemArray`).

Exceptions

std::bad_alloc if the initial buffer cannot be allocated.

Definition at line 232 of file tpl_flat_set.H.

◆ FlatSet() [2/6]

template<typename Key , class Compare = Aleph::less<Key>>

Aleph::FlatSet< Key, Compare >::FlatSet	(	const Compare &	cmp,
		size_t	cap = `MemArray<Key>::Min_Dim`
	)

inlineexplicit

Construct an empty set with a specific comparator.

Parameters

cmp	Comparator instance to copy.
cap	Initial capacity hint.

Exceptions

std::bad_alloc if the initial buffer cannot be allocated.

Definition at line 240 of file tpl_flat_set.H.

◆ FlatSet() [3/6]

template<typename Key , class Compare = Aleph::less<Key>>

template<std::input_iterator It>

Aleph::FlatSet< Key, Compare >::FlatSet	(	It	first,
		It	last,
		const Compare &	cmp = `Compare()`
	)

inline

Construct from an iterator range.

Loads all elements, then sorts once and removes duplicates: O(m log m) for m input elements, which beats m individual O(n) insertions.

Template Parameters

It	Input iterator whose value type converts to `Key`.

Parameters

first	Beginning of the range.
last	End of the range.
cmp	Comparator instance (defaulted).

Exceptions

std::bad_alloc if memory allocation fails.

Note: On duplicate (equivalent) inputs the first occurrence wins.

Definition at line 256 of file tpl_flat_set.H.

References Aleph::FlatSet< Key, Compare >::keys_, Aleph::MemArray< T >::put(), and Aleph::FlatSet< Key, Compare >::sort_and_unique().

◆ FlatSet() [4/6]

template<typename Key , class Compare = Aleph::less<Key>>

Aleph::FlatSet< Key, Compare >::FlatSet	(	std::initializer_list< Key >	l,
		const Compare &	cmp = `Compare()`
	)

inline

Construct from an initializer list.

Parameters

l	Elements to load; duplicates are dropped (first wins).
cmp	Comparator instance (defaulted).

Exceptions

std::bad_alloc if memory allocation fails.

Definition at line 270 of file tpl_flat_set.H.

◆ FlatSet() [5/6]

template<typename Key , class Compare = Aleph::less<Key>>

Aleph::FlatSet< Key, Compare >::FlatSet ( const FlatSet< Key, Compare > & )

default

Copy constructor (requires copyable Key).

◆ FlatSet() [6/6]

template<typename Key , class Compare = Aleph::less<Key>>

Aleph::FlatSet< Key, Compare >::FlatSet ( FlatSet< Key, Compare > && )

defaultnoexcept

Move constructor. The source is left valid but unspecified.

◆ ~FlatSet()

template<typename Key , class Compare = Aleph::less<Key>>

Aleph::FlatSet< Key, Compare >::~FlatSet ( )

default

Member Function Documentation

◆ begin()

template<typename Key , class Compare = Aleph::less<Key>>

const_iterator Aleph::FlatSet< Key, Compare >::begin ( ) const

inlinenoexcept

Iterator to the smallest key. O(1).

Definition at line 540 of file tpl_flat_set.H.

References Aleph::MemArray< T >::get_ptr(), and Aleph::FlatSet< Key, Compare >::keys_.

Referenced by Aleph::FlatSet< Key, Compare >::cbegin(), Aleph::FlatSet< Key, Compare >::erase(), Aleph::FlatSet< Key, Compare >::find(), Aleph::FlatSet< Key, Compare >::insert(), Aleph::FlatSet< Key, Compare >::insert(), Aleph::FlatSet< Key, Compare >::lower_bound(), Aleph::FlatSet< Key, Compare >::operator==(), TEST(), TEST(), TEST(), TEST(), and Aleph::FlatSet< Key, Compare >::upper_bound().

◆ capacity()

template<typename Key , class Compare = Aleph::less<Key>>

size_t Aleph::FlatSet< Key, Compare >::capacity ( ) const

inlinenoexcept

Return the capacity of the backing array. O(1).

Definition at line 312 of file tpl_flat_set.H.

References Aleph::MemArray< T >::capacity(), and Aleph::FlatSet< Key, Compare >::keys_.

Referenced by TEST().

◆ cbegin()

template<typename Key , class Compare = Aleph::less<Key>>

const_iterator Aleph::FlatSet< Key, Compare >::cbegin ( ) const

inlinenoexcept

Const iterator to the smallest key. O(1).

Definition at line 552 of file tpl_flat_set.H.

References Aleph::FlatSet< Key, Compare >::begin().

◆ cend()

template<typename Key , class Compare = Aleph::less<Key>>

const_iterator Aleph::FlatSet< Key, Compare >::cend ( ) const

inlinenoexcept

Const iterator past the greatest key. O(1).

Definition at line 558 of file tpl_flat_set.H.

References Aleph::FlatSet< Key, Compare >::end().

◆ clear()

template<typename Key , class Compare = Aleph::less<Key>>

void Aleph::FlatSet< Key, Compare >::clear ( )

inlinenoexcept

Remove all keys. Alias of empty(). Capacity is kept.

Definition at line 336 of file tpl_flat_set.H.

References Aleph::MemArray< T >::clear(), and Aleph::FlatSet< Key, Compare >::keys_.

Referenced by TEST().

◆ contains()

template<typename Key , class Compare = Aleph::less<Key>>

bool Aleph::FlatSet< Key, Compare >::contains ( const Key & k ) const

inline

Test membership.

Parameters

k	Key to search for.

Returns: true if an equivalent key is stored.

Note: Complexity: O(log n).

Definition at line 359 of file tpl_flat_set.H.

References k, Aleph::FlatSet< Key, Compare >::lower_idx(), and Aleph::FlatSet< Key, Compare >::match_at().

Referenced by Aleph::FlatSet< Key, Compare >::count(), TEST(), TEST(), TEST(), TEST(), TEST(), and TEST().

◆ count()

template<typename Key , class Compare = Aleph::less<Key>>

size_t Aleph::FlatSet< Key, Compare >::count ( const Key & k ) const

inline

Count occurrences of a key (0 or 1).

Parameters

k	Key to search for.

Returns: 1 if present, 0 otherwise.

Note: Complexity: O(log n).

Definition at line 369 of file tpl_flat_set.H.

References Aleph::FlatSet< Key, Compare >::contains(), and k.

Referenced by TEST().

◆ data()

template<typename Key , class Compare = Aleph::less<Key>>

const Key * Aleph::FlatSet< Key, Compare >::data ( ) const

inlinenoexcept

Pointer to the underlying sorted, contiguous storage. O(1).

Definition at line 564 of file tpl_flat_set.H.

References Aleph::MemArray< T >::get_ptr(), and Aleph::FlatSet< Key, Compare >::keys_.

Referenced by TEST().

◆ emplace()

template<typename Key , class Compare = Aleph::less<Key>>

template<class... Args>

std::pair< const_iterator, bool > Aleph::FlatSet< Key, Compare >::emplace ( Args &&... args )

inline

Construct a key in place and insert it.

The key is constructed once from args and then moved into position, so this is a convenience over insert(Key(args...)), not a true in-place construction (the sorted position must be searched first).

Template Parameters

Args	Argument types forwarded to `Key`'s constructor.

Parameters

args	Arguments forwarded to `Key`'s constructor.

Returns: Pair of (iterator to the key in the set, insertion flag).

Exceptions

std::bad_alloc if a growing reallocation fails.

Definition at line 503 of file tpl_flat_set.H.

References Aleph::blossom_maximum_cardinality_matching(), and Aleph::FlatSet< Key, Compare >::insert().

◆ empty()

template<typename Key , class Compare = Aleph::less<Key>>

void Aleph::FlatSet< Key, Compare >::empty ( )

inlinenoexcept

Remove all keys (Aleph convention).

Capacity is kept.

Note: Following the Aleph container convention (see Array::empty()), this mutates the set; use is_empty() to test for emptiness.

Definition at line 330 of file tpl_flat_set.H.

References Aleph::MemArray< T >::empty(), and Aleph::FlatSet< Key, Compare >::keys_.

Referenced by TEST().

◆ end()

template<typename Key , class Compare = Aleph::less<Key>>

const_iterator Aleph::FlatSet< Key, Compare >::end ( ) const

inlinenoexcept

Iterator past the greatest key. O(1).

Definition at line 546 of file tpl_flat_set.H.

References Aleph::MemArray< T >::get_ptr(), Aleph::FlatSet< Key, Compare >::keys_, and Aleph::MemArray< T >::size().

Referenced by Aleph::FlatSet< Key, Compare >::cend(), Aleph::FlatSet< Key, Compare >::find(), Aleph::FlatSet< Key, Compare >::operator==(), TEST(), TEST(), TEST(), TEST(), and TEST().

◆ equal_range()

template<typename Key , class Compare = Aleph::less<Key>>

std::pair< const_iterator, const_iterator > Aleph::FlatSet< Key, Compare >::equal_range ( const Key & k ) const

inline

Range of elements equivalent to k.

Parameters

k	Key to bound.

Returns: Pair {lower_bound(k), upper_bound(k)} (length 0 or 1).

Note: Complexity: O(log n).

Definition at line 399 of file tpl_flat_set.H.

References k, Aleph::FlatSet< Key, Compare >::lower_bound(), and Aleph::FlatSet< Key, Compare >::upper_bound().

Referenced by TEST().

◆ erase() [1/2]

template<typename Key , class Compare = Aleph::less<Key>>

size_t Aleph::FlatSet< Key, Compare >::erase ( const Key & k )

inline

Remove the key equivalent to k, if present.

Parameters

k	Key to remove.

Returns: Number of removed elements (0 or 1).

Note: Complexity: O(log n) search + O(n) shift. Never throws on the removal itself; a failed shrinking reallocation is ignored.

Definition at line 514 of file tpl_flat_set.H.

References Aleph::blossom_maximum_cardinality_matching(), k, Aleph::FlatSet< Key, Compare >::lower_idx(), Aleph::FlatSet< Key, Compare >::match_at(), and Aleph::FlatSet< Key, Compare >::remove_at().

Referenced by TEST(), and TEST().

◆ erase() [2/2]

template<typename Key , class Compare = Aleph::less<Key>>

const_iterator Aleph::FlatSet< Key, Compare >::erase ( const_iterator it )

inline

Remove the key at iterator it.

Parameters

it	Valid dereferenceable iterator into this set.

Returns: Iterator to the element following the removed one.

Exceptions

std::out_of_range if it does not point into the set.

Note: Complexity: O(n) shift. All other iterators are invalidated.

Definition at line 529 of file tpl_flat_set.H.

References ah_out_of_range_error_if, Aleph::FlatSet< Key, Compare >::begin(), Aleph::FlatSet< Key, Compare >::remove_at(), and Aleph::FlatSet< Key, Compare >::size().

◆ find()

template<typename Key , class Compare = Aleph::less<Key>>

const_iterator Aleph::FlatSet< Key, Compare >::find ( const Key & k ) const

inline

Find a key.

Parameters

k	Key to search for.

Returns: Iterator to the matching key, or end() if absent.

Note: Complexity: O(log n) over contiguous memory.

Definition at line 348 of file tpl_flat_set.H.

References Aleph::FlatSet< Key, Compare >::begin(), Aleph::FlatSet< Key, Compare >::end(), k, Aleph::FlatSet< Key, Compare >::lower_idx(), and Aleph::FlatSet< Key, Compare >::match_at().

Referenced by TEST(), and TEST().

◆ get_first()

template<typename Key , class Compare = Aleph::less<Key>>

const Key & Aleph::FlatSet< Key, Compare >::get_first ( ) const

inline

Smallest key (checked).

Returns: Const reference to the minimum.

Exceptions

std::underflow_error if the set is empty.

Definition at line 428 of file tpl_flat_set.H.

References ah_underflow_error_if, Aleph::FlatSet< Key, Compare >::is_empty(), and Aleph::FlatSet< Key, Compare >::keys_.

Referenced by Aleph::FlatSet< Key, Compare >::min(), and TEST().

◆ get_last()

template<typename Key , class Compare = Aleph::less<Key>>

const Key & Aleph::FlatSet< Key, Compare >::get_last ( ) const

inline

Greatest key (checked).

Returns: Const reference to the maximum.

Exceptions

std::underflow_error if the set is empty.

Definition at line 438 of file tpl_flat_set.H.

References ah_underflow_error_if, Aleph::FlatSet< Key, Compare >::is_empty(), Aleph::FlatSet< Key, Compare >::keys_, and Aleph::MemArray< T >::size().

Referenced by Aleph::FlatSet< Key, Compare >::max(), and TEST().

◆ insert() [1/2]

template<typename Key , class Compare = Aleph::less<Key>>

std::pair< const_iterator, bool > Aleph::FlatSet< Key, Compare >::insert ( const Key & k )

inline

Insert a copy of k if no equivalent key exists.

Parameters

k	Key to insert.

Returns: Pair of (iterator to the key in the set, true if inserted / false if an equivalent key was already present).

Exceptions

std::bad_alloc if a growing reallocation fails.

Note: Complexity: O(log n) search + O(n) shift.

Definition at line 465 of file tpl_flat_set.H.

References Aleph::FlatSet< Key, Compare >::begin(), Aleph::MemArray< T >::get_ptr(), k, Aleph::FlatSet< Key, Compare >::keys_, Aleph::FlatSet< Key, Compare >::lower_idx(), Aleph::FlatSet< Key, Compare >::make_room(), and Aleph::FlatSet< Key, Compare >::match_at().

Referenced by Aleph::FlatSet< Key, Compare >::emplace(), TEST(), TEST(), TEST(), and TEST().

◆ insert() [2/2]

template<typename Key , class Compare = Aleph::less<Key>>

std::pair< const_iterator, bool > Aleph::FlatSet< Key, Compare >::insert ( Key && k )

inline

Insert k by moving if no equivalent key exists.

Parameters

k	Key to move in.

Returns: Pair of (iterator to the key in the set, insertion flag).

Exceptions

std::bad_alloc if a growing reallocation fails.

Note: Complexity: O(log n) search + O(n) shift.

Definition at line 481 of file tpl_flat_set.H.

References Aleph::FlatSet< Key, Compare >::begin(), Aleph::MemArray< T >::get_ptr(), k, Aleph::FlatSet< Key, Compare >::keys_, Aleph::FlatSet< Key, Compare >::lower_idx(), Aleph::FlatSet< Key, Compare >::make_room(), and Aleph::FlatSet< Key, Compare >::match_at().

◆ is_empty()

template<typename Key , class Compare = Aleph::less<Key>>

bool Aleph::FlatSet< Key, Compare >::is_empty ( ) const

inlinenoexcept

Return true if the set holds no keys. O(1).

Definition at line 306 of file tpl_flat_set.H.

References Aleph::MemArray< T >::is_empty(), and Aleph::FlatSet< Key, Compare >::keys_.

Referenced by Aleph::FlatSet< Key, Compare >::get_first(), Aleph::FlatSet< Key, Compare >::get_last(), TEST(), and TEST().

◆ lower_bound()

template<typename Key , class Compare = Aleph::less<Key>>

const_iterator Aleph::FlatSet< Key, Compare >::lower_bound ( const Key & k ) const

inline

First element not less than k.

Parameters

k	Key to bound.

Returns: Iterator to the first element e with not cmp(e, k), or end().

Note: Complexity: O(log n).

Definition at line 379 of file tpl_flat_set.H.

References Aleph::FlatSet< Key, Compare >::begin(), k, and Aleph::FlatSet< Key, Compare >::lower_idx().

Referenced by Aleph::FlatSet< Key, Compare >::equal_range(), and TEST().

◆ lower_idx()

template<typename Key , class Compare = Aleph::less<Key>>

size_t Aleph::FlatSet< Key, Compare >::lower_idx ( const Key & k ) const

inlineprivate

Definition at line 134 of file tpl_flat_set.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::FlatSet< Key, Compare >::cmp_, k, Aleph::FlatSet< Key, Compare >::keys_, and Aleph::MemArray< T >::size().

Referenced by Aleph::FlatSet< Key, Compare >::contains(), Aleph::FlatSet< Key, Compare >::erase(), Aleph::FlatSet< Key, Compare >::find(), Aleph::FlatSet< Key, Compare >::insert(), Aleph::FlatSet< Key, Compare >::insert(), and Aleph::FlatSet< Key, Compare >::lower_bound().

◆ make_room()

template<typename Key , class Compare = Aleph::less<Key>>

void Aleph::FlatSet< Key, Compare >::make_room ( const size_t pos )

inlineprivate

Definition at line 165 of file tpl_flat_set.H.

References Aleph::MemArray< T >::get_ptr(), Aleph::FlatSet< Key, Compare >::keys_, Aleph::MemArray< T >::putn(), and Aleph::MemArray< T >::size().

Referenced by Aleph::FlatSet< Key, Compare >::insert(), and Aleph::FlatSet< Key, Compare >::insert().

◆ match_at()

template<typename Key , class Compare = Aleph::less<Key>>

bool Aleph::FlatSet< Key, Compare >::match_at	(	size_t	pos,
		const Key &	k
	)		const

inlineprivate

Definition at line 159 of file tpl_flat_set.H.

References Aleph::and, Aleph::blossom_maximum_cardinality_matching(), Aleph::FlatSet< Key, Compare >::cmp_, k, Aleph::FlatSet< Key, Compare >::keys_, and Aleph::MemArray< T >::size().

Referenced by Aleph::FlatSet< Key, Compare >::contains(), Aleph::FlatSet< Key, Compare >::erase(), Aleph::FlatSet< Key, Compare >::find(), Aleph::FlatSet< Key, Compare >::insert(), and Aleph::FlatSet< Key, Compare >::insert().

◆ max()

template<typename Key , class Compare = Aleph::less<Key>>

const Key & Aleph::FlatSet< Key, Compare >::max ( ) const

inline

Greatest key (checked). Alias of get_last().

Definition at line 451 of file tpl_flat_set.H.

References Aleph::FlatSet< Key, Compare >::get_last().

Referenced by TEST().

◆ min()

template<typename Key , class Compare = Aleph::less<Key>>

const Key & Aleph::FlatSet< Key, Compare >::min ( ) const

inline

Smallest key (checked). Alias of get_first().

Definition at line 445 of file tpl_flat_set.H.

References Aleph::FlatSet< Key, Compare >::get_first().

Referenced by TEST().

◆ nth()

template<typename Key , class Compare = Aleph::less<Key>>

const Key & Aleph::FlatSet< Key, Compare >::nth ( size_t i ) const

inline

Positional access to the i-th smallest key (checked).

Parameters

i	Zero-based rank.

Returns: Const reference to the i-th key in sorted order.

Exceptions

std::out_of_range if i >= size().

Note: Complexity: O(1). This is the flat-container bonus over trees.

Definition at line 410 of file tpl_flat_set.H.

References Aleph::FlatSet< Key, Compare >::keys_.

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

◆ operator!=()

template<typename Key , class Compare = Aleph::less<Key>>

bool Aleph::FlatSet< Key, Compare >::operator!= ( const FlatSet< Key, Compare > & s ) const

inline

Inequality: negation of operator==.

Definition at line 602 of file tpl_flat_set.H.

References Aleph::blossom_maximum_cardinality_matching().

◆ operator()()

template<typename Key , class Compare = Aleph::less<Key>>

const Key & Aleph::FlatSet< Key, Compare >::operator() ( size_t i ) const

inlinenoexcept

Positional access without bounds checking.

Parameters

i	Zero-based rank (must be `< size()`).

Returns: Const reference to the i-th key in sorted order.

Definition at line 419 of file tpl_flat_set.H.

References Aleph::FlatSet< Key, Compare >::keys_.

◆ operator=() [1/2]

template<typename Key , class Compare = Aleph::less<Key>>

FlatSet & Aleph::FlatSet< Key, Compare >::operator= ( const FlatSet< Key, Compare > & )

default

Copy assignment (requires copyable Key).

◆ operator=() [2/2]

template<typename Key , class Compare = Aleph::less<Key>>

FlatSet & Aleph::FlatSet< Key, Compare >::operator= ( FlatSet< Key, Compare > && )

defaultnoexcept

Move assignment. The source is left valid but unspecified.

◆ operator==()

template<typename Key , class Compare = Aleph::less<Key>>

bool Aleph::FlatSet< Key, Compare >::operator== ( const FlatSet< Key, Compare > & s ) const

inline

Equality: same size and pairwise equal elements.

Parameters

s	Set to compare against.

Returns: true if both sets hold equal elements in the same order.

Note: Complexity: O(n). Requires Key to be equality comparable.

Definition at line 596 of file tpl_flat_set.H.

References Aleph::and, Aleph::FlatSet< Key, Compare >::begin(), Aleph::FlatSet< Key, Compare >::end(), and Aleph::FlatSet< Key, Compare >::size().

◆ remove_at()

template<typename Key , class Compare = Aleph::less<Key>>

void Aleph::FlatSet< Key, Compare >::remove_at ( const size_t pos )

inlineprivate

Definition at line 175 of file tpl_flat_set.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::MemArray< T >::get(), Aleph::MemArray< T >::get_ptr(), Aleph::FlatSet< Key, Compare >::keys_, and Aleph::MemArray< T >::size().

Referenced by Aleph::FlatSet< Key, Compare >::erase(), and Aleph::FlatSet< Key, Compare >::erase().

◆ reserve()

template<typename Key , class Compare = Aleph::less<Key>>

void Aleph::FlatSet< Key, Compare >::reserve ( size_t cap )

inline

Reserve capacity for at least cap keys.

Parameters

cap	Desired capacity (rounded up to a power of two).

Exceptions

std::bad_alloc if memory allocation fails.

Definition at line 321 of file tpl_flat_set.H.

References Aleph::FlatSet< Key, Compare >::keys_, and Aleph::MemArray< T >::reserve().

Referenced by TEST().

◆ size()

template<typename Key , class Compare = Aleph::less<Key>>

size_t Aleph::FlatSet< Key, Compare >::size ( ) const

inlinenoexcept

Return the number of stored keys. O(1).

Definition at line 300 of file tpl_flat_set.H.

References Aleph::FlatSet< Key, Compare >::keys_, and Aleph::MemArray< T >::size().

Referenced by Aleph::FlatSet< Key, Compare >::erase(), Aleph::FlatSet< Key, Compare >::operator==(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), and TEST().

◆ sort_and_unique()

template<typename Key , class Compare = Aleph::less<Key>>

void Aleph::FlatSet< Key, Compare >::sort_and_unique ( )

inlineprivate

Definition at line 194 of file tpl_flat_set.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::FlatSet< Key, Compare >::cmp_, Aleph::MemArray< T >::get(), Aleph::MemArray< T >::get_ptr(), Aleph::FlatSet< Key, Compare >::keys_, m, Aleph::MemArray< T >::size(), and Aleph::timsort().

Referenced by Aleph::FlatSet< Key, Compare >::FlatSet().

◆ swap()

template<typename Key , class Compare = Aleph::less<Key>>

void Aleph::FlatSet< Key, Compare >::swap ( FlatSet< Key, Compare > & s )

inlinenoexcept

Swap contents with s in O(1).

Parameters

s	Set to swap with.

Definition at line 291 of file tpl_flat_set.H.

References Aleph::FlatSet< Key, Compare >::cmp_, Aleph::FlatSet< Key, Compare >::keys_, and Aleph::MemArray< T >::swap().

Referenced by TEST().

◆ traverse()

template<typename Key , class Compare = Aleph::less<Key>>

template<class Operation >

bool Aleph::FlatSet< Key, Compare >::traverse ( Operation operation ) const

inline

Traverse keys in sorted order while operation returns true.

Aleph-style bounded traversal: operation receives each key (as const Key &) in ascending order; returning false stops the walk.

Template Parameters

Operation Callable bool(const Key &).

Parameters

operation Operation to apply.

Returns: true if all keys were visited, false if stopped early.

Definition at line 579 of file tpl_flat_set.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::MemArray< T >::get_ptr(), Aleph::FlatSet< Key, Compare >::keys_, m, and Aleph::MemArray< T >::size().

Referenced by TEST().

◆ upper_bound()

template<typename Key , class Compare = Aleph::less<Key>>

const_iterator Aleph::FlatSet< Key, Compare >::upper_bound ( const Key & k ) const

inline

First element greater than k.

Parameters

k	Key to bound.

Returns: Iterator to the first element e with cmp(k, e), or end().

Note: Complexity: O(log n).

Definition at line 389 of file tpl_flat_set.H.

References Aleph::FlatSet< Key, Compare >::begin(), k, and Aleph::FlatSet< Key, Compare >::upper_idx().

Referenced by Aleph::FlatSet< Key, Compare >::equal_range(), and TEST().

◆ upper_idx()

template<typename Key , class Compare = Aleph::less<Key>>

size_t Aleph::FlatSet< Key, Compare >::upper_idx ( const Key & k ) const

inlineprivate

Definition at line 146 of file tpl_flat_set.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::FlatSet< Key, Compare >::cmp_, k, Aleph::FlatSet< Key, Compare >::keys_, and Aleph::MemArray< T >::size().

Referenced by Aleph::FlatSet< Key, Compare >::upper_bound().

Member Data Documentation

◆ cmp_

template<typename Key , class Compare = Aleph::less<Key>>

Compare Aleph::FlatSet< Key, Compare >::cmp_

private

Definition at line 131 of file tpl_flat_set.H.

Referenced by Aleph::FlatSet< Key, Compare >::lower_idx(), Aleph::FlatSet< Key, Compare >::match_at(), Aleph::FlatSet< Key, Compare >::sort_and_unique(), Aleph::FlatSet< Key, Compare >::swap(), and Aleph::FlatSet< Key, Compare >::upper_idx().

◆ keys_

template<typename Key , class Compare = Aleph::less<Key>>

MemArray<Key> Aleph::FlatSet< Key, Compare >::keys_

private

Definition at line 130 of file tpl_flat_set.H.

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

tpl_flat_set.H

Public Types

Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

Member Typedef Documentation

◆ const_iterator

◆ Item_Type

◆ iterator

◆ key_compare

◆ Key_Type

◆ key_type

◆ size_type

◆ value_type

Constructor & Destructor Documentation

◆ FlatSet() [1/6]

◆ FlatSet() [2/6]

◆ FlatSet() [3/6]

◆ FlatSet() [4/6]

◆ FlatSet() [5/6]

◆ FlatSet() [6/6]

◆ ~FlatSet()

Member Function Documentation

◆ begin()

◆ capacity()

◆ cbegin()

◆ cend()

◆ clear()

◆ contains()

◆ count()

◆ data()

◆ emplace()

◆ empty()

◆ end()

◆ equal_range()

◆ erase() [1/2]

◆ erase() [2/2]

◆ find()

◆ get_first()

◆ get_last()

◆ insert() [1/2]

◆ insert() [2/2]

◆ is_empty()

◆ lower_bound()

◆ lower_idx()

◆ make_room()

◆ match_at()

◆ max()

◆ min()

◆ nth()

◆ operator!=()

◆ operator()()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ operator==()

◆ remove_at()

◆ reserve()

◆ size()

◆ sort_and_unique()

◆ swap()

◆ traverse()

◆ upper_bound()

◆ upper_idx()

Member Data Documentation

◆ cmp_

◆ keys_