#include <map.hpp>

Collaboration diagram for immer::map< K, T, Hash, Equal, MemoryPolicy, B >:

Classes
struct	combine_value

struct	default_value

struct	equal_key

struct	equal_value

struct	error_value

struct	hash_key

struct	project_value

struct	project_value_ptr

Public Types
using	key_type = K

using	mapped_type = T

using	value_type = std::pair< K, T >

using	size_type = detail::hamts::size_t

using	diference_type = std::ptrdiff_t

using	hasher = Hash

using	key_equal = Equal

using	reference = const value_type &

using	const_reference = const value_type &

using	iterator = detail::hamts::champ_iterator< value_t, hash_key, equal_key, MemoryPolicy, B >

using	const_iterator = iterator

using	transient_type = map_transient< K, T, Hash, Equal, MemoryPolicy, B >

Public Member Functions
	map ()=default

iterator	begin () const

iterator	end () const

size_type	size () const

size_type	count (const K &k) const

const T &	operator[] (const K &k) const

const T &	at (const K &k) const

const T *	find (const K &k) const

bool	operator== (const map &other) const

bool	operator!= (const map &other) const

map	insert (value_type value) const

map	set (key_type k, mapped_type v) const

template<typename Fn >
map	update (key_type k, Fn &&fn) const

map	erase (const K &k) const

transient_type	transient () const &

transient_type	transient () &&

const impl_t &	impl () const

Private Types
using	value_t = std::pair< K, T >

using	impl_t = detail::hamts::champ< value_t, hash_key, equal_key, MemoryPolicy, B >

Private Member Functions
	map (impl_t impl)

Private Attributes
friend	transient_type

impl_t	impl_ = impl_t::empty()

Detailed Description

template<typename K, typename T, typename Hash = std::hash<K>, typename Equal = std::equal_to<K>, typename MemoryPolicy = default_memory_policy, detail::hamts::bits_t B = default_bits>
class immer::map< K, T, Hash, Equal, MemoryPolicy, B >

Immutable unordered mapping of values from type K to type T.

Template Parameters

K	The type of the keys.
T	The type of the values to be stored in the container.
Hash	The type of a function object capable of hashing values of type `T`.
Equal	The type of a function object capable of comparing values of type `T`.
MemoryPolicy	Memory management policy. See memory_policy.

This cotainer provides a good trade-off between cache locality, search, update performance and structural sharing. It does so by storing the data in contiguous chunks of :math:2^{B} elements. When storing big objects, the size of these contiguous chunks can become too big, damaging performance. If this is measured to be problematic for a specific use-case, it can be solved by using a immer::box to wrap the type T.

Example .. literalinclude:: ../example/map/intro.cpp :language: c++ :start-after: intro/start :end-before: intro/end

Definition at line 64 of file map.hpp.

Member Typedef Documentation

◆ const_iterator

template<typename K, typename T, typename Hash = std::hash<K>, typename Equal = std::equal_to<K>, typename MemoryPolicy = default_memory_policy, detail::hamts::bits_t B = default_bits>

using immer::map< K, T, Hash, Equal, MemoryPolicy, B >::const_iterator = iterator

Definition at line 150 of file map.hpp.

◆ const_reference

template<typename K, typename T, typename Hash = std::hash<K>, typename Equal = std::equal_to<K>, typename MemoryPolicy = default_memory_policy, detail::hamts::bits_t B = default_bits>

using immer::map< K, T, Hash, Equal, MemoryPolicy, B >::const_reference = const value_type&

Definition at line 146 of file map.hpp.

◆ diference_type

template<typename K, typename T, typename Hash = std::hash<K>, typename Equal = std::equal_to<K>, typename MemoryPolicy = default_memory_policy, detail::hamts::bits_t B = default_bits>

using immer::map< K, T, Hash, Equal, MemoryPolicy, B >::diference_type = std::ptrdiff_t

Definition at line 142 of file map.hpp.

◆ hasher

template<typename K, typename T, typename Hash = std::hash<K>, typename Equal = std::equal_to<K>, typename MemoryPolicy = default_memory_policy, detail::hamts::bits_t B = default_bits>

