1 #pragma once 2 3 #include <functional> // less 4 #include <memory> // allocator 5 #include <stdexcept> // for out_of_range 6 #include <utility> // pair 7 #include <vector> // vector 8 9 namespace nlohmann 10 { 11 12 /// ordered_map: a minimal map-like container that preserves insertion order 13 /// for use within nlohmann::basic_json<ordered_map> 14 template <class Key, class T, class IgnoredLess = std::less<Key>, 15 class Allocator = std::allocator<std::pair<const Key, T>>> 16 struct ordered_map : std::vector<std::pair<const Key, T>, Allocator> 17 { 18 using key_type = Key; 19 using mapped_type = T; 20 using Container = std::vector<std::pair<const Key, T>, Allocator>; 21 using typename Container::iterator; 22 using typename Container::const_iterator; 23 using typename Container::size_type; 24 using typename Container::value_type; 25 26 // Explicit constructors instead of `using Container::Container` 27 // otherwise older compilers choke on it (GCC <= 5.5, xcode <= 9.4) ordered_mapnlohmann::ordered_map28 ordered_map(const Allocator& alloc = Allocator()) : Container{alloc} {} 29 template <class It> ordered_mapnlohmann::ordered_map30 ordered_map(It first, It last, const Allocator& alloc = Allocator()) 31 : Container{first, last, alloc} {} ordered_mapnlohmann::ordered_map32 ordered_map(std::initializer_list<T> init, const Allocator& alloc = Allocator() ) 33 : Container{init, alloc} {} 34 emplacenlohmann::ordered_map35 std::pair<iterator, bool> emplace(const key_type& key, T&& t) 36 { 37 for (auto it = this->begin(); it != this->end(); ++it) 38 { 39 if (it->first == key) 40 { 41 return {it, false}; 42 } 43 } 44 Container::emplace_back(key, t); 45 return {--this->end(), true}; 46 } 47 operator []nlohmann::ordered_map48 T& operator[](const Key& key) 49 { 50 return emplace(key, T{}).first->second; 51 } 52 operator []nlohmann::ordered_map53 const T& operator[](const Key& key) const 54 { 55 return at(key); 56 } 57 atnlohmann::ordered_map58 T& at(const Key& key) 59 { 60 for (auto it = this->begin(); it != this->end(); ++it) 61 { 62 if (it->first == key) 63 { 64 return it->second; 65 } 66 } 67 68 JSON_THROW(std::out_of_range("key not found")); 69 } 70 atnlohmann::ordered_map71 const T& at(const Key& key) const 72 { 73 for (auto it = this->begin(); it != this->end(); ++it) 74 { 75 if (it->first == key) 76 { 77 return it->second; 78 } 79 } 80 81 JSON_THROW(std::out_of_range("key not found")); 82 } 83 erasenlohmann::ordered_map84 size_type erase(const Key& key) 85 { 86 for (auto it = this->begin(); it != this->end(); ++it) 87 { 88 if (it->first == key) 89 { 90 // Since we cannot move const Keys, re-construct them in place 91 for (auto next = it; ++next != this->end(); ++it) 92 { 93 it->~value_type(); // Destroy but keep allocation 94 new (&*it) value_type{std::move(*next)}; 95 } 96 Container::pop_back(); 97 return 1; 98 } 99 } 100 return 0; 101 } 102 erasenlohmann::ordered_map103 iterator erase(iterator pos) 104 { 105 auto it = pos; 106 107 // Since we cannot move const Keys, re-construct them in place 108 for (auto next = it; ++next != this->end(); ++it) 109 { 110 it->~value_type(); // Destroy but keep allocation 111 new (&*it) value_type{std::move(*next)}; 112 } 113 Container::pop_back(); 114 return pos; 115 } 116 countnlohmann::ordered_map117 size_type count(const Key& key) const 118 { 119 for (auto it = this->begin(); it != this->end(); ++it) 120 { 121 if (it->first == key) 122 { 123 return 1; 124 } 125 } 126 return 0; 127 } 128 findnlohmann::ordered_map129 iterator find(const Key& key) 130 { 131 for (auto it = this->begin(); it != this->end(); ++it) 132 { 133 if (it->first == key) 134 { 135 return it; 136 } 137 } 138 return Container::end(); 139 } 140 findnlohmann::ordered_map141 const_iterator find(const Key& key) const 142 { 143 for (auto it = this->begin(); it != this->end(); ++it) 144 { 145 if (it->first == key) 146 { 147 return it; 148 } 149 } 150 return Container::end(); 151 } 152 insertnlohmann::ordered_map153 std::pair<iterator, bool> insert( value_type&& value ) 154 { 155 return emplace(value.first, std::move(value.second)); 156 } 157 insertnlohmann::ordered_map158 std::pair<iterator, bool> insert( const value_type& value ) 159 { 160 for (auto it = this->begin(); it != this->end(); ++it) 161 { 162 if (it->first == value.first) 163 { 164 return {it, false}; 165 } 166 } 167 Container::push_back(value); 168 return {--this->end(), true}; 169 } 170 }; 171 172 } // namespace nlohmann 173