Public Types
typedef Key	key_type

typedef T	mapped_type

typedef std::pair< Key, T >	value_type

typedef set< Key, Compare, Hash, Equal >	key_set_type

typedef map_provider< Key, T, Compare, Hash, Equal, MappedHash, MappedEqual >	provider_type

typedef std::shared_ptr< provider_type >	provider_ptr

typedef confluent::iterator< traits >	iterator

typedef std::reverse_iterator< iterator >	reverse_iterator

Public Member Functions
	map (provider_ptr provider=provider_type::default_provider())

template<class InputIterator >
	map (InputIterator first, InputIterator last, provider_ptr provider=provider_type::default_provider())

	map (std::initializer_list< value_type > ilist, provider_ptr provider=provider_type::default_provider())

	map (iterator first, iterator last)

	map (const map &other)

	map (map &&other)

size_t	insert (const value_type &value)

template<class InputIterator >
size_t	insert (InputIterator first, InputIterator last)

size_t	insert (std::initializer_list< value_type > ilist)

size_t	insert (const map &other)

size_t	insert_or_assign (const value_type &value)

template<class InputIterator >
size_t	insert_or_assign (InputIterator first, InputIterator last)

size_t	insert_or_assign (std::initializer_list< value_type > ilist)

size_t	insert_or_assign (const map &other)

size_t	erase (const key_type &key)

size_t	erase (const value_type &value)

size_t	erase (iterator first, iterator last)

size_t	erase (const key_set_type &other)

size_t	erase (const map &other)

size_t	retain (iterator first, iterator last)

size_t	retain (const key_set_type &other)

size_t	retain (const map &other)

void	clear ()

void	swap (map &other)

map &	operator= (const map &other)

map &	operator= (map &&other)

map &	operator= (std::initializer_list< value_type > ilist)

map	operator\| (const map &rhs) const

map &	operator\|= (const map &rhs)

map	operator& (const map &rhs) const

map	operator& (const key_set_type &rhs) const

map &	operator&= (const map &rhs)

map &	operator&= (const key_set_type &rhs)

map	operator- (const map &rhs) const

map	operator- (const key_set_type &rhs) const

map &	operator-= (const map &rhs)

map &	operator-= (const key_set_type &rhs)

iterator	begin () const

iterator	end () const

iterator	cbegin () const

iterator	cend () const

reverse_iterator	rbegin () const

reverse_iterator	rend () const

iterator	find (const key_type &key) const

iterator	lower_bound (const key_type &key) const

iterator	upper_bound (const key_type &key) const

std::pair< iterator, iterator >	equal_range (const key_type &key) const

const mapped_type &	at (const key_type &key) const

const value_type &	at_index (size_t k) const

size_t	count (const key_type &key) const

size_t	count (const key_type &key, const mapped_type &mapped) const

bool	includes (const map &other) const

key_set_type	key_set () const

const provider_ptr &	provider () const

bool	empty () const

size_t	size () const

size_t	hash () const

bool	operator== (const map &other) const

bool	operator!= (const map &other) const

Detailed Description

template<class Key, class T, class Compare = std::less<Key>, class Hash = std::hash<Key>, class Equal = std::equal_to<Key>, class MappedHash = std::hash<T>, class MappedEqual = std::equal_to<T>>
class confluent::map< Key, T, Compare, Hash, Equal, MappedHash, MappedEqual >

The class confluent::map is a sorted associative container whose instances share key nodes with other sets and maps using the same set_provider and share assigment nodes with other maps using the same map_proivder.

Cloning maps and testing maps for equal content run in constant time. Merge operations such as set union, set intersection and set difference perform at optimal cost not only when one of the input maps is smaller than the other, but also when the number of elements that differ between the input maps is small. Maps can also be merged with sets at the same cost as maps can be merged with maps in operations that remove elements, such as set intersection and set difference.

Contained elements must be comparable, hashable and copy-constructible and documented complexity is based on that such operations are constant in time and memory and that hash collisions are rare.

Examples: CustomValueType.cc, PhoneNumbers.cc, and StatefulFunctors.cc.

Constructor & Destructor Documentation

◆ map() [1/6]

template<class Key , class T , class Compare = std::less<Key>, class Hash = std::hash<Key>, class Equal = std::equal_to<Key>, class MappedHash = std::hash<T>, class MappedEqual = std::equal_to<T>>

confluent::map< Key, T, Compare, Hash, Equal, MappedHash, MappedEqual >::map ( provider_ptr provider = provider_type::default_provider() )

inline

Creates a new map.

Parameters

provider map_provider to use for this map (optional)

Complexity: Constant in time and memory.

◆ map() [2/6]

template<class Key , class T , class Compare = std::less<Key>, class Hash = std::hash<Key>, class Equal = std::equal_to<Key>, class MappedHash = std::hash<T>, class MappedEqual = std::equal_to<T>>

template<class InputIterator >

confluent::map< Key, T, Compare, Hash, Equal, MappedHash, MappedEqual >::map	(	InputIterator	first,
		InputIterator	last,
		provider_ptr	provider = `provider_type::default_provider()`
	)

inline

Creates a new map from a range of elements.

Parameters

first	range start
last	range end
provider	map_provider to use for this map (optional)

Complexity: O(n log n) expected time on random input. O(n) on presorted input. O(n) in memory.

◆ map() [3/6]

template<class Key , class T , class Compare = std::less<Key>, class Hash = std::hash<Key>, class Equal = std::equal_to<Key>, class MappedHash = std::hash<T>, class MappedEqual = std::equal_to<T>>

confluent::map< Key, T, Compare, Hash, Equal, MappedHash, MappedEqual >::map	(	std::initializer_list< value_type >	ilist,
		provider_ptr	provider = `provider_type::default_provider()`
	)

inline

