libstdc++
profile/unordered_map
Go to the documentation of this file.
1 // Profiling unordered_map/unordered_multimap implementation -*- C++ -*-
2 
3 // Copyright (C) 2009-2019 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  noexcept(noexcept(__x.swap(__y)))
303  { __x.swap(__y); }
304 
305  template<typename _Key, typename _Tp, typename _Hash,
306  typename _Pred, typename _Alloc>
307  inline bool
308  operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
309  const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
310  { return static_cast<const _GLIBCXX_STD_BASE&>(__x) == __y; }
311 
312  template<typename _Key, typename _Tp, typename _Hash,
313  typename _Pred, typename _Alloc>
314  inline bool
315  operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
316  const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
317  { return !(__x == __y); }
318 
319 #undef _GLIBCXX_BASE
320 #undef _GLIBCXX_STD_BASE
321 #define _GLIBCXX_BASE unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>
322 #define _GLIBCXX_STD_BASE _GLIBCXX_STD_C::_GLIBCXX_BASE
323 
324  /// Class std::unordered_multimap wrapper with performance instrumentation.
325  template<typename _Key, typename _Tp,
326  typename _Hash = std::hash<_Key>,
327  typename _Pred = std::equal_to<_Key>,
328  typename _Alloc = std::allocator<std::pair<const _Key, _Tp> > >
329  class unordered_multimap
330  : public _GLIBCXX_STD_BASE,
331  public _Unordered_profile<unordered_multimap<_Key, _Tp,
332  _Hash, _Pred, _Alloc>,
333  false>
334  {
335  typedef typename _GLIBCXX_STD_BASE _Base;
336 
337  _Base&
338  _M_base() noexcept { return *this; }
339 
340  const _Base&
341  _M_base() const noexcept { return *this; }
342 
343  public:
344  typedef typename _Base::size_type size_type;
345  typedef typename _Base::hasher hasher;
346  typedef typename _Base::key_equal key_equal;
347  typedef typename _Base::allocator_type allocator_type;
348  typedef typename _Base::key_type key_type;
349  typedef typename _Base::value_type value_type;
350  typedef typename _Base::difference_type difference_type;
351  typedef typename _Base::reference reference;
352  typedef typename _Base::const_reference const_reference;
353 
354  typedef typename _Base::iterator iterator;
355  typedef typename _Base::const_iterator const_iterator;
356 
357  unordered_multimap() = default;
358 
359  explicit
360  unordered_multimap(size_type __n,
361  const hasher& __hf = hasher(),
362  const key_equal& __eql = key_equal(),
363  const allocator_type& __a = allocator_type())
364  : _Base(__n, __hf, __eql, __a) { }
365 
366  template<typename _InputIterator>
367  unordered_multimap(_InputIterator __f, _InputIterator __l,
368  size_type __n = 0,
369  const hasher& __hf = hasher(),
370  const key_equal& __eql = key_equal(),
371  const allocator_type& __a = allocator_type())
372  : _Base(__f, __l, __n, __hf, __eql, __a) { }
373 
374  unordered_multimap(const unordered_multimap&) = default;
375 
376  unordered_multimap(const _Base& __x)
377  : _Base(__x) { }
378 
379  unordered_multimap(unordered_multimap&&) = default;
380 
381  explicit
382  unordered_multimap(const allocator_type& __a)
383  : _Base(__a) { }
384 
385  unordered_multimap(const unordered_multimap& __ummap,
386  const allocator_type& __a)
387  : _Base(__ummap._M_base(), __a) { }
388 
389  unordered_multimap(unordered_multimap&& __ummap,
390  const allocator_type& __a)
391  : _Base(std::move(__ummap._M_base()), __a) { }
392 
393  unordered_multimap(initializer_list<value_type> __l,
394  size_type __n = 0,
395  const hasher& __hf = hasher(),
396  const key_equal& __eql = key_equal(),
397  const allocator_type& __a = allocator_type())
398  : _Base(__l, __n, __hf, __eql, __a) { }
399 
400  unordered_multimap(size_type __n, const allocator_type& __a)
401  : unordered_multimap(__n, hasher(), key_equal(), __a)
402  { }
403 
404  unordered_multimap(size_type __n, const hasher& __hf,
405  const allocator_type& __a)
406  : unordered_multimap(__n, __hf, key_equal(), __a)
407  { }
408 
409  template<typename _InputIterator>
410  unordered_multimap(_InputIterator __first, _InputIterator __last,
411  size_type __n,
412  const allocator_type& __a)
413  : unordered_multimap(__first, __last, __n, hasher(), key_equal(), __a)
414  { }
415 
416  template<typename _InputIterator>
417  unordered_multimap(_InputIterator __first, _InputIterator __last,
418  size_type __n, const hasher& __hf,
419  const allocator_type& __a)
420  : unordered_multimap(__first, __last, __n, __hf, key_equal(), __a)
421  { }
422 
423  unordered_multimap(initializer_list<value_type> __l,
424  size_type __n,
425  const allocator_type& __a)
426  : unordered_multimap(__l, __n, hasher(), key_equal(), __a)
427  { }
428 
429  unordered_multimap(initializer_list<value_type> __l,
430  size_type __n, const hasher& __hf,
431  const allocator_type& __a)
432  : unordered_multimap(__l, __n, __hf, key_equal(), __a)
433  { }
434 
435  unordered_multimap&
436  operator=(const unordered_multimap&) = default;
437 
438  unordered_multimap&
439  operator=(unordered_multimap&&) = default;
440 
441  unordered_multimap&
442  operator=(initializer_list<value_type> __l)
443  {
444  this->_M_profile_destruct();
445  _M_base() = __l;
446  this->_M_profile_construct();
447  return *this;
448  }
449 
450  void
451  clear() noexcept
452  {
453  this->_M_profile_destruct();
454  _Base::clear();
455  this->_M_profile_construct();
456  }
457 
458  template<typename... _Args>
459  iterator
460  emplace(_Args&&... __args)
461  {
462  size_type __old_size = _Base::bucket_count();
463  iterator __res
464  = _Base::emplace(std::forward<_Args>(__args)...);
465  this->_M_profile_resize(__old_size);
466  return __res;
467  }
468 
469  template<typename... _Args>
470  iterator
471  emplace_hint(const_iterator __it, _Args&&... __args)
472  {
473  size_type __old_size = _Base::bucket_count();
474  iterator __res
475  = _Base::emplace_hint(__it, std::forward<_Args>(__args)...);
476  this->_M_profile_resize(__old_size);
477  return __res;
478  }
479 
480  void
481  insert(std::initializer_list<value_type> __l)
482  {
483  size_type __old_size = _Base::bucket_count();
484  _Base::insert(__l);
485  this->_M_profile_resize(__old_size);
486  }
487 
488  iterator
489  insert(const value_type& __obj)
490  {
491  size_type __old_size = _Base::bucket_count();
492  iterator __res = _Base::insert(__obj);
493  this->_M_profile_resize(__old_size);
494  return __res;
495  }
496 
497  iterator
498  insert(const_iterator __iter, const value_type& __v)
499  {
500  size_type __old_size = _Base::bucket_count();
501  iterator __res = _Base::insert(__iter, __v);
502  this->_M_profile_resize(__old_size);
503  return __res;
504  }
505 
506  template<typename _Pair, typename = typename
507  std::enable_if<std::is_constructible<value_type,
508  _Pair&&>::value>::type>
509  iterator
510  insert(_Pair&& __obj)
511  {
512  size_type __old_size = _Base::bucket_count();
513  iterator __res = _Base::insert(std::forward<_Pair>(__obj));
514  this->_M_profile_resize(__old_size);
515  return __res;
516  }
517 
518  template<typename _Pair, typename = typename
519  std::enable_if<std::is_constructible<value_type,
520  _Pair&&>::value>::type>
521  iterator
522  insert(const_iterator __iter, _Pair&& __v)
523  {
524  size_type __old_size = _Base::bucket_count();
525  iterator __res = _Base::insert(__iter, std::forward<_Pair>(__v));
526  this->_M_profile_resize(__old_size);
527  return __res;
528  }
529 
530  template<typename _InputIter>
531  void
532  insert(_InputIter __first, _InputIter __last)
533  {
534  size_type __old_size = _Base::bucket_count();
535  _Base::insert(__first, __last);
536  this->_M_profile_resize(__old_size);
537  }
538 
539  void
540  swap(unordered_multimap& __x)
541  noexcept( noexcept(__x._M_base().swap(__x)) )
542  {
543  _Base::swap(__x._M_base());
544  this->_M_swap(__x);
545  }
546 
547  void
548  rehash(size_type __n)
549  {
550  size_type __old_size = _Base::bucket_count();
551  _Base::rehash(__n);
552  this->_M_profile_resize(__old_size);
553  }
554  };
555 
556  template<typename _Key, typename _Tp, typename _Hash,
557  typename _Pred, typename _Alloc>
558  inline void
559  swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
560  unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
561  noexcept(noexcept(__x.swap(__y)))
562  { __x.swap(__y); }
563 
564  template<typename _Key, typename _Tp, typename _Hash,
565  typename _Pred, typename _Alloc>
566  inline bool
567  operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
568  const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
569  { return static_cast<const _GLIBCXX_STD_BASE&>(__x) == __y; }
570 
571  template<typename _Key, typename _Tp, typename _Hash,
572  typename _Pred, typename _Alloc>
573  inline bool
574  operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
575  const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
576  { return !(__x == __y); }
577 
578 } // namespace __profile
579 } // namespace std
580 
581 #undef _GLIBCXX_BASE
582 #undef _GLIBCXX_STD_BASE
583 
584 #endif // C++11
585 
586 #endif