An object of this class is a map that combines the lookup speed of an unordered_map<> and ordering and iterator stability capabilities of a list<>. More...

#include <linked_hash_map.hpp>

Public Types
using	Key = Key_t
	Convenience alias for template arg.

using	Mapped = Mapped_t
	Convenience alias for template arg.

using	Hash = Hash_t
	Convenience alias for template arg.

using	Pred = Pred_t
	Convenience alias for template arg.

using	Value = std::pair< Key const, Mapped >
	Short-hand for key/mapped-value pairs stored in the structure.

using	Value_movable = std::pair< Key, Mapped >
	Short-hand for key/mapped-value pair best-suited (perf-wise) as arg type for the moving `insert()` overload.

using	size_type = std::size_t
	Expresses sizes/lengths of relevant things.

using	difference_type = std::ptrdiff_t
	Type for difference of `size_type`s.

using	Iterator = typename Value_list::iterator
	Type for iterator pointing into a mutable structure of this type.

using	Const_iterator = typename Value_list::const_iterator
	Type for iterator pointing into an immutable structure of this type.

using	Reverse_iterator = typename Value_list::reverse_iterator
	Type for reverse iterator pointing into a mutable structure of this type.

using	Const_reverse_iterator = typename Value_list::const_reverse_iterator
	Type for reverse iterator pointing into an immutable structure of this type.

using	key_type = Key
	For container compliance (hence the irregular capitalization): Key type.

using	mapped_type = Mapped
	For container compliance (hence the irregular capitalization): Mapped type.

using	value_type = Value
	For container compliance (hence the irregular capitalization): Key/Mapped pair type.

using	hasher = Hash
	For container compliance (hence the irregular capitalization): Hash type.

using	key_equal = Pred
	For container compliance (hence the irregular capitalization): Pred type.

using	pointer = Value *
	For container compliance (hence the irregular capitalization): pointer to Key/Mapped pair type.

using	const_pointer = const Value *
	For container compliance (hence the irregular capitalization): pointer to `const Key`/Mapped pair type.

using	reference = Value &
	For container compliance (hence the irregular capitalization): reference to Key/Mapped pair type.

using	const_reference = const Value &
	For container compliance (hence the irregular capitalization): reference to `const Key`/Mapped pair type.

using	iterator = Iterator
	For container compliance (hence the irregular capitalization): Iterator type.

using	const_iterator = Const_iterator
	For container compliance (hence the irregular capitalization): Const_iterator type.

Public Member Functions
	Linked_hash_map (size_type n_buckets=size_type(-1), const Hash &hasher_obj=Hash{}, const Pred &pred=Pred{})
	Constructs empty structure with some basic parameters. More...

	Linked_hash_map (std::initializer_list< Value > values, size_type n_buckets=size_type(-1), const Hash &hasher_obj=Hash{}, const Pred &pred=Pred{})
	Constructs structure with some basic parameters, and values initialized from initializer list. More...

	Linked_hash_map (const Linked_hash_map &src)
	Constructs object that is a copy of the given source. More...

	Linked_hash_map (Linked_hash_map &&src)
	Constructs object by making it equal to the given source, while the given source becomes as-if default-cted. More...

Linked_hash_map &	operator= (const Linked_hash_map &src)
	Overwrites this object with a copy of the given source. More...

Linked_hash_map &	operator= (Linked_hash_map &&src)
	Overwrites this object making it identical to the given source, while the given source becomes as-if default-cted. More...

void	swap (Linked_hash_map &other)
	Swaps the contents of this structure and `other`. More...

std::pair< Iterator, bool >	insert (const Value &key_and_mapped)
	Attempts to insert (copying both key and mapped-value) the given key/mapped-value pair into the map; if key already in `*this` makes no change. More...

std::pair< Iterator, bool >	insert (Value_movable &&key_and_mapped)
	Identical to the other overload, except that (if key not already present in `this`) the key and mapped-value are moved, not copied, into `this`. More...

Mapped &	operator[] (const Key &key)
	Either finds the Mapped value at the given key, or if not found inserts one with a default-constructed `Mapped{}`; then returns reference to the Mapped. More...

Mapped &	operator[] (Key &&key)
	Identical to the other overload, except that (if key not already present in `this`) the key is moved, not copied, into `this`. More...

