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