libstdc++
profile/unordered_set
Go to the documentation of this file.
1 // Profiling unordered_set/unordered_multiset implementation -*- C++ -*-
2 
3 // Copyright (C) 2009-2014 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  explicit
79  unordered_set(size_type __n = 10,
80  const hasher& __hf = hasher(),
81  const key_equal& __eql = key_equal(),
82  const allocator_type& __a = allocator_type())
83  : _Base(__n, __hf, __eql, __a)
84  { }
85 
86  template<typename _InputIterator>
87  unordered_set(_InputIterator __f, _InputIterator __l,
88  size_type __n = 0,
89  const hasher& __hf = hasher(),
90  const key_equal& __eql = key_equal(),
91  const allocator_type& __a = allocator_type())
92  : _Base(__f, __l, __n, __hf, __eql, __a)
93  { }
94 
95  unordered_set(const unordered_set&) = default;
96 
97  unordered_set(const _Base& __x)
98  : _Base(__x)
99  { }
100 
101  unordered_set(unordered_set&&) = default;
102 
103  explicit
104  unordered_set(const allocator_type& __a)
105  : _Base(__a)
106  { }
107 
108  unordered_set(const unordered_set& __uset,
109  const allocator_type& __a)
110  : _Base(__uset._M_base(), __a)
111  { }
112 
113  unordered_set(unordered_set&& __uset,
114  const allocator_type& __a)
115  : _Base(std::move(__uset._M_base()), __a)
116  { }
117 
118  unordered_set(initializer_list<value_type> __l,
119  size_type __n = 0,
120  const hasher& __hf = hasher(),
121  const key_equal& __eql = key_equal(),
122  const allocator_type& __a = allocator_type())
123  : _Base(__l, __n, __hf, __eql, __a)
124  { }
125 
126  unordered_set&
127  operator=(const unordered_set&) = default;
128 
129  unordered_set&
130  operator=(unordered_set&&) = default;
131 
132  unordered_set&
133  operator=(initializer_list<value_type> __l)
134  {
135  _M_base() = __l;
136  return *this;
137  }
138 
139  void
140  swap(unordered_set& __x)
141  noexcept( noexcept(__x._M_base().swap(__x)) )
142  { _Base::swap(__x); }
143 
144  void
145  clear() noexcept
146  {
147  __profcxx_hashtable_destruct(this, _Base::bucket_count(),
148  _Base::size());
149  this->_M_profile_destruct();
150  _Base::clear();
151  }
152 
153  template<typename... _Args>
154  std::pair<iterator, bool>
155  emplace(_Args&&... __args)
156  {
157  size_type __old_size = _Base::bucket_count();
158  std::pair<iterator, bool> __res
159  = _Base::emplace(std::forward<_Args>(__args)...);
160  _M_profile_resize(__old_size);
161  return __res;
162  }
163 
164  template<typename... _Args>
165  iterator
166  emplace_hint(const_iterator __it, _Args&&... __args)
167  {
168  size_type __old_size = _Base::bucket_count();
169  iterator __res
170  = _Base::emplace_hint(__it, std::forward<_Args>(__args)...);
171  _M_profile_resize(__old_size);
172  return __res;
173  }
174 
175  void
176  insert(std::initializer_list<value_type> __l)
177  {
178  size_type __old_size = _Base::bucket_count();
179  _Base::insert(__l);
180  _M_profile_resize(__old_size);
181  }
182 
183  std::pair<iterator, bool>
184  insert(const value_type& __obj)
185  {
186  size_type __old_size = _Base::bucket_count();
187  std::pair<iterator, bool> __res = _Base::insert(__obj);
188  _M_profile_resize(__old_size);
189  return __res;
190  }
191 
192  iterator
193  insert(const_iterator __iter, const value_type& __v)
194  {
195  size_type __old_size = _Base::bucket_count();
196  iterator __res = _Base::insert(__iter, __v);
197  _M_profile_resize(__old_size);
198  return __res;
199  }
200 
201  std::pair<iterator, bool>
202  insert(value_type&& __obj)
203  {
204  size_type __old_size = _Base::bucket_count();
205  std::pair<iterator, bool> __res = _Base::insert(std::move(__obj));
206  _M_profile_resize(__old_size);
207  return __res;
208  }
209 
210  iterator
211  insert(const_iterator __iter, value_type&& __v)
212  {
213  size_type __old_size = _Base::bucket_count();
214  iterator __res = _Base::insert(__iter, std::move(__v));
215  _M_profile_resize(__old_size);
216  return __res;
217  }
218 
219  template<typename _InputIter>
220  void
221  insert(_InputIter __first, _InputIter __last)
222  {
223  size_type __old_size = _Base::bucket_count();
224  _Base::insert(__first, __last);
225  _M_profile_resize(__old_size);
226  }
227 
228  void
229  rehash(size_type __n)
230  {
231  size_type __old_size = _Base::bucket_count();
232  _Base::rehash(__n);
233  _M_profile_resize(__old_size);
234  }
235 
236  private:
237  void
238  _M_profile_resize(size_type __old_size)
239  {
240  size_type __new_size = _Base::bucket_count();
241  if (__old_size != __new_size)
242  __profcxx_hashtable_resize(this, __old_size, __new_size);
243  }
244  };
245 
246  template<typename _Key, typename _Hash, typename _Pred, typename _Alloc>
247  inline void
248  swap(unordered_set<_Key, _Hash, _Pred, _Alloc>& __x,
249  unordered_set<_Key, _Hash, _Pred, _Alloc>& __y)
250  { __x.swap(__y); }
251 
252  template<typename _Key, typename _Hash, typename _Pred, typename _Alloc>
253  inline bool
254  operator==(const unordered_set<_Key, _Hash, _Pred, _Alloc>& __x,
255  const unordered_set<_Key, _Hash, _Pred, _Alloc>& __y)
256  { return static_cast<const _GLIBCXX_STD_BASE&>(__x) == __y; }
257 
258  template<typename _Key, typename _Hash, typename _Pred, typename _Alloc>
259  inline bool
260  operator!=(const unordered_set<_Key, _Hash, _Pred, _Alloc>& __x,
261  const unordered_set<_Key, _Hash, _Pred, _Alloc>& __y)
262  { return !(__x == __y); }
263 
264 #undef _GLIBCXX_BASE
265 #undef _GLIBCXX_STD_BASE
266 #define _GLIBCXX_STD_BASE _GLIBCXX_STD_C::_GLIBCXX_BASE
267 #define _GLIBCXX_BASE unordered_multiset<_Value, _Hash, _Pred, _Alloc>
268 
269  /** @brief Unordered_multiset wrapper with performance instrumentation. */
270  template<typename _Value,
271  typename _Hash = std::hash<_Value>,
272  typename _Pred = std::equal_to<_Value>,
273  typename _Alloc = std::allocator<_Value> >
274  class unordered_multiset
275  : public _GLIBCXX_STD_BASE,
276  public _Unordered_profile<unordered_multiset<_Value,
277  _Hash, _Pred, _Alloc>,
278  false>
279  {
280  typedef _GLIBCXX_STD_BASE _Base;
281 
282  _Base&
283  _M_base() noexcept { return *this; }
284 
285  const _Base&
286  _M_base() const noexcept { return *this; }
287 
288  public:
289  typedef typename _Base::size_type size_type;
290  typedef typename _Base::hasher hasher;
291  typedef typename _Base::key_equal key_equal;
292  typedef typename _Base::allocator_type allocator_type;
293  typedef typename _Base::key_type key_type;
294  typedef typename _Base::value_type value_type;
295  typedef typename _Base::difference_type difference_type;
296  typedef typename _Base::reference reference;
297  typedef typename _Base::const_reference const_reference;
298 
299  typedef typename _Base::iterator iterator;
300  typedef typename _Base::const_iterator const_iterator;
301 
302  explicit
303  unordered_multiset(size_type __n = 10,
304  const hasher& __hf = hasher(),
305  const key_equal& __eql = key_equal(),
306  const allocator_type& __a = allocator_type())
307  : _Base(__n, __hf, __eql, __a)
308  { }
309 
310  template<typename _InputIterator>
311  unordered_multiset(_InputIterator __f, _InputIterator __l,
312  size_type __n = 0,
313  const hasher& __hf = hasher(),
314  const key_equal& __eql = key_equal(),
315  const allocator_type& __a = allocator_type())
316  : _Base(__f, __l, __n, __hf, __eql, __a)
317  { }
318 
319  unordered_multiset(const unordered_multiset&) = default;
320 
321  unordered_multiset(const _Base& __x)
322  : _Base(__x)
323  { }
324 
325  unordered_multiset(unordered_multiset&&) = default;
326 
327  explicit
328  unordered_multiset(const allocator_type& __a)
329  : _Base(__a)
330  { }
331 
332  unordered_multiset(const unordered_multiset& __umset,
333  const allocator_type& __a)
334  : _Base(__umset._M_base(), __a)
335  { }
336 
337  unordered_multiset(unordered_multiset&& __umset,
338  const allocator_type& __a)
339  : _Base(std::move(__umset._M_base()), __a)
340  { }
341 
342  unordered_multiset(initializer_list<value_type> __l,
343  size_type __n = 0,
344  const hasher& __hf = hasher(),
345  const key_equal& __eql = key_equal(),
346  const allocator_type& __a = allocator_type())
347  : _Base(__l, __n, __hf, __eql, __a)
348  { }
349 
350  unordered_multiset&
351  operator=(const unordered_multiset&) = default;
352 
353  unordered_multiset&
354  operator=(unordered_multiset&&) = default;
355 
356  unordered_multiset&
357  operator=(initializer_list<value_type> __l)
358  {
359  _M_base() = __l;
360  return *this;
361  }
362 
363  void
364  swap(unordered_multiset& __x)
365  noexcept( noexcept(__x._M_base().swap(__x)) )
366  { _Base::swap(__x); }
367 
368  void
369  clear() noexcept
370  {
371  __profcxx_hashtable_destruct(this, _Base::bucket_count(),
372  _Base::size());
373  this->_M_profile_destruct();
374  _Base::clear();
375  }
376 
377  template<typename... _Args>
378  iterator
379  emplace(_Args&&... __args)
380  {
381  size_type __old_size = _Base::bucket_count();
382  iterator __res = _Base::emplace(std::forward<_Args>(__args)...);
383  _M_profile_resize(__old_size);
384  return __res;
385  }
386 
387  template<typename... _Args>
388  iterator
389  emplace_hint(const_iterator __it, _Args&&... __args)
390  {
391  size_type __old_size = _Base::bucket_count();
392  iterator __res
393  = _Base::emplace_hint(__it, std::forward<_Args>(__args)...);
394  _M_profile_resize(__old_size);
395  return __res;
396  }
397 
398  void
399  insert(std::initializer_list<value_type> __l)
400  {
401  size_type __old_size = _Base::bucket_count();
402  _Base::insert(__l);
403  _M_profile_resize(__old_size);
404  }
405 
406  iterator
407  insert(const value_type& __obj)
408  {
409  size_type __old_size = _Base::bucket_count();
410  iterator __res = _Base::insert(__obj);
411  _M_profile_resize(__old_size);
412  return __res;
413  }
414 
415  iterator
416  insert(const_iterator __iter, const value_type& __v)
417  {
418  size_type __old_size = _Base::bucket_count();
419  iterator __res = _Base::insert(__iter, __v);
420  _M_profile_resize(__old_size);
421  return __res;
422  }
423 
424  iterator
425  insert(value_type&& __obj)
426  {
427  size_type __old_size = _Base::bucket_count();
428  iterator __res = _Base::insert(std::move(__obj));
429  _M_profile_resize(__old_size);
430  return __res;
431  }
432 
433  iterator
434  insert(const_iterator __iter, value_type&& __v)
435  {
436  size_type __old_size = _Base::bucket_count();
437  iterator __res = _Base::insert(__iter, std::move(__v));
438  _M_profile_resize(__old_size);
439  return __res;
440  }
441 
442  template<typename _InputIter>
443  void
444  insert(_InputIter __first, _InputIter __last)
445  {
446  size_type __old_size = _Base::bucket_count();
447  _Base::insert(__first, __last);
448  _M_profile_resize(__old_size);
449  }
450 
451  void
452  rehash(size_type __n)
453  {
454  size_type __old_size = _Base::bucket_count();
455  _Base::rehash(__n);
456  _M_profile_resize(__old_size);
457  }
458 
459  private:
460  void
461  _M_profile_resize(size_type __old_size)
462  {
463  size_type __new_size = _Base::bucket_count();
464  if (__old_size != __new_size)
465  __profcxx_hashtable_resize(this, __old_size, __new_size);
466  }
467  };
468 
469  template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
470  inline void
471  swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
472  unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
473  { __x.swap(__y); }
474 
475  template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
476  inline bool
477  operator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
478  const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
479  { return static_cast<const _GLIBCXX_STD_BASE&>(__x) == __y; }
480 
481  template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
482  inline bool
483  operator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
484  const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
485  { return !(__x == __y); }
486 
487 } // namespace __profile
488 } // namespace std
489 
490 #undef _GLIBCXX_BASE
491 #undef _GLIBCXX_STD_BASE
492 
493 #endif // C++11
494 
495 #endif
std::size
constexpr size_t size() const noexcept
Returns the total number of bits.
Definition: bitset:1293
std::pair
Struct holding two objects of arbitrary type.
Definition: stl_pair.h:96
std::unordered_set
A standard container composed of unique keys (containing at most one of each key value) in which the ...
Definition: unordered_set.h:93
std::__profile::unordered_set
Unordered_set wrapper with performance instrumentation.
Definition: profile/unordered_set:51
std::allocator
The standard allocator, as per [20.4].
Definition: allocator.h:92
std::__profile::unordered_multiset
Unordered_multiset wrapper with performance instrumentation.
Definition: profile/unordered_set:274
std::swap
void swap(function< _Res(_Args...)> &__x, function< _Res(_Args...)> &__y)
Swap the targets of two polymorphic function object wrappers.
Definition: functional:2534
std::initializer_list
initializer_list
Definition: initializer_list:47
std::unordered_multiset
A standard container composed of equivalent keys (possibly containing multiple of each key value) in ...
Definition: unordered_set.h:728
std::equal_to
One of the comparison functors.
Definition: stl_function.h:336
base.h
Sequential helper functions. This file is a GNU profile extension to the Standard C++ Library...
std::hash
Primary class template hash.
Definition: system_error:115