Iterator	find (const Key &key)
	Attempts to find value at the given key in the map. More...

Const_iterator	find (const Key &key) const
	Identical to the other overload but in a `const` context: the returned iterator is to immutable memory. More...

size_type	count (const Key &key) const
	Returns the number of times a key equal to the given one is present (as-if via find()) in the map: either 1 or 0. More...

void	touch (const Const_iterator &it)
	Given a valid iterator into the structure, makes the pointed-to element "newest" by moving it from wherever it is to be first in the iteration order. More...

bool	touch (const Key &key)
	Given a key into the structure, makes the corresponding element "newest" by moving it from wherever it is to be first in the iteration order; or does nothing if no such key. More...

Iterator	erase (const Const_iterator &it)
	Erases the element pointed to by the given valid iterator. More...

Iterator	erase (const Const_iterator &it_newest, const Const_iterator &it_past_oldest)
	Erases all elements in the range [`it_newest`, `it_past_oldest`). More...

size_type	erase (const Key &key)
	Erases the element with the given key, if it exists. More...

void	clear ()
	Makes it so that `size() == 0`.

Iterator	begin ()
	Synonym of newest(). More...

Iterator	newest ()
	Returns first, a/k/a "newest," element's iterator; or past_oldest() if empty(). More...

Iterator	end ()
	Synonym of past_oldest(). More...

Iterator	past_oldest ()
	Returns special iterator indicating the position just past the iteration order; if not empty() this is one past last, a/k/a "oldest," element in the iteration order. More...

Const_iterator	cbegin () const
	Synonym of const_newest(). More...

Const_iterator	begin () const
	Synonym of cbegin(). More...

Const_iterator	const_newest () const
	Same as newest() but operating on immutable `*this`. More...

Const_iterator	cend () const
	Synonym of const_past_oldest(). More...

Const_iterator	end () const
	Synonym of cend(). More...

Const_iterator	const_past_oldest () const
	Same as past_oldest() but operating on immutable `*this`. More...

Reverse_iterator	rbegin ()
	Synonym of oldest(). More...

Reverse_iterator	oldest ()
	Returns first, a/k/a "oldest," element's reverse iterator. More...

Reverse_iterator	rend ()
	Synonym of past_newest(). More...

Reverse_iterator	past_newest ()
	Returns one past last, a/k/a "newest," element's reverse iterator. More...

Const_reverse_iterator	crbegin () const
	Synonym of const_oldest(). More...

Const_reverse_iterator	const_oldest () const
	Returns first, a/k/a "oldest," element's reverse iterator (to immutable element). More...

Const_reverse_iterator	crend () const
	Synonym of const_past_newest(). More...

Const_reverse_iterator	const_past_newest () const
	Returns special reverse iterator indicating the position just past the reverse-iteration order; if not empty() this is one past last, a/k/a "newest," element in the reverse-iteration order. More...

bool	empty () const
	Returns true if and only if container is empty. More...

size_type	size () const
	Returns number of elements stored. More...

size_type	max_size () const
	Returns max number of elements that can be stored. More...

Related Functions
(Note that these are not member functions.)
template<typename Key_t , typename Mapped_t , typename Hash_t , typename Pred_t >
void	swap (Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t > &val1, Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t > &val2)
	Equivalent to `val1.swap(val2)`. More...

Detailed Description

template<typename Key_t, typename Mapped_t, typename Hash_t, typename Pred_t>
class flow::util::Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >

An object of this class is a map that combines the lookup speed of an unordered_map<> and ordering and iterator stability capabilities of a list<>.

The API is generally that of an unordered_map<>. The differences essentially all have to do with iterators. This map introduces a concept of "newness," which determines the iteration order. Moreover, every iterator remains valid except (of course) under erasure of the underlying element. Newness is defined as follows inductively: whenever an element is inserted, it is "newest," thus it is placed at the front of the iterator order. Furthermore, the methods touch() can be used to make any element "newest" (moved to the front of the iterator order). Iterator thus formed orders elements from newest to oldest (hence newest() is begin(), past_oldest() is end()).