Creates a new map from an initializer_list.

Parameters

ilist	the list of elements to include in the created map
provider	map_provider to use for this map (optional)

Complexity: O(n log n) expected time on random input. O(n) on presorted input. O(n) in memory.

◆ map() [4/6]

template<class Key , class T , class Compare = std::less<Key>, class Hash = std::hash<Key>, class Equal = std::equal_to<Key>, class MappedHash = std::hash<T>, class MappedEqual = std::equal_to<T>>

confluent::map< Key, T, Compare, Hash, Equal, MappedHash, MappedEqual >::map	(	iterator	first,
		iterator	last
	)

inline

Creates a new map from a range in another map.

The created map will use the same map_provider as the source map.

Parameters

first	range start
last	range end

Complexity: O(log n * log n) expected time and memory.

◆ map() [5/6]

template<class Key , class T , class Compare = std::less<Key>, class Hash = std::hash<Key>, class Equal = std::equal_to<Key>, class MappedHash = std::hash<T>, class MappedEqual = std::equal_to<T>>

confluent::map< Key, T, Compare, Hash, Equal, MappedHash, MappedEqual >::map ( const map< Key, T, Compare, Hash, Equal, MappedHash, MappedEqual > & other )

inline

Creates a new map as a copy of another map.

The created map will use the same map_provider as the source map.

Parameters

other other map

Complexity: Constant in time and memory.

◆ map() [6/6]

template<class Key , class T , class Compare = std::less<Key>, class Hash = std::hash<Key>, class Equal = std::equal_to<Key>, class MappedHash = std::hash<T>, class MappedEqual = std::equal_to<T>>

confluent::map< Key, T, Compare, Hash, Equal, MappedHash, MappedEqual >::map ( map< Key, T, Compare, Hash, Equal, MappedHash, MappedEqual > && other )

inline

Creates a new map by moving content from another map.

The created map will use the same map_provider as the source map.

Result is undefined if the other map is used after content has been moved.

Parameters

other other map

Complexity: Constant in time and memory.

Member Function Documentation

◆ insert() [1/4]

template<class Key , class T , class Compare = std::less<Key>, class Hash = std::hash<Key>, class Equal = std::equal_to<Key>, class MappedHash = std::hash<T>, class MappedEqual = std::equal_to<T>>

size_t confluent::map< Key, T, Compare, Hash, Equal, MappedHash, MappedEqual >::insert ( const value_type & value )

inline

Inserts an element into this map.

The new element is inserted if it is not contained before.

Parameters

value element to insert

Returns: the number of inserted elements

Complexity: O(log n) expected time and memory.

Examples: PhoneNumbers.cc.

◆ insert() [2/4]

template<class Key , class T , class Compare = std::less<Key>, class Hash = std::hash<Key>, class Equal = std::equal_to<Key>, class MappedHash = std::hash<T>, class MappedEqual = std::equal_to<T>>

template<class InputIterator >

size_t confluent::map< Key, T, Compare, Hash, Equal, MappedHash, MappedEqual >::insert	(	InputIterator	first,
		InputIterator	last
	)

inline

Inserts a range of elements into this map.

New element are inserted if they are not contained before.

Parameters

first	range start
last	range end

Returns: the number of inserted elements

Complexity: Same cost as first creating a map from the given range and then inserting the created map into this map.

◆ insert() [3/4]

template<class Key , class T , class Compare = std::less<Key>, class Hash = std::hash<Key>, class Equal = std::equal_to<Key>, class MappedHash = std::hash<T>, class MappedEqual = std::equal_to<T>>

size_t confluent::map< Key, T, Compare, Hash, Equal, MappedHash, MappedEqual >::insert ( std::initializer_list< value_type > ilist )

inline

Inserts elements from an initializer_list into this map.

New element are inserted if they are not contained before.

Parameters

ilist the list of elements to insert

Returns: the number of inserted elements

Complexity: Same cost as first creating a map from the given initializer_list and then inserting the created map into this map.

◆ insert() [4/4]

template<class Key , class T , class Compare = std::less<Key>, class Hash = std::hash<Key>, class Equal = std::equal_to<Key>, class MappedHash = std::hash<T>, class MappedEqual = std::equal_to<T>>

size_t confluent::map< Key, T, Compare, Hash, Equal, MappedHash, MappedEqual >::insert ( const map< Key, T, Compare, Hash, Equal, MappedHash, MappedEqual > & other )

inline

Inserts elements in another map into this map.

New element are inserted, replacing any contained element with same key.

Result is undefined if not both maps are using the same map_provider.

Parameters

other other map to insert elements from

Returns: the number of inserted elements

Let n be the size of the larger map. Let m be the size of the smaller map. Let d be the size of the difference between this map and the other map.

Complexity: O(min(m * log(n/m), d * log(n/d))) expected time and memory.

◆ insert_or_assign() [1/4]

template<class Key , class T , class Compare = std::less<Key>, class Hash = std::hash<Key>, class Equal = std::equal_to<Key>, class MappedHash = std::hash<T>, class MappedEqual = std::equal_to<T>>

size_t confluent::map< Key, T, Compare, Hash, Equal, MappedHash, MappedEqual >::insert_or_assign ( const value_type & value )

inline

Inserts an element into this map.

The new element is inserted, replacing any contained element with same key.

Parameters

value element to insert

Returns: the number of inserted elements

Complexity: O(log n) expected time and memory.

Examples: PhoneNumbers.cc.

◆ insert_or_assign() [2/4]

template<class Key , class T , class Compare = std::less<Key>, class Hash = std::hash<Key>, class Equal = std::equal_to<Key>, class MappedHash = std::hash<T>, class MappedEqual = std::equal_to<T>>

template<class InputIterator >

