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