Unique-key hash map stored on Base's heap. More...
#include <StormByte/safe/unordered_map.hxx>
Classes | |
| class | BasicIterator |
| Forward cursor over Base-owned hash nodes. More... | |
| class | node_type |
| Owning handle to one extracted Base node. More... | |
| struct | insert_return_type |
| Result of inserting an extracted node. More... | |
Public Types | |
| using | key_type = K |
| Key type. | |
| using | mapped_type = V |
| Mapped type. | |
| using | value_type = Pair<const K, V> |
| Entry type. The key is immutable. | |
| using | hasher = Hash |
| Key hash. | |
| using | key_equal = KeyEqual |
| Key equality. | |
| using | size_type = Size |
| Element count. Size, not std::size_t. | |
| using | difference_type = std::ptrdiff_t |
| Iterator distance type. | |
| using | reference = value_type& |
| Mutable entry reference. | |
| using | const_reference = const value_type& |
| Read-only entry reference. | |
| using | iterator = BasicIterator<false> |
| Mutable iterator. | |
| using | const_iterator = BasicIterator<true> |
| Read-only iterator. | |
| using | insert_result = Pair<iterator, bool> |
| Iterator to the entry and whether it was inserted. | |
Public Member Functions | |
| UnorderedMap () noexcept | |
| Construct an empty map. | |
| UnorderedMap (size_type buckets, const Hash &hash=Hash(), const KeyEqual &equal=KeyEqual()) | |
| Construct an empty map with a bucket count and predicates. | |
| UnorderedMap (const UnorderedMap &other) | |
| Copy every node into new Base blocks. | |
| UnorderedMap (UnorderedMap &&other) noexcept | |
| Take the table. | |
| ~UnorderedMap () noexcept | |
| Destroy every node and the bucket array through Base. | |
| UnorderedMap & | operator= (const UnorderedMap &other) |
| Copy-assign. | |
| UnorderedMap & | operator= (UnorderedMap &&other) noexcept |
| Move-assign. | |
| STORMBYTE_FORCE_INLINE | UnorderedMap (const std::unordered_map< K, V > &other) |
| Copy a caller-owned STL map. | |
| STORMBYTE_FORCE_INLINE | UnorderedMap (std::unordered_map< K, V > &&other) |
| Move elements from a caller-owned STL map and leave it empty. | |
| template<std::ranges::input_range R> requires std::convertible_to<std::ranges::range_reference_t<R>, value_type> | |
| STORMBYTE_FORCE_INLINE | UnorderedMap (std::from_range_t, R &&range) |
Copy the entries of range. | |
| UnorderedMap (std::initializer_list< value_type > values) | |
| Insert every entry of an initializer list. | |
| UnorderedMap & | operator= (std::initializer_list< value_type > values) |
| Replace the contents with an initializer list. | |
| iterator | begin () noexcept |
| Return the first occupied node. | |
| iterator | end () noexcept |
| Return the past-the-end iterator. | |
| const_iterator | begin () const noexcept |
| Return the first occupied node. | |
| const_iterator | end () const noexcept |
| Return the past-the-end iterator. | |
| const_iterator | cbegin () const noexcept |
| Return the first occupied node. | |
| const_iterator | cend () const noexcept |
| Return the past-the-end iterator. | |
| bool | empty () const noexcept |
| Test whether the map holds no entries. | |
| size_type | size () const noexcept |
| Return the entry count. | |
| size_type | max_size () const noexcept |
| Return the maximum entry count this map can report. | |
| void | clear () noexcept |
| Destroy every entry. | |
| insert_result | insert (const value_type &value) |
Insert a copy of value when the key is absent. | |
| insert_result | insert (value_type &&value) |
Insert a moved value when the key is absent. | |
| void | insert (std::initializer_list< value_type > values) |
| Insert every entry of an initializer list. | |
| template<std::ranges::input_range R> requires std::convertible_to<std::ranges::range_reference_t<R>, value_type> | |
| STORMBYTE_FORCE_INLINE void | insert_range (R &&range) |
Insert every entry of range. | |
| template<class... Args> | |
| insert_result | emplace (Args &&... args) |
| Construct an entry in place when the key is absent. | |
| template<class... Args> | |
| insert_result | try_emplace (const K &key, Args &&... args) |
| Construct the mapped value in place when the key is absent. | |
| insert_result | insert_or_assign (const K &key, V mapped) |
| Insert or replace the mapped value. | |
| iterator | erase (const_iterator position) |
Erase the entry at position. | |
| size_type | erase (const K &key) |
Erase the entry with key. | |
| node_type | extract (const_iterator position) |
Unlink the entry at position. | |
| node_type | extract (const K &key) |
Unlink the entry with key. | |
| insert_return_type | insert (node_type &&node) |
| Link an extracted node. | |
| void | merge (UnorderedMap &other) |
Move entries whose keys are absent from other. | |
| void | swap (UnorderedMap &other) noexcept |
| Exchange tables. | |
| V & | at (const K &key) |
| Return the mapped value. | |
| const V & | at (const K &key) const |
| Return the mapped value. | |
| V & | operator[] (const K &key) |
| Return the mapped value, inserting a value-initialized one when absent. | |
| iterator | find (const K &key) |
| Find an entry. | |
| const_iterator | find (const K &key) const |
| Find an entry. | |
| size_type | count (const K &key) const |
Count entries with key. | |
| bool | contains (const K &key) const |
Test whether key is present. | |
| size_type | bucket_count () const noexcept |
| Return the bucket count. | |
| size_type | bucket_size (size_type index) const |
Return the number of entries in index. | |
| size_type | bucket (const K &key) const |
Return the bucket of key. | |
| float | load_factor () const noexcept |
| Return the current load factor. | |
| float | max_load_factor () const noexcept |
| Return the load factor that triggers a rehash. | |
| void | max_load_factor (float factor) noexcept |
| Set the load factor that triggers a rehash. | |
| void | rehash (size_type buckets) |
| Replace the bucket array. | |
| void | reserve (size_type count) |
Reserve room for count entries without exceeding the load factor. | |
| Hash | hash_function () const |
| Return the stored hash. | |
| KeyEqual | key_eq () const |
| Return the stored equality predicate. | |
| bool | operator== (const UnorderedMap &other) const |
| Compare entries by key and mapped value. | |
| STORMBYTE_FORCE_INLINE | operator std::unordered_map< K, V > () const |
| Copy the entries into caller-owned STL storage. | |
Unique-key hash map stored on Base's heap.
| K | Safe key type. It must be hashable by Hash. |
| V | Safe mapped type. |
| Hash | Cross-module hash. A stateless hash does not allocate. A stateful one is stored in the map and must itself be Safe. |
| KeyEqual | Key equality. A stateless predicate does not allocate. A stateful one is stored in the map and must itself be Safe. |
Nodes and the bucket array are allocated with Heap::Allocate. There is no allocator. Iterators are forward and point at Base nodes. A cursor keeps the map so it can leave an empty bucket. Dereference returns a real Pair reference. Public results are Pair, never std::pair. node_type owns a Base node. It is not std::unordered_map::node_type. extract unlinks that node. It does not copy it. The default hash is Hash, not std::hash. A conversion to or from std::unordered_map<K, V> copies the entries. It does not reuse the STL hasher.
| using StormByte::Safe::UnorderedMap< K, V, Hash, KeyEqual >::const_iterator = BasicIterator<true> |
Read-only iterator.
| using StormByte::Safe::UnorderedMap< K, V, Hash, KeyEqual >::const_reference = const value_type& |
Read-only entry reference.
| using StormByte::Safe::UnorderedMap< K, V, Hash, KeyEqual >::difference_type = std::ptrdiff_t |
Iterator distance type.
| using StormByte::Safe::UnorderedMap< K, V, Hash, KeyEqual >::hasher = Hash |
Key hash.
| using StormByte::Safe::UnorderedMap< K, V, Hash, KeyEqual >::insert_result = Pair<iterator, bool> |
Iterator to the entry and whether it was inserted.
| using StormByte::Safe::UnorderedMap< K, V, Hash, KeyEqual >::iterator = BasicIterator<false> |
Mutable iterator.
| using StormByte::Safe::UnorderedMap< K, V, Hash, KeyEqual >::key_equal = KeyEqual |
Key equality.
| using StormByte::Safe::UnorderedMap< K, V, Hash, KeyEqual >::key_type = K |
Key type.
| using StormByte::Safe::UnorderedMap< K, V, Hash, KeyEqual >::mapped_type = V |
Mapped type.
| using StormByte::Safe::UnorderedMap< K, V, Hash, KeyEqual >::reference = value_type& |
Mutable entry reference.
| using StormByte::Safe::UnorderedMap< K, V, Hash, KeyEqual >::size_type = Size |
Element count. Size, not std::size_t.
| using StormByte::Safe::UnorderedMap< K, V, Hash, KeyEqual >::value_type = Pair<const K, V> |
Entry type. The key is immutable.
|
noexcept |
Construct an empty map.
|
explicit |
Construct an empty map with a bucket count and predicates.
| buckets | Initial bucket count. Rounded up to a power of two. Zero selects the default. |
| hash | Key hash. |
| equal | Key equality. |
| AllocationError | The bucket array could not be allocated. |
| StormByte::Safe::UnorderedMap< K, V, Hash, KeyEqual >::UnorderedMap | ( | const UnorderedMap< K, V, Hash, KeyEqual > & | other | ) |
Copy every node into new Base blocks.
| other | Source. |
| AllocationError | A block could not be allocated. |
|
noexcept |
Take the table.
other is left empty.
| other | Source. |
|
noexcept |
Destroy every node and the bucket array through Base.
|
inlineexplicit |
Copy a caller-owned STL map.
Its state is unchanged. Its hasher is not reused.
| other | Source. |
| AllocationError | A block could not be allocated. |
|
inlineexplicit |
Move elements from a caller-owned STL map and leave it empty.
Its hasher is not reused.
| other | Source. Cleared before this function returns. |
| AllocationError | A block could not be allocated. |
|
inlineexplicit |
Copy the entries of range.
| R | Input range of value_type. |
| range | Source. Instantiated in the caller. |
| AllocationError | A block could not be allocated. |
| StormByte::Safe::UnorderedMap< K, V, Hash, KeyEqual >::UnorderedMap | ( | std::initializer_list< value_type > | values | ) |
Insert every entry of an initializer list.
| values | Entries. |
| AllocationError | A block could not be allocated. |
| V & StormByte::Safe::UnorderedMap< K, V, Hash, KeyEqual >::at | ( | const K & | key | ) |
Return the mapped value.
| key | Key. |
| OutOfBoundsError | The key is absent. |
| const V & StormByte::Safe::UnorderedMap< K, V, Hash, KeyEqual >::at | ( | const K & | key | ) | const |
Return the mapped value.
| key | Key. |
| OutOfBoundsError | The key is absent. |
|
noexcept |
Return the first occupied node.
|
noexcept |
Return the first occupied node.
| size_type StormByte::Safe::UnorderedMap< K, V, Hash, KeyEqual >::bucket | ( | const K & | key | ) | const |
Return the bucket of key.
| key | Key. |
|
inlinenoexcept |
Return the bucket count.
| size_type StormByte::Safe::UnorderedMap< K, V, Hash, KeyEqual >::bucket_size | ( | size_type | index | ) | const |
Return the number of entries in index.
| index | Bucket index. Not checked. |
|
inlinenoexcept |
Return the first occupied node.
|
inlinenoexcept |
Return the past-the-end iterator.
|
noexcept |
Destroy every entry.
The bucket array stays.
| bool StormByte::Safe::UnorderedMap< K, V, Hash, KeyEqual >::contains | ( | const K & | key | ) | const |
| size_type StormByte::Safe::UnorderedMap< K, V, Hash, KeyEqual >::count | ( | const K & | key | ) | const |
Count entries with key.
| key | Key. |
| insert_result StormByte::Safe::UnorderedMap< K, V, Hash, KeyEqual >::emplace | ( | Args &&... | args | ) |
Construct an entry in place when the key is absent.
| Args | Constructor argument types of value_type. |
| args | Arguments forwarded to value_type. |
| AllocationError | A node could not be allocated. |
|
inlinenoexcept |
Test whether the map holds no entries.
|
inlinenoexcept |
Return the past-the-end iterator.
|
inlinenoexcept |
Return the past-the-end iterator.
| size_type StormByte::Safe::UnorderedMap< K, V, Hash, KeyEqual >::erase | ( | const K & | key | ) |
Erase the entry with key.
| key | Key. |
| iterator StormByte::Safe::UnorderedMap< K, V, Hash, KeyEqual >::erase | ( | const_iterator | position | ) |
Erase the entry at position.
| position | Iterator to an entry. Not end. |
| node_type StormByte::Safe::UnorderedMap< K, V, Hash, KeyEqual >::extract | ( | const K & | key | ) |
Unlink the entry with key.
The node is not copied.
| key | Key. |
| node_type StormByte::Safe::UnorderedMap< K, V, Hash, KeyEqual >::extract | ( | const_iterator | position | ) |
Unlink the entry at position.
The node is not copied.
| position | Iterator to an entry. Not end. |
| iterator StormByte::Safe::UnorderedMap< K, V, Hash, KeyEqual >::find | ( | const K & | key | ) |
| const_iterator StormByte::Safe::UnorderedMap< K, V, Hash, KeyEqual >::find | ( | const K & | key | ) | const |
|
inline |
Return the stored hash.
| insert_result StormByte::Safe::UnorderedMap< K, V, Hash, KeyEqual >::insert | ( | const value_type & | value | ) |
Insert a copy of value when the key is absent.
| value | Entry. |
| AllocationError | A node could not be allocated. |
| insert_return_type StormByte::Safe::UnorderedMap< K, V, Hash, KeyEqual >::insert | ( | node_type && | node | ) |
Link an extracted node.
A duplicate key is returned in the result.
| node | Handle. Left empty when inserted. |
| AllocationError | The bucket array could not grow. |
| void StormByte::Safe::UnorderedMap< K, V, Hash, KeyEqual >::insert | ( | std::initializer_list< value_type > | values | ) |
Insert every entry of an initializer list.
| values | Entries. |
| AllocationError | A node could not be allocated. |
| insert_result StormByte::Safe::UnorderedMap< K, V, Hash, KeyEqual >::insert | ( | value_type && | value | ) |
Insert a moved value when the key is absent.
| value | Entry. |
| AllocationError | A node could not be allocated. |
| insert_result StormByte::Safe::UnorderedMap< K, V, Hash, KeyEqual >::insert_or_assign | ( | const K & | key, |
| V | mapped ) |
Insert or replace the mapped value.
| key | Key. |
| mapped | Mapped value. |
| AllocationError | A node could not be allocated. |
|
inline |
Insert every entry of range.
| R | Input range of value_type. |
| range | Source. Instantiated in the caller. |
| AllocationError | A node could not be allocated. |
|
inline |
Return the stored equality predicate.
|
noexcept |
Return the current load factor.
|
inlinenoexcept |
Return the load factor that triggers a rehash.
|
inlinenoexcept |
Set the load factor that triggers a rehash.
| factor | Maximum load factor. Not checked. |
|
inlinenoexcept |
Return the maximum entry count this map can report.
| void StormByte::Safe::UnorderedMap< K, V, Hash, KeyEqual >::merge | ( | UnorderedMap< K, V, Hash, KeyEqual > & | other | ) |
Move entries whose keys are absent from other.
| other | Source. Extracted nodes are unlinked, not copied. |
| AllocationError | The bucket array could not grow. |
|
inlineexplicit |
Copy the entries into caller-owned STL storage.
The STL hasher is std::hash.
| UnorderedMap & StormByte::Safe::UnorderedMap< K, V, Hash, KeyEqual >::operator= | ( | const UnorderedMap< K, V, Hash, KeyEqual > & | other | ) |
Copy-assign.
The previous table is released only after the copy exists.
| other | Source. |
| AllocationError | A block could not be allocated. |
| UnorderedMap & StormByte::Safe::UnorderedMap< K, V, Hash, KeyEqual >::operator= | ( | std::initializer_list< value_type > | values | ) |
Replace the contents with an initializer list.
| values | Entries. |
| AllocationError | A block could not be allocated. |
|
noexcept |
Move-assign.
other is left empty.
| other | Source. |
| bool StormByte::Safe::UnorderedMap< K, V, Hash, KeyEqual >::operator== | ( | const UnorderedMap< K, V, Hash, KeyEqual > & | other | ) | const |
Compare entries by key and mapped value.
Order does not matter.
| other | Map to compare. |
| V & StormByte::Safe::UnorderedMap< K, V, Hash, KeyEqual >::operator[] | ( | const K & | key | ) |
Return the mapped value, inserting a value-initialized one when absent.
| key | Key. |
| AllocationError | A node could not be allocated. |
| void StormByte::Safe::UnorderedMap< K, V, Hash, KeyEqual >::rehash | ( | size_type | buckets | ) |
Replace the bucket array.
Entries are relinked, not copied.
| buckets | New bucket count. Rounded up to a power of two. |
| AllocationError | The new bucket array could not be allocated. |
| void StormByte::Safe::UnorderedMap< K, V, Hash, KeyEqual >::reserve | ( | size_type | count | ) |
Reserve room for count entries without exceeding the load factor.
| count | Entry count to accommodate. |
| AllocationError | The bucket array could not be allocated. |
|
inlinenoexcept |
Return the entry count.
|
noexcept |
| insert_result StormByte::Safe::UnorderedMap< K, V, Hash, KeyEqual >::try_emplace | ( | const K & | key, |
| Args &&... | args ) |
Construct the mapped value in place when the key is absent.
| Args | Mapped constructor argument types. |
| key | Key. |
| args | Arguments forwarded to V. |
| AllocationError | A node could not be allocated. |