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