|
Flow 2.0.0
Flow project: Full implementation reference.
|
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. More... | |
| using | Mapped = Mapped_t |
| Convenience alias for template arg. More... | |
| using | Hash = Hash_t |
| Convenience alias for template arg. More... | |
| using | Pred = Pred_t |
| Convenience alias for template arg. More... | |
| using | Value = std::pair< Key const, Mapped > |
| Short-hand for key/mapped-value pairs stored in the structure. More... | |
| 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. More... | |
| using | size_type = std::size_t |
| Expresses sizes/lengths of relevant things. More... | |
| using | difference_type = std::ptrdiff_t |
Type for difference of size_types. More... | |
| using | Iterator = typename Value_list::iterator |
| Type for iterator pointing into a mutable structure of this type. More... | |
| using | Const_iterator = typename Value_list::const_iterator |
| Type for iterator pointing into an immutable structure of this type. More... | |
| using | Reverse_iterator = typename Value_list::reverse_iterator |
| Type for reverse iterator pointing into a mutable structure of this type. More... | |
| using | Const_reverse_iterator = typename Value_list::const_reverse_iterator |
| Type for reverse iterator pointing into an immutable structure of this type. More... | |
| using | key_type = Key |
| For container compliance (hence the irregular capitalization): Key type. More... | |
| using | mapped_type = Mapped |
| For container compliance (hence the irregular capitalization): Mapped type. More... | |
| using | value_type = Value |
| For container compliance (hence the irregular capitalization): Key/Mapped pair type. More... | |
| using | hasher = Hash |
| For container compliance (hence the irregular capitalization): Hash type. More... | |
| using | key_equal = Pred |
| For container compliance (hence the irregular capitalization): Pred type. More... | |
| using | pointer = Value * |
| For container compliance (hence the irregular capitalization): pointer to Key/Mapped pair type. More... | |
| using | const_pointer = const Value * |
For container compliance (hence the irregular capitalization): pointer to const Key/Mapped pair type. More... | |
| using | reference = Value & |
| For container compliance (hence the irregular capitalization): reference to Key/Mapped pair type. More... | |
| using | const_reference = const Value & |
For container compliance (hence the irregular capitalization): reference to const Key/Mapped pair type. More... | |
| using | iterator = Iterator |
| For container compliance (hence the irregular capitalization): Iterator type. More... | |
| using | const_iterator = Const_iterator |
| For container compliance (hence the irregular capitalization): Const_iterator type. More... | |
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. More... | |
| 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... | |
Private Types | |
| using | Value_list = std::list< Value > |
| Short-hand for doubly linked list of (Key, Mapped) pairs. More... | |
Private Member Functions | |
| Iterator | insert_impl (const Value &key_and_mapped) |
Helper that modifies m_value_list and m_value_iter_set so that key_and_mapped's copy is inserted into the structure. More... | |
| Iterator | insert_impl_mv (Value_movable &&key_and_mapped) |
Similar to insert_impl(), except key_and_mapped components are move()d into *this instead of being copied. More... | |
Private Attributes | |
| Value_list | m_value_list |
The actual values – which, as in unordered_map<K, M>, are instances of Value = pair<const Key, Mapped> – are stored in here, in the order in which user would iterate over them. More... | |
| Linked_hash_key_set< Key, Iterator, Hash, Pred, true > | m_value_iter_set |
Data structure that allows the amortized-constant-time (as in unordered_set) implementation of this->find(key), where key is const Key&. 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... | |
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>(..., ...));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.
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.)Same as for unordered_map<>.
You should get much of what you need to grok this just by reading the above and possibly looking at the Data section doc-headers under private:. Essentially, to repeat/recap: there's the list<pair<const Key, Mapped>> to store the actual values, in order (m_value_list); Iterator and Const_iterator come directly from there.
When lookup by Key is needed, the unordered_set m_value_iter_set comes into play. This is arguably the only real mechanical trickiness. It actually stores Iterators into m_value_list but in such a way as to allow seamless lookup from a mere const Key&; so m_value_iter_set.find(key) "magically" either finds .end() – then the key is not in *this – or the iterator into the actual key/mapped-value store in m_value_list. Using m_value_iter_set is easy; but a bit of internal infrastructure is necessary to have it work. Namely we have support class template Linked_hash_key<Key, Iterator>, and the unordered_set m_value_iter_set actually stores those guys, not raw Key copies; so it is a wrapper around an Iterator or a Key (union-style). m_value_iter_set stores Iterator wrappers, while lookup attempts use the Key wrapper form to pass into m_value_iter_set.find().
An earlier version of Linked_hash_map instead used a simple unordered_map<Key, Iterator> instead of the unordered_set<Linked_hash_key<Key, Iterator>>; so a lookup by key was just that. Eventually we replaced it with the more complex solution simply to avoid storing 2 copies of each Key (one in the list, one in the map); as the Iterator itself includes a pointer to the thing containing the corresponding Key in the first place. So this saves memory as well as various Key copying.
| 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 Keys) determines equality or lack thereof. |
Definition at line 117 of file linked_hash_map.hpp.
| using flow::util::Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::Const_iterator = typename Value_list::const_iterator |
Type for iterator pointing into an immutable structure of this type.
Definition at line 159 of file linked_hash_map.hpp.
| using flow::util::Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::const_iterator = Const_iterator |
For container compliance (hence the irregular capitalization): Const_iterator type.
Definition at line 188 of file linked_hash_map.hpp.
| using flow::util::Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::const_pointer = const Value* |
For container compliance (hence the irregular capitalization): pointer to const Key/Mapped pair type.
Definition at line 180 of file linked_hash_map.hpp.
| using flow::util::Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::const_reference = const Value& |
For container compliance (hence the irregular capitalization): reference to const Key/Mapped pair type.
Definition at line 184 of file linked_hash_map.hpp.
| using flow::util::Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::Const_reverse_iterator = typename Value_list::const_reverse_iterator |
Type for reverse iterator pointing into an immutable structure of this type.
Definition at line 165 of file linked_hash_map.hpp.
| using flow::util::Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::difference_type = std::ptrdiff_t |
Type for difference of size_types.
Definition at line 153 of file linked_hash_map.hpp.
| using flow::util::Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::Hash = Hash_t |
Convenience alias for template arg.
Definition at line 129 of file linked_hash_map.hpp.
| using flow::util::Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::hasher = Hash |
For container compliance (hence the irregular capitalization): Hash type.
Definition at line 174 of file linked_hash_map.hpp.
| using flow::util::Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::Iterator = typename Value_list::iterator |
Type for iterator pointing into a mutable structure of this type.
Definition at line 156 of file linked_hash_map.hpp.
| using flow::util::Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::iterator = Iterator |
For container compliance (hence the irregular capitalization): Iterator type.
Definition at line 186 of file linked_hash_map.hpp.
| using flow::util::Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::Key = Key_t |
Convenience alias for template arg.
Definition at line 123 of file linked_hash_map.hpp.
| using flow::util::Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::key_equal = Pred |
For container compliance (hence the irregular capitalization): Pred type.
Definition at line 176 of file linked_hash_map.hpp.
| using flow::util::Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::key_type = Key |
For container compliance (hence the irregular capitalization): Key type.
Definition at line 168 of file linked_hash_map.hpp.
| using flow::util::Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::Mapped = Mapped_t |
Convenience alias for template arg.
Definition at line 126 of file linked_hash_map.hpp.
| using flow::util::Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::mapped_type = Mapped |
For container compliance (hence the irregular capitalization): Mapped type.
Definition at line 170 of file linked_hash_map.hpp.
| using flow::util::Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::pointer = Value* |
For container compliance (hence the irregular capitalization): pointer to Key/Mapped pair type.
Definition at line 178 of file linked_hash_map.hpp.
| using flow::util::Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::Pred = Pred_t |
Convenience alias for template arg.
Definition at line 132 of file linked_hash_map.hpp.
| using flow::util::Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::reference = Value& |
For container compliance (hence the irregular capitalization): reference to Key/Mapped pair type.
Definition at line 182 of file linked_hash_map.hpp.
| using flow::util::Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::Reverse_iterator = typename Value_list::reverse_iterator |
Type for reverse iterator pointing into a mutable structure of this type.
Definition at line 162 of file linked_hash_map.hpp.
| using flow::util::Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::size_type = std::size_t |
Expresses sizes/lengths of relevant things.
Definition at line 151 of file linked_hash_map.hpp.
| using flow::util::Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::Value = std::pair<Key const, Mapped> |
Short-hand for key/mapped-value pairs stored in the structure.
Definition at line 135 of file linked_hash_map.hpp.
|
private |
Short-hand for doubly linked list of (Key, Mapped) pairs.
Definition at line 144 of file linked_hash_map.hpp.
| using flow::util::Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::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.
Definition at line 138 of file linked_hash_map.hpp.
| using flow::util::Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::value_type = Value |
For container compliance (hence the irregular capitalization): Key/Mapped pair type.
Definition at line 172 of file linked_hash_map.hpp.
| 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.
| 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 Keys are equal by value). |
Definition at line 666 of file linked_hash_map.hpp.
|
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.
| 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. |
Definition at line 675 of file linked_hash_map.hpp.
References flow::util::Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::m_value_iter_set, and flow::util::Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::m_value_list.
| 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).
| src | Source object. |
Definition at line 698 of file linked_hash_map.hpp.
| 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.
| src | Source object which is emptied. |
Definition at line 705 of file linked_hash_map.hpp.
| 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().
Definition at line 976 of file linked_hash_map.hpp.
Referenced by flow::util::Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::insert_impl(), flow::util::Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::insert_impl_mv(), and flow::util::Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::newest().
| 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).
Definition at line 1011 of file linked_hash_map.hpp.
| 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).
Definition at line 1004 of file linked_hash_map.hpp.
Referenced by flow::util::Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::const_newest().
| 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).
Definition at line 1025 of file linked_hash_map.hpp.
Referenced by flow::util::Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::const_past_oldest().
| void flow::util::Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::clear |
Makes it so that size() == 0.
Definition at line 961 of file linked_hash_map.hpp.
References flow::util::Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::clear().
Referenced by flow::util::Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::clear().
| 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.
Definition at line 997 of file linked_hash_map.hpp.
References flow::util::Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::cbegin().
| 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).
Definition at line 1067 of file linked_hash_map.hpp.
References flow::util::Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::crbegin().
| 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.
Definition at line 1081 of file linked_hash_map.hpp.
References flow::util::Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::crend().
| 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.
Definition at line 1018 of file linked_hash_map.hpp.
References flow::util::Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::cend().
| 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.
| key | Key whose equal to find. |
Definition at line 894 of file linked_hash_map.hpp.
References flow::util::Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::count().
Referenced by flow::util::Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::count().
| 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().
Definition at line 1074 of file linked_hash_map.hpp.
Referenced by flow::util::Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::const_oldest().
| 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.
Definition at line 1088 of file linked_hash_map.hpp.
Referenced by flow::util::Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::const_past_newest().
| 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<>.
Definition at line 1101 of file linked_hash_map.hpp.
References flow::util::Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::empty().
Referenced by flow::util::Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::empty().
| 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.
Definition at line 990 of file linked_hash_map.hpp.
Referenced by flow::util::Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::past_oldest().
| 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).
Definition at line 1032 of file linked_hash_map.hpp.
| 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.
| it | Iterator of element to erase. |
it, before *it was removed. Definition at line 921 of file linked_hash_map.hpp.
References flow::util::Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::erase().
Referenced by flow::util::Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::erase().
| 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.
| it_newest | Iterator of first ("newest") element to erase. |
| it_past_oldest | Iterator of one past last ("oldest") element to erase. |
it_past_oldest copy. Definition at line 931 of file linked_hash_map.hpp.
References flow::util::Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::erase().
| 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.
| key | Key such that its equal's (if found) element will be erased. |
Definition at line 944 of file linked_hash_map.hpp.
References flow::util::Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::find().
| 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.
| key | Key whose equal to find. |
this->end(). Definition at line 878 of file linked_hash_map.hpp.
References flow::util::Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::find().
Referenced by flow::util::Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::erase(), flow::util::Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::find(), and 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 >::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.
| key | Key whose equal to find. |
this->cend(). Definition at line 886 of file linked_hash_map.hpp.
References flow::util::Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::find().
| 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).
| key_and_mapped | The key/mapped-value pair to attempt to insert. A copy of this value is placed in *this. |
key_and_mapped.first. Definition at line 800 of file linked_hash_map.hpp.
Referenced by flow::net_flow::Node::close_connection_immediately().
| 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.
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.) 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.| key_and_mapped | The key/mapped-value pair to attempt to insert (both key and mapped-value are moved-from, if insertion occurs). |
Definition at line 813 of file linked_hash_map.hpp.
|
private |
Helper that modifies m_value_list and m_value_iter_set so that key_and_mapped's copy is inserted into the structure.
Pre-condition is that key_and_mapped.first is not in the structure (else behavior undefined).
| key_and_mapped | Same as in insert(). |
insert().first. Definition at line 849 of file linked_hash_map.hpp.
References flow::util::Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::begin().
|
private |
Similar to insert_impl(), except key_and_mapped components are move()d into *this instead of being copied.
| key_and_mapped | Same as in insert(). |
insert().first. Definition at line 865 of file linked_hash_map.hpp.
References flow::util::Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::begin().
| 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<>.
Definition at line 1108 of file linked_hash_map.hpp.
| 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().
Definition at line 969 of file linked_hash_map.hpp.
References flow::util::Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::begin().
| 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.
Definition at line 1039 of file linked_hash_map.hpp.
References flow::util::Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::rbegin().
| 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.
| src | Source object. No-op if this == &src. |
*this. Definition at line 713 of file linked_hash_map.hpp.
References flow::util::Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::m_value_iter_set, and flow::util::Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::m_value_list.
| 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()).
| src | Source object which is emptied; except no-op if this == &src. |
*this. Definition at line 778 of file linked_hash_map.hpp.
References flow::util::swap().
| 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; orreturn 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.
| key | Key whose equal to find or insert if not found. A copy of this value is placed in *this. |
Definition at line 825 of file linked_hash_map.hpp.
| 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.
| key | The key to attempt to insert (key is moved-from, if insertion occurs). |
Definition at line 836 of file linked_hash_map.hpp.
References flow::util::Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::find().
| 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.
Definition at line 1053 of file linked_hash_map.hpp.
References flow::util::Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::rend().
| 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.
Definition at line 983 of file linked_hash_map.hpp.
References flow::util::Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::end().
| 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().
Definition at line 1046 of file linked_hash_map.hpp.
Referenced by flow::util::Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::oldest().
| 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.
Definition at line 1060 of file linked_hash_map.hpp.
Referenced by flow::util::Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::past_newest().
| 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<>.
Definition at line 1095 of file linked_hash_map.hpp.
References flow::util::Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::size().
Referenced by flow::net_flow::Event_set::ev_type_to_socks_map_sizes_to_str(), and flow::util::Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::size().
| 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.
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.)| other | The other structure. |
Definition at line 789 of file linked_hash_map.hpp.
References flow::util::Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::m_value_iter_set, flow::util::Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::m_value_list, and flow::util::swap().
Referenced by flow::util::Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::swap().
| 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.
| it | Iterator to an element of the structure. |
Definition at line 900 of file linked_hash_map.hpp.
| 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.
| key | Key whose equal to find. |
true if the key was found (even if it was already "newest"); false if not found. Definition at line 906 of file linked_hash_map.hpp.
|
related |
Equivalent to val1.swap(val2).
| val1 | Object. |
| val2 | Object. |
Definition at line 1114 of file linked_hash_map.hpp.
References flow::util::Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::swap().
|
private |
Data structure that allows the amortized-constant-time (as in unordered_set) implementation of this->find(key), where key is const Key&.
Namely, then, given a Key, it gets us an Iterator into m_value_list – the central data store – or a null iterator if not-found.
(There is quick intro in Impl section of the class doc header.) Ignoring various technicalities and C++isms, ultimately it stores Iterators while supporting the find operation that
const Key& key; andit stored therein (if any) such that
This find-op must Hash the key; and then perform a (series of) Pred comparisons between key and the Keys stored at Iterators within that hash-bucket.
How this is accomplished is encapsulated inside Linked_hash_key_set, Linked_hash_key, Linked_hash_key_hash, and Linked_hash_key_pred helper (internally-used only) types. This is abstracted away; the bottom line is m_value_iter_set.find(key)->iter() yields the proper Iterator (assuming .find() didn't yield .end()).
Similarly m_value_iter_set.insert(iter) – where iter is an Iterator into m_value_list – just works.
Anything they'll need to do to this set (namely .find() and .insert()) carries the same performance cost as if they used a straight unordered_map<>, so by definition it is acceptable.
Definition at line 658 of file linked_hash_map.hpp.
Referenced by flow::util::Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::Linked_hash_map(), flow::util::Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::operator=(), and flow::util::Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::swap().
|
private |
The actual values – which, as in unordered_map<K, M>, are instances of Value = pair<const Key, Mapped> – are stored in here, in the order in which user would iterate over them.
If Value v is in this list, then no Value v1 == v can be elsewhere in the list. The order is semantically defined to be from "newest" to "oldest." Therefore, any newly inserted value goes at the start of the list. Similarly, any "touched" value is moved to the start of the list (see touch()).
This ordering is what a normal unordered_map<K, M> would not supply (it's in the name!) but that we advertise.
This is very much the central structure in a *this; its iterator type is our exposed Iterator. Straight-up, m_value_list supplies every single required operation (or at least ones on top of which any required ops could be implemented). There is exactly one exception to this: find(const Key&). It too could be implemented with m_value_list alone, but a linear search (linear-time worst- and average-case) would be necessary (unacceptable). Because of that we have m_value_iter_set. See that guy's doc header.
Moving a value from anywhere to either end of the list is a constant-time operation (assuming the source location's iterator is known). Hence touch() is constant-time. Moreover, touch() does not involve a copy of a Value (it only involves assigning, internally, a few linked list pointers). Also note that insertion is similarly constant-time. Finally, erasure is also constant-time. These are the basic operations needed.
Definition at line 630 of file linked_hash_map.hpp.
Referenced by flow::util::Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::Linked_hash_map(), flow::util::Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::operator=(), and flow::util::Linked_hash_map< Key_t, Mapped_t, Hash_t, Pred_t >::swap().
1.9.4