1 #pragma once 2 3 #include <functional> // less 4 #include <initializer_list> // initializer_list 5 #include <iterator> // input_iterator_tag, iterator_traits 6 #include <memory> // allocator 7 #include <stdexcept> // for out_of_range 8 #include <type_traits> // enable_if, is_convertible 9 #include <utility> // pair 10 #include <vector> // vector 11 12 #include <nlohmann/detail/macro_scope.hpp> 13 14 namespace nlohmann 15 { 16 17 /// ordered_map: a minimal map-like container that preserves insertion order 18 /// for use within nlohmann::basic_json<ordered_map> 19 template <class Key, class T, class IgnoredLess = std::less<Key>, 20 class Allocator = std::allocator<std::pair<const Key, T>>> 21 struct ordered_map : std::vector<std::pair<const Key, T>, Allocator> 22 { 23 using key_type = Key; 24 using mapped_type = T; 25 using Container = std::vector<std::pair<const Key, T>, Allocator>; 26 using typename Container::iterator; 27 using typename Container::const_iterator; 28 using typename Container::size_type; 29 using typename Container::value_type; 30 31 // Explicit constructors instead of `using Container::Container` 32 // otherwise older compilers choke on it (GCC <= 5.5, xcode <= 9.4) ordered_mapnlohmann::ordered_map33 ordered_map(const Allocator& alloc = Allocator()) : Container{alloc} {} 34 template <class It> ordered_mapnlohmann::ordered_map35 ordered_map(It first, It last, const Allocator& alloc = Allocator()) 36 : Container{first, last, alloc} {} ordered_mapnlohmann::ordered_map37 ordered_map(std::initializer_list<T> init, const Allocator& alloc = Allocator() ) 38 : Container{init, alloc} {} 39 emplacenlohmann::ordered_map40 std::pair<iterator, bool> emplace(const key_type& key, T&& t) 41 { 42 for (auto it = this->begin(); it != this->end(); ++it) 43 { 44 if (it->first == key) 45 { 46 return {it, false}; 47 } 48 } 49 Container::emplace_back(key, t); 50 return {--this->end(), true}; 51 } 52 operator []nlohmann::ordered_map53 T& operator[](const Key& key) 54 { 55 return emplace(key, T{}).first->second; 56 } 57 operator []nlohmann::ordered_map58 const T& operator[](const Key& key) const 59 { 60 return at(key); 61 } 62 atnlohmann::ordered_map63 T& at(const Key& key) 64 { 65 for (auto it = this->begin(); it != this->end(); ++it) 66 { 67 if (it->first == key) 68 { 69 return it->second; 70 } 71 } 72 73 JSON_THROW(std::out_of_range("key not found")); 74 } 75 atnlohmann::ordered_map76 const T& at(const Key& key) const 77 { 78 for (auto it = this->begin(); it != this->end(); ++it) 79 { 80 if (it->first == key) 81 { 82 return it->second; 83 } 84 } 85 86 JSON_THROW(std::out_of_range("key not found")); 87 } 88 erasenlohmann::ordered_map89 size_type erase(const Key& key) 90 { 91 for (auto it = this->begin(); it != this->end(); ++it) 92 { 93 if (it->first == key) 94 { 95 // Since we cannot move const Keys, re-construct them in place 96 for (auto next = it; ++next != this->end(); ++it) 97 { 98 it->~value_type(); // Destroy but keep allocation 99 new (&*it) value_type{std::move(*next)}; 100 } 101 Container::pop_back(); 102 return 1; 103 } 104 } 105 return 0; 106 } 107 erasenlohmann::ordered_map108 iterator erase(iterator pos) 109 { 110 auto it = pos; 111 112 // Since we cannot move const Keys, re-construct them in place 113 for (auto next = it; ++next != this->end(); ++it) 114 { 115 it->~value_type(); // Destroy but keep allocation 116 new (&*it) value_type{std::move(*next)}; 117 } 118 Container::pop_back(); 119 return pos; 120 } 121 countnlohmann::ordered_map122 size_type count(const Key& key) const 123 { 124 for (auto it = this->begin(); it != this->end(); ++it) 125 { 126 if (it->first == key) 127 { 128 return 1; 129 } 130 } 131 return 0; 132 } 133 findnlohmann::ordered_map134 iterator find(const Key& key) 135 { 136 for (auto it = this->begin(); it != this->end(); ++it) 137 { 138 if (it->first == key) 139 { 140 return it; 141 } 142 } 143 return Container::end(); 144 } 145 findnlohmann::ordered_map146 const_iterator find(const Key& key) const 147 { 148 for (auto it = this->begin(); it != this->end(); ++it) 149 { 150 if (it->first == key) 151 { 152 return it; 153 } 154 } 155 return Container::end(); 156 } 157 insertnlohmann::ordered_map158 std::pair<iterator, bool> insert( value_type&& value ) 159 { 160 return emplace(value.first, std::move(value.second)); 161 } 162 insertnlohmann::ordered_map163 std::pair<iterator, bool> insert( const value_type& value ) 164 { 165 for (auto it = this->begin(); it != this->end(); ++it) 166 { 167 if (it->first == value.first) 168 { 169 return {it, false}; 170 } 171 } 172 Container::push_back(value); 173 return {--this->end(), true}; 174 } 175 176 template<typename InputIt> 177 using require_input_iter = typename std::enable_if<std::is_convertible<typename std::iterator_traits<InputIt>::iterator_category, 178 std::input_iterator_tag>::value>::type; 179 180 template<typename InputIt, typename = require_input_iter<InputIt>> insertnlohmann::ordered_map181 void insert(InputIt first, InputIt last) 182 { 183 for (auto it = first; it != last; ++it) 184 { 185 insert(*it); 186 } 187 } 188 }; 189 190 } // namespace nlohmann 191