libstdc++
|
00001 // Debugging unordered_set/unordered_multiset implementation -*- C++ -*- 00002 00003 // Copyright (C) 2003-2015 Free Software Foundation, Inc. 00004 // 00005 // This file is part of the GNU ISO C++ Library. This library is free 00006 // software; you can redistribute it and/or modify it under the 00007 // terms of the GNU General Public License as published by the 00008 // Free Software Foundation; either version 3, or (at your option) 00009 // any later version. 00010 00011 // This library is distributed in the hope that it will be useful, 00012 // but WITHOUT ANY WARRANTY; without even the implied warranty of 00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00014 // GNU General Public License for more details. 00015 00016 // Under Section 7 of GPL version 3, you are granted additional 00017 // permissions described in the GCC Runtime Library Exception, version 00018 // 3.1, as published by the Free Software Foundation. 00019 00020 // You should have received a copy of the GNU General Public License and 00021 // a copy of the GCC Runtime Library Exception along with this program; 00022 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 00023 // <http://www.gnu.org/licenses/>. 00024 00025 /** @file debug/unordered_set 00026 * This file is a GNU debug extension to the Standard C++ Library. 00027 */ 00028 00029 #ifndef _GLIBCXX_DEBUG_UNORDERED_SET 00030 #define _GLIBCXX_DEBUG_UNORDERED_SET 1 00031 00032 #if __cplusplus < 201103L 00033 # include <bits/c++0x_warning.h> 00034 #else 00035 # include <unordered_set> 00036 00037 #include <debug/safe_unordered_container.h> 00038 #include <debug/safe_container.h> 00039 #include <debug/safe_iterator.h> 00040 #include <debug/safe_local_iterator.h> 00041 00042 namespace std _GLIBCXX_VISIBILITY(default) 00043 { 00044 namespace __debug 00045 { 00046 /// Class std::unordered_set with safety/checking/debug instrumentation. 00047 template<typename _Value, 00048 typename _Hash = std::hash<_Value>, 00049 typename _Pred = std::equal_to<_Value>, 00050 typename _Alloc = std::allocator<_Value> > 00051 class unordered_set 00052 : public __gnu_debug::_Safe_container< 00053 unordered_set<_Value, _Hash, _Pred, _Alloc>, _Alloc, 00054 __gnu_debug::_Safe_unordered_container>, 00055 public _GLIBCXX_STD_C::unordered_set<_Value, _Hash, _Pred, _Alloc> 00056 { 00057 typedef _GLIBCXX_STD_C::unordered_set< 00058 _Value, _Hash, _Pred, _Alloc> _Base; 00059 typedef __gnu_debug::_Safe_container< 00060 unordered_set, _Alloc, __gnu_debug::_Safe_unordered_container> _Safe; 00061 00062 typedef typename _Base::const_iterator _Base_const_iterator; 00063 typedef typename _Base::iterator _Base_iterator; 00064 typedef typename _Base::const_local_iterator _Base_const_local_iterator; 00065 typedef typename _Base::local_iterator _Base_local_iterator; 00066 00067 public: 00068 typedef typename _Base::size_type size_type; 00069 typedef typename _Base::hasher hasher; 00070 typedef typename _Base::key_equal key_equal; 00071 typedef typename _Base::allocator_type allocator_type; 00072 00073 typedef typename _Base::key_type key_type; 00074 typedef typename _Base::value_type value_type; 00075 00076 typedef __gnu_debug::_Safe_iterator< 00077 _Base_iterator, unordered_set> iterator; 00078 typedef __gnu_debug::_Safe_iterator< 00079 _Base_const_iterator, unordered_set> const_iterator; 00080 typedef __gnu_debug::_Safe_local_iterator< 00081 _Base_local_iterator, unordered_set> local_iterator; 00082 typedef __gnu_debug::_Safe_local_iterator< 00083 _Base_const_local_iterator, unordered_set> const_local_iterator; 00084 00085 unordered_set() = default; 00086 00087 explicit 00088 unordered_set(size_type __n, 00089 const hasher& __hf = hasher(), 00090 const key_equal& __eql = key_equal(), 00091 const allocator_type& __a = allocator_type()) 00092 : _Base(__n, __hf, __eql, __a) { } 00093 00094 template<typename _InputIterator> 00095 unordered_set(_InputIterator __first, _InputIterator __last, 00096 size_type __n = 0, 00097 const hasher& __hf = hasher(), 00098 const key_equal& __eql = key_equal(), 00099 const allocator_type& __a = allocator_type()) 00100 : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first, 00101 __last)), 00102 __gnu_debug::__base(__last), __n, 00103 __hf, __eql, __a) { } 00104 00105 unordered_set(const unordered_set&) = default; 00106 00107 unordered_set(const _Base& __x) 00108 : _Base(__x) { } 00109 00110 unordered_set(unordered_set&&) = default; 00111 00112 explicit 00113 unordered_set(const allocator_type& __a) 00114 : _Base(__a) { } 00115 00116 unordered_set(const unordered_set& __uset, 00117 const allocator_type& __a) 00118 : _Base(__uset, __a) { } 00119 00120 unordered_set(unordered_set&& __uset, 00121 const allocator_type& __a) 00122 : _Safe(std::move(__uset._M_safe()), __a), 00123 _Base(std::move(__uset._M_base()), __a) { } 00124 00125 unordered_set(initializer_list<value_type> __l, 00126 size_type __n = 0, 00127 const hasher& __hf = hasher(), 00128 const key_equal& __eql = key_equal(), 00129 const allocator_type& __a = allocator_type()) 00130 : _Base(__l, __n, __hf, __eql, __a) { } 00131 00132 unordered_set(size_type __n, const allocator_type& __a) 00133 : unordered_set(__n, hasher(), key_equal(), __a) 00134 { } 00135 00136 unordered_set(size_type __n, const hasher& __hf, 00137 const allocator_type& __a) 00138 : unordered_set(__n, __hf, key_equal(), __a) 00139 { } 00140 00141 template<typename _InputIterator> 00142 unordered_set(_InputIterator __first, _InputIterator __last, 00143 size_type __n, 00144 const allocator_type& __a) 00145 : unordered_set(__first, __last, __n, hasher(), key_equal(), __a) 00146 { } 00147 00148 template<typename _InputIterator> 00149 unordered_set(_InputIterator __first, _InputIterator __last, 00150 size_type __n, const hasher& __hf, 00151 const allocator_type& __a) 00152 : unordered_set(__first, __last, __n, __hf, key_equal(), __a) 00153 { } 00154 00155 unordered_set(initializer_list<value_type> __l, 00156 size_type __n, 00157 const allocator_type& __a) 00158 : unordered_set(__l, __n, hasher(), key_equal(), __a) 00159 { } 00160 00161 unordered_set(initializer_list<value_type> __l, 00162 size_type __n, const hasher& __hf, 00163 const allocator_type& __a) 00164 : unordered_set(__l, __n, __hf, key_equal(), __a) 00165 { } 00166 00167 ~unordered_set() = default; 00168 00169 unordered_set& 00170 operator=(const unordered_set&) = default; 00171 00172 unordered_set& 00173 operator=(unordered_set&&) = default; 00174 00175 unordered_set& 00176 operator=(initializer_list<value_type> __l) 00177 { 00178 _M_base() = __l; 00179 this->_M_invalidate_all(); 00180 return *this; 00181 } 00182 00183 void 00184 swap(unordered_set& __x) 00185 noexcept( noexcept(declval<_Base>().swap(__x)) ) 00186 { 00187 _Safe::_M_swap(__x); 00188 _Base::swap(__x); 00189 } 00190 00191 void 00192 clear() noexcept 00193 { 00194 _Base::clear(); 00195 this->_M_invalidate_all(); 00196 } 00197 00198 iterator 00199 begin() noexcept 00200 { return iterator(_Base::begin(), this); } 00201 00202 const_iterator 00203 begin() const noexcept 00204 { return const_iterator(_Base::begin(), this); } 00205 00206 iterator 00207 end() noexcept 00208 { return iterator(_Base::end(), this); } 00209 00210 const_iterator 00211 end() const noexcept 00212 { return const_iterator(_Base::end(), this); } 00213 00214 const_iterator 00215 cbegin() const noexcept 00216 { return const_iterator(_Base::begin(), this); } 00217 00218 const_iterator 00219 cend() const noexcept 00220 { return const_iterator(_Base::end(), this); } 00221 00222 // local versions 00223 local_iterator 00224 begin(size_type __b) 00225 { 00226 __glibcxx_check_bucket_index(__b); 00227 return local_iterator(_Base::begin(__b), this); 00228 } 00229 00230 local_iterator 00231 end(size_type __b) 00232 { 00233 __glibcxx_check_bucket_index(__b); 00234 return local_iterator(_Base::end(__b), this); 00235 } 00236 00237 const_local_iterator 00238 begin(size_type __b) const 00239 { 00240 __glibcxx_check_bucket_index(__b); 00241 return const_local_iterator(_Base::begin(__b), this); 00242 } 00243 00244 const_local_iterator 00245 end(size_type __b) const 00246 { 00247 __glibcxx_check_bucket_index(__b); 00248 return const_local_iterator(_Base::end(__b), this); 00249 } 00250 00251 const_local_iterator 00252 cbegin(size_type __b) const 00253 { 00254 __glibcxx_check_bucket_index(__b); 00255 return const_local_iterator(_Base::cbegin(__b), this); 00256 } 00257 00258 const_local_iterator 00259 cend(size_type __b) const 00260 { 00261 __glibcxx_check_bucket_index(__b); 00262 return const_local_iterator(_Base::cend(__b), this); 00263 } 00264 00265 size_type 00266 bucket_size(size_type __b) const 00267 { 00268 __glibcxx_check_bucket_index(__b); 00269 return _Base::bucket_size(__b); 00270 } 00271 00272 float 00273 max_load_factor() const noexcept 00274 { return _Base::max_load_factor(); } 00275 00276 void 00277 max_load_factor(float __f) 00278 { 00279 __glibcxx_check_max_load_factor(__f); 00280 _Base::max_load_factor(__f); 00281 } 00282 00283 template<typename... _Args> 00284 std::pair<iterator, bool> 00285 emplace(_Args&&... __args) 00286 { 00287 size_type __bucket_count = this->bucket_count(); 00288 std::pair<_Base_iterator, bool> __res 00289 = _Base::emplace(std::forward<_Args>(__args)...); 00290 _M_check_rehashed(__bucket_count); 00291 return std::make_pair(iterator(__res.first, this), __res.second); 00292 } 00293 00294 template<typename... _Args> 00295 iterator 00296 emplace_hint(const_iterator __hint, _Args&&... __args) 00297 { 00298 __glibcxx_check_insert(__hint); 00299 size_type __bucket_count = this->bucket_count(); 00300 _Base_iterator __it = _Base::emplace_hint(__hint.base(), 00301 std::forward<_Args>(__args)...); 00302 _M_check_rehashed(__bucket_count); 00303 return iterator(__it, this); 00304 } 00305 00306 std::pair<iterator, bool> 00307 insert(const value_type& __obj) 00308 { 00309 size_type __bucket_count = this->bucket_count(); 00310 std::pair<_Base_iterator, bool> __res 00311 = _Base::insert(__obj); 00312 _M_check_rehashed(__bucket_count); 00313 return std::make_pair(iterator(__res.first, this), __res.second); 00314 } 00315 00316 iterator 00317 insert(const_iterator __hint, const value_type& __obj) 00318 { 00319 __glibcxx_check_insert(__hint); 00320 size_type __bucket_count = this->bucket_count(); 00321 _Base_iterator __it = _Base::insert(__hint.base(), __obj); 00322 _M_check_rehashed(__bucket_count); 00323 return iterator(__it, this); 00324 } 00325 00326 std::pair<iterator, bool> 00327 insert(value_type&& __obj) 00328 { 00329 size_type __bucket_count = this->bucket_count(); 00330 std::pair<_Base_iterator, bool> __res 00331 = _Base::insert(std::move(__obj)); 00332 _M_check_rehashed(__bucket_count); 00333 return std::make_pair(iterator(__res.first, this), __res.second); 00334 } 00335 00336 iterator 00337 insert(const_iterator __hint, value_type&& __obj) 00338 { 00339 __glibcxx_check_insert(__hint); 00340 size_type __bucket_count = this->bucket_count(); 00341 _Base_iterator __it = _Base::insert(__hint.base(), std::move(__obj)); 00342 _M_check_rehashed(__bucket_count); 00343 return iterator(__it, this); 00344 } 00345 00346 void 00347 insert(std::initializer_list<value_type> __l) 00348 { 00349 size_type __bucket_count = this->bucket_count(); 00350 _Base::insert(__l); 00351 _M_check_rehashed(__bucket_count); 00352 } 00353 00354 template<typename _InputIterator> 00355 void 00356 insert(_InputIterator __first, _InputIterator __last) 00357 { 00358 __glibcxx_check_valid_range(__first, __last); 00359 size_type __bucket_count = this->bucket_count(); 00360 _Base::insert(__gnu_debug::__base(__first), 00361 __gnu_debug::__base(__last)); 00362 _M_check_rehashed(__bucket_count); 00363 } 00364 00365 iterator 00366 find(const key_type& __key) 00367 { return iterator(_Base::find(__key), this); } 00368 00369 const_iterator 00370 find(const key_type& __key) const 00371 { return const_iterator(_Base::find(__key), this); } 00372 00373 std::pair<iterator, iterator> 00374 equal_range(const key_type& __key) 00375 { 00376 std::pair<_Base_iterator, _Base_iterator> __res 00377 = _Base::equal_range(__key); 00378 return std::make_pair(iterator(__res.first, this), 00379 iterator(__res.second, this)); 00380 } 00381 00382 std::pair<const_iterator, const_iterator> 00383 equal_range(const key_type& __key) const 00384 { 00385 std::pair<_Base_const_iterator, _Base_const_iterator> 00386 __res = _Base::equal_range(__key); 00387 return std::make_pair(const_iterator(__res.first, this), 00388 const_iterator(__res.second, this)); 00389 } 00390 00391 size_type 00392 erase(const key_type& __key) 00393 { 00394 size_type __ret(0); 00395 _Base_iterator __victim(_Base::find(__key)); 00396 if (__victim != _Base::end()) 00397 { 00398 this->_M_invalidate_if( 00399 [__victim](_Base_const_iterator __it) 00400 { return __it == __victim; }); 00401 this->_M_invalidate_local_if( 00402 [__victim](_Base_const_local_iterator __it) 00403 { return __it._M_curr() == __victim._M_cur; }); 00404 size_type __bucket_count = this->bucket_count(); 00405 _Base::erase(__victim); 00406 _M_check_rehashed(__bucket_count); 00407 __ret = 1; 00408 } 00409 return __ret; 00410 } 00411 00412 iterator 00413 erase(const_iterator __it) 00414 { 00415 __glibcxx_check_erase(__it); 00416 _Base_const_iterator __victim = __it.base(); 00417 this->_M_invalidate_if( 00418 [__victim](_Base_const_iterator __it) 00419 { return __it == __victim; }); 00420 this->_M_invalidate_local_if( 00421 [__victim](_Base_const_local_iterator __it) 00422 { return __it._M_curr() == __victim._M_cur; }); 00423 size_type __bucket_count = this->bucket_count(); 00424 _Base_iterator __next = _Base::erase(__it.base()); 00425 _M_check_rehashed(__bucket_count); 00426 return iterator(__next, this); 00427 } 00428 00429 iterator 00430 erase(iterator __it) 00431 { return erase(const_iterator(__it)); } 00432 00433 iterator 00434 erase(const_iterator __first, const_iterator __last) 00435 { 00436 __glibcxx_check_erase_range(__first, __last); 00437 for (_Base_const_iterator __tmp = __first.base(); 00438 __tmp != __last.base(); ++__tmp) 00439 { 00440 _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(), 00441 _M_message(__gnu_debug::__msg_valid_range) 00442 ._M_iterator(__first, "first") 00443 ._M_iterator(__last, "last")); 00444 this->_M_invalidate_if( 00445 [__tmp](_Base_const_iterator __it) 00446 { return __it == __tmp; }); 00447 this->_M_invalidate_local_if( 00448 [__tmp](_Base_const_local_iterator __it) 00449 { return __it._M_curr() == __tmp._M_cur; }); 00450 } 00451 size_type __bucket_count = this->bucket_count(); 00452 _Base_iterator __next = _Base::erase(__first.base(), 00453 __last.base()); 00454 _M_check_rehashed(__bucket_count); 00455 return iterator(__next, this); 00456 } 00457 00458 _Base& 00459 _M_base() noexcept { return *this; } 00460 00461 const _Base& 00462 _M_base() const noexcept { return *this; } 00463 00464 private: 00465 void 00466 _M_check_rehashed(size_type __prev_count) 00467 { 00468 if (__prev_count != this->bucket_count()) 00469 this->_M_invalidate_locals(); 00470 } 00471 }; 00472 00473 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc> 00474 inline void 00475 swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, 00476 unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) 00477 { __x.swap(__y); } 00478 00479 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc> 00480 inline bool 00481 operator==(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, 00482 const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) 00483 { return __x._M_base() == __y._M_base(); } 00484 00485 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc> 00486 inline bool 00487 operator!=(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, 00488 const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) 00489 { return !(__x == __y); } 00490 00491 00492 /// Class std::unordered_multiset with safety/checking/debug instrumentation. 00493 template<typename _Value, 00494 typename _Hash = std::hash<_Value>, 00495 typename _Pred = std::equal_to<_Value>, 00496 typename _Alloc = std::allocator<_Value> > 00497 class unordered_multiset 00498 : public __gnu_debug::_Safe_container< 00499 unordered_multiset<_Value, _Hash, _Pred, _Alloc>, _Alloc, 00500 __gnu_debug::_Safe_unordered_container>, 00501 public _GLIBCXX_STD_C::unordered_multiset<_Value, _Hash, _Pred, _Alloc> 00502 { 00503 typedef _GLIBCXX_STD_C::unordered_multiset< 00504 _Value, _Hash, _Pred, _Alloc> _Base; 00505 typedef __gnu_debug::_Safe_container<unordered_multiset, 00506 _Alloc, __gnu_debug::_Safe_unordered_container> _Safe; 00507 typedef typename _Base::const_iterator _Base_const_iterator; 00508 typedef typename _Base::iterator _Base_iterator; 00509 typedef typename _Base::const_local_iterator 00510 _Base_const_local_iterator; 00511 typedef typename _Base::local_iterator _Base_local_iterator; 00512 00513 public: 00514 typedef typename _Base::size_type size_type; 00515 typedef typename _Base::hasher hasher; 00516 typedef typename _Base::key_equal key_equal; 00517 typedef typename _Base::allocator_type allocator_type; 00518 00519 typedef typename _Base::key_type key_type; 00520 typedef typename _Base::value_type value_type; 00521 00522 typedef __gnu_debug::_Safe_iterator< 00523 _Base_iterator, unordered_multiset> iterator; 00524 typedef __gnu_debug::_Safe_iterator< 00525 _Base_const_iterator, unordered_multiset> const_iterator; 00526 typedef __gnu_debug::_Safe_local_iterator< 00527 _Base_local_iterator, unordered_multiset> local_iterator; 00528 typedef __gnu_debug::_Safe_local_iterator< 00529 _Base_const_local_iterator, unordered_multiset> const_local_iterator; 00530 00531 unordered_multiset() = default; 00532 00533 explicit 00534 unordered_multiset(size_type __n, 00535 const hasher& __hf = hasher(), 00536 const key_equal& __eql = key_equal(), 00537 const allocator_type& __a = allocator_type()) 00538 : _Base(__n, __hf, __eql, __a) { } 00539 00540 template<typename _InputIterator> 00541 unordered_multiset(_InputIterator __first, _InputIterator __last, 00542 size_type __n = 0, 00543 const hasher& __hf = hasher(), 00544 const key_equal& __eql = key_equal(), 00545 const allocator_type& __a = allocator_type()) 00546 : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first, 00547 __last)), 00548 __gnu_debug::__base(__last), __n, 00549 __hf, __eql, __a) { } 00550 00551 unordered_multiset(const unordered_multiset&) = default; 00552 00553 unordered_multiset(const _Base& __x) 00554 : _Base(__x) { } 00555 00556 unordered_multiset(unordered_multiset&&) = default; 00557 00558 explicit 00559 unordered_multiset(const allocator_type& __a) 00560 : _Base(__a) { } 00561 00562 unordered_multiset(const unordered_multiset& __uset, 00563 const allocator_type& __a) 00564 : _Base(__uset, __a) { } 00565 00566 unordered_multiset(unordered_multiset&& __uset, 00567 const allocator_type& __a) 00568 : _Safe(std::move(__uset._M_safe()), __a), 00569 _Base(std::move(__uset._M_base()), __a) { } 00570 00571 unordered_multiset(initializer_list<value_type> __l, 00572 size_type __n = 0, 00573 const hasher& __hf = hasher(), 00574 const key_equal& __eql = key_equal(), 00575 const allocator_type& __a = allocator_type()) 00576 : _Base(__l, __n, __hf, __eql, __a) { } 00577 00578 unordered_multiset(size_type __n, const allocator_type& __a) 00579 : unordered_multiset(__n, hasher(), key_equal(), __a) 00580 { } 00581 00582 unordered_multiset(size_type __n, const hasher& __hf, 00583 const allocator_type& __a) 00584 : unordered_multiset(__n, __hf, key_equal(), __a) 00585 { } 00586 00587 template<typename _InputIterator> 00588 unordered_multiset(_InputIterator __first, _InputIterator __last, 00589 size_type __n, 00590 const allocator_type& __a) 00591 : unordered_multiset(__first, __last, __n, hasher(), key_equal(), __a) 00592 { } 00593 00594 template<typename _InputIterator> 00595 unordered_multiset(_InputIterator __first, _InputIterator __last, 00596 size_type __n, const hasher& __hf, 00597 const allocator_type& __a) 00598 : unordered_multiset(__first, __last, __n, __hf, key_equal(), __a) 00599 { } 00600 00601 unordered_multiset(initializer_list<value_type> __l, 00602 size_type __n, 00603 const allocator_type& __a) 00604 : unordered_multiset(__l, __n, hasher(), key_equal(), __a) 00605 { } 00606 00607 unordered_multiset(initializer_list<value_type> __l, 00608 size_type __n, const hasher& __hf, 00609 const allocator_type& __a) 00610 : unordered_multiset(__l, __n, __hf, key_equal(), __a) 00611 { } 00612 00613 ~unordered_multiset() = default; 00614 00615 unordered_multiset& 00616 operator=(const unordered_multiset&) = default; 00617 00618 unordered_multiset& 00619 operator=(unordered_multiset&&) = default; 00620 00621 unordered_multiset& 00622 operator=(initializer_list<value_type> __l) 00623 { 00624 this->_M_base() = __l; 00625 this->_M_invalidate_all(); 00626 return *this; 00627 } 00628 00629 void 00630 swap(unordered_multiset& __x) 00631 noexcept( noexcept(declval<_Base>().swap(__x)) ) 00632 { 00633 _Safe::_M_swap(__x); 00634 _Base::swap(__x); 00635 } 00636 00637 void 00638 clear() noexcept 00639 { 00640 _Base::clear(); 00641 this->_M_invalidate_all(); 00642 } 00643 00644 iterator 00645 begin() noexcept 00646 { return iterator(_Base::begin(), this); } 00647 00648 const_iterator 00649 begin() const noexcept 00650 { return const_iterator(_Base::begin(), this); } 00651 00652 iterator 00653 end() noexcept 00654 { return iterator(_Base::end(), this); } 00655 00656 const_iterator 00657 end() const noexcept 00658 { return const_iterator(_Base::end(), this); } 00659 00660 const_iterator 00661 cbegin() const noexcept 00662 { return const_iterator(_Base::begin(), this); } 00663 00664 const_iterator 00665 cend() const noexcept 00666 { return const_iterator(_Base::end(), this); } 00667 00668 // local versions 00669 local_iterator 00670 begin(size_type __b) 00671 { 00672 __glibcxx_check_bucket_index(__b); 00673 return local_iterator(_Base::begin(__b), this); 00674 } 00675 00676 local_iterator 00677 end(size_type __b) 00678 { 00679 __glibcxx_check_bucket_index(__b); 00680 return local_iterator(_Base::end(__b), this); 00681 } 00682 00683 const_local_iterator 00684 begin(size_type __b) const 00685 { 00686 __glibcxx_check_bucket_index(__b); 00687 return const_local_iterator(_Base::begin(__b), this); 00688 } 00689 00690 const_local_iterator 00691 end(size_type __b) const 00692 { 00693 __glibcxx_check_bucket_index(__b); 00694 return const_local_iterator(_Base::end(__b), this); 00695 } 00696 00697 const_local_iterator 00698 cbegin(size_type __b) const 00699 { 00700 __glibcxx_check_bucket_index(__b); 00701 return const_local_iterator(_Base::cbegin(__b), this); 00702 } 00703 00704 const_local_iterator 00705 cend(size_type __b) const 00706 { 00707 __glibcxx_check_bucket_index(__b); 00708 return const_local_iterator(_Base::cend(__b), this); 00709 } 00710 00711 size_type 00712 bucket_size(size_type __b) const 00713 { 00714 __glibcxx_check_bucket_index(__b); 00715 return _Base::bucket_size(__b); 00716 } 00717 00718 float 00719 max_load_factor() const noexcept 00720 { return _Base::max_load_factor(); } 00721 00722 void 00723 max_load_factor(float __f) 00724 { 00725 __glibcxx_check_max_load_factor(__f); 00726 _Base::max_load_factor(__f); 00727 } 00728 00729 template<typename... _Args> 00730 iterator 00731 emplace(_Args&&... __args) 00732 { 00733 size_type __bucket_count = this->bucket_count(); 00734 _Base_iterator __it 00735 = _Base::emplace(std::forward<_Args>(__args)...); 00736 _M_check_rehashed(__bucket_count); 00737 return iterator(__it, this); 00738 } 00739 00740 template<typename... _Args> 00741 iterator 00742 emplace_hint(const_iterator __hint, _Args&&... __args) 00743 { 00744 __glibcxx_check_insert(__hint); 00745 size_type __bucket_count = this->bucket_count(); 00746 _Base_iterator __it = _Base::emplace_hint(__hint.base(), 00747 std::forward<_Args>(__args)...); 00748 _M_check_rehashed(__bucket_count); 00749 return iterator(__it, this); 00750 } 00751 00752 iterator 00753 insert(const value_type& __obj) 00754 { 00755 size_type __bucket_count = this->bucket_count(); 00756 _Base_iterator __it = _Base::insert(__obj); 00757 _M_check_rehashed(__bucket_count); 00758 return iterator(__it, this); 00759 } 00760 00761 iterator 00762 insert(const_iterator __hint, const value_type& __obj) 00763 { 00764 __glibcxx_check_insert(__hint); 00765 size_type __bucket_count = this->bucket_count(); 00766 _Base_iterator __it = _Base::insert(__hint.base(), __obj); 00767 _M_check_rehashed(__bucket_count); 00768 return iterator(__it, this); 00769 } 00770 00771 iterator 00772 insert(value_type&& __obj) 00773 { 00774 size_type __bucket_count = this->bucket_count(); 00775 _Base_iterator __it = _Base::insert(std::move(__obj)); 00776 _M_check_rehashed(__bucket_count); 00777 return iterator(__it, this); 00778 } 00779 00780 iterator 00781 insert(const_iterator __hint, value_type&& __obj) 00782 { 00783 __glibcxx_check_insert(__hint); 00784 size_type __bucket_count = this->bucket_count(); 00785 _Base_iterator __it = _Base::insert(__hint.base(), std::move(__obj)); 00786 _M_check_rehashed(__bucket_count); 00787 return iterator(__it, this); 00788 } 00789 00790 void 00791 insert(std::initializer_list<value_type> __l) 00792 { 00793 size_type __bucket_count = this->bucket_count(); 00794 _Base::insert(__l); 00795 _M_check_rehashed(__bucket_count); 00796 } 00797 00798 template<typename _InputIterator> 00799 void 00800 insert(_InputIterator __first, _InputIterator __last) 00801 { 00802 __glibcxx_check_valid_range(__first, __last); 00803 size_type __bucket_count = this->bucket_count(); 00804 _Base::insert(__gnu_debug::__base(__first), 00805 __gnu_debug::__base(__last)); 00806 _M_check_rehashed(__bucket_count); 00807 } 00808 00809 iterator 00810 find(const key_type& __key) 00811 { return iterator(_Base::find(__key), this); } 00812 00813 const_iterator 00814 find(const key_type& __key) const 00815 { return const_iterator(_Base::find(__key), this); } 00816 00817 std::pair<iterator, iterator> 00818 equal_range(const key_type& __key) 00819 { 00820 std::pair<_Base_iterator, _Base_iterator> __res 00821 = _Base::equal_range(__key); 00822 return std::make_pair(iterator(__res.first, this), 00823 iterator(__res.second, this)); 00824 } 00825 00826 std::pair<const_iterator, const_iterator> 00827 equal_range(const key_type& __key) const 00828 { 00829 std::pair<_Base_const_iterator, _Base_const_iterator> 00830 __res = _Base::equal_range(__key); 00831 return std::make_pair(const_iterator(__res.first, this), 00832 const_iterator(__res.second, this)); 00833 } 00834 00835 size_type 00836 erase(const key_type& __key) 00837 { 00838 size_type __ret(0); 00839 std::pair<_Base_iterator, _Base_iterator> __pair = 00840 _Base::equal_range(__key); 00841 for (_Base_iterator __victim = __pair.first; __victim != __pair.second;) 00842 { 00843 this->_M_invalidate_if([__victim](_Base_const_iterator __it) 00844 { return __it == __victim; }); 00845 this->_M_invalidate_local_if( 00846 [__victim](_Base_const_local_iterator __it) 00847 { return __it._M_curr() == __victim._M_cur; }); 00848 _Base::erase(__victim++); 00849 ++__ret; 00850 } 00851 return __ret; 00852 } 00853 00854 iterator 00855 erase(const_iterator __it) 00856 { 00857 __glibcxx_check_erase(__it); 00858 _Base_const_iterator __victim = __it.base(); 00859 this->_M_invalidate_if([__victim](_Base_const_iterator __it) 00860 { return __it == __victim; }); 00861 this->_M_invalidate_local_if( 00862 [__victim](_Base_const_local_iterator __it) 00863 { return __it._M_curr() == __victim._M_cur; }); 00864 return iterator(_Base::erase(__it.base()), this); 00865 } 00866 00867 iterator 00868 erase(iterator __it) 00869 { return erase(const_iterator(__it)); } 00870 00871 iterator 00872 erase(const_iterator __first, const_iterator __last) 00873 { 00874 __glibcxx_check_erase_range(__first, __last); 00875 for (_Base_const_iterator __tmp = __first.base(); 00876 __tmp != __last.base(); ++__tmp) 00877 { 00878 _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(), 00879 _M_message(__gnu_debug::__msg_valid_range) 00880 ._M_iterator(__first, "first") 00881 ._M_iterator(__last, "last")); 00882 this->_M_invalidate_if([__tmp](_Base_const_iterator __it) 00883 { return __it == __tmp; }); 00884 this->_M_invalidate_local_if( 00885 [__tmp](_Base_const_local_iterator __it) 00886 { return __it._M_curr() == __tmp._M_cur; }); 00887 } 00888 return iterator(_Base::erase(__first.base(), 00889 __last.base()), this); 00890 } 00891 00892 _Base& 00893 _M_base() noexcept { return *this; } 00894 00895 const _Base& 00896 _M_base() const noexcept { return *this; } 00897 00898 private: 00899 void 00900 _M_check_rehashed(size_type __prev_count) 00901 { 00902 if (__prev_count != this->bucket_count()) 00903 this->_M_invalidate_locals(); 00904 } 00905 }; 00906 00907 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc> 00908 inline void 00909 swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, 00910 unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) 00911 { __x.swap(__y); } 00912 00913 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc> 00914 inline bool 00915 operator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, 00916 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) 00917 { return __x._M_base() == __y._M_base(); } 00918 00919 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc> 00920 inline bool 00921 operator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, 00922 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) 00923 { return !(__x == __y); } 00924 00925 } // namespace __debug 00926 } // namespace std 00927 00928 #endif // C++11 00929 00930 #endif