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