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