libstdc++
profile/unordered_set
Go to the documentation of this file.
1 // Profiling unordered_set/unordered_multiset implementation -*- C++ -*-
2 
3 // Copyright (C) 2009-2015 Free Software Foundation, Inc.
4 //
5 // This file is part of the GNU ISO C++ Library. This library is free
6 // software; you can redistribute it and/or modify it under the
7 // terms of the GNU General Public License as published by the
8 // Free Software Foundation; either version 3, or (at your option)
9 // any later version.
10 //
11 // This library is distributed in the hope that it will be useful,
12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 // GNU General Public License for more details.
15 
16 // Under Section 7 of GPL version 3, you are granted additional
17 // permissions described in the GCC Runtime Library Exception, version
18 // 3.1, as published by the Free Software Foundation.
19 
20 // You should have received a copy of the GNU General Public License along
21 // with this library; see the file COPYING3. If not see
22 // <http://www.gnu.org/licenses/>.
23 
24 /** @file profile/unordered_set
25  * This file is a GNU profile extension to the Standard C++ Library.
26  */
27 
28 #ifndef _GLIBCXX_PROFILE_UNORDERED_SET
29 #define _GLIBCXX_PROFILE_UNORDERED_SET 1
30 
31 #if __cplusplus < 201103L
32 # include <bits/c++0x_warning.h>
33 #else
34 # include <unordered_set>
35 
36 #include <profile/base.h>
37 #include <profile/unordered_base.h>
38 
39 #define _GLIBCXX_BASE unordered_set<_Key, _Hash, _Pred, _Alloc>
40 #define _GLIBCXX_STD_BASE _GLIBCXX_STD_C::_GLIBCXX_BASE
41 
42 namespace std _GLIBCXX_VISIBILITY(default)
43 {
44 namespace __profile
45 {
46  /** @brief Unordered_set wrapper with performance instrumentation. */
47  template<typename _Key,
48  typename _Hash = std::hash<_Key>,
49  typename _Pred = std::equal_to<_Key>,
50  typename _Alloc = std::allocator<_Key> >
51  class unordered_set
52  : public _GLIBCXX_STD_BASE,
53  public _Unordered_profile<unordered_set<_Key, _Hash, _Pred, _Alloc>,
54  true>
55  {
56  typedef _GLIBCXX_STD_BASE _Base;
57 
58  _Base&
59  _M_base() noexcept { return *this; }
60 
61  const _Base&
62  _M_base() const noexcept { return *this; }
63 
64  public:
65  typedef typename _Base::size_type size_type;
66  typedef typename _Base::hasher hasher;
67  typedef typename _Base::key_equal key_equal;
68  typedef typename _Base::allocator_type allocator_type;
69  typedef typename _Base::key_type key_type;
70  typedef typename _Base::value_type value_type;
71  typedef typename _Base::difference_type difference_type;
72  typedef typename _Base::reference reference;
73  typedef typename _Base::const_reference const_reference;
74 
75  typedef typename _Base::iterator iterator;
76  typedef typename _Base::const_iterator const_iterator;
77 
78  unordered_set() = default;
79 
80  explicit
81  unordered_set(size_type __n,
82  const hasher& __hf = hasher(),
83  const key_equal& __eql = key_equal(),
84  const allocator_type& __a = allocator_type())
85  : _Base(__n, __hf, __eql, __a)
86  { }
87 
88  template<typename _InputIterator>
89  unordered_set(_InputIterator __f, _InputIterator __l,
90  size_type __n = 0,
91  const hasher& __hf = hasher(),
92  const key_equal& __eql = key_equal(),
93  const allocator_type& __a = allocator_type())
94  : _Base(__f, __l, __n, __hf, __eql, __a)
95  { }
96 
97  unordered_set(const unordered_set&) = default;
98 
99  unordered_set(const _Base& __x)
100  : _Base(__x)
101  { }
102 
103  unordered_set(unordered_set&&) = default;
104 
105  explicit
106  unordered_set(const allocator_type& __a)
107  : _Base(__a)
108  { }
109 
110  unordered_set(const unordered_set& __uset,
111  const allocator_type& __a)
112  : _Base(__uset._M_base(), __a)
113  { }
114 
115  unordered_set(unordered_set&& __uset,
116  const allocator_type& __a)
117  : _Base(std::move(__uset._M_base()), __a)
118  { }
119 
120  unordered_set(initializer_list<value_type> __l,
121  size_type __n = 0,
122  const hasher& __hf = hasher(),
123  const key_equal& __eql = key_equal(),
124  const allocator_type& __a = allocator_type())
125  : _Base(__l, __n, __hf, __eql, __a)
126  { }
127 
128  unordered_set(size_type __n, const allocator_type& __a)
129  : unordered_set(__n, hasher(), key_equal(), __a)
130  { }
131 
132  unordered_set(size_type __n, const hasher& __hf,
133  const allocator_type& __a)
134  : unordered_set(__n, __hf, key_equal(), __a)
135  { }
136 
137  template<typename _InputIterator>
138  unordered_set(_InputIterator __first, _InputIterator __last,
139  size_type __n,
140  const allocator_type& __a)
141  : unordered_set(__first, __last, __n, hasher(), key_equal(), __a)
142  { }
143 
144  template<typename _InputIterator>
145  unordered_set(_InputIterator __first, _InputIterator __last,
146  size_type __n, const hasher& __hf,
147  const allocator_type& __a)
148  : unordered_set(__first, __last, __n, __hf, key_equal(), __a)
149  { }
150 
151  unordered_set(initializer_list<value_type> __l,
152  size_type __n,
153  const allocator_type& __a)
154  : unordered_set(__l, __n, hasher(), key_equal(), __a)
155  { }
156 
157  unordered_set(initializer_list<value_type> __l,
158  size_type __n, const hasher& __hf,
159  const allocator_type& __a)
160  : unordered_set(__l, __n, __hf, key_equal(), __a)
161  { }
162 
163  unordered_set&
164  operator=(const unordered_set&) = default;
165 
166  unordered_set&
167  operator=(unordered_set&&) = default;
168 
169  unordered_set&
170  operator=(initializer_list<value_type> __l)
171  {
172  this->_M_profile_destruct();
173  _M_base() = __l;
174  this->_M_profile_construct();
175  return *this;
176  }
177 
178  void
179  swap(unordered_set& __x)
180  noexcept( noexcept(__x._M_base().swap(__x)) )
181  {
182  _Base::swap(__x);
183  this->_M_swap(__x);
184  }
185 
186  void
187  clear() noexcept
188  {
189  this->_M_profile_destruct();
190  _Base::clear();
191  this->_M_profile_construct();
192  }
193 
194  template<typename... _Args>
195  std::pair<iterator, bool>
196  emplace(_Args&&... __args)
197  {
198  size_type __old_size = _Base::bucket_count();
199  std::pair<iterator, bool> __res
200  = _Base::emplace(std::forward<_Args>(__args)...);
201  this->_M_profile_resize(__old_size);
202  return __res;
203  }
204 
205  template<typename... _Args>
206  iterator
207  emplace_hint(const_iterator __it, _Args&&... __args)
208  {
209  size_type __old_size = _Base::bucket_count();
210  iterator __res
211  = _Base::emplace_hint(__it, std::forward<_Args>(__args)...);
212  this->_M_profile_resize(__old_size);
213  return __res;
214  }
215 
216  void
217  insert(std::initializer_list<value_type> __l)
218  {
219  size_type __old_size = _Base::bucket_count();
220  _Base::insert(__l);
221  this->_M_profile_resize(__old_size);
222  }
223 
224  std::pair<iterator, bool>
225  insert(const value_type& __obj)
226  {
227  size_type __old_size = _Base::bucket_count();
228  std::pair<iterator, bool> __res = _Base::insert(__obj);
229  this->_M_profile_resize(__old_size);
230  return __res;
231  }
232 
233  iterator
234  insert(const_iterator __iter, const value_type& __v)
235  {
236  size_type __old_size = _Base::bucket_count();
237  iterator __res = _Base::insert(__iter, __v);
238  this->_M_profile_resize(__old_size);
239  return __res;
240  }
241 
242  std::pair<iterator, bool>
243  insert(value_type&& __obj)
244  {
245  size_type __old_size = _Base::bucket_count();
246  std::pair<iterator, bool> __res = _Base::insert(std::move(__obj));
247  this->_M_profile_resize(__old_size);
248  return __res;
249  }
250 
251  iterator
252  insert(const_iterator __iter, value_type&& __v)
253  {
254  size_type __old_size = _Base::bucket_count();
255  iterator __res = _Base::insert(__iter, std::move(__v));
256  this->_M_profile_resize(__old_size);
257  return __res;
258  }
259 
260  template<typename _InputIter>
261  void
262  insert(_InputIter __first, _InputIter __last)
263  {
264  size_type __old_size = _Base::bucket_count();
265  _Base::insert(__first, __last);
266  this->_M_profile_resize(__old_size);
267  }
268 
269  void
270  rehash(size_type __n)
271  {
272  size_type __old_size = _Base::bucket_count();
273  _Base::rehash(__n);
274  this->_M_profile_resize(__old_size);
275  }
276  };
277 
278  template<typename _Key, typename _Hash, typename _Pred, typename _Alloc>
279  inline void
280  swap(unordered_set<_Key, _Hash, _Pred, _Alloc>& __x,
281  unordered_set<_Key, _Hash, _Pred, _Alloc>& __y)
282  { __x.swap(__y); }
283 
284  template<typename _Key, typename _Hash, typename _Pred, typename _Alloc>
285  inline bool
286  operator==(const unordered_set<_Key, _Hash, _Pred, _Alloc>& __x,
287  const unordered_set<_Key, _Hash, _Pred, _Alloc>& __y)
288  { return static_cast<const _GLIBCXX_STD_BASE&>(__x) == __y; }
289 
290  template<typename _Key, typename _Hash, typename _Pred, typename _Alloc>
291  inline bool
292  operator!=(const unordered_set<_Key, _Hash, _Pred, _Alloc>& __x,
293  const unordered_set<_Key, _Hash, _Pred, _Alloc>& __y)
294  { return !(__x == __y); }
295 
296 #undef _GLIBCXX_BASE
297 #undef _GLIBCXX_STD_BASE
298 #define _GLIBCXX_STD_BASE _GLIBCXX_STD_C::_GLIBCXX_BASE
299 #define _GLIBCXX_BASE unordered_multiset<_Value, _Hash, _Pred, _Alloc>
300 
301  /** @brief Unordered_multiset wrapper with performance instrumentation. */
302  template<typename _Value,
303  typename _Hash = std::hash<_Value>,
304  typename _Pred = std::equal_to<_Value>,
305  typename _Alloc = std::allocator<_Value> >
306  class unordered_multiset
307  : public _GLIBCXX_STD_BASE,
308  public _Unordered_profile<unordered_multiset<_Value,
309  _Hash, _Pred, _Alloc>,
310  false>
311  {
312  typedef _GLIBCXX_STD_BASE _Base;
313 
314  _Base&
315  _M_base() noexcept { return *this; }
316 
317  const _Base&
318  _M_base() const noexcept { return *this; }
319 
320  public:
321  typedef typename _Base::size_type size_type;
322  typedef typename _Base::hasher hasher;
323  typedef typename _Base::key_equal key_equal;
324  typedef typename _Base::allocator_type allocator_type;
325  typedef typename _Base::key_type key_type;
326  typedef typename _Base::value_type value_type;
327  typedef typename _Base::difference_type difference_type;
328  typedef typename _Base::reference reference;
329  typedef typename _Base::const_reference const_reference;
330 
331  typedef typename _Base::iterator iterator;
332  typedef typename _Base::const_iterator const_iterator;
333 
334  unordered_multiset() = default;
335 
336  explicit
337  unordered_multiset(size_type __n,
338  const hasher& __hf = hasher(),
339  const key_equal& __eql = key_equal(),
340  const allocator_type& __a = allocator_type())
341  : _Base(__n, __hf, __eql, __a)
342  { }
343 
344  template<typename _InputIterator>
345  unordered_multiset(_InputIterator __f, _InputIterator __l,
346  size_type __n = 0,
347  const hasher& __hf = hasher(),
348  const key_equal& __eql = key_equal(),
349  const allocator_type& __a = allocator_type())
350  : _Base(__f, __l, __n, __hf, __eql, __a)
351  { }
352 
353  unordered_multiset(const unordered_multiset&) = default;
354 
355  unordered_multiset(const _Base& __x)
356  : _Base(__x)
357  { }
358 
359  unordered_multiset(unordered_multiset&&) = default;
360 
361  explicit
362  unordered_multiset(const allocator_type& __a)
363  : _Base(__a)
364  { }
365 
366  unordered_multiset(const unordered_multiset& __umset,
367  const allocator_type& __a)
368  : _Base(__umset._M_base(), __a)
369  { }
370 
371  unordered_multiset(unordered_multiset&& __umset,
372  const allocator_type& __a)
373  : _Base(std::move(__umset._M_base()), __a)
374  { }
375 
376  unordered_multiset(initializer_list<value_type> __l,
377  size_type __n = 0,
378  const hasher& __hf = hasher(),
379  const key_equal& __eql = key_equal(),
380  const allocator_type& __a = allocator_type())
381  : _Base(__l, __n, __hf, __eql, __a)
382  { }
383 
384  unordered_multiset(size_type __n, const allocator_type& __a)
385  : unordered_multiset(__n, hasher(), key_equal(), __a)
386  { }
387 
388  unordered_multiset(size_type __n, const hasher& __hf,
389  const allocator_type& __a)
390  : unordered_multiset(__n, __hf, key_equal(), __a)
391  { }
392 
393  template<typename _InputIterator>
394  unordered_multiset(_InputIterator __first, _InputIterator __last,
395  size_type __n,
396  const allocator_type& __a)
397  : unordered_multiset(__first, __last, __n, hasher(), key_equal(), __a)
398  { }
399 
400  template<typename _InputIterator>
401  unordered_multiset(_InputIterator __first, _InputIterator __last,
402  size_type __n, const hasher& __hf,
403  const allocator_type& __a)
404  : unordered_multiset(__first, __last, __n, __hf, key_equal(), __a)
405  { }
406 
407  unordered_multiset(initializer_list<value_type> __l,
408  size_type __n,
409  const allocator_type& __a)
410  : unordered_multiset(__l, __n, hasher(), key_equal(), __a)
411  { }
412 
413  unordered_multiset(initializer_list<value_type> __l,
414  size_type __n, const hasher& __hf,
415  const allocator_type& __a)
416  : unordered_multiset(__l, __n, __hf, key_equal(), __a)
417  { }
418 
419  unordered_multiset&
420  operator=(const unordered_multiset&) = default;
421 
422  unordered_multiset&
423  operator=(unordered_multiset&&) = default;
424 
425  unordered_multiset&
426  operator=(initializer_list<value_type> __l)
427  {
428  this->_M_profile_destruct();
429  _M_base() = __l;
430  this->_M_profile_construct();
431  return *this;
432  }
433 
434  void
435  swap(unordered_multiset& __x)
436  noexcept( noexcept(__x._M_base().swap(__x)) )
437  {
438  _Base::swap(__x);
439  this->_M_swap(__x);
440  }
441 
442  void
443  clear() noexcept
444  {
445  this->_M_profile_destruct();
446  _Base::clear();
447  this->_M_profile_construct();
448  }
449 
450  template<typename... _Args>
451  iterator
452  emplace(_Args&&... __args)
453  {
454  size_type __old_size = _Base::bucket_count();
455  iterator __res = _Base::emplace(std::forward<_Args>(__args)...);
456  this->_M_profile_resize(__old_size);
457  return __res;
458  }
459 
460  template<typename... _Args>
461  iterator
462  emplace_hint(const_iterator __it, _Args&&... __args)
463  {
464  size_type __old_size = _Base::bucket_count();
465  iterator __res
466  = _Base::emplace_hint(__it, std::forward<_Args>(__args)...);
467  this->_M_profile_resize(__old_size);
468  return __res;
469  }
470 
471  void
472  insert(std::initializer_list<value_type> __l)
473  {
474  size_type __old_size = _Base::bucket_count();
475  _Base::insert(__l);
476  this->_M_profile_resize(__old_size);
477  }
478 
479  iterator
480  insert(const value_type& __obj)
481  {
482  size_type __old_size = _Base::bucket_count();
483  iterator __res = _Base::insert(__obj);
484  this->_M_profile_resize(__old_size);
485  return __res;
486  }
487 
488  iterator
489  insert(const_iterator __iter, const value_type& __v)
490  {
491  size_type __old_size = _Base::bucket_count();
492  iterator __res = _Base::insert(__iter, __v);
493  this->_M_profile_resize(__old_size);
494  return __res;
495  }
496 
497  iterator
498  insert(value_type&& __obj)
499  {
500  size_type __old_size = _Base::bucket_count();
501  iterator __res = _Base::insert(std::move(__obj));
502  this->_M_profile_resize(__old_size);
503  return __res;
504  }
505 
506  iterator
507  insert(const_iterator __iter, value_type&& __v)
508  {
509  size_type __old_size = _Base::bucket_count();
510  iterator __res = _Base::insert(__iter, std::move(__v));
511  this->_M_profile_resize(__old_size);
512  return __res;
513  }
514 
515  template<typename _InputIter>
516  void
517  insert(_InputIter __first, _InputIter __last)
518  {
519  size_type __old_size = _Base::bucket_count();
520  _Base::insert(__first, __last);
521  this->_M_profile_resize(__old_size);
522  }
523 
524  void
525  rehash(size_type __n)
526  {
527  size_type __old_size = _Base::bucket_count();
528  _Base::rehash(__n);
529  this->_M_profile_resize(__old_size);
530  }
531  };
532 
533  template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
534  inline void
535  swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
536  unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
537  { __x.swap(__y); }
538 
539  template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
540  inline bool
541  operator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
542  const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
543  { return static_cast<const _GLIBCXX_STD_BASE&>(__x) == __y; }
544 
545  template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
546  inline bool
547  operator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
548  const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
549  { return !(__x == __y); }
550 
551 } // namespace __profile
552 } // namespace std
553 
554 #undef _GLIBCXX_BASE
555 #undef _GLIBCXX_STD_BASE
556 
557 #endif // C++11
558 
559 #endif