using immer::map< K, T, Hash, Equal, MemoryPolicy, B >::hasher = Hash

Definition at line 143 of file map.hpp.

◆ impl_t

template<typename K, typename T, typename Hash = std::hash<K>, typename Equal = std::equal_to<K>, typename MemoryPolicy = default_memory_policy, detail::hamts::bits_t B = default_bits>

using immer::map< K, T, Hash, Equal, MemoryPolicy, B >::impl_t = detail::hamts::champ< value_t, hash_key, equal_key, MemoryPolicy, B>

private

Definition at line 135 of file map.hpp.

◆ iterator

template<typename K, typename T, typename Hash = std::hash<K>, typename Equal = std::equal_to<K>, typename MemoryPolicy = default_memory_policy, detail::hamts::bits_t B = default_bits>

using immer::map< K, T, Hash, Equal, MemoryPolicy, B >::iterator = detail::hamts::champ_iterator< value_t, hash_key, equal_key, MemoryPolicy, B>

Definition at line 149 of file map.hpp.

◆ key_equal

template<typename K, typename T, typename Hash = std::hash<K>, typename Equal = std::equal_to<K>, typename MemoryPolicy = default_memory_policy, detail::hamts::bits_t B = default_bits>

using immer::map< K, T, Hash, Equal, MemoryPolicy, B >::key_equal = Equal

Definition at line 144 of file map.hpp.

◆ key_type

template<typename K, typename T, typename Hash = std::hash<K>, typename Equal = std::equal_to<K>, typename MemoryPolicy = default_memory_policy, detail::hamts::bits_t B = default_bits>

using immer::map< K, T, Hash, Equal, MemoryPolicy, B >::key_type = K

Definition at line 138 of file map.hpp.

◆ mapped_type

template<typename K, typename T, typename Hash = std::hash<K>, typename Equal = std::equal_to<K>, typename MemoryPolicy = default_memory_policy, detail::hamts::bits_t B = default_bits>

using immer::map< K, T, Hash, Equal, MemoryPolicy, B >::mapped_type = T

Definition at line 139 of file map.hpp.

◆ reference

template<typename K, typename T, typename Hash = std::hash<K>, typename Equal = std::equal_to<K>, typename MemoryPolicy = default_memory_policy, detail::hamts::bits_t B = default_bits>

using immer::map< K, T, Hash, Equal, MemoryPolicy, B >::reference = const value_type&

Definition at line 145 of file map.hpp.

◆ size_type

template<typename K, typename T, typename Hash = std::hash<K>, typename Equal = std::equal_to<K>, typename MemoryPolicy = default_memory_policy, detail::hamts::bits_t B = default_bits>

using immer::map< K, T, Hash, Equal, MemoryPolicy, B >::size_type = detail::hamts::size_t

Definition at line 141 of file map.hpp.

◆ transient_type

template<typename K, typename T, typename Hash = std::hash<K>, typename Equal = std::equal_to<K>, typename MemoryPolicy = default_memory_policy, detail::hamts::bits_t B = default_bits>

using immer::map< K, T, Hash, Equal, MemoryPolicy, B >::transient_type = map_transient<K, T, Hash, Equal, MemoryPolicy, B>

Definition at line 152 of file map.hpp.

◆ value_t

template<typename K, typename T, typename Hash = std::hash<K>, typename Equal = std::equal_to<K>, typename MemoryPolicy = default_memory_policy, detail::hamts::bits_t B = default_bits>

using immer::map< K, T, Hash, Equal, MemoryPolicy, B >::value_t = std::pair<K, T>

private

Definition at line 66 of file map.hpp.

◆ value_type

template<typename K, typename T, typename Hash = std::hash<K>, typename Equal = std::equal_to<K>, typename MemoryPolicy = default_memory_policy, detail::hamts::bits_t B = default_bits>

using immer::map< K, T, Hash, Equal, MemoryPolicy, B >::value_type = std::pair<K, T>

Definition at line 140 of file map.hpp.

Constructor & Destructor Documentation

◆ map() [1/2]

template<typename K, typename T, typename Hash = std::hash<K>, typename Equal = std::equal_to<K>, typename MemoryPolicy = default_memory_policy, detail::hamts::bits_t B = default_bits>

