libstdc++
profile/unordered_set
Go to the documentation of this file.
1 // Profiling unordered_set/unordered_multiset implementation -*- C++ -*-
2 
3 // Copyright (C) 2009, 2010, 2011 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 #ifndef __GXX_EXPERIMENTAL_CXX0X__
32 # include <bits/c++0x_warning.h>
33 #else
34 # include <unordered_set>
35 
36 #include <profile/base.h>
37 
38 #define _GLIBCXX_BASE unordered_set<_Key, _Hash, _Pred, _Alloc>
39 #define _GLIBCXX_STD_BASE _GLIBCXX_STD_C::_GLIBCXX_BASE
40 
41 namespace std _GLIBCXX_VISIBILITY(default)
42 {
43 namespace __profile
44 {
45  /** @brief Unordered_set wrapper with performance instrumentation. */
46  template<typename _Key,
47  typename _Hash = std::hash<_Key>,
48  typename _Pred = std::equal_to<_Key>,
49  typename _Alloc = std::allocator<_Key> >
50  class unordered_set
51  : public _GLIBCXX_STD_BASE
52  {
53  typedef typename _GLIBCXX_STD_BASE _Base;
54 
55  public:
56  typedef typename _Base::size_type size_type;
57  typedef typename _Base::hasher hasher;
58  typedef typename _Base::key_equal key_equal;
59  typedef typename _Base::allocator_type allocator_type;
60  typedef typename _Base::key_type key_type;
61  typedef typename _Base::value_type value_type;
62  typedef typename _Base::difference_type difference_type;
63  typedef typename _Base::reference reference;
64  typedef typename _Base::const_reference const_reference;
65 
66  typedef typename _Base::iterator iterator;
67  typedef typename _Base::const_iterator const_iterator;
68 
69  explicit
70  unordered_set(size_type __n = 10,
71  const hasher& __hf = hasher(),
72  const key_equal& __eql = key_equal(),
73  const allocator_type& __a = allocator_type())
74  : _Base(__n, __hf, __eql, __a)
75  {
76  __profcxx_hashtable_construct(this, _Base::bucket_count());
77  __profcxx_hashtable_construct2(this);
78  }
79 
80  template<typename _InputIterator>
81  unordered_set(_InputIterator __f, _InputIterator __l,
82  size_type __n = 0,
83  const hasher& __hf = hasher(),
84  const key_equal& __eql = key_equal(),
85  const allocator_type& __a = allocator_type())
86  : _Base(__f, __l, __n, __hf, __eql, __a)
87  {
88  __profcxx_hashtable_construct(this, _Base::bucket_count());
89  __profcxx_hashtable_construct2(this);
90  }
91 
92  unordered_set(const unordered_set& __x)
93  : _Base(__x)
94  {
95  __profcxx_hashtable_construct(this, _Base::bucket_count());
96  __profcxx_hashtable_construct2(this);
97  }
98 
99  unordered_set(const _Base& __x)
100  : _Base(__x)
101  {
102  __profcxx_hashtable_construct(this, _Base::bucket_count());
103  __profcxx_hashtable_construct2(this);
104  }
105 
106  unordered_set(unordered_set&& __x)
107  : _Base(std::move(__x))
108  {
109  __profcxx_hashtable_construct(this, _Base::bucket_count());
110  __profcxx_hashtable_construct2(this);
111  }
112 
113  unordered_set(initializer_list<value_type> __l,
114  size_type __n = 0,
115  const hasher& __hf = hasher(),
116  const key_equal& __eql = key_equal(),
117  const allocator_type& __a = allocator_type())
118  : _Base(__l, __n, __hf, __eql, __a) { }
119 
120  unordered_set&
121  operator=(const unordered_set& __x)
122  {
123  *static_cast<_Base*>(this) = __x;
124  return *this;
125  }
126 
127  unordered_set&
128  operator=(unordered_set&& __x)
129  {
130  // NB: DR 1204.
131  // NB: DR 675.
132  this->clear();
133  this->swap(__x);
134  return *this;
135  }
136 
137  unordered_set&
138  operator=(initializer_list<value_type> __l)
139  {
140  this->clear();
141  this->insert(__l);
142  return *this;
143  }
144 
145  ~unordered_set() noexcept
146  {
147  __profcxx_hashtable_destruct(this, _Base::bucket_count(),
148  _Base::size());
149  _M_profile_destruct();
150  }
151 
152  void
153  swap(unordered_set& __x)
154  {
155  _Base::swap(__x);
156  }
157 
158  void
159  clear() noexcept
160  {
161  __profcxx_hashtable_destruct(this, _Base::bucket_count(),
162  _Base::size());
163  _M_profile_destruct();
164  _Base::clear();
165  }
166 
167  template<typename... _Args>
168  std::pair<iterator, bool>
169  emplace(_Args&&... __args)
170  {
171  size_type __old_size = _Base::bucket_count();
172  std::pair<iterator, bool> __res
173  = _Base::emplace(std::forward<_Args>(__args)...);
174  _M_profile_resize(__old_size);
175  return __res;
176  }
177 
178  template<typename... _Args>
179  iterator
180  emplace_hint(const_iterator __it, _Args&&... __args)
181  {
182  size_type __old_size = _Base::bucket_count();
183  iterator __res
184  = _Base::emplace_hint(__it, std::forward<_Args>(__args)...);
185  _M_profile_resize(__old_size);
186  return __res;
187  }
188 
189  void
190  insert(std::initializer_list<value_type> __l)
191  {
192  size_type __old_size = _Base::bucket_count();
193  _Base::insert(__l);
194  _M_profile_resize(__old_size);
195  }
196 
197  std::pair<iterator, bool>
198  insert(const value_type& __obj)
199  {
200  size_type __old_size = _Base::bucket_count();
201  std::pair<iterator, bool> __res = _Base::insert(__obj);
202  _M_profile_resize(__old_size);
203  return __res;
204  }
205 
206  iterator
207  insert(const_iterator __iter, const value_type& __v)
208  {
209  size_type __old_size = _Base::bucket_count();
210  iterator __res = _Base::insert(__iter, __v);
211  _M_profile_resize(__old_size);
212  return __res;
213  }
214 
215  std::pair<iterator, bool>
216  insert(value_type&& __obj)
217  {
218  size_type __old_size = _Base::bucket_count();
219  std::pair<iterator, bool> __res = _Base::insert(std::move(__obj));
220  _M_profile_resize(__old_size);
221  return __res;
222  }
223 
224  iterator
225  insert(const_iterator __iter, value_type&& __v)
226  {
227  size_type __old_size = _Base::bucket_count();
228  iterator __res = _Base::insert(__iter, std::move(__v));
229  _M_profile_resize(__old_size);
230  return __res;
231  }
232 
233  template<typename _InputIter>
234  void
235  insert(_InputIter __first, _InputIter __last)
236  {
237  size_type __old_size = _Base::bucket_count();
238  _Base::insert(__first, __last);
239  _M_profile_resize(__old_size);
240  }
241 
242  void
243  insert(const value_type* __first, const value_type* __last)
244  {
245  size_type __old_size = _Base::bucket_count();
246  _Base::insert(__first, __last);
247  _M_profile_resize(__old_size);
248  }
249 
250  void rehash(size_type __n)
251  {
252  size_type __old_size = _Base::bucket_count();
253  _Base::rehash(__n);
254  _M_profile_resize(__old_size);
255  }
256 
257  private:
258  void
259  _M_profile_resize(size_type __old_size)
260  {
261  size_type __new_size = _Base::bucket_count();
262  if (__old_size != __new_size)
263  __profcxx_hashtable_resize(this, __old_size, __new_size);
264  }
265 
266  void
267  _M_profile_destruct()
268  {
269  size_type __hops = 0, __lc = 0, __chain = 0;
270  iterator __it = this->begin();
271  while (__it != this->end())
272  {
273  size_type __bkt = this->bucket(*__it);
274  auto __lit = this->begin(__bkt);
275  auto __lend = this->end(__bkt);
276  for (++__it, ++__lit; __lit != __lend; ++__it, ++__lit)
277  ++__chain;
278  if (__chain)
279  {
280  ++__chain;
281  __lc = __lc > __chain ? __lc : __chain;
282  __hops += __chain * (__chain - 1) / 2;
283  __chain = 0;
284  }
285  }
286  __profcxx_hashtable_destruct2(this, __lc, _Base::size(), __hops);
287  }
288  };
289 
290  template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
291  inline void
292  swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
293  unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
294  { __x.swap(__y); }
295 
296  template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
297  inline bool
298  operator==(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
299  const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
300  { return __x._M_equal(__y); }
301 
302  template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
303  inline bool
304  operator!=(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
305  const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
306  { return !(__x == __y); }
307 
308 #undef _GLIBCXX_BASE
309 #undef _GLIBCXX_STD_BASE
310 #define _GLIBCXX_STD_BASE _GLIBCXX_STD_C::_GLIBCXX_BASE
311 #define _GLIBCXX_BASE unordered_multiset<_Value, _Hash, _Pred, _Alloc>
312 
313  /** @brief Unordered_multiset wrapper with performance instrumentation. */
314  template<typename _Value,
315  typename _Hash = std::hash<_Value>,
316  typename _Pred = std::equal_to<_Value>,
317  typename _Alloc = std::allocator<_Value> >
318  class unordered_multiset
319  : public _GLIBCXX_STD_BASE
320  {
321  typedef typename _GLIBCXX_STD_BASE _Base;
322 
323  public:
324  typedef typename _Base::size_type size_type;
325  typedef typename _Base::hasher hasher;
326  typedef typename _Base::key_equal key_equal;
327  typedef typename _Base::allocator_type allocator_type;
328  typedef typename _Base::key_type key_type;
329  typedef typename _Base::value_type value_type;
330  typedef typename _Base::difference_type difference_type;
331  typedef typename _Base::reference reference;
332  typedef typename _Base::const_reference const_reference;
333 
334  typedef typename _Base::iterator iterator;
335  typedef typename _Base::const_iterator const_iterator;
336 
337  explicit
338  unordered_multiset(size_type __n = 10,
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  __profcxx_hashtable_construct(this, _Base::bucket_count());
345  }
346 
347  template<typename _InputIterator>
348  unordered_multiset(_InputIterator __f, _InputIterator __l,
349  size_type __n = 0,
350  const hasher& __hf = hasher(),
351  const key_equal& __eql = key_equal(),
352  const allocator_type& __a = allocator_type())
353  : _Base(__f, __l, __n, __hf, __eql, __a)
354  {
355  __profcxx_hashtable_construct(this, _Base::bucket_count());
356  }
357 
358  unordered_multiset(const unordered_multiset& __x)
359  : _Base(__x)
360  {
361  __profcxx_hashtable_construct(this, _Base::bucket_count());
362  }
363 
364  unordered_multiset(const _Base& __x)
365  : _Base(__x)
366  {
367  __profcxx_hashtable_construct(this, _Base::bucket_count());
368  }
369 
370  unordered_multiset(unordered_multiset&& __x)
371  : _Base(std::move(__x))
372  {
373  __profcxx_hashtable_construct(this, _Base::bucket_count());
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  unordered_multiset&
384  operator=(const unordered_multiset& __x)
385  {
386  *static_cast<_Base*>(this) = __x;
387  return *this;
388  }
389 
390  unordered_multiset&
391  operator=(unordered_multiset&& __x)
392  {
393  // NB: DR 1204.
394  // NB: DR 675.
395  this->clear();
396  this->swap(__x);
397  return *this;
398  }
399 
400  unordered_multiset&
401  operator=(initializer_list<value_type> __l)
402  {
403  this->clear();
404  this->insert(__l);
405  return *this;
406  }
407 
408  ~unordered_multiset() noexcept
409  {
410  __profcxx_hashtable_destruct(this, _Base::bucket_count(),
411  _Base::size());
412  _M_profile_destruct();
413  }
414 
415  void
416  swap(unordered_multiset& __x)
417  {
418  _Base::swap(__x);
419  }
420 
421  void
422  clear() noexcept
423  {
424  __profcxx_hashtable_destruct(this, _Base::bucket_count(),
425  _Base::size());
426  _M_profile_destruct();
427  _Base::clear();
428  }
429 
430  template<typename... _Args>
431  iterator
432  emplace(_Args&&... __args)
433  {
434  size_type __old_size = _Base::bucket_count();
435  iterator __res = _Base::emplace(std::forward<_Args>(__args)...);
436  _M_profile_resize(__old_size);
437  return __res;
438  }
439 
440  template<typename... _Args>
441  iterator
442  emplace_hint(const_iterator __it, _Args&&... __args)
443  {
444  size_type __old_size = _Base::bucket_count();
445  iterator __res
446  = _Base::emplace_hint(__it, std::forward<_Args>(__args)...);
447  _M_profile_resize(__old_size);
448  return __res;
449  }
450 
451  void
452  insert(std::initializer_list<value_type> __l)
453  {
454  size_type __old_size = _Base::bucket_count();
455  _Base::insert(__l);
456  _M_profile_resize(__old_size);
457  }
458 
459  iterator
460  insert(const value_type& __obj)
461  {
462  size_type __old_size = _Base::bucket_count();
463  iterator __res = _Base::insert(__obj);
464  _M_profile_resize(__old_size);
465  return __res;
466  }
467 
468  iterator
469  insert(const_iterator __iter, const value_type& __v)
470  {
471  size_type __old_size = _Base::bucket_count();
472  iterator __res = _Base::insert(__iter, __v);
473  _M_profile_resize(__old_size);
474  return __res;
475  }
476 
477  iterator
478  insert(value_type&& __obj)
479  {
480  size_type __old_size = _Base::bucket_count();
481  iterator __res = _Base::insert(std::move(__obj));
482  _M_profile_resize(__old_size);
483  return __res;
484  }
485 
486  iterator
487  insert(const_iterator __iter, value_type&& __v)
488  {
489  size_type __old_size = _Base::bucket_count();
490  iterator __res = _Base::insert(__iter, std::move(__v));
491  _M_profile_resize(__old_size);
492  return __res;
493  }
494 
495  template<typename _InputIter>
496  void
497  insert(_InputIter __first, _InputIter __last)
498  {
499  size_type __old_size = _Base::bucket_count();
500  _Base::insert(__first, __last);
501  _M_profile_resize(__old_size);
502  }
503 
504  void
505  insert(const value_type* __first, const value_type* __last)
506  {
507  size_type __old_size = _Base::bucket_count();
508  _Base::insert(__first, __last);
509  _M_profile_resize(__old_size);
510  }
511 
512  void rehash(size_type __n)
513  {
514  size_type __old_size = _Base::bucket_count();
515  _Base::rehash(__n);
516  _M_profile_resize(__old_size);
517  }
518 
519  private:
520  void
521  _M_profile_resize(size_type __old_size)
522  {
523  size_type __new_size = _Base::bucket_count();
524  if (__old_size != __new_size)
525  __profcxx_hashtable_resize(this, __old_size, __new_size);
526  }
527 
528  void
529  _M_profile_destruct()
530  {
531  size_type __hops = 0, __lc = 0, __chain = 0;
532  iterator __it = this->begin();
533  while (__it != this->end())
534  {
535  size_type __bkt = this->bucket(*__it);
536  auto __lit = this->begin(__bkt);
537  auto __lend = this->end(__bkt);
538  for (++__it, ++__lit; __lit != __lend; ++__it, ++__lit)
539  ++__chain;
540  if (__chain)
541  {
542  ++__chain;
543  __lc = __lc > __chain ? __lc : __chain;
544  __hops += __chain * (__chain - 1) / 2;
545  __chain = 0;
546  }
547  }
548  __profcxx_hashtable_destruct2(this, __lc, _Base::size(), __hops);
549  }
550  };
551 
552  template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
553  inline void
554  swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
555  unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
556  { __x.swap(__y); }
557 
558  template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
559  inline bool
560  operator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
561  const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
562  { return __x._M_equal(__y); }
563 
564  template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
565  inline bool
566  operator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
567  const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
568  { return !(__x == __y); }
569 
570 } // namespace __profile
571 } // namespace std
572 
573 #undef _GLIBCXX_BASE
574 #undef _GLIBCXX_STD_BASE
575 
576 #endif // __GXX_EXPERIMENTAL_CXX0X__
577 
578 #endif
std::initializer_list
initializer_list
Definition: initializer_list:47
std::allocator
The standard allocator, as per [20.4].
Definition: bits/alloc_traits.h:43
std::equal_to
One of the comparison functors.
Definition: stl_function.h:206
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:281
std::end
constexpr const _Tp * end(initializer_list< _Tp > __ils) noexcept
Return an iterator pointing to one past the last element of the initilizer_list.
Definition: initializer_list:99
std::unordered_multiset
A standard container composed of equivalent keys (possibly containing multiple of each key value) in ...
Definition: unordered_set.h:346
std::pair
Struct holding two objects of arbitrary type.
Definition: stl_pair.h:88
std::__profile::unordered_set
Unordered_set wrapper with performance instrumentation.
Definition: profile/unordered_set:50
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:112
std::begin
constexpr const _Tp * begin(initializer_list< _Tp > __ils) noexcept
Return an iterator pointing to the first element of the initilizer_list.
Definition: initializer_list:89
std::size
constexpr size_t size() const _GLIBCXX_NOEXCEPT
Returns the total number of bits.
Definition: bitset:1284
std::__profile::unordered_multiset
Unordered_multiset wrapper with performance instrumentation.
Definition: profile/unordered_set:318