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