libstdc++
debug/unordered_set
Go to the documentation of this file.
1// Debugging unordered_set/unordered_multiset implementation -*- C++ -*-
2
3// Copyright (C) 2003-2023 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 and
21// a copy of the GCC Runtime Library Exception along with this program;
22// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
23// <http://www.gnu.org/licenses/>.
24
25/** @file debug/unordered_set
26 * This file is a GNU debug extension to the Standard C++ Library.
27 */
28
29#ifndef _GLIBCXX_DEBUG_UNORDERED_SET
30#define _GLIBCXX_DEBUG_UNORDERED_SET 1
31
32#pragma GCC system_header
33
34#if __cplusplus < 201103L
35# include <bits/c++0x_warning.h>
36#else
37# include <bits/c++config.h>
38namespace std _GLIBCXX_VISIBILITY(default) { namespace __debug {
39 template<typename _Key, typename _Hash, typename _Pred, typename _Allocator>
40 class unordered_set;
41 template<typename _Key, typename _Hash, typename _Pred, typename _Allocator>
42 class unordered_multiset;
43} } // namespace std::__debug
44# include <unordered_set>
45
46#include <debug/safe_unordered_container.h>
47#include <debug/safe_container.h>
48#include <debug/safe_iterator.h>
49#include <debug/safe_local_iterator.h>
50
51namespace std _GLIBCXX_VISIBILITY(default)
52{
53namespace __debug
54{
55 /// Class std::unordered_set with safety/checking/debug instrumentation.
56 template<typename _Value,
57 typename _Hash = std::hash<_Value>,
58 typename _Pred = std::equal_to<_Value>,
59 typename _Alloc = std::allocator<_Value> >
60 class unordered_set
61 : public __gnu_debug::_Safe_container<
62 unordered_set<_Value, _Hash, _Pred, _Alloc>, _Alloc,
63 __gnu_debug::_Safe_unordered_container>,
64 public _GLIBCXX_STD_C::unordered_set<_Value, _Hash, _Pred, _Alloc>
65 {
66 typedef _GLIBCXX_STD_C::unordered_set<
67 _Value, _Hash, _Pred, _Alloc> _Base;
68 typedef __gnu_debug::_Safe_container<
69 unordered_set, _Alloc, __gnu_debug::_Safe_unordered_container> _Safe;
70
71 typedef typename _Base::const_iterator _Base_const_iterator;
72 typedef typename _Base::iterator _Base_iterator;
73 typedef typename _Base::const_local_iterator _Base_const_local_iterator;
74 typedef typename _Base::local_iterator _Base_local_iterator;
75
76 template<typename _ItT, typename _SeqT, typename _CatT>
77 friend class ::__gnu_debug::_Safe_iterator;
78 template<typename _ItT, typename _SeqT>
79 friend class ::__gnu_debug::_Safe_local_iterator;
80
81 // Reference wrapper for base class. See PR libstdc++/90102.
82 struct _Base_ref
83 {
84 _Base_ref(const _Base& __r) : _M_ref(__r) { }
85
86 const _Base& _M_ref;
87 };
88
89 public:
90 typedef typename _Base::size_type size_type;
91 typedef typename _Base::difference_type difference_type;
92 typedef typename _Base::hasher hasher;
93 typedef typename _Base::key_equal key_equal;
94 typedef typename _Base::allocator_type allocator_type;
95
96 typedef typename _Base::key_type key_type;
97 typedef typename _Base::value_type value_type;
98
99 typedef typename _Base::pointer pointer;
100 typedef typename _Base::const_pointer const_pointer;
101 typedef typename _Base::reference reference;
102 typedef typename _Base::const_reference const_reference;
103 typedef __gnu_debug::_Safe_iterator<
104 _Base_iterator, unordered_set> iterator;
105 typedef __gnu_debug::_Safe_iterator<
106 _Base_const_iterator, unordered_set> const_iterator;
107 typedef __gnu_debug::_Safe_local_iterator<
108 _Base_local_iterator, unordered_set> local_iterator;
109 typedef __gnu_debug::_Safe_local_iterator<
110 _Base_const_local_iterator, unordered_set> const_local_iterator;
111
112 unordered_set() = default;
113
114 explicit
115 unordered_set(size_type __n,
116 const hasher& __hf = hasher(),
117 const key_equal& __eql = key_equal(),
118 const allocator_type& __a = allocator_type())
119 : _Base(__n, __hf, __eql, __a) { }
120
121 template<typename _InputIterator>
122 unordered_set(_InputIterator __first, _InputIterator __last,
123 size_type __n = 0,
124 const hasher& __hf = hasher(),
125 const key_equal& __eql = key_equal(),
126 const allocator_type& __a = allocator_type())
127 : _Base(__gnu_debug::__base(
128 __glibcxx_check_valid_constructor_range(__first, __last)),
129 __gnu_debug::__base(__last), __n,
130 __hf, __eql, __a) { }
131
132 unordered_set(const unordered_set&) = default;
133
134 unordered_set(_Base_ref __x)
135 : _Base(__x._M_ref) { }
136
137 unordered_set(unordered_set&&) = default;
138
139 explicit
140 unordered_set(const allocator_type& __a)
141 : _Base(__a) { }
142
143 unordered_set(const unordered_set& __uset,
144 const allocator_type& __a)
145 : _Base(__uset, __a) { }
146
147 unordered_set(unordered_set&& __uset,
148 const allocator_type& __a)
149 noexcept( noexcept(_Base(std::move(__uset), __a)) )
150 : _Safe(std::move(__uset), __a),
151 _Base(std::move(__uset), __a) { }
152
153 unordered_set(initializer_list<value_type> __l,
154 size_type __n = 0,
155 const hasher& __hf = hasher(),
156 const key_equal& __eql = key_equal(),
157 const allocator_type& __a = allocator_type())
158 : _Base(__l, __n, __hf, __eql, __a) { }
159
160 unordered_set(size_type __n, const allocator_type& __a)
161 : unordered_set(__n, hasher(), key_equal(), __a)
162 { }
163
164 unordered_set(size_type __n, const hasher& __hf,
165 const allocator_type& __a)
166 : unordered_set(__n, __hf, key_equal(), __a)
167 { }
168
169 template<typename _InputIterator>
170 unordered_set(_InputIterator __first, _InputIterator __last,
171 size_type __n,
172 const allocator_type& __a)
173 : unordered_set(__first, __last, __n, hasher(), key_equal(), __a)
174 { }
175
176 template<typename _InputIterator>
177 unordered_set(_InputIterator __first, _InputIterator __last,
178 size_type __n, const hasher& __hf,
179 const allocator_type& __a)
180 : unordered_set(__first, __last, __n, __hf, key_equal(), __a)
181 { }
182
183 unordered_set(initializer_list<value_type> __l,
184 size_type __n,
185 const allocator_type& __a)
186 : unordered_set(__l, __n, hasher(), key_equal(), __a)
187 { }
188
189 unordered_set(initializer_list<value_type> __l,
190 size_type __n, const hasher& __hf,
191 const allocator_type& __a)
192 : unordered_set(__l, __n, __hf, key_equal(), __a)
193 { }
194
195 ~unordered_set() = default;
196
197 unordered_set&
198 operator=(const unordered_set&) = default;
199
200 unordered_set&
201 operator=(unordered_set&&) = default;
202
203 unordered_set&
204 operator=(initializer_list<value_type> __l)
205 {
206 _Base::operator=(__l);
207 this->_M_invalidate_all();
208 return *this;
209 }
210
211 using _Base::get_allocator;
212 using _Base::empty;
213 using _Base::size;
214 using _Base::max_size;
215
216 void
217 swap(unordered_set& __x)
218 noexcept( noexcept(declval<_Base&>().swap(__x)) )
219 {
220 _Safe::_M_swap(__x);
221 _Base::swap(__x);
222 }
223
224 void
225 clear() noexcept
226 {
227 _Base::clear();
228 this->_M_invalidate_all();
229 }
230
231 iterator
232 begin() noexcept
233 { return { _Base::begin(), this }; }
234
235 const_iterator
236 begin() const noexcept
237 { return { _Base::begin(), this }; }
238
239 iterator
240 end() noexcept
241 { return { _Base::end(), this }; }
242
243 const_iterator
244 end() const noexcept
245 { return { _Base::end(), this }; }
246
247 const_iterator
248 cbegin() const noexcept
249 { return { _Base::cbegin(), this }; }
250
251 const_iterator
252 cend() const noexcept
253 { return { _Base::cend(), this }; }
254
255 // local versions
256 local_iterator
257 begin(size_type __b)
258 {
259 __glibcxx_check_bucket_index(__b);
260 return { _Base::begin(__b), this };
261 }
262
263 local_iterator
264 end(size_type __b)
265 {
266 __glibcxx_check_bucket_index(__b);
267 return { _Base::end(__b), this };
268 }
269
270 const_local_iterator
271 begin(size_type __b) const
272 {
273 __glibcxx_check_bucket_index(__b);
274 return { _Base::begin(__b), this };
275 }
276
277 const_local_iterator
278 end(size_type __b) const
279 {
280 __glibcxx_check_bucket_index(__b);
281 return { _Base::end(__b), this };
282 }
283
284 const_local_iterator
285 cbegin(size_type __b) const
286 {
287 __glibcxx_check_bucket_index(__b);
288 return { _Base::cbegin(__b), this };
289 }
290
291 const_local_iterator
292 cend(size_type __b) const
293 {
294 __glibcxx_check_bucket_index(__b);
295 return { _Base::cend(__b), this };
296 }
297
298 using _Base::bucket_count;
299 using _Base::max_bucket_count;
300
301 size_type
302 bucket_size(size_type __b) const
303 {
304 __glibcxx_check_bucket_index(__b);
305 return _Base::bucket_size(__b);
306 }
307
308 using _Base::bucket;
309 using _Base::load_factor;
310
311 float
312 max_load_factor() const noexcept
313 { return _Base::max_load_factor(); }
314
315 void
316 max_load_factor(float __f)
317 {
318 __glibcxx_check_max_load_factor(__f);
319 _Base::max_load_factor(__f);
320 }
321
322 using _Base::rehash;
323 using _Base::reserve;
324
325 template<typename... _Args>
326 std::pair<iterator, bool>
327 emplace(_Args&&... __args)
328 {
329 size_type __bucket_count = this->bucket_count();
330 auto __res = _Base::emplace(std::forward<_Args>(__args)...);
331 _M_check_rehashed(__bucket_count);
332 return { { __res.first, this }, __res.second };
333 }
334
335 template<typename... _Args>
336 iterator
337 emplace_hint(const_iterator __hint, _Args&&... __args)
338 {
339 __glibcxx_check_insert(__hint);
340 size_type __bucket_count = this->bucket_count();
341 auto __it = _Base::emplace_hint(__hint.base(),
342 std::forward<_Args>(__args)...);
343 _M_check_rehashed(__bucket_count);
344 return { __it, this };
345 }
346
347 std::pair<iterator, bool>
348 insert(const value_type& __obj)
349 {
350 size_type __bucket_count = this->bucket_count();
351 auto __res = _Base::insert(__obj);
352 _M_check_rehashed(__bucket_count);
353 return { { __res.first, this }, __res.second };
354 }
355
356 iterator
357 insert(const_iterator __hint, const value_type& __obj)
358 {
359 __glibcxx_check_insert(__hint);
360 size_type __bucket_count = this->bucket_count();
361 auto __it = _Base::insert(__hint.base(), __obj);
362 _M_check_rehashed(__bucket_count);
363 return { __it, this };
364 }
365
366 std::pair<iterator, bool>
367 insert(value_type&& __obj)
368 {
369 size_type __bucket_count = this->bucket_count();
370 auto __res = _Base::insert(std::move(__obj));
371 _M_check_rehashed(__bucket_count);
372 return { { __res.first, this }, __res.second };
373 }
374
375 iterator
376 insert(const_iterator __hint, value_type&& __obj)
377 {
378 __glibcxx_check_insert(__hint);
379 size_type __bucket_count = this->bucket_count();
380 auto __it = _Base::insert(__hint.base(), std::move(__obj));
381 _M_check_rehashed(__bucket_count);
382 return { __it, this };
383 }
384
385 void
386 insert(std::initializer_list<value_type> __l)
387 {
388 size_type __bucket_count = this->bucket_count();
389 _Base::insert(__l);
390 _M_check_rehashed(__bucket_count);
391 }
392
393 template<typename _InputIterator>
394 void
395 insert(_InputIterator __first, _InputIterator __last)
396 {
397 typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
398 __glibcxx_check_valid_range2(__first, __last, __dist);
399 size_type __bucket_count = this->bucket_count();
400
401 if (__dist.second >= __gnu_debug::__dp_sign)
402 _Base::insert(__gnu_debug::__unsafe(__first),
403 __gnu_debug::__unsafe(__last));
404 else
405 _Base::insert(__first, __last);
406
407 _M_check_rehashed(__bucket_count);
408 }
409
410#if __cplusplus > 201402L
411 using node_type = typename _Base::node_type;
412 using insert_return_type = _Node_insert_return<iterator, node_type>;
413
414 node_type
415 extract(const_iterator __position)
416 {
417 __glibcxx_check_erase(__position);
418 return _M_extract(__position.base());
419 }
420
421 node_type
422 extract(const key_type& __key)
423 {
424 const auto __position = _Base::find(__key);
425 if (__position != _Base::end())
426 return _M_extract(__position);
427 return {};
428 }
429
430 insert_return_type
431 insert(node_type&& __nh)
432 {
433 auto __ret = _Base::insert(std::move(__nh));
434 return
435 { { __ret.position, this }, __ret.inserted, std::move(__ret.node) };
436 }
437
438 iterator
439 insert(const_iterator __hint, node_type&& __nh)
440 {
441 __glibcxx_check_insert(__hint);
442 return { _Base::insert(__hint.base(), std::move(__nh)), this };
443 }
444
445 template<typename _H2, typename _P2>
446 void
447 merge(unordered_set<_Value, _H2, _P2, _Alloc>& __source)
448 {
449 auto __guard
450 = _Safe::_S_uc_guard(std::__detail::_Identity{}, __source);
451 _Base::merge(__source);
452 }
453
454 template<typename _H2, typename _P2>
455 void
456 merge(unordered_set<_Value, _H2, _P2, _Alloc>&& __source)
457 { merge(__source); }
458
459 template<typename _H2, typename _P2>
460 void
461 merge(unordered_multiset<_Value, _H2, _P2, _Alloc>& __source)
462 {
463 auto __guard
464 = _Safe::_S_umc_guard(std::__detail::_Identity{}, __source);
465 _Base::merge(__source);
466 }
467
468 template<typename _H2, typename _P2>
469 void
470 merge(unordered_multiset<_Value, _H2, _P2, _Alloc>&& __source)
471 { merge(__source); }
472#endif // C++17
473
474 using _Base::hash_function;
475 using _Base::key_eq;
476
477 iterator
478 find(const key_type& __key)
479 { return { _Base::find(__key), this }; }
480
481#if __cplusplus > 201703L
482 template<typename _Kt,
483 typename = std::__has_is_transparent_t<_Hash, _Kt>,
484 typename = std::__has_is_transparent_t<_Pred, _Kt>>
485 iterator
486 find(const _Kt& __k)
487 { return { _Base::find(__k), this }; }
488#endif
489
490 const_iterator
491 find(const key_type& __key) const
492 { return { _Base::find(__key), this }; }
493
494#if __cplusplus > 201703L
495 template<typename _Kt,
496 typename = std::__has_is_transparent_t<_Hash, _Kt>,
497 typename = std::__has_is_transparent_t<_Pred, _Kt>>
498 const_iterator
499 find(const _Kt& __k) const
500 { return { _Base::find(__k), this }; }
501#endif
502
503 using _Base::count;
504
505#if __cplusplus > 201703L
506 using _Base::contains;
507#endif
508
509 std::pair<iterator, iterator>
510 equal_range(const key_type& __key)
511 {
512 auto __res = _Base::equal_range(__key);
513 return { { __res.first, this }, { __res.second, this } };
514 }
515
516#if __cplusplus > 201703L
517 template<typename _Kt,
518 typename = std::__has_is_transparent_t<_Hash, _Kt>,
519 typename = std::__has_is_transparent_t<_Pred, _Kt>>
520 std::pair<iterator, iterator>
521 equal_range(const _Kt& __k)
522 {
523 auto __res = _Base::equal_range(__k);
524 return { { __res.first, this }, { __res.second, this } };
525 }
526#endif
527
528 std::pair<const_iterator, const_iterator>
529 equal_range(const key_type& __key) const
530 {
531 auto __res = _Base::equal_range(__key);
532 return { { __res.first, this }, { __res.second, this } };
533 }
534
535#if __cplusplus > 201703L
536 template<typename _Kt,
537 typename = std::__has_is_transparent_t<_Hash, _Kt>,
538 typename = std::__has_is_transparent_t<_Pred, _Kt>>
539 std::pair<const_iterator, const_iterator>
540 equal_range(const _Kt& __k) const
541 {
542 auto __res = _Base::equal_range(__k);
543 return { { __res.first, this }, { __res.second, this } };
544 }
545#endif
546
547 size_type
548 erase(const key_type& __key)
549 {
550 size_type __ret(0);
551 auto __victim = _Base::find(__key);
552 if (__victim != _Base::end())
553 {
554 _M_erase(__victim);
555 __ret = 1;
556 }
557 return __ret;
558 }
559
560 iterator
561 erase(const_iterator __it)
562 {
563 __glibcxx_check_erase(__it);
564 return { _M_erase(__it.base()), this };
565 }
566
567 _Base_iterator
568 erase(_Base_const_iterator __it)
569 {
570 __glibcxx_check_erase2(__it);
571 return _M_erase(__it);
572 }
573
574 iterator
575 erase(iterator __it)
576 {
577 __glibcxx_check_erase(__it);
578 return { _M_erase(__it.base()), this };
579 }
580
581 iterator
582 erase(const_iterator __first, const_iterator __last)
583 {
584 __glibcxx_check_erase_range(__first, __last);
585 for (auto __tmp = __first.base(); __tmp != __last.base(); ++__tmp)
586 {
587 _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::cend(),
588 _M_message(__gnu_debug::__msg_valid_range)
589 ._M_iterator(__first, "first")
590 ._M_iterator(__last, "last"));
591 _M_invalidate(__tmp);
592 }
593
594 size_type __bucket_count = this->bucket_count();
595 auto __next = _Base::erase(__first.base(), __last.base());
596 _M_check_rehashed(__bucket_count);
597 return { __next, this };
598 }
599
600 _Base&
601 _M_base() noexcept { return *this; }
602
603 const _Base&
604 _M_base() const noexcept { return *this; }
605
606 private:
607 void
608 _M_check_rehashed(size_type __prev_count)
609 {
610 if (__prev_count != this->bucket_count())
611 this->_M_invalidate_all();
612 }
613
614 void
615 _M_invalidate(_Base_const_iterator __victim)
616 {
617 this->_M_invalidate_if(
618 [__victim](_Base_const_iterator __it) { return __it == __victim; });
619 this->_M_invalidate_local_if(
620 [__victim](_Base_const_local_iterator __it)
621 { return __it == __victim; });
622 }
623
624 _Base_iterator
625 _M_erase(_Base_const_iterator __victim)
626 {
627 _M_invalidate(__victim);
628 size_type __bucket_count = this->bucket_count();
629 _Base_iterator __next = _Base::erase(__victim);
630 _M_check_rehashed(__bucket_count);
631 return __next;
632 }
633
634#if __cplusplus > 201402L
635 node_type
636 _M_extract(_Base_const_iterator __victim)
637 {
638 _M_invalidate(__victim);
639 return _Base::extract(__victim);
640 }
641#endif
642 };
643
644#if __cpp_deduction_guides >= 201606
645
646 template<typename _InputIterator,
647 typename _Hash =
648 hash<typename iterator_traits<_InputIterator>::value_type>,
649 typename _Pred =
650 equal_to<typename iterator_traits<_InputIterator>::value_type>,
651 typename _Allocator =
652 allocator<typename iterator_traits<_InputIterator>::value_type>,
653 typename = _RequireInputIter<_InputIterator>,
654 typename = _RequireNotAllocatorOrIntegral<_Hash>,
655 typename = _RequireNotAllocator<_Pred>,
656 typename = _RequireAllocator<_Allocator>>
657 unordered_set(_InputIterator, _InputIterator,
658 unordered_set<int>::size_type = {},
659 _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
660 -> unordered_set<typename iterator_traits<_InputIterator>::value_type,
661 _Hash, _Pred, _Allocator>;
662
663 template<typename _Tp, typename _Hash = hash<_Tp>,
664 typename _Pred = equal_to<_Tp>,
665 typename _Allocator = allocator<_Tp>,
666 typename = _RequireNotAllocatorOrIntegral<_Hash>,
667 typename = _RequireNotAllocator<_Pred>,
668 typename = _RequireAllocator<_Allocator>>
669 unordered_set(initializer_list<_Tp>,
670 unordered_set<int>::size_type = {},
671 _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
672 -> unordered_set<_Tp, _Hash, _Pred, _Allocator>;
673
674 template<typename _InputIterator, typename _Allocator,
675 typename = _RequireInputIter<_InputIterator>,
676 typename = _RequireAllocator<_Allocator>>
677 unordered_set(_InputIterator, _InputIterator,
678 unordered_set<int>::size_type, _Allocator)
679 -> unordered_set<typename iterator_traits<_InputIterator>::value_type,
680 hash<
681 typename iterator_traits<_InputIterator>::value_type>,
682 equal_to<
683 typename iterator_traits<_InputIterator>::value_type>,
684 _Allocator>;
685
686 template<typename _InputIterator, typename _Hash, typename _Allocator,
687 typename = _RequireInputIter<_InputIterator>,
688 typename = _RequireNotAllocatorOrIntegral<_Hash>,
689 typename = _RequireAllocator<_Allocator>>
690 unordered_set(_InputIterator, _InputIterator,
691 unordered_set<int>::size_type,
692 _Hash, _Allocator)
693 -> unordered_set<typename iterator_traits<_InputIterator>::value_type,
694 _Hash,
695 equal_to<
696 typename iterator_traits<_InputIterator>::value_type>,
697 _Allocator>;
698
699 template<typename _Tp, typename _Allocator,
700 typename = _RequireAllocator<_Allocator>>
701 unordered_set(initializer_list<_Tp>,
702 unordered_set<int>::size_type, _Allocator)
703 -> unordered_set<_Tp, hash<_Tp>, equal_to<_Tp>, _Allocator>;
704
705 template<typename _Tp, typename _Hash, typename _Allocator,
706 typename = _RequireNotAllocatorOrIntegral<_Hash>,
707 typename = _RequireAllocator<_Allocator>>
708 unordered_set(initializer_list<_Tp>,
709 unordered_set<int>::size_type, _Hash, _Allocator)
710 -> unordered_set<_Tp, _Hash, equal_to<_Tp>, _Allocator>;
711
712#endif
713
714 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
715 inline void
716 swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
717 unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
718 noexcept(noexcept(__x.swap(__y)))
719 { __x.swap(__y); }
720
721 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
722 inline bool
723 operator==(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
724 const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
725 { return __x._M_base() == __y._M_base(); }
726
727#if __cpp_impl_three_way_comparison < 201907L
728 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
729 inline bool
730 operator!=(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
731 const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
732 { return !(__x == __y); }
733#endif
734
735 /// Class std::unordered_multiset with safety/checking/debug instrumentation.
736 template<typename _Value,
737 typename _Hash = std::hash<_Value>,
738 typename _Pred = std::equal_to<_Value>,
739 typename _Alloc = std::allocator<_Value> >
740 class unordered_multiset
741 : public __gnu_debug::_Safe_container<
742 unordered_multiset<_Value, _Hash, _Pred, _Alloc>, _Alloc,
743 __gnu_debug::_Safe_unordered_container>,
744 public _GLIBCXX_STD_C::unordered_multiset<_Value, _Hash, _Pred, _Alloc>
745 {
746 typedef _GLIBCXX_STD_C::unordered_multiset<
747 _Value, _Hash, _Pred, _Alloc> _Base;
748 typedef __gnu_debug::_Safe_container<unordered_multiset,
749 _Alloc, __gnu_debug::_Safe_unordered_container> _Safe;
750 typedef typename _Base::const_iterator _Base_const_iterator;
751 typedef typename _Base::iterator _Base_iterator;
752 typedef typename _Base::const_local_iterator
753 _Base_const_local_iterator;
754 typedef typename _Base::local_iterator _Base_local_iterator;
755
756 template<typename _ItT, typename _SeqT, typename _CatT>
757 friend class ::__gnu_debug::_Safe_iterator;
758 template<typename _ItT, typename _SeqT>
759 friend class ::__gnu_debug::_Safe_local_iterator;
760
761 // Reference wrapper for base class. See PR libstdc++/90102.
762 struct _Base_ref
763 {
764 _Base_ref(const _Base& __r) : _M_ref(__r) { }
765
766 const _Base& _M_ref;
767 };
768
769 public:
770 typedef typename _Base::size_type size_type;
771 typedef typename _Base::difference_type difference_type;
772 typedef typename _Base::hasher hasher;
773 typedef typename _Base::key_equal key_equal;
774 typedef typename _Base::allocator_type allocator_type;
775
776 typedef typename _Base::key_type key_type;
777 typedef typename _Base::value_type value_type;
778
779 typedef typename _Base::pointer pointer;
780 typedef typename _Base::const_pointer const_pointer;
781 typedef typename _Base::reference reference;
782 typedef typename _Base::const_reference const_reference;
783 typedef __gnu_debug::_Safe_iterator<
784 _Base_iterator, unordered_multiset> iterator;
785 typedef __gnu_debug::_Safe_iterator<
786 _Base_const_iterator, unordered_multiset> const_iterator;
787 typedef __gnu_debug::_Safe_local_iterator<
788 _Base_local_iterator, unordered_multiset> local_iterator;
789 typedef __gnu_debug::_Safe_local_iterator<
790 _Base_const_local_iterator, unordered_multiset> const_local_iterator;
791
792 unordered_multiset() = default;
793
794 explicit
795 unordered_multiset(size_type __n,
796 const hasher& __hf = hasher(),
797 const key_equal& __eql = key_equal(),
798 const allocator_type& __a = allocator_type())
799 : _Base(__n, __hf, __eql, __a) { }
800
801 template<typename _InputIterator>
802 unordered_multiset(_InputIterator __first, _InputIterator __last,
803 size_type __n = 0,
804 const hasher& __hf = hasher(),
805 const key_equal& __eql = key_equal(),
806 const allocator_type& __a = allocator_type())
807 : _Base(__gnu_debug::__base(
808 __glibcxx_check_valid_constructor_range(__first, __last)),
809 __gnu_debug::__base(__last), __n,
810 __hf, __eql, __a) { }
811
812 unordered_multiset(const unordered_multiset&) = default;
813
814 unordered_multiset(_Base_ref __x)
815 : _Base(__x._M_ref) { }
816
817 unordered_multiset(unordered_multiset&&) = default;
818
819 explicit
820 unordered_multiset(const allocator_type& __a)
821 : _Base(__a) { }
822
823 unordered_multiset(const unordered_multiset& __uset,
824 const allocator_type& __a)
825 : _Base(__uset, __a) { }
826
827 unordered_multiset(unordered_multiset&& __uset,
828 const allocator_type& __a)
829 noexcept( noexcept(_Base(std::move(__uset), __a)) )
830 : _Safe(std::move(__uset), __a),
831 _Base(std::move(__uset), __a) { }
832
833 unordered_multiset(initializer_list<value_type> __l,
834 size_type __n = 0,
835 const hasher& __hf = hasher(),
836 const key_equal& __eql = key_equal(),
837 const allocator_type& __a = allocator_type())
838 : _Base(__l, __n, __hf, __eql, __a) { }
839
840 unordered_multiset(size_type __n, const allocator_type& __a)
841 : unordered_multiset(__n, hasher(), key_equal(), __a)
842 { }
843
844 unordered_multiset(size_type __n, const hasher& __hf,
845 const allocator_type& __a)
846 : unordered_multiset(__n, __hf, key_equal(), __a)
847 { }
848
849 template<typename _InputIterator>
850 unordered_multiset(_InputIterator __first, _InputIterator __last,
851 size_type __n,
852 const allocator_type& __a)
853 : unordered_multiset(__first, __last, __n, hasher(), key_equal(), __a)
854 { }
855
856 template<typename _InputIterator>
857 unordered_multiset(_InputIterator __first, _InputIterator __last,
858 size_type __n, const hasher& __hf,
859 const allocator_type& __a)
860 : unordered_multiset(__first, __last, __n, __hf, key_equal(), __a)
861 { }
862
863 unordered_multiset(initializer_list<value_type> __l,
864 size_type __n,
865 const allocator_type& __a)
866 : unordered_multiset(__l, __n, hasher(), key_equal(), __a)
867 { }
868
869 unordered_multiset(initializer_list<value_type> __l,
870 size_type __n, const hasher& __hf,
871 const allocator_type& __a)
872 : unordered_multiset(__l, __n, __hf, key_equal(), __a)
873 { }
874
875 ~unordered_multiset() = default;
876
877 unordered_multiset&
878 operator=(const unordered_multiset&) = default;
879
880 unordered_multiset&
881 operator=(unordered_multiset&&) = default;
882
883 unordered_multiset&
884 operator=(initializer_list<value_type> __l)
885 {
886 _Base::operator=(__l);
887 this->_M_invalidate_all();
888 return *this;
889 }
890
891 using _Base::get_allocator;
892 using _Base::empty;
893 using _Base::size;
894 using _Base::max_size;
895
896 void
897 swap(unordered_multiset& __x)
898 noexcept( noexcept(declval<_Base&>().swap(__x)) )
899 {
900 _Safe::_M_swap(__x);
901 _Base::swap(__x);
902 }
903
904 void
905 clear() noexcept
906 {
907 _Base::clear();
908 this->_M_invalidate_all();
909 }
910
911 iterator
912 begin() noexcept
913 { return { _Base::begin(), this }; }
914
915 const_iterator
916 begin() const noexcept
917 { return { _Base::begin(), this }; }
918
919 iterator
920 end() noexcept
921 { return { _Base::end(), this }; }
922
923 const_iterator
924 end() const noexcept
925 { return { _Base::end(), this }; }
926
927 const_iterator
928 cbegin() const noexcept
929 { return { _Base::cbegin(), this }; }
930
931 const_iterator
932 cend() const noexcept
933 { return { _Base::cend(), this }; }
934
935 // local versions
936 local_iterator
937 begin(size_type __b)
938 {
939 __glibcxx_check_bucket_index(__b);
940 return { _Base::begin(__b), this };
941 }
942
943 local_iterator
944 end(size_type __b)
945 {
946 __glibcxx_check_bucket_index(__b);
947 return { _Base::end(__b), this };
948 }
949
950 const_local_iterator
951 begin(size_type __b) const
952 {
953 __glibcxx_check_bucket_index(__b);
954 return { _Base::begin(__b), this };
955 }
956
957 const_local_iterator
958 end(size_type __b) const
959 {
960 __glibcxx_check_bucket_index(__b);
961 return { _Base::end(__b), this };
962 }
963
964 const_local_iterator
965 cbegin(size_type __b) const
966 {
967 __glibcxx_check_bucket_index(__b);
968 return { _Base::cbegin(__b), this };
969 }
970
971 const_local_iterator
972 cend(size_type __b) const
973 {
974 __glibcxx_check_bucket_index(__b);
975 return { _Base::cend(__b), this };
976 }
977
978 using _Base::bucket_count;
979 using _Base::max_bucket_count;
980
981 size_type
982 bucket_size(size_type __b) const
983 {
984 __glibcxx_check_bucket_index(__b);
985 return _Base::bucket_size(__b);
986 }
987
988 using _Base::bucket;
989 using _Base::load_factor;
990
991 float
992 max_load_factor() const noexcept
993 { return _Base::max_load_factor(); }
994
995 void
996 max_load_factor(float __f)
997 {
998 __glibcxx_check_max_load_factor(__f);
999 _Base::max_load_factor(__f);
1000 }
1001
1002 using _Base::rehash;
1003 using _Base::reserve;
1004
1005 template<typename... _Args>
1006 iterator
1007 emplace(_Args&&... __args)
1008 {
1009 size_type __bucket_count = this->bucket_count();
1010 auto __it = _Base::emplace(std::forward<_Args>(__args)...);
1011 _M_check_rehashed(__bucket_count);
1012 return { __it, this };
1013 }
1014
1015 template<typename... _Args>
1016 iterator
1017 emplace_hint(const_iterator __hint, _Args&&... __args)
1018 {
1019 __glibcxx_check_insert(__hint);
1020 size_type __bucket_count = this->bucket_count();
1021 auto __it = _Base::emplace_hint(__hint.base(),
1022 std::forward<_Args>(__args)...);
1023 _M_check_rehashed(__bucket_count);
1024 return { __it, this };
1025 }
1026
1027 iterator
1028 insert(const value_type& __obj)
1029 {
1030 size_type __bucket_count = this->bucket_count();
1031 auto __it = _Base::insert(__obj);
1032 _M_check_rehashed(__bucket_count);
1033 return { __it, this };
1034 }
1035
1036 iterator
1037 insert(const_iterator __hint, const value_type& __obj)
1038 {
1039 __glibcxx_check_insert(__hint);
1040 size_type __bucket_count = this->bucket_count();
1041 auto __it = _Base::insert(__hint.base(), __obj);
1042 _M_check_rehashed(__bucket_count);
1043 return { __it, this };
1044 }
1045
1046 iterator
1047 insert(value_type&& __obj)
1048 {
1049 size_type __bucket_count = this->bucket_count();
1050 auto __it = _Base::insert(std::move(__obj));
1051 _M_check_rehashed(__bucket_count);
1052 return { __it, this };
1053 }
1054
1055 iterator
1056 insert(const_iterator __hint, value_type&& __obj)
1057 {
1058 __glibcxx_check_insert(__hint);
1059 size_type __bucket_count = this->bucket_count();
1060 auto __it = _Base::insert(__hint.base(), std::move(__obj));
1061 _M_check_rehashed(__bucket_count);
1062 return { __it, this };
1063 }
1064
1065 void
1066 insert(std::initializer_list<value_type> __l)
1067 {
1068 size_type __bucket_count = this->bucket_count();
1069 _Base::insert(__l);
1070 _M_check_rehashed(__bucket_count);
1071 }
1072
1073 template<typename _InputIterator>
1074 void
1075 insert(_InputIterator __first, _InputIterator __last)
1076 {
1077 typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
1078 __glibcxx_check_valid_range2(__first, __last, __dist);
1079 size_type __bucket_count = this->bucket_count();
1080
1081 if (__dist.second >= __gnu_debug::__dp_sign)
1082 _Base::insert(__gnu_debug::__unsafe(__first),
1083 __gnu_debug::__unsafe(__last));
1084 else
1085 _Base::insert(__first, __last);
1086
1087 _M_check_rehashed(__bucket_count);
1088 }
1089
1090#if __cplusplus > 201402L
1091 using node_type = typename _Base::node_type;
1092
1093 node_type
1094 extract(const_iterator __position)
1095 {
1096 __glibcxx_check_erase(__position);
1097 return _M_extract(__position.base());
1098 }
1099
1100 node_type
1101 extract(const key_type& __key)
1102 {
1103 const auto __position = _Base::find(__key);
1104 if (__position != _Base::end())
1105 return _M_extract(__position);
1106 return {};
1107 }
1108
1109 iterator
1110 insert(node_type&& __nh)
1111 { return { _Base::insert(std::move(__nh)), this }; }
1112
1113 iterator
1114 insert(const_iterator __hint, node_type&& __nh)
1115 {
1116 __glibcxx_check_insert(__hint);
1117 return { _Base::insert(__hint.base(), std::move(__nh)), this };
1118 }
1119
1120 template<typename _H2, typename _P2>
1121 void
1122 merge(unordered_multiset<_Value, _H2, _P2, _Alloc>& __source)
1123 {
1124 auto __guard
1125 = _Safe::_S_umc_guard(std::__detail::_Identity{}, __source);
1126 _Base::merge(__source);
1127 }
1128
1129 template<typename _H2, typename _P2>
1130 void
1131 merge(unordered_multiset<_Value, _H2, _P2, _Alloc>&& __source)
1132 { merge(__source); }
1133
1134 template<typename _H2, typename _P2>
1135 void
1136 merge(unordered_set<_Value, _H2, _P2, _Alloc>& __source)
1137 {
1138 auto __guard
1139 = _Safe::_S_uc_guard(std::__detail::_Identity{}, __source);
1140 _Base::merge(__source);
1141 }
1142
1143 template<typename _H2, typename _P2>
1144 void
1145 merge(unordered_set<_Value, _H2, _P2, _Alloc>&& __source)
1146 { merge(__source); }
1147#endif // C++17
1148
1149 using _Base::hash_function;
1150 using _Base::key_eq;
1151
1152 iterator
1153 find(const key_type& __key)
1154 { return { _Base::find(__key), this }; }
1155
1156#if __cplusplus > 201703L
1157 template<typename _Kt,
1158 typename = std::__has_is_transparent_t<_Hash, _Kt>,
1159 typename = std::__has_is_transparent_t<_Pred, _Kt>>
1160 iterator
1161 find(const _Kt& __k)
1162 { return { _Base::find(__k), this }; }
1163#endif
1164
1165 const_iterator
1166 find(const key_type& __key) const
1167 { return { _Base::find(__key), this }; }
1168
1169#if __cplusplus > 201703L
1170 template<typename _Kt,
1171 typename = std::__has_is_transparent_t<_Hash, _Kt>,
1172 typename = std::__has_is_transparent_t<_Pred, _Kt>>
1173 const_iterator
1174 find(const _Kt& __k) const
1175 { return { _Base::find(__k), this }; }
1176#endif
1177
1178 using _Base::count;
1179
1180#if __cplusplus > 201703L
1181 using _Base::contains;
1182#endif
1183
1184 std::pair<iterator, iterator>
1185 equal_range(const key_type& __key)
1186 {
1187 auto __res = _Base::equal_range(__key);
1188 return { { __res.first, this }, { __res.second, this } };
1189 }
1190
1191#if __cplusplus > 201703L
1192 template<typename _Kt,
1193 typename = std::__has_is_transparent_t<_Hash, _Kt>,
1194 typename = std::__has_is_transparent_t<_Pred, _Kt>>
1195 std::pair<iterator, iterator>
1196 equal_range(const _Kt& __k)
1197 {
1198 auto __res = _Base::equal_range(__k);
1199 return { { __res.first, this }, { __res.second, this } };
1200 }
1201#endif
1202
1203 std::pair<const_iterator, const_iterator>
1204 equal_range(const key_type& __key) const
1205 {
1206 auto __res = _Base::equal_range(__key);
1207 return { { __res.first, this }, { __res.second, this } };
1208 }
1209
1210#if __cplusplus > 201703L
1211 template<typename _Kt,
1212 typename = std::__has_is_transparent_t<_Hash, _Kt>,
1213 typename = std::__has_is_transparent_t<_Pred, _Kt>>
1214 std::pair<const_iterator, const_iterator>
1215 equal_range(const _Kt& __k) const
1216 {
1217 auto __res = _Base::equal_range(__k);
1218 return { { __res.first, this }, { __res.second, this } };
1219 }
1220#endif
1221
1222 size_type
1223 erase(const key_type& __key)
1224 {
1225 size_type __ret(0);
1226 auto __pair = _Base::equal_range(__key);
1227 for (auto __victim = __pair.first; __victim != __pair.second;)
1228 {
1229 _M_invalidate(__victim);
1230 __victim = _Base::erase(__victim);
1231 ++__ret;
1232 }
1233
1234 return __ret;
1235 }
1236
1237 iterator
1238 erase(const_iterator __it)
1239 {
1240 __glibcxx_check_erase(__it);
1241 return { _M_erase(__it.base()), this };
1242 }
1243
1244 _Base_iterator
1245 erase(_Base_const_iterator __it)
1246 {
1247 __glibcxx_check_erase2(__it);
1248 return _M_erase(__it);
1249 }
1250
1251 iterator
1252 erase(iterator __it)
1253 {
1254 __glibcxx_check_erase(__it);
1255 return { _M_erase(__it.base()), this };
1256 }
1257
1258 iterator
1259 erase(const_iterator __first, const_iterator __last)
1260 {
1261 __glibcxx_check_erase_range(__first, __last);
1262 for (auto __tmp = __first.base(); __tmp != __last.base(); ++__tmp)
1263 {
1264 _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::cend(),
1265 _M_message(__gnu_debug::__msg_valid_range)
1266 ._M_iterator(__first, "first")
1267 ._M_iterator(__last, "last"));
1268 _M_invalidate(__tmp);
1269 }
1270 return { _Base::erase(__first.base(), __last.base()), this };
1271 }
1272
1273 _Base&
1274 _M_base() noexcept { return *this; }
1275
1276 const _Base&
1277 _M_base() const noexcept { return *this; }
1278
1279 private:
1280 void
1281 _M_check_rehashed(size_type __prev_count)
1282 {
1283 if (__prev_count != this->bucket_count())
1284 this->_M_invalidate_all();
1285 }
1286
1287 void
1288 _M_invalidate(_Base_const_iterator __victim)
1289 {
1290 this->_M_invalidate_if(
1291 [__victim](_Base_const_iterator __it) { return __it == __victim; });
1292 this->_M_invalidate_local_if(
1293 [__victim](_Base_const_local_iterator __it)
1294 { return __it == __victim; });
1295 }
1296
1297 _Base_iterator
1298 _M_erase(_Base_const_iterator __victim)
1299 {
1300 _M_invalidate(__victim);
1301 size_type __bucket_count = this->bucket_count();
1302 _Base_iterator __next = _Base::erase(__victim);
1303 _M_check_rehashed(__bucket_count);
1304 return __next;
1305 }
1306
1307#if __cplusplus > 201402L
1308 node_type
1309 _M_extract(_Base_const_iterator __victim)
1310 {
1311 _M_invalidate(__victim);
1312 return _Base::extract(__victim);
1313 }
1314#endif
1315 };
1316
1317#if __cpp_deduction_guides >= 201606
1318
1319 template<typename _InputIterator,
1320 typename _Hash =
1321 hash<typename iterator_traits<_InputIterator>::value_type>,
1322 typename _Pred =
1323 equal_to<typename iterator_traits<_InputIterator>::value_type>,
1324 typename _Allocator =
1325 allocator<typename iterator_traits<_InputIterator>::value_type>,
1326 typename = _RequireInputIter<_InputIterator>,
1327 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1328 typename = _RequireNotAllocator<_Pred>,
1329 typename = _RequireAllocator<_Allocator>>
1330 unordered_multiset(_InputIterator, _InputIterator,
1331 unordered_multiset<int>::size_type = {},
1332 _Hash = _Hash(), _Pred = _Pred(),
1333 _Allocator = _Allocator())
1334 -> unordered_multiset<typename iterator_traits<_InputIterator>::value_type,
1335 _Hash, _Pred, _Allocator>;
1336
1337 template<typename _Tp, typename _Hash = hash<_Tp>,
1338 typename _Pred = equal_to<_Tp>,
1339 typename _Allocator = allocator<_Tp>,
1340 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1341 typename = _RequireNotAllocator<_Pred>,
1342 typename = _RequireAllocator<_Allocator>>
1343 unordered_multiset(initializer_list<_Tp>,
1344 unordered_multiset<int>::size_type = {},
1345 _Hash = _Hash(), _Pred = _Pred(),
1346 _Allocator = _Allocator())
1347 -> unordered_multiset<_Tp, _Hash, _Pred, _Allocator>;
1348
1349 template<typename _InputIterator, typename _Allocator,
1350 typename = _RequireInputIter<_InputIterator>,
1351 typename = _RequireAllocator<_Allocator>>
1352 unordered_multiset(_InputIterator, _InputIterator,
1353 unordered_multiset<int>::size_type, _Allocator)
1354 -> unordered_multiset<typename iterator_traits<_InputIterator>::value_type,
1355 hash<typename
1356 iterator_traits<_InputIterator>::value_type>,
1357 equal_to<typename
1358 iterator_traits<_InputIterator>::value_type>,
1359 _Allocator>;
1360
1361 template<typename _InputIterator, typename _Hash, typename _Allocator,
1362 typename = _RequireInputIter<_InputIterator>,
1363 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1364 typename = _RequireAllocator<_Allocator>>
1365 unordered_multiset(_InputIterator, _InputIterator,
1366 unordered_multiset<int>::size_type,
1367 _Hash, _Allocator)
1368 -> unordered_multiset<typename
1369 iterator_traits<_InputIterator>::value_type,
1370 _Hash,
1371 equal_to<
1372 typename
1373 iterator_traits<_InputIterator>::value_type>,
1374 _Allocator>;
1375
1376 template<typename _Tp, typename _Allocator,
1377 typename = _RequireAllocator<_Allocator>>
1378 unordered_multiset(initializer_list<_Tp>,
1379 unordered_multiset<int>::size_type, _Allocator)
1380 -> unordered_multiset<_Tp, hash<_Tp>, equal_to<_Tp>, _Allocator>;
1381
1382 template<typename _Tp, typename _Hash, typename _Allocator,
1383 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1384 typename = _RequireAllocator<_Allocator>>
1385 unordered_multiset(initializer_list<_Tp>,
1386 unordered_multiset<int>::size_type, _Hash, _Allocator)
1387 -> unordered_multiset<_Tp, _Hash, equal_to<_Tp>, _Allocator>;
1388
1389#endif
1390
1391 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
1392 inline void
1393 swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1394 unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1395 noexcept(noexcept(__x.swap(__y)))
1396 { __x.swap(__y); }
1397
1398 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
1399 inline bool
1400 operator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1401 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1402 { return __x._M_base() == __y._M_base(); }
1403
1404#if __cpp_impl_three_way_comparison < 201907L
1405 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
1406 inline bool
1407 operator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1408 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1409 { return !(__x == __y); }
1410#endif
1411
1412} // namespace __debug
1413} // namespace std
1414
1415#endif // C++11
1416
1417#endif
__glibcxx_check_insert
#define __glibcxx_check_insert(_Position)
Definition macros.h:146
__glibcxx_check_erase_range
#define __glibcxx_check_erase_range(_First, _Last)
Definition macros.h:248
__glibcxx_check_erase
#define __glibcxx_check_erase(_Position)
Definition macros.h:212
std::declval
auto declval() noexcept -> decltype(__declval< _Tp >(0))
Definition type_traits:2384
std::move
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
Definition move.h:97
std::forward
constexpr _Tp && forward(typename std::remove_reference< _Tp >::type &__t) noexcept
Forward an lvalue.
Definition move.h:70
std
ISO C++ entities toplevel namespace is std.
__gnu_debug::__base
constexpr _Iterator __base(_Iterator __it)
Definition helper_functions.h:321
std::__debug
GNU debug code, replaces standard behavior with debug behavior.
std::initializer_list
initializer_list
Definition initializer_list:46
std::hash
Primary class template hash.
Definition functional_hash.h:103
std::allocator
The standard allocator, as per C++03 [20.4.1].
Definition allocator.h:131
__gnu_debug::_Safe_iterator
Safe iterator wrapper.
Definition safe_iterator.h:117
__gnu_debug::_Safe_iterator::base
_Iterator & base() noexcept
Return the underlying iterator.
Definition safe_iterator.h:360
std::iterator_traits
Traits class for iterators.
Definition stl_iterator_base_types.h:178
std::_Node_insert_return
Return type of insert(node_handle&&) on unique maps/sets.
Definition node_handle.h:395
std::equal_to
One of the comparison functors.
Definition stl_function.h:374
std::pair
Struct holding two objects of arbitrary type.
Definition stl_pair.h:189
std::unordered_multiset
A standard container composed of equivalent keys (possibly containing multiple of each key value) in ...
Definition unordered_set.h:973
std::unordered_multiset::size_type
_Hashtable::size_type size_type
Iterator-related typedefs.
Definition unordered_set.h:998
std::unordered_set
A standard container composed of unique keys (containing at most one of each key value) in which the ...
Definition unordered_set.h:105
std::unordered_set::size_type
_Hashtable::size_type size_type
Iterator-related typedefs.
Definition unordered_set.h:130
__gnu_debug::_Safe_container
Safe class dealing with some allocator dependent operations.
Definition safe_container.h:43
__gnu_debug::_Safe_unordered_container
Base class for constructing a safe unordered container type that tracks iterators that reference it.
Definition safe_unordered_container.h:59
std::__debug::unordered_set
Class std::unordered_set with safety/checking/debug instrumentation.
Definition debug/unordered_set:65
std::__debug::unordered_multiset
Class std::unordered_multiset with safety/checking/debug instrumentation.
Definition debug/unordered_set:745