libstdc++
profile/unordered_set
Go to the documentation of this file.
1 // Profiling unordered_set/unordered_multiset implementation -*- C++ -*-
2 
3 // Copyright (C) 2009-2017 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  noexcept(noexcept(__x.swap(__y)))
283  { __x.swap(__y); }
284 
285  template<typename _Key, typename _Hash, typename _Pred, typename _Alloc>
286  inline bool
287  operator==(const unordered_set<_Key, _Hash, _Pred, _Alloc>& __x,
288  const unordered_set<_Key, _Hash, _Pred, _Alloc>& __y)
289  { return static_cast<const _GLIBCXX_STD_BASE&>(__x) == __y; }
290 
291  template<typename _Key, typename _Hash, typename _Pred, typename _Alloc>
292  inline bool
293  operator!=(const unordered_set<_Key, _Hash, _Pred, _Alloc>& __x,
294  const unordered_set<_Key, _Hash, _Pred, _Alloc>& __y)
295  { return !(__x == __y); }
296 
297 #undef _GLIBCXX_BASE
298 #undef _GLIBCXX_STD_BASE
299 #define _GLIBCXX_STD_BASE _GLIBCXX_STD_C::_GLIBCXX_BASE
300 #define _GLIBCXX_BASE unordered_multiset<_Value, _Hash, _Pred, _Alloc>
301 
302  /** @brief Unordered_multiset wrapper with performance instrumentation. */
303  template<typename _Value,
304  typename _Hash = std::hash<_Value>,
305  typename _Pred = std::equal_to<_Value>,
306  typename _Alloc = std::allocator<_Value> >
307  class unordered_multiset
308  : public _GLIBCXX_STD_BASE,
309  public _Unordered_profile<unordered_multiset<_Value,
310  _Hash, _Pred, _Alloc>,
311  false>
312  {
313  typedef _GLIBCXX_STD_BASE _Base;
314 
315  _Base&
316  _M_base() noexcept { return *this; }
317 
318  const _Base&
319  _M_base() const noexcept { return *this; }
320 
321  public:
322  typedef typename _Base::size_type size_type;
323  typedef typename _Base::hasher hasher;
324  typedef typename _Base::key_equal key_equal;
325  typedef typename _Base::allocator_type allocator_type;
326  typedef typename _Base::key_type key_type;
327  typedef typename _Base::value_type value_type;
328  typedef typename _Base::difference_type difference_type;
329  typedef typename _Base::reference reference;
330  typedef typename _Base::const_reference const_reference;
331 
332  typedef typename _Base::iterator iterator;
333  typedef typename _Base::const_iterator const_iterator;
334 
335  unordered_multiset() = default;
336 
337  explicit
338  unordered_multiset(size_type __n,
339  const hasher& __hf = hasher(),
340  const key_equal& __eql = key_equal(),
341  const allocator_type& __a = allocator_type())
342  : _Base(__n, __hf, __eql, __a)
343  { }
344 
345  template<typename _InputIterator>
346  unordered_multiset(_InputIterator __f, _InputIterator __l,
347  size_type __n = 0,
348  const hasher& __hf = hasher(),
349  const key_equal& __eql = key_equal(),
350  const allocator_type& __a = allocator_type())
351  : _Base(__f, __l, __n, __hf, __eql, __a)
352  { }
353 
354  unordered_multiset(const unordered_multiset&) = default;
355 
356  unordered_multiset(const _Base& __x)
357  : _Base(__x)
358  { }
359 
360  unordered_multiset(unordered_multiset&&) = default;
361 
362  explicit
363  unordered_multiset(const allocator_type& __a)
364  : _Base(__a)
365  { }
366 
367  unordered_multiset(const unordered_multiset& __umset,
368  const allocator_type& __a)
369  : _Base(__umset._M_base(), __a)
370  { }
371 
372  unordered_multiset(unordered_multiset&& __umset,
373  const allocator_type& __a)
374  : _Base(std::move(__umset._M_base()), __a)
375  { }
376 
377  unordered_multiset(initializer_list<value_type> __l,
378  size_type __n = 0,
379  const hasher& __hf = hasher(),
380  const key_equal& __eql = key_equal(),
381  const allocator_type& __a = allocator_type())
382  : _Base(__l, __n, __hf, __eql, __a)
383  { }
384 
385  unordered_multiset(size_type __n, const allocator_type& __a)
386  : unordered_multiset(__n, hasher(), key_equal(), __a)
387  { }
388 
389  unordered_multiset(size_type __n, const hasher& __hf,
390  const allocator_type& __a)
391  : unordered_multiset(__n, __hf, key_equal(), __a)
392  { }
393 
394  template<typename _InputIterator>
395  unordered_multiset(_InputIterator __first, _InputIterator __last,
396  size_type __n,
397  const allocator_type& __a)
398  : unordered_multiset(__first, __last, __n, hasher(), key_equal(), __a)
399  { }
400 
401  template<typename _InputIterator>
402  unordered_multiset(_InputIterator __first, _InputIterator __last,
403  size_type __n, const hasher& __hf,
404  const allocator_type& __a)
405  : unordered_multiset(__first, __last, __n, __hf, key_equal(), __a)
406  { }
407 
408  unordered_multiset(initializer_list<value_type> __l,
409  size_type __n,
410  const allocator_type& __a)
411  : unordered_multiset(__l, __n, hasher(), key_equal(), __a)
412  { }
413 
414  unordered_multiset(initializer_list<value_type> __l,
415  size_type __n, const hasher& __hf,
416  const allocator_type& __a)
417  : unordered_multiset(__l, __n, __hf, key_equal(), __a)
418  { }
419 
420  unordered_multiset&
421  operator=(const unordered_multiset&) = default;
422 
423  unordered_multiset&
424  operator=(unordered_multiset&&) = default;
425 
426  unordered_multiset&
427  operator=(initializer_list<value_type> __l)
428  {
429  this->_M_profile_destruct();
430  _M_base() = __l;
431  this->_M_profile_construct();
432  return *this;
433  }
434 
435  void
436  swap(unordered_multiset& __x)
437  noexcept( noexcept(__x._M_base().swap(__x)) )
438  {
439  _Base::swap(__x);
440  this->_M_swap(__x);
441  }
442 
443  void
444  clear() noexcept
445  {
446  this->_M_profile_destruct();
447  _Base::clear();
448  this->_M_profile_construct();
449  }
450 
451  template<typename... _Args>
452  iterator
453  emplace(_Args&&... __args)
454  {
455  size_type __old_size = _Base::bucket_count();
456  iterator __res = _Base::emplace(std::forward<_Args>(__args)...);
457  this->_M_profile_resize(__old_size);
458  return __res;
459  }
460 
461  template<typename... _Args>
462  iterator
463  emplace_hint(const_iterator __it, _Args&&... __args)
464  {
465  size_type __old_size = _Base::bucket_count();
466  iterator __res
467  = _Base::emplace_hint(__it, std::forward<_Args>(__args)...);
468  this->_M_profile_resize(__old_size);
469  return __res;
470  }
471 
472  void
473  insert(std::initializer_list<value_type> __l)
474  {
475  size_type __old_size = _Base::bucket_count();
476  _Base::insert(__l);
477  this->_M_profile_resize(__old_size);
478  }
479 
480  iterator
481  insert(const value_type& __obj)
482  {
483  size_type __old_size = _Base::bucket_count();
484  iterator __res = _Base::insert(__obj);
485  this->_M_profile_resize(__old_size);
486  return __res;
487  }
488 
489  iterator
490  insert(const_iterator __iter, const value_type& __v)
491  {
492  size_type __old_size = _Base::bucket_count();
493  iterator __res = _Base::insert(__iter, __v);
494  this->_M_profile_resize(__old_size);
495  return __res;
496  }
497 
498  iterator
499  insert(value_type&& __obj)
500  {
501  size_type __old_size = _Base::bucket_count();
502  iterator __res = _Base::insert(std::move(__obj));
503  this->_M_profile_resize(__old_size);
504  return __res;
505  }
506 
507  iterator
508  insert(const_iterator __iter, value_type&& __v)
509  {
510  size_type __old_size = _Base::bucket_count();
511  iterator __res = _Base::insert(__iter, std::move(__v));
512  this->_M_profile_resize(__old_size);
513  return __res;
514  }
515 
516  template<typename _InputIter>
517  void
518  insert(_InputIter __first, _InputIter __last)
519  {
520  size_type __old_size = _Base::bucket_count();
521  _Base::insert(__first, __last);
522  this->_M_profile_resize(__old_size);
523  }
524 
525  void
526  rehash(size_type __n)
527  {
528  size_type __old_size = _Base::bucket_count();
529  _Base::rehash(__n);
530  this->_M_profile_resize(__old_size);
531  }
532  };
533 
534  template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
535  inline void
536  swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
537  unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
538  noexcept(noexcept(__x.swap(__y)))
539  { __x.swap(__y); }
540 
541  template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
542  inline bool
543  operator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
544  const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
545  { return static_cast<const _GLIBCXX_STD_BASE&>(__x) == __y; }
546 
547  template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
548  inline bool
549  operator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
550  const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
551  { return !(__x == __y); }
552 
553 } // namespace __profile
554 } // namespace std
555 
556 #undef _GLIBCXX_BASE
557 #undef _GLIBCXX_STD_BASE
558 
559 #endif // C++11
560 
561 #endif