Performance expectations: The best way to determine a method's time needs is to imagine what it must do. If it must perform a lookup by key, that is an unordered_set<> lookup resulting in an (at least internal) iterator. If it must insert an element, it is always inserted at the start of a list; and also into an unordered_set<>. If it must erase an element based on an iterator, that element is erased from a list based on that iterator; and also by key from said unordered_set<>. Iteration itself is iteration along a list. But essentially, every operation is either near constant time or constant time. In terms of space needs, this essentially stores the values themselves in a list; and also a pointer to each list-held key/element in an unordered_set<>, which also stores a pointer or list iterator per element.

Move semantics for both keys and mapped-values are supported (let T be a concrete type for a *this and x a *this):

x.insert(std::make_pair<Key, Mapped>(..., ...));
- or x.insert(T::Value_movable{..., ...});
x[std::move(...)] = std::move(...).

There is the standard complement of container-wide move operations: move-construction, move-assignment, and swap() (all constant-time, excluding any implied this->clear() in the move-assignment).

The iterators are, really, list<pair<const Key, Mapped>> iterators; and as such are not invalidated except due to direct erasure of a given pointee.

Todo:: Linked_hash_map and Linked_hash_set have a reasonable complement of C++1x-ish APIs including move-semantics; but the API does not quite mirror the full complement of what is in existence for unordered_* counterparts in C++17 STL/Boost – it would be nice to add these. This includes such things as .emplace() and .try_emplace() but more fundamentally would probably involve trolling std::unordered_* and copying its ~full API (and likely some of a decent impl too). That said what's available already acquits itself reasonably well. (Historically this was first written before C++11 and hasn't been given the full-on C++1x overhaul but instead merely the essentials thereof.)

Thread safety

Same as for unordered_map<>.

Template Parameters

Key_t	Key type. We omit formal requirements, as it is tedious and full of corner cases depending on what you plan to invoke (e.g., whether you use move-semantics for keys). Please use common sense knowing the basic data structures involved as explained above. That said: if Key is of non-trivial size, it is good to have it have performant move-constructibility and move-assignability and then make use of it via move-aware APIs as suggested in the doc header above.
Mapped_t	The 2nd (satellite) part of the Value pair type. Same commentary as for Key applies here.
Hash_t	Hasher type. Same requirements and behavior as `boost::unordered_set<>` counterpart. If using the default value for Hash (`boost::hash<Key>`), and the default object is passed to ctor (`Hash{}`) (this is typical), but there is no hash-function already defined for Key, then the easiest way to define it is: make a `size_t hash_value(Key)` free function in the same namespace as Key.
Pred_t	Equality-determiner type. Same requirements and behavior as `boost::unordered_set<>` counterpart. If using the default value for Pred (`std::equal_to<Key>`), and the default object is passed to ctor (`Pred{}`) (this is typical), but there is no equality op defined for Key, then the easiest way to define it is: make an operator-method or free function such that `k1 == k2` (where `k1` and `k2` are `Key`s) determines equality or lack thereof.

Constructor & Destructor Documentation

◆ Linked_hash_map() [1/4]

template<typename Key_t , typename Mapped_t , typename Hash_t , typename Pred_t >

flow::util::Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::Linked_hash_map	(	size_type	n_buckets = `size_type(-1)`,
		const Hash &	hasher_obj = `Hash{}`,
		const Pred &	pred = `Pred{}`
	)

Constructs empty structure with some basic parameters.

Parameters

n_buckets	Number of buckets for the unordered (hash) table. Special value -1 (default) will cause us to use whatever `unordered_set<>` would use by default.
hasher_obj	Instance of the hash function type (`hasher_obj(k) -> size_t` should be hash of `Key k`).
pred	Instance of the equality function type (`pred(k1, k2)` should return `true` if and only if the `Key`s are equal by value).

◆ Linked_hash_map() [2/4]

template<typename Key_t , typename Mapped_t , typename Hash_t , typename Pred_t >

flow::util::Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::Linked_hash_map	(	std::initializer_list< Value >	values,
		size_type	n_buckets = `size_type(-1)`,
		const Hash &	hasher_obj = `Hash{}`,
		const Pred &	pred = `Pred{}`
	)

explicit

Constructs structure with some basic parameters, and values initialized from initializer list.

