Maipa's Standard Library Extension 1.5.6
mstd
Loading...
Searching...
No Matches
ordered_set.hpp
1/*
2 * mstd - Maipa's Standard Library
3 *
4 * Licensed under the BSD 3-Clause License with Attribution Requirement.
5 * See the LICENSE file for details: https://github.com/MAIPA01/mstd/blob/main/LICENSE
6 *
7 * Copyright (c) 2025, Patryk Antosik (MAIPA01)
8 */
9
10#pragma once
11#ifndef _MSTD_ORDERED_SET_HPP_
12 #define _MSTD_ORDERED_SET_HPP_
13
14 #include <mstd/config.hpp>
15
16 #if !_MSTD_HAS_CXX17
17_MSTD_WARNING("this is only available for c++17 and greater!");
18 #else
19
20 #include <mstd/containers_types.hpp>
21
22namespace mstd {
23 template<class T>
24 class ordered_set {
25 public:
26 using value_type = remove_cvref_t<T>;
27 using iterator = _MSTD_TYPENAME17 std::vector<value_type>::iterator;
28 using const_iterator = _MSTD_TYPENAME17 std::vector<value_type>::const_iterator;
29 using reverse_iterator = _MSTD_TYPENAME17 std::vector<value_type>::reverse_iterator;
30 using const_reverse_iterator = _MSTD_TYPENAME17 std::vector<value_type>::const_reverse_iterator;
31
32 private:
33 std::vector<value_type> _orderedElements;
34 std::unordered_map<value_type, size_t> _elementsMap;
35
36 _MSTD_CONSTEXPR20 void _update_indexes(const size_t from) {
37 static_assert(std::is_copy_constructible_v<value_type>, "Is not copy constructible");
38 for (size_t i = from; i != _orderedElements.size(); ++i) { _elementsMap[_orderedElements[i]] = i; }
39 }
40
41 template<class U>
42 _MSTD_CONSTEXPR20 value_type& _insert(const_iterator where, U&& item) {
43 if (!contains(item)) {
44 size_t whereOffset =
45 std::clamp<size_t>(std::distance(_orderedElements.cbegin(), where), 0, _orderedElements.size());
46
47 _orderedElements.insert(where, std::forward<U>(item));
48
49 _update_indexes(whereOffset);
50 return *std::next(_orderedElements.begin(), whereOffset);
51 }
52
53 size_t whereOffset =
54 std::clamp<size_t>(std::distance(_orderedElements.cbegin(), where), 0, _orderedElements.size() - 1);
55 const size_t& elementOffset = _elementsMap.at(item);
56
57 // remove element
58 _orderedElements.erase(std::next(_orderedElements.cbegin(), elementOffset));
59
60 // insert element where
61 _orderedElements.insert(std::next(_orderedElements.cbegin(), whereOffset), std::forward<U>(item));
62
63 // update iterators
64 if (whereOffset > elementOffset) { _update_indexes(elementOffset); }
65 else { _update_indexes(whereOffset); }
66
67 return *std::next(_orderedElements.begin(), whereOffset);
68 }
69
70 template<class U>
71 _MSTD_CONSTEXPR20 value_type& _insert_back(U&& item) {
72 return insert(cend(), std::forward<U>(item));
73 }
74
75 template<class U>
76 _MSTD_CONSTEXPR20 void _erase(U&& item) {
77 if (!contains(item)) { return; }
78
79 size_t elementOffset = _elementsMap.at(item);
80
81 _orderedElements.erase(std::next(_orderedElements.begin(), elementOffset));
82 _elementsMap.erase(std::forward<U>(item));
83
84 _update_indexes(elementOffset);
85 }
86
87 template<class U>
88 [[nodiscard]] _MSTD_CONSTEXPR20 bool _contains(U&& item) const {
89 #if _MSTD_HAS_CXX20
90 return _elementsMap.contains(std::forward<U>(item));
91 #else
92 return _elementsMap.find(std::forward<U>(item)) != _elementsMap.end();
93 #endif
94 }
95
96 template<class U>
97 [[nodiscard]] _MSTD_CONSTEXPR20 iterator _find(U&& item) {
98 auto it = _elementsMap.find(std::forward<U>(item));
99 return it != _elementsMap.end() ? std::next(_orderedElements.begin(), it->second) : _orderedElements.end();
100 }
101
102 template<class U>
103 [[nodiscard]] _MSTD_CONSTEXPR20 const_iterator _find(U&& item) const {
104 auto it = _elementsMap.find(std::forward<U>(item));
105 return it != _elementsMap.end() ? std::next(_orderedElements.begin(), it->second) : _orderedElements.end();
106 }
107
108 public:
109 _MSTD_CONSTEXPR20 ordered_set() = default;
110
111 _MSTD_CONSTEXPR20 ordered_set(const ordered_set& other) = default;
112 _MSTD_CONSTEXPR20 ordered_set(ordered_set&& other) noexcept = default;
113
114 _MSTD_CONSTEXPR20 ordered_set(std::initializer_list<value_type> init) { insert_back(init.begin(), init.end()); }
115
116 #if _MSTD_HAS_CXX20
117 template<mstd::iterator_of<value_type> Iter>
118 #else
119 template<class Iter, std::enable_if_t<is_iterator_of_v<Iter, value_type>, bool> = true>
120 #endif
121 _MSTD_CONSTEXPR20 ordered_set(Iter begin, Iter end) {
122 insert_back(begin, end);
123 }
124
125 _MSTD_CONSTEXPR20 ~ordered_set() = default;
126
127 _MSTD_CONSTEXPR20 ordered_set& operator=(const ordered_set& other) = default;
128 _MSTD_CONSTEXPR20 ordered_set& operator=(ordered_set&& other) noexcept = default;
129
130 #if _MSTD_HAS_CXX20
131 template<class... Args>
132 #else
133 template<class... Args, std::enable_if_t<std::is_constructible_v<value_type, Args...>, bool> = true>
134 #endif
135 _MSTD_CONSTEXPR20 value_type& emplace(const_iterator where,
136 Args&&... args) _MSTD_REQUIRES((std::constructible_from<value_type, Args...>)) {
137 const size_t whereOffset =
138 std::clamp<size_t>(std::distance(_orderedElements.cbegin(), where), 0, _orderedElements.size());
139
140 _orderedElements.emplace(where, std::forward<Args>(args)...);
141
142 _update_indexes(whereOffset);
143
144 return *std::next(_orderedElements.begin(), whereOffset);
145 }
146
147 #if _MSTD_HAS_CXX20
148 template<class... Args>
149 #else
150 template<class... Args, std::enable_if_t<std::is_constructible_v<value_type, Args...>, bool> = true>
151 #endif
152 _MSTD_CONSTEXPR20 value_type& emplace_back(
153 Args&&... args
154 ) _MSTD_REQUIRES((std::constructible_from<value_type, Args...>)) {
155 return emplace(cend(), std::forward<Args>(args)...);
156 }
157
158 _MSTD_CONSTEXPR20 value_type& insert(const_iterator where, value_type&& item) { return _insert(where, std::move(item)); }
159
160 _MSTD_CONSTEXPR20 value_type& insert(const_iterator where, const value_type& item) { return _insert(where, item); }
161
162 #if _MSTD_HAS_CXX20
163 template<mstd::iterator_of<value_type> Iter>
164 #else
165 template<class Iter, std::enable_if_t<is_iterator_of_v<Iter, value_type>, bool> = true>
166 #endif
167 _MSTD_CONSTEXPR20 void insert(const_iterator where, Iter begin, Iter end) {
168 size_t currWhereOffset = std::distance(_orderedElements.cbegin(), where);
169 for (Iter iter = begin; iter != end; ++iter, ++currWhereOffset) {
170 currWhereOffset = std::clamp<size_t>(currWhereOffset, 0, _orderedElements.size());
171 insert(std::next(_orderedElements.begin(), currWhereOffset), *iter);
172 }
173 }
174
175 _MSTD_CONSTEXPR20 void insert(const_iterator where, std::initializer_list<value_type> init) {
176 insert(where, init.begin(), init.end());
177 }
178
179 _MSTD_CONSTEXPR20 value_type& insert_back(const value_type& item) { return _insert_back(item); }
180
181 _MSTD_CONSTEXPR20 value_type& insert_back(value_type&& item) { return _insert_back(std::move(item)); }
182
183 #if _MSTD_HAS_CXX20
184 template<mstd::iterator_of<value_type> Iter>
185 #else
186 template<class Iter, std::enable_if_t<is_iterator_of_v<Iter, value_type>, bool> = true>
187 #endif
188 _MSTD_CONSTEXPR20 void insert_back(Iter begin, Iter end) {
189 insert(cend(), begin, end);
190 }
191
192 _MSTD_CONSTEXPR20 void insert_back(std::initializer_list<value_type> init) { insert_back(init.begin(), init.end()); }
193
194 _MSTD_CONSTEXPR20 void erase(const value_type& item) { _erase(item); }
195
196 _MSTD_CONSTEXPR20 void erase(value_type&& item) { _erase(std::move(item)); }
197
198 [[nodiscard]] _MSTD_CONSTEXPR20 bool contains(const value_type& item) const { return _contains(item); }
199
200 [[nodiscard]] _MSTD_CONSTEXPR20 bool contains(value_type&& item) const { return _contains(std::move(item)); }
201
202 [[nodiscard]] _MSTD_CONSTEXPR20 iterator find(const value_type& item) { return _find(item); }
203
204 [[nodiscard]] _MSTD_CONSTEXPR20 iterator find(value_type&& item) { return _find(std::move(item)); }
205
206 [[nodiscard]] _MSTD_CONSTEXPR20 const_iterator find(const value_type& item) const { return _find(item); }
207
208 // [[nodiscard]] _MSTD_CONSTEXPR20 const_iterator find(value_type&& item) const {
209 // return _find(std::move(item));
210 // }
211
212 [[nodiscard]] _MSTD_CONSTEXPR20 size_t size() const { return _orderedElements.size(); }
213
214 [[nodiscard]] _MSTD_CONSTEXPR20 bool empty() const { return _orderedElements.empty(); }
215
216 _MSTD_CONSTEXPR20 void clear() {
217 _orderedElements.clear();
218 _elementsMap.clear();
219 }
220
221 [[nodiscard]] _MSTD_CONSTEXPR20 value_type& front() { return _orderedElements.front(); }
222
223 [[nodiscard]] _MSTD_CONSTEXPR20 const value_type& front() const { return _orderedElements.front(); }
224
225 [[nodiscard]] _MSTD_CONSTEXPR20 value_type& back() { return _orderedElements.back(); }
226
227 [[nodiscard]] _MSTD_CONSTEXPR20 const value_type& back() const { return _orderedElements.back(); }
228
229 [[nodiscard]] _MSTD_CONSTEXPR20 value_type& at(const size_t idx) { return _orderedElements.at(idx); }
230
231 [[nodiscard]] _MSTD_CONSTEXPR20 const value_type& at(const size_t idx) const { return _orderedElements.at(idx); }
232
233 [[nodiscard]] _MSTD_CONSTEXPR20 iterator begin() { return _orderedElements.begin(); }
234
235 [[nodiscard]] _MSTD_CONSTEXPR20 iterator end() { return _orderedElements.end(); }
236
237 [[nodiscard]] _MSTD_CONSTEXPR20 const_iterator begin() const { return _orderedElements.cbegin(); }
238
239 [[nodiscard]] _MSTD_CONSTEXPR20 const_iterator end() const { return _orderedElements.cend(); }
240
241 [[nodiscard]] _MSTD_CONSTEXPR20 const_iterator cbegin() const { return _orderedElements.cbegin(); }
242
243 [[nodiscard]] _MSTD_CONSTEXPR20 const_iterator cend() const { return _orderedElements.cend(); }
244
245 [[nodiscard]] _MSTD_CONSTEXPR20 reverse_iterator rbegin() { return _orderedElements.rbegin(); }
246
247 [[nodiscard]] _MSTD_CONSTEXPR20 reverse_iterator rend() { return _orderedElements.rend(); }
248
249 [[nodiscard]] _MSTD_CONSTEXPR20 const_reverse_iterator rbegin() const { return _orderedElements.crbegin(); }
250
251 [[nodiscard]] _MSTD_CONSTEXPR20 const_reverse_iterator rend() const { return _orderedElements.crend(); }
252
253 [[nodiscard]] _MSTD_CONSTEXPR20 const_reverse_iterator crbegin() const { return _orderedElements.crbegin(); }
254
255 [[nodiscard]] _MSTD_CONSTEXPR20 const_reverse_iterator crend() const { return _orderedElements.crend(); }
256
257 [[nodiscard]] _MSTD_CONSTEXPR20 bool operator==(const ordered_set& other) const {
258 return _orderedElements == other._orderedElements;
259 }
260
261 [[nodiscard]] _MSTD_CONSTEXPR20 bool operator!=(const ordered_set& other) const { return !(*this == other); }
262
263 [[nodiscard]] _MSTD_CONSTEXPR20 value_type& operator[](const size_t idx) { return _orderedElements[idx]; }
264
265 [[nodiscard]] _MSTD_CONSTEXPR20 const value_type& operator[](const size_t idx) const { return _orderedElements[idx]; }
266 };
267} // namespace mstd
268 #endif
269#endif
_MSTD_HAS_CXX17
#define _MSTD_HAS_CXX17
Definition config.hpp:45
_MSTD_HAS_CXX20
#define _MSTD_HAS_CXX20
Definition config.hpp:52
_MSTD_REQUIRES
#define _MSTD_REQUIRES(condition)
Definition config.hpp:86
_MSTD_TYPENAME17
#define _MSTD_TYPENAME17
Definition config.hpp:82
_MSTD_CONSTEXPR20
#define _MSTD_CONSTEXPR20
Definition config.hpp:84