Maipa's Standard Library Extension 1.5.6
mstd
Loading...
Searching...
No Matches
ordered_map.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_MAP_HPP_
12 #define _MSTD_ORDERED_MAP_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 Key, class T>
24 class ordered_map {
25 public:
26 using key_type = remove_cvref_t<Key>;
27 using mapped_type = remove_cvref_t<T>;
28 using value_type = std::pair<key_type, mapped_type>;
29 using reference = value_type&;
30 using const_reference = const value_type&;
31
32 private:
33 using _data_type = std::vector<value_type>;
34
35 public:
36 using size_type = _MSTD_TYPENAME17 _data_type::size_type;
37 using difference_type = _MSTD_TYPENAME17 _data_type::difference_type;
38 using iterator = _MSTD_TYPENAME17 _data_type::iterator;
39 using const_iterator = _MSTD_TYPENAME17 _data_type::const_iterator;
40 using reverse_iterator = _MSTD_TYPENAME17 _data_type::reverse_iterator;
41 using const_reverse_iterator = _MSTD_TYPENAME17 _data_type::const_reverse_iterator;
42
43 private:
44 using _map_type = std::unordered_map<key_type, size_type>;
45
46 _data_type _orderedElements;
47 _map_type _elementsMap;
48
49 _MSTD_CONSTEXPR20 void _update_indexes(const size_type from) {
50 static_assert(std::is_copy_constructible_v<key_type>, "Key is not copy constructible!");
51 for (size_type i = from; i != _orderedElements.size(); ++i) { _elementsMap[_orderedElements[i].first] = i; }
52 }
53
54 template<class UK, class U>
55 _MSTD_CONSTEXPR20 mapped_type& _emplace(const_iterator where, UK&& key, U&& value) {
56 return _insert(where, std::make_pair(std::forward<UK>(key), std::forward<U>(value)));
57 }
58
59 template<class UK, class U>
60 _MSTD_CONSTEXPR20 mapped_type& _emplace_back(UK&& key, U&& value) {
61 return _emplace(cend(), std::forward<UK>(key), std::forward<U>(value));
62 }
63
64 template<class U>
65 _MSTD_CONSTEXPR20 mapped_type& _insert(const_iterator where, U&& value) {
66 const key_type key = value.first;
67 if (!contains(key)) {
68 // insert at where and set value (after update iterators in map)
69 size_type whereOffset = std::distance(_orderedElements.cbegin(), where);
70
71 _orderedElements.insert(where, std::forward<U>(value));
72
73 _update_indexes(whereOffset);
74
75 return _orderedElements.at(_elementsMap.at(key)).second;
76 }
77
78 // move key to where and change value (after update iterators in map)
79 size_type whereOffset =
80 std::clamp<size_type>(std::distance(_orderedElements.cbegin(), where), 0, _orderedElements.size() - 1);
81 const size_type& elemOffset = _elementsMap.at(key);
82
83 // remove elem
84 _orderedElements.erase(std::next(_orderedElements.begin(), elemOffset));
85
86 // insert new elem
87 _orderedElements.insert(std::next(_orderedElements.begin(), whereOffset), std::forward<U>(value));
88
89 // update iterators in map
90 if (whereOffset > elemOffset) { _update_indexes(elemOffset); }
91 else { _update_indexes(whereOffset); }
92
93 return _orderedElements.at(_elementsMap.at(key)).second;
94 }
95
96 template<class U>
97 _MSTD_CONSTEXPR20 mapped_type& _insert_back(U&& value) {
98 return _insert(cend(), std::forward<U>(value));
99 }
100
101 template<class UK>
102 _MSTD_CONSTEXPR20 void _erase(UK&& key) {
103 if (!contains(std::forward<UK>(key))) { return; }
104
105 size_type elementOffset = _elementsMap.at(std::forward<UK>(key));
106
107 _orderedElements.erase(std::next(_orderedElements.begin(), elementOffset));
108 _elementsMap.erase(std::forward<UK>(key));
109
110 _update_indexes(elementOffset);
111 }
112
113 template<class UK>
114 [[nodiscard]] _MSTD_CONSTEXPR20 mapped_type& _at(UK&& key) {
115 if _MSTD_CONSTEXPR17 (fmt::is_formattable<key_type>::value) {
116 mstd_assert(contains(std::forward<UK>(key)), "Key '{}' not found", std::forward<UK>(key));
117 }
118 else { mstd_assert(contains(std::forward<UK>(key)), "Key not found"); }
119 return _orderedElements.at(_elementsMap.at(std::forward<UK>(key))).second;
120 }
121
122 template<class UK>
123 [[nodiscard]] _MSTD_CONSTEXPR20 const mapped_type& _at(UK&& key) const {
124 if _MSTD_CONSTEXPR17 (fmt::is_formattable<key_type>::value) {
125 mstd_assert(contains(std::forward<UK>(key)), "Key '{}' not found", std::forward<UK>(key));
126 }
127 else { mstd_assert(contains(std::forward<UK>(key)), "Key not found"); }
128 return _orderedElements.at(_elementsMap.at(std::forward<UK>(key))).second;
129 }
130
131 template<class UK>
132 [[nodiscard]] _MSTD_CONSTEXPR20 bool _contains(UK&& key) const {
133 #if _MSTD_HAS_CXX20
134 return _elementsMap.contains(std::forward<UK>(key));
135 #else
136 return _elementsMap.find(std::forward<UK>(key)) != _elementsMap.end();
137 #endif
138 }
139
140 template<class UK>
141 [[nodiscard]] _MSTD_CONSTEXPR20 iterator _find(UK&& key) {
142 auto it = _elementsMap.find(std::forward<UK>(key));
143 return it != _elementsMap.end() ? std::next(_orderedElements.begin(), it->second) : _orderedElements.end();
144 }
145
146 template<class UK>
147 [[nodiscard]] _MSTD_CONSTEXPR20 const_iterator _find(UK&& key) const {
148 auto it = _elementsMap.find(std::forward<UK>(key));
149 return it != _elementsMap.end() ? std::next(_orderedElements.begin(), it->second) : _orderedElements.end();
150 }
151
152 template<class UK>
153 [[nodiscard]] _MSTD_CONSTEXPR20 mapped_type& _at_with_construct(UK&& key) {
154 auto it = find(key);
155 if (it == end()) { return emplace_back(std::forward<UK>(key), mapped_type()); }
156 return it->second;
157 }
158
159 public:
160 _MSTD_CONSTEXPR20 ordered_map() = default;
161
162 _MSTD_CONSTEXPR20 ordered_map(const ordered_map& other) = default;
163 _MSTD_CONSTEXPR20 ordered_map(ordered_map&& other) noexcept = default;
164
165 _MSTD_CONSTEXPR20 ordered_map(std::initializer_list<value_type> init) { insert_back(init.begin(), init.end()); }
166
167 #if _MSTD_HAS_CXX20
168 template<mstd::iterator_of<value_type> Iter>
169 #else
170 template<class Iter, std::enable_if_t<is_iterator_of_v<Iter, value_type>, bool> = true>
171 #endif
172 _MSTD_CONSTEXPR20 ordered_map(Iter begin, Iter end) {
173 insert_back(begin, end);
174 }
175
176 _MSTD_CONSTEXPR20 ~ordered_map() = default;
177
178 _MSTD_CONSTEXPR20 ordered_map& operator=(const ordered_map& other) = default;
179 _MSTD_CONSTEXPR20 ordered_map& operator=(ordered_map&& other) noexcept = default;
180
181 _MSTD_CONSTEXPR20 mapped_type& emplace(const_iterator where, const key_type& key, const mapped_type& value) {
182 return _emplace(where, key, value);
183 }
184
185 _MSTD_CONSTEXPR20 mapped_type& emplace(const_iterator where, key_type&& key, mapped_type&& value) {
186 return _emplace(where, std::move(key), std::move(value));
187 }
188
189 _MSTD_CONSTEXPR20 mapped_type& emplace_back(const key_type& key, const mapped_type& value) {
190 return _emplace_back(key, value);
191 }
192
193 _MSTD_CONSTEXPR20 mapped_type& emplace_back(key_type&& key, mapped_type&& value) {
194 return _emplace_back(std::move(key), std::move(value));
195 }
196
197 _MSTD_CONSTEXPR20 mapped_type& insert(const_iterator where, const value_type& value) { return _insert(where, value); }
198
199 _MSTD_CONSTEXPR20 mapped_type& insert(const_iterator where, value_type&& value) {
200 return _insert(where, std::move(value));
201 }
202
203 #if _MSTD_HAS_CXX20
204 template<mstd::iterator_of<value_type> Iter>
205 #else
206 template<class Iter, std::enable_if_t<is_iterator_of_v<Iter, value_type>, bool> = true>
207 #endif
208 _MSTD_CONSTEXPR20 void insert(const_iterator where, Iter begin, Iter end) {
209 size_t currWhereOffset = std::distance(_orderedElements.cbegin(), where);
210 for (Iter iter = begin; iter != end; ++iter, ++currWhereOffset) {
211 currWhereOffset = std::clamp<size_t>(currWhereOffset, 0, _orderedElements.size());
212 insert(std::next(_orderedElements.begin(), currWhereOffset), *iter);
213 }
214 }
215
216 _MSTD_CONSTEXPR20 void insert(const_iterator where, std::initializer_list<value_type> init) {
217 insert(where, init.begin(), init.end());
218 }
219
220 _MSTD_CONSTEXPR20 mapped_type& insert_back(const value_type& value) { return _insert_back(value); }
221
222 _MSTD_CONSTEXPR20 mapped_type& insert_back(value_type&& value) { return _insert_back(std::move(value)); }
223
224 #if _MSTD_HAS_CXX20
225 template<mstd::iterator_of<value_type> Iter>
226 #else
227 template<class Iter, std::enable_if_t<is_iterator_of_v<Iter, value_type>, bool> = true>
228 #endif
229 _MSTD_CONSTEXPR20 void insert_back(Iter begin, Iter end) {
230 insert(cend(), begin, end);
231 }
232
233 _MSTD_CONSTEXPR20 void insert_back(std::initializer_list<value_type> init) { insert_back(init.begin(), init.end()); }
234
235 _MSTD_CONSTEXPR20 void erase(const key_type& key) { _erase(key); }
236
237 _MSTD_CONSTEXPR20 void erase(key_type&& key) { _erase(std::move(key)); }
238
239 [[nodiscard]] _MSTD_CONSTEXPR20 mapped_type& at(const key_type& key) { return _at(key); }
240
241 [[nodiscard]] _MSTD_CONSTEXPR20 mapped_type& at(key_type&& key) { return _at(std::move(key)); }
242
243 [[nodiscard]] _MSTD_CONSTEXPR20 const mapped_type& at(const key_type& key) const { return _at(key); }
244
245 [[nodiscard]] _MSTD_CONSTEXPR20 const mapped_type& at(key_type&& key) const { return _at(std::move(key)); }
246
247 [[nodiscard]] _MSTD_CONSTEXPR20 size_type size() const { return _elementsMap.size(); }
248
249 [[nodiscard]] _MSTD_CONSTEXPR20 bool empty() const { return _elementsMap.empty(); }
250
251 [[nodiscard]] _MSTD_CONSTEXPR20 bool contains(const key_type& key) const { return _contains(key); }
252
253 [[nodiscard]] _MSTD_CONSTEXPR20 bool contains(key_type&& key) const { return _contains(std::move(key)); }
254
255 [[nodiscard]] _MSTD_CONSTEXPR20 iterator find(const key_type& key) { return _find(key); }
256
257 [[nodiscard]] _MSTD_CONSTEXPR20 iterator find(key_type&& key) { return _find(std::move(key)); }
258
259 [[nodiscard]] _MSTD_CONSTEXPR20 const_iterator find(const key_type& key) const { return _find(key); }
260
261 [[nodiscard]] _MSTD_CONSTEXPR20 const_iterator find(key_type&& key) const { return _find(std::move(key)); }
262
263 _MSTD_CONSTEXPR20 void clear() {
264 _elementsMap.clear();
265 _orderedElements.clear();
266 }
267
268 [[nodiscard]] _MSTD_CONSTEXPR20 iterator begin() { return _orderedElements.begin(); }
269
270 [[nodiscard]] _MSTD_CONSTEXPR20 iterator end() { return _orderedElements.end(); }
271
272 [[nodiscard]] _MSTD_CONSTEXPR20 const_iterator begin() const { return _orderedElements.cbegin(); }
273
274 [[nodiscard]] _MSTD_CONSTEXPR20 const_iterator end() const { return _orderedElements.cend(); }
275
276 [[nodiscard]] _MSTD_CONSTEXPR20 const_iterator cbegin() const { return _orderedElements.cbegin(); }
277
278 [[nodiscard]] _MSTD_CONSTEXPR20 const_iterator cend() const { return _orderedElements.cend(); }
279
280 [[nodiscard]] _MSTD_CONSTEXPR20 reverse_iterator rbegin() { return _orderedElements.rbegin(); }
281
282 [[nodiscard]] _MSTD_CONSTEXPR20 reverse_iterator rend() { return _orderedElements.rend(); }
283
284 [[nodiscard]] _MSTD_CONSTEXPR20 const_reverse_iterator rbegin() const { return _orderedElements.crbegin(); }
285
286 [[nodiscard]] _MSTD_CONSTEXPR20 const_reverse_iterator rend() const { return _orderedElements.crend(); }
287
288 [[nodiscard]] _MSTD_CONSTEXPR20 const_reverse_iterator crbegin() const { return _orderedElements.crbegin(); }
289
290 [[nodiscard]] _MSTD_CONSTEXPR20 const_reverse_iterator crend() const { return _orderedElements.crend(); }
291
292 [[nodiscard]] _MSTD_CONSTEXPR20 mapped_type& operator[](const key_type& key) {
293 if _MSTD_CONSTEXPR17 (std::is_default_constructible_v<mapped_type>) { return _at_with_construct(key); }
294 else { return _at(key); }
295 }
296
297 [[nodiscard]] _MSTD_CONSTEXPR20 mapped_type& operator[](key_type&& key) {
298 if _MSTD_CONSTEXPR17 (std::is_default_constructible_v<mapped_type>) { return _at_with_construct(std::move(key)); }
299 else { return _at(std::move(key)); }
300 }
301
302 [[nodiscard]] _MSTD_CONSTEXPR20 const mapped_type& operator[](const key_type& key) const { return _at(key); }
303
304 [[nodiscard]] _MSTD_CONSTEXPR20 const mapped_type& operator[](key_type&& key) const { return _at(std::move(key)); }
305
306 [[nodiscard]] _MSTD_CONSTEXPR20 bool operator==(const ordered_map& other) const {
307 return _orderedElements == other._orderedElements && _elementsMap == other._elementsMap;
308 }
309
310 [[nodiscard]] _MSTD_CONSTEXPR20 bool operator!=(const ordered_map& other) const { return !(*this == other); }
311 };
312} // namespace mstd
313 #endif
314#endif
_MSTD_HAS_CXX17
#define _MSTD_HAS_CXX17
Definition config.hpp:45
_MSTD_CONSTEXPR17
#define _MSTD_CONSTEXPR17
Definition config.hpp:76
_MSTD_HAS_CXX20
#define _MSTD_HAS_CXX20
Definition config.hpp:52
_MSTD_TYPENAME17
#define _MSTD_TYPENAME17
Definition config.hpp:82
_MSTD_CONSTEXPR20
#define _MSTD_CONSTEXPR20
Definition config.hpp:84