]>
Commit | Line | Data |
---|---|---|
e63637ea BK |
1 | // Debugging unordered_set/unordered_multiset implementation -*- C++ -*- |
2 | ||
818ab71a | 3 | // Copyright (C) 2003-2016 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 | ||
373 | iterator | |
374 | find(const key_type& __key) | |
375 | { return iterator(_Base::find(__key), this); } | |
376 | ||
377 | const_iterator | |
378 | find(const key_type& __key) const | |
379 | { return const_iterator(_Base::find(__key), this); } | |
380 | ||
381 | std::pair<iterator, iterator> | |
382 | equal_range(const key_type& __key) | |
383 | { | |
15ee1a77 FD |
384 | std::pair<_Base_iterator, _Base_iterator> __res |
385 | = _Base::equal_range(__key); | |
ced3cb9f PC |
386 | return std::make_pair(iterator(__res.first, this), |
387 | iterator(__res.second, this)); | |
388 | } | |
389 | ||
390 | std::pair<const_iterator, const_iterator> | |
391 | equal_range(const key_type& __key) const | |
392 | { | |
afe96d41 FD |
393 | std::pair<_Base_const_iterator, _Base_const_iterator> |
394 | __res = _Base::equal_range(__key); | |
ced3cb9f PC |
395 | return std::make_pair(const_iterator(__res.first, this), |
396 | const_iterator(__res.second, this)); | |
397 | } | |
398 | ||
399 | size_type | |
400 | erase(const key_type& __key) | |
401 | { | |
402 | size_type __ret(0); | |
afe96d41 FD |
403 | _Base_iterator __victim(_Base::find(__key)); |
404 | if (__victim != _Base::end()) | |
ced3cb9f | 405 | { |
77e0bf4e FD |
406 | this->_M_invalidate_if( |
407 | [__victim](_Base_const_iterator __it) | |
408 | { return __it == __victim; }); | |
77e0bf4e | 409 | this->_M_invalidate_local_if( |
5b3be7cf | 410 | [__victim](_Base_const_local_iterator __it) |
92e16228 | 411 | { return __it._M_curr() == __victim._M_cur; }); |
77e0bf4e | 412 | size_type __bucket_count = this->bucket_count(); |
afe96d41 | 413 | _Base::erase(__victim); |
77e0bf4e | 414 | _M_check_rehashed(__bucket_count); |
ced3cb9f PC |
415 | __ret = 1; |
416 | } | |
417 | return __ret; | |
418 | } | |
419 | ||
d723ced2 | 420 | iterator |
ced3cb9f PC |
421 | erase(const_iterator __it) |
422 | { | |
423 | __glibcxx_check_erase(__it); | |
77e0bf4e FD |
424 | _Base_const_iterator __victim = __it.base(); |
425 | this->_M_invalidate_if( | |
426 | [__victim](_Base_const_iterator __it) | |
427 | { return __it == __victim; }); | |
77e0bf4e | 428 | this->_M_invalidate_local_if( |
5b3be7cf | 429 | [__victim](_Base_const_local_iterator __it) |
92e16228 | 430 | { return __it._M_curr() == __victim._M_cur; }); |
77e0bf4e FD |
431 | size_type __bucket_count = this->bucket_count(); |
432 | _Base_iterator __next = _Base::erase(__it.base()); | |
433 | _M_check_rehashed(__bucket_count); | |
434 | return iterator(__next, this); | |
ced3cb9f PC |
435 | } |
436 | ||
6dc88283 PC |
437 | iterator |
438 | erase(iterator __it) | |
439 | { return erase(const_iterator(__it)); } | |
440 | ||
d723ced2 | 441 | iterator |
ced3cb9f PC |
442 | erase(const_iterator __first, const_iterator __last) |
443 | { | |
444 | __glibcxx_check_erase_range(__first, __last); | |
afe96d41 FD |
445 | for (_Base_const_iterator __tmp = __first.base(); |
446 | __tmp != __last.base(); ++__tmp) | |
447 | { | |
448 | _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(), | |
449 | _M_message(__gnu_debug::__msg_valid_range) | |
450 | ._M_iterator(__first, "first") | |
451 | ._M_iterator(__last, "last")); | |
77e0bf4e FD |
452 | this->_M_invalidate_if( |
453 | [__tmp](_Base_const_iterator __it) | |
454 | { return __it == __tmp; }); | |
77e0bf4e | 455 | this->_M_invalidate_local_if( |
5b3be7cf | 456 | [__tmp](_Base_const_local_iterator __it) |
92e16228 | 457 | { return __it._M_curr() == __tmp._M_cur; }); |
afe96d41 | 458 | } |
77e0bf4e FD |
459 | size_type __bucket_count = this->bucket_count(); |
460 | _Base_iterator __next = _Base::erase(__first.base(), | |
461 | __last.base()); | |
462 | _M_check_rehashed(__bucket_count); | |
463 | return iterator(__next, this); | |
ced3cb9f PC |
464 | } |
465 | ||
466 | _Base& | |
15ee1a77 | 467 | _M_base() noexcept { return *this; } |
ced3cb9f PC |
468 | |
469 | const _Base& | |
d3677132 | 470 | _M_base() const noexcept { return *this; } |
ced3cb9f | 471 | |
69b3331e | 472 | private: |
77e0bf4e FD |
473 | void |
474 | _M_check_rehashed(size_type __prev_count) | |
475 | { | |
476 | if (__prev_count != this->bucket_count()) | |
15ee1a77 | 477 | this->_M_invalidate_locals(); |
69b3331e | 478 | } |
e63637ea BK |
479 | }; |
480 | ||
481 | template<typename _Value, typename _Hash, typename _Pred, typename _Alloc> | |
69b3331e PC |
482 | inline void |
483 | swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, | |
484 | unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) | |
c5d9ec56 | 485 | noexcept(noexcept(__x.swap(__y))) |
69b3331e | 486 | { __x.swap(__y); } |
e63637ea | 487 | |
5dc22714 PC |
488 | template<typename _Value, typename _Hash, typename _Pred, typename _Alloc> |
489 | inline bool | |
490 | operator==(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, | |
491 | const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) | |
637fd8b3 | 492 | { return __x._M_base() == __y._M_base(); } |
5dc22714 PC |
493 | |
494 | template<typename _Value, typename _Hash, typename _Pred, typename _Alloc> | |
495 | inline bool | |
496 | operator!=(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, | |
497 | const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) | |
498 | { return !(__x == __y); } | |
499 | ||
e63637ea | 500 | |
1ceb9e06 | 501 | /// Class std::unordered_multiset with safety/checking/debug instrumentation. |
e63637ea | 502 | template<typename _Value, |
ced3cb9f | 503 | typename _Hash = std::hash<_Value>, |
e63637ea | 504 | typename _Pred = std::equal_to<_Value>, |
ced3cb9f | 505 | typename _Alloc = std::allocator<_Value> > |
e63637ea | 506 | class unordered_multiset |
15ee1a77 FD |
507 | : public __gnu_debug::_Safe_container< |
508 | unordered_multiset<_Value, _Hash, _Pred, _Alloc>, _Alloc, | |
509 | __gnu_debug::_Safe_unordered_container>, | |
510 | public _GLIBCXX_STD_C::unordered_multiset<_Value, _Hash, _Pred, _Alloc> | |
e63637ea | 511 | { |
15ee1a77 FD |
512 | typedef _GLIBCXX_STD_C::unordered_multiset< |
513 | _Value, _Hash, _Pred, _Alloc> _Base; | |
514 | typedef __gnu_debug::_Safe_container<unordered_multiset, | |
515 | _Alloc, __gnu_debug::_Safe_unordered_container> _Safe; | |
516 | typedef typename _Base::const_iterator _Base_const_iterator; | |
517 | typedef typename _Base::iterator _Base_iterator; | |
518 | typedef typename _Base::const_local_iterator | |
519 | _Base_const_local_iterator; | |
520 | typedef typename _Base::local_iterator _Base_local_iterator; | |
0462b6aa | 521 | |
e63637ea | 522 | public: |
15ee1a77 FD |
523 | typedef typename _Base::size_type size_type; |
524 | typedef typename _Base::hasher hasher; | |
525 | typedef typename _Base::key_equal key_equal; | |
526 | typedef typename _Base::allocator_type allocator_type; | |
527 | ||
528 | typedef typename _Base::key_type key_type; | |
529 | typedef typename _Base::value_type value_type; | |
530 | ||
531 | typedef __gnu_debug::_Safe_iterator< | |
532 | _Base_iterator, unordered_multiset> iterator; | |
533 | typedef __gnu_debug::_Safe_iterator< | |
534 | _Base_const_iterator, unordered_multiset> const_iterator; | |
77e0bf4e | 535 | typedef __gnu_debug::_Safe_local_iterator< |
15ee1a77 | 536 | _Base_local_iterator, unordered_multiset> local_iterator; |
77e0bf4e FD |
537 | typedef __gnu_debug::_Safe_local_iterator< |
538 | _Base_const_local_iterator, unordered_multiset> const_local_iterator; | |
e63637ea | 539 | |
da27f556 FD |
540 | unordered_multiset() = default; |
541 | ||
e63637ea | 542 | explicit |
da27f556 | 543 | unordered_multiset(size_type __n, |
ced3cb9f PC |
544 | const hasher& __hf = hasher(), |
545 | const key_equal& __eql = key_equal(), | |
546 | const allocator_type& __a = allocator_type()) | |
547 | : _Base(__n, __hf, __eql, __a) { } | |
e63637ea BK |
548 | |
549 | template<typename _InputIterator> | |
15ee1a77 | 550 | unordered_multiset(_InputIterator __first, _InputIterator __last, |
417e896e | 551 | size_type __n = 0, |
15ee1a77 FD |
552 | const hasher& __hf = hasher(), |
553 | const key_equal& __eql = key_equal(), | |
ced3cb9f | 554 | const allocator_type& __a = allocator_type()) |
1f5ca1a1 PC |
555 | : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first, |
556 | __last)), | |
557 | __gnu_debug::__base(__last), __n, | |
4c2d93db | 558 | __hf, __eql, __a) { } |
ced3cb9f | 559 | |
0462b6aa | 560 | unordered_multiset(const unordered_multiset&) = default; |
ced3cb9f | 561 | |
15ee1a77 | 562 | unordered_multiset(const _Base& __x) |
4c2d93db | 563 | : _Base(__x) { } |
ced3cb9f | 564 | |
0462b6aa FD |
565 | unordered_multiset(unordered_multiset&&) = default; |
566 | ||
567 | explicit | |
568 | unordered_multiset(const allocator_type& __a) | |
15ee1a77 | 569 | : _Base(__a) { } |
0462b6aa FD |
570 | |
571 | unordered_multiset(const unordered_multiset& __uset, | |
572 | const allocator_type& __a) | |
15ee1a77 FD |
573 | : _Base(__uset, __a) { } |
574 | ||
0462b6aa FD |
575 | unordered_multiset(unordered_multiset&& __uset, |
576 | const allocator_type& __a) | |
15ee1a77 FD |
577 | : _Safe(std::move(__uset._M_safe()), __a), |
578 | _Base(std::move(__uset._M_base()), __a) { } | |
e63637ea | 579 | |
988499f4 | 580 | unordered_multiset(initializer_list<value_type> __l, |
417e896e | 581 | size_type __n = 0, |
988499f4 JM |
582 | const hasher& __hf = hasher(), |
583 | const key_equal& __eql = key_equal(), | |
584 | const allocator_type& __a = allocator_type()) | |
4c2d93db | 585 | : _Base(__l, __n, __hf, __eql, __a) { } |
e63637ea | 586 | |
e55b80f5 FD |
587 | unordered_multiset(size_type __n, const allocator_type& __a) |
588 | : unordered_multiset(__n, hasher(), key_equal(), __a) | |
589 | { } | |
590 | ||
591 | unordered_multiset(size_type __n, const hasher& __hf, | |
592 | const allocator_type& __a) | |
593 | : unordered_multiset(__n, __hf, key_equal(), __a) | |
594 | { } | |
595 | ||
596 | template<typename _InputIterator> | |
597 | unordered_multiset(_InputIterator __first, _InputIterator __last, | |
598 | size_type __n, | |
599 | const allocator_type& __a) | |
600 | : unordered_multiset(__first, __last, __n, hasher(), key_equal(), __a) | |
601 | { } | |
602 | ||
603 | template<typename _InputIterator> | |
604 | unordered_multiset(_InputIterator __first, _InputIterator __last, | |
605 | size_type __n, const hasher& __hf, | |
606 | const allocator_type& __a) | |
607 | : unordered_multiset(__first, __last, __n, __hf, key_equal(), __a) | |
608 | { } | |
609 | ||
610 | unordered_multiset(initializer_list<value_type> __l, | |
611 | size_type __n, | |
612 | const allocator_type& __a) | |
613 | : unordered_multiset(__l, __n, hasher(), key_equal(), __a) | |
614 | { } | |
615 | ||
616 | unordered_multiset(initializer_list<value_type> __l, | |
617 | size_type __n, const hasher& __hf, | |
618 | const allocator_type& __a) | |
619 | : unordered_multiset(__l, __n, __hf, key_equal(), __a) | |
620 | { } | |
621 | ||
15ee1a77 | 622 | ~unordered_multiset() = default; |
6f59ea25 | 623 | |
ced3cb9f | 624 | unordered_multiset& |
15ee1a77 | 625 | operator=(const unordered_multiset&) = default; |
69b3331e PC |
626 | |
627 | unordered_multiset& | |
15ee1a77 | 628 | operator=(unordered_multiset&&) = default; |
69b3331e | 629 | |
988499f4 JM |
630 | unordered_multiset& |
631 | operator=(initializer_list<value_type> __l) | |
632 | { | |
15ee1a77 | 633 | this->_M_base() = __l; |
0462b6aa | 634 | this->_M_invalidate_all(); |
988499f4 JM |
635 | return *this; |
636 | } | |
637 | ||
e63637ea | 638 | void |
ff74fd13 | 639 | swap(unordered_multiset& __x) |
c5d9ec56 | 640 | noexcept( noexcept(declval<_Base&>().swap(__x)) ) |
e63637ea | 641 | { |
15ee1a77 | 642 | _Safe::_M_swap(__x); |
ced3cb9f | 643 | _Base::swap(__x); |
e63637ea | 644 | } |
69b3331e | 645 | |
ced3cb9f | 646 | void |
d3677132 | 647 | clear() noexcept |
69b3331e PC |
648 | { |
649 | _Base::clear(); | |
650 | this->_M_invalidate_all(); | |
651 | } | |
652 | ||
ced3cb9f | 653 | iterator |
d3677132 | 654 | begin() noexcept |
ced3cb9f PC |
655 | { return iterator(_Base::begin(), this); } |
656 | ||
657 | const_iterator | |
d3677132 | 658 | begin() const noexcept |
ced3cb9f PC |
659 | { return const_iterator(_Base::begin(), this); } |
660 | ||
661 | iterator | |
d3677132 | 662 | end() noexcept |
ced3cb9f PC |
663 | { return iterator(_Base::end(), this); } |
664 | ||
665 | const_iterator | |
d3677132 | 666 | end() const noexcept |
ced3cb9f PC |
667 | { return const_iterator(_Base::end(), this); } |
668 | ||
669 | const_iterator | |
d3677132 | 670 | cbegin() const noexcept |
ced3cb9f PC |
671 | { return const_iterator(_Base::begin(), this); } |
672 | ||
673 | const_iterator | |
d3677132 | 674 | cend() const noexcept |
ced3cb9f PC |
675 | { return const_iterator(_Base::end(), this); } |
676 | ||
677 | // local versions | |
77e0bf4e FD |
678 | local_iterator |
679 | begin(size_type __b) | |
7181e991 FD |
680 | { |
681 | __glibcxx_check_bucket_index(__b); | |
2e5189c8 | 682 | return local_iterator(_Base::begin(__b), this); |
7181e991 | 683 | } |
77e0bf4e FD |
684 | |
685 | local_iterator | |
686 | end(size_type __b) | |
7181e991 FD |
687 | { |
688 | __glibcxx_check_bucket_index(__b); | |
2e5189c8 | 689 | return local_iterator(_Base::end(__b), this); |
7181e991 | 690 | } |
77e0bf4e FD |
691 | |
692 | const_local_iterator | |
693 | begin(size_type __b) const | |
7181e991 FD |
694 | { |
695 | __glibcxx_check_bucket_index(__b); | |
2e5189c8 | 696 | return const_local_iterator(_Base::begin(__b), this); |
7181e991 | 697 | } |
77e0bf4e FD |
698 | |
699 | const_local_iterator | |
700 | end(size_type __b) const | |
7181e991 FD |
701 | { |
702 | __glibcxx_check_bucket_index(__b); | |
2e5189c8 | 703 | return const_local_iterator(_Base::end(__b), this); |
7181e991 | 704 | } |
77e0bf4e FD |
705 | |
706 | const_local_iterator | |
707 | cbegin(size_type __b) const | |
7181e991 FD |
708 | { |
709 | __glibcxx_check_bucket_index(__b); | |
2e5189c8 | 710 | return const_local_iterator(_Base::cbegin(__b), this); |
7181e991 | 711 | } |
77e0bf4e FD |
712 | |
713 | const_local_iterator | |
714 | cend(size_type __b) const | |
7181e991 FD |
715 | { |
716 | __glibcxx_check_bucket_index(__b); | |
2e5189c8 | 717 | return const_local_iterator(_Base::cend(__b), this); |
7181e991 FD |
718 | } |
719 | ||
720 | size_type | |
721 | bucket_size(size_type __b) const | |
722 | { | |
723 | __glibcxx_check_bucket_index(__b); | |
724 | return _Base::bucket_size(__b); | |
725 | } | |
14cbb5d8 FD |
726 | |
727 | float | |
728 | max_load_factor() const noexcept | |
729 | { return _Base::max_load_factor(); } | |
730 | ||
731 | void | |
732 | max_load_factor(float __f) | |
733 | { | |
734 | __glibcxx_check_max_load_factor(__f); | |
735 | _Base::max_load_factor(__f); | |
736 | } | |
ced3cb9f | 737 | |
9b81593b FD |
738 | template<typename... _Args> |
739 | iterator | |
740 | emplace(_Args&&... __args) | |
741 | { | |
742 | size_type __bucket_count = this->bucket_count(); | |
743 | _Base_iterator __it | |
744 | = _Base::emplace(std::forward<_Args>(__args)...); | |
745 | _M_check_rehashed(__bucket_count); | |
746 | return iterator(__it, this); | |
747 | } | |
748 | ||
749 | template<typename... _Args> | |
750 | iterator | |
751 | emplace_hint(const_iterator __hint, _Args&&... __args) | |
752 | { | |
753 | __glibcxx_check_insert(__hint); | |
754 | size_type __bucket_count = this->bucket_count(); | |
755 | _Base_iterator __it = _Base::emplace_hint(__hint.base(), | |
756 | std::forward<_Args>(__args)...); | |
757 | _M_check_rehashed(__bucket_count); | |
758 | return iterator(__it, this); | |
759 | } | |
760 | ||
ced3cb9f PC |
761 | iterator |
762 | insert(const value_type& __obj) | |
77e0bf4e FD |
763 | { |
764 | size_type __bucket_count = this->bucket_count(); | |
765 | _Base_iterator __it = _Base::insert(__obj); | |
766 | _M_check_rehashed(__bucket_count); | |
767 | return iterator(__it, this); | |
768 | } | |
ced3cb9f PC |
769 | |
770 | iterator | |
d66411ba FD |
771 | insert(const_iterator __hint, const value_type& __obj) |
772 | { | |
773 | __glibcxx_check_insert(__hint); | |
77e0bf4e | 774 | size_type __bucket_count = this->bucket_count(); |
15ee1a77 | 775 | _Base_iterator __it = _Base::insert(__hint.base(), __obj); |
77e0bf4e FD |
776 | _M_check_rehashed(__bucket_count); |
777 | return iterator(__it, this); | |
d66411ba | 778 | } |
ced3cb9f | 779 | |
fb7342fd PC |
780 | iterator |
781 | insert(value_type&& __obj) | |
77e0bf4e FD |
782 | { |
783 | size_type __bucket_count = this->bucket_count(); | |
15ee1a77 | 784 | _Base_iterator __it = _Base::insert(std::move(__obj)); |
77e0bf4e FD |
785 | _M_check_rehashed(__bucket_count); |
786 | return iterator(__it, this); | |
787 | } | |
fb7342fd PC |
788 | |
789 | iterator | |
d66411ba FD |
790 | insert(const_iterator __hint, value_type&& __obj) |
791 | { | |
792 | __glibcxx_check_insert(__hint); | |
77e0bf4e | 793 | size_type __bucket_count = this->bucket_count(); |
15ee1a77 | 794 | _Base_iterator __it = _Base::insert(__hint.base(), std::move(__obj)); |
77e0bf4e FD |
795 | _M_check_rehashed(__bucket_count); |
796 | return iterator(__it, this); | |
d66411ba | 797 | } |
fb7342fd | 798 | |
ced3cb9f PC |
799 | void |
800 | insert(std::initializer_list<value_type> __l) | |
77e0bf4e FD |
801 | { |
802 | size_type __bucket_count = this->bucket_count(); | |
803 | _Base::insert(__l); | |
804 | _M_check_rehashed(__bucket_count); | |
805 | } | |
ced3cb9f PC |
806 | |
807 | template<typename _InputIterator> | |
77e0bf4e FD |
808 | void |
809 | insert(_InputIterator __first, _InputIterator __last) | |
810 | { | |
24167c42 FD |
811 | typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist; |
812 | __glibcxx_check_valid_range2(__first, __last, __dist); | |
77e0bf4e | 813 | size_type __bucket_count = this->bucket_count(); |
24167c42 FD |
814 | |
815 | if (__dist.second >= __gnu_debug::__dp_sign) | |
816 | _Base::insert(__gnu_debug::__unsafe(__first), | |
817 | __gnu_debug::__unsafe(__last)); | |
818 | else | |
819 | _Base::insert(__first, __last); | |
820 | ||
77e0bf4e | 821 | _M_check_rehashed(__bucket_count); |
ced3cb9f PC |
822 | } |
823 | ||
824 | iterator | |
825 | find(const key_type& __key) | |
826 | { return iterator(_Base::find(__key), this); } | |
827 | ||
828 | const_iterator | |
829 | find(const key_type& __key) const | |
830 | { return const_iterator(_Base::find(__key), this); } | |
831 | ||
832 | std::pair<iterator, iterator> | |
833 | equal_range(const key_type& __key) | |
834 | { | |
15ee1a77 FD |
835 | std::pair<_Base_iterator, _Base_iterator> __res |
836 | = _Base::equal_range(__key); | |
ced3cb9f PC |
837 | return std::make_pair(iterator(__res.first, this), |
838 | iterator(__res.second, this)); | |
839 | } | |
840 | ||
841 | std::pair<const_iterator, const_iterator> | |
842 | equal_range(const key_type& __key) const | |
843 | { | |
afe96d41 FD |
844 | std::pair<_Base_const_iterator, _Base_const_iterator> |
845 | __res = _Base::equal_range(__key); | |
ced3cb9f PC |
846 | return std::make_pair(const_iterator(__res.first, this), |
847 | const_iterator(__res.second, this)); | |
848 | } | |
849 | ||
850 | size_type | |
851 | erase(const key_type& __key) | |
852 | { | |
853 | size_type __ret(0); | |
d3b8263e FD |
854 | std::pair<_Base_iterator, _Base_iterator> __pair = |
855 | _Base::equal_range(__key); | |
856 | for (_Base_iterator __victim = __pair.first; __victim != __pair.second;) | |
ced3cb9f | 857 | { |
77e0bf4e FD |
858 | this->_M_invalidate_if([__victim](_Base_const_iterator __it) |
859 | { return __it == __victim; }); | |
77e0bf4e | 860 | this->_M_invalidate_local_if( |
5b3be7cf | 861 | [__victim](_Base_const_local_iterator __it) |
92e16228 | 862 | { return __it._M_curr() == __victim._M_cur; }); |
d3b8263e FD |
863 | _Base::erase(__victim++); |
864 | ++__ret; | |
ced3cb9f PC |
865 | } |
866 | return __ret; | |
867 | } | |
868 | ||
d723ced2 | 869 | iterator |
ced3cb9f PC |
870 | erase(const_iterator __it) |
871 | { | |
872 | __glibcxx_check_erase(__it); | |
77e0bf4e FD |
873 | _Base_const_iterator __victim = __it.base(); |
874 | this->_M_invalidate_if([__victim](_Base_const_iterator __it) | |
875 | { return __it == __victim; }); | |
77e0bf4e | 876 | this->_M_invalidate_local_if( |
5b3be7cf | 877 | [__victim](_Base_const_local_iterator __it) |
92e16228 | 878 | { return __it._M_curr() == __victim._M_cur; }); |
d723ced2 | 879 | return iterator(_Base::erase(__it.base()), this); |
ced3cb9f PC |
880 | } |
881 | ||
6dc88283 PC |
882 | iterator |
883 | erase(iterator __it) | |
884 | { return erase(const_iterator(__it)); } | |
885 | ||
d723ced2 | 886 | iterator |
ced3cb9f PC |
887 | erase(const_iterator __first, const_iterator __last) |
888 | { | |
889 | __glibcxx_check_erase_range(__first, __last); | |
afe96d41 FD |
890 | for (_Base_const_iterator __tmp = __first.base(); |
891 | __tmp != __last.base(); ++__tmp) | |
892 | { | |
893 | _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(), | |
894 | _M_message(__gnu_debug::__msg_valid_range) | |
895 | ._M_iterator(__first, "first") | |
896 | ._M_iterator(__last, "last")); | |
77e0bf4e FD |
897 | this->_M_invalidate_if([__tmp](_Base_const_iterator __it) |
898 | { return __it == __tmp; }); | |
77e0bf4e | 899 | this->_M_invalidate_local_if( |
5b3be7cf | 900 | [__tmp](_Base_const_local_iterator __it) |
92e16228 | 901 | { return __it._M_curr() == __tmp._M_cur; }); |
afe96d41 | 902 | } |
d723ced2 PC |
903 | return iterator(_Base::erase(__first.base(), |
904 | __last.base()), this); | |
ced3cb9f PC |
905 | } |
906 | ||
907 | _Base& | |
15ee1a77 | 908 | _M_base() noexcept { return *this; } |
ced3cb9f PC |
909 | |
910 | const _Base& | |
15ee1a77 | 911 | _M_base() const noexcept { return *this; } |
ced3cb9f | 912 | |
69b3331e | 913 | private: |
77e0bf4e FD |
914 | void |
915 | _M_check_rehashed(size_type __prev_count) | |
916 | { | |
917 | if (__prev_count != this->bucket_count()) | |
15ee1a77 | 918 | this->_M_invalidate_locals(); |
69b3331e | 919 | } |
e63637ea BK |
920 | }; |
921 | ||
922 | template<typename _Value, typename _Hash, typename _Pred, typename _Alloc> | |
69b3331e PC |
923 | inline void |
924 | swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, | |
925 | unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) | |
c5d9ec56 | 926 | noexcept(noexcept(__x.swap(__y))) |
69b3331e | 927 | { __x.swap(__y); } |
e63637ea | 928 | |
5dc22714 PC |
929 | template<typename _Value, typename _Hash, typename _Pred, typename _Alloc> |
930 | inline bool | |
931 | operator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, | |
932 | const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) | |
637fd8b3 | 933 | { return __x._M_base() == __y._M_base(); } |
5dc22714 PC |
934 | |
935 | template<typename _Value, typename _Hash, typename _Pred, typename _Alloc> | |
936 | inline bool | |
937 | operator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, | |
938 | const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) | |
939 | { return !(__x == __y); } | |
940 | ||
e63637ea BK |
941 | } // namespace __debug |
942 | } // namespace std | |
943 | ||
734f5023 | 944 | #endif // C++11 |
c878d6ba | 945 | |
e63637ea | 946 | #endif |