size_t confluent::map< Key, T, Compare, Hash, Equal, MappedHash, MappedEqual >::insert_or_assign	(	InputIterator	first,
		InputIterator	last
	)

inline

Inserts a range of elements into this map.

The new element are inserted, replacing any contained elements with same keys.

Parameters

first	range start
last	range end

Returns: the number of inserted elements

Complexity: Same cost as first creating a map from the given range and then inserting the created map into this map.

◆ insert_or_assign() [3/4]

template<class Key , class T , class Compare = std::less<Key>, class Hash = std::hash<Key>, class Equal = std::equal_to<Key>, class MappedHash = std::hash<T>, class MappedEqual = std::equal_to<T>>

size_t confluent::map< Key, T, Compare, Hash, Equal, MappedHash, MappedEqual >::insert_or_assign ( std::initializer_list< value_type > ilist )

inline

Inserts elements from an initializer_list into this map.

The new element are inserted, replacing any contained elements with same keys.

Parameters

ilist the list of elements to insert

Returns: the number of inserted elements

Complexity: Same cost as first creating a map from the given initializer_list and then inserting the created map into this map.

◆ insert_or_assign() [4/4]

template<class Key , class T , class Compare = std::less<Key>, class Hash = std::hash<Key>, class Equal = std::equal_to<Key>, class MappedHash = std::hash<T>, class MappedEqual = std::equal_to<T>>

size_t confluent::map< Key, T, Compare, Hash, Equal, MappedHash, MappedEqual >::insert_or_assign ( const map< Key, T, Compare, Hash, Equal, MappedHash, MappedEqual > & other )

inline

Inserts elements in another map into this map.

The new element are inserted, replacing any contained elements with same keys.

Result is undefined if not both maps are using the same map_provider.

Parameters

other other map to insert elements from

Returns: the number of inserted elements

Let n be the size of the larger map. Let m be the size of the smaller map. Let d be the size of the difference between this map and the other map.

Complexity: O(min(m * log(n/m), d * log(n/d))) expected time and memory.

◆ erase() [1/5]

template<class Key , class T , class Compare = std::less<Key>, class Hash = std::hash<Key>, class Equal = std::equal_to<Key>, class MappedHash = std::hash<T>, class MappedEqual = std::equal_to<T>>

size_t confluent::map< Key, T, Compare, Hash, Equal, MappedHash, MappedEqual >::erase ( const key_type & key )

inline

Erases an element from this map.

An element with the given key is erased if contained in the map.

Parameters

key	element to erase

Returns: the number of erased elements

Complexity: O(log n) expected time and memory.

Examples: PhoneNumbers.cc.

◆ erase() [2/5]

template<class Key , class T , class Compare = std::less<Key>, class Hash = std::hash<Key>, class Equal = std::equal_to<Key>, class MappedHash = std::hash<T>, class MappedEqual = std::equal_to<T>>

size_t confluent::map< Key, T, Compare, Hash, Equal, MappedHash, MappedEqual >::erase ( const value_type & value )

inline

Erases an element from this map.

The given element is erased if contained in the map.

Parameters

value element to erase

Returns: the number of erased elements

Complexity: O(log n) expected time and memory.

◆ erase() [3/5]

template<class Key , class T , class Compare = std::less<Key>, class Hash = std::hash<Key>, class Equal = std::equal_to<Key>, class MappedHash = std::hash<T>, class MappedEqual = std::equal_to<T>>

size_t confluent::map< Key, T, Compare, Hash, Equal, MappedHash, MappedEqual >::erase	(	iterator	first,
		iterator	last
	)

inline

Erases a range of elements from this map.

The given range must be a range in this map.

Parameters

first	range start
last	range end

Returns: the number of erased elements

Complexity: O(log n * log n) expected time and memory.

Note: This operation might cause destruction of unused nodes, but the cost of destructing nodes is always covered by the cost of creating them.

◆ erase() [4/5]

template<class Key , class T , class Compare = std::less<Key>, class Hash = std::hash<Key>, class Equal = std::equal_to<Key>, class MappedHash = std::hash<T>, class MappedEqual = std::equal_to<T>>

size_t confluent::map< Key, T, Compare, Hash, Equal, MappedHash, MappedEqual >::erase ( const key_set_type & other )

inline

Erases elements whose keys matches the elements in a given set.

After the operation key set of this map will contain the set difference, i.e. all keys that were present in this map but not in the given set.

Result is undefined if the given set is not using the same set_provider as the key set of this map.

Parameters

other other set to erase elements from

Returns: the number of erased elements

Let n be the size of the larger container. Let m be the size of the smaller container. Let d be the size of the difference between the key set of this map and the given set.

Complexity: O(min(m * log(n/m), d * log(n/d))) expected time and memory.

Note: This operation might cause destruction of unused nodes, but the cost of destructing nodes is always covered by the cost of creating them.

◆ erase() [5/5]

template<class Key , class T , class Compare = std::less<Key>, class Hash = std::hash<Key>, class Equal = std::equal_to<Key>, class MappedHash = std::hash<T>, class MappedEqual = std::equal_to<T>>

size_t confluent::map< Key, T, Compare, Hash, Equal, MappedHash, MappedEqual >::erase ( const map< Key, T, Compare, Hash, Equal, MappedHash, MappedEqual > & other )

inline

Erases elements in another map from this map.

After the operation this map will contain the map difference, i.e. all elements that were present in this map but not in the other map.

Result is undefined if not both maps are using the same map_provider.

Parameters

other other map to erase elements from

Returns: the number of erased elements

Let n be the size of the larger map. Let m be the size of the smaller map. Let d be the size of the difference between this map and the other map.

Complexity: O(min(m * log(n/m), d * log(n/d))) expected time and memory.

Note: This operation might cause destruction of unused nodes, but the cost of destructing nodes is always covered by the cost of creating them.