The values are inserted as if insert(v) was called for each pair v in values in reverse order. Since the canonical ordering places the newest (last inserted/touch()ed) element at the front of the ordering, that means that forward iteration through the set (right after this constructor runs) will yield values in the same order as in initializer list values.

Parameters

values	Values with which to fill the structure after initializing it. Typically you'd provide a series of key/value pairs like this: `{ { key1, value1 }, { key2, value2 }, ... }`. They will appear in iterated sequence in the same order as they appear in this list.
n_buckets	See other constructor.
hasher_obj	See other constructor.
pred	See other constructor.

◆ Linked_hash_map() [3/4]

template<typename Key_t , typename Mapped_t , typename Hash_t , typename Pred_t >

flow::util::Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::Linked_hash_map ( const Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t > & src )

Constructs object that is a copy of the given source.

Equivalent to default-ction followed by operator=(src).

Parameters

src	Source object.

◆ Linked_hash_map() [4/4]

template<typename Key_t , typename Mapped_t , typename Hash_t , typename Pred_t >

flow::util::Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::Linked_hash_map ( Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t > && src )

Constructs object by making it equal to the given source, while the given source becomes as-if default-cted.

Equivalent to default-ction followed by operator=(std::move(src)).

This is a constant-time operation.

Parameters

src	Source object which is emptied.

Member Function Documentation

◆ begin() [1/2]

template<typename Key_t , typename Mapped_t , typename Hash_t , typename Pred_t >

Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::Iterator flow::util::Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::begin

Synonym of newest().

Returns: See newest().

◆ begin() [2/2]

template<typename Key_t , typename Mapped_t , typename Hash_t , typename Pred_t >

Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::Const_iterator flow::util::Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::begin

Synonym of cbegin().

Exists to satisfy the C++11 rangy stuff (which makes for(:) – and other magic – work).

Returns: See cbegin().

◆ cbegin()

template<typename Key_t , typename Mapped_t , typename Hash_t , typename Pred_t >

Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::Const_iterator flow::util::Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::cbegin

Synonym of const_newest().

Exists as standard container method (hence the odd formatting).

Returns: See const_newest().

◆ cend()

template<typename Key_t , typename Mapped_t , typename Hash_t , typename Pred_t >

Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::Const_iterator flow::util::Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::cend

Synonym of const_past_oldest().

Exists as standard container method (hence the odd formatting).

Returns: See const_past_oldest().

◆ const_newest()

template<typename Key_t , typename Mapped_t , typename Hash_t , typename Pred_t >

Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::Const_iterator flow::util::Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::const_newest

Same as newest() but operating on immutable *this.

Returns: Ditto.

◆ const_oldest()

template<typename Key_t , typename Mapped_t , typename Hash_t , typename Pred_t >

Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::Const_reverse_iterator flow::util::Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::const_oldest

Returns first, a/k/a "oldest," element's reverse iterator (to immutable element).

Returns: Ditto.

◆ const_past_newest()

template<typename Key_t , typename Mapped_t , typename Hash_t , typename Pred_t >

Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::Const_reverse_iterator flow::util::Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::const_past_newest

Returns special reverse iterator indicating the position just past the reverse-iteration order; if not empty() this is one past last, a/k/a "newest," element in the reverse-iteration order.

Returns: Ditto.

◆ const_past_oldest()

template<typename Key_t , typename Mapped_t , typename Hash_t , typename Pred_t >

Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::Const_iterator flow::util::Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::const_past_oldest

Same as past_oldest() but operating on immutable *this.

Returns: Ditto.

◆ count()

template<typename Key_t , typename Mapped_t , typename Hash_t , typename Pred_t >

Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::size_type flow::util::Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::count ( const Key & key ) const

Returns the number of times a key equal to the given one is present (as-if via find()) in the map: either 1 or 0.

Parameters

key	Key whose equal to find.

Returns: 0 or 1.

◆ crbegin()

template<typename Key_t , typename Mapped_t , typename Hash_t , typename Pred_t >

Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::Const_reverse_iterator flow::util::Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::crbegin

Synonym of const_oldest().

Returns: See const_oldest().

◆ crend()

template<typename Key_t , typename Mapped_t , typename Hash_t , typename Pred_t >

Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::Const_reverse_iterator flow::util::Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::crend

Synonym of const_past_newest().

Exists as standard container method.

Returns: See const_past_newest().

◆ empty()

