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