◆ retain() [1/3]

template<class Key , class T , class Compare = std::less<Key>, class Hash = std::hash<Key>, class Equal = std::equal_to<Key>, class MappedHash = std::hash<T>, class MappedEqual = std::equal_to<T>>

size_t confluent::map< Key, T, Compare, Hash, Equal, MappedHash, MappedEqual >::retain	(	iterator	first,
		iterator	last
	)

inline

Retains a range of elements.

The given range must be a range in this map.

After the operation this map will contain the elements in the range.

Parameters

first	range start
last	range end

Returns: the number of erased elements

Complexity: O(log n * log n) expected time and memory.

Note: This operation might cause destruction of unused nodes, but the cost of destructing nodes is always covered by the cost of creating them.

◆ retain() [2/3]

template<class Key , class T , class Compare = std::less<Key>, class Hash = std::hash<Key>, class Equal = std::equal_to<Key>, class MappedHash = std::hash<T>, class MappedEqual = std::equal_to<T>>

size_t confluent::map< Key, T, Compare, Hash, Equal, MappedHash, MappedEqual >::retain ( const key_set_type & other )

inline

Retains elements whose keys matches the elements in a given set.

After the operation key set of this map will contain the set intersection, i.e. all keys that were present in this map and also in the given set.

Result is undefined if not the given set is using the same set_provider as the key set of this map.

Parameters

other other set to erase elements from

Returns: the number of erased elements

Let n be the size of the larger container. Let m be the size of the smaller container. Let d be the size of the difference between the key set of this map and the given set.

Complexity: O(min(m * log(n/m), d * log(n/d))) expected time and memory.

Note: This operation might cause destruction of unused nodes, but the cost of destructing nodes is always covered by the cost of creating them.

◆ retain() [3/3]

template<class Key , class T , class Compare = std::less<Key>, class Hash = std::hash<Key>, class Equal = std::equal_to<Key>, class MappedHash = std::hash<T>, class MappedEqual = std::equal_to<T>>

size_t confluent::map< Key, T, Compare, Hash, Equal, MappedHash, MappedEqual >::retain ( const map< Key, T, Compare, Hash, Equal, MappedHash, MappedEqual > & other )

inline

Retains elements that are contained in another map.

After the operation this map will contain the map intersection, i.e. all elements that were present in this map and also in the other map.

Result is undefined if not both maps are using the same map_provider.

Parameters

other other map to erase elements from

Returns: the number of erased elements

Let n be the size of the larger map. Let m be the size of the smaller map. Let d be the size of the difference between this map and the other map.

Complexity: O(min(m * log(n/m), d * log(n/d))) expected time and memory.

Note: This operation might cause destruction of unused nodes, but the cost of destructing nodes is always covered by the cost of creating them.

◆ clear()

template<class Key , class T , class Compare = std::less<Key>, class Hash = std::hash<Key>, class Equal = std::equal_to<Key>, class MappedHash = std::hash<T>, class MappedEqual = std::equal_to<T>>

void confluent::map< Key, T, Compare, Hash, Equal, MappedHash, MappedEqual >::clear ( )

inline

Erases all elements in this map.

Complexity: Constant in time and memory.

Note: This operation might cause destruction of unused nodes, but the cost of destructing nodes is always covered by the cost of creating them.

◆ swap()

template<class Key , class T , class Compare = std::less<Key>, class Hash = std::hash<Key>, class Equal = std::equal_to<Key>, class MappedHash = std::hash<T>, class MappedEqual = std::equal_to<T>>

void confluent::map< Key, T, Compare, Hash, Equal, MappedHash, MappedEqual >::swap ( map< Key, T, Compare, Hash, Equal, MappedHash, MappedEqual > & other )

inline

Swaps the content of this map with the content of another map.

Complexity: Constant in time and memory.

◆ operator=() [1/3]

template<class Key , class T , class Compare = std::less<Key>, class Hash = std::hash<Key>, class Equal = std::equal_to<Key>, class MappedHash = std::hash<T>, class MappedEqual = std::equal_to<T>>

map& confluent::map< Key, T, Compare, Hash, Equal, MappedHash, MappedEqual >::operator= ( const map< Key, T, Compare, Hash, Equal, MappedHash, MappedEqual > & other )

inline

Replaces the content of this map with the content of another map.

After the operation this map will use the same provider as the other map.

Complexity: Constant in time and memory.

Note: This operation might cause destruction of unused nodes, but the cost of destructing nodes is always covered by the cost of creating them.

◆ operator=() [2/3]

template<class Key , class T , class Compare = std::less<Key>, class Hash = std::hash<Key>, class Equal = std::equal_to<Key>, class MappedHash = std::hash<T>, class MappedEqual = std::equal_to<T>>

map& confluent::map< Key, T, Compare, Hash, Equal, MappedHash, MappedEqual >::operator= ( map< Key, T, Compare, Hash, Equal, MappedHash, MappedEqual > && other )

inline

Replaces the content of this map with the content of another map.

After the operation this map will use the same provider as the other map used before the operation.

Result is undefined if the other map is used after content has been moved.

Complexity: Constant in time and memory.

Note: This operation might cause destruction of unused nodes, but the cost of destructing nodes is always covered by the cost of creating them.

◆ operator=() [3/3]

template<class Key , class T , class Compare = std::less<Key>, class Hash = std::hash<Key>, class Equal = std::equal_to<Key>, class MappedHash = std::hash<T>, class MappedEqual = std::equal_to<T>>

map& confluent::map< Key, T, Compare, Hash, Equal, MappedHash, MappedEqual >::operator= ( std::initializer_list< value_type > ilist )

inline

Replaces the content of this map with elements from an initializer_list.

Parameters

ilist the list of elements to assign

Complexity: O(n log n) expected time on random input. O(n) on presorted input. O(n) in memory.

