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
42namespace std _GLIBCXX_VISIBILITY(default)
43{
44namespace __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