immer::map< K, T, Hash, Equal, MemoryPolicy, B >::map ( )

default

Default constructor. It creates a set of size() == 0. It does not allocate memory and its complexity is $ O(1) $ .

◆ map() [2/2]

template<typename K, typename T, typename Hash = std::hash<K>, typename Equal = std::equal_to<K>, typename MemoryPolicy = default_memory_policy, detail::hamts::bits_t B = default_bits>

immer::map< K, T, Hash, Equal, MemoryPolicy, B >::map ( impl_t impl )

inlineprivate

Definition at line 304 of file map.hpp.

Member Function Documentation

◆ at()

template<typename K, typename T, typename Hash = std::hash<K>, typename Equal = std::equal_to<K>, typename MemoryPolicy = default_memory_policy, detail::hamts::bits_t B = default_bits>

const T& immer::map< K, T, Hash, Equal, MemoryPolicy, B >::at ( const K & k ) const

inline

Returns a const reference to the values associated to the key k. If the key is not contained in the map, throws an std::out_of_range error. It does not allocate memory and its complexity is effectively $ O(1) $ .

Definition at line 203 of file map.hpp.

◆ begin()

template<typename K, typename T, typename Hash = std::hash<K>, typename Equal = std::equal_to<K>, typename MemoryPolicy = default_memory_policy, detail::hamts::bits_t B = default_bits>

iterator immer::map< K, T, Hash, Equal, MemoryPolicy, B >::begin ( ) const

inline

Returns an iterator pointing at the first element of the collection. It does not allocate memory and its complexity is $ O(1) $ .

Definition at line 165 of file map.hpp.

Referenced by SerializeImmerMap().

◆ count()

template<typename K, typename T, typename Hash = std::hash<K>, typename Equal = std::equal_to<K>, typename MemoryPolicy = default_memory_policy, detail::hamts::bits_t B = default_bits>

size_type immer::map< K, T, Hash, Equal, MemoryPolicy, B >::count ( const K & k ) const

inline

Returns 1 when the key k is contained in the map or 0 otherwise. It won't allocate memory and its complexity is effectively $ O(1) $ .

Definition at line 184 of file map.hpp.

Referenced by CDeterministicMNList::HasUniqueProperty().

◆ end()

template<typename K, typename T, typename Hash = std::hash<K>, typename Equal = std::equal_to<K>, typename MemoryPolicy = default_memory_policy, detail::hamts::bits_t B = default_bits>

iterator immer::map< K, T, Hash, Equal, MemoryPolicy, B >::end ( ) const

inline

Returns an iterator pointing just after the last element of the collection. It does not allocate and its complexity is $ O(1) $ .

Definition at line 171 of file map.hpp.

Referenced by SerializeImmerMap().

◆ erase()

template<typename K, typename T, typename Hash = std::hash<K>, typename Equal = std::equal_to<K>, typename MemoryPolicy = default_memory_policy, detail::hamts::bits_t B = default_bits>

map immer::map< K, T, Hash, Equal, MemoryPolicy, B >::erase ( const K & k ) const

inline

Returns a map without the key k. If the key is not associated in the map it returns the same map. It may allocate memory and its complexity is effectively $ O(1) $ .

Definition at line 286 of file map.hpp.

Referenced by CDeterministicMNList::DeleteUniqueProperty(), and CDeterministicMNList::RemoveMN().

◆ find()

template<typename K, typename T, typename Hash = std::hash<K>, typename Equal = std::equal_to<K>, typename MemoryPolicy = default_memory_policy, detail::hamts::bits_t B = default_bits>

const T* immer::map< K, T, Hash, Equal, MemoryPolicy, B >::find ( const K & k ) const

inline

Returns a pointer to the value associated with the key k. If the key is not contained in the map, a nullptr is returned. It does not allocate memory and its complexity is effectively $ O(1) $ .

.. admonition:: Why doesn't this function return an iterator?

Associative containers from the C++ standard library provide a find method that returns an iterator pointing to the element in the container or end() when the key is missing. In the case of an unordered container, the only meaningful thing one may do with it is to compare it with the end, to test if the find was succesfull, and dereference it. This comparison is cumbersome compared to testing for a non-empty optional value. Furthermore, for an immutable container, returning an iterator would have some additional performance cost, with no benefits otherwise.

