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