Unique values stored in a Base-heap hash table. More...
#include <StormByte/safe/unordered_set.hxx>
Classes | |
| class | iterator |
| Forward cursor. More... | |
| class | const_iterator |
| Read-only forward cursor. 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 |
| Value and lookup type. | |
| using | value_type = K |
| Stored value. | |
| using | hasher = Hash |
| Value hash. | |
| using | key_equal = KeyEqual |
| Value equality. | |
| using | size_type = Size |
| Element count. Size, not std::size_t. | |
| using | difference_type = std::ptrdiff_t |
| Iterator distance type. | |
| using | reference = const K& |
| Read-only value reference. | |
| using | const_reference = const K& |
| Read-only value reference. | |
| using | insert_result = Pair<iterator, bool> |
| Iterator to the value and whether it was inserted. | |
Public Member Functions | |
| UnorderedSet () noexcept | |
| Construct an empty set. | |
| UnorderedSet (size_type buckets, const Hash &hash=Hash(), const KeyEqual &equal=KeyEqual()) | |
| Construct an empty set with a bucket count and predicates. | |
| UnorderedSet (const UnorderedSet &other) | |
| Copy the values. | |
| UnorderedSet (UnorderedSet &&other) noexcept | |
| Take the table. | |
| ~UnorderedSet () | |
| Destroy the values. | |
| UnorderedSet & | operator= (const UnorderedSet &other) |
| Copy-assign the values. | |
| UnorderedSet & | operator= (UnorderedSet &&other) noexcept |
| Move-assign the table. | |
| UnorderedSet & | operator= (std::initializer_list< K > values) |
| Replace the contents with an initializer list. | |
| template<class InputIt> | |
| UnorderedSet (InputIt first, InputIt last) | |
| Construct from an iterator range. | |
| template<class InputIt> | |
| UnorderedSet (InputIt first, InputIt last, size_type buckets, const Hash &hash=Hash(), const KeyEqual &equal=KeyEqual()) | |
| Construct from an iterator range, a bucket count and predicates. | |
| UnorderedSet (std::initializer_list< K > values) | |
| Construct from an initializer list. | |
| UnorderedSet (std::initializer_list< K > values, size_type buckets, const Hash &hash=Hash(), const KeyEqual &equal=KeyEqual()) | |
| Construct from an initializer list, a bucket count and predicates. | |
| STORMBYTE_FORCE_INLINE | UnorderedSet (const std::unordered_set< K > &other) |
| Copy a caller-owned STL set. | |
| STORMBYTE_FORCE_INLINE | UnorderedSet (std::unordered_set< K > &&other) |
| Move values from a caller-owned STL set and leave it empty. | |
| hasher | hash_function () const |
| Return the stored hash. | |
| key_equal | key_eq () const |
| Return the stored equality predicate. | |
| iterator | begin () noexcept |
| Return an iterator to the first occupied node. | |
| const_iterator | begin () const noexcept |
| Return an iterator to the first occupied node. | |
| const_iterator | cbegin () const noexcept |
| Return an iterator to the first occupied node. | |
| iterator | end () noexcept |
| Return the past-the-end iterator. | |
| const_iterator | end () const noexcept |
| Return the past-the-end iterator. | |
| const_iterator | cend () const noexcept |
| Return the past-the-end iterator. | |
| bool | empty () const noexcept |
| Test whether the set has no values. | |
| size_type | size () const noexcept |
| Return the number of values. | |
| size_type | max_size () const noexcept |
| Return the maximum number of values. | |
| void | clear () noexcept |
| Destroy every value. | |
| insert_result | insert (const K &value) |
| Insert a value if it is absent. | |
| insert_result | insert (K &&value) |
| Insert a value if it is absent. | |
| iterator | insert (const_iterator hint, const K &value) |
| Insert a value. | |
| iterator | insert (const_iterator hint, K &&value) |
| Insert a value. | |
| template<class InputIt> | |
| void | insert (InputIt first, InputIt last) |
| Insert every value in [first, last). | |
| void | insert (std::initializer_list< K > values) |
| Insert every value 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 a copy of range. | |
| template<class... Args> | |
| insert_result | emplace (Args &&... args) |
| Construct a value in a new node if it is absent. | |
| template<class... Args> | |
| iterator | emplace_hint (const_iterator hint, Args &&... args) |
| Construct a value. | |
| insert_return_type | insert (node_type &&handle) |
| Insert an extracted node if its value is absent. | |
| iterator | insert (const_iterator hint, node_type &&handle) |
| Insert an extracted node. | |
| node_type | extract (const_iterator position) |
Unlink the value at position and return that node. | |
| node_type | extract (const K &value) |
Unlink value and return that node. | |
| template<class OtherHash, class OtherEqual> | |
| void | merge (UnorderedSet< K, OtherHash, OtherEqual > &source) |
Take unique values from source. | |
| iterator | erase (iterator position) |
| Erase the value at an iterator. | |
| iterator | erase (const_iterator position) |
| Erase the value at a read-only iterator. | |
| iterator | erase (const_iterator first, const_iterator last) |
| Erase [first, last). | |
| size_type | erase (const K &value) |
| Erase a value. | |
| void | swap (UnorderedSet &other) noexcept |
| Exchange tables. | |
| iterator | find (const K &value) |
| Find a value. | |
| const_iterator | find (const K &value) const |
| Find a value. | |
| size_type | count (const K &value) const |
| Count matching values. | |
| bool | contains (const K &value) const |
| Test whether a value is present. | |
| Pair< iterator, iterator > | equal_range (const K &value) |
Return the range of values equal to value. | |
| Pair< const_iterator, const_iterator > | equal_range (const K &value) const |
Return the range of values equal to value. | |
| size_type | bucket_count () const noexcept |
| Return the bucket count. | |
| size_type | bucket_size (size_type index) const |
Return the number of values in index. | |
| size_type | bucket (const K &value) const |
Return the bucket of value. | |
| 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 values without exceeding the load factor. | |
| bool | operator== (const UnorderedSet &other) const |
| Compare values. | |
| bool | operator!= (const UnorderedSet &other) const |
| Compare values. | |
| STORMBYTE_FORCE_INLINE | operator std::unordered_set< K > () const |
| Copy the values into caller-owned STL storage. | |
Unique values stored in a Base-heap hash table.
| K | Safe value type. It must be hashable by Hash. |
| Hash | Cross-module hash. A stateless hash does not allocate. A stateful one is stored in the set and must itself be Safe. |
| KeyEqual | Value equality. A stateless predicate does not allocate. A stateful one is stored in the set and must itself be Safe. |
The table is the same Base-heap table as UnorderedMap. Iterators yield the value, not a pair. Order is bucket order. Rehash invalidates every cursor. node_type owns a Base node. It is not std::unordered_set::node_type. There is no allocator. The default hash is Hash, not std::hash. A conversion to std::unordered_set copies the values and does not reuse this hasher.
| using StormByte::Safe::UnorderedSet< K, Hash, KeyEqual >::const_reference = const K& |
Read-only value reference.
| using StormByte::Safe::UnorderedSet< K, Hash, KeyEqual >::difference_type = std::ptrdiff_t |
Iterator distance type.
| using StormByte::Safe::UnorderedSet< K, Hash, KeyEqual >::hasher = Hash |
Value hash.
| using StormByte::Safe::UnorderedSet< K, Hash, KeyEqual >::insert_result = Pair<iterator, bool> |
Iterator to the value and whether it was inserted.
| using StormByte::Safe::UnorderedSet< K, Hash, KeyEqual >::key_equal = KeyEqual |
Value equality.
| using StormByte::Safe::UnorderedSet< K, Hash, KeyEqual >::key_type = K |
Value and lookup type.
| using StormByte::Safe::UnorderedSet< K, Hash, KeyEqual >::reference = const K& |
Read-only value reference.
| using StormByte::Safe::UnorderedSet< K, Hash, KeyEqual >::size_type = Size |
Element count. Size, not std::size_t.
| using StormByte::Safe::UnorderedSet< K, Hash, KeyEqual >::value_type = K |
Stored value.
|
noexcept |
Construct an empty set.
|
explicit |
Construct an empty set with a bucket count and predicates.
| buckets | Initial bucket count. Rounded up to a power of two. Zero selects the default. |
| hash | Value hash. |
| equal | Value equality. |
| AllocationError | The bucket array could not be allocated. |
| StormByte::Safe::UnorderedSet< K, Hash, KeyEqual >::UnorderedSet | ( | const UnorderedSet< K, Hash, KeyEqual > & | other | ) |
|
noexcept |
Take the table.
other is left empty.
| other | Source. |
| StormByte::Safe::UnorderedSet< K, Hash, KeyEqual >::~UnorderedSet | ( | ) |
Destroy the values.
| StormByte::Safe::UnorderedSet< K, Hash, KeyEqual >::UnorderedSet | ( | InputIt | first, |
| InputIt | last ) |
Construct from an iterator range.
| InputIt | Input iterator of values. |
| first | Start. |
| last | End. |
| AllocationError | A node could not be allocated. |
| StormByte::Safe::UnorderedSet< K, Hash, KeyEqual >::UnorderedSet | ( | InputIt | first, |
| InputIt | last, | ||
| size_type | buckets, | ||
| const Hash & | hash = Hash(), | ||
| const KeyEqual & | equal = KeyEqual() ) |
Construct from an iterator range, a bucket count and predicates.
| InputIt | Input iterator of values. |
| first | Start. |
| last | End. |
| buckets | Initial bucket count. |
| hash | Value hash. |
| equal | Value equality. |
| AllocationError | A node could not be allocated. |
| StormByte::Safe::UnorderedSet< K, Hash, KeyEqual >::UnorderedSet | ( | std::initializer_list< K > | values | ) |
Construct from an initializer list.
| values | Values. Duplicates are dropped. |
| AllocationError | A node could not be allocated. |
| StormByte::Safe::UnorderedSet< K, Hash, KeyEqual >::UnorderedSet | ( | std::initializer_list< K > | values, |
| size_type | buckets, | ||
| const Hash & | hash = Hash(), | ||
| const KeyEqual & | equal = KeyEqual() ) |
Construct from an initializer list, a bucket count and predicates.
| values | Values. Duplicates are dropped. |
| buckets | Initial bucket count. |
| hash | Value hash. |
| equal | Value equality. |
| AllocationError | A node could not be allocated. |
|
inlineexplicit |
Copy a caller-owned STL set.
Its hasher is not reused.
| other | Source. |
| AllocationError | A node could not be allocated. |
|
inlineexplicit |
Move values from a caller-owned STL set and leave it empty.
Its hasher is not reused.
| other | Source. Cleared before this function returns. |
| AllocationError | A node could not be allocated. |
|
noexcept |
Return an iterator to the first occupied node.
|
noexcept |
Return an iterator to the first occupied node.
| size_type StormByte::Safe::UnorderedSet< K, Hash, KeyEqual >::bucket | ( | const K & | value | ) | const |
Return the bucket of value.
| value | Lookup value. |
|
noexcept |
Return the bucket count.
| size_type StormByte::Safe::UnorderedSet< K, Hash, KeyEqual >::bucket_size | ( | size_type | index | ) | const |
Return the number of values in index.
| index | Bucket index. Not checked. |
|
noexcept |
Return an iterator to the first occupied node.
|
noexcept |
Return the past-the-end iterator.
|
noexcept |
Destroy every value.
The bucket array stays.
| bool StormByte::Safe::UnorderedSet< K, Hash, KeyEqual >::contains | ( | const K & | value | ) | const |
| size_type StormByte::Safe::UnorderedSet< K, Hash, KeyEqual >::count | ( | const K & | value | ) | const |
Count matching values.
| value | Lookup value. |
| insert_result StormByte::Safe::UnorderedSet< K, Hash, KeyEqual >::emplace | ( | Args &&... | args | ) |
Construct a value in a new node if it is absent.
| Args | Value constructor argument types. |
| args | Arguments forwarded to K. |
| AllocationError | The node could not be allocated. |
| iterator StormByte::Safe::UnorderedSet< K, Hash, KeyEqual >::emplace_hint | ( | const_iterator | hint, |
| Args &&... | args ) |
Construct a value.
hint is ignored.
| Args | Value constructor argument types. |
| hint | Unused. |
| args | Arguments forwarded to K. |
| AllocationError | The node could not be allocated. |
|
noexcept |
Test whether the set has no values.
|
noexcept |
Return the past-the-end iterator.
|
noexcept |
Return the past-the-end iterator.
| Pair< iterator, iterator > StormByte::Safe::UnorderedSet< K, Hash, KeyEqual >::equal_range | ( | const K & | value | ) |
Return the range of values equal to value.
| value | Lookup value. |
| Pair< const_iterator, const_iterator > StormByte::Safe::UnorderedSet< K, Hash, KeyEqual >::equal_range | ( | const K & | value | ) | const |
Return the range of values equal to value.
| value | Lookup value. |
| size_type StormByte::Safe::UnorderedSet< K, Hash, KeyEqual >::erase | ( | const K & | value | ) |
Erase a value.
| value | Lookup value. |
| iterator StormByte::Safe::UnorderedSet< K, Hash, KeyEqual >::erase | ( | const_iterator | first, |
| const_iterator | last ) |
Erase [first, last).
| first | First value to erase. |
| last | End of the range. |
| iterator StormByte::Safe::UnorderedSet< K, Hash, KeyEqual >::erase | ( | const_iterator | position | ) |
Erase the value at a read-only iterator.
| position | Value to erase. |
| iterator StormByte::Safe::UnorderedSet< K, Hash, KeyEqual >::erase | ( | iterator | position | ) |
Erase the value at an iterator.
| position | Value to erase. |
| node_type StormByte::Safe::UnorderedSet< K, Hash, KeyEqual >::extract | ( | const K & | value | ) |
Unlink value and return that node.
| value | Lookup value. |
| node_type StormByte::Safe::UnorderedSet< K, Hash, KeyEqual >::extract | ( | const_iterator | position | ) |
Unlink the value at position and return that node.
| position | Value to extract. |
position is end. | iterator StormByte::Safe::UnorderedSet< K, Hash, KeyEqual >::find | ( | const K & | value | ) |
Find a value.
| value | Lookup value. |
| const_iterator StormByte::Safe::UnorderedSet< K, Hash, KeyEqual >::find | ( | const K & | value | ) | const |
Find a value.
| value | Lookup value. |
| hasher StormByte::Safe::UnorderedSet< K, Hash, KeyEqual >::hash_function | ( | ) | const |
Return the stored hash.
| insert_result StormByte::Safe::UnorderedSet< K, Hash, KeyEqual >::insert | ( | const K & | value | ) |
Insert a value if it is absent.
| value | Value to copy. |
| AllocationError | The node could not be allocated. |
| iterator StormByte::Safe::UnorderedSet< K, Hash, KeyEqual >::insert | ( | const_iterator | hint, |
| const K & | value ) |
Insert a value.
hint is ignored.
| hint | Unused. |
| value | Value to copy. |
| AllocationError | The node could not be allocated. |
| iterator StormByte::Safe::UnorderedSet< K, Hash, KeyEqual >::insert | ( | const_iterator | hint, |
| K && | value ) |
Insert a value.
hint is ignored.
| hint | Unused. |
| value | Value to move. |
| AllocationError | The node could not be allocated. |
| iterator StormByte::Safe::UnorderedSet< K, Hash, KeyEqual >::insert | ( | const_iterator | hint, |
| node_type && | handle ) |
Insert an extracted node.
hint is ignored.
| hint | Unused. |
| handle | Node from a set with this hash and equality. Emptied when inserted. |
handle was empty. | AllocationError | The bucket array could not grow. |
| void StormByte::Safe::UnorderedSet< K, Hash, KeyEqual >::insert | ( | InputIt | first, |
| InputIt | last ) |
Insert every value in [first, last).
| InputIt | Input iterator of values. |
| first | Start. |
| last | End. |
| AllocationError | A node could not be allocated. |
| insert_result StormByte::Safe::UnorderedSet< K, Hash, KeyEqual >::insert | ( | K && | value | ) |
Insert a value if it is absent.
| value | Value to move. |
| AllocationError | The node could not be allocated. |
| insert_return_type StormByte::Safe::UnorderedSet< K, Hash, KeyEqual >::insert | ( | node_type && | handle | ) |
Insert an extracted node if its value is absent.
The same node is linked.
| handle | Node from a set with this hash and equality. Emptied when inserted. |
| AllocationError | The bucket array could not grow. |
| void StormByte::Safe::UnorderedSet< K, Hash, KeyEqual >::insert | ( | std::initializer_list< K > | values | ) |
Insert every value of an initializer list.
| values | Values. |
| AllocationError | A node could not be allocated. |
|
inline |
Insert a copy of range.
| R | Input range of values. |
| range | Source. Instantiated in the caller. |
| AllocationError | A node could not be allocated. |
| key_equal StormByte::Safe::UnorderedSet< K, Hash, KeyEqual >::key_eq | ( | ) | const |
Return the stored equality predicate.
|
noexcept |
Return the current load factor.
|
noexcept |
Return the load factor that triggers a rehash.
|
noexcept |
Set the load factor that triggers a rehash.
| factor | Maximum load factor. Not checked. |
|
noexcept |
Return the maximum number of values.
| void StormByte::Safe::UnorderedSet< K, Hash, KeyEqual >::merge | ( | UnorderedSet< K, OtherHash, OtherEqual > & | source | ) |
Take unique values from source.
| OtherHash | Source hash. |
| OtherEqual | Source equality. |
| source | Set to drain. The same hash and equality transfer the node. A different predicate copies the value. Values already present stay in source. |
| AllocationError | A copied node could not be allocated. |
|
inlineexplicit |
Copy the values into caller-owned STL storage.
The STL hasher is std::hash.
| bool StormByte::Safe::UnorderedSet< K, Hash, KeyEqual >::operator!= | ( | const UnorderedSet< K, Hash, KeyEqual > & | other | ) | const |
Compare values.
Order does not matter.
| other | Other set. |
| UnorderedSet & StormByte::Safe::UnorderedSet< K, Hash, KeyEqual >::operator= | ( | const UnorderedSet< K, Hash, KeyEqual > & | other | ) |
Copy-assign the values.
| other | Source. |
| AllocationError | A node could not be allocated. |
| UnorderedSet & StormByte::Safe::UnorderedSet< K, Hash, KeyEqual >::operator= | ( | std::initializer_list< K > | values | ) |
Replace the contents with an initializer list.
| values | Values. Duplicates are dropped. |
| AllocationError | A node could not be allocated. |
|
noexcept |
Move-assign the table.
other is left empty.
| other | Source. |
| bool StormByte::Safe::UnorderedSet< K, Hash, KeyEqual >::operator== | ( | const UnorderedSet< K, Hash, KeyEqual > & | other | ) | const |
Compare values.
Order does not matter.
| other | Other set. |
| void StormByte::Safe::UnorderedSet< K, Hash, KeyEqual >::rehash | ( | size_type | buckets | ) |
Replace the bucket array.
Values 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::UnorderedSet< K, Hash, KeyEqual >::reserve | ( | size_type | count | ) |
Reserve room for count values without exceeding the load factor.
| count | Value count to accommodate. |
| AllocationError | The bucket array could not be allocated. |
|
noexcept |
Return the number of values.
|
noexcept |
Exchange tables.
| other | Other set. |