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
23NLOHMANN_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>
27template <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
355private:
356 JSON_NO_UNIQUE_ADDRESS key_compare m_compare = key_compare();
357};
358
359NLOHMANN_JSON_NAMESPACE_END
360