hxflat_set< key_t_, compare_t_, multi_t_, capacity_ > Class Template Reference

#include <hxflat_set.hpp>

Public Types
using	key_t = key_t_
using	compare_t = compare_t_
using	iterator = const key_t_*
using	const_iterator = const key_t_*

Public Member Functions
	hxflat_set (void)
	hxflat_set (const hxflat_set &x_) noexcept
	hxflat_set (hxflat_set &&x_) noexcept
	~hxflat_set (void) noexcept
void	operator= (const hxflat_set &x_) noexcept
template<hxsize_t capacity_x_>
void	operator= (const hxflat_set< key_t_, compare_t_, multi_t_, capacity_x_ > &x_) noexcept
void	operator= (hxflat_set &&x_) noexcept
const key_t_ *	operator[] (hxsize_t index_) const
const key_t_ *	begin (void) const
hxsize_t	capacity (void) const
const key_t_ *	cbegin (void) const
const key_t_ *	cend (void) const
void	clear (void) noexcept
hxsize_t	count (const key_t_ &key_) const
bool	empty (void) const
const key_t_ *	end (void) const
template<hxsize_t capacity_x_>
bool	equal (const hxflat_set< key_t_, compare_t_, multi_t_, capacity_x_ > &x_) const
hxsize_t	erase (const key_t_ &key_) noexcept
const key_t_ *	erase (const key_t_ *pos_) noexcept
const key_t_ *	find (const key_t_ &key_) const
bool	full (void) const
const key_t_ *	insert (const key_t_ &key_) noexcept
const key_t_ *	insert (key_t_ &&key_) noexcept
template<hxsize_t capacity_x_>
bool	less (const hxflat_set< key_t_, compare_t_, multi_t_, capacity_x_ > &x_) const
const key_t_ *	lower_bound (const key_t_ &key_) const
hxsize_t	max_size (void) const
void	reserve (hxsize_t cap_, hxsystem_allocator_t allocator_=hxsystem_allocator_current, hxalignment_t alignment_=hxalignment)
hxsize_t	size (void) const
void	swap (hxflat_set &x_) noexcept
const key_t_ *	upper_bound (const key_t_ &key_) const

Detailed Description

template<typename key_t_, typename compare_t_ = hxkey_less_t<key_t_>, bool multi_t_ = true, hxsize_t capacity_ = hxallocator_dynamic_capacity>
class hxflat_set< key_t_, compare_t_, multi_t_, capacity_ >

hxflat_set - A sorted associative container that stores keys in a single array.

Lookup is Θ(log n) via binary search. Insert and erase are Θ(n) because elements are shifted to maintain order. This design keeps keys cache-friendly and avoids heap overhead per element.

When multi_t is false duplicate keys are rejected and insert returns a pointer to the existing element. When multi_t is true duplicate keys are always inserted. compare_t must be a callable with signature bool(const key_t_&, const key_t_&) returning true when the first argument is ordered before the second. It defaults to hxkey_less_t.

When capacity is hxallocator_dynamic_capacity storage must be allocated by calling reserve before inserting elements. Otherwise the array is statically sized to capacity elements and reserve may only be called with exactly that value. extract() is not provided, just use data().

E.g.:

// A static flat set of 64 integers.
hxflat_set<int, hxkey_less_t<int>, false, 64> lookup;

• key_t : Key type.
• compare_t : Callable implementing a strict weak order on key_t.
• multi_t : When true duplicate keys are allowed.
• capacity : Fixed element count or hxallocator_dynamic_capacity.

Member Typedef Documentation

compare_t

template<typename key_t_, typename compare_t_ = hxkey_less_t<key_t_>, bool multi_t_ = true, hxsize_t capacity_ = hxallocator_dynamic_capacity>

using hxflat_set< key_t_, compare_t_, multi_t_, capacity_ >::compare_t = compare_t_

const_iterator

template<typename key_t_, typename compare_t_ = hxkey_less_t<key_t_>, bool multi_t_ = true, hxsize_t capacity_ = hxallocator_dynamic_capacity>

using hxflat_set< key_t_, compare_t_, multi_t_, capacity_ >::const_iterator = const key_t_*

const_iterator - Const random access iterator over keys.

iterator

template<typename key_t_, typename compare_t_ = hxkey_less_t<key_t_>, bool multi_t_ = true, hxsize_t capacity_ = hxallocator_dynamic_capacity>

using hxflat_set< key_t_, compare_t_, multi_t_, capacity_ >::iterator = const key_t_*

iterator - Random access iterator over keys.

key_t

template<typename key_t_, typename compare_t_ = hxkey_less_t<key_t_>, bool multi_t_ = true, hxsize_t capacity_ = hxallocator_dynamic_capacity>

