libstdc++
|
00001 // Debugging unordered_set/unordered_multiset implementation -*- C++ -*- 00002 00003 // Copyright (C) 2003-2016 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 typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist; 00359 __glibcxx_check_valid_range2(__first, __last, __dist); 00360 size_type __bucket_count = this->bucket_count(); 00361 00362 if (__dist.second >= __gnu_debug::__dp_sign) 00363 _Base::insert(__gnu_debug::__unsafe(__first), 00364 __gnu_debug::__unsafe(__last)); 00365 else 00366 _Base::insert(__first, __last); 00367 00368 _M_check_rehashed(__bucket_count); 00369 } 00370 00371 iterator 00372 find(const key_type& __key) 00373 { return iterator(_Base::find(__key), this); } 00374 00375 const_iterator 00376 find(const key_type& __key) const 00377 { return const_iterator(_Base::find(__key), this); } 00378 00379 std::pair<iterator, iterator> 00380 equal_range(const key_type& __key) 00381 { 00382 std::pair<_Base_iterator, _Base_iterator> __res 00383 = _Base::equal_range(__key); 00384 return std::make_pair(iterator(__res.first, this), 00385 iterator(__res.second, this)); 00386 } 00387 00388 std::pair<const_iterator, const_iterator> 00389 equal_range(const key_type& __key) const 00390 { 00391 std::pair<_Base_const_iterator, _Base_const_iterator> 00392 __res = _Base::equal_range(__key); 00393 return std::make_pair(const_iterator(__res.first, this), 00394 const_iterator(__res.second, this)); 00395 } 00396 00397 size_type 00398 erase(const key_type& __key) 00399 { 00400 size_type __ret(0); 00401 _Base_iterator __victim(_Base::find(__key)); 00402 if (__victim != _Base::end()) 00403 { 00404 this->_M_invalidate_if( 00405 [__victim](_Base_const_iterator __it) 00406 { return __it == __victim; }); 00407 this->_M_invalidate_local_if( 00408 [__victim](_Base_const_local_iterator __it) 00409 { return __it._M_curr() == __victim._M_cur; }); 00410 size_type __bucket_count = this->bucket_count(); 00411 _Base::erase(__victim); 00412 _M_check_rehashed(__bucket_count); 00413 __ret = 1; 00414 } 00415 return __ret; 00416 } 00417 00418 iterator 00419 erase(const_iterator __it) 00420 { 00421 __glibcxx_check_erase(__it); 00422 _Base_const_iterator __victim = __it.base(); 00423 this->_M_invalidate_if( 00424 [__victim](_Base_const_iterator __it) 00425 { return __it == __victim; }); 00426 this->_M_invalidate_local_if( 00427 [__victim](_Base_const_local_iterator __it) 00428 { return __it._M_curr() == __victim._M_cur; }); 00429 size_type __bucket_count = this->bucket_count(); 00430 _Base_iterator __next = _Base::erase(__it.base()); 00431 _M_check_rehashed(__bucket_count); 00432 return iterator(__next, this); 00433 } 00434 00435 iterator 00436 erase(iterator __it) 00437 { return erase(const_iterator(__it)); } 00438 00439 iterator 00440 erase(const_iterator __first, const_iterator __last) 00441 { 00442 __glibcxx_check_erase_range(__first, __last); 00443 for (_Base_const_iterator __tmp = __first.base(); 00444 __tmp != __last.base(); ++__tmp) 00445 { 00446 _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(), 00447 _M_message(__gnu_debug::__msg_valid_range) 00448 ._M_iterator(__first, "first") 00449 ._M_iterator(__last, "last")); 00450 this->_M_invalidate_if( 00451 [__tmp](_Base_const_iterator __it) 00452 { return __it == __tmp; }); 00453 this->_M_invalidate_local_if( 00454 [__tmp](_Base_const_local_iterator __it) 00455 { return __it._M_curr() == __tmp._M_cur; }); 00456 } 00457 size_type __bucket_count = this->bucket_count(); 00458 _Base_iterator __next = _Base::erase(__first.base(), 00459 __last.base()); 00460 _M_check_rehashed(__bucket_count); 00461 return iterator(__next, this); 00462 } 00463 00464 _Base& 00465 _M_base() noexcept { return *this; } 00466 00467 const _Base& 00468 _M_base() const noexcept { return *this; } 00469 00470 private: 00471 void 00472 _M_check_rehashed(size_type __prev_count) 00473 { 00474 if (__prev_count != this->bucket_count()) 00475 this->_M_invalidate_locals(); 00476 } 00477 }; 00478 00479 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc> 00480 inline void 00481 swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, 00482 unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) 00483 noexcept(noexcept(__x.swap(__y))) 00484 { __x.swap(__y); } 00485 00486 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc> 00487 inline bool 00488 operator==(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, 00489 const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) 00490 { return __x._M_base() == __y._M_base(); } 00491 00492 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc> 00493 inline bool 00494 operator!=(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, 00495 const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) 00496 { return !(__x == __y); } 00497 00498 00499 /// Class std::unordered_multiset with safety/checking/debug instrumentation. 00500 template<typename _Value, 00501 typename _Hash = std::hash<_Value>, 00502 typename _Pred = std::equal_to<_Value>, 00503 typename _Alloc = std::allocator<_Value> > 00504 class unordered_multiset 00505 : public __gnu_debug::_Safe_container< 00506 unordered_multiset<_Value, _Hash, _Pred, _Alloc>, _Alloc, 00507 __gnu_debug::_Safe_unordered_container>, 00508 public _GLIBCXX_STD_C::unordered_multiset<_Value, _Hash, _Pred, _Alloc> 00509 { 00510 typedef _GLIBCXX_STD_C::unordered_multiset< 00511 _Value, _Hash, _Pred, _Alloc> _Base; 00512 typedef __gnu_debug::_Safe_container<unordered_multiset, 00513 _Alloc, __gnu_debug::_Safe_unordered_container> _Safe; 00514 typedef typename _Base::const_iterator _Base_const_iterator; 00515 typedef typename _Base::iterator _Base_iterator; 00516 typedef typename _Base::const_local_iterator 00517 _Base_const_local_iterator; 00518 typedef typename _Base::local_iterator _Base_local_iterator; 00519 00520 public: 00521 typedef typename _Base::size_type size_type; 00522 typedef typename _Base::hasher hasher; 00523 typedef typename _Base::key_equal key_equal; 00524 typedef typename _Base::allocator_type allocator_type; 00525 00526 typedef typename _Base::key_type key_type; 00527 typedef typename _Base::value_type value_type; 00528 00529 typedef __gnu_debug::_Safe_iterator< 00530 _Base_iterator, unordered_multiset> iterator; 00531 typedef __gnu_debug::_Safe_iterator< 00532 _Base_const_iterator, unordered_multiset> const_iterator; 00533 typedef __gnu_debug::_Safe_local_iterator< 00534 _Base_local_iterator, unordered_multiset> local_iterator; 00535 typedef __gnu_debug::_Safe_local_iterator< 00536 _Base_const_local_iterator, unordered_multiset> const_local_iterator; 00537 00538 unordered_multiset() = default; 00539 00540 explicit 00541 unordered_multiset(size_type __n, 00542 const hasher& __hf = hasher(), 00543 const key_equal& __eql = key_equal(), 00544 const allocator_type& __a = allocator_type()) 00545 : _Base(__n, __hf, __eql, __a) { } 00546 00547 template<typename _InputIterator> 00548 unordered_multiset(_InputIterator __first, _InputIterator __last, 00549 size_type __n = 0, 00550 const hasher& __hf = hasher(), 00551 const key_equal& __eql = key_equal(), 00552 const allocator_type& __a = allocator_type()) 00553 : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first, 00554 __last)), 00555 __gnu_debug::__base(__last), __n, 00556 __hf, __eql, __a) { } 00557 00558 unordered_multiset(const unordered_multiset&) = default; 00559 00560 unordered_multiset(const _Base& __x) 00561 : _Base(__x) { } 00562 00563 unordered_multiset(unordered_multiset&&) = default; 00564 00565 explicit 00566 unordered_multiset(const allocator_type& __a) 00567 : _Base(__a) { } 00568 00569 unordered_multiset(const unordered_multiset& __uset, 00570 const allocator_type& __a) 00571 : _Base(__uset, __a) { } 00572 00573 unordered_multiset(unordered_multiset&& __uset, 00574 const allocator_type& __a) 00575 : _Safe(std::move(__uset._M_safe()), __a), 00576 _Base(std::move(__uset._M_base()), __a) { } 00577 00578 unordered_multiset(initializer_list<value_type> __l, 00579 size_type __n = 0, 00580 const hasher& __hf = hasher(), 00581 const key_equal& __eql = key_equal(), 00582 const allocator_type& __a = allocator_type()) 00583 : _Base(__l, __n, __hf, __eql, __a) { } 00584 00585 unordered_multiset(size_type __n, const allocator_type& __a) 00586 : unordered_multiset(__n, hasher(), key_equal(), __a) 00587 { } 00588 00589 unordered_multiset(size_type __n, const hasher& __hf, 00590 const allocator_type& __a) 00591 : unordered_multiset(__n, __hf, key_equal(), __a) 00592 { } 00593 00594 template<typename _InputIterator> 00595 unordered_multiset(_InputIterator __first, _InputIterator __last, 00596 size_type __n, 00597 const allocator_type& __a) 00598 : unordered_multiset(__first, __last, __n, hasher(), key_equal(), __a) 00599 { } 00600 00601 template<typename _InputIterator> 00602 unordered_multiset(_InputIterator __first, _InputIterator __last, 00603 size_type __n, const hasher& __hf, 00604 const allocator_type& __a) 00605 : unordered_multiset(__first, __last, __n, __hf, key_equal(), __a) 00606 { } 00607 00608 unordered_multiset(initializer_list<value_type> __l, 00609 size_type __n, 00610 const allocator_type& __a) 00611 : unordered_multiset(__l, __n, hasher(), key_equal(), __a) 00612 { } 00613 00614 unordered_multiset(initializer_list<value_type> __l, 00615 size_type __n, const hasher& __hf, 00616 const allocator_type& __a) 00617 : unordered_multiset(__l, __n, __hf, key_equal(), __a) 00618 { } 00619 00620 ~unordered_multiset() = default; 00621 00622 unordered_multiset& 00623 operator=(const unordered_multiset&) = default; 00624 00625 unordered_multiset& 00626 operator=(unordered_multiset&&) = default; 00627 00628 unordered_multiset& 00629 operator=(initializer_list<value_type> __l) 00630 { 00631 this->_M_base() = __l; 00632 this->_M_invalidate_all(); 00633 return *this; 00634 } 00635 00636 void 00637 swap(unordered_multiset& __x) 00638 noexcept( noexcept(declval<_Base&>().swap(__x)) ) 00639 { 00640 _Safe::_M_swap(__x); 00641 _Base::swap(__x); 00642 } 00643 00644 void 00645 clear() noexcept 00646 { 00647 _Base::clear(); 00648 this->_M_invalidate_all(); 00649 } 00650 00651 iterator 00652 begin() noexcept 00653 { return iterator(_Base::begin(), this); } 00654 00655 const_iterator 00656 begin() const noexcept 00657 { return const_iterator(_Base::begin(), this); } 00658 00659 iterator 00660 end() noexcept 00661 { return iterator(_Base::end(), this); } 00662 00663 const_iterator 00664 end() const noexcept 00665 { return const_iterator(_Base::end(), this); } 00666 00667 const_iterator 00668 cbegin() const noexcept 00669 { return const_iterator(_Base::begin(), this); } 00670 00671 const_iterator 00672 cend() const noexcept 00673 { return const_iterator(_Base::end(), this); } 00674 00675 // local versions 00676 local_iterator 00677 begin(size_type __b) 00678 { 00679 __glibcxx_check_bucket_index(__b); 00680 return local_iterator(_Base::begin(__b), this); 00681 } 00682 00683 local_iterator 00684 end(size_type __b) 00685 { 00686 __glibcxx_check_bucket_index(__b); 00687 return local_iterator(_Base::end(__b), this); 00688 } 00689 00690 const_local_iterator 00691 begin(size_type __b) const 00692 { 00693 __glibcxx_check_bucket_index(__b); 00694 return const_local_iterator(_Base::begin(__b), this); 00695 } 00696 00697 const_local_iterator 00698 end(size_type __b) const 00699 { 00700 __glibcxx_check_bucket_index(__b); 00701 return const_local_iterator(_Base::end(__b), this); 00702 } 00703 00704 const_local_iterator 00705 cbegin(size_type __b) const 00706 { 00707 __glibcxx_check_bucket_index(__b); 00708 return const_local_iterator(_Base::cbegin(__b), this); 00709 } 00710 00711 const_local_iterator 00712 cend(size_type __b) const 00713 { 00714 __glibcxx_check_bucket_index(__b); 00715 return const_local_iterator(_Base::cend(__b), this); 00716 } 00717 00718 size_type 00719 bucket_size(size_type __b) const 00720 { 00721 __glibcxx_check_bucket_index(__b); 00722 return _Base::bucket_size(__b); 00723 } 00724 00725 float 00726 max_load_factor() const noexcept 00727 { return _Base::max_load_factor(); } 00728 00729 void 00730 max_load_factor(float __f) 00731 { 00732 __glibcxx_check_max_load_factor(__f); 00733 _Base::max_load_factor(__f); 00734 } 00735 00736 template<typename... _Args> 00737 iterator 00738 emplace(_Args&&... __args) 00739 { 00740 size_type __bucket_count = this->bucket_count(); 00741 _Base_iterator __it 00742 = _Base::emplace(std::forward<_Args>(__args)...); 00743 _M_check_rehashed(__bucket_count); 00744 return iterator(__it, this); 00745 } 00746 00747 template<typename... _Args> 00748 iterator 00749 emplace_hint(const_iterator __hint, _Args&&... __args) 00750 { 00751 __glibcxx_check_insert(__hint); 00752 size_type __bucket_count = this->bucket_count(); 00753 _Base_iterator __it = _Base::emplace_hint(__hint.base(), 00754 std::forward<_Args>(__args)...); 00755 _M_check_rehashed(__bucket_count); 00756 return iterator(__it, this); 00757 } 00758 00759 iterator 00760 insert(const value_type& __obj) 00761 { 00762 size_type __bucket_count = this->bucket_count(); 00763 _Base_iterator __it = _Base::insert(__obj); 00764 _M_check_rehashed(__bucket_count); 00765 return iterator(__it, this); 00766 } 00767 00768 iterator 00769 insert(const_iterator __hint, const 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(), __obj); 00774 _M_check_rehashed(__bucket_count); 00775 return iterator(__it, this); 00776 } 00777 00778 iterator 00779 insert(value_type&& __obj) 00780 { 00781 size_type __bucket_count = this->bucket_count(); 00782 _Base_iterator __it = _Base::insert(std::move(__obj)); 00783 _M_check_rehashed(__bucket_count); 00784 return iterator(__it, this); 00785 } 00786 00787 iterator 00788 insert(const_iterator __hint, value_type&& __obj) 00789 { 00790 __glibcxx_check_insert(__hint); 00791 size_type __bucket_count = this->bucket_count(); 00792 _Base_iterator __it = _Base::insert(__hint.base(), std::move(__obj)); 00793 _M_check_rehashed(__bucket_count); 00794 return iterator(__it, this); 00795 } 00796 00797 void 00798 insert(std::initializer_list<value_type> __l) 00799 { 00800 size_type __bucket_count = this->bucket_count(); 00801 _Base::insert(__l); 00802 _M_check_rehashed(__bucket_count); 00803 } 00804 00805 template<typename _InputIterator> 00806 void 00807 insert(_InputIterator __first, _InputIterator __last) 00808 { 00809 typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist; 00810 __glibcxx_check_valid_range2(__first, __last, __dist); 00811 size_type __bucket_count = this->bucket_count(); 00812 00813 if (__dist.second >= __gnu_debug::__dp_sign) 00814 _Base::insert(__gnu_debug::__unsafe(__first), 00815 __gnu_debug::__unsafe(__last)); 00816 else 00817 _Base::insert(__first, __last); 00818 00819 _M_check_rehashed(__bucket_count); 00820 } 00821 00822 iterator 00823 find(const key_type& __key) 00824 { return iterator(_Base::find(__key), this); } 00825 00826 const_iterator 00827 find(const key_type& __key) const 00828 { return const_iterator(_Base::find(__key), this); } 00829 00830 std::pair<iterator, iterator> 00831 equal_range(const key_type& __key) 00832 { 00833 std::pair<_Base_iterator, _Base_iterator> __res 00834 = _Base::equal_range(__key); 00835 return std::make_pair(iterator(__res.first, this), 00836 iterator(__res.second, this)); 00837 } 00838 00839 std::pair<const_iterator, const_iterator> 00840 equal_range(const key_type& __key) const 00841 { 00842 std::pair<_Base_const_iterator, _Base_const_iterator> 00843 __res = _Base::equal_range(__key); 00844 return std::make_pair(const_iterator(__res.first, this), 00845 const_iterator(__res.second, this)); 00846 } 00847 00848 size_type 00849 erase(const key_type& __key) 00850 { 00851 size_type __ret(0); 00852 std::pair<_Base_iterator, _Base_iterator> __pair = 00853 _Base::equal_range(__key); 00854 for (_Base_iterator __victim = __pair.first; __victim != __pair.second;) 00855 { 00856 this->_M_invalidate_if([__victim](_Base_const_iterator __it) 00857 { return __it == __victim; }); 00858 this->_M_invalidate_local_if( 00859 [__victim](_Base_const_local_iterator __it) 00860 { return __it._M_curr() == __victim._M_cur; }); 00861 _Base::erase(__victim++); 00862 ++__ret; 00863 } 00864 return __ret; 00865 } 00866 00867 iterator 00868 erase(const_iterator __it) 00869 { 00870 __glibcxx_check_erase(__it); 00871 _Base_const_iterator __victim = __it.base(); 00872 this->_M_invalidate_if([__victim](_Base_const_iterator __it) 00873 { return __it == __victim; }); 00874 this->_M_invalidate_local_if( 00875 [__victim](_Base_const_local_iterator __it) 00876 { return __it._M_curr() == __victim._M_cur; }); 00877 return iterator(_Base::erase(__it.base()), this); 00878 } 00879 00880 iterator 00881 erase(iterator __it) 00882 { return erase(const_iterator(__it)); } 00883 00884 iterator 00885 erase(const_iterator __first, const_iterator __last) 00886 { 00887 __glibcxx_check_erase_range(__first, __last); 00888 for (_Base_const_iterator __tmp = __first.base(); 00889 __tmp != __last.base(); ++__tmp) 00890 { 00891 _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(), 00892 _M_message(__gnu_debug::__msg_valid_range) 00893 ._M_iterator(__first, "first") 00894 ._M_iterator(__last, "last")); 00895 this->_M_invalidate_if([__tmp](_Base_const_iterator __it) 00896 { return __it == __tmp; }); 00897 this->_M_invalidate_local_if( 00898 [__tmp](_Base_const_local_iterator __it) 00899 { return __it._M_curr() == __tmp._M_cur; }); 00900 } 00901 return iterator(_Base::erase(__first.base(), 00902 __last.base()), this); 00903 } 00904 00905 _Base& 00906 _M_base() noexcept { return *this; } 00907 00908 const _Base& 00909 _M_base() const noexcept { return *this; } 00910 00911 private: 00912 void 00913 _M_check_rehashed(size_type __prev_count) 00914 { 00915 if (__prev_count != this->bucket_count()) 00916 this->_M_invalidate_locals(); 00917 } 00918 }; 00919 00920 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc> 00921 inline void 00922 swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, 00923 unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) 00924 noexcept(noexcept(__x.swap(__y))) 00925 { __x.swap(__y); } 00926 00927 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc> 00928 inline bool 00929 operator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, 00930 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) 00931 { return __x._M_base() == __y._M_base(); } 00932 00933 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc> 00934 inline bool 00935 operator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, 00936 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) 00937 { return !(__x == __y); } 00938 00939 } // namespace __debug 00940 } // namespace std 00941 00942 #endif // C++11 00943 00944 #endif