]>
Commit | Line | Data |
---|---|---|
e63637ea BK |
1 | // Debugging unordered_set/unordered_multiset implementation -*- C++ -*- |
2 | ||
85ec4feb | 3 | // Copyright (C) 2003-2018 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 PC |
36 | #else |
37 | # include <unordered_set> | |
e63637ea | 38 | |
364c862b | 39 | #include <debug/safe_unordered_container.h> |
15ee1a77 | 40 | #include <debug/safe_container.h> |
e63637ea | 41 | #include <debug/safe_iterator.h> |
77e0bf4e | 42 | #include <debug/safe_local_iterator.h> |
e63637ea | 43 | |
12ffa228 | 44 | namespace std _GLIBCXX_VISIBILITY(default) |
e63637ea BK |
45 | { |
46 | namespace __debug | |
47 | { | |
1ceb9e06 | 48 | /// Class std::unordered_set with safety/checking/debug instrumentation. |
e63637ea | 49 | template<typename _Value, |
ced3cb9f | 50 | typename _Hash = std::hash<_Value>, |
e63637ea | 51 | typename _Pred = std::equal_to<_Value>, |
ced3cb9f | 52 | typename _Alloc = std::allocator<_Value> > |
e63637ea | 53 | class unordered_set |
15ee1a77 FD |
54 | : public __gnu_debug::_Safe_container< |
55 | unordered_set<_Value, _Hash, _Pred, _Alloc>, _Alloc, | |
56 | __gnu_debug::_Safe_unordered_container>, | |
57 | public _GLIBCXX_STD_C::unordered_set<_Value, _Hash, _Pred, _Alloc> | |
e63637ea | 58 | { |
15ee1a77 FD |
59 | typedef _GLIBCXX_STD_C::unordered_set< |
60 | _Value, _Hash, _Pred, _Alloc> _Base; | |
61 | typedef __gnu_debug::_Safe_container< | |
62 | unordered_set, _Alloc, __gnu_debug::_Safe_unordered_container> _Safe; | |
63 | ||
64 | typedef typename _Base::const_iterator _Base_const_iterator; | |
65 | typedef typename _Base::iterator _Base_iterator; | |
77e0bf4e | 66 | typedef typename _Base::const_local_iterator _Base_const_local_iterator; |
15ee1a77 | 67 | typedef typename _Base::local_iterator _Base_local_iterator; |
e63637ea BK |
68 | |
69 | public: | |
15ee1a77 FD |
70 | typedef typename _Base::size_type size_type; |
71 | typedef typename _Base::hasher hasher; | |
72 | typedef typename _Base::key_equal key_equal; | |
73 | typedef typename _Base::allocator_type allocator_type; | |
74 | ||
75 | typedef typename _Base::key_type key_type; | |
76 | typedef typename _Base::value_type value_type; | |
77 | ||
78 | typedef __gnu_debug::_Safe_iterator< | |
79 | _Base_iterator, unordered_set> iterator; | |
80 | typedef __gnu_debug::_Safe_iterator< | |
81 | _Base_const_iterator, unordered_set> const_iterator; | |
82 | typedef __gnu_debug::_Safe_local_iterator< | |
83 | _Base_local_iterator, unordered_set> local_iterator; | |
84 | typedef __gnu_debug::_Safe_local_iterator< | |
85 | _Base_const_local_iterator, unordered_set> const_local_iterator; | |
e63637ea | 86 | |
da27f556 FD |
87 | unordered_set() = default; |
88 | ||
e63637ea | 89 | explicit |
da27f556 | 90 | unordered_set(size_type __n, |
e63637ea BK |
91 | const hasher& __hf = hasher(), |
92 | const key_equal& __eql = key_equal(), | |
93 | const allocator_type& __a = allocator_type()) | |
ced3cb9f | 94 | : _Base(__n, __hf, __eql, __a) { } |
e63637ea BK |
95 | |
96 | template<typename _InputIterator> | |
15ee1a77 | 97 | unordered_set(_InputIterator __first, _InputIterator __last, |
417e896e | 98 | size_type __n = 0, |
15ee1a77 FD |
99 | const hasher& __hf = hasher(), |
100 | const key_equal& __eql = key_equal(), | |
e63637ea | 101 | const allocator_type& __a = allocator_type()) |
1f5ca1a1 PC |
102 | : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first, |
103 | __last)), | |
104 | __gnu_debug::__base(__last), __n, | |
4c2d93db | 105 | __hf, __eql, __a) { } |
ced3cb9f | 106 | |
0462b6aa | 107 | unordered_set(const unordered_set&) = default; |
ced3cb9f | 108 | |
0462b6aa | 109 | unordered_set(const _Base& __x) |
15ee1a77 | 110 | : _Base(__x) { } |
0462b6aa FD |
111 | |
112 | unordered_set(unordered_set&&) = default; | |
113 | ||
114 | explicit | |
115 | unordered_set(const allocator_type& __a) | |
15ee1a77 | 116 | : _Base(__a) { } |
0462b6aa FD |
117 | |
118 | unordered_set(const unordered_set& __uset, | |
119 | const allocator_type& __a) | |
15ee1a77 | 120 | : _Base(__uset, __a) { } |
ced3cb9f | 121 | |
0462b6aa FD |
122 | unordered_set(unordered_set&& __uset, |
123 | const allocator_type& __a) | |
15ee1a77 FD |
124 | : _Safe(std::move(__uset._M_safe()), __a), |
125 | _Base(std::move(__uset._M_base()), __a) { } | |
e63637ea | 126 | |
988499f4 | 127 | unordered_set(initializer_list<value_type> __l, |
417e896e | 128 | size_type __n = 0, |
988499f4 JM |
129 | const hasher& __hf = hasher(), |
130 | const key_equal& __eql = key_equal(), | |
131 | const allocator_type& __a = allocator_type()) | |
4c2d93db | 132 | : _Base(__l, __n, __hf, __eql, __a) { } |
e63637ea | 133 | |
e55b80f5 FD |
134 | unordered_set(size_type __n, const allocator_type& __a) |
135 | : unordered_set(__n, hasher(), key_equal(), __a) | |
136 | { } | |
137 | ||
138 | unordered_set(size_type __n, const hasher& __hf, | |
139 | const allocator_type& __a) | |
140 | : unordered_set(__n, __hf, key_equal(), __a) | |
141 | { } | |
142 | ||
143 | template<typename _InputIterator> | |
144 | unordered_set(_InputIterator __first, _InputIterator __last, | |
145 | size_type __n, | |
146 | const allocator_type& __a) | |
147 | : unordered_set(__first, __last, __n, hasher(), key_equal(), __a) | |
148 | { } | |
149 | ||
150 | template<typename _InputIterator> | |
151 | unordered_set(_InputIterator __first, _InputIterator __last, | |
152 | size_type __n, const hasher& __hf, | |
153 | const allocator_type& __a) | |
154 | : unordered_set(__first, __last, __n, __hf, key_equal(), __a) | |
155 | { } | |
156 | ||
157 | unordered_set(initializer_list<value_type> __l, | |
158 | size_type __n, | |
159 | const allocator_type& __a) | |
160 | : unordered_set(__l, __n, hasher(), key_equal(), __a) | |
161 | { } | |
162 | ||
163 | unordered_set(initializer_list<value_type> __l, | |
164 | size_type __n, const hasher& __hf, | |
165 | const allocator_type& __a) | |
166 | : unordered_set(__l, __n, __hf, key_equal(), __a) | |
167 | { } | |
168 | ||
15ee1a77 | 169 | ~unordered_set() = default; |
6f59ea25 | 170 | |
ced3cb9f | 171 | unordered_set& |
15ee1a77 | 172 | operator=(const unordered_set&) = default; |
69b3331e PC |
173 | |
174 | unordered_set& | |
15ee1a77 | 175 | operator=(unordered_set&&) = default; |
69b3331e | 176 | |
988499f4 JM |
177 | unordered_set& |
178 | operator=(initializer_list<value_type> __l) | |
179 | { | |
0462b6aa FD |
180 | _M_base() = __l; |
181 | this->_M_invalidate_all(); | |
988499f4 JM |
182 | return *this; |
183 | } | |
184 | ||
e63637ea | 185 | void |
ff74fd13 | 186 | swap(unordered_set& __x) |
c5d9ec56 | 187 | noexcept( noexcept(declval<_Base&>().swap(__x)) ) |
e63637ea | 188 | { |
15ee1a77 | 189 | _Safe::_M_swap(__x); |
ced3cb9f | 190 | _Base::swap(__x); |
e63637ea | 191 | } |
69b3331e PC |
192 | |
193 | void | |
d3677132 | 194 | clear() noexcept |
69b3331e PC |
195 | { |
196 | _Base::clear(); | |
197 | this->_M_invalidate_all(); | |
198 | } | |
199 | ||
15ee1a77 | 200 | iterator |
d3677132 | 201 | begin() noexcept |
ced3cb9f PC |
202 | { return iterator(_Base::begin(), this); } |
203 | ||
204 | const_iterator | |
d3677132 | 205 | begin() const noexcept |
ced3cb9f PC |
206 | { return const_iterator(_Base::begin(), this); } |
207 | ||
208 | iterator | |
d3677132 | 209 | end() noexcept |
ced3cb9f PC |
210 | { return iterator(_Base::end(), this); } |
211 | ||
212 | const_iterator | |
d3677132 | 213 | end() const noexcept |
ced3cb9f PC |
214 | { return const_iterator(_Base::end(), this); } |
215 | ||
216 | const_iterator | |
d3677132 | 217 | cbegin() const noexcept |
ced3cb9f PC |
218 | { return const_iterator(_Base::begin(), this); } |
219 | ||
220 | const_iterator | |
d3677132 | 221 | cend() const noexcept |
ced3cb9f PC |
222 | { return const_iterator(_Base::end(), this); } |
223 | ||
224 | // local versions | |
77e0bf4e FD |
225 | local_iterator |
226 | begin(size_type __b) | |
7181e991 FD |
227 | { |
228 | __glibcxx_check_bucket_index(__b); | |
2e5189c8 | 229 | return local_iterator(_Base::begin(__b), this); |
7181e991 | 230 | } |
77e0bf4e FD |
231 | |
232 | local_iterator | |
233 | end(size_type __b) | |
7181e991 FD |
234 | { |
235 | __glibcxx_check_bucket_index(__b); | |
2e5189c8 | 236 | return local_iterator(_Base::end(__b), this); |
7181e991 | 237 | } |
77e0bf4e FD |
238 | |
239 | const_local_iterator | |
240 | begin(size_type __b) const | |
7181e991 FD |
241 | { |
242 | __glibcxx_check_bucket_index(__b); | |
2e5189c8 | 243 | return const_local_iterator(_Base::begin(__b), this); |
7181e991 | 244 | } |
77e0bf4e FD |
245 | |
246 | const_local_iterator | |
247 | end(size_type __b) const | |
7181e991 FD |
248 | { |
249 | __glibcxx_check_bucket_index(__b); | |
2e5189c8 | 250 | return const_local_iterator(_Base::end(__b), this); |
7181e991 | 251 | } |
77e0bf4e FD |
252 | |
253 | const_local_iterator | |
254 | cbegin(size_type __b) const | |
7181e991 FD |
255 | { |
256 | __glibcxx_check_bucket_index(__b); | |
2e5189c8 | 257 | return const_local_iterator(_Base::cbegin(__b), this); |
7181e991 | 258 | } |
77e0bf4e FD |
259 | |
260 | const_local_iterator | |
261 | cend(size_type __b) const | |
7181e991 FD |
262 | { |
263 | __glibcxx_check_bucket_index(__b); | |
2e5189c8 | 264 | return const_local_iterator(_Base::cend(__b), this); |
7181e991 FD |
265 | } |
266 | ||
267 | size_type | |
268 | bucket_size(size_type __b) const | |
269 | { | |
270 | __glibcxx_check_bucket_index(__b); | |
271 | return _Base::bucket_size(__b); | |
272 | } | |
ced3cb9f | 273 | |
14cbb5d8 FD |
274 | float |
275 | max_load_factor() const noexcept | |
276 | { return _Base::max_load_factor(); } | |
277 | ||
278 | void | |
279 | max_load_factor(float __f) | |
280 | { | |
281 | __glibcxx_check_max_load_factor(__f); | |
282 | _Base::max_load_factor(__f); | |
283 | } | |
284 | ||
9b81593b FD |
285 | template<typename... _Args> |
286 | std::pair<iterator, bool> | |
287 | emplace(_Args&&... __args) | |
288 | { | |
289 | size_type __bucket_count = this->bucket_count(); | |
290 | std::pair<_Base_iterator, bool> __res | |
291 | = _Base::emplace(std::forward<_Args>(__args)...); | |
292 | _M_check_rehashed(__bucket_count); | |
293 | return std::make_pair(iterator(__res.first, this), __res.second); | |
294 | } | |
295 | ||
296 | template<typename... _Args> | |
297 | iterator | |
298 | emplace_hint(const_iterator __hint, _Args&&... __args) | |
299 | { | |
300 | __glibcxx_check_insert(__hint); | |
301 | size_type __bucket_count = this->bucket_count(); | |
302 | _Base_iterator __it = _Base::emplace_hint(__hint.base(), | |
303 | std::forward<_Args>(__args)...); | |
304 | _M_check_rehashed(__bucket_count); | |
305 | return iterator(__it, this); | |
306 | } | |
307 | ||
ced3cb9f PC |
308 | std::pair<iterator, bool> |
309 | insert(const value_type& __obj) | |
310 | { | |
77e0bf4e | 311 | size_type __bucket_count = this->bucket_count(); |
15ee1a77 FD |
312 | std::pair<_Base_iterator, bool> __res |
313 | = _Base::insert(__obj); | |
77e0bf4e | 314 | _M_check_rehashed(__bucket_count); |
ced3cb9f PC |
315 | return std::make_pair(iterator(__res.first, this), __res.second); |
316 | } | |
317 | ||
318 | iterator | |
d66411ba | 319 | insert(const_iterator __hint, const value_type& __obj) |
ced3cb9f | 320 | { |
d66411ba | 321 | __glibcxx_check_insert(__hint); |
77e0bf4e FD |
322 | size_type __bucket_count = this->bucket_count(); |
323 | _Base_iterator __it = _Base::insert(__hint.base(), __obj); | |
324 | _M_check_rehashed(__bucket_count); | |
325 | return iterator(__it, this); | |
ced3cb9f PC |
326 | } |
327 | ||
fb7342fd PC |
328 | std::pair<iterator, bool> |
329 | insert(value_type&& __obj) | |
330 | { | |
77e0bf4e | 331 | size_type __bucket_count = this->bucket_count(); |
15ee1a77 FD |
332 | std::pair<_Base_iterator, bool> __res |
333 | = _Base::insert(std::move(__obj)); | |
77e0bf4e | 334 | _M_check_rehashed(__bucket_count); |
fb7342fd PC |
335 | return std::make_pair(iterator(__res.first, this), __res.second); |
336 | } | |
337 | ||
338 | iterator | |
d66411ba | 339 | insert(const_iterator __hint, value_type&& __obj) |
fb7342fd | 340 | { |
d66411ba | 341 | __glibcxx_check_insert(__hint); |
77e0bf4e FD |
342 | size_type __bucket_count = this->bucket_count(); |
343 | _Base_iterator __it = _Base::insert(__hint.base(), std::move(__obj)); | |
344 | _M_check_rehashed(__bucket_count); | |
345 | return iterator(__it, this); | |
fb7342fd PC |
346 | } |
347 | ||
ced3cb9f PC |
348 | void |
349 | insert(std::initializer_list<value_type> __l) | |
77e0bf4e FD |
350 | { |
351 | size_type __bucket_count = this->bucket_count(); | |
352 | _Base::insert(__l); | |
353 | _M_check_rehashed(__bucket_count); | |
354 | } | |
ced3cb9f PC |
355 | |
356 | template<typename _InputIterator> | |
77e0bf4e FD |
357 | void |
358 | insert(_InputIterator __first, _InputIterator __last) | |
359 | { | |
24167c42 FD |
360 | typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist; |
361 | __glibcxx_check_valid_range2(__first, __last, __dist); | |
77e0bf4e | 362 | size_type __bucket_count = this->bucket_count(); |
24167c42 FD |
363 | |
364 | if (__dist.second >= __gnu_debug::__dp_sign) | |
365 | _Base::insert(__gnu_debug::__unsafe(__first), | |
366 | __gnu_debug::__unsafe(__last)); | |
367 | else | |
368 | _Base::insert(__first, __last); | |
369 | ||
77e0bf4e | 370 | _M_check_rehashed(__bucket_count); |
ced3cb9f PC |
371 | } |
372 | ||
2dbe56bd JW |
373 | #if __cplusplus > 201402L |
374 | using node_type = typename _Base::node_type; | |
adaefe2a | 375 | using insert_return_type = _Node_insert_return<iterator, node_type>; |
2dbe56bd JW |
376 | |
377 | node_type | |
378 | extract(const_iterator __position) | |
379 | { | |
380 | __glibcxx_check_erase(__position); | |
381 | _Base_const_iterator __victim = __position.base(); | |
382 | this->_M_invalidate_if( | |
383 | [__victim](_Base_const_iterator __it) { return __it == __victim; } | |
384 | ); | |
385 | this->_M_invalidate_local_if( | |
386 | [__victim](_Base_const_local_iterator __it) { | |
387 | return __it._M_curr() == __victim._M_cur; | |
388 | }); | |
389 | return _Base::extract(__position.base()); | |
390 | } | |
391 | ||
392 | node_type | |
393 | extract(const key_type& __key) | |
394 | { | |
395 | const auto __position = find(__key); | |
396 | if (__position != end()) | |
397 | return extract(__position); | |
398 | return {}; | |
399 | } | |
400 | ||
401 | insert_return_type | |
402 | insert(node_type&& __nh) | |
403 | { | |
404 | auto __ret = _Base::insert(std::move(__nh)); | |
405 | iterator __pos = iterator(__ret.position, this); | |
adaefe2a | 406 | return { __pos, __ret.inserted, std::move(__ret.node) }; |
2dbe56bd JW |
407 | } |
408 | ||
409 | iterator | |
410 | insert(const_iterator __hint, node_type&& __nh) | |
411 | { | |
412 | __glibcxx_check_insert(__hint); | |
413 | return iterator(_Base::insert(__hint.base(), std::move(__nh)), this); | |
414 | } | |
415 | ||
416 | using _Base::merge; | |
417 | #endif // C++17 | |
418 | ||
ced3cb9f PC |
419 | iterator |
420 | find(const key_type& __key) | |
421 | { return iterator(_Base::find(__key), this); } | |
422 | ||
423 | const_iterator | |
424 | find(const key_type& __key) const | |
425 | { return const_iterator(_Base::find(__key), this); } | |
426 | ||
427 | std::pair<iterator, iterator> | |
428 | equal_range(const key_type& __key) | |
429 | { | |
15ee1a77 FD |
430 | std::pair<_Base_iterator, _Base_iterator> __res |
431 | = _Base::equal_range(__key); | |
ced3cb9f PC |
432 | return std::make_pair(iterator(__res.first, this), |
433 | iterator(__res.second, this)); | |
434 | } | |
435 | ||
436 | std::pair<const_iterator, const_iterator> | |
437 | equal_range(const key_type& __key) const | |
438 | { | |
afe96d41 FD |
439 | std::pair<_Base_const_iterator, _Base_const_iterator> |
440 | __res = _Base::equal_range(__key); | |
ced3cb9f PC |
441 | return std::make_pair(const_iterator(__res.first, this), |
442 | const_iterator(__res.second, this)); | |
443 | } | |
444 | ||
445 | size_type | |
446 | erase(const key_type& __key) | |
447 | { | |
448 | size_type __ret(0); | |
afe96d41 FD |
449 | _Base_iterator __victim(_Base::find(__key)); |
450 | if (__victim != _Base::end()) | |
ced3cb9f | 451 | { |
77e0bf4e FD |
452 | this->_M_invalidate_if( |
453 | [__victim](_Base_const_iterator __it) | |
454 | { return __it == __victim; }); | |
77e0bf4e | 455 | this->_M_invalidate_local_if( |
5b3be7cf | 456 | [__victim](_Base_const_local_iterator __it) |
92e16228 | 457 | { return __it._M_curr() == __victim._M_cur; }); |
77e0bf4e | 458 | size_type __bucket_count = this->bucket_count(); |
afe96d41 | 459 | _Base::erase(__victim); |
77e0bf4e | 460 | _M_check_rehashed(__bucket_count); |
ced3cb9f PC |
461 | __ret = 1; |
462 | } | |
463 | return __ret; | |
464 | } | |
465 | ||
d723ced2 | 466 | iterator |
ced3cb9f PC |
467 | erase(const_iterator __it) |
468 | { | |
469 | __glibcxx_check_erase(__it); | |
77e0bf4e FD |
470 | _Base_const_iterator __victim = __it.base(); |
471 | this->_M_invalidate_if( | |
472 | [__victim](_Base_const_iterator __it) | |
473 | { return __it == __victim; }); | |
77e0bf4e | 474 | this->_M_invalidate_local_if( |
5b3be7cf | 475 | [__victim](_Base_const_local_iterator __it) |
92e16228 | 476 | { return __it._M_curr() == __victim._M_cur; }); |
77e0bf4e FD |
477 | size_type __bucket_count = this->bucket_count(); |
478 | _Base_iterator __next = _Base::erase(__it.base()); | |
479 | _M_check_rehashed(__bucket_count); | |
480 | return iterator(__next, this); | |
ced3cb9f PC |
481 | } |
482 | ||
6dc88283 PC |
483 | iterator |
484 | erase(iterator __it) | |
485 | { return erase(const_iterator(__it)); } | |
486 | ||
d723ced2 | 487 | iterator |
ced3cb9f PC |
488 | erase(const_iterator __first, const_iterator __last) |
489 | { | |
490 | __glibcxx_check_erase_range(__first, __last); | |
afe96d41 FD |
491 | for (_Base_const_iterator __tmp = __first.base(); |
492 | __tmp != __last.base(); ++__tmp) | |
493 | { | |
494 | _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(), | |
495 | _M_message(__gnu_debug::__msg_valid_range) | |
496 | ._M_iterator(__first, "first") | |
497 | ._M_iterator(__last, "last")); | |
77e0bf4e FD |
498 | this->_M_invalidate_if( |
499 | [__tmp](_Base_const_iterator __it) | |
500 | { return __it == __tmp; }); | |
77e0bf4e | 501 | this->_M_invalidate_local_if( |
5b3be7cf | 502 | [__tmp](_Base_const_local_iterator __it) |
92e16228 | 503 | { return __it._M_curr() == __tmp._M_cur; }); |
afe96d41 | 504 | } |
77e0bf4e FD |
505 | size_type __bucket_count = this->bucket_count(); |
506 | _Base_iterator __next = _Base::erase(__first.base(), | |
507 | __last.base()); | |
508 | _M_check_rehashed(__bucket_count); | |
509 | return iterator(__next, this); | |
ced3cb9f PC |
510 | } |
511 | ||
512 | _Base& | |
15ee1a77 | 513 | _M_base() noexcept { return *this; } |
ced3cb9f PC |
514 | |
515 | const _Base& | |
d3677132 | 516 | _M_base() const noexcept { return *this; } |
ced3cb9f | 517 | |
69b3331e | 518 | private: |
77e0bf4e FD |
519 | void |
520 | _M_check_rehashed(size_type __prev_count) | |
521 | { | |
522 | if (__prev_count != this->bucket_count()) | |
15ee1a77 | 523 | this->_M_invalidate_locals(); |
69b3331e | 524 | } |
e63637ea BK |
525 | }; |
526 | ||
957f5fea VV |
527 | #if __cpp_deduction_guides >= 201606 |
528 | ||
529 | template<typename _InputIterator, | |
530 | typename _Hash = | |
531 | hash<typename iterator_traits<_InputIterator>::value_type>, | |
532 | typename _Pred = | |
533 | equal_to<typename iterator_traits<_InputIterator>::value_type>, | |
534 | typename _Allocator = | |
535 | allocator<typename iterator_traits<_InputIterator>::value_type>, | |
536 | typename = _RequireInputIter<_InputIterator>, | |
537 | typename = _RequireAllocator<_Allocator>> | |
538 | unordered_set(_InputIterator, _InputIterator, | |
539 | unordered_set<int>::size_type = {}, | |
540 | _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator()) | |
541 | -> unordered_set<typename iterator_traits<_InputIterator>::value_type, | |
542 | _Hash, _Pred, _Allocator>; | |
543 | ||
544 | template<typename _Tp, typename _Hash = hash<_Tp>, | |
545 | typename _Pred = equal_to<_Tp>, | |
546 | typename _Allocator = allocator<_Tp>, | |
547 | typename = _RequireAllocator<_Allocator>> | |
548 | unordered_set(initializer_list<_Tp>, | |
549 | unordered_set<int>::size_type = {}, | |
550 | _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator()) | |
551 | -> unordered_set<_Tp, _Hash, _Pred, _Allocator>; | |
552 | ||
553 | template<typename _InputIterator, typename _Allocator, | |
554 | typename = _RequireInputIter<_InputIterator>, | |
555 | typename = _RequireAllocator<_Allocator>> | |
556 | unordered_set(_InputIterator, _InputIterator, | |
557 | unordered_set<int>::size_type, _Allocator) | |
558 | -> unordered_set<typename iterator_traits<_InputIterator>::value_type, | |
559 | hash< | |
560 | typename iterator_traits<_InputIterator>::value_type>, | |
561 | equal_to< | |
562 | typename iterator_traits<_InputIterator>::value_type>, | |
563 | _Allocator>; | |
564 | ||
565 | template<typename _InputIterator, typename _Hash, typename _Allocator, | |
566 | typename = _RequireInputIter<_InputIterator>, | |
567 | typename = _RequireAllocator<_Allocator>> | |
568 | unordered_set(_InputIterator, _InputIterator, | |
569 | unordered_set<int>::size_type, | |
570 | _Hash, _Allocator) | |
571 | -> unordered_set<typename iterator_traits<_InputIterator>::value_type, | |
572 | _Hash, | |
573 | equal_to< | |
574 | typename iterator_traits<_InputIterator>::value_type>, | |
575 | _Allocator>; | |
576 | ||
577 | template<typename _Tp, typename _Allocator, | |
578 | typename = _RequireAllocator<_Allocator>> | |
579 | unordered_set(initializer_list<_Tp>, | |
580 | unordered_set<int>::size_type, _Allocator) | |
581 | -> unordered_set<_Tp, hash<_Tp>, equal_to<_Tp>, _Allocator>; | |
582 | ||
583 | template<typename _Tp, typename _Hash, typename _Allocator, | |
584 | typename = _RequireAllocator<_Allocator>> | |
585 | unordered_set(initializer_list<_Tp>, | |
586 | unordered_set<int>::size_type, _Hash, _Allocator) | |
587 | -> unordered_set<_Tp, _Hash, equal_to<_Tp>, _Allocator>; | |
588 | ||
589 | #endif | |
590 | ||
e63637ea | 591 | template<typename _Value, typename _Hash, typename _Pred, typename _Alloc> |
69b3331e PC |
592 | inline void |
593 | swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, | |
594 | unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) | |
c5d9ec56 | 595 | noexcept(noexcept(__x.swap(__y))) |
69b3331e | 596 | { __x.swap(__y); } |
e63637ea | 597 | |
5dc22714 PC |
598 | template<typename _Value, typename _Hash, typename _Pred, typename _Alloc> |
599 | inline bool | |
600 | operator==(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, | |
601 | const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) | |
637fd8b3 | 602 | { return __x._M_base() == __y._M_base(); } |
5dc22714 PC |
603 | |
604 | template<typename _Value, typename _Hash, typename _Pred, typename _Alloc> | |
605 | inline bool | |
606 | operator!=(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, | |
607 | const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) | |
608 | { return !(__x == __y); } | |
609 | ||
e63637ea | 610 | |
1ceb9e06 | 611 | /// Class std::unordered_multiset with safety/checking/debug instrumentation. |
e63637ea | 612 | template<typename _Value, |
ced3cb9f | 613 | typename _Hash = std::hash<_Value>, |
e63637ea | 614 | typename _Pred = std::equal_to<_Value>, |
ced3cb9f | 615 | typename _Alloc = std::allocator<_Value> > |
e63637ea | 616 | class unordered_multiset |
15ee1a77 FD |
617 | : public __gnu_debug::_Safe_container< |
618 | unordered_multiset<_Value, _Hash, _Pred, _Alloc>, _Alloc, | |
619 | __gnu_debug::_Safe_unordered_container>, | |
620 | public _GLIBCXX_STD_C::unordered_multiset<_Value, _Hash, _Pred, _Alloc> | |
e63637ea | 621 | { |
15ee1a77 FD |
622 | typedef _GLIBCXX_STD_C::unordered_multiset< |
623 | _Value, _Hash, _Pred, _Alloc> _Base; | |
624 | typedef __gnu_debug::_Safe_container<unordered_multiset, | |
625 | _Alloc, __gnu_debug::_Safe_unordered_container> _Safe; | |
626 | typedef typename _Base::const_iterator _Base_const_iterator; | |
627 | typedef typename _Base::iterator _Base_iterator; | |
628 | typedef typename _Base::const_local_iterator | |
629 | _Base_const_local_iterator; | |
630 | typedef typename _Base::local_iterator _Base_local_iterator; | |
0462b6aa | 631 | |
e63637ea | 632 | public: |
15ee1a77 FD |
633 | typedef typename _Base::size_type size_type; |
634 | typedef typename _Base::hasher hasher; | |
635 | typedef typename _Base::key_equal key_equal; | |
636 | typedef typename _Base::allocator_type allocator_type; | |
637 | ||
638 | typedef typename _Base::key_type key_type; | |
639 | typedef typename _Base::value_type value_type; | |
640 | ||
641 | typedef __gnu_debug::_Safe_iterator< | |
642 | _Base_iterator, unordered_multiset> iterator; | |
643 | typedef __gnu_debug::_Safe_iterator< | |
644 | _Base_const_iterator, unordered_multiset> const_iterator; | |
77e0bf4e | 645 | typedef __gnu_debug::_Safe_local_iterator< |
15ee1a77 | 646 | _Base_local_iterator, unordered_multiset> local_iterator; |
77e0bf4e FD |
647 | typedef __gnu_debug::_Safe_local_iterator< |
648 | _Base_const_local_iterator, unordered_multiset> const_local_iterator; | |
e63637ea | 649 | |
da27f556 FD |
650 | unordered_multiset() = default; |
651 | ||
e63637ea | 652 | explicit |
da27f556 | 653 | unordered_multiset(size_type __n, |
ced3cb9f PC |
654 | const hasher& __hf = hasher(), |
655 | const key_equal& __eql = key_equal(), | |
656 | const allocator_type& __a = allocator_type()) | |
657 | : _Base(__n, __hf, __eql, __a) { } | |
e63637ea BK |
658 | |
659 | template<typename _InputIterator> | |
15ee1a77 | 660 | unordered_multiset(_InputIterator __first, _InputIterator __last, |
417e896e | 661 | size_type __n = 0, |
15ee1a77 FD |
662 | const hasher& __hf = hasher(), |
663 | const key_equal& __eql = key_equal(), | |
ced3cb9f | 664 | const allocator_type& __a = allocator_type()) |
1f5ca1a1 PC |
665 | : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first, |
666 | __last)), | |
667 | __gnu_debug::__base(__last), __n, | |
4c2d93db | 668 | __hf, __eql, __a) { } |
ced3cb9f | 669 | |
0462b6aa | 670 | unordered_multiset(const unordered_multiset&) = default; |
ced3cb9f | 671 | |
15ee1a77 | 672 | unordered_multiset(const _Base& __x) |
4c2d93db | 673 | : _Base(__x) { } |
ced3cb9f | 674 | |
0462b6aa FD |
675 | unordered_multiset(unordered_multiset&&) = default; |
676 | ||
677 | explicit | |
678 | unordered_multiset(const allocator_type& __a) | |
15ee1a77 | 679 | : _Base(__a) { } |
0462b6aa FD |
680 | |
681 | unordered_multiset(const unordered_multiset& __uset, | |
682 | const allocator_type& __a) | |
15ee1a77 FD |
683 | : _Base(__uset, __a) { } |
684 | ||
0462b6aa FD |
685 | unordered_multiset(unordered_multiset&& __uset, |
686 | const allocator_type& __a) | |
15ee1a77 FD |
687 | : _Safe(std::move(__uset._M_safe()), __a), |
688 | _Base(std::move(__uset._M_base()), __a) { } | |
e63637ea | 689 | |
988499f4 | 690 | unordered_multiset(initializer_list<value_type> __l, |
417e896e | 691 | size_type __n = 0, |
988499f4 JM |
692 | const hasher& __hf = hasher(), |
693 | const key_equal& __eql = key_equal(), | |
694 | const allocator_type& __a = allocator_type()) | |
4c2d93db | 695 | : _Base(__l, __n, __hf, __eql, __a) { } |
e63637ea | 696 | |
e55b80f5 FD |
697 | unordered_multiset(size_type __n, const allocator_type& __a) |
698 | : unordered_multiset(__n, hasher(), key_equal(), __a) | |
699 | { } | |
700 | ||
701 | unordered_multiset(size_type __n, const hasher& __hf, | |
702 | const allocator_type& __a) | |
703 | : unordered_multiset(__n, __hf, key_equal(), __a) | |
704 | { } | |
705 | ||
706 | template<typename _InputIterator> | |
707 | unordered_multiset(_InputIterator __first, _InputIterator __last, | |
708 | size_type __n, | |
709 | const allocator_type& __a) | |
710 | : unordered_multiset(__first, __last, __n, hasher(), key_equal(), __a) | |
711 | { } | |
712 | ||
713 | template<typename _InputIterator> | |
714 | unordered_multiset(_InputIterator __first, _InputIterator __last, | |
715 | size_type __n, const hasher& __hf, | |
716 | const allocator_type& __a) | |
717 | : unordered_multiset(__first, __last, __n, __hf, key_equal(), __a) | |
718 | { } | |
719 | ||
720 | unordered_multiset(initializer_list<value_type> __l, | |
721 | size_type __n, | |
722 | const allocator_type& __a) | |
723 | : unordered_multiset(__l, __n, hasher(), key_equal(), __a) | |
724 | { } | |
725 | ||
726 | unordered_multiset(initializer_list<value_type> __l, | |
727 | size_type __n, const hasher& __hf, | |
728 | const allocator_type& __a) | |
729 | : unordered_multiset(__l, __n, __hf, key_equal(), __a) | |
730 | { } | |
731 | ||
15ee1a77 | 732 | ~unordered_multiset() = default; |
6f59ea25 | 733 | |
ced3cb9f | 734 | unordered_multiset& |
15ee1a77 | 735 | operator=(const unordered_multiset&) = default; |
69b3331e PC |
736 | |
737 | unordered_multiset& | |
15ee1a77 | 738 | operator=(unordered_multiset&&) = default; |
69b3331e | 739 | |
988499f4 JM |
740 | unordered_multiset& |
741 | operator=(initializer_list<value_type> __l) | |
742 | { | |
15ee1a77 | 743 | this->_M_base() = __l; |
0462b6aa | 744 | this->_M_invalidate_all(); |
988499f4 JM |
745 | return *this; |
746 | } | |
747 | ||
e63637ea | 748 | void |
ff74fd13 | 749 | swap(unordered_multiset& __x) |
c5d9ec56 | 750 | noexcept( noexcept(declval<_Base&>().swap(__x)) ) |
e63637ea | 751 | { |
15ee1a77 | 752 | _Safe::_M_swap(__x); |
ced3cb9f | 753 | _Base::swap(__x); |
e63637ea | 754 | } |
69b3331e | 755 | |
ced3cb9f | 756 | void |
d3677132 | 757 | clear() noexcept |
69b3331e PC |
758 | { |
759 | _Base::clear(); | |
760 | this->_M_invalidate_all(); | |
761 | } | |
762 | ||
ced3cb9f | 763 | iterator |
d3677132 | 764 | begin() noexcept |
ced3cb9f PC |
765 | { return iterator(_Base::begin(), this); } |
766 | ||
767 | const_iterator | |
d3677132 | 768 | begin() const noexcept |
ced3cb9f PC |
769 | { return const_iterator(_Base::begin(), this); } |
770 | ||
771 | iterator | |
d3677132 | 772 | end() noexcept |
ced3cb9f PC |
773 | { return iterator(_Base::end(), this); } |
774 | ||
775 | const_iterator | |
d3677132 | 776 | end() const noexcept |
ced3cb9f PC |
777 | { return const_iterator(_Base::end(), this); } |
778 | ||
779 | const_iterator | |
d3677132 | 780 | cbegin() const noexcept |
ced3cb9f PC |
781 | { return const_iterator(_Base::begin(), this); } |
782 | ||
783 | const_iterator | |
d3677132 | 784 | cend() const noexcept |
ced3cb9f PC |
785 | { return const_iterator(_Base::end(), this); } |
786 | ||
787 | // local versions | |
77e0bf4e FD |
788 | local_iterator |
789 | begin(size_type __b) | |
7181e991 FD |
790 | { |
791 | __glibcxx_check_bucket_index(__b); | |
2e5189c8 | 792 | return local_iterator(_Base::begin(__b), this); |
7181e991 | 793 | } |
77e0bf4e FD |
794 | |
795 | local_iterator | |
796 | end(size_type __b) | |
7181e991 FD |
797 | { |
798 | __glibcxx_check_bucket_index(__b); | |
2e5189c8 | 799 | return local_iterator(_Base::end(__b), this); |
7181e991 | 800 | } |
77e0bf4e FD |
801 | |
802 | const_local_iterator | |
803 | begin(size_type __b) const | |
7181e991 FD |
804 | { |
805 | __glibcxx_check_bucket_index(__b); | |
2e5189c8 | 806 | return const_local_iterator(_Base::begin(__b), this); |
7181e991 | 807 | } |
77e0bf4e FD |
808 | |
809 | const_local_iterator | |
810 | end(size_type __b) const | |
7181e991 FD |
811 | { |
812 | __glibcxx_check_bucket_index(__b); | |
2e5189c8 | 813 | return const_local_iterator(_Base::end(__b), this); |
7181e991 | 814 | } |
77e0bf4e FD |
815 | |
816 | const_local_iterator | |
817 | cbegin(size_type __b) const | |
7181e991 FD |
818 | { |
819 | __glibcxx_check_bucket_index(__b); | |
2e5189c8 | 820 | return const_local_iterator(_Base::cbegin(__b), this); |
7181e991 | 821 | } |
77e0bf4e FD |
822 | |
823 | const_local_iterator | |
824 | cend(size_type __b) const | |
7181e991 FD |
825 | { |
826 | __glibcxx_check_bucket_index(__b); | |
2e5189c8 | 827 | return const_local_iterator(_Base::cend(__b), this); |
7181e991 FD |
828 | } |
829 | ||
830 | size_type | |
831 | bucket_size(size_type __b) const | |
832 | { | |
833 | __glibcxx_check_bucket_index(__b); | |
834 | return _Base::bucket_size(__b); | |
835 | } | |
14cbb5d8 FD |
836 | |
837 | float | |
838 | max_load_factor() const noexcept | |
839 | { return _Base::max_load_factor(); } | |
840 | ||
841 | void | |
842 | max_load_factor(float __f) | |
843 | { | |
844 | __glibcxx_check_max_load_factor(__f); | |
845 | _Base::max_load_factor(__f); | |
846 | } | |
ced3cb9f | 847 | |
9b81593b FD |
848 | template<typename... _Args> |
849 | iterator | |
850 | emplace(_Args&&... __args) | |
851 | { | |
852 | size_type __bucket_count = this->bucket_count(); | |
853 | _Base_iterator __it | |
854 | = _Base::emplace(std::forward<_Args>(__args)...); | |
855 | _M_check_rehashed(__bucket_count); | |
856 | return iterator(__it, this); | |
857 | } | |
858 | ||
859 | template<typename... _Args> | |
860 | iterator | |
861 | emplace_hint(const_iterator __hint, _Args&&... __args) | |
862 | { | |
863 | __glibcxx_check_insert(__hint); | |
864 | size_type __bucket_count = this->bucket_count(); | |
865 | _Base_iterator __it = _Base::emplace_hint(__hint.base(), | |
866 | std::forward<_Args>(__args)...); | |
867 | _M_check_rehashed(__bucket_count); | |
868 | return iterator(__it, this); | |
869 | } | |
870 | ||
ced3cb9f PC |
871 | iterator |
872 | insert(const value_type& __obj) | |
77e0bf4e FD |
873 | { |
874 | size_type __bucket_count = this->bucket_count(); | |
875 | _Base_iterator __it = _Base::insert(__obj); | |
876 | _M_check_rehashed(__bucket_count); | |
877 | return iterator(__it, this); | |
878 | } | |
ced3cb9f PC |
879 | |
880 | iterator | |
d66411ba FD |
881 | insert(const_iterator __hint, const value_type& __obj) |
882 | { | |
883 | __glibcxx_check_insert(__hint); | |
77e0bf4e | 884 | size_type __bucket_count = this->bucket_count(); |
15ee1a77 | 885 | _Base_iterator __it = _Base::insert(__hint.base(), __obj); |
77e0bf4e FD |
886 | _M_check_rehashed(__bucket_count); |
887 | return iterator(__it, this); | |
d66411ba | 888 | } |
ced3cb9f | 889 | |
fb7342fd PC |
890 | iterator |
891 | insert(value_type&& __obj) | |
77e0bf4e FD |
892 | { |
893 | size_type __bucket_count = this->bucket_count(); | |
15ee1a77 | 894 | _Base_iterator __it = _Base::insert(std::move(__obj)); |
77e0bf4e FD |
895 | _M_check_rehashed(__bucket_count); |
896 | return iterator(__it, this); | |
897 | } | |
fb7342fd PC |
898 | |
899 | iterator | |
d66411ba FD |
900 | insert(const_iterator __hint, value_type&& __obj) |
901 | { | |
902 | __glibcxx_check_insert(__hint); | |
77e0bf4e | 903 | size_type __bucket_count = this->bucket_count(); |
15ee1a77 | 904 | _Base_iterator __it = _Base::insert(__hint.base(), std::move(__obj)); |
77e0bf4e FD |
905 | _M_check_rehashed(__bucket_count); |
906 | return iterator(__it, this); | |
d66411ba | 907 | } |
fb7342fd | 908 | |
ced3cb9f PC |
909 | void |
910 | insert(std::initializer_list<value_type> __l) | |
77e0bf4e FD |
911 | { |
912 | size_type __bucket_count = this->bucket_count(); | |
913 | _Base::insert(__l); | |
914 | _M_check_rehashed(__bucket_count); | |
915 | } | |
ced3cb9f PC |
916 | |
917 | template<typename _InputIterator> | |
77e0bf4e FD |
918 | void |
919 | insert(_InputIterator __first, _InputIterator __last) | |
920 | { | |
24167c42 FD |
921 | typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist; |
922 | __glibcxx_check_valid_range2(__first, __last, __dist); | |
77e0bf4e | 923 | size_type __bucket_count = this->bucket_count(); |
24167c42 FD |
924 | |
925 | if (__dist.second >= __gnu_debug::__dp_sign) | |
926 | _Base::insert(__gnu_debug::__unsafe(__first), | |
927 | __gnu_debug::__unsafe(__last)); | |
928 | else | |
929 | _Base::insert(__first, __last); | |
930 | ||
77e0bf4e | 931 | _M_check_rehashed(__bucket_count); |
ced3cb9f PC |
932 | } |
933 | ||
2dbe56bd JW |
934 | #if __cplusplus > 201402L |
935 | using node_type = typename _Base::node_type; | |
936 | ||
937 | node_type | |
938 | extract(const_iterator __position) | |
939 | { | |
940 | __glibcxx_check_erase(__position); | |
941 | _Base_const_iterator __victim = __position.base(); | |
942 | this->_M_invalidate_if( | |
943 | [__victim](_Base_const_iterator __it) { return __it == __victim; } | |
944 | ); | |
945 | this->_M_invalidate_local_if( | |
946 | [__victim](_Base_const_local_iterator __it) { | |
947 | return __it._M_curr() == __victim._M_cur; | |
948 | }); | |
949 | return _Base::extract(__position.base()); | |
950 | } | |
951 | ||
952 | node_type | |
953 | extract(const key_type& __key) | |
954 | { | |
955 | const auto __position = find(__key); | |
956 | if (__position != end()) | |
957 | return extract(__position); | |
958 | return {}; | |
959 | } | |
960 | ||
961 | iterator | |
962 | insert(node_type&& __nh) | |
963 | { return iterator(_Base::insert(std::move(__nh)), this); } | |
964 | ||
965 | iterator | |
966 | insert(const_iterator __hint, node_type&& __nh) | |
967 | { | |
968 | __glibcxx_check_insert(__hint); | |
969 | return iterator(_Base::insert(__hint.base(), std::move(__nh)), this); | |
970 | } | |
971 | ||
972 | using _Base::merge; | |
973 | #endif // C++17 | |
974 | ||
ced3cb9f PC |
975 | iterator |
976 | find(const key_type& __key) | |
977 | { return iterator(_Base::find(__key), this); } | |
978 | ||
979 | const_iterator | |
980 | find(const key_type& __key) const | |
981 | { return const_iterator(_Base::find(__key), this); } | |
982 | ||
983 | std::pair<iterator, iterator> | |
984 | equal_range(const key_type& __key) | |
985 | { | |
15ee1a77 FD |
986 | std::pair<_Base_iterator, _Base_iterator> __res |
987 | = _Base::equal_range(__key); | |
ced3cb9f PC |
988 | return std::make_pair(iterator(__res.first, this), |
989 | iterator(__res.second, this)); | |
990 | } | |
991 | ||
992 | std::pair<const_iterator, const_iterator> | |
993 | equal_range(const key_type& __key) const | |
994 | { | |
afe96d41 FD |
995 | std::pair<_Base_const_iterator, _Base_const_iterator> |
996 | __res = _Base::equal_range(__key); | |
ced3cb9f PC |
997 | return std::make_pair(const_iterator(__res.first, this), |
998 | const_iterator(__res.second, this)); | |
999 | } | |
1000 | ||
1001 | size_type | |
1002 | erase(const key_type& __key) | |
1003 | { | |
1004 | size_type __ret(0); | |
d3b8263e FD |
1005 | std::pair<_Base_iterator, _Base_iterator> __pair = |
1006 | _Base::equal_range(__key); | |
1007 | for (_Base_iterator __victim = __pair.first; __victim != __pair.second;) | |
ced3cb9f | 1008 | { |
77e0bf4e FD |
1009 | this->_M_invalidate_if([__victim](_Base_const_iterator __it) |
1010 | { return __it == __victim; }); | |
77e0bf4e | 1011 | this->_M_invalidate_local_if( |
5b3be7cf | 1012 | [__victim](_Base_const_local_iterator __it) |
92e16228 | 1013 | { return __it._M_curr() == __victim._M_cur; }); |
d3b8263e FD |
1014 | _Base::erase(__victim++); |
1015 | ++__ret; | |
ced3cb9f PC |
1016 | } |
1017 | return __ret; | |
1018 | } | |
1019 | ||
d723ced2 | 1020 | iterator |
ced3cb9f PC |
1021 | erase(const_iterator __it) |
1022 | { | |
1023 | __glibcxx_check_erase(__it); | |
77e0bf4e FD |
1024 | _Base_const_iterator __victim = __it.base(); |
1025 | this->_M_invalidate_if([__victim](_Base_const_iterator __it) | |
1026 | { return __it == __victim; }); | |
77e0bf4e | 1027 | this->_M_invalidate_local_if( |
5b3be7cf | 1028 | [__victim](_Base_const_local_iterator __it) |
92e16228 | 1029 | { return __it._M_curr() == __victim._M_cur; }); |
d723ced2 | 1030 | return iterator(_Base::erase(__it.base()), this); |
ced3cb9f PC |
1031 | } |
1032 | ||
6dc88283 PC |
1033 | iterator |
1034 | erase(iterator __it) | |
1035 | { return erase(const_iterator(__it)); } | |
1036 | ||
d723ced2 | 1037 | iterator |
ced3cb9f PC |
1038 | erase(const_iterator __first, const_iterator __last) |
1039 | { | |
1040 | __glibcxx_check_erase_range(__first, __last); | |
afe96d41 FD |
1041 | for (_Base_const_iterator __tmp = __first.base(); |
1042 | __tmp != __last.base(); ++__tmp) | |
1043 | { | |
1044 | _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(), | |
1045 | _M_message(__gnu_debug::__msg_valid_range) | |
1046 | ._M_iterator(__first, "first") | |
1047 | ._M_iterator(__last, "last")); | |
77e0bf4e FD |
1048 | this->_M_invalidate_if([__tmp](_Base_const_iterator __it) |
1049 | { return __it == __tmp; }); | |
77e0bf4e | 1050 | this->_M_invalidate_local_if( |
5b3be7cf | 1051 | [__tmp](_Base_const_local_iterator __it) |
92e16228 | 1052 | { return __it._M_curr() == __tmp._M_cur; }); |
afe96d41 | 1053 | } |
d723ced2 PC |
1054 | return iterator(_Base::erase(__first.base(), |
1055 | __last.base()), this); | |
ced3cb9f PC |
1056 | } |
1057 | ||
1058 | _Base& | |
15ee1a77 | 1059 | _M_base() noexcept { return *this; } |
ced3cb9f PC |
1060 | |
1061 | const _Base& | |
15ee1a77 | 1062 | _M_base() const noexcept { return *this; } |
ced3cb9f | 1063 | |
69b3331e | 1064 | private: |
77e0bf4e FD |
1065 | void |
1066 | _M_check_rehashed(size_type __prev_count) | |
1067 | { | |
1068 | if (__prev_count != this->bucket_count()) | |
15ee1a77 | 1069 | this->_M_invalidate_locals(); |
69b3331e | 1070 | } |
e63637ea BK |
1071 | }; |
1072 | ||
957f5fea VV |
1073 | #if __cpp_deduction_guides >= 201606 |
1074 | ||
1075 | template<typename _InputIterator, | |
1076 | typename _Hash = | |
1077 | hash<typename iterator_traits<_InputIterator>::value_type>, | |
1078 | typename _Pred = | |
1079 | equal_to<typename iterator_traits<_InputIterator>::value_type>, | |
1080 | typename _Allocator = | |
1081 | allocator<typename iterator_traits<_InputIterator>::value_type>, | |
1082 | typename = _RequireInputIter<_InputIterator>, | |
1083 | typename = _RequireAllocator<_Allocator>> | |
1084 | unordered_multiset(_InputIterator, _InputIterator, | |
1085 | unordered_multiset<int>::size_type = {}, | |
1086 | _Hash = _Hash(), _Pred = _Pred(), | |
1087 | _Allocator = _Allocator()) | |
1088 | -> unordered_multiset<typename iterator_traits<_InputIterator>::value_type, | |
1089 | _Hash, _Pred, _Allocator>; | |
1090 | ||
1091 | template<typename _Tp, typename _Hash = hash<_Tp>, | |
1092 | typename _Pred = equal_to<_Tp>, | |
1093 | typename _Allocator = allocator<_Tp>, | |
1094 | typename = _RequireAllocator<_Allocator>> | |
1095 | unordered_multiset(initializer_list<_Tp>, | |
1096 | unordered_multiset<int>::size_type = {}, | |
1097 | _Hash = _Hash(), _Pred = _Pred(), | |
1098 | _Allocator = _Allocator()) | |
1099 | -> unordered_multiset<_Tp, _Hash, _Pred, _Allocator>; | |
1100 | ||
1101 | template<typename _InputIterator, typename _Allocator, | |
1102 | typename = _RequireInputIter<_InputIterator>, | |
1103 | typename = _RequireAllocator<_Allocator>> | |
1104 | unordered_multiset(_InputIterator, _InputIterator, | |
1105 | unordered_multiset<int>::size_type, _Allocator) | |
1106 | -> unordered_multiset<typename iterator_traits<_InputIterator>::value_type, | |
1107 | hash<typename | |
1108 | iterator_traits<_InputIterator>::value_type>, | |
1109 | equal_to<typename | |
1110 | iterator_traits<_InputIterator>::value_type>, | |
1111 | _Allocator>; | |
1112 | ||
1113 | template<typename _InputIterator, typename _Hash, typename _Allocator, | |
1114 | typename = _RequireInputIter<_InputIterator>, | |
1115 | typename = _RequireAllocator<_Allocator>> | |
1116 | unordered_multiset(_InputIterator, _InputIterator, | |
1117 | unordered_multiset<int>::size_type, | |
1118 | _Hash, _Allocator) | |
1119 | -> unordered_multiset<typename | |
1120 | iterator_traits<_InputIterator>::value_type, | |
1121 | _Hash, | |
1122 | equal_to< | |
1123 | typename | |
1124 | iterator_traits<_InputIterator>::value_type>, | |
1125 | _Allocator>; | |
1126 | ||
1127 | template<typename _Tp, typename _Allocator, | |
1128 | typename = _RequireAllocator<_Allocator>> | |
1129 | unordered_multiset(initializer_list<_Tp>, | |
1130 | unordered_multiset<int>::size_type, _Allocator) | |
1131 | -> unordered_multiset<_Tp, hash<_Tp>, equal_to<_Tp>, _Allocator>; | |
1132 | ||
1133 | template<typename _Tp, typename _Hash, typename _Allocator, | |
1134 | typename = _RequireAllocator<_Allocator>> | |
1135 | unordered_multiset(initializer_list<_Tp>, | |
1136 | unordered_multiset<int>::size_type, _Hash, _Allocator) | |
1137 | -> unordered_multiset<_Tp, _Hash, equal_to<_Tp>, _Allocator>; | |
1138 | ||
1139 | #endif | |
1140 | ||
e63637ea | 1141 | template<typename _Value, typename _Hash, typename _Pred, typename _Alloc> |
69b3331e PC |
1142 | inline void |
1143 | swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, | |
1144 | unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) | |
c5d9ec56 | 1145 | noexcept(noexcept(__x.swap(__y))) |
69b3331e | 1146 | { __x.swap(__y); } |
e63637ea | 1147 | |
5dc22714 PC |
1148 | template<typename _Value, typename _Hash, typename _Pred, typename _Alloc> |
1149 | inline bool | |
1150 | operator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, | |
1151 | const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) | |
637fd8b3 | 1152 | { return __x._M_base() == __y._M_base(); } |
5dc22714 PC |
1153 | |
1154 | template<typename _Value, typename _Hash, typename _Pred, typename _Alloc> | |
1155 | inline bool | |
1156 | operator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, | |
1157 | const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) | |
1158 | { return !(__x == __y); } | |
1159 | ||
e63637ea BK |
1160 | } // namespace __debug |
1161 | } // namespace std | |
1162 | ||
734f5023 | 1163 | #endif // C++11 |
c878d6ba | 1164 | |
e63637ea | 1165 | #endif |