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