In our opinion, this function should return a std::optional<const T&> but this construction is not valid in any current standard. As a compromise we return a pointer, which has similar syntactic properties yet it is unfortunatelly unnecessarily unrestricted.

Definition at line 236 of file map.hpp.

Referenced by CDeterministicMNList::AddMN(), CDeterministicMNList::AddUniqueProperty(), CDeterministicMNList::DeleteUniqueProperty(), CDeterministicMNList::GetMN(), CDeterministicMNList::GetMNByInternalId(), CDeterministicMNList::GetUniquePropertyMN(), CDeterministicMNList::IsMNPoSeBanned(), CDeterministicMNList::IsMNValid(), and CDeterministicMNList::UpdateMN().

◆ impl()

template<typename K, typename T, typename Hash = std::hash<K>, typename Equal = std::equal_to<K>, typename MemoryPolicy = default_memory_policy, detail::hamts::bits_t B = default_bits>

const impl_t& immer::map< K, T, Hash, Equal, MemoryPolicy, B >::impl ( ) const

inline

Definition at line 299 of file map.hpp.

◆ insert()

template<typename K, typename T, typename Hash = std::hash<K>, typename Equal = std::equal_to<K>, typename MemoryPolicy = default_memory_policy, detail::hamts::bits_t B = default_bits>

map immer::map< K, T, Hash, Equal, MemoryPolicy, B >::insert ( value_type value ) const

inline

Returns a map containing the association value. If the key is already in the map, it replaces its association in the map. It may allocate memory and its complexity is effectively $ O(1) $ .

Definition at line 254 of file map.hpp.

◆ operator!=()

template<typename K, typename T, typename Hash = std::hash<K>, typename Equal = std::equal_to<K>, typename MemoryPolicy = default_memory_policy, detail::hamts::bits_t B = default_bits>

bool immer::map< K, T, Hash, Equal, MemoryPolicy, B >::operator!= ( const map< K, T, Hash, Equal, MemoryPolicy, B > & other ) const

inline

Definition at line 245 of file map.hpp.

◆ operator==()

template<typename K, typename T, typename Hash = std::hash<K>, typename Equal = std::equal_to<K>, typename MemoryPolicy = default_memory_policy, detail::hamts::bits_t B = default_bits>

bool immer::map< K, T, Hash, Equal, MemoryPolicy, B >::operator== ( const map< K, T, Hash, Equal, MemoryPolicy, B > & other ) const

inline

Returns whether the sets are equal.

Definition at line 243 of file map.hpp.

◆ operator[]()

template<typename K, typename T, typename Hash = std::hash<K>, typename Equal = std::equal_to<K>, typename MemoryPolicy = default_memory_policy, detail::hamts::bits_t B = default_bits>

const T& immer::map< K, T, Hash, Equal, MemoryPolicy, B >::operator[] ( const K & k ) const

inline

Returns a const reference to the values associated to the key k. If the key is not contained in the map, it returns a default constructed value. It does not allocate memory and its complexity is effectively $ O(1) $ .

Definition at line 194 of file map.hpp.

◆ set()

template<typename K, typename T, typename Hash = std::hash<K>, typename Equal = std::equal_to<K>, typename MemoryPolicy = default_memory_policy, detail::hamts::bits_t B = default_bits>

map immer::map< K, T, Hash, Equal, MemoryPolicy, B >::set	(	key_type	k,
		mapped_type	v
	)		const

inline

Returns a map containing the association (k, v). If the key is already in the map, it replaces its association in the map. It may allocate memory and its complexity is effectively $ O(1) $ .

Definition at line 263 of file map.hpp.

Referenced by CDeterministicMNList::AddMN(), CDeterministicMNList::AddUniqueProperty(), CDeterministicMNList::DeleteUniqueProperty(), UnserializeImmerMap(), and CDeterministicMNList::UpdateMN().

◆ size()

template<typename K, typename T, typename Hash = std::hash<K>, typename Equal = std::equal_to<K>, typename MemoryPolicy = default_memory_policy, detail::hamts::bits_t B = default_bits>

