hxflat_map< key_t_, mapped_t_, compare_t_, multi_t_, capacity_ > Class Template Reference

#include <hxflat_map.hpp>

Classes
class	const_iterator
class	iterator

Public Types
using	key_t = key_t_
using	mapped_t = mapped_t_
using	compare_t = compare_t_

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

Detailed Description

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

hxflat_map - A sorted associative container that stores keys and mapped values in two parallel arrays.

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

When multi_t is false duplicate keys are rejected and insert returns an iterator 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 arrays are statically sized to capacity elements and reserve may only be called with exactly that value.

E.g.:

// A static flat map of 64 integer keys to string pointers.
hxflat_map<int, const char*, hxkey_less_t<int>, false, 64> lookup;

• key_t : Key type.
• T : Mapped value 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 mapped_t_, typename compare_t_ = hxkey_less_t<key_t_>, bool multi_t_ = true, hxsize_t capacity_ = hxallocator_dynamic_capacity>

using hxflat_map< key_t_, mapped_t_, compare_t_, multi_t_, capacity_ >::compare_t = compare_t_

key_t

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

using hxflat_map< key_t_, mapped_t_, compare_t_, multi_t_, capacity_ >::key_t = key_t_

mapped_t

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

using hxflat_map< key_t_, mapped_t_, compare_t_, multi_t_, capacity_ >::mapped_t = mapped_t_

Constructor & Destructor Documentation

hxflat_map() [1/3]

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

hxflat_map< key_t_, mapped_t_, compare_t_, multi_t_, capacity_ >::hxflat_map ( void )

explicit

Constructs an empty map.

Requires reserve before inserting when capacity is hxallocator_dynamic_capacity.

hxflat_map() [2/3]

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

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

noexcept

Copy constructs from another hxflat_map.

Requires x.size() ≤ capacity().

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

hxflat_map() [3/3]

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

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

noexcept

Move constructs from a temporary hxflat_map.

Requires hxallocator_dynamic_capacity.

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

~hxflat_map()

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

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

noexcept

Destructs the map and destroys all key-value pairs.

Member Function Documentation

begin() [1/2]

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

iterator hxflat_map< key_t_, mapped_t_, compare_t_, multi_t_, capacity_ >::begin ( void )

inline

Returns an iterator pointing to the first element.

begin() [2/2]

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

const_iterator hxflat_map< key_t_, mapped_t_, compare_t_, multi_t_, capacity_ >::begin ( void ) const

inline

Returns a const iterator pointing to the first element.

capacity()

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

hxsize_t hxflat_map< key_t_, mapped_t_, compare_t_, multi_t_, capacity_ >::capacity ( void ) const

inline

Returns the number of elements the map can hold.

cbegin()

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

const_iterator hxflat_map< key_t_, mapped_t_, compare_t_, multi_t_, capacity_ >::cbegin ( void ) const

inline

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

cend()

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

const_iterator hxflat_map< key_t_, mapped_t_, compare_t_, multi_t_, capacity_ >::cend ( void ) const

inline

Returns a const iterator pointing past the last element.

clear()

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

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

noexcept

Removes all elements and destroys their key-value pairs.

count()

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

hxsize_t hxflat_map< key_t_, mapped_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 mapped_t_, typename compare_t_ = hxkey_less_t<key_t_>, bool multi_t_ = true, hxsize_t capacity_ = hxallocator_dynamic_capacity>

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

inline

Checks if the map contains no elements.

end() [1/2]

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

iterator hxflat_map< key_t_, mapped_t_, compare_t_, multi_t_, capacity_ >::end ( void )

inline

Returns an iterator pointing past the last element.

end() [2/2]

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

const_iterator hxflat_map< key_t_, mapped_t_, compare_t_, multi_t_, capacity_ >::end ( void ) const

inline

Returns a const iterator pointing past the last element.

equal()

template<typename key_t_, typename mapped_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_map< key_t_, mapped_t_, compare_t_, multi_t_, capacity_ >::equal

(

const hxflat_map< key_t_, mapped_t_, compare_t_, multi_t_, capacity_x_ > &

x_

)

const

Returns true if this map and x contain the same key-value pairs in the same order using hxkey_equal on both keys and values.

• x : The map to compare against.

erase() [1/2]

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

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

noexcept

Removes all elements with the given key and destroys their key-value pairs.

Returns the number of elements removed.

• key : The key to search for and remove.

erase() [2/2]

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

iterator hxflat_map< key_t_, mapped_t_, compare_t_, multi_t_, capacity_ >::erase ( iterator pos_ )

noexcept

Removes the element at the iterator position and destroys the key-value pair.

Returns an iterator to the element that followed the erased one.

• pos : An iterator to an element in this map.

find() [1/2]

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

