libstdc++
profile/unordered_map
Go to the documentation of this file.
1 // Profiling unordered_map/unordered_multimap implementation -*- C++ -*-
2 
3 // Copyright (C) 2009-2015 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  unordered_map() = default;
80 
81  explicit
82  unordered_map(size_type __n,
83  const hasher& __hf = hasher(),
84  const key_equal& __eql = key_equal(),
85  const allocator_type& __a = allocator_type())
86  : _Base(__n, __hf, __eql, __a) { }
87 
88  template<typename _InputIterator>
89  unordered_map(_InputIterator __f, _InputIterator __l,
90  size_type __n = 0,
91  const hasher& __hf = hasher(),
92  const key_equal& __eql = key_equal(),
93  const allocator_type& __a = allocator_type())
94  : _Base(__f, __l, __n, __hf, __eql, __a) { }
95 
96  unordered_map(const unordered_map&) = default;
97 
98  unordered_map(const _Base& __x)
99  : _Base(__x) { }
100 
101  unordered_map(unordered_map&&) = default;
102 
103  explicit
104  unordered_map(const allocator_type& __a)
105  : _Base(__a) { }
106 
107  unordered_map(const unordered_map& __umap,
108  const allocator_type& __a)
109  : _Base(__umap, __a) { }
110 
111  unordered_map(unordered_map&& __umap,
112  const allocator_type& __a)
113  : _Base(std::move(__umap._M_base()), __a) { }
114 
115  unordered_map(initializer_list<value_type> __l,
116  size_type __n = 0,
117  const hasher& __hf = hasher(),
118  const key_equal& __eql = key_equal(),
119  const allocator_type& __a = allocator_type())
120  : _Base(__l, __n, __hf, __eql, __a) { }
121 
122  unordered_map(size_type __n, const allocator_type& __a)
123  : unordered_map(__n, hasher(), key_equal(), __a)
124  { }
125 
126  unordered_map(size_type __n, const hasher& __hf,
127  const allocator_type& __a)
128  : unordered_map(__n, __hf, key_equal(), __a)
129  { }
130 
131  template<typename _InputIterator>
132  unordered_map(_InputIterator __first, _InputIterator __last,
133  size_type __n,
134  const allocator_type& __a)
135  : unordered_map(__first, __last, __n, hasher(), key_equal(), __a)
136  { }
137 
138  template<typename _InputIterator>
139  unordered_map(_InputIterator __first, _InputIterator __last,
140  size_type __n, const hasher& __hf,
141  const allocator_type& __a)
142  : unordered_map(__first, __last, __n, __hf, key_equal(), __a)
143  { }
144 
145  unordered_map(initializer_list<value_type> __l,
146  size_type __n,
147  const allocator_type& __a)
148  : unordered_map(__l, __n, hasher(), key_equal(), __a)
149  { }
150 
151  unordered_map(initializer_list<value_type> __l,
152  size_type __n, const hasher& __hf,
153  const allocator_type& __a)
154  : unordered_map(__l, __n, __hf, key_equal(), __a)
155  { }
156 
157  unordered_map&
158  operator=(const unordered_map&) = default;
159 
160  unordered_map&
161  operator=(unordered_map&&) = default;
162 
163  unordered_map&
164  operator=(initializer_list<value_type> __l)
165  {
166  this->_M_profile_destruct();
167  _M_base() = __l;
168  this->_M_profile_construct();
169  return *this;
170  }
171 
172  void
173  clear() noexcept
174  {
175  this->_M_profile_destruct();
176  _Base::clear();
177  this->_M_profile_construct();
178  }
179 
180  template<typename... _Args>
181  std::pair<iterator, bool>
182  emplace(_Args&&... __args)
183  {
184  size_type __old_size = _Base::bucket_count();
185  std::pair<iterator, bool> __res
186  = _Base::emplace(std::forward<_Args>(__args)...);
187  this->_M_profile_resize(__old_size);
188  return __res;
189  }
190 
191  template<typename... _Args>
192  iterator
193  emplace_hint(const_iterator __it, _Args&&... __args)
194  {
195  size_type __old_size = _Base::bucket_count();
196  iterator __res
197  = _Base::emplace_hint(__it, std::forward<_Args>(__args)...);
198  this->_M_profile_resize(__old_size);
199  return __res;
200  }
201 
202  void
203  insert(std::initializer_list<value_type> __l)
204  {
205  size_type __old_size = _Base::bucket_count();
206  _Base::insert(__l);
207  this->_M_profile_resize(__old_size);
208  }
209 
210  std::pair<iterator, bool>
211  insert(const value_type& __obj)
212  {
213  size_type __old_size = _Base::bucket_count();
214  std::pair<iterator, bool> __res = _Base::insert(__obj);
215  this->_M_profile_resize(__old_size);
216  return __res;
217  }
218 
219  iterator
220  insert(const_iterator __iter, const value_type& __v)
221  {
222  size_type __old_size = _Base::bucket_count();
223  iterator __res = _Base::insert(__iter, __v);
224  this->_M_profile_resize(__old_size);
225  return __res;
226  }
227 
228  template<typename _Pair, typename = typename
229  std::enable_if<std::is_constructible<value_type,
230  _Pair&&>::value>::type>
231  std::pair<iterator, bool>
232  insert(_Pair&& __obj)
233  {
234  size_type __old_size = _Base::bucket_count();
235  std::pair<iterator, bool> __res
236  = _Base::insert(std::forward<_Pair>(__obj));
237  this->_M_profile_resize(__old_size);
238  return __res;
239  }
240 
241  template<typename _Pair, typename = typename
242  std::enable_if<std::is_constructible<value_type,
243  _Pair&&>::value>::type>
244  iterator
245  insert(const_iterator __iter, _Pair&& __v)
246  {
247  size_type __old_size = _Base::bucket_count();
248  iterator __res = _Base::insert(__iter, std::forward<_Pair>(__v));
249  this->_M_profile_resize(__old_size);
250  return __res;
251  }
252 
253  template<typename _InputIter>
254  void
255  insert(_InputIter __first, _InputIter __last)
256  {
257  size_type __old_size = _Base::bucket_count();
258  _Base::insert(__first, __last);
259  this->_M_profile_resize(__old_size);
260  }
261 
262  // operator[]
263  mapped_type&
264  operator[](const _Key& __k)
265  {
266  size_type __old_size = _Base::bucket_count();
267  mapped_type& __res = _M_base()[__k];
268  this->_M_profile_resize(__old_size);
269  return __res;
270  }
271 
272  mapped_type&
273  operator[](_Key&& __k)
274  {
275  size_type __old_size = _Base::bucket_count();
276  mapped_type& __res = _M_base()[std::move(__k)];
277  this->_M_profile_resize(__old_size);
278  return __res;
279  }
280 
281  void
282  swap(unordered_map& __x)
283  noexcept( noexcept(__x._M_base().swap(__x)) )
284  {
285  _Base::swap(__x._M_base());
286  this->_M_swap(__x);
287  }
288 
289  void rehash(size_type __n)
290  {
291  size_type __old_size = _Base::bucket_count();
292  _Base::rehash(__n);
293  this->_M_profile_resize(__old_size);
294  }
295  };
296 
297  template<typename _Key, typename _Tp, typename _Hash,
298  typename _Pred, typename _Alloc>
299  inline void
300  swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
301  unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
302  { __x.swap(__y); }
303 
304  template<typename _Key, typename _Tp, typename _Hash,
305  typename _Pred, typename _Alloc>
306  inline bool
307  operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
308  const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
309  { return static_cast<const _GLIBCXX_STD_BASE&>(__x) == __y; }
310 
311  template<typename _Key, typename _Tp, typename _Hash,
312  typename _Pred, typename _Alloc>
313  inline bool
314  operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
315  const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
316  { return !(__x == __y); }
317 
318 #undef _GLIBCXX_BASE
319 #undef _GLIBCXX_STD_BASE
320 #define _GLIBCXX_BASE unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>
321 #define _GLIBCXX_STD_BASE _GLIBCXX_STD_C::_GLIBCXX_BASE
322 
323  /// Class std::unordered_multimap wrapper with performance instrumentation.
324  template<typename _Key, typename _Tp,
325  typename _Hash = std::hash<_Key>,
326  typename _Pred = std::equal_to<_Key>,
327  typename _Alloc = std::allocator<std::pair<const _Key, _Tp> > >
328  class unordered_multimap
329  : public _GLIBCXX_STD_BASE,
330  public _Unordered_profile<unordered_multimap<_Key, _Tp,
331  _Hash, _Pred, _Alloc>,
332  false>
333  {
334  typedef typename _GLIBCXX_STD_BASE _Base;
335 
336  _Base&
337  _M_base() noexcept { return *this; }
338 
339  const _Base&
340  _M_base() const noexcept { return *this; }
341 
342  public:
343  typedef typename _Base::size_type size_type;
344  typedef typename _Base::hasher hasher;
345  typedef typename _Base::key_equal key_equal;
346  typedef typename _Base::allocator_type allocator_type;
347  typedef typename _Base::key_type key_type;
348  typedef typename _Base::value_type value_type;
349  typedef typename _Base::difference_type difference_type;
350  typedef typename _Base::reference reference;
351  typedef typename _Base::const_reference const_reference;
352 
353  typedef typename _Base::iterator iterator;
354  typedef typename _Base::const_iterator const_iterator;
355 
356  unordered_multimap() = default;
357 
358  explicit
359  unordered_multimap(size_type __n,
360  const hasher& __hf = hasher(),
361  const key_equal& __eql = key_equal(),
362  const allocator_type& __a = allocator_type())
363  : _Base(__n, __hf, __eql, __a) { }
364 
365  template<typename _InputIterator>
366  unordered_multimap(_InputIterator __f, _InputIterator __l,
367  size_type __n = 0,
368  const hasher& __hf = hasher(),
369  const key_equal& __eql = key_equal(),
370  const allocator_type& __a = allocator_type())
371  : _Base(__f, __l, __n, __hf, __eql, __a) { }
372 
373  unordered_multimap(const unordered_multimap&) = default;
374 
375  unordered_multimap(const _Base& __x)
376  : _Base(__x) { }
377 
378  unordered_multimap(unordered_multimap&&) = default;
379 
380  explicit
381  unordered_multimap(const allocator_type& __a)
382  : _Base(__a) { }
383 
384  unordered_multimap(const unordered_multimap& __ummap,
385  const allocator_type& __a)
386  : _Base(__ummap._M_base(), __a) { }
387 
388  unordered_multimap(unordered_multimap&& __ummap,
389  const allocator_type& __a)
390  : _Base(std::move(__ummap._M_base()), __a) { }
391 
392  unordered_multimap(initializer_list<value_type> __l,
393  size_type __n = 0,
394  const hasher& __hf = hasher(),
395  const key_equal& __eql = key_equal(),
396  const allocator_type& __a = allocator_type())
397  : _Base(__l, __n, __hf, __eql, __a) { }
398 
399  unordered_multimap(size_type __n, const allocator_type& __a)
400  : unordered_multimap(__n, hasher(), key_equal(), __a)
401  { }
402 
403  unordered_multimap(size_type __n, const hasher& __hf,
404  const allocator_type& __a)
405  : unordered_multimap(__n, __hf, key_equal(), __a)
406  { }
407 
408  template<typename _InputIterator>
409  unordered_multimap(_InputIterator __first, _InputIterator __last,
410  size_type __n,
411  const allocator_type& __a)
412  : unordered_multimap(__first, __last, __n, hasher(), key_equal(), __a)
413  { }
414 
415  template<typename _InputIterator>
416  unordered_multimap(_InputIterator __first, _InputIterator __last,
417  size_type __n, const hasher& __hf,
418  const allocator_type& __a)
419  : unordered_multimap(__first, __last, __n, __hf, key_equal(), __a)
420  { }
421 
422  unordered_multimap(initializer_list<value_type> __l,
423  size_type __n,
424  const allocator_type& __a)
425  : unordered_multimap(__l, __n, hasher(), key_equal(), __a)
426  { }
427 
428  unordered_multimap(initializer_list<value_type> __l,
429  size_type __n, const hasher& __hf,
430  const allocator_type& __a)
431  : unordered_multimap(__l, __n, __hf, key_equal(), __a)
432  { }
433 
434  unordered_multimap&
435  operator=(const unordered_multimap&) = default;
436 
437  unordered_multimap&
438  operator=(unordered_multimap&&) = default;
439 
440  unordered_multimap&
441  operator=(initializer_list<value_type> __l)
442  {
443  this->_M_profile_destruct();
444  _M_base() = __l;
445  this->_M_profile_construct();
446  return *this;
447  }
448 
449  void
450  clear() noexcept
451  {
452  this->_M_profile_destruct();
453  _Base::clear();
454  this->_M_profile_construct();
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  this->_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  this->_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  this->_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  this->_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  this->_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  this->_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  this->_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  this->_M_profile_resize(__old_size);
536  }
537 
538  void
539  swap(unordered_multimap& __x)
540  noexcept( noexcept(__x._M_base().swap(__x)) )
541  {
542  _Base::swap(__x._M_base());
543  this->_M_swap(__x);
544  }
545 
546  void
547  rehash(size_type __n)
548  {
549  size_type __old_size = _Base::bucket_count();
550  _Base::rehash(__n);
551  this->_M_profile_resize(__old_size);
552  }
553  };
554 
555  template<typename _Key, typename _Tp, typename _Hash,
556  typename _Pred, typename _Alloc>
557  inline void
558  swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
559  unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
560  { __x.swap(__y); }
561 
562  template<typename _Key, typename _Tp, typename _Hash,
563  typename _Pred, typename _Alloc>
564  inline bool
565  operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
566  const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
567  { return static_cast<const _GLIBCXX_STD_BASE&>(__x) == __y; }
568 
569  template<typename _Key, typename _Tp, typename _Hash,
570  typename _Pred, typename _Alloc>
571  inline bool
572  operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
573  const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
574  { return !(__x == __y); }
575 
576 } // namespace __profile
577 } // namespace std
578 
579 #undef _GLIBCXX_BASE
580 #undef _GLIBCXX_STD_BASE
581 
582 #endif // C++11
583 
584 #endif