using hxflat_set< key_t_, compare_t_, multi_t_, capacity_ >::key_t = key_t_

Constructor & Destructor Documentation

hxflat_set() [1/3]

template<typename key_t_, typename compare_t_ = hxkey_less_t<key_t_>, bool multi_t_ = true, hxsize_t capacity_ = hxallocator_dynamic_capacity>

hxflat_set< key_t_, compare_t_, multi_t_, capacity_ >::hxflat_set ( void )

explicit

Constructs an empty set.

Requires reserve before inserting when capacity is hxallocator_dynamic_capacity.

hxflat_set() [2/3]

template<typename key_t_, typename compare_t_ = hxkey_less_t<key_t_>, bool multi_t_ = true, hxsize_t capacity_ = hxallocator_dynamic_capacity>

hxflat_set< key_t_, compare_t_, multi_t_, capacity_ >::hxflat_set ( const hxflat_set< key_t_, compare_t_, multi_t_, capacity_ > & x_ )

noexcept

Copy constructs from another hxflat_set.

Requires x.size() ≤ capacity().

• x : A non-temporary hxflat_set<key_t, compare_t, multi_t, capacity>.

hxflat_set() [3/3]

template<typename key_t_, typename compare_t_ = hxkey_less_t<key_t_>, bool multi_t_ = true, hxsize_t capacity_ = hxallocator_dynamic_capacity>

hxflat_set< key_t_, compare_t_, multi_t_, capacity_ >::hxflat_set ( hxflat_set< key_t_, compare_t_, multi_t_, capacity_ > && x_ )

noexcept

Move constructs from a temporary hxflat_set.

Requires hxallocator_dynamic_capacity.

• x : A temporary hxflat_set<key_t, compare_t, multi_t, hxallocator_dynamic_capacity>.

~hxflat_set()

template<typename key_t_, typename compare_t_ = hxkey_less_t<key_t_>, bool multi_t_ = true, hxsize_t capacity_ = hxallocator_dynamic_capacity>

hxflat_set< key_t_, compare_t_, multi_t_, capacity_ >::~hxflat_set ( void )

noexcept

Destructs the set and destroys all keys.

Member Function Documentation

begin()

template<typename key_t_, typename compare_t_ = hxkey_less_t<key_t_>, bool multi_t_ = true, hxsize_t capacity_ = hxallocator_dynamic_capacity>

const key_t_ * hxflat_set< key_t_, compare_t_, multi_t_, capacity_ >::begin ( void ) const

inline

Returns a const pointer to the first element.

capacity()

template<typename key_t_, typename compare_t_ = hxkey_less_t<key_t_>, bool multi_t_ = true, hxsize_t capacity_ = hxallocator_dynamic_capacity>

hxsize_t hxflat_set< key_t_, compare_t_, multi_t_, capacity_ >::capacity

(

void

)

const

Returns the capacity of the set or 0 if unallocated.

cbegin()

template<typename key_t_, typename compare_t_ = hxkey_less_t<key_t_>, bool multi_t_ = true, hxsize_t capacity_ = hxallocator_dynamic_capacity>

const key_t_ * hxflat_set< key_t_, compare_t_, multi_t_, capacity_ >::cbegin ( void ) const

inline

Returns a const pointer to the first element (alias for begin).

cend()

template<typename key_t_, typename compare_t_ = hxkey_less_t<key_t_>, bool multi_t_ = true, hxsize_t capacity_ = hxallocator_dynamic_capacity>

const key_t_ * hxflat_set< key_t_, compare_t_, multi_t_, capacity_ >::cend ( void ) const

inline

Returns a const pointer past the last element.

clear()

template<typename key_t_, typename compare_t_ = hxkey_less_t<key_t_>, bool multi_t_ = true, hxsize_t capacity_ = hxallocator_dynamic_capacity>

void hxflat_set< key_t_, compare_t_, multi_t_, capacity_ >::clear ( void )

noexcept

Removes all elements and destroys their keys.

count()

template<typename key_t_, typename compare_t_ = hxkey_less_t<key_t_>, bool multi_t_ = true, hxsize_t capacity_ = hxallocator_dynamic_capacity>

hxsize_t hxflat_set< key_t_, compare_t_, multi_t_, capacity_ >::count

(

const key_t_ &

key_

)

const

Returns the number of elements with the given key.

• key : The key to count.

empty()

template<typename key_t_, typename compare_t_ = hxkey_less_t<key_t_>, bool multi_t_ = true, hxsize_t capacity_ = hxallocator_dynamic_capacity>