template<typename Key_t , typename Mapped_t , typename Hash_t , typename Pred_t >

bool flow::util::Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::empty

Returns true if and only if container is empty.

Same performance as of unordered_set<>.

Returns: Ditto.

◆ end() [1/2]

template<typename Key_t , typename Mapped_t , typename Hash_t , typename Pred_t >

Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::Iterator flow::util::Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::end

Synonym of past_oldest().

Exists as standard container method.

Returns: See past_oldest().

◆ end() [2/2]

template<typename Key_t , typename Mapped_t , typename Hash_t , typename Pred_t >

Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::Const_iterator flow::util::Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::end

Synonym of cend().

Exists to satisfy the C++11 rangy stuff (which makes for(:) – and other magic – work).

Returns: See cend().

◆ erase() [1/3]

template<typename Key_t , typename Mapped_t , typename Hash_t , typename Pred_t >

Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::Iterator flow::util::Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::erase ( const Const_iterator & it )

Erases the element pointed to by the given valid iterator.

Behavior undefined if it is not valid. it becomes invalid.

Parameters

it	Iterator of element to erase.

Returns: Iterator one position past (i.e., "older") than it, before *it was removed.

◆ erase() [2/3]

template<typename Key_t , typename Mapped_t , typename Hash_t , typename Pred_t >

Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::Iterator flow::util::Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::erase	(	const Const_iterator &	it_newest,
		const Const_iterator &	it_past_oldest
	)

Erases all elements in the range [it_newest, it_past_oldest).

Behavior undefined if a given iterator is invalid, or if the range is invalid. Corner case: an empty range is allowed; then this no-ops. Unless no-op, it_newest becomes invalid.

Parameters

it_newest	Iterator of first ("newest") element to erase.
it_past_oldest	Iterator of one past last ("oldest") element to erase.

Returns: it_past_oldest copy.

◆ erase() [3/3]

template<typename Key_t , typename Mapped_t , typename Hash_t , typename Pred_t >

Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::size_type flow::util::Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::erase ( const Key & key )

Erases the element with the given key, if it exists.

find(key) equivalent is performed first. Return value indicates whether it existed.

Parameters

key	Key such that its equal's (if found) element will be erased.

Returns: Number of elements erased (0 or 1).

◆ find() [1/2]

template<typename Key_t , typename Mapped_t , typename Hash_t , typename Pred_t >

Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::Iterator flow::util::Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::find ( const Key & key )

Attempts to find value at the given key in the map.

Key presence is determined identically to how it would be done in an unordered_set<Key, Hash, Pred>, with the particular Hash and Pred instances given to ctor (typically their default-cted instances, typically occupying no memory).

The returned iterator (if valid) can be used to mutate the element inside the map; though only the Mapped is mutable; the const Key is immutable.

Any subsequent writes to the referred-to (by returned iterator) area of memory will NOT have the effect of touch(). If you need it call touch() yourself.

Parameters

key	Key whose equal to find.

Returns: If found, iterator to the key/mapped-value pair with the equivalent key; else this->end().

◆ find() [2/2]

template<typename Key_t , typename Mapped_t , typename Hash_t , typename Pred_t >

Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::Const_iterator flow::util::Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::find ( const Key & key ) const

Identical to the other overload but in a const context: the returned iterator is to immutable memory.

Parameters

key	Key whose equal to find.

Returns: If found, iterator to the key/mapped-value pair with the equivalent key; else this->cend().

◆ insert() [1/2]

template<typename Key_t , typename Mapped_t , typename Hash_t , typename Pred_t >

std::pair< typename Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::Iterator, bool > flow::util::Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::insert ( const Value & key_and_mapped )

Attempts to insert (copying both key and mapped-value) the given key/mapped-value pair into the map; if key already in *this makes no change.

See also the overload which can avoid a copy and destructively move the key and mapped-value instead.

Return value indicates various info of interest about what occurred or did not occur. If inserted, the new element is considered "newest," as if by touch(). If not inserted, the existing element location is not affected (use touch() upon consulting the return value, if this is desirable).

Parameters

key_and_mapped The key/mapped-value pair to attempt to insert. A copy of this value is placed in *this.

Returns: A pair whose second element is true if and only if the insertion occurred; and whose first element is an iterator pointing to either the newly inserted element or already present one with a key equal to key_and_mapped.first.

