2 * Copyright (C) 2024-2026 David C. Manuelda (StormBytePP)
4 * This is the base for StormByte Suite libraries.
6 * StormByte original source is dual-licensed:
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)
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>).
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.
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.
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.
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>.
37 * SPDX-License-Identifier: LGPL-3.0-or-later OR LicenseRef-StormByte-Commercial
44 template<Type::SafeValue K, class Hash, class KeyEqual>
45 UnorderedSet<K, Hash, KeyEqual>::UnorderedSet() noexcept = default;
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) {}
50 template<Type::SafeValue K, class Hash, class KeyEqual>
51 UnorderedSet<K, Hash, KeyEqual>::UnorderedSet(const UnorderedSet& other): m_values(other.m_values) {}
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)) {}
56 template<Type::SafeValue K, class Hash, class KeyEqual>
57 UnorderedSet<K, Hash, KeyEqual>::~UnorderedSet() = default;
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;
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);
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);
80 template<Type::SafeValue K, class Hash, class KeyEqual>
81 template<class InputIt>
82 UnorderedSet<K, Hash, KeyEqual>::UnorderedSet(InputIt first, InputIt last) {
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) {
92 template<Type::SafeValue K, class Hash, class KeyEqual>
93 UnorderedSet<K, Hash, KeyEqual>::UnorderedSet(std::initializer_list<K> values) {
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) {
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(); }
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(); }
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()); }
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()); }
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(); }
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()); }
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()); }
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(); }
126 template<Type::SafeValue K, class Hash, class KeyEqual>
127 bool UnorderedSet<K, Hash, KeyEqual>::empty() const noexcept { return m_values.empty(); }
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(); }
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(); }
135 template<Type::SafeValue K, class Hash, class KeyEqual>
136 void UnorderedSet<K, Hash, KeyEqual>::clear() noexcept { m_values.clear(); }
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};
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};
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;
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;
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));
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()); }
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)...));
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)...));
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))};
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;
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));
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));
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)) {
215 auto next = std::next(cursor);
216 if constexpr (std::same_as<Hash, OtherHash> && std::same_as<KeyEqual, OtherEqual>)
217 insert(source.extract(cursor));
220 source.erase(cursor);
221 insert(std::move(value));
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));
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));
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) {
240 return first == end() ? end() : find(*first);
241 iterator result = end();
242 while (first != last) {
243 const_iterator current = first;
245 result = erase(current);
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); }
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); }
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)); }
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)); }
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); }
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); }
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);
272 return Pair<iterator, iterator>{end(), end()};
273 iterator next = found;
275 return Pair<iterator, iterator>{found, next};
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);
282 return Pair<const_iterator, const_iterator>{end(), end()};
283 const_iterator next = found;
285 return Pair<const_iterator, const_iterator>{found, next};
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(); }
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); }
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); }
297 template<Type::SafeValue K, class Hash, class KeyEqual>
298 float UnorderedSet<K, Hash, KeyEqual>::load_factor() const noexcept { return m_values.load_factor(); }
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(); }
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); }
306 template<Type::SafeValue K, class Hash, class KeyEqual>
307 void UnorderedSet<K, Hash, KeyEqual>::rehash(size_type buckets) { m_values.rehash(buckets); }
309 template<Type::SafeValue K, class Hash, class KeyEqual>
310 void UnorderedSet<K, Hash, KeyEqual>::reserve(size_type count) { m_values.reserve(count); }
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; }
315 template<Type::SafeValue K, class Hash, class KeyEqual>
316 bool UnorderedSet<K, Hash, KeyEqual>::operator!=(const UnorderedSet& other) const { return !(*this == other); }