Note: This operation might cause destruction of unused nodes, but the cost of destructing nodes is always covered by the cost of creating them.

◆ operator|()

template<class Key , class T , class Compare = std::less<Key>, class Hash = std::hash<Key>, class Equal = std::equal_to<Key>, class MappedHash = std::hash<T>, class MappedEqual = std::equal_to<T>>

map confluent::map< Key, T, Compare, Hash, Equal, MappedHash, MappedEqual >::operator| ( const map< Key, T, Compare, Hash, Equal, MappedHash, MappedEqual > & rhs ) const

inline

Returns the union of this map and another map.

Result is undefined if not both maps are using the same map_provider.

Parameters

rhs	other map to merge with this map

Returns: a map containing all elements in this map and in the other map

Let n be the size of the larger map. Let m be the size of the smaller map. Let d be the size of the difference between this map and the other map.

Complexity: O(min(m * log(n/m), d * log(n/d))) expected time and memory.

◆ operator|=()

template<class Key , class T , class Compare = std::less<Key>, class Hash = std::hash<Key>, class Equal = std::equal_to<Key>, class MappedHash = std::hash<T>, class MappedEqual = std::equal_to<T>>

map& confluent::map< Key, T, Compare, Hash, Equal, MappedHash, MappedEqual >::operator|= ( const map< Key, T, Compare, Hash, Equal, MappedHash, MappedEqual > & rhs )

inline

Replaces the content of this map with the union of this map and another map.

Result is undefined if not both maps are using the same map_provider.

Parameters

rhs	other map to merge with this map

Returns: a reference to this map after it has been updated

Let n be the size of the larger map. Let m be the size of the smaller map. Let d be the size of the difference between this map and the other map.

Complexity: O(min(m * log(n/m), d * log(n/d))) expected time and memory.

◆ operator&() [1/2]

template<class Key , class T , class Compare = std::less<Key>, class Hash = std::hash<Key>, class Equal = std::equal_to<Key>, class MappedHash = std::hash<T>, class MappedEqual = std::equal_to<T>>

map confluent::map< Key, T, Compare, Hash, Equal, MappedHash, MappedEqual >::operator& ( const map< Key, T, Compare, Hash, Equal, MappedHash, MappedEqual > & rhs ) const

inline

Returns the intersection of this map and another map.

Result is undefined if not both maps are using the same map_provider.

Parameters

rhs	other map to merge with this map

Returns: a map containing all elements in this map and in the other map

Let n be the size of the larger map. Let m be the size of the smaller map. Let d be the size of the difference between this map and the other map.

Complexity: O(min(m * log(n/m), d * log(n/d))) expected time and memory.

Note: This operation might cause destruction of unused nodes, but the cost of destructing nodes is always covered by the cost of creating them.

◆ operator&() [2/2]

template<class Key , class T , class Compare = std::less<Key>, class Hash = std::hash<Key>, class Equal = std::equal_to<Key>, class MappedHash = std::hash<T>, class MappedEqual = std::equal_to<T>>

map confluent::map< Key, T, Compare, Hash, Equal, MappedHash, MappedEqual >::operator& ( const key_set_type & rhs ) const

inline

Returns the intersection of this map and a given set.

Result is undefined if not the given set is using the same set_provider as the key set of this map.

Parameters

rhs	set to merge with this map

Returns: a map containing all elements in this map whose keys are in the given set

Let n be the size of the larger container. Let m be the size of the smaller container. Let d be the size of the difference between the key set of this map and the given set.

Complexity: O(min(m * log(n/m), d * log(n/d))) expected time and memory.

Note: This operation might cause destruction of unused nodes, but the cost of destructing nodes is always covered by the cost of creating them.

◆ operator&=() [1/2]

template<class Key , class T , class Compare = std::less<Key>, class Hash = std::hash<Key>, class Equal = std::equal_to<Key>, class MappedHash = std::hash<T>, class MappedEqual = std::equal_to<T>>

map& confluent::map< Key, T, Compare, Hash, Equal, MappedHash, MappedEqual >::operator&= ( const map< Key, T, Compare, Hash, Equal, MappedHash, MappedEqual > & rhs )

inline

Replaces the content of this map with the intersection of this map and another map.

Result is undefined if not both maps are using the same map_provider.

Parameters

rhs	other map to merge with this map

Returns: a reference to this map after it has been updated

Let n be the size of the larger map. Let m be the size of the smaller map. Let d be the size of the difference between this map and the other map.

Complexity: O(min(m * log(n/m), d * log(n/d))) expected time and memory.

Note: This operation might cause destruction of unused nodes, but the cost of destructing nodes is always covered by the cost of creating them.

◆ operator&=() [2/2]

template<class Key , class T , class Compare = std::less<Key>, class Hash = std::hash<Key>, class Equal = std::equal_to<Key>, class MappedHash = std::hash<T>, class MappedEqual = std::equal_to<T>>

map& confluent::map< Key, T, Compare, Hash, Equal, MappedHash, MappedEqual >::operator&= ( const key_set_type & rhs )

inline

Replaces the content of this map with the intersection of this map and a given set.

Result is undefined if not the given set is using the same set_provider as the key set of this map.

Parameters

rhs	other map to merge with this map

Returns: a reference to this map after it has been updated

Let n be the size of the larger map. Let m be the size of the smaller map. Let d be the size of the difference between this map and the other map.

Complexity: O(min(m * log(n/m), d * log(n/d))) expected time and memory.

Note: This operation might cause destruction of unused nodes, but the cost of destructing nodes is always covered by the cost of creating them.

◆ operator-() [1/2]

template<class Key , class T , class Compare = std::less<Key>, class Hash = std::hash<Key>, class Equal = std::equal_to<Key>, class MappedHash = std::hash<T>, class MappedEqual = std::equal_to<T>>

