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