◆ insert() [2/2]

template<typename Key_t , typename Mapped_t , typename Hash_t , typename Pred_t >

std::pair< typename Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::Iterator, bool > flow::util::Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::insert ( Value_movable && key_and_mapped )

Identical to the other overload, except that (if key not already present in *this) the key and mapped-value are moved, not copied, into *this.

Note: key_and_mapped pointee must be of type Value_movable, a/k/a pair<Key, Mapped> – not Value, a/k/a pair<const Key, Mapped> – otherwise the other insert() overload may get invoked, and copying may occur contrary to your intention. E.g., use std::make_pair<Key, Mapped>() or "decltype(*this)::Value_movable{}". (For a move to occur, the source-object can't be const; so that's why.); You can often also use x[std::move(key)] = std::move(value), particularly if you know key isn't in there, or you are OK with replacing the value if it is. In those cases it's probably more convenient, no pairs or Value_movables to worry oneself.

Parameters

key_and_mapped The key/mapped-value pair to attempt to insert (both key and mapped-value are moved-from, if insertion occurs).

Returns: See other overload.

◆ max_size()

template<typename Key_t , typename Mapped_t , typename Hash_t , typename Pred_t >

Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::size_type flow::util::Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::max_size

Returns max number of elements that can be stored.

Same performance as of unordered_set<> + list<>.

Returns: Ditto.

◆ newest()

template<typename Key_t , typename Mapped_t , typename Hash_t , typename Pred_t >

Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::Iterator flow::util::Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::newest

Returns first, a/k/a "newest," element's iterator; or past_oldest() if empty().

Returns: Ditto.

◆ oldest()

template<typename Key_t , typename Mapped_t , typename Hash_t , typename Pred_t >

Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::Reverse_iterator flow::util::Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::oldest

Returns first, a/k/a "oldest," element's reverse iterator.

Returns: Ditto.

◆ operator=() [1/2]

template<typename Key_t , typename Mapped_t , typename Hash_t , typename Pred_t >

Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t > & flow::util::Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::operator= ( const Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t > & src )

Overwrites this object with a copy of the given source.

