lal::detail::set_array< value_t, indexer_t > Class Template Reference

A set-like data structure implemented with an array. More...

#include <set_array.hpp>

Public Member Functions
template<typename vt = value_t, typename it = indexer_t, std::enable_if_t< std::is_same_v< vt, it >, bool > = true>
void	init (const std::size_t max_num_elems, const std::size_t max_index_value) noexcept
	Initialize the set with no indexer object.
template<typename vt = value_t, typename it = indexer_t, std::enable_if_t< not std::is_same_v< vt, it >, bool > = true>
void	init (const std::size_t max_num_elems, const std::size_t max_index_value, indexer_t &&i) noexcept
	Initialize the set with an indexer object.
const value_t &	operator[] (const std::size_t i) const noexcept
	Operator to access values in a given position.
std::size_t	capacity () const noexcept
	Maximum size of this set.
std::size_t	size () const noexcept
	Actual size of this set.
bool	exists (const value_t &v) const noexcept
	Does an element exist?
std::size_t	position (const value_t &v) const noexcept
	Where is an element located?
void	add (const value_t &v) noexcept
	Add a new element to the set.
void	add (value_t &&v) noexcept
	Add a new element to the set.
void	remove (const value_t &v) noexcept
	Remove an element from the set.
const value_t *	begin_values () const noexcept
	Begin iterator to m_values.
value_t *	begin_values () noexcept
	Begin iterator to m_values.
const value_t *	end_values () const noexcept
	End iterator to m_values.
value_t *	end_values () noexcept
	End iterator to m_values.
const value_t *	begin_position () const noexcept
	Begin iterator to m_position.
value_t *	begin_position () noexcept
	Begin iterator to m_position.
const value_t *	end_position () const noexcept
	End iterator to m_position.
value_t *	end_position () noexcept
	End iterator to m_position.

Private Member Functions
std::size_t	index (const value_t &v) const noexcept
	Calculate the index of an element using the indexer object m_I.

Private Attributes
indexer_t	m_I
	The indexer object.
array< value_t >	m_values
	The unique values in this set.
std::size_t	m_size
	The number of values in m_values.
array< char >	m_exists
	Does a value exist in the set?
array< std::size_t >	m_position
	The position of every value in the set.

Static Private Attributes
static constexpr char	EXISTS = 1
	Does an element exist in the set?
static constexpr char	NOT_EXISTS = 0
	Does an element not exist in the set?

Detailed Description

template<typename value_t, class indexer_t = value_t>
class lal::detail::set_array< value_t, indexer_t >

A set-like data structure implemented with an array.

It is actually a simplified unordered hash map implemented using 4 arrays. The goal is to implement a set-like data structure. Elements contained in the set are added to array m_values which is known to hold a maximum number of elements \(M\); its actual size is stored in m_size.

Every time an element \(E\) is added to the set, its position (in m_values) is recorded in m_position via a function that maps \(E\) to an integer value between \(0\) and \(M-1\). This function is implemented via a so-called indexer object, the only requirement of which is to have an operator (value_t) that returns said index. After the position is recorded, its existence in the set is also recorded, but in m_exists.

If two different elements \(E_1\) and \(E_2\) are mapped to the same index value via the indexer, then they will be treated as the same object.

If the contained elements are integer values (char, short, int, ...) there is no need to implement an indexer object and the type of the indexer value needs not be provided. If the elements are more complex, a requirement to use this object is to implement an indexer object.

When adding an element, the indexer object is called only once. When removing an element, the indexer object is called twice.

This set has to be initialized with a maximum size (which is the maximum number of elements this array would contain in the worst case) and a maximum index value (the highest index that an element could have in the worst case).

Now follows an example that shows how to use this set with integer types,

lal::detail::set_array<int> s(10, 10);
s.add(3);
s.add(4);
s.remove(3);

Now follows an example that shows how to use this set with pairs of integers,

struct indexer {
    std::size_t operator()(const lal::edge& p) const noexcept {
        return p.first + p.second*10;
    }
};
indexer I;
lal::detail::set_array<std::pair<int, int>> s(10, 100, std::move(I));
s.add({3,4});
s.add({4,4});
s.remove({3,4});

Template Parameters

value_t	The type of the contained elements
indexer_t	The type of the indexer object

Member Function Documentation

init() [1/2]

template<typename value_t , class indexer_t = value_t>

template<typename vt = value_t, typename it = indexer_t, std::enable_if_t< std::is_same_v< vt, it >, bool > = true>

void lal::detail::set_array< value_t, indexer_t >::init ( const std::size_t max_num_elems, const std::size_t max_index_value )

inlinenoexcept

Initialize the set with no indexer object.

Parameters

max_num_elems	Maximum number of elements in this set.
max_index_value	Maximum index value in the worst case.

init() [2/2]

template<typename value_t , class indexer_t = value_t>

template<typename vt = value_t, typename it = indexer_t, std::enable_if_t< not std::is_same_v< vt, it >, bool > = true>

void lal::detail::set_array< value_t, indexer_t >::init ( const std::size_t max_num_elems, const std::size_t max_index_value, indexer_t && i )

inlinenoexcept

Initialize the set with an indexer object.

Parameters

max_num_elems	Maximum number of elements in this set.
max_index_value	Maximum index value in the worst case.
i	Indexer object.

operator[]()

template<typename value_t , class indexer_t = value_t>

const value_t & lal::detail::set_array< value_t, indexer_t >::operator[] ( const std::size_t i ) const

inlinenodiscardnoexcept

Operator to access values in a given position.

Parameters

i	Index value.

Returns

The value at the i-th position of m_values.

Member Data Documentation

m_position

template<typename value_t , class indexer_t = value_t>

array<std::size_t> lal::detail::set_array< value_t, indexer_t >::m_position

private

The position of every value in the set.

This position is an index that points to a cell of m_values.

---

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

• lal/detail/set_array.hpp