Implemention of a linked hash-map. More...

#include <linked_map.hxx>

Public Types
typedef std::list< pair_t >::const_iterator	const_iterator

typedef std::pair< key_t, value_t >	init_pair_t

typedef std::list< pair_t >::iterator	iterator

typedef K	key_t

typedef std::list< pair_t >	list_t

typedef std::unordered_map< key_t const *, iterator, pointed_hash_t< key_t const, H >, pointed_equal_t< key_t const, E > >	map_t

typedef std::pair< key_t const, value_t >	pair_t

typedef linked_map_t< K, V, H, E >	self_type_t

typedef map_t::size_type	size_type

typedef V	value_t

typedef pair_t	value_type

Public Member Functions
	linked_map_t ()

	linked_map_t (linked_map_t< key_t, value_t > &&other)

	linked_map_t (linked_map_t< key_t, value_t > const &other)

template<class O >
	linked_map_t (O &&container, typename std::enable_if< is_iterable_with< O, init_pair_t >::value, bool >::type require_remap=true)
	Universal constructor to build a linked_map_t from any kind of iterable containing `std::pair<std::string,std::string>`'s. More...

	linked_map_t (std::initializer_list< pair_t > l)

	linked_map_t (std::list< pair_t > l)

value_t &	at (key_t const &key)
	Access value bound to `key`. More...

value_t const &	at (key_t const &key) const
	Access value bound to `key`. More...

pair_t &	back ()

pair_t const &	back () const

const_iterator	begin () const noexcept

iterator	begin () noexcept

size_type	bucket_count () const noexcept
	Accessor directly inherited from std::unordered_map. More...

size_type	bucket_size (unsigned n) const noexcept
	Accessor directly inherited from std::unordered_map. More...

const_iterator	cbegin () const noexcept

const_iterator	cend () const noexcept

void	clear () noexcept
	Clears this linked_map_t. More...

size_type	count (key_t const &key) const
	Returns the number of binding associated with `key`, that is 0 or 1. More...

bool	empty () const noexcept
	Returns if this linked_map_t is empty. More...

const_iterator	end () const noexcept

iterator	end () noexcept

template<typename KeyEquality = E, typename ValueEquality = std::equal_to<V>>
bool	equals_as_list (self_type_t const &other) const
	Returns `true` if this linked_map_t is equal to `other`, when both are considered as lists of pairs. More...

template<typename ValueEquality = std::equal_to<V>>
bool	equals_as_map (self_type_t const &other) const
	Returns `true` if the bindings in this linked_map_t are exactly those in `other`, when considered as mapsr. More...

iterator	erase (const_iterator pos)

size_type	erase (key_t const &key)
	Deletes the value bound to `key`. More...

iterator	find (key_t const &key)
	Returns the position corresponding to the binding of `key`. More...

const_iterator	find (key_t const &key) const
	Returns the position corresponding to the binding of `key`. More...

pair_t &	front ()

pair_t const &	front () const

iterator	insert (const_iterator pos, key_t key, value_t value, bool overwrite_existing=false)
	Inserts a new `key`/`value` binding before `pos`; deletes existing binding for `key` prior to insertion if `overwrite_existing` is `true`. More...

float	load_factor () const noexcept
	Accessor directly inherited from std::unordered_map. More...

size_type	max_bucket_count () const noexcept
	Accessor directly inherited from std::unordered_map. More...

float	max_load_factor () const noexcept
	Accessor directly inherited from std::unordered_map. More...

void	max_load_factor (float x)
	Accessor directly inherited from std::unordered_map. More...

size_type	max_size () const noexcept

bool	operator!= (self_type_t const &other)
	Returns `true` if this linked_map_t is different from `other`. More...

bool	operator== (self_type_t const &other)
	Returns `true` if this linked_map_t is equal to `other`, when both are considered as lists of pairs. More...

value_t &	operator[] (key_t key)
	Access, modify or set the value bound to `key`. More...

