StormByte 3.0.0
C++26 foundation of the StormByte suite
Loading...
Searching...
No Matches
unordered_set.txx
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
42namespace StormByte {
43 namespace Safe {
44 template<Type::SafeValue K, class Hash, class KeyEqual>
45 UnorderedSet<K, Hash, KeyEqual>::UnorderedSet() noexcept = default;
46
47 template<Type::SafeValue K, class Hash, class KeyEqual>
48 UnorderedSet<K, Hash, KeyEqual>::UnorderedSet(size_type buckets, const Hash& hash, const KeyEqual& equal): m_values(buckets, hash, equal) {}
49
50 template<Type::SafeValue K, class Hash, class KeyEqual>
51 UnorderedSet<K, Hash, KeyEqual>::UnorderedSet(const UnorderedSet& other): m_values(other.m_values) {}
52
53 template<Type::SafeValue K, class Hash, class KeyEqual>
54 UnorderedSet<K, Hash, KeyEqual>::UnorderedSet(UnorderedSet&& other) noexcept: m_values(std::move(other.m_values)) {}
55
56 template<Type::SafeValue K, class Hash, class KeyEqual>
57 UnorderedSet<K, Hash, KeyEqual>::~UnorderedSet() = default;
58
59 template<Type::SafeValue K, class Hash, class KeyEqual>
60 UnorderedSet<K, Hash, KeyEqual>& UnorderedSet<K, Hash, KeyEqual>::operator=(const UnorderedSet& other) {
61 m_values = other.m_values;
62 return *this;
63 }
64
65 template<Type::SafeValue K, class Hash, class KeyEqual>
66 UnorderedSet<K, Hash, KeyEqual>& UnorderedSet<K, Hash, KeyEqual>::operator=(UnorderedSet&& other) noexcept {
67 m_values = std::move(other.m_values);
68 return *this;
69 }
70
71 template<Type::SafeValue K, class Hash, class KeyEqual>
72 UnorderedSet<K, Hash, KeyEqual>& UnorderedSet<K, Hash, KeyEqual>::operator=(std::initializer_list<K> values) {
73 UnorderedSet replacement(bucket_count(), hash_function(), key_eq());
74 replacement.max_load_factor(max_load_factor());
75 replacement.insert(values);
76 swap(replacement);
77 return *this;
78 }
79
80 template<Type::SafeValue K, class Hash, class KeyEqual>
81 template<class InputIt>
82 UnorderedSet<K, Hash, KeyEqual>::UnorderedSet(InputIt first, InputIt last) {
83 insert(first, last);
84 }
85
86 template<Type::SafeValue K, class Hash, class KeyEqual>
87 template<class InputIt>
88 UnorderedSet<K, Hash, KeyEqual>::UnorderedSet(InputIt first, InputIt last, size_type buckets, const Hash& hash, const KeyEqual& equal): m_values(buckets, hash, equal) {
89 insert(first, last);
90 }
91
92 template<Type::SafeValue K, class Hash, class KeyEqual>
93 UnorderedSet<K, Hash, KeyEqual>::UnorderedSet(std::initializer_list<K> values) {
94 insert(values);
95 }
96
97 template<Type::SafeValue K, class Hash, class KeyEqual>
98 UnorderedSet<K, Hash, KeyEqual>::UnorderedSet(std::initializer_list<K> values, size_type buckets, const Hash& hash, const KeyEqual& equal): m_values(buckets, hash, equal) {
99 insert(values);
100 }
101
102 template<Type::SafeValue K, class Hash, class KeyEqual>
103 typename UnorderedSet<K, Hash, KeyEqual>::hasher UnorderedSet<K, Hash, KeyEqual>::hash_function() const { return m_values.hash_function(); }
104
105 template<Type::SafeValue K, class Hash, class KeyEqual>
106 typename UnorderedSet<K, Hash, KeyEqual>::key_equal UnorderedSet<K, Hash, KeyEqual>::key_eq() const { return m_values.key_eq(); }
107
108 template<Type::SafeValue K, class Hash, class KeyEqual>
109 typename UnorderedSet<K, Hash, KeyEqual>::iterator UnorderedSet<K, Hash, KeyEqual>::begin() noexcept { return iterator(m_values.begin()); }
110
111 template<Type::SafeValue K, class Hash, class KeyEqual>
112 typename UnorderedSet<K, Hash, KeyEqual>::const_iterator UnorderedSet<K, Hash, KeyEqual>::begin() const noexcept { return const_iterator(m_values.begin()); }
113
114 template<Type::SafeValue K, class Hash, class KeyEqual>
115 typename UnorderedSet<K, Hash, KeyEqual>::const_iterator UnorderedSet<K, Hash, KeyEqual>::cbegin() const noexcept { return begin(); }
116
117 template<Type::SafeValue K, class Hash, class KeyEqual>
118 typename UnorderedSet<K, Hash, KeyEqual>::iterator UnorderedSet<K, Hash, KeyEqual>::end() noexcept { return iterator(m_values.end()); }
119
120 template<Type::SafeValue K, class Hash, class KeyEqual>
121 typename UnorderedSet<K, Hash, KeyEqual>::const_iterator UnorderedSet<K, Hash, KeyEqual>::end() const noexcept { return const_iterator(m_values.end()); }
122
123 template<Type::SafeValue K, class Hash, class KeyEqual>
124 typename UnorderedSet<K, Hash, KeyEqual>::const_iterator UnorderedSet<K, Hash, KeyEqual>::cend() const noexcept { return end(); }
125
126 template<Type::SafeValue K, class Hash, class KeyEqual>
127 bool UnorderedSet<K, Hash, KeyEqual>::empty() const noexcept { return m_values.empty(); }
128
129 template<Type::SafeValue K, class Hash, class KeyEqual>
130 typename UnorderedSet<K, Hash, KeyEqual>::size_type UnorderedSet<K, Hash, KeyEqual>::size() const noexcept { return m_values.size(); }
131
132 template<Type::SafeValue K, class Hash, class KeyEqual>
133 typename UnorderedSet<K, Hash, KeyEqual>::size_type UnorderedSet<K, Hash, KeyEqual>::max_size() const noexcept { return m_values.max_size(); }
134
135 template<Type::SafeValue K, class Hash, class KeyEqual>
136 void UnorderedSet<K, Hash, KeyEqual>::clear() noexcept { m_values.clear(); }
137
138 template<Type::SafeValue K, class Hash, class KeyEqual>
139 typename UnorderedSet<K, Hash, KeyEqual>::insert_result UnorderedSet<K, Hash, KeyEqual>::insert(const K& value) {
140 auto result = m_values.emplace(value, Monostate{});
141 return insert_result{iterator(result.first), result.second};
142 }
143
144 template<Type::SafeValue K, class Hash, class KeyEqual>
145 typename UnorderedSet<K, Hash, KeyEqual>::insert_result UnorderedSet<K, Hash, KeyEqual>::insert(K&& value) {
146 auto result = m_values.emplace(std::move(value), Monostate{});
147 return insert_result{iterator(result.first), result.second};
148 }
149
150 template<Type::SafeValue K, class Hash, class KeyEqual>
151 typename UnorderedSet<K, Hash, KeyEqual>::iterator UnorderedSet<K, Hash, KeyEqual>::insert(const_iterator, const K& value) {
152 return insert(value).first;
153 }
154
155 template<Type::SafeValue K, class Hash, class KeyEqual>
156 typename UnorderedSet<K, Hash, KeyEqual>::iterator UnorderedSet<K, Hash, KeyEqual>::insert(const_iterator, K&& value) {
157 return insert(std::move(value)).first;
158 }
159
160 template<Type::SafeValue K, class Hash, class KeyEqual>
161 template<class InputIt>
162 void UnorderedSet<K, Hash, KeyEqual>::insert(InputIt first, InputIt last) {
163 for (; first != last; ++first)
164 insert(value_type(*first));
165 }
166
167 template<Type::SafeValue K, class Hash, class KeyEqual>
168 void UnorderedSet<K, Hash, KeyEqual>::insert(std::initializer_list<K> values) { insert(values.begin(), values.end()); }
169
170 template<Type::SafeValue K, class Hash, class KeyEqual>
171 template<class... Args>
172 typename UnorderedSet<K, Hash, KeyEqual>::insert_result UnorderedSet<K, Hash, KeyEqual>::emplace(Args&&... args) {
173 return insert(K(std::forward<Args>(args)...));
174 }
175
176 template<Type::SafeValue K, class Hash, class KeyEqual>
177 template<class... Args>
178 typename UnorderedSet<K, Hash, KeyEqual>::iterator UnorderedSet<K, Hash, KeyEqual>::emplace_hint(const_iterator hint, Args&&... args) {
179 return insert(hint, K(std::forward<Args>(args)...));
180 }
181
182 template<Type::SafeValue K, class Hash, class KeyEqual>
183 typename UnorderedSet<K, Hash, KeyEqual>::insert_return_type UnorderedSet<K, Hash, KeyEqual>::insert(node_type&& handle) {
184 auto result = m_values.insert(std::move(handle.m_node));
185 return insert_return_type{iterator(result.position), result.inserted, node_type(std::move(result.node))};
186 }
187
188 template<Type::SafeValue K, class Hash, class KeyEqual>
189 typename UnorderedSet<K, Hash, KeyEqual>::iterator UnorderedSet<K, Hash, KeyEqual>::insert(const_iterator, node_type&& handle) {
190 auto result = insert(std::move(handle));
191 if (!result.inserted)
192 handle = std::move(result.node);
193 return result.position;
194 }
195
196 template<Type::SafeValue K, class Hash, class KeyEqual>
197 typename UnorderedSet<K, Hash, KeyEqual>::node_type UnorderedSet<K, Hash, KeyEqual>::extract(const_iterator position) {
198 return node_type(m_values.extract(position.m_cursor));
199 }
200
201 template<Type::SafeValue K, class Hash, class KeyEqual>
202 typename UnorderedSet<K, Hash, KeyEqual>::node_type UnorderedSet<K, Hash, KeyEqual>::extract(const K& value) {
203 return node_type(m_values.extract(value));
204 }
205
206 template<Type::SafeValue K, class Hash, class KeyEqual>
207 template<class OtherHash, class OtherEqual>
208 void UnorderedSet<K, Hash, KeyEqual>::merge(UnorderedSet<K, OtherHash, OtherEqual>& source) {
209 auto cursor = source.begin();
210 while (cursor != source.end()) {
211 if (contains(*cursor)) {
212 ++cursor;
213 continue;
214 }
215 auto next = std::next(cursor);
216 if constexpr (std::same_as<Hash, OtherHash> && std::same_as<KeyEqual, OtherEqual>)
217 insert(source.extract(cursor));
218 else {
219 K value = *cursor;
220 source.erase(cursor);
221 insert(std::move(value));
222 }
223 cursor = next;
224 }
225 }
226
227 template<Type::SafeValue K, class Hash, class KeyEqual>
228 typename UnorderedSet<K, Hash, KeyEqual>::iterator UnorderedSet<K, Hash, KeyEqual>::erase(iterator position) {
229 return iterator(m_values.erase(position.m_cursor));
230 }
231
232 template<Type::SafeValue K, class Hash, class KeyEqual>
233 typename UnorderedSet<K, Hash, KeyEqual>::iterator UnorderedSet<K, Hash, KeyEqual>::erase(const_iterator position) {
234 return iterator(m_values.erase(position.m_cursor));
235 }
236
237 template<Type::SafeValue K, class Hash, class KeyEqual>
238 typename UnorderedSet<K, Hash, KeyEqual>::iterator UnorderedSet<K, Hash, KeyEqual>::erase(const_iterator first, const_iterator last) {
239 if (first == last)
240 return first == end() ? end() : find(*first);
241 iterator result = end();
242 while (first != last) {
243 const_iterator current = first;
244 ++first;
245 result = erase(current);
246 }
247 return result;
248 }
249
250 template<Type::SafeValue K, class Hash, class KeyEqual>
251 typename UnorderedSet<K, Hash, KeyEqual>::size_type UnorderedSet<K, Hash, KeyEqual>::erase(const K& value) { return m_values.erase(value); }
252
253 template<Type::SafeValue K, class Hash, class KeyEqual>
254 void UnorderedSet<K, Hash, KeyEqual>::swap(UnorderedSet& other) noexcept { m_values.swap(other.m_values); }
255
256 template<Type::SafeValue K, class Hash, class KeyEqual>
257 typename UnorderedSet<K, Hash, KeyEqual>::iterator UnorderedSet<K, Hash, KeyEqual>::find(const K& value) { return iterator(m_values.find(value)); }
258
259 template<Type::SafeValue K, class Hash, class KeyEqual>
260 typename UnorderedSet<K, Hash, KeyEqual>::const_iterator UnorderedSet<K, Hash, KeyEqual>::find(const K& value) const { return const_iterator(m_values.find(value)); }
261
262 template<Type::SafeValue K, class Hash, class KeyEqual>
263 typename UnorderedSet<K, Hash, KeyEqual>::size_type UnorderedSet<K, Hash, KeyEqual>::count(const K& value) const { return m_values.count(value); }
264
265 template<Type::SafeValue K, class Hash, class KeyEqual>
266 bool UnorderedSet<K, Hash, KeyEqual>::contains(const K& value) const { return m_values.contains(value); }
267
268 template<Type::SafeValue K, class Hash, class KeyEqual>
269 Pair<typename UnorderedSet<K, Hash, KeyEqual>::iterator, typename UnorderedSet<K, Hash, KeyEqual>::iterator> UnorderedSet<K, Hash, KeyEqual>::equal_range(const K& value) {
270 iterator found = find(value);
271 if (found == end())
272 return Pair<iterator, iterator>{end(), end()};
273 iterator next = found;
274 ++next;
275 return Pair<iterator, iterator>{found, next};
276 }
277
278 template<Type::SafeValue K, class Hash, class KeyEqual>
279 Pair<typename UnorderedSet<K, Hash, KeyEqual>::const_iterator, typename UnorderedSet<K, Hash, KeyEqual>::const_iterator> UnorderedSet<K, Hash, KeyEqual>::equal_range(const K& value) const {
280 const_iterator found = find(value);
281 if (found == end())
282 return Pair<const_iterator, const_iterator>{end(), end()};
283 const_iterator next = found;
284 ++next;
285 return Pair<const_iterator, const_iterator>{found, next};
286 }
287
288 template<Type::SafeValue K, class Hash, class KeyEqual>
289 typename UnorderedSet<K, Hash, KeyEqual>::size_type UnorderedSet<K, Hash, KeyEqual>::bucket_count() const noexcept { return m_values.bucket_count(); }
290
291 template<Type::SafeValue K, class Hash, class KeyEqual>
292 typename UnorderedSet<K, Hash, KeyEqual>::size_type UnorderedSet<K, Hash, KeyEqual>::bucket_size(size_type index) const { return m_values.bucket_size(index); }
293
294 template<Type::SafeValue K, class Hash, class KeyEqual>
295 typename UnorderedSet<K, Hash, KeyEqual>::size_type UnorderedSet<K, Hash, KeyEqual>::bucket(const K& value) const { return m_values.bucket(value); }
296
297 template<Type::SafeValue K, class Hash, class KeyEqual>
298 float UnorderedSet<K, Hash, KeyEqual>::load_factor() const noexcept { return m_values.load_factor(); }
299
300 template<Type::SafeValue K, class Hash, class KeyEqual>
301 float UnorderedSet<K, Hash, KeyEqual>::max_load_factor() const noexcept { return m_values.max_load_factor(); }
302
303 template<Type::SafeValue K, class Hash, class KeyEqual>
304 void UnorderedSet<K, Hash, KeyEqual>::max_load_factor(float factor) noexcept { m_values.max_load_factor(factor); }
305
306 template<Type::SafeValue K, class Hash, class KeyEqual>
307 void UnorderedSet<K, Hash, KeyEqual>::rehash(size_type buckets) { m_values.rehash(buckets); }
308
309 template<Type::SafeValue K, class Hash, class KeyEqual>
310 void UnorderedSet<K, Hash, KeyEqual>::reserve(size_type count) { m_values.reserve(count); }
311
312 template<Type::SafeValue K, class Hash, class KeyEqual>
313 bool UnorderedSet<K, Hash, KeyEqual>::operator==(const UnorderedSet& other) const { return m_values == other.m_values; }
314
315 template<Type::SafeValue K, class Hash, class KeyEqual>
316 bool UnorderedSet<K, Hash, KeyEqual>::operator!=(const UnorderedSet& other) const { return !(*this == other); }
317 }
318}