InspIRCd  4.0
flat_map.h
1 /*
2  * InspIRCd -- Internet Relay Chat Daemon
3  *
4  * Copyright (C) 2019-2020 Sadie Powell <[email protected]>
5  * Copyright (C) 2014 Attila Molnar <[email protected]>
6  *
7  * This file is part of InspIRCd. InspIRCd is free software: you can
8  * redistribute it and/or modify it under the terms of the GNU General Public
9  * License as published by the Free Software Foundation, version 2.
10  *
11  * This program is distributed in the hope that it will be useful, but WITHOUT
12  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
13  * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
14  * details.
15  *
16  * You should have received a copy of the GNU General Public License
17  * along with this program. If not, see <http://www.gnu.org/licenses/>.
18  */
19 
20 
21 #pragma once
22 
23 #include <vector>
24 
25 namespace insp
26 {
27 
28 namespace detail
29 {
30 
31 template <typename T, typename Comp>
32 class map_pair_compare : public Comp
33 {
34  typedef T value_type;
35  typedef typename value_type::first_type key_type;
36 
37  public:
38  bool operator()(const value_type& x, const value_type& y) const
39  {
40  return Comp::operator()(x.first, y.first);
41  }
42 
43  bool operator()(const value_type& x, const key_type& y) const
44  {
45  return Comp::operator()(x.first, y);
46  }
47 
48  bool operator()(const key_type& x, const value_type& y) const
49  {
50  return Comp::operator()(x, y.first);
51  }
52 };
53 
54 template <typename Val, typename Comp>
55 class map_value_compare : public std::binary_function<Val, Val, bool>
56 {
57  public:
58  // Constructor should be private
59 
60  bool operator()(const Val& x, const Val& y) const
61  {
62  Comp c;
63  return c(x.first, y.first);
64  }
65 };
66 
67 template <typename T, typename Comp, typename Key = T, typename ElementComp = Comp>
69 {
70  protected:
71  typedef std::vector<T> storage_type;
72  storage_type vect;
73 
74  public:
75  typedef typename storage_type::iterator iterator;
76  typedef typename storage_type::const_iterator const_iterator;
77  typedef typename storage_type::reverse_iterator reverse_iterator;
78  typedef typename storage_type::const_reverse_iterator const_reverse_iterator;
79 
80  typedef typename storage_type::size_type size_type;
81  typedef typename storage_type::difference_type difference_type;
82  typedef Key key_type;
83  typedef T value_type;
84 
85  typedef Comp key_compare;
86  typedef ElementComp value_compare;
87 
88  flat_map_base() = default;
89 
90  flat_map_base(const flat_map_base& other)
91  : vect(other.vect)
92  {
93  }
94 
95  flat_map_base& operator=(const flat_map_base& other) = default;
96 
97  size_type size() const { return vect.size(); }
98  bool empty() const { return vect.empty(); }
99  size_type capacity() const { return vect.capacity(); }
100  size_type max_size() const { return vect.max_size(); }
101 
102  void clear() { vect.clear(); }
103  void reserve(size_type n) { vect.reserve(n); }
104 
105  iterator begin() { return vect.begin(); }
106  iterator end() { return vect.end(); }
107  reverse_iterator rbegin() { return vect.rbegin(); }
108  reverse_iterator rend() { return vect.rend(); }
109 
110  const_iterator begin() const { return vect.begin(); }
111  const_iterator end() const { return vect.end(); }
112  const_reverse_iterator rbegin() const { return vect.rbegin(); }
113  const_reverse_iterator rend() const { return vect.rend(); }
114 
115  key_compare key_comp() const { return Comp(); }
116 
117  iterator erase(iterator it) { return vect.erase(it); }
118  iterator erase(iterator first, iterator last) { return vect.erase(first, last); }
119  size_type erase(const key_type& x)
120  {
121  size_type n = vect.size();
122  std::pair<iterator, iterator> itpair = equal_range(x);
123  vect.erase(itpair.first, itpair.second);
124  return n - vect.size();
125  }
126 
127  iterator find(const key_type& x)
128  {
129  value_compare c;
130  iterator it = std::lower_bound(vect.begin(), vect.end(), x, c);
131  if ((it != vect.end()) && (!c(x, *it)))
132  return it;
133  return vect.end();
134  }
135 
136  const_iterator find(const key_type& x) const
137  {
138  // Same as above but this time we return a const_iterator
139  value_compare c;
140  const_iterator it = std::lower_bound(vect.begin(), vect.end(), x, c);
141  if ((it != vect.end()) && (!c(x, *it)))
142  return it;
143  return vect.end();
144  }
145 
146  std::pair<iterator, iterator> equal_range(const key_type& x)
147  {
148  return std::equal_range(vect.begin(), vect.end(), x, value_compare());
149  }
150 
151  std::pair<const_iterator, const_iterator> equal_range(const key_type& x) const
152  {
153  return std::equal_range(vect.begin(), vect.end(), x, value_compare());
154  }
155 
156  iterator lower_bound(const key_type& x)
157  {
158  return std::lower_bound(vect.begin(), vect.end(), x, value_compare());
159  }
160 
161  const_iterator lower_bound(const key_type& x) const
162  {
163  return std::lower_bound(vect.begin(), vect.end(), x, value_compare());
164  }
165 
166  iterator upper_bound(const key_type& x)
167  {
168  return std::upper_bound(vect.begin(), vect.end(), x, value_compare());
169  }
170 
171  const_iterator upper_bound(const key_type& x) const
172  {
173  return std::upper_bound(vect.begin(), vect.end(), x, value_compare());
174  }
175 
176  size_type count(const key_type& x) const
177  {
178  std::pair<const_iterator, const_iterator> itpair = equal_range(x);
179  return std::distance(itpair.first, itpair.second);
180  }
181 
182  protected:
183  std::pair<iterator, bool> insert_single(const value_type& x)
184  {
185  bool inserted = false;
186 
187  value_compare c;
188  iterator it = std::lower_bound(vect.begin(), vect.end(), x, c);
189  if ((it == vect.end()) || (c(x, *it)))
190  {
191  inserted = true;
192  it = vect.insert(it, x);
193  }
194  return std::make_pair(it, inserted);
195  }
196 
197  iterator insert_multi(const value_type& x)
198  {
199  iterator it = std::lower_bound(vect.begin(), vect.end(), x, value_compare());
200  return vect.insert(it, x);
201  }
202 };
203 
204 } // namespace detail
205 
206 template <typename T, typename Comp = std::less<T>, typename ElementComp = Comp>
207 class flat_set : public detail::flat_map_base<T, Comp, T, ElementComp>
208 {
210 
211  public:
212  typedef typename base_type::iterator iterator;
213  typedef typename base_type::value_type value_type;
214 
215  flat_set() = default;
216 
217  template <typename InputIterator>
218  flat_set(InputIterator first, InputIterator last)
219  {
220  this->insert(first, last);
221  }
222 
223  flat_set(std::initializer_list<value_type> init)
224  {
225  for (const auto& elem : init)
226  insert(elem);
227  }
228 
229  flat_set(const flat_set& other)
230  : base_type(other)
231  {
232  }
233 
234  flat_set& operator=(const flat_set& other) = default;
235 
236  template <typename... Args>
237  std::pair<iterator, bool> emplace(Args&&... args)
238  {
239  return insert(value_type(std::forward<Args>(args)...));
240  }
241 
242  std::pair<iterator, bool> insert(const value_type& x)
243  {
244  return this->insert_single(x);
245  }
246 
247  template <typename InputIterator>
248  void insert(InputIterator first, InputIterator last)
249  {
250  for (; first != last; ++first)
251  this->insert_single(*first);
252  }
253 
254  void swap(flat_set& other)
255  {
256  base_type::vect.swap(other.vect);
257  }
258 };
259 
260 template <typename T, typename Comp = std::less<T>, typename ElementComp = Comp>
261 class flat_multiset : public detail::flat_map_base<T, Comp, T, ElementComp>
262 {
264 
265  public:
266  typedef typename base_type::iterator iterator;
267  typedef typename base_type::value_type value_type;
268 
269  flat_multiset() = default;
270 
271  template <typename InputIterator>
272  flat_multiset(InputIterator first, InputIterator last)
273  {
274  this->insert(first, last);
275  }
276 
277  flat_multiset(std::initializer_list<value_type> init)
278  {
279  for (const auto& elem : init)
280  insert(elem);
281  }
282 
283  flat_multiset(const flat_multiset& other)
284  : base_type(other)
285  {
286  }
287 
288  flat_multiset& operator=(const flat_multiset& other) = default;
289 
290  template <typename... Args>
291  iterator emplace(Args&&... args)
292  {
293  return insert(value_type(std::forward<Args>(args)...));
294  }
295 
296  iterator insert(const value_type& x)
297  {
298  return this->insert_multi(x);
299  }
300 
301  template <typename InputIterator>
302  void insert(InputIterator first, InputIterator last)
303  {
304  for (; first != last; ++first)
305  insert_multi(*first);
306  }
307 
308  void swap(flat_multiset& other)
309  {
310  base_type::vect.swap(other.vect);
311  }
312 };
313 
314 template <typename T, typename U, typename Comp = std::less<T>, typename ElementComp = Comp >
315 class flat_map : public detail::flat_map_base<std::pair<T, U>, Comp, T, detail::map_pair_compare<std::pair<T, U>, ElementComp> >
316 {
318 
319  public:
320  typedef typename base_type::iterator iterator;
321  typedef typename base_type::key_type key_type;
322  typedef typename base_type::value_type value_type;
323  typedef U mapped_type;
324  typedef typename base_type::value_compare value_compare;
325 
326  flat_map() = default;
327 
328  template <typename InputIterator>
329  flat_map(InputIterator first, InputIterator last)
330  {
331  insert(first, last);
332  }
333 
334  flat_map(std::initializer_list<value_type> init)
335  {
336  for (const auto& elem : init)
337  insert(elem);
338  }
339 
340  flat_map(const flat_map& other)
341  : base_type(other)
342  {
343  }
344 
345  flat_map& operator=(const flat_map& other) = default;
346 
347  template <typename... Args>
348  std::pair<iterator, bool> emplace(Args&&... args)
349  {
350  return insert(value_type(std::forward<Args>(args)...));
351  }
352 
353  std::pair<iterator, bool> insert(const value_type& x)
354  {
355  return this->insert_single(x);
356  }
357 
358  template <typename InputIterator>
359  void insert(InputIterator first, InputIterator last)
360  {
361  for (; first != last; ++first)
362  this->insert_single(*first);
363  }
364 
365  void swap(flat_map& other)
366  {
367  base_type::vect.swap(other.vect);
368  }
369 
370  mapped_type& operator[](const key_type& x)
371  {
372  return insert(value_type(x, mapped_type())).first->second;
373  }
374 
375  value_compare value_comp() const
376  {
377  return value_compare();
378  }
379 };
380 
381 template <typename T, typename U, typename Comp = std::less<T>, typename ElementComp = Comp >
382 class flat_multimap : public detail::flat_map_base<std::pair<T, U>, Comp, T, detail::map_pair_compare<std::pair<T, U>, ElementComp> >
383 {
385 
386  public:
387  typedef typename base_type::iterator iterator;
388  typedef typename base_type::value_type value_type;
389  typedef U mapped_type;
390  typedef typename base_type::value_compare value_compare;
391 
392  flat_multimap() = default;
393 
394  template <typename InputIterator>
395  flat_multimap(InputIterator first, InputIterator last)
396  {
397  this->insert(first, last);
398  }
399 
400  flat_multimap(std::initializer_list<value_type> init)
401  {
402  for (const auto& elem : init)
403  insert(elem);
404  }
405 
406  flat_multimap(const flat_multimap& other)
407  : base_type(other)
408  {
409  }
410 
411  flat_multimap& operator=(const flat_multimap& other) = default;
412 
413  template <typename... Args>
414  iterator emplace(Args&&... args)
415  {
416  return insert(value_type(std::forward<Args>(args)...));
417  }
418 
419  iterator insert(const value_type& x)
420  {
421  return this->insert_multi(x);
422  }
423 
424  template <typename InputIterator>
425  void insert(InputIterator first, InputIterator last)
426  {
427  for (; first != last; ++first)
428  this->insert_multi(*first);
429  }
430 
431  void swap(flat_multimap& other)
432  {
433  base_type::vect.swap(other.vect);
434  }
435 
436  value_compare value_comp() const
437  {
438  return value_compare();
439  }
440 };
441 
442 } // namespace insp
Definition: flat_map.h:69
Definition: flat_map.h:33
Definition: flat_map.h:56
Definition: flat_map.h:316
Definition: flat_map.h:383
Definition: flat_map.h:262
Definition: flat_map.h:208