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, 2011, 2012 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 unordered_map& __x)
94  : _Base(__x)
95  {
96  __profcxx_hashtable_construct(this, _Base::bucket_count());
97  __profcxx_hashtable_construct2(this);
98  }
99 
100  unordered_map(const _Base& __x)
101  : _Base(__x)
102  {
103  __profcxx_hashtable_construct(this, _Base::bucket_count());
104  __profcxx_hashtable_construct2(this);
105  }
106 
107  unordered_map(unordered_map&& __x)
108  : _Base(std::move(__x))
109  {
110  __profcxx_hashtable_construct(this, _Base::bucket_count());
111  __profcxx_hashtable_construct2(this);
112  }
113 
114  unordered_map(initializer_list<value_type> __l,
115  size_type __n = 0,
116  const hasher& __hf = hasher(),
117  const key_equal& __eql = key_equal(),
118  const allocator_type& __a = allocator_type())
119  : _Base(__l, __n, __hf, __eql, __a) { }
120 
121  unordered_map&
122  operator=(const unordered_map& __x)
123  {
124  *static_cast<_Base*>(this) = __x;
125  return *this;
126  }
127 
128  unordered_map&
129  operator=(unordered_map&& __x)
130  {
131  // NB: DR 1204.
132  // NB: DR 675.
133  this->clear();
134  this->swap(__x);
135  return *this;
136  }
137 
138  unordered_map&
139  operator=(initializer_list<value_type> __l)
140  {
141  this->clear();
142  this->insert(__l);
143  return *this;
144  }
145 
146  ~unordered_map() noexcept
147  {
148  __profcxx_hashtable_destruct(this, _Base::bucket_count(),
149  _Base::size());
150  _M_profile_destruct();
151  }
152 
153  _Base&
154  _M_base() noexcept { return *this; }
155 
156  const _Base&
157  _M_base() const noexcept { return *this; }
158 
159  void
160  clear() noexcept
161  {
162  __profcxx_hashtable_destruct(this, _Base::bucket_count(),
163  _Base::size());
164  _M_profile_destruct();
165  _Base::clear();
166  }
167 
168  template<typename... _Args>
169  std::pair<iterator, bool>
170  emplace(_Args&&... __args)
171  {
172  size_type __old_size = _Base::bucket_count();
173  std::pair<iterator, bool> __res
174  = _Base::emplace(std::forward<_Args>(__args)...);
175  _M_profile_resize(__old_size);
176  return __res;
177  }
178 
179  template<typename... _Args>
180  iterator
181  emplace_hint(const_iterator __it, _Args&&... __args)
182  {
183  size_type __old_size = _Base::bucket_count();
184  iterator __res
185  = _Base::emplace_hint(__it, std::forward<_Args>(__args)...);
186  _M_profile_resize(__old_size);
187  return __res;
188  }
189 
190  void
191  insert(std::initializer_list<value_type> __l)
192  {
193  size_type __old_size = _Base::bucket_count();
194  _Base::insert(__l);
195  _M_profile_resize(__old_size);
196  }
197 
198  std::pair<iterator, bool>
199  insert(const value_type& __obj)
200  {
201  size_type __old_size = _Base::bucket_count();
202  std::pair<iterator, bool> __res = _Base::insert(__obj);
203  _M_profile_resize(__old_size);
204  return __res;
205  }
206 
207  iterator
208  insert(const_iterator __iter, const value_type& __v)
209  {
210  size_type __old_size = _Base::bucket_count();
211  iterator __res = _Base::insert(__iter, __v);
212  _M_profile_resize(__old_size);
213  return __res;
214  }
215 
216  template<typename _Pair, typename = typename
217  std::enable_if<std::is_constructible<value_type,
218  _Pair&&>::value>::type>
219  std::pair<iterator, bool>
220  insert(_Pair&& __obj)
221  {
222  size_type __old_size = _Base::bucket_count();
223  std::pair<iterator, bool> __res
224  = _Base::insert(std::forward<_Pair>(__obj));
225  _M_profile_resize(__old_size);
226  return __res;
227  }
228 
229  template<typename _Pair, typename = typename
230  std::enable_if<std::is_constructible<value_type,
231  _Pair&&>::value>::type>
232  iterator
233  insert(const_iterator __iter, _Pair&& __v)
234  {
235  size_type __old_size = _Base::bucket_count();
236  iterator __res = _Base::insert(__iter, std::forward<_Pair>(__v));
237  _M_profile_resize(__old_size);
238  return __res;
239  }
240 
241  template<typename _InputIter>
242  void
243  insert(_InputIter __first, _InputIter __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
251  insert(const value_type* __first, const value_type* __last)
252  {
253  size_type __old_size = _Base::bucket_count();
254  _Base::insert(__first, __last);
255  _M_profile_resize(__old_size);
256  }
257 
258  // operator[]
259  mapped_type&
260  operator[](const _Key& __k)
261  {
262  size_type __old_size = _Base::bucket_count();
263  mapped_type& __res = _M_base()[__k];
264  _M_profile_resize(__old_size);
265  return __res;
266  }
267 
268  mapped_type&
269  operator[](_Key&& __k)
270  {
271  size_type __old_size = _Base::bucket_count();
272  mapped_type& __res = _M_base()[std::move(__k)];
273  _M_profile_resize(__old_size);
274  return __res;
275  }
276 
277  void
278  swap(unordered_map& __x)
279  { _Base::swap(__x); }
280 
281  void rehash(size_type __n)
282  {
283  size_type __old_size = _Base::bucket_count();
284  _Base::rehash(__n);
285  _M_profile_resize(__old_size);
286  }
287 
288  private:
289  void
290  _M_profile_resize(size_type __old_size)
291  {
292  size_type __new_size = _Base::bucket_count();
293  if (__old_size != __new_size)
294  __profcxx_hashtable_resize(this, __old_size, __new_size);
295  }
296 
297  void
298  _M_profile_destruct()
299  {
300  size_type __hops = 0, __lc = 0, __chain = 0;
301  iterator __it = this->begin();
302  while (__it != this->end())
303  {
304  size_type __bkt = this->bucket(__it->first);
305  auto __lit = this->begin(__bkt);
306  auto __lend = this->end(__bkt);
307  for (++__it, ++__lit; __lit != __lend; ++__it, ++__lit)
308  ++__chain;
309  if (__chain)
310  {
311  ++__chain;
312  __lc = __lc > __chain ? __lc : __chain;
313  __hops += __chain * (__chain - 1) / 2;
314  __chain = 0;
315  }
316  }
317  __profcxx_hashtable_destruct2(this, __lc, _Base::size(), __hops);
318  }
319  };
320 
321  template<typename _Key, typename _Tp, typename _Hash,
322  typename _Pred, typename _Alloc>
323  inline void
324  swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
325  unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
326  { __x.swap(__y); }
327 
328  template<typename _Key, typename _Tp, typename _Hash,
329  typename _Pred, typename _Alloc>
330  inline bool
331  operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
332  const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
333  { return __x._M_equal(__y); }
334 
335  template<typename _Key, typename _Tp, typename _Hash,
336  typename _Pred, typename _Alloc>
337  inline bool
338  operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
339  const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
340  { return !(__x == __y); }
341 
342 #undef _GLIBCXX_BASE
343 #undef _GLIBCXX_STD_BASE
344 #define _GLIBCXX_BASE unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>
345 #define _GLIBCXX_STD_BASE _GLIBCXX_STD_C::_GLIBCXX_BASE
346 
347  /// Class std::unordered_multimap wrapper with performance instrumentation.
348  template<typename _Key, typename _Tp,
349  typename _Hash = std::hash<_Key>,
350  typename _Pred = std::equal_to<_Key>,
351  typename _Alloc = std::allocator<_Key> >
352  class unordered_multimap
353  : public _GLIBCXX_STD_BASE
354  {
355  typedef typename _GLIBCXX_STD_BASE _Base;
356 
357  public:
358  typedef typename _Base::size_type size_type;
359  typedef typename _Base::hasher hasher;
360  typedef typename _Base::key_equal key_equal;
361  typedef typename _Base::allocator_type allocator_type;
362  typedef typename _Base::key_type key_type;
363  typedef typename _Base::value_type value_type;
364  typedef typename _Base::difference_type difference_type;
365  typedef typename _Base::reference reference;
366  typedef typename _Base::const_reference const_reference;
367 
368  typedef typename _Base::iterator iterator;
369  typedef typename _Base::const_iterator const_iterator;
370 
371  explicit
372  unordered_multimap(size_type __n = 10,
373  const hasher& __hf = hasher(),
374  const key_equal& __eql = key_equal(),
375  const allocator_type& __a = allocator_type())
376  : _Base(__n, __hf, __eql, __a)
377  {
378  __profcxx_hashtable_construct(this, _Base::bucket_count());
379  }
380  template<typename _InputIterator>
381  unordered_multimap(_InputIterator __f, _InputIterator __l,
382  size_type __n = 0,
383  const hasher& __hf = hasher(),
384  const key_equal& __eql = key_equal(),
385  const allocator_type& __a = allocator_type())
386  : _Base(__f, __l, __n, __hf, __eql, __a)
387  {
388  __profcxx_hashtable_construct(this, _Base::bucket_count());
389  }
390 
391  unordered_multimap(const unordered_multimap& __x)
392  : _Base(__x)
393  {
394  __profcxx_hashtable_construct(this, _Base::bucket_count());
395  }
396 
397  unordered_multimap(const _Base& __x)
398  : _Base(__x)
399  {
400  __profcxx_hashtable_construct(this, _Base::bucket_count());
401  }
402 
403  unordered_multimap(unordered_multimap&& __x)
404  : _Base(std::move(__x))
405  {
406  __profcxx_hashtable_construct(this, _Base::bucket_count());
407  }
408 
409  unordered_multimap(initializer_list<value_type> __l,
410  size_type __n = 0,
411  const hasher& __hf = hasher(),
412  const key_equal& __eql = key_equal(),
413  const allocator_type& __a = allocator_type())
414  : _Base(__l, __n, __hf, __eql, __a) { }
415 
416  unordered_multimap&
417  operator=(const unordered_multimap& __x)
418  {
419  *static_cast<_Base*>(this) = __x;
420  return *this;
421  }
422 
423  unordered_multimap&
424  operator=(unordered_multimap&& __x)
425  {
426  // NB: DR 1204.
427  // NB: DR 675.
428  this->clear();
429  this->swap(__x);
430  return *this;
431  }
432 
433  unordered_multimap&
434  operator=(initializer_list<value_type> __l)
435  {
436  this->clear();
437  this->insert(__l);
438  return *this;
439  }
440 
441  ~unordered_multimap() noexcept
442  {
443  __profcxx_hashtable_destruct(this, _Base::bucket_count(),
444  _Base::size());
445  _M_profile_destruct();
446  }
447 
448  void
449  clear() noexcept
450  {
451  __profcxx_hashtable_destruct(this, _Base::bucket_count(),
452  _Base::size());
453  _M_profile_destruct();
454  _Base::clear();
455  }
456 
457  template<typename... _Args>
458  iterator
459  emplace(_Args&&... __args)
460  {
461  size_type __old_size = _Base::bucket_count();
462  iterator __res
463  = _Base::emplace(std::forward<_Args>(__args)...);
464  _M_profile_resize(__old_size);
465  return __res;
466  }
467 
468  template<typename... _Args>
469  iterator
470  emplace_hint(const_iterator __it, _Args&&... __args)
471  {
472  size_type __old_size = _Base::bucket_count();
473  iterator __res
474  = _Base::emplace_hint(__it, std::forward<_Args>(__args)...);
475  _M_profile_resize(__old_size);
476  return __res;
477  }
478 
479  void
480  insert(std::initializer_list<value_type> __l)
481  {
482  size_type __old_size = _Base::bucket_count();
483  _Base::insert(__l);
484  _M_profile_resize(__old_size);
485  }
486 
487  iterator
488  insert(const value_type& __obj)
489  {
490  size_type __old_size = _Base::bucket_count();
491  iterator __res = _Base::insert(__obj);
492  _M_profile_resize(__old_size);
493  return __res;
494  }
495 
496  iterator
497  insert(const_iterator __iter, const value_type& __v)
498  {
499  size_type __old_size = _Base::bucket_count();
500  iterator __res = _Base::insert(__iter, __v);
501  _M_profile_resize(__old_size);
502  return __res;
503  }
504 
505  template<typename _Pair, typename = typename
506  std::enable_if<std::is_constructible<value_type,
507  _Pair&&>::value>::type>
508  iterator
509  insert(_Pair&& __obj)
510  {
511  size_type __old_size = _Base::bucket_count();
512  iterator __res = _Base::insert(std::forward<_Pair>(__obj));
513  _M_profile_resize(__old_size);
514  return __res;
515  }
516 
517  template<typename _Pair, typename = typename
518  std::enable_if<std::is_constructible<value_type,
519  _Pair&&>::value>::type>
520  iterator
521  insert(const_iterator __iter, _Pair&& __v)
522  {
523  size_type __old_size = _Base::bucket_count();
524  iterator __res = _Base::insert(__iter, std::forward<_Pair>(__v));
525  _M_profile_resize(__old_size);
526  return __res;
527  }
528 
529  template<typename _InputIter>
530  void
531  insert(_InputIter __first, _InputIter __last)
532  {
533  size_type __old_size = _Base::bucket_count();
534  _Base::insert(__first, __last);
535  _M_profile_resize(__old_size);
536  }
537 
538  void
539  insert(const value_type* __first, const value_type* __last)
540  {
541  size_type __old_size = _Base::bucket_count();
542  _Base::insert(__first, __last);
543  _M_profile_resize(__old_size);
544  }
545 
546  void
547  swap(unordered_multimap& __x)
548  { _Base::swap(__x); }
549 
550  void rehash(size_type __n)
551  {
552  size_type __old_size = _Base::bucket_count();
553  _Base::rehash(__n);
554  _M_profile_resize(__old_size);
555  }
556 
557  private:
558  void
559  _M_profile_resize(size_type __old_size)
560  {
561  size_type __new_size = _Base::bucket_count();
562  if (__old_size != __new_size)
563  __profcxx_hashtable_resize(this, __old_size, __new_size);
564  }
565 
566  void
567  _M_profile_destruct()
568  {
569  size_type __hops = 0, __lc = 0, __chain = 0;
570  iterator __it = this->begin();
571  while (__it != this->end())
572  {
573  size_type __bkt = this->bucket(__it->first);
574  auto __lit = this->begin(__bkt);
575  auto __lend = this->end(__bkt);
576  for (++__it, ++__lit; __lit != __lend; ++__it, ++__lit)
577  ++__chain;
578  if (__chain)
579  {
580  ++__chain;
581  __lc = __lc > __chain ? __lc : __chain;
582  __hops += __chain * (__chain - 1) / 2;
583  __chain = 0;
584  }
585  }
586  __profcxx_hashtable_destruct2(this, __lc, _Base::size(), __hops);
587  }
588  };
589 
590  template<typename _Key, typename _Tp, typename _Hash,
591  typename _Pred, typename _Alloc>
592  inline void
593  swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
594  unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
595  { __x.swap(__y); }
596 
597  template<typename _Key, typename _Tp, typename _Hash,
598  typename _Pred, typename _Alloc>
599  inline bool
600  operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
601  const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
602  { return __x._M_equal(__y); }
603 
604  template<typename _Key, typename _Tp, typename _Hash,
605  typename _Pred, typename _Alloc>
606  inline bool
607  operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
608  const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
609  { return !(__x == __y); }
610 
611 } // namespace __profile
612 } // namespace std
613 
614 #undef _GLIBCXX_BASE
615 #undef _GLIBCXX_STD_BASE
616 
617 #endif // __GXX_EXPERIMENTAL_CXX0X__
618 
619 #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::is_constructible
is_constructible
Definition: type_traits:916
std::unordered_map
A standard container composed of unique keys (containing at most one of each key value) that associat...
Definition: unordered_map.h:264
std::equal_to
One of the comparison functors.
Definition: stl_function.h:206
std::enable_if
Define a member typedef type only if a boolean constant is true.
Definition: type_traits:1718
std::__profile::unordered_multimap
Class std::unordered_multimap wrapper with performance instrumentation.
Definition: profile/unordered_map:352
std::__profile::unordered_map
Class std::unordered_map wrapper with performance instrumentation.
Definition: profile/unordered_map:50
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::pair
Struct holding two objects of arbitrary type.
Definition: stl_pair.h:88
std::unordered_multimap
A standard container composed of equivalent keys (possibly containing multiple of each key value) tha...
Definition: unordered_map.h:332
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