bool hxflat_set< key_t_, compare_t_, multi_t_, capacity_ >::empty ( void ) const

inline

Checks if the set contains no elements.

end()

template<typename key_t_, typename compare_t_ = hxkey_less_t<key_t_>, bool multi_t_ = true, hxsize_t capacity_ = hxallocator_dynamic_capacity>

const key_t_ * hxflat_set< key_t_, compare_t_, multi_t_, capacity_ >::end ( void ) const

inline

Returns a const pointer past the last element.

equal()

template<typename key_t_, typename compare_t_ = hxkey_less_t<key_t_>, bool multi_t_ = true, hxsize_t capacity_ = hxallocator_dynamic_capacity>

template<hxsize_t capacity_x_>

bool hxflat_set< key_t_, compare_t_, multi_t_, capacity_ >::equal

(

const hxflat_set< key_t_, compare_t_, multi_t_, capacity_x_ > &

x_

)

const

Returns true if this set and x contain the same keys in the same order using hxkey_equal.

• x : The set to compare against.

erase() [1/2]

template<typename key_t_, typename compare_t_ = hxkey_less_t<key_t_>, bool multi_t_ = true, hxsize_t capacity_ = hxallocator_dynamic_capacity>

hxsize_t hxflat_set< key_t_, compare_t_, multi_t_, capacity_ >::erase ( const key_t_ & key_ )

noexcept

Removes all elements with the given key and destroys their keys.

Returns the number of elements removed.

• key : The key to search for and remove.

erase() [2/2]

template<typename key_t_, typename compare_t_ = hxkey_less_t<key_t_>, bool multi_t_ = true, hxsize_t capacity_ = hxallocator_dynamic_capacity>

const key_t_ * hxflat_set< key_t_, compare_t_, multi_t_, capacity_ >::erase ( const key_t_ * pos_ )

noexcept

Removes the element at the pointer position and destroys the key.

Returns a const pointer to the element that followed the erased one.

• pos : A const pointer to an element in this set.

find()

template<typename key_t_, typename compare_t_ = hxkey_less_t<key_t_>, bool multi_t_ = true, hxsize_t capacity_ = hxallocator_dynamic_capacity>

const key_t_ * hxflat_set< key_t_, compare_t_, multi_t_, capacity_ >::find

(

const key_t_ &

key_

)

const

Returns a const pointer to the key if found, or hxnull if not present.

When multi_t is true the first match is returned.

• key : The key to search for.

full()

template<typename key_t_, typename compare_t_ = hxkey_less_t<key_t_>, bool multi_t_ = true, hxsize_t capacity_ = hxallocator_dynamic_capacity>

bool hxflat_set< key_t_, compare_t_, multi_t_, capacity_ >::full ( void ) const

inline

Returns true if the set has reached its capacity.

insert() [1/2]

template<typename key_t_, typename compare_t_ = hxkey_less_t<key_t_>, bool multi_t_ = true, hxsize_t capacity_ = hxallocator_dynamic_capacity>

const key_t_ * hxflat_set< key_t_, compare_t_, multi_t_, capacity_ >::insert ( const key_t_ & key_ )

noexcept

Inserts a key.

When multi_t is false and a matching key already exists, returns a const pointer to the existing element without inserting. Otherwise inserts in sorted order and returns a const pointer to the new element.

• key : The key to insert.

insert() [2/2]

template<typename key_t_, typename compare_t_ = hxkey_less_t<key_t_>, bool multi_t_ = true, hxsize_t capacity_ = hxallocator_dynamic_capacity>

const key_t_ * hxflat_set< key_t_, compare_t_, multi_t_, capacity_ >::insert ( key_t_ && key_ )

noexcept

Move overload of insert.

• key : The key forwarded into storage.

less()

template<typename key_t_, typename compare_t_ = hxkey_less_t<key_t_>, bool multi_t_ = true, hxsize_t capacity_ = hxallocator_dynamic_capacity>

template<hxsize_t capacity_x_>

bool hxflat_set< key_t_, compare_t_, multi_t_, capacity_ >::less

(

const hxflat_set< key_t_, compare_t_, multi_t_, capacity_x_ > &

x_

)

const

Returns true if this set compares less than x lexicographically, using hxkey_equal and hxkey_less on keys.

• x : The set to compare against.

lower_bound()

template<typename key_t_, typename compare_t_ = hxkey_less_t<key_t_>, bool multi_t_ = true, hxsize_t capacity_ = hxallocator_dynamic_capacity>

const key_t_ * hxflat_set< key_t_, compare_t_, multi_t_, capacity_ >::lower_bound

(

const key_t_ &

key_

)

const