size_type immer::map< K, T, Hash, Equal, MemoryPolicy, B >::size ( ) const

inline

Returns the number of elements in the container. It does not allocate memory and its complexity is $ O(1) $ .

Definition at line 177 of file map.hpp.

Referenced by CDeterministicMNList::GetAllMNsCount(), CDeterministicMNList::GetMNPayee(), CDeterministicMNList::Serialize(), and SerializeImmerMap().

◆ transient() [1/2]

template<typename K, typename T, typename Hash = std::hash<K>, typename Equal = std::equal_to<K>, typename MemoryPolicy = default_memory_policy, detail::hamts::bits_t B = default_bits>

transient_type immer::map< K, T, Hash, Equal, MemoryPolicy, B >::transient ( ) const &

inline

Returns an transient form of this container, a immer::map_transient.

Definition at line 293 of file map.hpp.

◆ transient() [2/2]

template<typename K, typename T, typename Hash = std::hash<K>, typename Equal = std::equal_to<K>, typename MemoryPolicy = default_memory_policy, detail::hamts::bits_t B = default_bits>

transient_type immer::map< K, T, Hash, Equal, MemoryPolicy, B >::transient ( ) &&

inline

Definition at line 295 of file map.hpp.

◆ update()

template<typename K, typename T, typename Hash = std::hash<K>, typename Equal = std::equal_to<K>, typename MemoryPolicy = default_memory_policy, detail::hamts::bits_t B = default_bits>

template<typename Fn >

map immer::map< K, T, Hash, Equal, MemoryPolicy, B >::update	(	key_type	k,
		Fn &&	fn
	)		const

inline

Returns a map replacing the association (k, v) by the association new association (k, fn(v)), where v is the currently associated value for k in the map or a default constructed value otherwise. It may allocate memory and its complexity is effectively $ O(1) $ .

Definition at line 274 of file map.hpp.

Member Data Documentation

◆ impl_

template<typename K, typename T, typename Hash = std::hash<K>, typename Equal = std::equal_to<K>, typename MemoryPolicy = default_memory_policy, detail::hamts::bits_t B = default_bits>

impl_t immer::map< K, T, Hash, Equal, MemoryPolicy, B >::impl_ = impl_t::empty()

private

Definition at line 308 of file map.hpp.

◆ transient_type

template<typename K, typename T, typename Hash = std::hash<K>, typename Equal = std::equal_to<K>, typename MemoryPolicy = default_memory_policy, detail::hamts::bits_t B = default_bits>

friend immer::map< K, T, Hash, Equal, MemoryPolicy, B >::transient_type

private

Definition at line 302 of file map.hpp.

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

src/immer/map.hpp

Dash Core Source Documentation (0.16.0.1)

Classes

Public Types

Public Member Functions

Private Types

Private Member Functions

Private Attributes

Detailed Description

template<typename K, typename T, typename Hash = std::hash<K>, typename Equal = std::equal_to<K>, typename MemoryPolicy = default_memory_policy, detail::hamts::bits_t B = default_bits> class immer::map< K, T, Hash, Equal, MemoryPolicy, B >

Member Typedef Documentation

◆ const_iterator

◆ const_reference

◆ diference_type

◆ hasher

◆ impl_t

◆ iterator

◆ key_equal

◆ key_type

◆ mapped_type

◆ reference

◆ size_type

◆ transient_type

◆ value_t

◆ value_type

Constructor & Destructor Documentation

◆ map() [1/2]

◆ map() [2/2]

Member Function Documentation

◆ at()

◆ begin()

◆ count()

◆ end()

◆ erase()

◆ find()

◆ impl()

◆ insert()

◆ operator!=()

◆ operator==()

◆ operator[]()

◆ set()

◆ size()

◆ transient() [1/2]

◆ transient() [2/2]

◆ update()

Member Data Documentation

◆ impl_

◆ transient_type

template<typename K, typename T, typename Hash = std::hash<K>, typename Equal = std::equal_to<K>, typename MemoryPolicy = default_memory_policy, detail::hamts::bits_t B = default_bits>
class immer::map< K, T, Hash, Equal, MemoryPolicy, B >