We become equal to src but independent of it to a common-sense extent. In addition, the hasher instance and equality predicate are copied from src. Finally, a reasonable attempt is made to also make the internal structure of the hash map to be similar to that of `src.

Parameters

src	Source object. No-op if `this == &src`.

Returns: *this.

◆ operator=() [2/2]

template<typename Key_t , typename Mapped_t , typename Hash_t , typename Pred_t >

Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t > & flow::util::Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::operator= ( Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t > && src )

Overwrites this object making it identical to the given source, while the given source becomes as-if default-cted.

This is a constant-time operation, plus whatever is the cost of this->clear() (linear in pre-op .size()).

Parameters

src	Source object which is emptied; except no-op if `this == &src`.

Returns: *this.

◆ operator[]() [1/2]

template<typename Key_t , typename Mapped_t , typename Hash_t , typename Pred_t >

Mapped_t & flow::util::Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::operator[] ( const Key & key )

Either finds the Mapped value at the given key, or if not found inserts one with a default-constructed Mapped{}; then returns reference to the Mapped.

That ref can be used to read and/or modify that value directly. See also the overload which can avoid a copy and destructively move the key instead.

If inserted, the new element is considered "newest," as if by touch(). If not inserted, the existing element location is not affected.

So it is ~equivalent to

(key is in map) return this->find(key)->second; or
(otherwise) return this->insert(key, Mapped{}).first->second.

As long as the value is not removed from the map, the reference will continue to be valid.

Any subsequent writes to the referred-to area of memory will NOT have the effect of touch(). If you need it call touch() yourself.

Parameters

key	Key whose equal to find or insert if not found. A copy of this value is placed in `*this`.

Returns: Reference to mutable Mapped value directly inside the data structure.

◆ operator[]() [2/2]

template<typename Key_t , typename Mapped_t , typename Hash_t , typename Pred_t >

Mapped_t & flow::util::Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::operator[] ( Key && key )

Identical to the other overload, except that (if key not already present in *this) the key is moved, not copied, into *this.

Parameters

key	The key to attempt to insert (key is moved-from, if insertion occurs).

Returns: See other overload.

◆ past_newest()

template<typename Key_t , typename Mapped_t , typename Hash_t , typename Pred_t >

Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::Reverse_iterator flow::util::Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::past_newest

Returns one past last, a/k/a "newest," element's reverse iterator.

Returns: Ditto.

◆ past_oldest()

template<typename Key_t , typename Mapped_t , typename Hash_t , typename Pred_t >

Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::Iterator flow::util::Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::past_oldest

Returns special iterator indicating the position just past the iteration order; if not empty() this is one past last, a/k/a "oldest," element in the iteration order.

Returns: Ditto.

◆ rbegin()

template<typename Key_t , typename Mapped_t , typename Hash_t , typename Pred_t >

Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::Reverse_iterator flow::util::Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::rbegin

Synonym of oldest().

Returns: See oldest().

◆ rend()

template<typename Key_t , typename Mapped_t , typename Hash_t , typename Pred_t >

Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::Reverse_iterator flow::util::Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::rend

Synonym of past_newest().

Exists as standard container method.

Returns: See past_newest().

◆ size()

template<typename Key_t , typename Mapped_t , typename Hash_t , typename Pred_t >

Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::size_type flow::util::Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::size

Returns number of elements stored.

Same performance as of unordered_set<>.

Returns: Ditto.

◆ swap()

template<typename Key_t , typename Mapped_t , typename Hash_t , typename Pred_t >

void flow::util::Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::swap ( Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t > & other )

Swaps the contents of this structure and other.

This is a constant-time operation, as internal representations are swapped instead of any copy-assignment.

See also: The swap() free function. It is generally best (equivalent but covers more generic cases) to use the ADL-enabled swap(a, b) pattern instead of this member function. That is: using std::swap; ...; swap(a, b);. (Details are outside our scope here; but in short ADL will cause the right thing to happen.)

Parameters

other The other structure.

◆ touch() [1/2]

template<typename Key_t , typename Mapped_t , typename Hash_t , typename Pred_t >

void flow::util::Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::touch ( const Const_iterator & it )

Given a valid iterator into the structure, makes the pointed-to element "newest" by moving it from wherever it is to be first in the iteration order.

Behavior undefined if iterator invalid.

The iterator continues to be valid.

Parameters

it	Iterator to an element of the structure.

◆ touch() [2/2]

template<typename Key_t , typename Mapped_t , typename Hash_t , typename Pred_t >

bool flow::util::Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::touch ( const Key & key )

Given a key into the structure, makes the corresponding element "newest" by moving it from wherever it is to be first in the iteration order; or does nothing if no such key.

find(key) equivalent is performed first. Return value indicates whether it was found.

Parameters

key	Key whose equal to find.

Returns: true if the key was found (even if it was already "newest"); false if not found.

Friends And Related Function Documentation

◆ swap()

template<typename Key_t , typename Mapped_t , typename Hash_t , typename Pred_t >

void swap	(	Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t > &	val1,
		Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t > &	val2
	)

Parameters

val1	Object.
val2	Object.

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

util/linked_hash_map.hpp
util/util_fwd.hpp

Public Types

Public Member Functions

Related Functions

Detailed Description

Thread safety

Constructor & Destructor Documentation

◆ Linked_hash_map() [1/4]

◆ Linked_hash_map() [2/4]

◆ Linked_hash_map() [3/4]

◆ Linked_hash_map() [4/4]

Member Function Documentation

◆ begin() [1/2]

◆ begin() [2/2]

◆ cbegin()

◆ cend()

◆ const_newest()

◆ const_oldest()

◆ const_past_newest()

◆ const_past_oldest()

◆ count()

◆ crbegin()

◆ crend()

◆ empty()

◆ end() [1/2]

◆ end() [2/2]

◆ erase() [1/3]

◆ erase() [2/3]

◆ erase() [3/3]

◆ find() [1/2]

◆ find() [2/2]

◆ insert() [1/2]

◆ insert() [2/2]

◆ max_size()

◆ newest()

◆ oldest()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ operator[]() [1/2]

◆ operator[]() [2/2]

◆ past_newest()

◆ past_oldest()

◆ rbegin()

◆ rend()

◆ size()

◆ swap()

◆ touch() [1/2]

◆ touch() [2/2]

Friends And Related Function Documentation

◆ swap()