void	push_back (key_t key, value_t value, bool overwrite_existing=false)
	Inserts a new `key`/`value` binding at the back of this linked_map_t; deletes existing binding for `key` prior to insertion if `overwrite_existing` is `true`. More...

void	push_front (key_t key, value_t value, bool overwrite_existing=false)
	Inserts a new `key`/`value` binding at the front of this linked_map_t; deletes existing binding for `key` prior to insertion if `overwrite_existing` is `true`. More...

void	rehash (size_type n)
	Accessor directly inherited from std::unordered_map. More...

void	reserve (size_type n)
	Accessor directly inherited from std::unordered_map. More...

size_type	size () const noexcept
	Returns the number of bindings in this linked_map_t. More...

void	sort ()
	Sort this linked_map_t by key assuming `operator<` exists on key_t. More...

template<class Compare >
void	sort (Compare comp)
	Sort this linked_map_t by given comparison. More...

Protected Member Functions
void	remap (bool hard)
	Recompute map from list. More...

Protected Attributes
list_t	list

map_t	map

Detailed Description

template<typename K, typename V, typename H = std::hash<K>, typename E = std::equal_to<K>>
class awali::linked_map_t< K, V, H, E >

Implemention of a linked hash-map.

The main structure is in field list, a std::list of std::pair<K const, V> (const is there to avoid user to break the structure invariant). The iterators of a {@link linked_map_t} (iteratorandconst_iterator`) are directly those of list. The secondary structure is map, an std::unordered_map that maps keys of type K* to iterators of the list above. The map uses the classes pointed_hash_t and pointed_equal_t to hash its keys: they wrap the possibility user-defined H and E in order to compute equality and hash based on the pointed value (of type K) instead of the pointer value (of type K*).

Member Typedef Documentation

◆ const_iterator

template<typename K , typename V , typename H = std::hash<K>, typename E = std::equal_to<K>>

typedef std::list<pair_t>::const_iterator awali::linked_map_t< K, V, H, E >::const_iterator

◆ init_pair_t

template<typename K , typename V , typename H = std::hash<K>, typename E = std::equal_to<K>>

typedef std::pair<key_t,value_t> awali::linked_map_t< K, V, H, E >::init_pair_t

◆ iterator

template<typename K , typename V , typename H = std::hash<K>, typename E = std::equal_to<K>>

typedef std::list<pair_t>::iterator awali::linked_map_t< K, V, H, E >::iterator

◆ key_t

template<typename K , typename V , typename H = std::hash<K>, typename E = std::equal_to<K>>

typedef K awali::linked_map_t< K, V, H, E >::key_t

◆ list_t

template<typename K , typename V , typename H = std::hash<K>, typename E = std::equal_to<K>>

typedef std::list<pair_t> awali::linked_map_t< K, V, H, E >::list_t

◆ map_t

template<typename K , typename V , typename H = std::hash<K>, typename E = std::equal_to<K>>

typedef std::unordered_map< key_t const*, iterator, pointed_hash_t<key_t const,H>, pointed_equal_t<key_t const,E> > awali::linked_map_t< K, V, H, E >::map_t

◆ pair_t

template<typename K , typename V , typename H = std::hash<K>, typename E = std::equal_to<K>>

typedef std::pair<key_t const,value_t> awali::linked_map_t< K, V, H, E >::pair_t

◆ self_type_t

template<typename K , typename V , typename H = std::hash<K>, typename E = std::equal_to<K>>

typedef linked_map_t<K,V,H,E> awali::linked_map_t< K, V, H, E >::self_type_t

◆ size_type

template<typename K , typename V , typename H = std::hash<K>, typename E = std::equal_to<K>>

typedef map_t::size_type awali::linked_map_t< K, V, H, E >::size_type

◆ value_t

template<typename K , typename V , typename H = std::hash<K>, typename E = std::equal_to<K>>

typedef V awali::linked_map_t< K, V, H, E >::value_t

◆ value_type

template<typename K , typename V , typename H = std::hash<K>, typename E = std::equal_to<K>>

typedef pair_t awali::linked_map_t< K, V, H, E >::value_type

Constructor & Destructor Documentation

◆ linked_map_t() [1/6]

template<typename K , typename V , typename H = std::hash<K>, typename E = std::equal_to<K>>

awali::linked_map_t< K, V, H, E >::linked_map_t ( )

◆ linked_map_t() [2/6]

template<typename K , typename V , typename H = std::hash<K>, typename E = std::equal_to<K>>

awali::linked_map_t< K, V, H, E >::linked_map_t ( std::initializer_list< pair_t > l )

◆ linked_map_t() [3/6]

template<typename K , typename V , typename H = std::hash<K>, typename E = std::equal_to<K>>

awali::linked_map_t< K, V, H, E >::linked_map_t ( std::list< pair_t > l )

◆ linked_map_t() [4/6]

template<typename K , typename V , typename H = std::hash<K>, typename E = std::equal_to<K>>

awali::linked_map_t< K, V, H, E >::linked_map_t ( linked_map_t< key_t, value_t > const & other )

◆ linked_map_t() [5/6]

template<typename K , typename V , typename H = std::hash<K>, typename E = std::equal_to<K>>

awali::linked_map_t< K, V, H, E >::linked_map_t ( linked_map_t< key_t, value_t > && other )

◆ linked_map_t() [6/6]

template<typename K , typename V , typename H = std::hash<K>, typename E = std::equal_to<K>>

template<class O >

awali::linked_map_t< K, V, H, E >::linked_map_t	(	O &&	container,
		typename std::enable_if< is_iterable_with< O, init_pair_t >::value, bool >::type	require_remap = `true`
	)

Universal constructor to build a linked_map_t from any kind of iterable containing std::pair<std::string,std::string>'s.

If provided with an rvalue reference, it moves the elements out of it (so the container does not change size, but its elements are emptied). If provided with an lvalue reference, it copies each pair from it.

Parameters

container	Container to copy or move the binding pairs from
require_remap	If set to `false`, the first elements in the pairs in `container` are assumed to be unique; if it is not the case, the produced linked_map_t is inconsistent. If set to `true`, only the last binding for a given key is kept. extra checks.

Member Function Documentation

◆ at() [1/2]

template<typename K , typename V , typename H = std::hash<K>, typename E = std::equal_to<K>>

value_t& awali::linked_map_t< K, V, H, E >::at ( key_t const & key )

Access value bound to key.

Exceptions

std::out_of_range if key is unbound.

◆ at() [2/2]

template<typename K , typename V , typename H = std::hash<K>, typename E = std::equal_to<K>>

value_t const& awali::linked_map_t< K, V, H, E >::at ( key_t const & key ) const

Access value bound to key.

Exceptions

std::out_of_range if key is unbound.

◆ back() [1/2]

template<typename K , typename V , typename H = std::hash<K>, typename E = std::equal_to<K>>

pair_t& awali::linked_map_t< K, V, H, E >::back ( )

◆ back() [2/2]

template<typename K , typename V , typename H = std::hash<K>, typename E = std::equal_to<K>>

pair_t const& awali::linked_map_t< K, V, H, E >::back ( ) const

◆ begin() [1/2]

template<typename K , typename V , typename H = std::hash<K>, typename E = std::equal_to<K>>

const_iterator awali::linked_map_t< K, V, H, E >::begin ( ) const

noexcept

◆ begin() [2/2]

template<typename K , typename V , typename H = std::hash<K>, typename E = std::equal_to<K>>

iterator awali::linked_map_t< K, V, H, E >::begin ( )

noexcept

◆ bucket_count()

template<typename K , typename V , typename H = std::hash<K>, typename E = std::equal_to<K>>

size_type awali::linked_map_t< K, V, H, E >::bucket_count ( ) const

noexcept

Accessor directly inherited from std::unordered_map.

◆ bucket_size()

template<typename K , typename V , typename H = std::hash<K>, typename E = std::equal_to<K>>

size_type awali::linked_map_t< K, V, H, E >::bucket_size ( unsigned n ) const

noexcept

Accessor directly inherited from std::unordered_map.

◆ cbegin()

template<typename K , typename V , typename H = std::hash<K>, typename E = std::equal_to<K>>

const_iterator awali::linked_map_t< K, V, H, E >::cbegin ( ) const

noexcept

◆ cend()

template<typename K , typename V , typename H = std::hash<K>, typename E = std::equal_to<K>>

const_iterator awali::linked_map_t< K, V, H, E >::cend ( ) const

noexcept

◆ clear()

template<typename K , typename V , typename H = std::hash<K>, typename E = std::equal_to<K>>

void awali::linked_map_t< K, V, H, E >::clear ( )

noexcept

Clears this linked_map_t.

◆ count()

template<typename K , typename V , typename H = std::hash<K>, typename E = std::equal_to<K>>

size_type awali::linked_map_t< K, V, H, E >::count ( key_t const & key ) const

Returns the number of binding associated with key, that is 0 or 1.

◆ empty()

template<typename K , typename V , typename H = std::hash<K>, typename E = std::equal_to<K>>

bool awali::linked_map_t< K, V, H, E >::empty ( ) const

noexcept

Returns if this linked_map_t is empty.

◆ end() [1/2]

template<typename K , typename V , typename H = std::hash<K>, typename E = std::equal_to<K>>

const_iterator awali::linked_map_t< K, V, H, E >::end ( ) const

noexcept

◆ end() [2/2]

template<typename K , typename V , typename H = std::hash<K>, typename E = std::equal_to<K>>

iterator awali::linked_map_t< K, V, H, E >::end ( )

noexcept

◆ equals_as_list()

template<typename K , typename V , typename H = std::hash<K>, typename E = std::equal_to<K>>

template<typename KeyEquality = E, typename ValueEquality = std::equal_to<V>>

bool awali::linked_map_t< K, V, H, E >::equals_as_list ( self_type_t const & other ) const

Returns true if this linked_map_t is equal to other, when both are considered as lists of pairs.

Order of bindings is taken into account.
Equality for keys is tested with template parameter KeyEquality.
Equality for values is tested with ValueEquality.

◆ equals_as_map()

template<typename K , typename V , typename H = std::hash<K>, typename E = std::equal_to<K>>

template<typename ValueEquality = std::equal_to<V>>

bool awali::linked_map_t< K, V, H, E >::equals_as_map ( self_type_t const & other ) const

Returns true if the bindings in this linked_map_t are exactly those in other, when considered as mapsr.

Order of bindings is ignored.
Equality for keys is tested with class template parameter E: each key bound in other is looked up in this.
Equality for values is tested by an object of type ValueEquality, built using the default constructor.

◆ erase() [1/2]

template<typename K , typename V , typename H = std::hash<K>, typename E = std::equal_to<K>>

iterator awali::linked_map_t< K, V, H, E >::erase ( const_iterator pos )

◆ erase() [2/2]

template<typename K , typename V , typename H = std::hash<K>, typename E = std::equal_to<K>>

size_type awali::linked_map_t< K, V, H, E >::erase ( key_t const & key )

Deletes the value bound to key.

Returns: the number of binding deleted (1 if key was bound, 0 if it was not).

◆ find() [1/2]

template<typename K , typename V , typename H = std::hash<K>, typename E = std::equal_to<K>>

iterator awali::linked_map_t< K, V, H, E >::find ( key_t const & key )

Returns the position corresponding to the binding of key.

Returns end() if key is unbound.

◆ find() [2/2]

template<typename K , typename V , typename H = std::hash<K>, typename E = std::equal_to<K>>

const_iterator awali::linked_map_t< K, V, H, E >::find ( key_t const & key ) const

Returns the position corresponding to the binding of key.

Returns end() if key is unbound.

◆ front() [1/2]

template<typename K , typename V , typename H = std::hash<K>, typename E = std::equal_to<K>>

pair_t& awali::linked_map_t< K, V, H, E >::front ( )

◆ front() [2/2]

template<typename K , typename V , typename H = std::hash<K>, typename E = std::equal_to<K>>

pair_t const& awali::linked_map_t< K, V, H, E >::front ( ) const

◆ insert()

template<typename K , typename V , typename H = std::hash<K>, typename E = std::equal_to<K>>

iterator awali::linked_map_t< K, V, H, E >::insert	(	const_iterator	pos,
		key_t	key,
		value_t	value,
		bool	overwrite_existing = `false`
	)

Inserts a new key/value binding before pos; deletes existing binding for key prior to insertion if overwrite_existing is true.

If key was unbound, insert binding before pos. If key was bound and overwrite_existing is true, delete old binding and inserts the new binding before pos. If key was bound and overwrite_existing is false, do nothing.

◆ load_factor()

template<typename K , typename V , typename H = std::hash<K>, typename E = std::equal_to<K>>

float awali::linked_map_t< K, V, H, E >::load_factor ( ) const

noexcept

Accessor directly inherited from std::unordered_map.

◆ max_bucket_count()

template<typename K , typename V , typename H = std::hash<K>, typename E = std::equal_to<K>>

size_type awali::linked_map_t< K, V, H, E >::max_bucket_count ( ) const

noexcept

Accessor directly inherited from std::unordered_map.

◆ max_load_factor() [1/2]

template<typename K , typename V , typename H = std::hash<K>, typename E = std::equal_to<K>>

float awali::linked_map_t< K, V, H, E >::max_load_factor ( ) const

noexcept

Accessor directly inherited from std::unordered_map.

◆ max_load_factor() [2/2]

template<typename K , typename V , typename H = std::hash<K>, typename E = std::equal_to<K>>

void awali::linked_map_t< K, V, H, E >::max_load_factor ( float x )

Accessor directly inherited from std::unordered_map.

◆ max_size()

template<typename K , typename V , typename H = std::hash<K>, typename E = std::equal_to<K>>

size_type awali::linked_map_t< K, V, H, E >::max_size ( ) const

noexcept

◆ operator!=()

template<typename K , typename V , typename H = std::hash<K>, typename E = std::equal_to<K>>

bool awali::linked_map_t< K, V, H, E >::operator!= ( self_type_t const & other )

Returns true if this linked_map_t is different from other.

Alias for !( (*this) == other).

◆ operator==()

template<typename K , typename V , typename H = std::hash<K>, typename E = std::equal_to<K>>

bool awali::linked_map_t< K, V, H, E >::operator== ( self_type_t const & other )

Returns true if this linked_map_t is equal to other, when both are considered as lists of pairs.

Order of bindings is taken into account.
Equality for keys is tested with class template parameter E.
Equality for values is tested with operator==.

Same as equals_as_list with default values for template parameters.

◆ operator[]()

template<typename K , typename V , typename H = std::hash<K>, typename E = std::equal_to<K>>

value_t& awali::linked_map_t< K, V, H, E >::operator[] ( key_t key )

Access, modify or set the value bound to key.

If key is unbound before the call, a new binding is inserted at the end of this linked_map. It associates key to the value resulting from the default value_t constructor, and returns a reference to it. Typical usage is map[key] = value where key is of type key_t and value of type value_t.

◆ push_back()

template<typename K , typename V , typename H = std::hash<K>, typename E = std::equal_to<K>>

void awali::linked_map_t< K, V, H, E >::push_back	(	key_t	key,
		value_t	value,
		bool	overwrite_existing = `false`
	)

Inserts a new key/value binding at the back of this linked_map_t; deletes existing binding for key prior to insertion if overwrite_existing is true.

Alias for insert(end(),key,value,overwrite_existing)

◆ push_front()

template<typename K , typename V , typename H = std::hash<K>, typename E = std::equal_to<K>>

void awali::linked_map_t< K, V, H, E >::push_front	(	key_t	key,
		value_t	value,
		bool	overwrite_existing = `false`
	)

Inserts a new key/value binding at the front of this linked_map_t; deletes existing binding for key prior to insertion if overwrite_existing is true.

Alias for insert(begin(),key,value,overwrite_existing)

◆ rehash()

template<typename K , typename V , typename H = std::hash<K>, typename E = std::equal_to<K>>

void awali::linked_map_t< K, V, H, E >::rehash ( size_type n )

Accessor directly inherited from std::unordered_map.

◆ remap()

template<typename K , typename V , typename H = std::hash<K>, typename E = std::equal_to<K>>

void awali::linked_map_t< K, V, H, E >::remap ( bool hard )

protected

Recompute map from list.

hard tells whether the list may contain key duplicates:

if hard is true: duplicates key are removed from list might have duplicates and only the last binding is kept.
if hard is false: list is not verified for key duplicates; if it has duplicated, this linked_map_t is in an inconsistent state.

◆ reserve()

template<typename K , typename V , typename H = std::hash<K>, typename E = std::equal_to<K>>

void awali::linked_map_t< K, V, H, E >::reserve ( size_type n )

Accessor directly inherited from std::unordered_map.

◆ size()

template<typename K , typename V , typename H = std::hash<K>, typename E = std::equal_to<K>>

size_type awali::linked_map_t< K, V, H, E >::size ( ) const

noexcept

Returns the number of bindings in this linked_map_t.

◆ sort() [1/2]

template<typename K , typename V , typename H = std::hash<K>, typename E = std::equal_to<K>>

void awali::linked_map_t< K, V, H, E >::sort ( )

Sort this linked_map_t by key assuming operator< exists on key_t.

◆ sort() [2/2]

template<typename K , typename V , typename H = std::hash<K>, typename E = std::equal_to<K>>

template<class Compare >

void awali::linked_map_t< K, V, H, E >::sort ( Compare comp )

Sort this linked_map_t by given comparison.

Field Documentation

◆ list

template<typename K , typename V , typename H = std::hash<K>, typename E = std::equal_to<K>>

list_t awali::linked_map_t< K, V, H, E >::list

protected

◆ map

template<typename K , typename V , typename H = std::hash<K>, typename E = std::equal_to<K>>

map_t awali::linked_map_t< K, V, H, E >::map

protected

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

/home/marsault/git-client/telecom/awali.git/awali/common/linked_map.hxx

Public Types

Public Member Functions

Protected Member Functions

Protected Attributes

Detailed Description

template<typename K, typename V, typename H = std::hash<K>, typename E = std::equal_to<K>> class awali::linked_map_t< K, V, H, E >

Member Typedef Documentation

◆ const_iterator

◆ init_pair_t

◆ iterator

◆ key_t

◆ list_t

◆ map_t

◆ pair_t

◆ self_type_t

◆ size_type

◆ value_t

◆ value_type

Constructor & Destructor Documentation

◆ linked_map_t() [1/6]

◆ linked_map_t() [2/6]

◆ linked_map_t() [3/6]

◆ linked_map_t() [4/6]

◆ linked_map_t() [5/6]

◆ linked_map_t() [6/6]

Member Function Documentation

◆ at() [1/2]

◆ at() [2/2]

◆ back() [1/2]

◆ back() [2/2]

◆ begin() [1/2]

◆ begin() [2/2]

◆ bucket_count()

◆ bucket_size()

◆ cbegin()

◆ cend()

◆ clear()

◆ count()

◆ empty()

◆ end() [1/2]

◆ end() [2/2]

◆ equals_as_list()

◆ equals_as_map()

◆ erase() [1/2]

◆ erase() [2/2]

◆ find() [1/2]

◆ find() [2/2]

◆ front() [1/2]

◆ front() [2/2]

◆ insert()

◆ load_factor()

◆ max_bucket_count()

◆ max_load_factor() [1/2]

◆ max_load_factor() [2/2]

◆ max_size()

◆ operator!=()

◆ operator==()

◆ operator[]()

◆ push_back()

◆ push_front()

◆ rehash()

◆ remap()

◆ reserve()

◆ size()

◆ sort() [1/2]

◆ sort() [2/2]

Field Documentation

◆ list

◆ map

template<typename K, typename V, typename H = std::hash<K>, typename E = std::equal_to<K>>
class awali::linked_map_t< K, V, H, E >