Horizon
Loading...
Searching...
No Matches
ordered_map.hpp
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
14namespace nlohmann
15{
16
19template <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)
33 ordered_map(const Allocator& alloc = Allocator()) : Container{alloc} {}
34 template <class It>
35 ordered_map(It first, It last, const Allocator& alloc = Allocator())
36 : Container{first, last, alloc} {}
37 ordered_map(std::initializer_list<T> init, const Allocator& alloc = Allocator() )
38 : Container{init, alloc} {}
39
40 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
53 T& operator[](const Key& key)
54 {
55 return emplace(key, T{}).first->second;
56 }
57
58 const T& operator[](const Key& key) const
59 {
60 return at(key);
61 }
62
63 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
76 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
89 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
108 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
122 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
134 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
146 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
158 std::pair<iterator, bool> insert( value_type&& value )
159 {
160 return emplace(value.first, std::move(value.second));
161 }
162
163 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>>
181 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
namespace for Niels Lohmann
Definition adl_serializer.hpp:12
ordered_map: a minimal map-like container that preserves insertion order for use within nlohmann::bas...
Definition ordered_map.hpp:22