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