52#include <initializer_list>
56#include <unordered_map>
79 template<Type::SafeValue K, Type::SafeValue V,
class Hash = Hash<K>,
class KeyEqual = std::equal_to<K>>
102 template<
bool IsConst>
104 using NodeType = std::conditional_t<IsConst, const Node, Node>;
105 using MapType = std::conditional_t<IsConst, const UnorderedMap, UnorderedMap>;
112 using reference = std::conditional_t<IsConst, const value_type&, value_type&>;
113 using pointer = std::conditional_t<IsConst, const value_type*, value_type*>;
125 template<
bool OtherConst>
126 requires IsConst && (!OtherConst)
158 template<
bool OtherConst>
159 bool operator==(const
BasicIterator<OtherConst>& other) const noexcept {
return m_node == other.m_node; }
170 explicit BasicIterator(NodeType* node, MapType* map)
noexcept: m_node(node), m_map(map) {}
221 if (
this != &other) {
223 m_node = other.m_node;
224 other.m_node =
nullptr;
233 bool empty() const noexcept {
return m_node ==
nullptr; }
239 explicit operator bool() const noexcept {
return !
empty(); }
245 const K&
key()
const {
return m_node->Entry.first; }
251 V&
mapped() {
return m_node->Entry.second; }
257 const V&
mapped()
const {
return m_node->Entry.second; }
272 explicit node_type(Node* node)
noexcept: m_node(node) {}
277 void reset() noexcept {
278 if (m_node ==
nullptr)
280 m_node->Entry.~value_type();
285 Node* m_node =
nullptr;
350 for (
const auto& entry : other)
360 for (
auto& entry : other)
371 template<std::ranges::input_range R>
372 requires std::convertible_to<std::ranges::range_reference_t<R>, value_type>
432 bool empty() const noexcept {
return m_size == 0; }
480 template<
std::ranges::input_range R>
483 for (
auto&& entry : range)
494 template<
class... Args>
505 template<
class... Args>
551 insert_return_type
insert(node_type&& node);
580 const V&
at(
const K& key)
const;
680 KeyEqual
key_eq()
const {
return m_equal; }
694 std::unordered_map<K, V> copied(m_bucket_count);
716 static size_type BucketSlot(std::size_t code,
Size count)
noexcept {
717 return Size{code & (
static_cast<std::size_t
>(count) - 1)};
725 static size_type BucketCount(size_type count)
noexcept;
733 Node** AllocateBuckets(size_type count);
738 void FreeBuckets() noexcept;
743 void Destroy() noexcept;
751 Node* FindNode(const K& key, std::
size_t code) const noexcept;
757 Node* FirstNode() const noexcept;
764 Node* NextBucket(size_type slot) const noexcept;
771 void Link(Node* node);
778 Node* Unlink(Node* node) noexcept;
784 void Ensure(size_type extra);
786 Node** m_buckets =
nullptr;
787 size_type m_bucket_count = 0;
788 size_type m_size = 0;
789 float m_max_load = 1.0f;
803 template<Type::SafeValue K, Type::SafeValue V,
class Hash,
class KeyEqual>
819 template<SafeValue K, SafeValue V,
class Hash,
class KeyEqual>
820 requires IsSafe<K>::value && IsSafe<V>::value
821 struct IsSafe<
Safe::UnorderedMap<K, V, Hash, KeyEqual>>: std::true_type {};
830 template<SafeValue K, SafeValue V,
class Hash,
class KeyEqual>
841 template<SafeValue K, SafeValue V,
class Hash,
class KeyEqual>
std::pair whose members keep their own Safe storage.
Definition pair.hxx:73
Second second
Second value.
Definition pair.hxx:79
First first
First value.
Definition pair.hxx:78
Forward cursor over Base-owned hash nodes.
Definition unordered_map.hxx:103
std::forward_iterator_tag iterator_concept
C++20 iterator concept.
Definition unordered_map.hxx:109
std::conditional_t< IsConst, const value_type *, value_type * > pointer
Entry pointer.
Definition unordered_map.hxx:113
std::conditional_t< IsConst, const value_type &, value_type & > reference
Entry reference.
Definition unordered_map.hxx:112
&&!OtherConst BasicIterator(const BasicIterator< OtherConst > &other) noexcept
Convert a mutable iterator to a const iterator.
Definition unordered_map.hxx:127
UnorderedMap::value_type value_type
Entry type.
Definition unordered_map.hxx:110
std::ptrdiff_t difference_type
Iterator distance type.
Definition unordered_map.hxx:111
std::forward_iterator_tag iterator_category
Iterator category.
Definition unordered_map.hxx:108
void StormByteSafeCursor
Base cursor mark. Copying the cursor copies one node pointer.
Definition unordered_map.hxx:114
friend class BasicIterator
Definition unordered_map.hxx:163
friend class UnorderedMap
Definition unordered_map.hxx:162
pointer operator->() const noexcept
Access the entry stored in the node.
Definition unordered_map.hxx:139
reference operator*() const noexcept
Return the entry stored in the node.
Definition unordered_map.hxx:133
BasicIterator() noexcept
Construct a singular iterator.
Definition unordered_map.hxx:119
BasicIterator & operator++() noexcept
Advance to the next occupied node, skipping empty buckets.
Owning handle to one extracted Base node.
Definition unordered_map.hxx:186
node_type() noexcept=default
Construct an empty handle.
V & mapped()
Return the owned mapped value.
Definition unordered_map.hxx:251
~node_type()
Destroy the owned node, if any.
Definition unordered_map.hxx:207
const K & key() const
Return the owned key.
Definition unordered_map.hxx:245
friend class UnorderedMap
Definition unordered_map.hxx:266
bool empty() const noexcept
Test whether the handle owns a node.
Definition unordered_map.hxx:233
node_type & operator=(const node_type &)=delete
Copying a node handle is not supported.
void swap(node_type &other) noexcept
Exchange owned nodes.
Definition unordered_map.hxx:263
node_type & operator=(node_type &&other) noexcept
Take the node.
Definition unordered_map.hxx:220
const V & mapped() const
Return the owned mapped value.
Definition unordered_map.hxx:257
Unique-key hash map stored on Base's heap.
Definition unordered_map.hxx:80
insert_return_type insert(node_type &&node)
Link an extracted node.
void rehash(size_type buckets)
Replace the bucket array.
STORMBYTE_FORCE_INLINE UnorderedMap(std::unordered_map< K, V > &&other)
Move elements from a caller-owned STL map and leave it empty.
Definition unordered_map.hxx:359
Pair< iterator, bool > insert_result
Iterator to the entry and whether it was inserted.
Definition unordered_map.hxx:178
Pair< const K, V > value_type
Entry type. The key is immutable.
Definition unordered_map.hxx:87
size_type max_size() const noexcept
Return the maximum entry count this map can report.
Definition unordered_map.hxx:444
const_iterator find(const K &key) const
Find an entry.
size_type count(const K &key) const
Count entries with key.
Size size_type
Element count. Size, not std::size_t.
Definition unordered_map.hxx:90
KeyEqual key_equal
Key equality.
Definition unordered_map.hxx:89
size_type bucket(const K &key) const
Return the bucket of key.
Hash hash_function() const
Return the stored hash.
Definition unordered_map.hxx:674
iterator begin() noexcept
Return the first occupied node.
const_iterator begin() const noexcept
Return the first occupied node.
bool empty() const noexcept
Test whether the map holds no entries.
Definition unordered_map.hxx:432
insert_result emplace(Args &&... args)
Construct an entry in place when the key is absent.
void swap(UnorderedMap &other) noexcept
Exchange tables.
node_type extract(const K &key)
Unlink the entry with key.
const_iterator cend() const noexcept
Return the past-the-end iterator.
Definition unordered_map.hxx:426
iterator find(const K &key)
Find an entry.
const_iterator cbegin() const noexcept
Return the first occupied node.
Definition unordered_map.hxx:420
Hash hasher
Key hash.
Definition unordered_map.hxx:88
size_type bucket_count() const noexcept
Definition unordered_map.hxx:622
void clear() noexcept
Destroy every entry.
void merge(UnorderedMap &other)
Move entries whose keys are absent from other.
STORMBYTE_FORCE_INLINE UnorderedMap(std::from_range_t, R &&range)
Copy the entries of range.
Definition unordered_map.hxx:373
size_type bucket_size(size_type index) const
Return the number of entries in index.
bool operator==(const UnorderedMap &other) const
Compare entries by key and mapped value.
iterator erase(const_iterator position)
Erase the entry at position.
BasicIterator< true > const_iterator
Read-only iterator.
Definition unordered_map.hxx:177
V mapped_type
Mapped type.
Definition unordered_map.hxx:86
std::ptrdiff_t difference_type
Iterator distance type.
Definition unordered_map.hxx:91
insert_result insert_or_assign(const K &key, V mapped)
Insert or replace the mapped value.
size_type erase(const K &key)
Erase the entry with key.
bool contains(const K &key) const
Test whether key is present.
UnorderedMap(std::initializer_list< value_type > values)
Insert every entry of an initializer list.
void max_load_factor(float factor) noexcept
Set the load factor that triggers a rehash.
Definition unordered_map.hxx:654
float load_factor() const noexcept
Return the current load factor.
UnorderedMap() noexcept
Construct an empty map.
const V & at(const K &key) const
Return the mapped value.
KeyEqual key_eq() const
Return the stored equality predicate.
Definition unordered_map.hxx:680
BasicIterator< false > iterator
Mutable iterator.
Definition unordered_map.hxx:176
value_type & reference
Mutable entry reference.
Definition unordered_map.hxx:92
iterator end() noexcept
Definition unordered_map.hxx:402
size_type size() const noexcept
Return the entry count.
Definition unordered_map.hxx:438
node_type extract(const_iterator position)
Unlink the entry at position.
insert_result insert(const value_type &value)
UnorderedMap & operator=(std::initializer_list< value_type > values)
Replace the contents with an initializer list.
V & at(const K &key)
Return the mapped value.
insert_result try_emplace(const K &key, Args &&... args)
Construct the mapped value in place when the key is absent.
V & operator[](const K &key)
Return the mapped value, inserting a value-initialized one when absent.
const value_type & const_reference
Read-only entry reference.
Definition unordered_map.hxx:93
float max_load_factor() const noexcept
Definition unordered_map.hxx:648
K key_type
Key type.
Definition unordered_map.hxx:85
STORMBYTE_FORCE_INLINE void insert_range(R &&range)
Definition unordered_map.hxx:482
void reserve(size_type count)
Reserve room for count entries without exceeding the load factor.
Count of abstract units (uint64_t storage).
Definition size.hxx:107
Recognizes a conditional Safe component after stripping cv and references.
Definition safe.hxx:301
Private Base heap used by StormByte::Safe::Shared, StormByte::Safe::Unique and StormByte::Safe::Clona...
void Free(void *pointer) noexcept
Release a block obtained from Allocate.
Owned values that cross a DLL without the caller's CRT.
void swap(Binary &left, Binary &right) noexcept
Exchange two sequences.
Definition binary.hxx:760
Root namespace of the StormByte suite.
Octet count. Defined in byte_size.hxx. Forwarded so Type::Numeral can name it.
Host-width-stable count (uint64_t), implicit only to std::size_t.
Cross-module hash.
Definition hash.hxx:95
Result of inserting an extracted node.
Definition unordered_map.hxx:291
iterator position
Entry, or end when the node was not inserted and is empty.
Definition unordered_map.hxx:292
bool inserted
Whether the node was linked.
Definition unordered_map.hxx:293
node_type node
Returned node when the key was already present.
Definition unordered_map.hxx:294
Recognizes types whose DLL-boundary safety depends on documented provider requirements.
Definition safe.hxx:262
Recognizes collection values with Base-controlled lifetime.
Definition safe.hxx:347
Recognizes Base Safe components, not universal ABI compatibility.
Definition safe.hxx:138
#define STORMBYTE_PUBLIC_TYPE
Definition visibility.h:57
#define STORMBYTE_PUBLIC
Definition visibility.h:52