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