Returns a const pointer to the first element whose key is not ordered before key.

Returns end if no such element exists.

• key : The key to search for.

max_size()

template<typename key_t_, typename compare_t_ = hxkey_less_t<key_t_>, bool multi_t_ = true, hxsize_t capacity_ = hxallocator_dynamic_capacity>

hxsize_t hxflat_set< key_t_, compare_t_, multi_t_, capacity_ >::max_size ( void ) const

inline

Returns the capacity of the set.

operator=() [1/3]

template<typename key_t_, typename compare_t_ = hxkey_less_t<key_t_>, bool multi_t_ = true, hxsize_t capacity_ = hxallocator_dynamic_capacity>

void hxflat_set< key_t_, compare_t_, multi_t_, capacity_ >::operator= ( const hxflat_set< key_t_, compare_t_, multi_t_, capacity_ > & x_ )

noexcept

Assigns the contents of x to this set.

Clears this set then copies all elements from x. Requires x.size() ≤ capacity().

• x : The set to copy from.

operator=() [2/3]

template<typename key_t_, typename compare_t_ = hxkey_less_t<key_t_>, bool multi_t_ = true, hxsize_t capacity_ = hxallocator_dynamic_capacity>

template<hxsize_t capacity_x_>

void hxflat_set< key_t_, compare_t_, multi_t_, capacity_ >::operator= ( const hxflat_set< key_t_, compare_t_, multi_t_, capacity_x_ > & x_ )

noexcept

Cross-capacity copy assignment.

Assigns the contents of x to this set. Requires x.size() ≤ capacity().

• x : The set to copy from.

operator=() [3/3]

template<typename key_t_, typename compare_t_ = hxkey_less_t<key_t_>, bool multi_t_ = true, hxsize_t capacity_ = hxallocator_dynamic_capacity>

void hxflat_set< key_t_, compare_t_, multi_t_, capacity_ >::operator= ( hxflat_set< key_t_, compare_t_, multi_t_, capacity_ > && x_ )

noexcept

Move assigns from a temporary set using swap.

Requires hxallocator_dynamic_capacity.

• x : A temporary set to move from.

operator[]()

template<typename key_t_, typename compare_t_ = hxkey_less_t<key_t_>, bool multi_t_ = true, hxsize_t capacity_ = hxallocator_dynamic_capacity>

const key_t_ * hxflat_set< key_t_, compare_t_, multi_t_, capacity_ >::operator[]

(

hxsize_t

index_

)

const

Returns a const pointer to the element at index.

Requires index < size().

• index : The 0-based position of the element.

reserve()

template<typename key_t_, typename compare_t_ = hxkey_less_t<key_t_>, bool multi_t_ = true, hxsize_t capacity_ = hxallocator_dynamic_capacity>

void hxflat_set< key_t_, compare_t_, multi_t_, capacity_ >::reserve	(	hxsize_t	cap_,
		hxsystem_allocator_t	allocator_ = hxsystem_allocator_current,
		hxalignment_t	alignment_ = hxalignment )

Allocates storage for cap keys.

When capacity is fixed, cap must equal capacity. Reallocation is not allowed.

• cap : The number of elements to allocate storage for.
• allocator : The memory manager ID to use for allocation (default: hxsystem_allocator_current)
• alignment : The alignment for the allocation. (default: hxalignment)

size()

template<typename key_t_, typename compare_t_ = hxkey_less_t<key_t_>, bool multi_t_ = true, hxsize_t capacity_ = hxallocator_dynamic_capacity>

hxsize_t hxflat_set< key_t_, compare_t_, multi_t_, capacity_ >::size ( void ) const

inline

Returns the number of elements in the set.

swap()

template<typename key_t_, typename compare_t_ = hxkey_less_t<key_t_>, bool multi_t_ = true, hxsize_t capacity_ = hxallocator_dynamic_capacity>

void hxflat_set< key_t_, compare_t_, multi_t_, capacity_ >::swap ( hxflat_set< key_t_, compare_t_, multi_t_, capacity_ > & x_ )

noexcept

Swaps the contents with x.

Requires hxallocator_dynamic_capacity.

• x : The set to swap with.

upper_bound()

template<typename key_t_, typename compare_t_ = hxkey_less_t<key_t_>, bool multi_t_ = true, hxsize_t capacity_ = hxallocator_dynamic_capacity>

const key_t_ * hxflat_set< key_t_, compare_t_, multi_t_, capacity_ >::upper_bound

(

const key_t_ &

key_

)

const

Returns a const pointer to the first element whose key is ordered after key.

Returns end if no such element exists.

• key : The key to search for.

---

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

• include/hx/hxflat_set.hpp