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