1 | // __ _____ _____ _____ |
2 | // __| | __| | | | JSON for Modern C++ |
3 | // | | |__ | | | | | | version 3.11.3 |
4 | // |_____|_____|_____|_|___| https://github.com/nlohmann/json |
5 | // |
6 | // SPDX-FileCopyrightText: 2013-2023 Niels Lohmann <https://nlohmann.me> |
7 | // SPDX-License-Identifier: MIT |
8 | |
9 | #pragma once |
10 | |
11 | #include <functional> // equal_to, less |
12 | #include <initializer_list> // initializer_list |
13 | #include <iterator> // input_iterator_tag, iterator_traits |
14 | #include <memory> // allocator |
15 | #include <stdexcept> // for out_of_range |
16 | #include <type_traits> // enable_if, is_convertible |
17 | #include <utility> // pair |
18 | #include <vector> // vector |
19 | |
20 | #include <nlohmann/detail/macro_scope.hpp> |
21 | #include <nlohmann/detail/meta/type_traits.hpp> |
22 | |
23 | NLOHMANN_JSON_NAMESPACE_BEGIN |
24 | |
25 | /// ordered_map: a minimal map-like container that preserves insertion order |
26 | /// for use within nlohmann::basic_json<ordered_map> |
27 | template <class Key, class T, class IgnoredLess = std::less<Key>, |
28 | class Allocator = std::allocator<std::pair<const Key, T>>> |
29 | struct ordered_map : std::vector<std::pair<const Key, T>, Allocator> |
30 | { |
31 | using key_type = Key; |
32 | using mapped_type = T; |
33 | using Container = std::vector<std::pair<const Key, T>, Allocator>; |
34 | using iterator = typename Container::iterator; |
35 | using const_iterator = typename Container::const_iterator; |
36 | using size_type = typename Container::size_type; |
37 | using value_type = typename Container::value_type; |
38 | #ifdef JSON_HAS_CPP_14 |
39 | using key_compare = std::equal_to<>; |
40 | #else |
41 | using key_compare = std::equal_to<Key>; |
42 | #endif |
43 | |
44 | // Explicit constructors instead of `using Container::Container` |
45 | // otherwise older compilers choke on it (GCC <= 5.5, xcode <= 9.4) |
46 | ordered_map() noexcept(noexcept(Container())) : Container{} {} |
47 | explicit ordered_map(const Allocator& alloc) noexcept(noexcept(Container(alloc))) : Container{alloc} {} |
48 | template <class It> |
49 | ordered_map(It first, It last, const Allocator& alloc = Allocator()) |
50 | : Container{first, last, alloc} {} |
51 | ordered_map(std::initializer_list<value_type> init, const Allocator& alloc = Allocator() ) |
52 | : Container{init, alloc} {} |
53 | |
54 | std::pair<iterator, bool> emplace(const key_type& key, T&& t) |
55 | { |
56 | for (auto it = this->begin(); it != this->end(); ++it) |
57 | { |
58 | if (m_compare(it->first, key)) |
59 | { |
60 | return {it, false}; |
61 | } |
62 | } |
63 | Container::emplace_back(key, std::forward<T>(t)); |
64 | return {std::prev(this->end()), true}; |
65 | } |
66 | |
67 | template<class KeyType, detail::enable_if_t< |
68 | detail::is_usable_as_key_type<key_compare, key_type, KeyType>::value, int> = 0> |
69 | std::pair<iterator, bool> emplace(KeyType && key, T && t) |
70 | { |
71 | for (auto it = this->begin(); it != this->end(); ++it) |
72 | { |
73 | if (m_compare(it->first, key)) |
74 | { |
75 | return {it, false}; |
76 | } |
77 | } |
78 | Container::emplace_back(std::forward<KeyType>(key), std::forward<T>(t)); |
79 | return {std::prev(this->end()), true}; |
80 | } |
81 | |
82 | T& operator[](const key_type& key) |
83 | { |
84 | return emplace(key, T{}).first->second; |
85 | } |
86 | |
87 | template<class KeyType, detail::enable_if_t< |
88 | detail::is_usable_as_key_type<key_compare, key_type, KeyType>::value, int> = 0> |
89 | T & operator[](KeyType && key) |
90 | { |
91 | return emplace(std::forward<KeyType>(key), T{}).first->second; |
92 | } |
93 | |
94 | const T& operator[](const key_type& key) const |
95 | { |
96 | return at(key); |
97 | } |
98 | |
99 | template<class KeyType, detail::enable_if_t< |
100 | detail::is_usable_as_key_type<key_compare, key_type, KeyType>::value, int> = 0> |
101 | const T & operator[](KeyType && key) const |
102 | { |
103 | return at(std::forward<KeyType>(key)); |
104 | } |
105 | |
106 | T& at(const key_type& key) |
107 | { |
108 | for (auto it = this->begin(); it != this->end(); ++it) |
109 | { |
110 | if (m_compare(it->first, key)) |
111 | { |
112 | return it->second; |
113 | } |
114 | } |
115 | |
116 | JSON_THROW(std::out_of_range("key not found" )); |
117 | } |
118 | |
119 | template<class KeyType, detail::enable_if_t< |
120 | detail::is_usable_as_key_type<key_compare, key_type, KeyType>::value, int> = 0> |
121 | T & at(KeyType && key) // NOLINT(cppcoreguidelines-missing-std-forward) |
122 | { |
123 | for (auto it = this->begin(); it != this->end(); ++it) |
124 | { |
125 | if (m_compare(it->first, key)) |
126 | { |
127 | return it->second; |
128 | } |
129 | } |
130 | |
131 | JSON_THROW(std::out_of_range("key not found" )); |
132 | } |
133 | |
134 | const T& at(const key_type& key) const |
135 | { |
136 | for (auto it = this->begin(); it != this->end(); ++it) |
137 | { |
138 | if (m_compare(it->first, key)) |
139 | { |
140 | return it->second; |
141 | } |
142 | } |
143 | |
144 | JSON_THROW(std::out_of_range("key not found" )); |
145 | } |
146 | |
147 | template<class KeyType, detail::enable_if_t< |
148 | detail::is_usable_as_key_type<key_compare, key_type, KeyType>::value, int> = 0> |
149 | const T & at(KeyType && key) const // NOLINT(cppcoreguidelines-missing-std-forward) |
150 | { |
151 | for (auto it = this->begin(); it != this->end(); ++it) |
152 | { |
153 | if (m_compare(it->first, key)) |
154 | { |
155 | return it->second; |
156 | } |
157 | } |
158 | |
159 | JSON_THROW(std::out_of_range("key not found" )); |
160 | } |
161 | |
162 | size_type erase(const key_type& key) |
163 | { |
164 | for (auto it = this->begin(); it != this->end(); ++it) |
165 | { |
166 | if (m_compare(it->first, key)) |
167 | { |
168 | // Since we cannot move const Keys, re-construct them in place |
169 | for (auto next = it; ++next != this->end(); ++it) |
170 | { |
171 | it->~value_type(); // Destroy but keep allocation |
172 | new (&*it) value_type{std::move(*next)}; |
173 | } |
174 | Container::pop_back(); |
175 | return 1; |
176 | } |
177 | } |
178 | return 0; |
179 | } |
180 | |
181 | template<class KeyType, detail::enable_if_t< |
182 | detail::is_usable_as_key_type<key_compare, key_type, KeyType>::value, int> = 0> |
183 | size_type erase(KeyType && key) // NOLINT(cppcoreguidelines-missing-std-forward) |
184 | { |
185 | for (auto it = this->begin(); it != this->end(); ++it) |
186 | { |
187 | if (m_compare(it->first, key)) |
188 | { |
189 | // Since we cannot move const Keys, re-construct them in place |
190 | for (auto next = it; ++next != this->end(); ++it) |
191 | { |
192 | it->~value_type(); // Destroy but keep allocation |
193 | new (&*it) value_type{std::move(*next)}; |
194 | } |
195 | Container::pop_back(); |
196 | return 1; |
197 | } |
198 | } |
199 | return 0; |
200 | } |
201 | |
202 | iterator erase(iterator pos) |
203 | { |
204 | return erase(pos, std::next(pos)); |
205 | } |
206 | |
207 | iterator erase(iterator first, iterator last) |
208 | { |
209 | if (first == last) |
210 | { |
211 | return first; |
212 | } |
213 | |
214 | const auto elements_affected = std::distance(first, last); |
215 | const auto offset = std::distance(Container::begin(), first); |
216 | |
217 | // This is the start situation. We need to delete elements_affected |
218 | // elements (3 in this example: e, f, g), and need to return an |
219 | // iterator past the last deleted element (h in this example). |
220 | // Note that offset is the distance from the start of the vector |
221 | // to first. We will need this later. |
222 | |
223 | // [ a, b, c, d, e, f, g, h, i, j ] |
224 | // ^ ^ |
225 | // first last |
226 | |
227 | // Since we cannot move const Keys, we re-construct them in place. |
228 | // We start at first and re-construct (viz. copy) the elements from |
229 | // the back of the vector. Example for first iteration: |
230 | |
231 | // ,--------. |
232 | // v | destroy e and re-construct with h |
233 | // [ a, b, c, d, e, f, g, h, i, j ] |
234 | // ^ ^ |
235 | // it it + elements_affected |
236 | |
237 | for (auto it = first; std::next(it, elements_affected) != Container::end(); ++it) |
238 | { |
239 | it->~value_type(); // destroy but keep allocation |
240 | new (&*it) value_type{std::move(*std::next(it, elements_affected))}; // "move" next element to it |
241 | } |
242 | |
243 | // [ a, b, c, d, h, i, j, h, i, j ] |
244 | // ^ ^ |
245 | // first last |
246 | |
247 | // remove the unneeded elements at the end of the vector |
248 | Container::resize(this->size() - static_cast<size_type>(elements_affected)); |
249 | |
250 | // [ a, b, c, d, h, i, j ] |
251 | // ^ ^ |
252 | // first last |
253 | |
254 | // first is now pointing past the last deleted element, but we cannot |
255 | // use this iterator, because it may have been invalidated by the |
256 | // resize call. Instead, we can return begin() + offset. |
257 | return Container::begin() + offset; |
258 | } |
259 | |
260 | size_type count(const key_type& key) const |
261 | { |
262 | for (auto it = this->begin(); it != this->end(); ++it) |
263 | { |
264 | if (m_compare(it->first, key)) |
265 | { |
266 | return 1; |
267 | } |
268 | } |
269 | return 0; |
270 | } |
271 | |
272 | template<class KeyType, detail::enable_if_t< |
273 | detail::is_usable_as_key_type<key_compare, key_type, KeyType>::value, int> = 0> |
274 | size_type count(KeyType && key) const // NOLINT(cppcoreguidelines-missing-std-forward) |
275 | { |
276 | for (auto it = this->begin(); it != this->end(); ++it) |
277 | { |
278 | if (m_compare(it->first, key)) |
279 | { |
280 | return 1; |
281 | } |
282 | } |
283 | return 0; |
284 | } |
285 | |
286 | iterator find(const key_type& key) |
287 | { |
288 | for (auto it = this->begin(); it != this->end(); ++it) |
289 | { |
290 | if (m_compare(it->first, key)) |
291 | { |
292 | return it; |
293 | } |
294 | } |
295 | return Container::end(); |
296 | } |
297 | |
298 | template<class KeyType, detail::enable_if_t< |
299 | detail::is_usable_as_key_type<key_compare, key_type, KeyType>::value, int> = 0> |
300 | iterator find(KeyType && key) // NOLINT(cppcoreguidelines-missing-std-forward) |
301 | { |
302 | for (auto it = this->begin(); it != this->end(); ++it) |
303 | { |
304 | if (m_compare(it->first, key)) |
305 | { |
306 | return it; |
307 | } |
308 | } |
309 | return Container::end(); |
310 | } |
311 | |
312 | const_iterator find(const key_type& key) const |
313 | { |
314 | for (auto it = this->begin(); it != this->end(); ++it) |
315 | { |
316 | if (m_compare(it->first, key)) |
317 | { |
318 | return it; |
319 | } |
320 | } |
321 | return Container::end(); |
322 | } |
323 | |
324 | std::pair<iterator, bool> insert( value_type&& value ) |
325 | { |
326 | return emplace(value.first, std::move(value.second)); |
327 | } |
328 | |
329 | std::pair<iterator, bool> insert( const value_type& value ) |
330 | { |
331 | for (auto it = this->begin(); it != this->end(); ++it) |
332 | { |
333 | if (m_compare(it->first, value.first)) |
334 | { |
335 | return {it, false}; |
336 | } |
337 | } |
338 | Container::push_back(value); |
339 | return {--this->end(), true}; |
340 | } |
341 | |
342 | template<typename InputIt> |
343 | using require_input_iter = typename std::enable_if<std::is_convertible<typename std::iterator_traits<InputIt>::iterator_category, |
344 | std::input_iterator_tag>::value>::type; |
345 | |
346 | template<typename InputIt, typename = require_input_iter<InputIt>> |
347 | void insert(InputIt first, InputIt last) |
348 | { |
349 | for (auto it = first; it != last; ++it) |
350 | { |
351 | insert(*it); |
352 | } |
353 | } |
354 | |
355 | private: |
356 | JSON_NO_UNIQUE_ADDRESS key_compare m_compare = key_compare(); |
357 | }; |
358 | |
359 | NLOHMANN_JSON_NAMESPACE_END |
360 | |