]>
Commit | Line | Data |
---|---|---|
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> |
40 | namespace 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 | 53 | namespace std _GLIBCXX_VISIBILITY(default) |
e63637ea BK |
54 | { |
55 | namespace __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 |