• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 //     __ _____ _____ _____
2 //  __|  |   __|     |   | |  JSON for Modern C++
3 // |  |  |__   |  |  | | | |  version 3.11.2
4 // |_____|_____|_____|_|___|  https://github.com/nlohmann/json
5 //
6 // SPDX-FileCopyrightText: 2013-2022 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)
ordered_mapordered_map46     ordered_map() noexcept(noexcept(Container())) : Container{} {}
ordered_mapordered_map47     explicit ordered_map(const Allocator& alloc) noexcept(noexcept(Container(alloc))) : Container{alloc} {}
48     template <class It>
ordered_mapordered_map49     ordered_map(It first, It last, const Allocator& alloc = Allocator())
50         : Container{first, last, alloc} {}
ordered_mapordered_map51     ordered_map(std::initializer_list<value_type> init, const Allocator& alloc = Allocator() )
52         : Container{init, alloc} {}
53 
emplaceordered_map54     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>
emplaceordered_map69     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 
operator []ordered_map82     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>
operator []ordered_map89     T & operator[](KeyType && key)
90     {
91         return emplace(std::forward<KeyType>(key), T{}).first->second;
92     }
93 
operator []ordered_map94     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>
operator []ordered_map101     const T & operator[](KeyType && key) const
102     {
103         return at(std::forward<KeyType>(key));
104     }
105 
atordered_map106     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>
atordered_map121     T & at(KeyType && key)
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 
atordered_map134     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>
atordered_map149     const T & at(KeyType && key) const
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 
eraseordered_map162     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>
eraseordered_map183     size_type erase(KeyType && key)
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 
eraseordered_map202     iterator erase(iterator pos)
203     {
204         return erase(pos, std::next(pos));
205     }
206 
eraseordered_map207     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 
countordered_map260     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>
countordered_map274     size_type count(KeyType && key) const
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 
findordered_map286     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>
findordered_map300     iterator find(KeyType && key)
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 
findordered_map312     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 
insertordered_map324     std::pair<iterator, bool> insert( value_type&& value )
325     {
326         return emplace(value.first, std::move(value.second));
327     }
328 
insertordered_map329     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>>
insertordered_map347     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