]> git.ipfire.org Git - thirdparty/gcc.git/blame - libstdc++-v3/include/debug/unordered_set
ada: Fix alignment violation for chain of aligned and misaligned composite types
[thirdparty/gcc.git] / libstdc++-v3 / include / debug / unordered_set
CommitLineData
e63637ea
BK
1// Debugging unordered_set/unordered_multiset implementation -*- C++ -*-
2
6441eb6d 3// Copyright (C) 2003-2025 Free Software Foundation, Inc.
e63637ea
BK
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
748086b7 8// Free Software Foundation; either version 3, or (at your option)
e63637ea
BK
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
748086b7
JJ
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/>.
e63637ea
BK
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
63a598de 32#ifdef _GLIBCXX_SYSHDR
541a9b10 33#pragma GCC system_header
63a598de 34#endif
541a9b10 35
734f5023 36#if __cplusplus < 201103L
ab65a4c7 37# include <bits/c++0x_warning.h>
c878d6ba 38#else
9ca2ac69
JW
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
c878d6ba 46# include <unordered_set>
e63637ea 47
364c862b 48#include <debug/safe_unordered_container.h>
15ee1a77 49#include <debug/safe_container.h>
e63637ea 50#include <debug/safe_iterator.h>
77e0bf4e 51#include <debug/safe_local_iterator.h>
e63637ea 52
12ffa228 53namespace std _GLIBCXX_VISIBILITY(default)
e63637ea
BK
54{
55namespace __debug
56{
1ceb9e06 57 /// Class std::unordered_set with safety/checking/debug instrumentation.
e63637ea 58 template<typename _Value,
ced3cb9f 59 typename _Hash = std::hash<_Value>,
e63637ea 60 typename _Pred = std::equal_to<_Value>,
ced3cb9f 61 typename _Alloc = std::allocator<_Value> >
e63637ea 62 class unordered_set
15ee1a77
FD
63 : public __gnu_debug::_Safe_container<
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>
e63637ea 67 {
15ee1a77
FD
68 typedef _GLIBCXX_STD_C::unordered_set<
69 _Value, _Hash, _Pred, _Alloc> _Base;
70 typedef __gnu_debug::_Safe_container<
71 unordered_set, _Alloc, __gnu_debug::_Safe_unordered_container> _Safe;
72
73 typedef typename _Base::const_iterator _Base_const_iterator;
74 typedef typename _Base::iterator _Base_iterator;
77e0bf4e 75 typedef typename _Base::const_local_iterator _Base_const_local_iterator;
15ee1a77 76 typedef typename _Base::local_iterator _Base_local_iterator;
e63637ea 77
e9afbed0
FD
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
eca833b8
JW
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
e63637ea 91 public:
15ee1a77 92 typedef typename _Base::size_type size_type;
f4b4ce15 93 typedef typename _Base::difference_type difference_type;
15ee1a77
FD
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
f4b4ce15
FD
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;
15ee1a77
FD
105 typedef __gnu_debug::_Safe_iterator<
106 _Base_iterator, unordered_set> iterator;
107 typedef __gnu_debug::_Safe_iterator<
108 _Base_const_iterator, unordered_set> const_iterator;
109 typedef __gnu_debug::_Safe_local_iterator<
110 _Base_local_iterator, unordered_set> local_iterator;
111 typedef __gnu_debug::_Safe_local_iterator<
112 _Base_const_local_iterator, unordered_set> const_local_iterator;
e63637ea 113
da27f556
FD
114 unordered_set() = default;
115
e63637ea 116 explicit
da27f556 117 unordered_set(size_type __n,
e63637ea
BK
118 const hasher& __hf = hasher(),
119 const key_equal& __eql = key_equal(),
120 const allocator_type& __a = allocator_type())
ced3cb9f 121 : _Base(__n, __hf, __eql, __a) { }
e63637ea
BK
122
123 template<typename _InputIterator>
15ee1a77 124 unordered_set(_InputIterator __first, _InputIterator __last,
417e896e 125 size_type __n = 0,
15ee1a77
FD
126 const hasher& __hf = hasher(),
127 const key_equal& __eql = key_equal(),
e63637ea 128 const allocator_type& __a = allocator_type())
90aabc7e
FD
129 : _Base(__gnu_debug::__base(
130 __glibcxx_check_valid_constructor_range(__first, __last)),
1f5ca1a1 131 __gnu_debug::__base(__last), __n,
4c2d93db 132 __hf, __eql, __a) { }
ced3cb9f 133
0462b6aa 134 unordered_set(const unordered_set&) = default;
ced3cb9f 135
eca833b8
JW
136 unordered_set(_Base_ref __x)
137 : _Base(__x._M_ref) { }
0462b6aa
FD
138
139 unordered_set(unordered_set&&) = default;
140
141 explicit
142 unordered_set(const allocator_type& __a)
15ee1a77 143 : _Base(__a) { }
0462b6aa
FD
144
145 unordered_set(const unordered_set& __uset,
146 const allocator_type& __a)
15ee1a77 147 : _Base(__uset, __a) { }
ced3cb9f 148
0462b6aa
FD
149 unordered_set(unordered_set&& __uset,
150 const allocator_type& __a)
e9a53a4f
FD
151 noexcept( noexcept(_Base(std::move(__uset), __a)) )
152 : _Safe(std::move(__uset), __a),
153 _Base(std::move(__uset), __a) { }
e63637ea 154
988499f4 155 unordered_set(initializer_list<value_type> __l,
417e896e 156 size_type __n = 0,
988499f4
JM
157 const hasher& __hf = hasher(),
158 const key_equal& __eql = key_equal(),
159 const allocator_type& __a = allocator_type())
4c2d93db 160 : _Base(__l, __n, __hf, __eql, __a) { }
e63637ea 161
e55b80f5 162 unordered_set(size_type __n, const allocator_type& __a)
12324b9a 163 : unordered_set(__n, hasher(), key_equal(), __a)
e55b80f5
FD
164 { }
165
166 unordered_set(size_type __n, const hasher& __hf,
167 const allocator_type& __a)
12324b9a 168 : unordered_set(__n, __hf, key_equal(), __a)
e55b80f5
FD
169 { }
170
1ecd95ea
TK
171 template<typename _InputIterator>
172 unordered_set(_InputIterator __first, _InputIterator __last,
173 const allocator_type& __a)
174 : unordered_set(__first, __last, 0, hasher(), key_equal(), __a)
175 { }
176
e55b80f5
FD
177 template<typename _InputIterator>
178 unordered_set(_InputIterator __first, _InputIterator __last,
179 size_type __n,
180 const allocator_type& __a)
12324b9a 181 : unordered_set(__first, __last, __n, hasher(), key_equal(), __a)
e55b80f5
FD
182 { }
183
184 template<typename _InputIterator>
185 unordered_set(_InputIterator __first, _InputIterator __last,
186 size_type __n, const hasher& __hf,
187 const allocator_type& __a)
12324b9a 188 : unordered_set(__first, __last, __n, __hf, key_equal(), __a)
e55b80f5
FD
189 { }
190
1ecd95ea
TK
191 unordered_set(initializer_list<value_type> __l,
192 const allocator_type& __a)
193 : unordered_set(__l, 0, hasher(), key_equal(), __a)
194 { }
195
e55b80f5
FD
196 unordered_set(initializer_list<value_type> __l,
197 size_type __n,
198 const allocator_type& __a)
12324b9a 199 : unordered_set(__l, __n, hasher(), key_equal(), __a)
e55b80f5
FD
200 { }
201
202 unordered_set(initializer_list<value_type> __l,
203 size_type __n, const hasher& __hf,
204 const allocator_type& __a)
12324b9a 205 : unordered_set(__l, __n, __hf, key_equal(), __a)
e55b80f5
FD
206 { }
207
ae54d8cb 208#if __glibcxx_containers_ranges // C++ >= 23
7cc40201
TK
209 template<__detail::__container_compatible_range<value_type> _Rg>
210 unordered_set(from_range_t, _Rg&& __rg,
211 size_type __n = 0,
212 const hasher& __hf = hasher(),
213 const key_equal& __eql = key_equal(),
214 const allocator_type& __a = allocator_type())
215 : _Base(from_range, std::forward<_Rg>(__rg), __n, __hf, __eql, __a)
216 { }
217
218 template<__detail::__container_compatible_range<value_type> _Rg>
219 unordered_set(from_range_t, _Rg&& __rg, const allocator_type& __a)
220 : _Base(from_range, std::forward<_Rg>(__rg), __a)
221 { }
222
223 template<__detail::__container_compatible_range<value_type> _Rg>
224 unordered_set(from_range_t, _Rg&& __rg, size_type __n,
225 const allocator_type& __a)
226 : _Base(from_range, std::forward<_Rg>(__rg), __n, __a)
227 { }
228
229 template<__detail::__container_compatible_range<value_type> _Rg>
230 unordered_set(from_range_t, _Rg&& __rg, size_type __n,
231 const hasher& __hf, const allocator_type& __a)
232 : _Base(from_range, std::forward<_Rg>(__rg), __n, __hf, __a)
233 { }
234#endif
235
15ee1a77 236 ~unordered_set() = default;
6f59ea25 237
ced3cb9f 238 unordered_set&
15ee1a77 239 operator=(const unordered_set&) = default;
69b3331e
PC
240
241 unordered_set&
15ee1a77 242 operator=(unordered_set&&) = default;
69b3331e 243
988499f4
JM
244 unordered_set&
245 operator=(initializer_list<value_type> __l)
246 {
e9a53a4f 247 _Base::operator=(__l);
0462b6aa 248 this->_M_invalidate_all();
988499f4
JM
249 return *this;
250 }
251
f4b4ce15
FD
252 using _Base::get_allocator;
253 using _Base::empty;
254 using _Base::size;
255 using _Base::max_size;
256
e63637ea 257 void
ff74fd13 258 swap(unordered_set& __x)
c5d9ec56 259 noexcept( noexcept(declval<_Base&>().swap(__x)) )
e63637ea 260 {
15ee1a77 261 _Safe::_M_swap(__x);
ced3cb9f 262 _Base::swap(__x);
e63637ea 263 }
69b3331e
PC
264
265 void
d3677132 266 clear() noexcept
69b3331e
PC
267 {
268 _Base::clear();
269 this->_M_invalidate_all();
270 }
271
15ee1a77 272 iterator
d3677132 273 begin() noexcept
4b763dee 274 { return { _Base::begin(), this }; }
ced3cb9f
PC
275
276 const_iterator
d3677132 277 begin() const noexcept
4b763dee 278 { return { _Base::begin(), this }; }
ced3cb9f
PC
279
280 iterator
d3677132 281 end() noexcept
4b763dee 282 { return { _Base::end(), this }; }
ced3cb9f
PC
283
284 const_iterator
d3677132 285 end() const noexcept
4b763dee 286 { return { _Base::end(), this }; }
ced3cb9f
PC
287
288 const_iterator
d3677132 289 cbegin() const noexcept
4b763dee 290 { return { _Base::cbegin(), this }; }
ced3cb9f
PC
291
292 const_iterator
d3677132 293 cend() const noexcept
4b763dee 294 { return { _Base::cend(), this }; }
ced3cb9f
PC
295
296 // local versions
77e0bf4e
FD
297 local_iterator
298 begin(size_type __b)
7181e991
FD
299 {
300 __glibcxx_check_bucket_index(__b);
4b763dee 301 return { _Base::begin(__b), this };
7181e991 302 }
77e0bf4e
FD
303
304 local_iterator
305 end(size_type __b)
7181e991
FD
306 {
307 __glibcxx_check_bucket_index(__b);
4b763dee 308 return { _Base::end(__b), this };
7181e991 309 }
77e0bf4e
FD
310
311 const_local_iterator
312 begin(size_type __b) const
7181e991
FD
313 {
314 __glibcxx_check_bucket_index(__b);
4b763dee 315 return { _Base::begin(__b), this };
7181e991 316 }
77e0bf4e
FD
317
318 const_local_iterator
319 end(size_type __b) const
7181e991
FD
320 {
321 __glibcxx_check_bucket_index(__b);
4b763dee 322 return { _Base::end(__b), this };
7181e991 323 }
77e0bf4e
FD
324
325 const_local_iterator
326 cbegin(size_type __b) const
7181e991
FD
327 {
328 __glibcxx_check_bucket_index(__b);
4b763dee 329 return { _Base::cbegin(__b), this };
7181e991 330 }
77e0bf4e
FD
331
332 const_local_iterator
333 cend(size_type __b) const
7181e991
FD
334 {
335 __glibcxx_check_bucket_index(__b);
4b763dee 336 return { _Base::cend(__b), this };
7181e991
FD
337 }
338
f4b4ce15
FD
339 using _Base::bucket_count;
340 using _Base::max_bucket_count;
341
7181e991
FD
342 size_type
343 bucket_size(size_type __b) const
344 {
345 __glibcxx_check_bucket_index(__b);
346 return _Base::bucket_size(__b);
347 }
ced3cb9f 348
f4b4ce15
FD
349 using _Base::bucket;
350 using _Base::load_factor;
351
14cbb5d8
FD
352 float
353 max_load_factor() const noexcept
354 { return _Base::max_load_factor(); }
355
356 void
357 max_load_factor(float __f)
358 {
359 __glibcxx_check_max_load_factor(__f);
360 _Base::max_load_factor(__f);
361 }
362
f4b4ce15
FD
363 using _Base::rehash;
364 using _Base::reserve;
365
9b81593b
FD
366 template<typename... _Args>
367 std::pair<iterator, bool>
368 emplace(_Args&&... __args)
369 {
370 size_type __bucket_count = this->bucket_count();
4b763dee 371 auto __res = _Base::emplace(std::forward<_Args>(__args)...);
9b81593b 372 _M_check_rehashed(__bucket_count);
4b763dee 373 return { { __res.first, this }, __res.second };
9b81593b
FD
374 }
375
376 template<typename... _Args>
377 iterator
378 emplace_hint(const_iterator __hint, _Args&&... __args)
379 {
380 __glibcxx_check_insert(__hint);
381 size_type __bucket_count = this->bucket_count();
4b763dee
FD
382 auto __it = _Base::emplace_hint(__hint.base(),
383 std::forward<_Args>(__args)...);
9b81593b 384 _M_check_rehashed(__bucket_count);
4b763dee 385 return { __it, this };
9b81593b
FD
386 }
387
ced3cb9f
PC
388 std::pair<iterator, bool>
389 insert(const value_type& __obj)
390 {
77e0bf4e 391 size_type __bucket_count = this->bucket_count();
4b763dee 392 auto __res = _Base::insert(__obj);
77e0bf4e 393 _M_check_rehashed(__bucket_count);
4b763dee 394 return { { __res.first, this }, __res.second };
ced3cb9f
PC
395 }
396
397 iterator
d66411ba 398 insert(const_iterator __hint, const value_type& __obj)
ced3cb9f 399 {
d66411ba 400 __glibcxx_check_insert(__hint);
77e0bf4e 401 size_type __bucket_count = this->bucket_count();
4b763dee 402 auto __it = _Base::insert(__hint.base(), __obj);
77e0bf4e 403 _M_check_rehashed(__bucket_count);
4b763dee 404 return { __it, this };
ced3cb9f
PC
405 }
406
fb7342fd
PC
407 std::pair<iterator, bool>
408 insert(value_type&& __obj)
409 {
77e0bf4e 410 size_type __bucket_count = this->bucket_count();
4b763dee 411 auto __res = _Base::insert(std::move(__obj));
77e0bf4e 412 _M_check_rehashed(__bucket_count);
4b763dee 413 return { { __res.first, this }, __res.second };
fb7342fd
PC
414 }
415
416 iterator
d66411ba 417 insert(const_iterator __hint, value_type&& __obj)
fb7342fd 418 {
d66411ba 419 __glibcxx_check_insert(__hint);
77e0bf4e 420 size_type __bucket_count = this->bucket_count();
4b763dee 421 auto __it = _Base::insert(__hint.base(), std::move(__obj));
77e0bf4e 422 _M_check_rehashed(__bucket_count);
4b763dee 423 return { __it, this };
fb7342fd
PC
424 }
425
ced3cb9f
PC
426 void
427 insert(std::initializer_list<value_type> __l)
77e0bf4e
FD
428 {
429 size_type __bucket_count = this->bucket_count();
430 _Base::insert(__l);
431 _M_check_rehashed(__bucket_count);
432 }
ced3cb9f
PC
433
434 template<typename _InputIterator>
77e0bf4e
FD
435 void
436 insert(_InputIterator __first, _InputIterator __last)
437 {
24167c42
FD
438 typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
439 __glibcxx_check_valid_range2(__first, __last, __dist);
77e0bf4e 440 size_type __bucket_count = this->bucket_count();
24167c42
FD
441
442 if (__dist.second >= __gnu_debug::__dp_sign)
443 _Base::insert(__gnu_debug::__unsafe(__first),
444 __gnu_debug::__unsafe(__last));
445 else
446 _Base::insert(__first, __last);
447
77e0bf4e 448 _M_check_rehashed(__bucket_count);
ced3cb9f
PC
449 }
450
2dbe56bd
JW
451#if __cplusplus > 201402L
452 using node_type = typename _Base::node_type;
adaefe2a 453 using insert_return_type = _Node_insert_return<iterator, node_type>;
2dbe56bd
JW
454
455 node_type
456 extract(const_iterator __position)
457 {
458 __glibcxx_check_erase(__position);
4b763dee 459 return _M_extract(__position.base());
2dbe56bd
JW
460 }
461
462 node_type
463 extract(const key_type& __key)
464 {
4b763dee
FD
465 const auto __position = _Base::find(__key);
466 if (__position != _Base::end())
467 return _M_extract(__position);
2dbe56bd
JW
468 return {};
469 }
470
471 insert_return_type
472 insert(node_type&& __nh)
473 {
474 auto __ret = _Base::insert(std::move(__nh));
4b763dee
FD
475 return
476 { { __ret.position, this }, __ret.inserted, std::move(__ret.node) };
2dbe56bd
JW
477 }
478
479 iterator
480 insert(const_iterator __hint, node_type&& __nh)
481 {
482 __glibcxx_check_insert(__hint);
4b763dee 483 return { _Base::insert(__hint.base(), std::move(__nh)), this };
2dbe56bd
JW
484 }
485
f4b4ce15
FD
486 template<typename _H2, typename _P2>
487 void
488 merge(unordered_set<_Value, _H2, _P2, _Alloc>& __source)
489 {
490 auto __guard
491 = _Safe::_S_uc_guard(std::__detail::_Identity{}, __source);
e9a53a4f 492 _Base::merge(__source);
f4b4ce15
FD
493 }
494
495 template<typename _H2, typename _P2>
496 void
497 merge(unordered_set<_Value, _H2, _P2, _Alloc>&& __source)
498 { merge(__source); }
499
500 template<typename _H2, typename _P2>
501 void
502 merge(unordered_multiset<_Value, _H2, _P2, _Alloc>& __source)
503 {
504 auto __guard
505 = _Safe::_S_umc_guard(std::__detail::_Identity{}, __source);
e9a53a4f 506 _Base::merge(__source);
f4b4ce15
FD
507 }
508
509 template<typename _H2, typename _P2>
510 void
511 merge(unordered_multiset<_Value, _H2, _P2, _Alloc>&& __source)
512 { merge(__source); }
2dbe56bd
JW
513#endif // C++17
514
f4b4ce15
FD
515 using _Base::hash_function;
516 using _Base::key_eq;
517
ced3cb9f
PC
518 iterator
519 find(const key_type& __key)
4b763dee 520 { return { _Base::find(__key), this }; }
ced3cb9f 521
d2b1a684
FD
522#if __cplusplus > 201703L
523 template<typename _Kt,
524 typename = std::__has_is_transparent_t<_Hash, _Kt>,
525 typename = std::__has_is_transparent_t<_Pred, _Kt>>
526 iterator
527 find(const _Kt& __k)
528 { return { _Base::find(__k), this }; }
529#endif
530
ced3cb9f
PC
531 const_iterator
532 find(const key_type& __key) const
4b763dee 533 { return { _Base::find(__key), this }; }
ced3cb9f 534
d2b1a684
FD
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 const_iterator
540 find(const _Kt& __k) const
541 { return { _Base::find(__k), this }; }
542#endif
543
f4b4ce15
FD
544 using _Base::count;
545
546#if __cplusplus > 201703L
547 using _Base::contains;
548#endif
549
ced3cb9f
PC
550 std::pair<iterator, iterator>
551 equal_range(const key_type& __key)
552 {
4b763dee
FD
553 auto __res = _Base::equal_range(__key);
554 return { { __res.first, this }, { __res.second, this } };
ced3cb9f
PC
555 }
556
d2b1a684
FD
557#if __cplusplus > 201703L
558 template<typename _Kt,
559 typename = std::__has_is_transparent_t<_Hash, _Kt>,
560 typename = std::__has_is_transparent_t<_Pred, _Kt>>
561 std::pair<iterator, iterator>
562 equal_range(const _Kt& __k)
563 {
564 auto __res = _Base::equal_range(__k);
565 return { { __res.first, this }, { __res.second, this } };
566 }
567#endif
568
ced3cb9f
PC
569 std::pair<const_iterator, const_iterator>
570 equal_range(const key_type& __key) const
571 {
4b763dee
FD
572 auto __res = _Base::equal_range(__key);
573 return { { __res.first, this }, { __res.second, this } };
ced3cb9f
PC
574 }
575
d2b1a684
FD
576#if __cplusplus > 201703L
577 template<typename _Kt,
578 typename = std::__has_is_transparent_t<_Hash, _Kt>,
579 typename = std::__has_is_transparent_t<_Pred, _Kt>>
580 std::pair<const_iterator, const_iterator>
581 equal_range(const _Kt& __k) const
582 {
583 auto __res = _Base::equal_range(__k);
584 return { { __res.first, this }, { __res.second, this } };
585 }
586#endif
587
ced3cb9f
PC
588 size_type
589 erase(const key_type& __key)
590 {
591 size_type __ret(0);
4b763dee 592 auto __victim = _Base::find(__key);
afe96d41 593 if (__victim != _Base::end())
ced3cb9f 594 {
4b763dee 595 _M_erase(__victim);
ced3cb9f
PC
596 __ret = 1;
597 }
598 return __ret;
599 }
600
d723ced2 601 iterator
ced3cb9f
PC
602 erase(const_iterator __it)
603 {
604 __glibcxx_check_erase(__it);
4b763dee 605 return { _M_erase(__it.base()), this };
ced3cb9f
PC
606 }
607
5f40d34b
FD
608 _Base_iterator
609 erase(_Base_const_iterator __it)
610 {
611 __glibcxx_check_erase2(__it);
612 return _M_erase(__it);
613 }
614
6dc88283
PC
615 iterator
616 erase(iterator __it)
4b763dee
FD
617 {
618 __glibcxx_check_erase(__it);
619 return { _M_erase(__it.base()), this };
620 }
6dc88283 621
d723ced2 622 iterator
ced3cb9f
PC
623 erase(const_iterator __first, const_iterator __last)
624 {
625 __glibcxx_check_erase_range(__first, __last);
4b763dee 626 for (auto __tmp = __first.base(); __tmp != __last.base(); ++__tmp)
afe96d41 627 {
4b763dee 628 _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::cend(),
afe96d41
FD
629 _M_message(__gnu_debug::__msg_valid_range)
630 ._M_iterator(__first, "first")
631 ._M_iterator(__last, "last"));
4b763dee 632 _M_invalidate(__tmp);
afe96d41 633 }
4b763dee 634
77e0bf4e 635 size_type __bucket_count = this->bucket_count();
4b763dee 636 auto __next = _Base::erase(__first.base(), __last.base());
77e0bf4e 637 _M_check_rehashed(__bucket_count);
4b763dee 638 return { __next, this };
ced3cb9f
PC
639 }
640
641 _Base&
15ee1a77 642 _M_base() noexcept { return *this; }
ced3cb9f
PC
643
644 const _Base&
d3677132 645 _M_base() const noexcept { return *this; }
ced3cb9f 646
69b3331e 647 private:
77e0bf4e
FD
648 void
649 _M_check_rehashed(size_type __prev_count)
650 {
651 if (__prev_count != this->bucket_count())
20a4550c 652 this->_M_invalidate_all();
69b3331e 653 }
4b763dee
FD
654
655 void
656 _M_invalidate(_Base_const_iterator __victim)
657 {
658 this->_M_invalidate_if(
659 [__victim](_Base_const_iterator __it) { return __it == __victim; });
660 this->_M_invalidate_local_if(
661 [__victim](_Base_const_local_iterator __it)
acc1d1a9 662 { return __it == __victim; });
4b763dee
FD
663 }
664
665 _Base_iterator
666 _M_erase(_Base_const_iterator __victim)
667 {
668 _M_invalidate(__victim);
669 size_type __bucket_count = this->bucket_count();
670 _Base_iterator __next = _Base::erase(__victim);
671 _M_check_rehashed(__bucket_count);
672 return __next;
673 }
674
675#if __cplusplus > 201402L
676 node_type
677 _M_extract(_Base_const_iterator __victim)
678 {
679 _M_invalidate(__victim);
680 return _Base::extract(__victim);
681 }
682#endif
e63637ea
BK
683 };
684
957f5fea
VV
685#if __cpp_deduction_guides >= 201606
686
687 template<typename _InputIterator,
688 typename _Hash =
c0cb38c2 689 hash<typename iterator_traits<_InputIterator>::value_type>,
957f5fea 690 typename _Pred =
c0cb38c2 691 equal_to<typename iterator_traits<_InputIterator>::value_type>,
957f5fea 692 typename _Allocator =
c0cb38c2 693 allocator<typename iterator_traits<_InputIterator>::value_type>,
957f5fea 694 typename = _RequireInputIter<_InputIterator>,
c0cb38c2
FD
695 typename = _RequireNotAllocatorOrIntegral<_Hash>,
696 typename = _RequireNotAllocator<_Pred>,
957f5fea
VV
697 typename = _RequireAllocator<_Allocator>>
698 unordered_set(_InputIterator, _InputIterator,
699 unordered_set<int>::size_type = {},
700 _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
701 -> unordered_set<typename iterator_traits<_InputIterator>::value_type,
702 _Hash, _Pred, _Allocator>;
703
704 template<typename _Tp, typename _Hash = hash<_Tp>,
705 typename _Pred = equal_to<_Tp>,
706 typename _Allocator = allocator<_Tp>,
c0cb38c2
FD
707 typename = _RequireNotAllocatorOrIntegral<_Hash>,
708 typename = _RequireNotAllocator<_Pred>,
957f5fea
VV
709 typename = _RequireAllocator<_Allocator>>
710 unordered_set(initializer_list<_Tp>,
711 unordered_set<int>::size_type = {},
712 _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
713 -> unordered_set<_Tp, _Hash, _Pred, _Allocator>;
714
715 template<typename _InputIterator, typename _Allocator,
716 typename = _RequireInputIter<_InputIterator>,
717 typename = _RequireAllocator<_Allocator>>
718 unordered_set(_InputIterator, _InputIterator,
719 unordered_set<int>::size_type, _Allocator)
720 -> unordered_set<typename iterator_traits<_InputIterator>::value_type,
721 hash<
722 typename iterator_traits<_InputIterator>::value_type>,
723 equal_to<
724 typename iterator_traits<_InputIterator>::value_type>,
725 _Allocator>;
726
1ecd95ea
TK
727 template<typename _InputIterator, typename _Allocator,
728 typename = _RequireInputIter<_InputIterator>,
729 typename = _RequireAllocator<_Allocator>>
730 unordered_set(_InputIterator, _InputIterator, _Allocator)
731 -> unordered_set<typename iterator_traits<_InputIterator>::value_type,
732 hash<
733 typename iterator_traits<_InputIterator>::value_type>,
734 equal_to<
735 typename iterator_traits<_InputIterator>::value_type>,
736 _Allocator>;
737
957f5fea
VV
738 template<typename _InputIterator, typename _Hash, typename _Allocator,
739 typename = _RequireInputIter<_InputIterator>,
c0cb38c2 740 typename = _RequireNotAllocatorOrIntegral<_Hash>,
957f5fea
VV
741 typename = _RequireAllocator<_Allocator>>
742 unordered_set(_InputIterator, _InputIterator,
743 unordered_set<int>::size_type,
744 _Hash, _Allocator)
745 -> unordered_set<typename iterator_traits<_InputIterator>::value_type,
746 _Hash,
747 equal_to<
748 typename iterator_traits<_InputIterator>::value_type>,
749 _Allocator>;
750
751 template<typename _Tp, typename _Allocator,
752 typename = _RequireAllocator<_Allocator>>
753 unordered_set(initializer_list<_Tp>,
754 unordered_set<int>::size_type, _Allocator)
755 -> unordered_set<_Tp, hash<_Tp>, equal_to<_Tp>, _Allocator>;
756
1ecd95ea
TK
757 template<typename _Tp, typename _Allocator,
758 typename = _RequireAllocator<_Allocator>>
759 unordered_set(initializer_list<_Tp>, _Allocator)
760 -> unordered_set<_Tp, hash<_Tp>, equal_to<_Tp>, _Allocator>;
761
957f5fea 762 template<typename _Tp, typename _Hash, typename _Allocator,
c0cb38c2 763 typename = _RequireNotAllocatorOrIntegral<_Hash>,
957f5fea
VV
764 typename = _RequireAllocator<_Allocator>>
765 unordered_set(initializer_list<_Tp>,
766 unordered_set<int>::size_type, _Hash, _Allocator)
767 -> unordered_set<_Tp, _Hash, equal_to<_Tp>, _Allocator>;
768
769#endif
770
e63637ea 771 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
69b3331e
PC
772 inline void
773 swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
774 unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
c5d9ec56 775 noexcept(noexcept(__x.swap(__y)))
69b3331e 776 { __x.swap(__y); }
e63637ea 777
5dc22714
PC
778 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
779 inline bool
780 operator==(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
781 const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
637fd8b3 782 { return __x._M_base() == __y._M_base(); }
5dc22714 783
7ab9c243 784#if __cpp_impl_three_way_comparison < 201907L
5dc22714
PC
785 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
786 inline bool
787 operator!=(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
788 const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
789 { return !(__x == __y); }
7ab9c243 790#endif
e63637ea 791
1ceb9e06 792 /// Class std::unordered_multiset with safety/checking/debug instrumentation.
e63637ea 793 template<typename _Value,
ced3cb9f 794 typename _Hash = std::hash<_Value>,
e63637ea 795 typename _Pred = std::equal_to<_Value>,
ced3cb9f 796 typename _Alloc = std::allocator<_Value> >
e63637ea 797 class unordered_multiset
15ee1a77
FD
798 : public __gnu_debug::_Safe_container<
799 unordered_multiset<_Value, _Hash, _Pred, _Alloc>, _Alloc,
800 __gnu_debug::_Safe_unordered_container>,
801 public _GLIBCXX_STD_C::unordered_multiset<_Value, _Hash, _Pred, _Alloc>
e63637ea 802 {
15ee1a77
FD
803 typedef _GLIBCXX_STD_C::unordered_multiset<
804 _Value, _Hash, _Pred, _Alloc> _Base;
805 typedef __gnu_debug::_Safe_container<unordered_multiset,
806 _Alloc, __gnu_debug::_Safe_unordered_container> _Safe;
807 typedef typename _Base::const_iterator _Base_const_iterator;
808 typedef typename _Base::iterator _Base_iterator;
809 typedef typename _Base::const_local_iterator
810 _Base_const_local_iterator;
811 typedef typename _Base::local_iterator _Base_local_iterator;
0462b6aa 812
e9afbed0
FD
813 template<typename _ItT, typename _SeqT, typename _CatT>
814 friend class ::__gnu_debug::_Safe_iterator;
815 template<typename _ItT, typename _SeqT>
816 friend class ::__gnu_debug::_Safe_local_iterator;
817
eca833b8
JW
818 // Reference wrapper for base class. See PR libstdc++/90102.
819 struct _Base_ref
820 {
821 _Base_ref(const _Base& __r) : _M_ref(__r) { }
822
823 const _Base& _M_ref;
824 };
825
e63637ea 826 public:
15ee1a77 827 typedef typename _Base::size_type size_type;
f4b4ce15 828 typedef typename _Base::difference_type difference_type;
15ee1a77
FD
829 typedef typename _Base::hasher hasher;
830 typedef typename _Base::key_equal key_equal;
831 typedef typename _Base::allocator_type allocator_type;
832
833 typedef typename _Base::key_type key_type;
834 typedef typename _Base::value_type value_type;
835
f4b4ce15
FD
836 typedef typename _Base::pointer pointer;
837 typedef typename _Base::const_pointer const_pointer;
838 typedef typename _Base::reference reference;
839 typedef typename _Base::const_reference const_reference;
15ee1a77
FD
840 typedef __gnu_debug::_Safe_iterator<
841 _Base_iterator, unordered_multiset> iterator;
842 typedef __gnu_debug::_Safe_iterator<
843 _Base_const_iterator, unordered_multiset> const_iterator;
77e0bf4e 844 typedef __gnu_debug::_Safe_local_iterator<
15ee1a77 845 _Base_local_iterator, unordered_multiset> local_iterator;
77e0bf4e 846 typedef __gnu_debug::_Safe_local_iterator<
e9afbed0 847 _Base_const_local_iterator, unordered_multiset> const_local_iterator;
e63637ea 848
da27f556
FD
849 unordered_multiset() = default;
850
e63637ea 851 explicit
da27f556 852 unordered_multiset(size_type __n,
ced3cb9f
PC
853 const hasher& __hf = hasher(),
854 const key_equal& __eql = key_equal(),
855 const allocator_type& __a = allocator_type())
856 : _Base(__n, __hf, __eql, __a) { }
e63637ea
BK
857
858 template<typename _InputIterator>
15ee1a77 859 unordered_multiset(_InputIterator __first, _InputIterator __last,
417e896e 860 size_type __n = 0,
15ee1a77
FD
861 const hasher& __hf = hasher(),
862 const key_equal& __eql = key_equal(),
ced3cb9f 863 const allocator_type& __a = allocator_type())
90aabc7e
FD
864 : _Base(__gnu_debug::__base(
865 __glibcxx_check_valid_constructor_range(__first, __last)),
1f5ca1a1 866 __gnu_debug::__base(__last), __n,
4c2d93db 867 __hf, __eql, __a) { }
ced3cb9f 868
0462b6aa 869 unordered_multiset(const unordered_multiset&) = default;
ced3cb9f 870
eca833b8
JW
871 unordered_multiset(_Base_ref __x)
872 : _Base(__x._M_ref) { }
ced3cb9f 873
0462b6aa
FD
874 unordered_multiset(unordered_multiset&&) = default;
875
876 explicit
877 unordered_multiset(const allocator_type& __a)
15ee1a77 878 : _Base(__a) { }
0462b6aa
FD
879
880 unordered_multiset(const unordered_multiset& __uset,
881 const allocator_type& __a)
15ee1a77
FD
882 : _Base(__uset, __a) { }
883
0462b6aa
FD
884 unordered_multiset(unordered_multiset&& __uset,
885 const allocator_type& __a)
e9a53a4f
FD
886 noexcept( noexcept(_Base(std::move(__uset), __a)) )
887 : _Safe(std::move(__uset), __a),
888 _Base(std::move(__uset), __a) { }
e63637ea 889
988499f4 890 unordered_multiset(initializer_list<value_type> __l,
417e896e 891 size_type __n = 0,
988499f4
JM
892 const hasher& __hf = hasher(),
893 const key_equal& __eql = key_equal(),
894 const allocator_type& __a = allocator_type())
4c2d93db 895 : _Base(__l, __n, __hf, __eql, __a) { }
e63637ea 896
e55b80f5 897 unordered_multiset(size_type __n, const allocator_type& __a)
12324b9a 898 : unordered_multiset(__n, hasher(), key_equal(), __a)
e55b80f5
FD
899 { }
900
901 unordered_multiset(size_type __n, const hasher& __hf,
902 const allocator_type& __a)
12324b9a 903 : unordered_multiset(__n, __hf, key_equal(), __a)
e55b80f5
FD
904 { }
905
1ecd95ea
TK
906 template<typename _InputIterator>
907 unordered_multiset(_InputIterator __first, _InputIterator __last,
908 const allocator_type& __a)
909 : unordered_multiset(__first, __last, 0, hasher(), key_equal(), __a)
910 { }
911
e55b80f5
FD
912 template<typename _InputIterator>
913 unordered_multiset(_InputIterator __first, _InputIterator __last,
914 size_type __n,
915 const allocator_type& __a)
12324b9a 916 : unordered_multiset(__first, __last, __n, hasher(), key_equal(), __a)
e55b80f5
FD
917 { }
918
919 template<typename _InputIterator>
920 unordered_multiset(_InputIterator __first, _InputIterator __last,
921 size_type __n, const hasher& __hf,
922 const allocator_type& __a)
12324b9a 923 : unordered_multiset(__first, __last, __n, __hf, key_equal(), __a)
e55b80f5
FD
924 { }
925
1ecd95ea
TK
926 unordered_multiset(initializer_list<value_type> __l,
927 const allocator_type& __a)
928 : unordered_multiset(__l, 0, hasher(), key_equal(), __a)
929 { }
930
e55b80f5
FD
931 unordered_multiset(initializer_list<value_type> __l,
932 size_type __n,
933 const allocator_type& __a)
12324b9a 934 : unordered_multiset(__l, __n, hasher(), key_equal(), __a)
e55b80f5
FD
935 { }
936
937 unordered_multiset(initializer_list<value_type> __l,
938 size_type __n, const hasher& __hf,
939 const allocator_type& __a)
12324b9a 940 : unordered_multiset(__l, __n, __hf, key_equal(), __a)
e55b80f5
FD
941 { }
942
ae54d8cb 943#if __glibcxx_containers_ranges // C++ >= 23
7cc40201
TK
944 template<__detail::__container_compatible_range<value_type> _Rg>
945 unordered_multiset(from_range_t, _Rg&& __rg,
946 size_type __n = 0,
947 const hasher& __hf = hasher(),
948 const key_equal& __eql = key_equal(),
949 const allocator_type& __a = allocator_type())
950 : _Base(from_range, std::forward<_Rg>(__rg), __n, __hf, __eql, __a)
951 { }
952
953 template<__detail::__container_compatible_range<value_type> _Rg>
954 unordered_multiset(from_range_t, _Rg&& __rg, const allocator_type& __a)
955 : _Base(from_range, std::forward<_Rg>(__rg), __a)
956 { }
957
958 template<__detail::__container_compatible_range<value_type> _Rg>
959 unordered_multiset(from_range_t, _Rg&& __rg, size_type __n,
960 const allocator_type& __a)
961 : _Base(from_range, std::forward<_Rg>(__rg), __n, __a)
962 { }
963
964 template<__detail::__container_compatible_range<value_type> _Rg>
965 unordered_multiset(from_range_t, _Rg&& __rg, size_type __n,
966 const hasher& __hf, const allocator_type& __a)
967 : _Base(from_range, std::forward<_Rg>(__rg), __n, __hf, __a)
968 { }
969#endif
970
15ee1a77 971 ~unordered_multiset() = default;
6f59ea25 972
ced3cb9f 973 unordered_multiset&
15ee1a77 974 operator=(const unordered_multiset&) = default;
69b3331e
PC
975
976 unordered_multiset&
15ee1a77 977 operator=(unordered_multiset&&) = default;
69b3331e 978
988499f4
JM
979 unordered_multiset&
980 operator=(initializer_list<value_type> __l)
981 {
e9a53a4f 982 _Base::operator=(__l);
0462b6aa 983 this->_M_invalidate_all();
988499f4
JM
984 return *this;
985 }
986
f4b4ce15
FD
987 using _Base::get_allocator;
988 using _Base::empty;
989 using _Base::size;
990 using _Base::max_size;
991
e63637ea 992 void
ff74fd13 993 swap(unordered_multiset& __x)
c5d9ec56 994 noexcept( noexcept(declval<_Base&>().swap(__x)) )
e63637ea 995 {
15ee1a77 996 _Safe::_M_swap(__x);
ced3cb9f 997 _Base::swap(__x);
e63637ea 998 }
69b3331e 999
ced3cb9f 1000 void
d3677132 1001 clear() noexcept
69b3331e
PC
1002 {
1003 _Base::clear();
1004 this->_M_invalidate_all();
1005 }
1006
ced3cb9f 1007 iterator
d3677132 1008 begin() noexcept
4b763dee 1009 { return { _Base::begin(), this }; }
ced3cb9f
PC
1010
1011 const_iterator
d3677132 1012 begin() const noexcept
4b763dee 1013 { return { _Base::begin(), this }; }
ced3cb9f
PC
1014
1015 iterator
d3677132 1016 end() noexcept
4b763dee 1017 { return { _Base::end(), this }; }
ced3cb9f
PC
1018
1019 const_iterator
d3677132 1020 end() const noexcept
4b763dee 1021 { return { _Base::end(), this }; }
ced3cb9f
PC
1022
1023 const_iterator
d3677132 1024 cbegin() const noexcept
4b763dee 1025 { return { _Base::cbegin(), this }; }
ced3cb9f
PC
1026
1027 const_iterator
d3677132 1028 cend() const noexcept
4b763dee 1029 { return { _Base::cend(), this }; }
ced3cb9f
PC
1030
1031 // local versions
77e0bf4e
FD
1032 local_iterator
1033 begin(size_type __b)
7181e991
FD
1034 {
1035 __glibcxx_check_bucket_index(__b);
4b763dee 1036 return { _Base::begin(__b), this };
7181e991 1037 }
77e0bf4e
FD
1038
1039 local_iterator
1040 end(size_type __b)
7181e991
FD
1041 {
1042 __glibcxx_check_bucket_index(__b);
4b763dee 1043 return { _Base::end(__b), this };
7181e991 1044 }
77e0bf4e
FD
1045
1046 const_local_iterator
1047 begin(size_type __b) const
7181e991
FD
1048 {
1049 __glibcxx_check_bucket_index(__b);
4b763dee 1050 return { _Base::begin(__b), this };
7181e991 1051 }
77e0bf4e
FD
1052
1053 const_local_iterator
1054 end(size_type __b) const
7181e991
FD
1055 {
1056 __glibcxx_check_bucket_index(__b);
4b763dee 1057 return { _Base::end(__b), this };
7181e991 1058 }
77e0bf4e
FD
1059
1060 const_local_iterator
1061 cbegin(size_type __b) const
7181e991
FD
1062 {
1063 __glibcxx_check_bucket_index(__b);
4b763dee 1064 return { _Base::cbegin(__b), this };
7181e991 1065 }
77e0bf4e
FD
1066
1067 const_local_iterator
1068 cend(size_type __b) const
7181e991
FD
1069 {
1070 __glibcxx_check_bucket_index(__b);
4b763dee 1071 return { _Base::cend(__b), this };
7181e991
FD
1072 }
1073
f4b4ce15
FD
1074 using _Base::bucket_count;
1075 using _Base::max_bucket_count;
1076
7181e991
FD
1077 size_type
1078 bucket_size(size_type __b) const
1079 {
1080 __glibcxx_check_bucket_index(__b);
1081 return _Base::bucket_size(__b);
1082 }
14cbb5d8 1083
f4b4ce15
FD
1084 using _Base::bucket;
1085 using _Base::load_factor;
1086
14cbb5d8
FD
1087 float
1088 max_load_factor() const noexcept
1089 { return _Base::max_load_factor(); }
1090
1091 void
1092 max_load_factor(float __f)
1093 {
1094 __glibcxx_check_max_load_factor(__f);
1095 _Base::max_load_factor(__f);
1096 }
ced3cb9f 1097
f4b4ce15
FD
1098 using _Base::rehash;
1099 using _Base::reserve;
1100
9b81593b
FD
1101 template<typename... _Args>
1102 iterator
1103 emplace(_Args&&... __args)
1104 {
1105 size_type __bucket_count = this->bucket_count();
4b763dee 1106 auto __it = _Base::emplace(std::forward<_Args>(__args)...);
9b81593b 1107 _M_check_rehashed(__bucket_count);
4b763dee 1108 return { __it, this };
9b81593b
FD
1109 }
1110
1111 template<typename... _Args>
1112 iterator
1113 emplace_hint(const_iterator __hint, _Args&&... __args)
1114 {
1115 __glibcxx_check_insert(__hint);
1116 size_type __bucket_count = this->bucket_count();
4b763dee
FD
1117 auto __it = _Base::emplace_hint(__hint.base(),
1118 std::forward<_Args>(__args)...);
9b81593b 1119 _M_check_rehashed(__bucket_count);
4b763dee 1120 return { __it, this };
9b81593b
FD
1121 }
1122
ced3cb9f
PC
1123 iterator
1124 insert(const value_type& __obj)
77e0bf4e
FD
1125 {
1126 size_type __bucket_count = this->bucket_count();
4b763dee 1127 auto __it = _Base::insert(__obj);
77e0bf4e 1128 _M_check_rehashed(__bucket_count);
4b763dee 1129 return { __it, this };
77e0bf4e 1130 }
ced3cb9f
PC
1131
1132 iterator
d66411ba
FD
1133 insert(const_iterator __hint, const value_type& __obj)
1134 {
1135 __glibcxx_check_insert(__hint);
77e0bf4e 1136 size_type __bucket_count = this->bucket_count();
4b763dee 1137 auto __it = _Base::insert(__hint.base(), __obj);
77e0bf4e 1138 _M_check_rehashed(__bucket_count);
4b763dee 1139 return { __it, this };
d66411ba 1140 }
ced3cb9f 1141
fb7342fd
PC
1142 iterator
1143 insert(value_type&& __obj)
77e0bf4e
FD
1144 {
1145 size_type __bucket_count = this->bucket_count();
4b763dee 1146 auto __it = _Base::insert(std::move(__obj));
77e0bf4e 1147 _M_check_rehashed(__bucket_count);
4b763dee 1148 return { __it, this };
77e0bf4e 1149 }
fb7342fd
PC
1150
1151 iterator
d66411ba
FD
1152 insert(const_iterator __hint, value_type&& __obj)
1153 {
1154 __glibcxx_check_insert(__hint);
77e0bf4e 1155 size_type __bucket_count = this->bucket_count();
4b763dee 1156 auto __it = _Base::insert(__hint.base(), std::move(__obj));
77e0bf4e 1157 _M_check_rehashed(__bucket_count);
4b763dee 1158 return { __it, this };
d66411ba 1159 }
fb7342fd 1160
ced3cb9f
PC
1161 void
1162 insert(std::initializer_list<value_type> __l)
77e0bf4e
FD
1163 {
1164 size_type __bucket_count = this->bucket_count();
1165 _Base::insert(__l);
1166 _M_check_rehashed(__bucket_count);
1167 }
ced3cb9f
PC
1168
1169 template<typename _InputIterator>
77e0bf4e
FD
1170 void
1171 insert(_InputIterator __first, _InputIterator __last)
1172 {
24167c42
FD
1173 typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
1174 __glibcxx_check_valid_range2(__first, __last, __dist);
77e0bf4e 1175 size_type __bucket_count = this->bucket_count();
24167c42
FD
1176
1177 if (__dist.second >= __gnu_debug::__dp_sign)
1178 _Base::insert(__gnu_debug::__unsafe(__first),
1179 __gnu_debug::__unsafe(__last));
1180 else
1181 _Base::insert(__first, __last);
1182
77e0bf4e 1183 _M_check_rehashed(__bucket_count);
ced3cb9f
PC
1184 }
1185
2dbe56bd
JW
1186#if __cplusplus > 201402L
1187 using node_type = typename _Base::node_type;
1188
1189 node_type
1190 extract(const_iterator __position)
1191 {
1192 __glibcxx_check_erase(__position);
4b763dee 1193 return _M_extract(__position.base());
2dbe56bd
JW
1194 }
1195
1196 node_type
1197 extract(const key_type& __key)
1198 {
4b763dee
FD
1199 const auto __position = _Base::find(__key);
1200 if (__position != _Base::end())
1201 return _M_extract(__position);
2dbe56bd
JW
1202 return {};
1203 }
1204
1205 iterator
1206 insert(node_type&& __nh)
4b763dee 1207 { return { _Base::insert(std::move(__nh)), this }; }
2dbe56bd
JW
1208
1209 iterator
1210 insert(const_iterator __hint, node_type&& __nh)
1211 {
1212 __glibcxx_check_insert(__hint);
4b763dee 1213 return { _Base::insert(__hint.base(), std::move(__nh)), this };
2dbe56bd
JW
1214 }
1215
f4b4ce15
FD
1216 template<typename _H2, typename _P2>
1217 void
1218 merge(unordered_multiset<_Value, _H2, _P2, _Alloc>& __source)
1219 {
1220 auto __guard
1221 = _Safe::_S_umc_guard(std::__detail::_Identity{}, __source);
e9a53a4f 1222 _Base::merge(__source);
f4b4ce15
FD
1223 }
1224
1225 template<typename _H2, typename _P2>
1226 void
1227 merge(unordered_multiset<_Value, _H2, _P2, _Alloc>&& __source)
1228 { merge(__source); }
1229
1230 template<typename _H2, typename _P2>
1231 void
1232 merge(unordered_set<_Value, _H2, _P2, _Alloc>& __source)
1233 {
1234 auto __guard
1235 = _Safe::_S_uc_guard(std::__detail::_Identity{}, __source);
e9a53a4f 1236 _Base::merge(__source);
f4b4ce15
FD
1237 }
1238
1239 template<typename _H2, typename _P2>
1240 void
1241 merge(unordered_set<_Value, _H2, _P2, _Alloc>&& __source)
1242 { merge(__source); }
2dbe56bd
JW
1243#endif // C++17
1244
f4b4ce15
FD
1245 using _Base::hash_function;
1246 using _Base::key_eq;
1247
ced3cb9f
PC
1248 iterator
1249 find(const key_type& __key)
4b763dee 1250 { return { _Base::find(__key), this }; }
ced3cb9f 1251
d2b1a684
FD
1252#if __cplusplus > 201703L
1253 template<typename _Kt,
1254 typename = std::__has_is_transparent_t<_Hash, _Kt>,
1255 typename = std::__has_is_transparent_t<_Pred, _Kt>>
1256 iterator
1257 find(const _Kt& __k)
1258 { return { _Base::find(__k), this }; }
1259#endif
1260
ced3cb9f
PC
1261 const_iterator
1262 find(const key_type& __key) const
4b763dee 1263 { return { _Base::find(__key), this }; }
ced3cb9f 1264
d2b1a684
FD
1265#if __cplusplus > 201703L
1266 template<typename _Kt,
1267 typename = std::__has_is_transparent_t<_Hash, _Kt>,
1268 typename = std::__has_is_transparent_t<_Pred, _Kt>>
1269 const_iterator
1270 find(const _Kt& __k) const
1271 { return { _Base::find(__k), this }; }
1272#endif
1273
f4b4ce15
FD
1274 using _Base::count;
1275
1276#if __cplusplus > 201703L
1277 using _Base::contains;
1278#endif
1279
ced3cb9f
PC
1280 std::pair<iterator, iterator>
1281 equal_range(const key_type& __key)
1282 {
4b763dee
FD
1283 auto __res = _Base::equal_range(__key);
1284 return { { __res.first, this }, { __res.second, this } };
ced3cb9f
PC
1285 }
1286
d2b1a684
FD
1287#if __cplusplus > 201703L
1288 template<typename _Kt,
1289 typename = std::__has_is_transparent_t<_Hash, _Kt>,
1290 typename = std::__has_is_transparent_t<_Pred, _Kt>>
1291 std::pair<iterator, iterator>
1292 equal_range(const _Kt& __k)
1293 {
1294 auto __res = _Base::equal_range(__k);
1295 return { { __res.first, this }, { __res.second, this } };
1296 }
1297#endif
1298
ced3cb9f
PC
1299 std::pair<const_iterator, const_iterator>
1300 equal_range(const key_type& __key) const
1301 {
4b763dee
FD
1302 auto __res = _Base::equal_range(__key);
1303 return { { __res.first, this }, { __res.second, this } };
ced3cb9f
PC
1304 }
1305
d2b1a684
FD
1306#if __cplusplus > 201703L
1307 template<typename _Kt,
1308 typename = std::__has_is_transparent_t<_Hash, _Kt>,
1309 typename = std::__has_is_transparent_t<_Pred, _Kt>>
1310 std::pair<const_iterator, const_iterator>
1311 equal_range(const _Kt& __k) const
1312 {
1313 auto __res = _Base::equal_range(__k);
1314 return { { __res.first, this }, { __res.second, this } };
1315 }
1316#endif
1317
ced3cb9f
PC
1318 size_type
1319 erase(const key_type& __key)
1320 {
1321 size_type __ret(0);
4b763dee
FD
1322 auto __pair = _Base::equal_range(__key);
1323 for (auto __victim = __pair.first; __victim != __pair.second;)
ced3cb9f 1324 {
4b763dee
FD
1325 _M_invalidate(__victim);
1326 __victim = _Base::erase(__victim);
d3b8263e 1327 ++__ret;
ced3cb9f 1328 }
4b763dee 1329
ced3cb9f
PC
1330 return __ret;
1331 }
1332
d723ced2 1333 iterator
ced3cb9f
PC
1334 erase(const_iterator __it)
1335 {
1336 __glibcxx_check_erase(__it);
4b763dee 1337 return { _M_erase(__it.base()), this };
ced3cb9f
PC
1338 }
1339
5f40d34b
FD
1340 _Base_iterator
1341 erase(_Base_const_iterator __it)
1342 {
1343 __glibcxx_check_erase2(__it);
1344 return _M_erase(__it);
1345 }
1346
6dc88283
PC
1347 iterator
1348 erase(iterator __it)
4b763dee
FD
1349 {
1350 __glibcxx_check_erase(__it);
1351 return { _M_erase(__it.base()), this };
1352 }
6dc88283 1353
d723ced2 1354 iterator
ced3cb9f
PC
1355 erase(const_iterator __first, const_iterator __last)
1356 {
1357 __glibcxx_check_erase_range(__first, __last);
4b763dee 1358 for (auto __tmp = __first.base(); __tmp != __last.base(); ++__tmp)
afe96d41 1359 {
4b763dee 1360 _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::cend(),
afe96d41
FD
1361 _M_message(__gnu_debug::__msg_valid_range)
1362 ._M_iterator(__first, "first")
1363 ._M_iterator(__last, "last"));
4b763dee 1364 _M_invalidate(__tmp);
afe96d41 1365 }
4b763dee 1366 return { _Base::erase(__first.base(), __last.base()), this };
ced3cb9f
PC
1367 }
1368
1369 _Base&
15ee1a77 1370 _M_base() noexcept { return *this; }
ced3cb9f
PC
1371
1372 const _Base&
15ee1a77 1373 _M_base() const noexcept { return *this; }
ced3cb9f 1374
69b3331e 1375 private:
77e0bf4e
FD
1376 void
1377 _M_check_rehashed(size_type __prev_count)
1378 {
1379 if (__prev_count != this->bucket_count())
20a4550c 1380 this->_M_invalidate_all();
69b3331e 1381 }
4b763dee
FD
1382
1383 void
1384 _M_invalidate(_Base_const_iterator __victim)
1385 {
1386 this->_M_invalidate_if(
1387 [__victim](_Base_const_iterator __it) { return __it == __victim; });
1388 this->_M_invalidate_local_if(
1389 [__victim](_Base_const_local_iterator __it)
acc1d1a9 1390 { return __it == __victim; });
4b763dee
FD
1391 }
1392
1393 _Base_iterator
1394 _M_erase(_Base_const_iterator __victim)
1395 {
1396 _M_invalidate(__victim);
1397 size_type __bucket_count = this->bucket_count();
1398 _Base_iterator __next = _Base::erase(__victim);
1399 _M_check_rehashed(__bucket_count);
1400 return __next;
1401 }
1402
1403#if __cplusplus > 201402L
1404 node_type
1405 _M_extract(_Base_const_iterator __victim)
1406 {
1407 _M_invalidate(__victim);
1408 return _Base::extract(__victim);
1409 }
1410#endif
e63637ea
BK
1411 };
1412
957f5fea
VV
1413#if __cpp_deduction_guides >= 201606
1414
1415 template<typename _InputIterator,
1416 typename _Hash =
c0cb38c2 1417 hash<typename iterator_traits<_InputIterator>::value_type>,
957f5fea 1418 typename _Pred =
c0cb38c2 1419 equal_to<typename iterator_traits<_InputIterator>::value_type>,
957f5fea 1420 typename _Allocator =
c0cb38c2 1421 allocator<typename iterator_traits<_InputIterator>::value_type>,
957f5fea 1422 typename = _RequireInputIter<_InputIterator>,
c0cb38c2
FD
1423 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1424 typename = _RequireNotAllocator<_Pred>,
957f5fea
VV
1425 typename = _RequireAllocator<_Allocator>>
1426 unordered_multiset(_InputIterator, _InputIterator,
1427 unordered_multiset<int>::size_type = {},
1428 _Hash = _Hash(), _Pred = _Pred(),
1429 _Allocator = _Allocator())
1430 -> unordered_multiset<typename iterator_traits<_InputIterator>::value_type,
4b763dee 1431 _Hash, _Pred, _Allocator>;
957f5fea
VV
1432
1433 template<typename _Tp, typename _Hash = hash<_Tp>,
1434 typename _Pred = equal_to<_Tp>,
1435 typename _Allocator = allocator<_Tp>,
c0cb38c2
FD
1436 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1437 typename = _RequireNotAllocator<_Pred>,
957f5fea
VV
1438 typename = _RequireAllocator<_Allocator>>
1439 unordered_multiset(initializer_list<_Tp>,
1440 unordered_multiset<int>::size_type = {},
1441 _Hash = _Hash(), _Pred = _Pred(),
1442 _Allocator = _Allocator())
1443 -> unordered_multiset<_Tp, _Hash, _Pred, _Allocator>;
1444
1445 template<typename _InputIterator, typename _Allocator,
1446 typename = _RequireInputIter<_InputIterator>,
1447 typename = _RequireAllocator<_Allocator>>
1448 unordered_multiset(_InputIterator, _InputIterator,
1449 unordered_multiset<int>::size_type, _Allocator)
1450 -> unordered_multiset<typename iterator_traits<_InputIterator>::value_type,
1451 hash<typename
1452 iterator_traits<_InputIterator>::value_type>,
1453 equal_to<typename
1454 iterator_traits<_InputIterator>::value_type>,
1455 _Allocator>;
1456
1ecd95ea
TK
1457 template<typename _InputIterator, typename _Allocator,
1458 typename = _RequireInputIter<_InputIterator>,
1459 typename = _RequireAllocator<_Allocator>>
1460 unordered_multiset(_InputIterator, _InputIterator, _Allocator)
1461 -> unordered_multiset<typename iterator_traits<_InputIterator>::value_type,
1462 hash<typename
1463 iterator_traits<_InputIterator>::value_type>,
1464 equal_to<typename
1465 iterator_traits<_InputIterator>::value_type>,
1466 _Allocator>;
1467
957f5fea
VV
1468 template<typename _InputIterator, typename _Hash, typename _Allocator,
1469 typename = _RequireInputIter<_InputIterator>,
c0cb38c2 1470 typename = _RequireNotAllocatorOrIntegral<_Hash>,
957f5fea
VV
1471 typename = _RequireAllocator<_Allocator>>
1472 unordered_multiset(_InputIterator, _InputIterator,
1473 unordered_multiset<int>::size_type,
1474 _Hash, _Allocator)
1475 -> unordered_multiset<typename
1476 iterator_traits<_InputIterator>::value_type,
1477 _Hash,
1478 equal_to<
1479 typename
1480 iterator_traits<_InputIterator>::value_type>,
1481 _Allocator>;
1482
1483 template<typename _Tp, typename _Allocator,
1484 typename = _RequireAllocator<_Allocator>>
1485 unordered_multiset(initializer_list<_Tp>,
1486 unordered_multiset<int>::size_type, _Allocator)
1487 -> unordered_multiset<_Tp, hash<_Tp>, equal_to<_Tp>, _Allocator>;
1488
1ecd95ea
TK
1489 template<typename _Tp, typename _Allocator,
1490 typename = _RequireAllocator<_Allocator>>
1491 unordered_multiset(initializer_list<_Tp>, _Allocator)
1492 -> unordered_multiset<_Tp, hash<_Tp>, equal_to<_Tp>, _Allocator>;
1493
957f5fea 1494 template<typename _Tp, typename _Hash, typename _Allocator,
c0cb38c2 1495 typename = _RequireNotAllocatorOrIntegral<_Hash>,
957f5fea
VV
1496 typename = _RequireAllocator<_Allocator>>
1497 unordered_multiset(initializer_list<_Tp>,
1498 unordered_multiset<int>::size_type, _Hash, _Allocator)
1499 -> unordered_multiset<_Tp, _Hash, equal_to<_Tp>, _Allocator>;
1500
ae54d8cb 1501#if __glibcxx_containers_ranges // C++ >= 23
7cc40201
TK
1502 template<ranges::input_range _Rg,
1503 __not_allocator_like _Hash = hash<ranges::range_value_t<_Rg>>,
1504 __not_allocator_like _Pred = equal_to<ranges::range_value_t<_Rg>>,
1505 __allocator_like _Allocator = allocator<ranges::range_value_t<_Rg>>>
1506 unordered_set(from_range_t, _Rg&&, unordered_set<int>::size_type = {},
1507 _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
1508 -> unordered_set<ranges::range_value_t<_Rg>, _Hash, _Pred, _Allocator>;
1509
1510 template<ranges::input_range _Rg,
1511 __allocator_like _Allocator>
1512 unordered_set(from_range_t, _Rg&&, unordered_set<int>::size_type,
1513 _Allocator)
1514 -> unordered_set<ranges::range_value_t<_Rg>,
1515 hash<ranges::range_value_t<_Rg>>,
1516 equal_to<ranges::range_value_t<_Rg>>,
1517 _Allocator>;
1518
1519 template<ranges::input_range _Rg,
1520 __allocator_like _Allocator>
1521 unordered_set(from_range_t, _Rg&&, _Allocator)
1522 -> unordered_set<ranges::range_value_t<_Rg>,
1523 hash<ranges::range_value_t<_Rg>>,
1524 equal_to<ranges::range_value_t<_Rg>>,
1525 _Allocator>;
1526
1527 template<ranges::input_range _Rg,
1528 __not_allocator_like _Hash,
1529 __allocator_like _Allocator>
1530 unordered_set(from_range_t, _Rg&&, unordered_set<int>::size_type,
1531 _Hash, _Allocator)
1532 -> unordered_set<ranges::range_value_t<_Rg>, _Hash,
1533 equal_to<ranges::range_value_t<_Rg>>,
1534 _Allocator>;
1535
ae54d8cb 1536#if __glibcxx_containers_ranges // C++ >= 23
7cc40201
TK
1537 template<ranges::input_range _Rg,
1538 __not_allocator_like _Hash = hash<ranges::range_value_t<_Rg>>,
1539 __not_allocator_like _Pred = equal_to<ranges::range_value_t<_Rg>>,
1540 __allocator_like _Allocator = allocator<ranges::range_value_t<_Rg>>>
1541 unordered_multiset(from_range_t, _Rg&&,
1542 unordered_multiset<int>::size_type = {},
1543 _Hash = _Hash(), _Pred = _Pred(),
1544 _Allocator = _Allocator())
1545 -> unordered_multiset<ranges::range_value_t<_Rg>, _Hash, _Pred, _Allocator>;
1546
1547 template<ranges::input_range _Rg,
1548 __allocator_like _Allocator>
1549 unordered_multiset(from_range_t, _Rg&&, _Allocator)
1550 -> unordered_multiset<ranges::range_value_t<_Rg>,
1551 hash<ranges::range_value_t<_Rg>>,
1552 equal_to<ranges::range_value_t<_Rg>>,
1553 _Allocator>;
1554
1555 template<ranges::input_range _Rg,
1556 __allocator_like _Allocator>
1557 unordered_multiset(from_range_t, _Rg&&, unordered_multiset<int>::size_type,
1558 _Allocator)
1559 -> unordered_multiset<ranges::range_value_t<_Rg>,
1560 hash<ranges::range_value_t<_Rg>>,
1561 equal_to<ranges::range_value_t<_Rg>>,
1562 _Allocator>;
1563
1564 template<ranges::input_range _Rg,
1565 __not_allocator_like _Hash,
1566 __allocator_like _Allocator>
1567 unordered_multiset(from_range_t, _Rg&&,
1568 unordered_multiset<int>::size_type,
1569 _Hash, _Allocator)
1570 -> unordered_multiset<ranges::range_value_t<_Rg>, _Hash,
1571 equal_to<ranges::range_value_t<_Rg>>,
1572 _Allocator>;
1573#endif
1574#endif
1575
957f5fea
VV
1576#endif
1577
e63637ea 1578 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
69b3331e
PC
1579 inline void
1580 swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1581 unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
c5d9ec56 1582 noexcept(noexcept(__x.swap(__y)))
69b3331e 1583 { __x.swap(__y); }
e63637ea 1584
5dc22714
PC
1585 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
1586 inline bool
1587 operator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1588 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
637fd8b3 1589 { return __x._M_base() == __y._M_base(); }
5dc22714 1590
7ab9c243 1591#if __cpp_impl_three_way_comparison < 201907L
5dc22714
PC
1592 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
1593 inline bool
1594 operator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1595 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1596 { return !(__x == __y); }
7ab9c243 1597#endif
5dc22714 1598
e63637ea
BK
1599} // namespace __debug
1600} // namespace std
1601
734f5023 1602#endif // C++11
c878d6ba 1603
e63637ea 1604#endif