StormByte 3.0.0
C++26 foundation of the StormByte suite
Loading...
Searching...
No Matches
unordered_map.hxx
Go to the documentation of this file.
1/*
2 * Copyright (C) 2024-2026 David C. Manuelda (StormBytePP)
3 *
4 * This is the base for StormByte Suite libraries.
5 *
6 * StormByte original source is dual-licensed:
7 *
8 * 1. GNU Lesser General Public License v3.0 (or later)
9 * You may redistribute and/or modify this file under the terms of the
10 * GNU Lesser General Public License as published by the Free Software
11 * Foundation, either version 3 of the License, or (at your option)
12 * any later version.
13 *
14 * 2. Commercial license
15 * Alternatively, this file may be used under the terms of a commercial
16 * license agreement with the copyright holder
17 * (David C. Manuelda <StormByte@gmail.com>).
18 *
19 * Both licenses apply only to original StormByte source in this repository.
20 * They do not cover other StormByte modules or any third-party material
21 * shipped with this repository (including everything under thirdparty/),
22 * which remains under its own license.
23 *
24 * Neither license grants any patent rights. Any patent licenses required
25 * to use this software or third-party components must be obtained separately
26 * from the patent holders.
27 *
28 * StormByte is distributed in the hope that it will be useful,
29 * but WITHOUT ANY WARRANTY; without even the implied warranty of
30 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
31 * GNU Lesser General Public License for more details.
32 *
33 * You should have received a copy of the GNU Lesser General Public License
34 * version 3 along with StormByte. If not, see
35 * <https://www.gnu.org/licenses/lgpl-3.0.html>.
36 *
37 * SPDX-License-Identifier: LGPL-3.0-or-later OR LicenseRef-StormByte-Commercial
38 */
39
40#pragma once
41
42#include <StormByte/size.hxx>
49
50#include <cstddef>
51#include <functional>
52#include <initializer_list>
53#include <iterator>
54#include <limits>
55#include <ranges>
56#include <unordered_map>
57#include <utility>
58
63namespace StormByte {
68 namespace Safe {
79 template<Type::SafeValue K, Type::SafeValue V, class Hash = Hash<K>, class KeyEqual = std::equal_to<K>>
81 private:
82 struct Node;
83
84 public:
85 using key_type = K;
86 using mapped_type = V;
88 using hasher = Hash;
89 using key_equal = KeyEqual;
90 using size_type = Size;
91 using difference_type = std::ptrdiff_t;
93 using const_reference = const value_type&;
94
102 template<bool IsConst>
103 class BasicIterator final {
104 using NodeType = std::conditional_t<IsConst, const Node, Node>;
105 using MapType = std::conditional_t<IsConst, const UnorderedMap, UnorderedMap>;
106
107 public:
108 using iterator_category = std::forward_iterator_tag;
109 using iterator_concept = std::forward_iterator_tag;
111 using difference_type = std::ptrdiff_t;
112 using reference = std::conditional_t<IsConst, const value_type&, value_type&>;
113 using pointer = std::conditional_t<IsConst, const value_type*, value_type*>;
114 using StormByteSafeCursor = void;
115
119 BasicIterator() noexcept: m_node(nullptr), m_map(nullptr) {}
120
125 template<bool OtherConst>
126 requires IsConst && (!OtherConst)
127 BasicIterator(const BasicIterator<OtherConst>& other) noexcept: m_node(other.m_node), m_map(other.m_map) {}
128
133 reference operator*() const noexcept { return m_node->Entry; }
134
139 pointer operator->() const noexcept { return &m_node->Entry; }
140
146
151 BasicIterator operator++(int) noexcept;
152
158 template<bool OtherConst>
159 bool operator==(const BasicIterator<OtherConst>& other) const noexcept { return m_node == other.m_node; }
160
161 private:
162 friend class UnorderedMap;
163 template<bool> friend class BasicIterator;
164
170 explicit BasicIterator(NodeType* node, MapType* map) noexcept: m_node(node), m_map(map) {}
171
172 NodeType* m_node;
173 MapType* m_map;
174 };
175
179
186 class node_type {
187 public:
191 node_type() noexcept = default;
192
196 node_type(const node_type&) = delete;
197
202 node_type(node_type&& other) noexcept: m_node(other.m_node) { other.m_node = nullptr; }
203
207 ~node_type() { reset(); }
208
213 node_type& operator=(const node_type&) = delete;
214
220 node_type& operator=(node_type&& other) noexcept {
221 if (this != &other) {
222 reset();
223 m_node = other.m_node;
224 other.m_node = nullptr;
225 }
226 return *this;
227 }
228
233 bool empty() const noexcept { return m_node == nullptr; }
234
239 explicit operator bool() const noexcept { return !empty(); }
240
245 const K& key() const { return m_node->Entry.first; }
246
251 V& mapped() { return m_node->Entry.second; }
252
257 const V& mapped() const { return m_node->Entry.second; }
258
263 void swap(node_type& other) noexcept { std::swap(m_node, other.m_node); }
264
265 private:
266 friend class UnorderedMap;
267
272 explicit node_type(Node* node) noexcept: m_node(node) {}
273
277 void reset() noexcept {
278 if (m_node == nullptr)
279 return;
280 m_node->Entry.~value_type();
281 Heap::Free(m_node);
282 m_node = nullptr;
283 }
284
285 Node* m_node = nullptr;
286 };
287
296
300 UnorderedMap() noexcept;
301
309 explicit UnorderedMap(size_type buckets, const Hash& hash = Hash(), const KeyEqual& equal = KeyEqual());
310
317
322 UnorderedMap(UnorderedMap&& other) noexcept;
323
327 ~UnorderedMap() noexcept;
328
335 UnorderedMap& operator=(const UnorderedMap& other);
336
342 UnorderedMap& operator=(UnorderedMap&& other) noexcept;
343
349 STORMBYTE_FORCE_INLINE explicit UnorderedMap(const std::unordered_map<K, V>& other): UnorderedMap(other.bucket_count()) {
350 for (const auto& entry : other)
351 insert(value_type(entry.first, entry.second));
352 }
353
359 STORMBYTE_FORCE_INLINE explicit UnorderedMap(std::unordered_map<K, V>&& other): UnorderedMap(other.bucket_count()) {
360 for (auto& entry : other)
361 insert(value_type(entry.first, std::move(entry.second)));
362 other.clear();
363 }
364
371 template<std::ranges::input_range R>
372 requires std::convertible_to<std::ranges::range_reference_t<R>, value_type>
373 STORMBYTE_FORCE_INLINE explicit UnorderedMap(std::from_range_t, R&& range): UnorderedMap() {
374 insert_range(std::forward<R>(range));
375 }
376
382 UnorderedMap(std::initializer_list<value_type> values);
383
390 UnorderedMap& operator=(std::initializer_list<value_type> values);
391
396 iterator begin() noexcept;
397
402 iterator end() noexcept { return iterator(nullptr, this); }
403
408 const_iterator begin() const noexcept;
409
414 const_iterator end() const noexcept { return const_iterator(nullptr, this); }
415
420 const_iterator cbegin() const noexcept { return begin(); }
421
426 const_iterator cend() const noexcept { return end(); }
427
432 bool empty() const noexcept { return m_size == 0; }
433
438 size_type size() const noexcept { return m_size; }
439
444 size_type max_size() const noexcept { return std::numeric_limits<size_type>::max(); }
445
449 void clear() noexcept;
450
458
466
472 void insert(std::initializer_list<value_type> values);
473
480 template<std::ranges::input_range R>
481 requires std::convertible_to<std::ranges::range_reference_t<R>, value_type>
483 for (auto&& entry : range)
484 insert(value_type(std::forward<decltype(entry)>(entry)));
485 }
486
494 template<class... Args>
495 insert_result emplace(Args&&... args);
496
505 template<class... Args>
506 insert_result try_emplace(const K& key, Args&&... args);
507
515 insert_result insert_or_assign(const K& key, V mapped);
516
523
529 size_type erase(const K& key);
530
536 node_type extract(const_iterator position);
537
543 node_type extract(const K& key);
544
551 insert_return_type insert(node_type&& node);
552
558 void merge(UnorderedMap& other);
559
564 void swap(UnorderedMap& other) noexcept;
565
572 V& at(const K& key);
573
580 const V& at(const K& key) const;
581
588 V& operator[](const K& key);
589
595 iterator find(const K& key);
596
602 const_iterator find(const K& key) const;
603
609 size_type count(const K& key) const;
610
616 bool contains(const K& key) const;
617
622 size_type bucket_count() const noexcept { return m_bucket_count; }
623
630
636 size_type bucket(const K& key) const;
637
642 float load_factor() const noexcept;
643
648 float max_load_factor() const noexcept { return m_max_load; }
649
654 void max_load_factor(float factor) noexcept { m_max_load = factor; }
655
661 void rehash(size_type buckets);
662
669
674 Hash hash_function() const { return m_hash; }
675
680 KeyEqual key_eq() const { return m_equal; }
681
687 bool operator==(const UnorderedMap& other) const;
688
693 STORMBYTE_FORCE_INLINE explicit operator std::unordered_map<K, V>() const {
694 std::unordered_map<K, V> copied(m_bucket_count);
695 for (const value_type& entry : *this)
696 copied.emplace(entry.first, entry.second);
697 return copied;
698 }
699
700 private:
704 struct Node {
705 Node* Next;
706 std::size_t Code;
707 value_type Entry;
708 };
709
716 static size_type BucketSlot(std::size_t code, Size count) noexcept {
717 return Size{code & (static_cast<std::size_t>(count) - 1)};
718 }
719
725 static size_type BucketCount(size_type count) noexcept;
726
733 Node** AllocateBuckets(size_type count);
734
738 void FreeBuckets() noexcept;
739
743 void Destroy() noexcept;
744
751 Node* FindNode(const K& key, std::size_t code) const noexcept;
752
757 Node* FirstNode() const noexcept;
758
764 Node* NextBucket(size_type slot) const noexcept;
765
771 void Link(Node* node);
772
778 Node* Unlink(Node* node) noexcept;
779
784 void Ensure(size_type extra);
785
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;
790 Hash m_hash{};
791 KeyEqual m_equal{};
792 };
793
803 template<Type::SafeValue K, Type::SafeValue V, class Hash, class KeyEqual>
804 void swap(UnorderedMap<K, V, Hash, KeyEqual>& left, UnorderedMap<K, V, Hash, KeyEqual>& right) noexcept { left.swap(right); }
805 }
806
811 namespace Type {
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 {};
822
830 template<SafeValue K, SafeValue V, class Hash, class KeyEqual>
831 requires MaybeSafe<K> || MaybeSafe<V>
832 struct IsMaybeSafe<Safe::UnorderedMap<K, V, Hash, KeyEqual>>: std::true_type {};
833
841 template<SafeValue K, SafeValue V, class Hash, class KeyEqual>
842 struct IsSafeValue<Safe::UnorderedMap<K, V, Hash, KeyEqual>>: std::true_type {};
843 }
844}
845
849
852
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.
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.
STL namespace.
#define STORMBYTE_FORCE_INLINE
Definition platform.h:134
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