map confluent::map< Key, T, Compare, Hash, Equal, MappedHash, MappedEqual >::operator- ( const map< Key, T, Compare, Hash, Equal, MappedHash, MappedEqual > & rhs ) const

inline

Returns the difference of this map and another map.

Result is undefined if not both maps are using the same map_provider.

Parameters

rhs	other map to merge with this map

Returns: a map containing all elements in this map and in the other map

Let n be the size of the larger map. Let m be the size of the smaller map. Let d be the size of the difference between this map and the other map.

Complexity: O(min(m * log(n/m), d * log(n/d))) expected time and memory.

Note: This operation might cause destruction of unused nodes, but the cost of destructing nodes is always covered by the cost of creating them.

◆ operator-() [2/2]

template<class Key , class T , class Compare = std::less<Key>, class Hash = std::hash<Key>, class Equal = std::equal_to<Key>, class MappedHash = std::hash<T>, class MappedEqual = std::equal_to<T>>

map confluent::map< Key, T, Compare, Hash, Equal, MappedHash, MappedEqual >::operator- ( const key_set_type & rhs ) const

inline

Returns the difference of this map and a given set.

Result is undefined if not the given set is using the same set_provider as the key set of this map.

Parameters

rhs	set to merge with this map

Returns: a map containing all elements in this map whose keys are in the given set

Let n be the size of the larger container. Let m be the size of the smaller container. Let d be the size of the difference between the key set of this map and the given set.

Complexity: O(min(m * log(n/m), d * log(n/d))) expected time and memory.

Note: This operation might cause destruction of unused nodes, but the cost of destructing nodes is always covered by the cost of creating them.

◆ operator-=() [1/2]

template<class Key , class T , class Compare = std::less<Key>, class Hash = std::hash<Key>, class Equal = std::equal_to<Key>, class MappedHash = std::hash<T>, class MappedEqual = std::equal_to<T>>

map& confluent::map< Key, T, Compare, Hash, Equal, MappedHash, MappedEqual >::operator-= ( const map< Key, T, Compare, Hash, Equal, MappedHash, MappedEqual > & rhs )

inline

Replaces the content of this map with the difference of this map and another map.

Result is undefined if not both maps are using the same map_provider.

Parameters

rhs	other map to merge with this map

Returns: a reference to this map after it has been updated

Let n be the size of the larger map. Let m be the size of the smaller map. Let d be the size of the difference between this map and the other map.

Complexity: O(min(m * log(n/m), d * log(n/d))) expected time and memory.

Note: This operation might cause destruction of unused nodes, but the cost of destructing nodes is always covered by the cost of creating them.

◆ operator-=() [2/2]

template<class Key , class T , class Compare = std::less<Key>, class Hash = std::hash<Key>, class Equal = std::equal_to<Key>, class MappedHash = std::hash<T>, class MappedEqual = std::equal_to<T>>

map& confluent::map< Key, T, Compare, Hash, Equal, MappedHash, MappedEqual >::operator-= ( const key_set_type & rhs )

inline

Replaces the content of this map with the intersection of this map and a given set.

Result is undefined if not the given set is using the same set_provider as the key set of this map.

Parameters

rhs	other map to merge with this map

Returns: a reference to this map after it has been updated

Let n be the size of the larger map. Let m be the size of the smaller map. Let d be the size of the difference between this map and the other map.

Complexity: O(min(m * log(n/m), d * log(n/d))) expected time and memory.

Note: This operation might cause destruction of unused nodes, but the cost of destructing nodes is always covered by the cost of creating them.

◆ begin()

template<class Key , class T , class Compare = std::less<Key>, class Hash = std::hash<Key>, class Equal = std::equal_to<Key>, class MappedHash = std::hash<T>, class MappedEqual = std::equal_to<T>>

iterator confluent::map< Key, T, Compare, Hash, Equal, MappedHash, MappedEqual >::begin ( ) const

inline

Returns an iterator to the beginning of this map.

◆ end()

template<class Key , class T , class Compare = std::less<Key>, class Hash = std::hash<Key>, class Equal = std::equal_to<Key>, class MappedHash = std::hash<T>, class MappedEqual = std::equal_to<T>>

iterator confluent::map< Key, T, Compare, Hash, Equal, MappedHash, MappedEqual >::end ( ) const

inline

Returns an iterator to the end of this map.

◆ cbegin()

template<class Key , class T , class Compare = std::less<Key>, class Hash = std::hash<Key>, class Equal = std::equal_to<Key>, class MappedHash = std::hash<T>, class MappedEqual = std::equal_to<T>>

iterator confluent::map< Key, T, Compare, Hash, Equal, MappedHash, MappedEqual >::cbegin ( ) const

inline

Returns an iterator to the beginning of this map.

◆ cend()

template<class Key , class T , class Compare = std::less<Key>, class Hash = std::hash<Key>, class Equal = std::equal_to<Key>, class MappedHash = std::hash<T>, class MappedEqual = std::equal_to<T>>

iterator confluent::map< Key, T, Compare, Hash, Equal, MappedHash, MappedEqual >::cend ( ) const

inline

Returns an iterator to the end of this map.

◆ rbegin()

template<class Key , class T , class Compare = std::less<Key>, class Hash = std::hash<Key>, class Equal = std::equal_to<Key>, class MappedHash = std::hash<T>, class MappedEqual = std::equal_to<T>>

reverse_iterator confluent::map< Key, T, Compare, Hash, Equal, MappedHash, MappedEqual >::rbegin ( ) const

inline

Returns a reverse iterator to the beginning of this map.

◆ rend()

template<class Key , class T , class Compare = std::less<Key>, class Hash = std::hash<Key>, class Equal = std::equal_to<Key>, class MappedHash = std::hash<T>, class MappedEqual = std::equal_to<T>>

