StormByte 3.0.0
C++26 foundation of the StormByte suite
Loading...
Searching...
No Matches
unordered_set.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
47
48#include <cstddef>
49#include <functional>
50#include <initializer_list>
51#include <iterator>
52#include <unordered_set>
53#include <utility>
54
59namespace StormByte {
64 namespace Safe {
74 template<Type::SafeValue K, class Hash = Hash<K>, class KeyEqual = std::equal_to<K>>
77
78 public:
79 using key_type = K;
80 using value_type = K;
81 using hasher = Hash;
82 using key_equal = KeyEqual;
83 using size_type = Size;
84 using difference_type = std::ptrdiff_t;
85 using reference = const K&;
86 using const_reference = const K&;
87
92 class iterator {
93 public:
94 using iterator_category = std::forward_iterator_tag;
95 using iterator_concept = std::forward_iterator_tag;
96 using value_type = K;
97 using difference_type = std::ptrdiff_t;
98 using pointer = const K*;
99 using reference = const K&;
100 using StormByteSafeCursor = void;
101
105 iterator() noexcept = default;
106
111 reference operator*() const { return m_cursor->first; }
112
117 pointer operator->() const { return &m_cursor->first; }
118
123 iterator& operator++() { ++m_cursor; return *this; }
124
129 iterator operator++(int) { iterator previous = *this; ++*this; return previous; }
130
136 bool operator==(const iterator& other) const noexcept { return m_cursor == other.m_cursor; }
137
138 private:
139 friend class UnorderedSet;
140 explicit iterator(typename Storage::iterator cursor) noexcept: m_cursor(cursor) {}
141 typename Storage::iterator m_cursor;
142 };
143
149 public:
150 using iterator_category = std::forward_iterator_tag;
151 using iterator_concept = std::forward_iterator_tag;
152 using value_type = K;
153 using difference_type = std::ptrdiff_t;
154 using pointer = const K*;
155 using reference = const K&;
156 using StormByteSafeCursor = void;
157
161 const_iterator() noexcept = default;
162
167 const_iterator(iterator other) noexcept: m_cursor(other.m_cursor) {}
168
173 reference operator*() const { return m_cursor->first; }
174
179 pointer operator->() const { return &m_cursor->first; }
180
185 const_iterator& operator++() { ++m_cursor; return *this; }
186
191 const_iterator operator++(int) { const_iterator previous = *this; ++*this; return previous; }
192
198 bool operator==(const const_iterator& other) const noexcept { return m_cursor == other.m_cursor; }
199
200 private:
201 friend class UnorderedSet;
202 explicit const_iterator(typename Storage::const_iterator cursor) noexcept: m_cursor(cursor) {}
203 typename Storage::const_iterator m_cursor;
204 };
205
207
214 class node_type {
215 public:
219 node_type() noexcept = default;
220
225 node_type(node_type&& other) noexcept = default;
226
232 node_type& operator=(node_type&& other) noexcept = default;
233
237 node_type(const node_type&) = delete;
238
243 node_type& operator=(const node_type&) = delete;
244
248 ~node_type() = default;
249
254 bool empty() const noexcept { return m_node.empty(); }
255
260 explicit operator bool() const noexcept { return !empty(); }
261
266 const K& value() const { return m_node.key(); }
267
272 void swap(node_type& other) noexcept { m_node.swap(other.m_node); }
273
274 private:
275 friend class UnorderedSet;
276 explicit node_type(typename Storage::node_type node) noexcept: m_node(std::move(node)) {}
277 typename Storage::node_type m_node;
278 };
279
288
292 UnorderedSet() noexcept;
293
301 explicit UnorderedSet(size_type buckets, const Hash& hash = Hash(), const KeyEqual& equal = KeyEqual());
302
309
314 UnorderedSet(UnorderedSet&& other) noexcept;
315
320
327 UnorderedSet& operator=(const UnorderedSet& other);
328
334 UnorderedSet& operator=(UnorderedSet&& other) noexcept;
335
342 UnorderedSet& operator=(std::initializer_list<K> values);
343
351 template<class InputIt>
352 UnorderedSet(InputIt first, InputIt last);
353
364 template<class InputIt>
365 UnorderedSet(InputIt first, InputIt last, size_type buckets, const Hash& hash = Hash(), const KeyEqual& equal = KeyEqual());
366
372 UnorderedSet(std::initializer_list<K> values);
373
382 UnorderedSet(std::initializer_list<K> values, size_type buckets, const Hash& hash = Hash(), const KeyEqual& equal = KeyEqual());
383
389 STORMBYTE_FORCE_INLINE explicit UnorderedSet(const std::unordered_set<K>& other): UnorderedSet(other.bucket_count()) {
390 for (const K& value : other)
391 insert(value);
392 }
393
399 STORMBYTE_FORCE_INLINE explicit UnorderedSet(std::unordered_set<K>&& other): UnorderedSet(other.bucket_count()) {
400 for (const K& value : other)
401 insert(value);
402 other.clear();
403 }
404
410
416
421 iterator begin() noexcept;
422
427 const_iterator begin() const noexcept;
428
433 const_iterator cbegin() const noexcept;
434
439 iterator end() noexcept;
440
445 const_iterator end() const noexcept;
446
451 const_iterator cend() const noexcept;
452
457 bool empty() const noexcept;
458
463 size_type size() const noexcept;
464
469 size_type max_size() const noexcept;
470
474 void clear() noexcept;
475
482 insert_result insert(const K& value);
483
491
499 iterator insert(const_iterator hint, const K& value);
500
509
517 template<class InputIt>
518 void insert(InputIt first, InputIt last);
519
525 void insert(std::initializer_list<K> values);
526
533 template<std::ranges::input_range R>
534 requires std::convertible_to<std::ranges::range_reference_t<R>, value_type>
536 for (auto&& value : range)
537 insert(value_type(std::forward<decltype(value)>(value)));
538 }
539
547 template<class... Args>
548 insert_result emplace(Args&&... args);
549
558 template<class... Args>
559 iterator emplace_hint(const_iterator hint, Args&&... args);
560
568
577
584
590 node_type extract(const K& value);
591
599 template<class OtherHash, class OtherEqual>
601
608
615
623
629 size_type erase(const K& value);
630
635 void swap(UnorderedSet& other) noexcept;
636
642 iterator find(const K& value);
643
649 const_iterator find(const K& value) const;
650
656 size_type count(const K& value) const;
657
663 bool contains(const K& value) const;
664
671
678
683 size_type bucket_count() const noexcept;
684
691
697 size_type bucket(const K& value) const;
698
703 float load_factor() const noexcept;
704
709 float max_load_factor() const noexcept;
710
715 void max_load_factor(float factor) noexcept;
716
722 void rehash(size_type buckets);
723
730
736 bool operator==(const UnorderedSet& other) const;
737
743 bool operator!=(const UnorderedSet& other) const;
744
749 STORMBYTE_FORCE_INLINE explicit operator std::unordered_set<K>() const {
750 std::unordered_set<K> exported(bucket_count());
751 for (const K& value : *this)
752 exported.insert(value);
753 return exported;
754 }
755
756 private:
757 Storage m_values;
758 };
759
768 template<Type::SafeValue K, class Hash, class KeyEqual>
770 left.swap(right);
771 }
772 }
773}
774
793
796
std::pair whose members keep their own Safe storage.
Definition pair.hxx:73
Unique-key hash map stored on Base's heap.
Definition unordered_map.hxx:80
BasicIterator< true > const_iterator
Definition unordered_map.hxx:177
BasicIterator< false > iterator
Definition unordered_map.hxx:176
Read-only forward cursor.
Definition unordered_set.hxx:148
std::forward_iterator_tag iterator_concept
C++20 iterator concept.
Definition unordered_set.hxx:151
const_iterator & operator++()
Advance to the next occupied node.
Definition unordered_set.hxx:185
const_iterator operator++(int)
Advance to the next occupied node.
Definition unordered_set.hxx:191
bool operator==(const const_iterator &other) const noexcept
Compare node identity.
Definition unordered_set.hxx:198
friend class UnorderedSet
Definition unordered_set.hxx:201
const K & reference
Reference to the value.
Definition unordered_set.hxx:155
std::ptrdiff_t difference_type
Iterator distance type.
Definition unordered_set.hxx:153
const K * pointer
Pointer to the value.
Definition unordered_set.hxx:154
K value_type
Stored value.
Definition unordered_set.hxx:152
pointer operator->() const
Return a pointer to the value.
Definition unordered_set.hxx:179
void StormByteSafeCursor
Base cursor mark. Copying the cursor copies one node pointer.
Definition unordered_set.hxx:156
std::forward_iterator_tag iterator_category
Iterator category.
Definition unordered_set.hxx:150
const_iterator() noexcept=default
Construct a singular iterator.
reference operator*() const
Return the value.
Definition unordered_set.hxx:173
Forward cursor.
Definition unordered_set.hxx:92
const K & reference
Reference to the value.
Definition unordered_set.hxx:99
iterator operator++(int)
Advance to the next occupied node.
Definition unordered_set.hxx:129
std::ptrdiff_t difference_type
Iterator distance type.
Definition unordered_set.hxx:97
friend class UnorderedSet
Definition unordered_set.hxx:139
void StormByteSafeCursor
Base cursor mark. Copying the cursor copies one node pointer.
Definition unordered_set.hxx:100
const K * pointer
Pointer to the value.
Definition unordered_set.hxx:98
std::forward_iterator_tag iterator_category
Iterator category.
Definition unordered_set.hxx:94
bool operator==(const iterator &other) const noexcept
Compare node identity.
Definition unordered_set.hxx:136
iterator() noexcept=default
Construct a singular iterator.
std::forward_iterator_tag iterator_concept
C++20 iterator concept.
Definition unordered_set.hxx:95
iterator & operator++()
Advance to the next occupied node.
Definition unordered_set.hxx:123
pointer operator->() const
Return a pointer to the value.
Definition unordered_set.hxx:117
K value_type
Stored value.
Definition unordered_set.hxx:96
Owning handle to one extracted Base node.
Definition unordered_set.hxx:214
bool empty() const noexcept
Test whether the handle owns a node.
Definition unordered_set.hxx:254
friend class UnorderedSet
Definition unordered_set.hxx:275
node_type() noexcept=default
Construct an empty handle.
void swap(node_type &other) noexcept
Exchange owned nodes.
Definition unordered_set.hxx:272
const K & value() const
Return the owned value.
Definition unordered_set.hxx:266
Unique values stored in a Base-heap hash table.
Definition unordered_set.hxx:75
key_equal key_eq() const
Return the stored equality predicate.
void rehash(size_type buckets)
Replace the bucket array.
size_type size() const noexcept
Return the number of values.
iterator emplace_hint(const_iterator hint, Args &&... args)
Construct a value.
iterator erase(const_iterator position)
Erase the value at a read-only iterator.
void swap(UnorderedSet &other) noexcept
Exchange tables.
insert_result emplace(Args &&... args)
Construct a value in a new node if it is absent.
size_type max_size() const noexcept
Return the maximum number of values.
STORMBYTE_FORCE_INLINE UnorderedSet(std::unordered_set< K > &&other)
Move values from a caller-owned STL set and leave it empty.
Definition unordered_set.hxx:399
const_iterator find(const K &value) const
Find a value.
size_type count(const K &value) const
Count matching values.
size_type erase(const K &value)
Erase a value.
iterator erase(const_iterator first, const_iterator last)
Erase [first, last).
iterator find(const K &value)
Find a value.
size_type bucket_count() const noexcept
Return the bucket count.
Pair< iterator, bool > insert_result
Iterator to the value and whether it was inserted.
Definition unordered_set.hxx:206
UnorderedSet() noexcept
Construct an empty set.
size_type bucket(const K &value) const
Return the bucket of value.
bool empty() const noexcept
Test whether the set has no values.
node_type extract(const K &value)
Unlink value and return that node.
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.
const K & const_reference
Read-only value reference.
Definition unordered_set.hxx:86
void reserve(size_type count)
Reserve room for count values without exceeding the load factor.
const K & reference
Read-only value reference.
Definition unordered_set.hxx:85
float max_load_factor() const noexcept
Return the load factor that triggers a rehash.
Size size_type
Element count. Size, not std::size_t.
Definition unordered_set.hxx:83
size_type bucket_size(size_type index) const
Return the number of values in index.
std::ptrdiff_t difference_type
Iterator distance type.
Definition unordered_set.hxx:84
KeyEqual key_equal
Value equality.
Definition unordered_set.hxx:82
node_type extract(const_iterator position)
Unlink the value at position and return that node.
STORMBYTE_FORCE_INLINE void insert_range(R &&range)
Insert a copy of range.
Definition unordered_set.hxx:535
iterator end() noexcept
Return the past-the-end iterator.
Hash hasher
Value hash.
Definition unordered_set.hxx:81
Pair< iterator, iterator > equal_range(const K &value)
Return the range of values equal to value.
void clear() noexcept
Destroy every value.
float load_factor() const noexcept
Return the current load factor.
iterator erase(iterator position)
Erase the value at an iterator.
insert_result insert(const K &value)
Insert a value if it is absent.
iterator begin() noexcept
Return an iterator to the first occupied node.
const_iterator cbegin() const noexcept
Return an iterator to the first occupied node.
Pair< const_iterator, const_iterator > equal_range(const K &value) const
Return the range of values equal to value.
K key_type
Value and lookup type.
Definition unordered_set.hxx:79
K value_type
Stored value.
Definition unordered_set.hxx:80
const_iterator cend() const noexcept
Return the past-the-end iterator.
bool contains(const K &value) const
Test whether a value is present.
hasher hash_function() const
Return the stored hash.
void merge(UnorderedSet< K, OtherHash, OtherEqual > &source)
Take unique values from source.
Count of abstract units (uint64_t storage).
Definition size.hxx:107
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.
STL namespace.
#define STORMBYTE_FORCE_INLINE
Definition platform.h:134
Cross-module hash.
Definition hash.hxx:95
Result of inserting an extracted node.
Definition unordered_set.hxx:283
iterator position
Value, or end when the node was not inserted and is empty.
Definition unordered_set.hxx:284
bool inserted
Whether the node was linked.
Definition unordered_set.hxx:285
node_type node
Returned node when the value was already present.
Definition unordered_set.hxx:286
#define STORMBYTE_PUBLIC_TYPE
Definition visibility.h:57
#define STORMBYTE_PUBLIC
Definition visibility.h:52