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