StormByte 3.0.0
C++26 foundation of the StormByte suite
Loading...
Searching...
No Matches
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 <set>
53#include <utility>
54
59namespace StormByte {
64 namespace Safe {
73 template<Type::SafeValue K, class Compare = std::less<K>>
74 requires std::strict_weak_order<Compare, const K&, const K&>
76 using Storage = Map<K, Monostate, Compare>;
77
78 public:
79 using key_type = K;
80 using value_type = K;
81 using key_compare = Compare;
82 using value_compare = Compare;
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::bidirectional_iterator_tag;
95 using iterator_concept = std::bidirectional_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
135 iterator& operator--() { --m_cursor; return *this; }
136
141 iterator operator--(int) { iterator previous = *this; --*this; return previous; }
142
148 bool operator==(const iterator& other) const noexcept { return m_cursor == other.m_cursor; }
149
150 private:
151 friend class Set;
152 explicit iterator(typename Storage::iterator cursor) noexcept: m_cursor(cursor) {}
153 typename Storage::iterator m_cursor;
154 };
155
161 public:
162 using iterator_category = std::bidirectional_iterator_tag;
163 using iterator_concept = std::bidirectional_iterator_tag;
164 using value_type = K;
165 using difference_type = std::ptrdiff_t;
166 using pointer = const K*;
167 using reference = const K&;
168 using StormByteSafeCursor = void;
169
173 const_iterator() noexcept = default;
174
179 const_iterator(iterator other) noexcept: m_cursor(other.m_cursor) {}
180
185 reference operator*() const { return m_cursor->first; }
186
191 pointer operator->() const { return &m_cursor->first; }
192
197 const_iterator& operator++() { ++m_cursor; return *this; }
198
203 const_iterator operator++(int) { const_iterator previous = *this; ++*this; return previous; }
204
209 const_iterator& operator--() { --m_cursor; return *this; }
210
215 const_iterator operator--(int) { const_iterator previous = *this; --*this; return previous; }
216
222 bool operator==(const const_iterator& other) const noexcept { return m_cursor == other.m_cursor; }
223
224 private:
225 friend class Set;
226 explicit const_iterator(typename Storage::const_iterator cursor) noexcept: m_cursor(cursor) {}
227 typename Storage::const_iterator m_cursor;
228 };
229
230 using reverse_iterator = std::reverse_iterator<iterator>;
231 using const_reverse_iterator = std::reverse_iterator<const_iterator>;
233
240 class node_type {
241 public:
245 node_type() noexcept = default;
246
251 node_type(node_type&& other) noexcept = default;
252
258 node_type& operator=(node_type&& other) noexcept = default;
259
263 node_type(const node_type&) = delete;
264
269 node_type& operator=(const node_type&) = delete;
270
274 ~node_type() = default;
275
280 bool empty() const noexcept { return m_node.empty(); }
281
286 explicit operator bool() const noexcept { return !empty(); }
287
292 const K& value() const { return m_node.key(); }
293
298 void swap(node_type& other) noexcept { m_node.swap(other.m_node); }
299
300 private:
301 friend class Set;
302 explicit node_type(typename Storage::node_type node) noexcept: m_node(std::move(node)) {}
303 typename Storage::node_type m_node;
304 };
305
314
319
324 explicit Set(const Compare& compare);
325
331 Set(const Set& other);
332
337 Set(Set&& other);
338
343
350 Set& operator=(const Set& other);
351
357 Set& operator=(Set&& other) noexcept;
358
365 Set& operator=(std::initializer_list<K> values);
366
374 template<class InputIt>
375 Set(InputIt first, InputIt last);
376
385 template<class InputIt>
386 Set(InputIt first, InputIt last, const Compare& compare);
387
393 Set(std::initializer_list<K> values);
394
401 Set(std::initializer_list<K> values, const Compare& compare);
402
408
414
419 iterator begin() noexcept;
420
425 const_iterator begin() const noexcept;
426
431 const_iterator cbegin() const noexcept;
432
437 iterator end() noexcept;
438
443 const_iterator end() const noexcept;
444
449 const_iterator cend() const noexcept;
450
456
462
468
474
479 const_reverse_iterator rend() const noexcept;
480
486
491 bool empty() const noexcept;
492
497 size_type size() const noexcept;
498
503 size_type max_size() const noexcept;
504
508 void clear() noexcept;
509
516 insert_result insert(const K& value);
517
525
533 iterator insert(const_iterator hint, const K& value);
534
543
551 template<class InputIt>
552 void insert(InputIt first, InputIt last);
553
559 void insert(std::initializer_list<K> values);
560
567 template<std::ranges::input_range R>
568 requires std::convertible_to<std::ranges::range_reference_t<R>, value_type>
570 for (auto&& value : range)
571 insert(value_type(std::forward<decltype(value)>(value)));
572 }
573
581 template<class... Args>
582 insert_result emplace(Args&&... args);
583
592 template<class... Args>
593 iterator emplace_hint(const_iterator hint, Args&&... args);
594
601
609
616
622 node_type extract(const K& value);
623
630 template<class OtherCompare>
632
638 iterator erase(iterator position) noexcept;
639
645 iterator erase(const_iterator position) noexcept;
646
654
660 size_type erase(const K& value) noexcept;
661
666 void swap(Set& other) noexcept;
667
673 iterator find(const K& value);
674
680 const_iterator find(const K& value) const;
681
687 size_type count(const K& value) const;
688
694 bool contains(const K& value) const;
695
701 iterator lower_bound(const K& value);
702
708 const_iterator lower_bound(const K& value) const;
709
715 iterator upper_bound(const K& value);
716
722 const_iterator upper_bound(const K& value) const;
723
730
737
743 bool operator==(const Set& other) const;
744
750 bool operator!=(const Set& other) const;
751
757 bool operator<(const Set& other) const;
758
764 bool operator<=(const Set& other) const;
765
771 bool operator>(const Set& other) const;
772
778 bool operator>=(const Set& other) const;
779
784 STORMBYTE_FORCE_INLINE explicit operator std::set<K, Compare>() const {
785 std::set<K, Compare> exported(key_comp());
786 for (const K& value : *this)
787 exported.insert(value);
788 return exported;
789 }
790
791 private:
792 Storage m_values;
793 };
794
802 template<Type::SafeValue K, class Compare>
803 inline void swap(Set<K, Compare>& left, Set<K, Compare>& right) noexcept {
804 left.swap(right);
805 }
806 }
807}
808
810extern template class STORMBYTE_PUBLIC StormByte::Safe::Set<bool>;
811extern template class STORMBYTE_PUBLIC StormByte::Safe::Set<char>;
820extern template class STORMBYTE_PUBLIC StormByte::Safe::Set<int>;
822extern template class STORMBYTE_PUBLIC StormByte::Safe::Set<long>;
827
828#include <StormByte/safe/set.txx>
830
Ordered unique-key map stored on Base's heap.
Definition map.hxx:78
BasicIterator< true > const_iterator
Definition map.hxx:211
BasicIterator< false > iterator
Definition map.hxx:210
std::pair whose members keep their own Safe storage.
Definition pair.hxx:73
Read-only bidirectional cursor.
Definition set.hxx:160
const K & reference
Reference to the key.
Definition set.hxx:167
std::bidirectional_iterator_tag iterator_category
Iterator category.
Definition set.hxx:162
reference operator*() const
Return the key.
Definition set.hxx:185
const_iterator operator--(int)
Move to the previous key.
Definition set.hxx:215
std::ptrdiff_t difference_type
Iterator distance type.
Definition set.hxx:165
K value_type
Stored value.
Definition set.hxx:164
const_iterator & operator++()
Advance to the next key.
Definition set.hxx:197
const_iterator() noexcept=default
Construct a singular iterator.
pointer operator->() const
Return a pointer to the key.
Definition set.hxx:191
const_iterator & operator--()
Move to the previous key.
Definition set.hxx:209
friend class Set
Definition set.hxx:225
void StormByteSafeCursor
Base cursor mark. Copying the cursor copies one node pointer.
Definition set.hxx:168
const_iterator operator++(int)
Advance to the next key.
Definition set.hxx:203
const K * pointer
Pointer to the key.
Definition set.hxx:166
bool operator==(const const_iterator &other) const noexcept
Compare node identity.
Definition set.hxx:222
std::bidirectional_iterator_tag iterator_concept
C++20 iterator concept.
Definition set.hxx:163
Bidirectional cursor.
Definition set.hxx:92
const K * pointer
Pointer to the key.
Definition set.hxx:98
pointer operator->() const
Return a pointer to the key.
Definition set.hxx:117
std::bidirectional_iterator_tag iterator_concept
C++20 iterator concept.
Definition set.hxx:95
iterator & operator--()
Move to the previous key.
Definition set.hxx:135
bool operator==(const iterator &other) const noexcept
Compare node identity.
Definition set.hxx:148
void StormByteSafeCursor
Base cursor mark. Copying the cursor copies one node pointer.
Definition set.hxx:100
friend class Set
Definition set.hxx:151
K value_type
Stored value.
Definition set.hxx:96
std::bidirectional_iterator_tag iterator_category
Iterator category.
Definition set.hxx:94
iterator operator++(int)
Advance to the next key.
Definition set.hxx:129
iterator & operator++()
Advance to the next key.
Definition set.hxx:123
iterator operator--(int)
Move to the previous key.
Definition set.hxx:141
const K & reference
Reference to the key.
Definition set.hxx:99
iterator() noexcept=default
Construct a singular iterator.
std::ptrdiff_t difference_type
Iterator distance type.
Definition set.hxx:97
Owning handle to one extracted Base node.
Definition set.hxx:240
friend class Set
Definition set.hxx:301
void swap(node_type &other) noexcept
Exchange owned nodes.
Definition set.hxx:298
node_type() noexcept=default
Construct an empty handle.
const K & value() const
Return the owned value.
Definition set.hxx:292
bool empty() const noexcept
Test whether the handle owns a node.
Definition set.hxx:280
Ordered unique values stored on Base's heap.
Definition set.hxx:75
node_type extract(const K &value)
Unlink value and return that node.
K key_type
Value and lookup type.
Definition set.hxx:79
iterator upper_bound(const K &value)
Return the first value greater than value.
reverse_iterator rbegin() noexcept
Return a reverse iterator to the last value.
iterator insert(const_iterator hint, node_type &&handle)
Insert an extracted node, using hint when the neighbours confirm it.
size_type count(const K &value) const
Count matching values.
bool operator<(const Set &other) const
Compare lexicographically.
Set & operator=(const Set &other)
Copy-assign the values.
iterator find(const K &value)
Find a value.
Set & operator=(std::initializer_list< K > values)
Replace the contents with an initializer list.
const_iterator upper_bound(const K &value) const
Return the first value greater than value.
size_type erase(const K &value) noexcept
Erase a value.
Set(std::initializer_list< K > values, const Compare &compare)
Construct from an initializer list and a comparator.
bool operator==(const Set &other) const
Compare lexicographically.
bool operator<=(const Set &other) const
Compare lexicographically.
Set()
Construct an empty set.
bool empty() const noexcept
Test whether the set has no values.
bool contains(const K &value) const
Test whether a value is present.
iterator erase(const_iterator first, const_iterator last) noexcept
Erase [first, last).
value_compare value_comp() const
Return the ordering.
Pair< const_iterator, const_iterator > equal_range(const K &value) const
Return the range of values equal to value.
STORMBYTE_FORCE_INLINE void insert_range(R &&range)
Insert a copy of range.
Definition set.hxx:569
reverse_iterator rend() noexcept
Return the past-the-start reverse iterator.
key_compare key_comp() const
Return the ordering.
bool operator!=(const Set &other) const
Compare lexicographically.
Pair< iterator, iterator > equal_range(const K &value)
Return the range of values equal to value.
Set & operator=(Set &&other) noexcept
Move-assign the values.
size_type max_size() const noexcept
Return the maximum number of values.
bool operator>=(const Set &other) const
Compare lexicographically.
iterator end() noexcept
Return the past-the-end iterator.
~Set()
Destroy the values.
iterator erase(const_iterator position) noexcept
Erase the value at a read-only iterator.
iterator begin() noexcept
Return an iterator to the first value.
void clear() noexcept
Destroy every value.
Pair< iterator, bool > insert_result
Iterator to the value and whether it was inserted.
Definition set.hxx:232
const_reverse_iterator crend() const noexcept
Return the past-the-start reverse iterator.
Size size_type
Element count. Size, not std::size_t.
Definition set.hxx:83
std::reverse_iterator< iterator > reverse_iterator
Mutable reverse iterator.
Definition set.hxx:230
std::ptrdiff_t difference_type
Iterator distance type.
Definition set.hxx:84
Compare value_compare
Ordering of values. Same as the key ordering.
Definition set.hxx:82
Set(Set &&other)
Take the values.
iterator lower_bound(const K &value)
Return the first value not less than value.
size_type size() const noexcept
Return the number of values.
void swap(Set &other) noexcept
Exchange values and comparators.
Set(const Set &other)
Copy the values.
Compare key_compare
Ordering.
Definition set.hxx:81
Set(const Compare &compare)
Construct an empty set with a comparator.
const_iterator lower_bound(const K &value) const
Return the first value not less than value.
bool operator>(const Set &other) const
Compare lexicographically.
insert_result emplace(Args &&... args)
Construct a value in a new node if it is absent.
const_iterator find(const K &value) const
Find a value.
void merge(Set< K, OtherCompare > &source)
Take unique values from source.
insert_return_type insert(node_type &&handle)
Insert an extracted node if its value is absent.
Set(InputIt first, InputIt last)
Construct from an iterator range.
const_iterator cend() const noexcept
Return the past-the-end iterator.
Set(InputIt first, InputIt last, const Compare &compare)
Construct from an iterator range and a comparator.
iterator erase(iterator position) noexcept
Erase the value at an iterator.
node_type extract(const_iterator position)
Unlink the value at position and return that node.
const_reverse_iterator crbegin() const noexcept
Return a reverse iterator to the last value.
const_iterator cbegin() const noexcept
Return an iterator to the first value.
std::reverse_iterator< const_iterator > const_reverse_iterator
Read-only reverse iterator.
Definition set.hxx:231
const K & reference
Read-only value reference.
Definition set.hxx:85
iterator emplace_hint(const_iterator hint, Args &&... args)
Construct a value, using hint when the neighbours confirm it.
Set(std::initializer_list< K > values)
Construct from an initializer list.
K value_type
Stored value.
Definition set.hxx:80
insert_result insert(const K &value)
Insert a value if it is absent.
const K & const_reference
Read-only value reference.
Definition set.hxx:86
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
Result of inserting an extracted node.
Definition set.hxx:309
node_type node
Returned node when the value was already present.
Definition set.hxx:312
bool inserted
Whether the node was linked.
Definition set.hxx:311
iterator position
Value, or end when the node was not inserted and is empty.
Definition set.hxx:310
#define STORMBYTE_PUBLIC_TYPE
Definition visibility.h:57
#define STORMBYTE_PUBLIC
Definition visibility.h:52