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