mapped_t_ * hxflat_map< key_t_, mapped_t_, compare_t_, multi_t_, capacity_ >::find

(

const key_t_ &

key_

)

Non-const version of find.

• key : The key to search for.

find() [2/2]

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

const mapped_t_ * hxflat_map< key_t_, mapped_t_, compare_t_, multi_t_, capacity_ >::find

(

const key_t_ &

key_

)

const

Returns a const pointer to the mapped value for key, or hxnull if the key is not found.

When multi_t is true the first match is returned.

• key : The key to search for.

full()

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

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

inline

Returns true if the map has reached its capacity.

get() [1/2]

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

iterator hxflat_map< key_t_, mapped_t_, compare_t_, multi_t_, capacity_ >::get

(

hxsize_t

index_

)

Non-const version of get.

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

get() [2/2]

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

const_iterator hxflat_map< key_t_, mapped_t_, compare_t_, multi_t_, capacity_ >::get

(

hxsize_t

index_

)

const

Returns a const iterator to the element at index, or an end iterator if index is out of range.

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

insert() [1/2]

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

iterator hxflat_map< key_t_, mapped_t_, compare_t_, multi_t_, capacity_ >::insert ( const key_t_ & key_, const mapped_t_ & mapped_ )

noexcept

Inserts a key-value pair.

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

• key : The key of the new element.
• value : The mapped value of the new element.

insert() [2/2]

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

iterator hxflat_map< key_t_, mapped_t_, compare_t_, multi_t_, capacity_ >::insert ( const key_t_ & key_, mapped_t_ && mapped_ )

noexcept

Move-value overload of insert.

• key : The key of the new element.
• value : The mapped value forwarded into storage.

less()

template<typename key_t_, typename mapped_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_map< key_t_, mapped_t_, compare_t_, multi_t_, capacity_ >::less

(

const hxflat_map< key_t_, mapped_t_, compare_t_, multi_t_, capacity_x_ > &

x_

)

const

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

• x : The map to compare against.

lower_bound() [1/2]

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

iterator hxflat_map< key_t_, mapped_t_, compare_t_, multi_t_, capacity_ >::lower_bound

(

const key_t_ &

key_

)

Non-const version of lower_bound.

• key : The key to search for.

lower_bound() [2/2]

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

const_iterator hxflat_map< key_t_, mapped_t_, compare_t_, multi_t_, capacity_ >::lower_bound

(

const key_t_ &

key_

)

const

Returns an iterator 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 mapped_t_, typename compare_t_ = hxkey_less_t<key_t_>, bool multi_t_ = true, hxsize_t capacity_ = hxallocator_dynamic_capacity>

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

inline

Returns the capacity of the map.

operator=() [1/3]

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

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

noexcept

Assigns the contents of x to this map.

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

• x : The map to copy from.

operator=() [2/3]

template<typename key_t_, typename mapped_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_map< key_t_, mapped_t_, compare_t_, multi_t_, capacity_ >::operator= ( const hxflat_map< key_t_, mapped_t_, compare_t_, multi_t_, capacity_x_ > & x_ )

noexcept

Cross-capacity copy assignment.

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

• x : The map to copy from.

operator=() [3/3]

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

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

noexcept

Move assigns from a temporary map using swap.

Requires hxallocator_dynamic_capacity.

• x : A temporary map to move from.

operator[]() [1/2]

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

iterator hxflat_map< key_t_, mapped_t_, compare_t_, multi_t_, capacity_ >::operator[]

(

hxsize_t

index_

)

Returns an iterator to the element at index.

Requires index < size().

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

operator[]() [2/2]

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

const_iterator hxflat_map< key_t_, mapped_t_, compare_t_, multi_t_, capacity_ >::operator[]

(

hxsize_t

index_

)

const

Returns a const iterator to the element at index.

Requires index < size().

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

reserve()

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

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

noexcept

Allocates storage for cap keys and values.

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 mapped_t_, typename compare_t_ = hxkey_less_t<key_t_>, bool multi_t_ = true, hxsize_t capacity_ = hxallocator_dynamic_capacity>

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

inline

Returns the number of elements in the map.

swap()

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

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

noexcept

Swaps the contents with x.

Requires hxallocator_dynamic_capacity.

• x : The map to swap with.

upper_bound() [1/2]

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

iterator hxflat_map< key_t_, mapped_t_, compare_t_, multi_t_, capacity_ >::upper_bound

(

const key_t_ &

key_

)

Non-const version of upper_bound.

• key : The key to search for.

upper_bound() [2/2]

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

const_iterator hxflat_map< key_t_, mapped_t_, compare_t_, multi_t_, capacity_ >::upper_bound

(

const key_t_ &

key_

)

const

Returns an iterator 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_map.hpp