Horizon
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 
14 namespace nlohmann
15 {
16 
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)
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