reverse_iterator confluent::map< Key, T, Compare, Hash, Equal, MappedHash, MappedEqual >::rend ( ) const

inline

Returns a reverse iterator to the end of this map.

◆ find()

template<class Key , class T , class Compare = std::less<Key>, class Hash = std::hash<Key>, class Equal = std::equal_to<Key>, class MappedHash = std::hash<T>, class MappedEqual = std::equal_to<T>>

iterator confluent::map< Key, T, Compare, Hash, Equal, MappedHash, MappedEqual >::find ( const key_type & key ) const

inline

Finds an element with a given key.

Parameters

key	key to search for

Returns: an iterator to the found element or end of this set if not found

Complexity: O(log n) expected time.

◆ lower_bound()

template<class Key , class T , class Compare = std::less<Key>, class Hash = std::hash<Key>, class Equal = std::equal_to<Key>, class MappedHash = std::hash<T>, class MappedEqual = std::equal_to<T>>

iterator confluent::map< Key, T, Compare, Hash, Equal, MappedHash, MappedEqual >::lower_bound ( const key_type & key ) const

inline

Returns an iterator to the first element whose key does not compare less than a given key.

Parameters

key	key to search for

Returns: an iterator to the first element not less than the given key.

Complexity: O(log n) expected time.

◆ upper_bound()

template<class Key , class T , class Compare = std::less<Key>, class Hash = std::hash<Key>, class Equal = std::equal_to<Key>, class MappedHash = std::hash<T>, class MappedEqual = std::equal_to<T>>

iterator confluent::map< Key, T, Compare, Hash, Equal, MappedHash, MappedEqual >::upper_bound ( const key_type & key ) const

inline

Returns an iterator to the first element whose key compares greater than a given key.

Parameters

key	key to search for

Returns: an iterator to the first element greater than the given key.

Complexity: O(log n) expected time.

◆ equal_range()

template<class Key , class T , class Compare = std::less<Key>, class Hash = std::hash<Key>, class Equal = std::equal_to<Key>, class MappedHash = std::hash<T>, class MappedEqual = std::equal_to<T>>

std::pair<iterator, iterator> confluent::map< Key, T, Compare, Hash, Equal, MappedHash, MappedEqual >::equal_range ( const key_type & key ) const

inline

Returns range of elements matching a given key.

r = s.equal_range(key);

is equivalent to

r = { s.lower_bound(key), s.upper_bound(key)};

Complexity: O(log n) expected time.

◆ at()

template<class Key , class T , class Compare = std::less<Key>, class Hash = std::hash<Key>, class Equal = std::equal_to<Key>, class MappedHash = std::hash<T>, class MappedEqual = std::equal_to<T>>

const mapped_type& confluent::map< Key, T, Compare, Hash, Equal, MappedHash, MappedEqual >::at ( const key_type & key ) const

inline

Returns a mapped value that matches a given key.

Parameters

key	key to search for

Returns: the mapped value of the element whose key matches the given key.

Exceptions

std::out_of_range if the given key was not found

Complexity: O(log n) expected time.

◆ at_index()

template<class Key , class T , class Compare = std::less<Key>, class Hash = std::hash<Key>, class Equal = std::equal_to<Key>, class MappedHash = std::hash<T>, class MappedEqual = std::equal_to<T>>

const value_type& confluent::map< Key, T, Compare, Hash, Equal, MappedHash, MappedEqual >::at_index ( size_t k ) const

inline

Finds an element at a given index.

Parameters

k	the index of the wanted element

Returns: a reference to the element at the given index

Complexity: O(log n) expected time.

◆ count() [1/2]

template<class Key , class T , class Compare = std::less<Key>, class Hash = std::hash<Key>, class Equal = std::equal_to<Key>, class MappedHash = std::hash<T>, class MappedEqual = std::equal_to<T>>

size_t confluent::map< Key, T, Compare, Hash, Equal, MappedHash, MappedEqual >::count ( const key_type & key ) const

inline

Returns the number of elements whose key match a given key

Parameters

key	key to search for

Returns: 0 if an element was found, otherwise 1

Complexity: O(log n) expected time.

◆ count() [2/2]

template<class Key , class T , class Compare = std::less<Key>, class Hash = std::hash<Key>, class Equal = std::equal_to<Key>, class MappedHash = std::hash<T>, class MappedEqual = std::equal_to<T>>

size_t confluent::map< Key, T, Compare, Hash, Equal, MappedHash, MappedEqual >::count	(	const key_type &	key,
		const mapped_type &	mapped
	)		const

inline

Returns the number of elements matching a given key and mapped value.

Parameters

key	key to search for
mapped	mapped value to search for

Returns: 0 if an element was found, otherwise 1

Complexity: O(log n) expected time.

◆ includes()

template<class Key , class T , class Compare = std::less<Key>, class Hash = std::hash<Key>, class Equal = std::equal_to<Key>, class MappedHash = std::hash<T>, class MappedEqual = std::equal_to<T>>

bool confluent::map< Key, T, Compare, Hash, Equal, MappedHash, MappedEqual >::includes ( const map< Key, T, Compare, Hash, Equal, MappedHash, MappedEqual > & other ) const

inline

Tests if this map includes the elements in another map.

Result is undefined if not both maps are using the same map_provider.

Parameters

other map to test if its elements are included in this map

Returns: true if all elements are included, false otherwise

Let n be the size of this map. Let m be the size of the other. Let d be the size of the difference between this map and the other map.

Complexity: O(min(m * log(n/m), d * log(n/d))) expected time and memory.

Note: The operation will return directly if m > n.

◆ key_set()

