InspIRCd  3.0
flat_map.h
1 /*
2  * InspIRCd -- Internet Relay Chat Daemon
3  *
4  * Copyright (C) 2019 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() { }
89 
90  flat_map_base(const flat_map_base& other)
91  : vect(other.vect)
92  {
93  }
94 
95  size_type size() const { return vect.size(); }
96  bool empty() const { return vect.empty(); }
97  size_type capacity() const { return vect.capacity(); }
98  size_type max_size() const { return vect.max_size(); }
99 
100  void clear() { vect.clear(); }
101  void reserve(size_type n) { vect.reserve(n); }
102 
103  iterator begin() { return vect.begin(); }
104  iterator end() { return vect.end(); }
105  reverse_iterator rbegin() { return vect.rbegin(); }
106  reverse_iterator rend() { return vect.rend(); }
107 
108  const_iterator begin() const { return vect.begin(); }
109  const_iterator end() const { return vect.end(); }
110  const_reverse_iterator rbegin() const { return vect.rbegin(); }
111  const_reverse_iterator rend() const { return vect.rend(); }
112 
113  key_compare key_comp() const { return Comp(); }
114 
115  iterator erase(iterator it) { return vect.erase(it); }
116  iterator erase(iterator first, iterator last) { return vect.erase(first, last); }
117  size_type erase(const key_type& x)
118  {
119  size_type n = vect.size();
120  std::pair<iterator, iterator> itpair = equal_range(x);
121  vect.erase(itpair.first, itpair.second);
122  return n - vect.size();
123  }
124 
125  iterator find(const key_type& x)
126  {
127  value_compare c;
128  iterator it = std::lower_bound(vect.begin(), vect.end(), x, c);
129  if ((it != vect.end()) && (!c(x, *it)))
130  return it;
131  return vect.end();
132  }
133 
134  const_iterator find(const key_type& x) const
135  {
136  // Same as above but this time we return a const_iterator
137  value_compare c;
138  const_iterator it = std::lower_bound(vect.begin(), vect.end(), x, c);
139  if ((it != vect.end()) && (!c(x, *it)))
140  return it;
141  return vect.end();
142  }
143 
144  std::pair<iterator, iterator> equal_range(const key_type& x)
145  {
146  return std::equal_range(vect.begin(), vect.end(), x, value_compare());
147  }
148 
149  std::pair<const_iterator, const_iterator> equal_range(const key_type& x) const
150  {
151  return std::equal_range(vect.begin(), vect.end(), x, value_compare());
152  }
153 
154  iterator lower_bound(const key_type& x)
155  {
156  return std::lower_bound(vect.begin(), vect.end(), x, value_compare());
157  }
158 
159  const_iterator lower_bound(const key_type& x) const
160  {
161  return std::lower_bound(vect.begin(), vect.end(), x, value_compare());
162  }
163 
164  iterator upper_bound(const key_type& x)
165  {
166  return std::upper_bound(vect.begin(), vect.end(), x, value_compare());
167  }
168 
169  const_iterator upper_bound(const key_type& x) const
170  {
171  return std::upper_bound(vect.begin(), vect.end(), x, value_compare());
172  }
173 
174  size_type count(const key_type& x) const
175  {
176  std::pair<const_iterator, const_iterator> itpair = equal_range(x);
177  return std::distance(itpair.first, itpair.second);
178  }
179 
180  protected:
181  std::pair<iterator, bool> insert_single(const value_type& x)
182  {
183  bool inserted = false;
184 
185  value_compare c;
186  iterator it = std::lower_bound(vect.begin(), vect.end(), x, c);
187  if ((it == vect.end()) || (c(x, *it)))
188  {
189  inserted = true;
190  it = vect.insert(it, x);
191  }
192  return std::make_pair(it, inserted);
193  }
194 
195  iterator insert_multi(const value_type& x)
196  {
197  iterator it = std::lower_bound(vect.begin(), vect.end(), x, value_compare());
198  return vect.insert(it, x);
199  }
200 };
201 
202 } // namespace detail
203 
204 template <typename T, typename Comp = std::less<T>, typename ElementComp = Comp>
205 class flat_set : public detail::flat_map_base<T, Comp, T, ElementComp>
206 {
208 
209  public:
210  typedef typename base_t::iterator iterator;
211  typedef typename base_t::value_type value_type;
212 
213  flat_set() { }
214 
215  template <typename InputIterator>
216  flat_set(InputIterator first, InputIterator last)
217  {
218  this->insert(first, last);
219  }
220 
221  flat_set(const flat_set& other)
222  : base_t(other)
223  {
224  }
225 
226  std::pair<iterator, bool> insert(const value_type& x)
227  {
228  return this->insert_single(x);
229  }
230 
231  template <typename InputIterator>
232  void insert(InputIterator first, InputIterator last)
233  {
234  for (; first != last; ++first)
235  this->insert_single(*first);
236  }
237 
238  void swap(flat_set& other)
239  {
240  base_t::vect.swap(other.vect);
241  }
242 };
243 
244 template <typename T, typename Comp = std::less<T>, typename ElementComp = Comp>
245 class flat_multiset : public detail::flat_map_base<T, Comp, T, ElementComp>
246 {
248 
249  public:
250  typedef typename base_t::iterator iterator;
251  typedef typename base_t::value_type value_type;
252 
253  flat_multiset() { }
254 
255  template <typename InputIterator>
256  flat_multiset(InputIterator first, InputIterator last)
257  {
258  this->insert(first, last);
259  }
260 
261  flat_multiset(const flat_multiset& other)
262  : base_t(other)
263  {
264  }
265 
266  iterator insert(const value_type& x)
267  {
268  return this->insert_multi(x);
269  }
270 
271  template <typename InputIterator>
272  void insert(InputIterator first, InputIterator last)
273  {
274  for (; first != last; ++first)
275  insert_multi(*first);
276  }
277 
278  void swap(flat_multiset& other)
279  {
280  base_t::vect.swap(other.vect);
281  }
282 };
283 
284 template <typename T, typename U, typename Comp = std::less<T>, typename ElementComp = Comp >
285 class flat_map : public detail::flat_map_base<std::pair<T, U>, Comp, T, detail::map_pair_compare<std::pair<T, U>, ElementComp> >
286 {
288 
289  public:
290  typedef typename base_t::iterator iterator;
291  typedef typename base_t::key_type key_type;
292  typedef typename base_t::value_type value_type;
293  typedef U mapped_type;
294  typedef typename base_t::value_compare value_compare;
295 
296  flat_map() { }
297 
298  template <typename InputIterator>
299  flat_map(InputIterator first, InputIterator last)
300  {
301  insert(first, last);
302  }
303 
304  flat_map(const flat_map& other)
305  : base_t(other)
306  {
307  }
308 
309  std::pair<iterator, bool> insert(const value_type& x)
310  {
311  return this->insert_single(x);
312  }
313 
314  template <typename InputIterator>
315  void insert(InputIterator first, InputIterator last)
316  {
317  for (; first != last; ++first)
318  this->insert_single(*first);
319  }
320 
321  void swap(flat_map& other)
322  {
323  base_t::vect.swap(other.vect);
324  }
325 
326  mapped_type& operator[](const key_type& x)
327  {
328  return insert(std::make_pair(x, mapped_type())).first->second;
329  }
330 
331  value_compare value_comp() const
332  {
333  return value_compare();
334  }
335 };
336 
337 template <typename T, typename U, typename Comp = std::less<T>, typename ElementComp = Comp >
338 class flat_multimap : public detail::flat_map_base<std::pair<T, U>, Comp, T, detail::map_pair_compare<std::pair<T, U>, ElementComp> >
339 {
341 
342  public:
343  typedef typename base_t::iterator iterator;
344  typedef typename base_t::value_type value_type;
345  typedef U mapped_type;
346  typedef typename base_t::value_compare value_compare;
347 
348  flat_multimap() { }
349 
350  template <typename InputIterator>
351  flat_multimap(InputIterator first, InputIterator last)
352  {
353  this->insert(first, last);
354  }
355 
356  flat_multimap(const flat_multimap& other)
357  : base_t(other)
358  {
359  }
360 
361  iterator insert(const value_type& x)
362  {
363  return this->insert_multi(x);
364  }
365 
366  template <typename InputIterator>
367  void insert(InputIterator first, InputIterator last)
368  {
369  for (; first != last; ++first)
370  this->insert_multi(*first);
371  }
372 
373  void swap(flat_multimap& other)
374  {
375  base_t::vect.swap(other.vect);
376  }
377 
378  value_compare value_comp() const
379  {
380  return value_compare();
381  }
382 };
383 
384 } // namespace insp
insp::detail::flat_map_base
Definition: flat_map.h:68
insp::flat_set
Definition: flat_map.h:205
insp::flat_map
Definition: flat_map.h:285
insp::detail::map_value_compare
Definition: flat_map.h:55
insp::flat_multiset
Definition: flat_map.h:245
insp::detail::map_pair_compare
Definition: flat_map.h:32
insp::flat_multimap
Definition: flat_map.h:338