template<class Key , class T , class Compare = std::less<Key>, class Hash = std::hash<Key>, class Equal = std::equal_to<Key>, class MappedHash = std::hash<T>, class MappedEqual = std::equal_to<T>>

key_set_type confluent::map< Key, T, Compare, Hash, Equal, MappedHash, MappedEqual >::key_set ( ) const

inline

Returns a set containing the keys in this map.

Complexity: Constant in time and memory.

Examples: PhoneNumbers.cc.

◆ provider()

template<class Key , class T , class Compare = std::less<Key>, class Hash = std::hash<Key>, class Equal = std::equal_to<Key>, class MappedHash = std::hash<T>, class MappedEqual = std::equal_to<T>>

const provider_ptr& confluent::map< Key, T, Compare, Hash, Equal, MappedHash, MappedEqual >::provider ( ) const

inline

Returns a shared pointer to the map_provider used by this map.

◆ empty()

template<class Key , class T , class Compare = std::less<Key>, class Hash = std::hash<Key>, class Equal = std::equal_to<Key>, class MappedHash = std::hash<T>, class MappedEqual = std::equal_to<T>>

bool confluent::map< Key, T, Compare, Hash, Equal, MappedHash, MappedEqual >::empty ( ) const

inline

Tests if this map is empty.

Returns: true if this map contains no elements, false otherwise

Complexity: Constant in time.

◆ size()

template<class Key , class T , class Compare = std::less<Key>, class Hash = std::hash<Key>, class Equal = std::equal_to<Key>, class MappedHash = std::hash<T>, class MappedEqual = std::equal_to<T>>

size_t confluent::map< Key, T, Compare, Hash, Equal, MappedHash, MappedEqual >::size ( ) const

inline

Returns the number of elements in this map.

Complexity: Constant in time.

Examples: PhoneNumbers.cc.

◆ hash()

template<class Key , class T , class Compare = std::less<Key>, class Hash = std::hash<Key>, class Equal = std::equal_to<Key>, class MappedHash = std::hash<T>, class MappedEqual = std::equal_to<T>>

size_t confluent::map< Key, T, Compare, Hash, Equal, MappedHash, MappedEqual >::hash ( ) const

inline

Returns the combined hash value of all elements in this map.

Complexity: Constant in time.

◆ operator==()

template<class Key , class T , class Compare = std::less<Key>, class Hash = std::hash<Key>, class Equal = std::equal_to<Key>, class MappedHash = std::hash<T>, class MappedEqual = std::equal_to<T>>

bool confluent::map< Key, T, Compare, Hash, Equal, MappedHash, MappedEqual >::operator== ( const map< Key, T, Compare, Hash, Equal, MappedHash, MappedEqual > & other ) const

inline

Tests if this map contains the same elements as another map.

Result is undefined if not both maps are using the same map_provider.

Returns: : true if this map contains the same elements as the other map, false otherwise

Complexity: Constant in time.

◆ operator!=()

template<class Key , class T , class Compare = std::less<Key>, class Hash = std::hash<Key>, class Equal = std::equal_to<Key>, class MappedHash = std::hash<T>, class MappedEqual = std::equal_to<T>>

bool confluent::map< Key, T, Compare, Hash, Equal, MappedHash, MappedEqual >::operator!= ( const map< Key, T, Compare, Hash, Equal, MappedHash, MappedEqual > & other ) const

inline

Tests if this map does not contain the same elements as another map.

Result is undefined if not both maps are using the same map_provider.

Returns: : true if this map does not contain the same elements as the other map, false otherwise

Complexity: Constant in time.

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

src/map.h

Public Types

Public Member Functions

Detailed Description

template<class Key, class T, class Compare = std::less<Key>, class Hash = std::hash<Key>, class Equal = std::equal_to<Key>, class MappedHash = std::hash<T>, class MappedEqual = std::equal_to<T>> class confluent::map< Key, T, Compare, Hash, Equal, MappedHash, MappedEqual >

Constructor & Destructor Documentation

◆ map() [1/6]

◆ map() [2/6]

◆ map() [3/6]

◆ map() [4/6]

◆ map() [5/6]

◆ map() [6/6]

Member Function Documentation

◆ insert() [1/4]

◆ insert() [2/4]

◆ insert() [3/4]

◆ insert() [4/4]

◆ insert_or_assign() [1/4]

◆ insert_or_assign() [2/4]

◆ insert_or_assign() [3/4]

◆ insert_or_assign() [4/4]

◆ erase() [1/5]

◆ erase() [2/5]

◆ erase() [3/5]

◆ erase() [4/5]

◆ erase() [5/5]

◆ retain() [1/3]

◆ retain() [2/3]

◆ retain() [3/3]

◆ clear()

◆ swap()

◆ operator=() [1/3]

◆ operator=() [2/3]

◆ operator=() [3/3]

◆ operator|()

◆ operator|=()

◆ operator&() [1/2]

◆ operator&() [2/2]

◆ operator&=() [1/2]

◆ operator&=() [2/2]

◆ operator-() [1/2]

◆ operator-() [2/2]

◆ operator-=() [1/2]

◆ operator-=() [2/2]

◆ begin()

◆ end()

◆ cbegin()

◆ cend()

◆ rbegin()

◆ rend()

◆ find()

◆ lower_bound()

◆ upper_bound()

◆ equal_range()

◆ at()

◆ at_index()

◆ count() [1/2]

◆ count() [2/2]

◆ includes()

◆ key_set()

◆ provider()

◆ empty()

◆ size()

◆ hash()

◆ operator==()

◆ operator!=()

template<class Key, class T, class Compare = std::less<Key>, class Hash = std::hash<Key>, class Equal = std::equal_to<Key>, class MappedHash = std::hash<T>, class MappedEqual = std::equal_to<T>>
class confluent::map< Key, T, Compare, Hash, Equal, MappedHash, MappedEqual >