libstdc++
|
00001 // Debugging unordered_set/unordered_multiset implementation -*- C++ -*- 00002 00003 // Copyright (C) 2003-2018 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 #pragma GCC system_header 00033 00034 #if __cplusplus < 201103L 00035 # include <bits/c++0x_warning.h> 00036 #else 00037 # include <unordered_set> 00038 00039 #include <debug/safe_unordered_container.h> 00040 #include <debug/safe_container.h> 00041 #include <debug/safe_iterator.h> 00042 #include <debug/safe_local_iterator.h> 00043 00044 namespace std _GLIBCXX_VISIBILITY(default) 00045 { 00046 namespace __debug 00047 { 00048 /// Class std::unordered_set with safety/checking/debug instrumentation. 00049 template<typename _Value, 00050 typename _Hash = std::hash<_Value>, 00051 typename _Pred = std::equal_to<_Value>, 00052 typename _Alloc = std::allocator<_Value> > 00053 class unordered_set 00054 : public __gnu_debug::_Safe_container< 00055 unordered_set<_Value, _Hash, _Pred, _Alloc>, _Alloc, 00056 __gnu_debug::_Safe_unordered_container>, 00057 public _GLIBCXX_STD_C::unordered_set<_Value, _Hash, _Pred, _Alloc> 00058 { 00059 typedef _GLIBCXX_STD_C::unordered_set< 00060 _Value, _Hash, _Pred, _Alloc> _Base; 00061 typedef __gnu_debug::_Safe_container< 00062 unordered_set, _Alloc, __gnu_debug::_Safe_unordered_container> _Safe; 00063 00064 typedef typename _Base::const_iterator _Base_const_iterator; 00065 typedef typename _Base::iterator _Base_iterator; 00066 typedef typename _Base::const_local_iterator _Base_const_local_iterator; 00067 typedef typename _Base::local_iterator _Base_local_iterator; 00068 00069 public: 00070 typedef typename _Base::size_type size_type; 00071 typedef typename _Base::hasher hasher; 00072 typedef typename _Base::key_equal key_equal; 00073 typedef typename _Base::allocator_type allocator_type; 00074 00075 typedef typename _Base::key_type key_type; 00076 typedef typename _Base::value_type value_type; 00077 00078 typedef __gnu_debug::_Safe_iterator< 00079 _Base_iterator, unordered_set> iterator; 00080 typedef __gnu_debug::_Safe_iterator< 00081 _Base_const_iterator, unordered_set> const_iterator; 00082 typedef __gnu_debug::_Safe_local_iterator< 00083 _Base_local_iterator, unordered_set> local_iterator; 00084 typedef __gnu_debug::_Safe_local_iterator< 00085 _Base_const_local_iterator, unordered_set> const_local_iterator; 00086 00087 unordered_set() = default; 00088 00089 explicit 00090 unordered_set(size_type __n, 00091 const hasher& __hf = hasher(), 00092 const key_equal& __eql = key_equal(), 00093 const allocator_type& __a = allocator_type()) 00094 : _Base(__n, __hf, __eql, __a) { } 00095 00096 template<typename _InputIterator> 00097 unordered_set(_InputIterator __first, _InputIterator __last, 00098 size_type __n = 0, 00099 const hasher& __hf = hasher(), 00100 const key_equal& __eql = key_equal(), 00101 const allocator_type& __a = allocator_type()) 00102 : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first, 00103 __last)), 00104 __gnu_debug::__base(__last), __n, 00105 __hf, __eql, __a) { } 00106 00107 unordered_set(const unordered_set&) = default; 00108 00109 unordered_set(const _Base& __x) 00110 : _Base(__x) { } 00111 00112 unordered_set(unordered_set&&) = default; 00113 00114 explicit 00115 unordered_set(const allocator_type& __a) 00116 : _Base(__a) { } 00117 00118 unordered_set(const unordered_set& __uset, 00119 const allocator_type& __a) 00120 : _Base(__uset, __a) { } 00121 00122 unordered_set(unordered_set&& __uset, 00123 const allocator_type& __a) 00124 : _Safe(std::move(__uset._M_safe()), __a), 00125 _Base(std::move(__uset._M_base()), __a) { } 00126 00127 unordered_set(initializer_list<value_type> __l, 00128 size_type __n = 0, 00129 const hasher& __hf = hasher(), 00130 const key_equal& __eql = key_equal(), 00131 const allocator_type& __a = allocator_type()) 00132 : _Base(__l, __n, __hf, __eql, __a) { } 00133 00134 unordered_set(size_type __n, const allocator_type& __a) 00135 : unordered_set(__n, hasher(), key_equal(), __a) 00136 { } 00137 00138 unordered_set(size_type __n, const hasher& __hf, 00139 const allocator_type& __a) 00140 : unordered_set(__n, __hf, key_equal(), __a) 00141 { } 00142 00143 template<typename _InputIterator> 00144 unordered_set(_InputIterator __first, _InputIterator __last, 00145 size_type __n, 00146 const allocator_type& __a) 00147 : unordered_set(__first, __last, __n, hasher(), key_equal(), __a) 00148 { } 00149 00150 template<typename _InputIterator> 00151 unordered_set(_InputIterator __first, _InputIterator __last, 00152 size_type __n, const hasher& __hf, 00153 const allocator_type& __a) 00154 : unordered_set(__first, __last, __n, __hf, key_equal(), __a) 00155 { } 00156 00157 unordered_set(initializer_list<value_type> __l, 00158 size_type __n, 00159 const allocator_type& __a) 00160 : unordered_set(__l, __n, hasher(), key_equal(), __a) 00161 { } 00162 00163 unordered_set(initializer_list<value_type> __l, 00164 size_type __n, const hasher& __hf, 00165 const allocator_type& __a) 00166 : unordered_set(__l, __n, __hf, key_equal(), __a) 00167 { } 00168 00169 ~unordered_set() = default; 00170 00171 unordered_set& 00172 operator=(const unordered_set&) = default; 00173 00174 unordered_set& 00175 operator=(unordered_set&&) = default; 00176 00177 unordered_set& 00178 operator=(initializer_list<value_type> __l) 00179 { 00180 _M_base() = __l; 00181 this->_M_invalidate_all(); 00182 return *this; 00183 } 00184 00185 void 00186 swap(unordered_set& __x) 00187 noexcept( noexcept(declval<_Base&>().swap(__x)) ) 00188 { 00189 _Safe::_M_swap(__x); 00190 _Base::swap(__x); 00191 } 00192 00193 void 00194 clear() noexcept 00195 { 00196 _Base::clear(); 00197 this->_M_invalidate_all(); 00198 } 00199 00200 iterator 00201 begin() noexcept 00202 { return iterator(_Base::begin(), this); } 00203 00204 const_iterator 00205 begin() const noexcept 00206 { return const_iterator(_Base::begin(), this); } 00207 00208 iterator 00209 end() noexcept 00210 { return iterator(_Base::end(), this); } 00211 00212 const_iterator 00213 end() const noexcept 00214 { return const_iterator(_Base::end(), this); } 00215 00216 const_iterator 00217 cbegin() const noexcept 00218 { return const_iterator(_Base::begin(), this); } 00219 00220 const_iterator 00221 cend() const noexcept 00222 { return const_iterator(_Base::end(), this); } 00223 00224 // local versions 00225 local_iterator 00226 begin(size_type __b) 00227 { 00228 __glibcxx_check_bucket_index(__b); 00229 return local_iterator(_Base::begin(__b), this); 00230 } 00231 00232 local_iterator 00233 end(size_type __b) 00234 { 00235 __glibcxx_check_bucket_index(__b); 00236 return local_iterator(_Base::end(__b), this); 00237 } 00238 00239 const_local_iterator 00240 begin(size_type __b) const 00241 { 00242 __glibcxx_check_bucket_index(__b); 00243 return const_local_iterator(_Base::begin(__b), this); 00244 } 00245 00246 const_local_iterator 00247 end(size_type __b) const 00248 { 00249 __glibcxx_check_bucket_index(__b); 00250 return const_local_iterator(_Base::end(__b), this); 00251 } 00252 00253 const_local_iterator 00254 cbegin(size_type __b) const 00255 { 00256 __glibcxx_check_bucket_index(__b); 00257 return const_local_iterator(_Base::cbegin(__b), this); 00258 } 00259 00260 const_local_iterator 00261 cend(size_type __b) const 00262 { 00263 __glibcxx_check_bucket_index(__b); 00264 return const_local_iterator(_Base::cend(__b), this); 00265 } 00266 00267 size_type 00268 bucket_size(size_type __b) const 00269 { 00270 __glibcxx_check_bucket_index(__b); 00271 return _Base::bucket_size(__b); 00272 } 00273 00274 float 00275 max_load_factor() const noexcept 00276 { return _Base::max_load_factor(); } 00277 00278 void 00279 max_load_factor(float __f) 00280 { 00281 __glibcxx_check_max_load_factor(__f); 00282 _Base::max_load_factor(__f); 00283 } 00284 00285 template<typename... _Args> 00286 std::pair<iterator, bool> 00287 emplace(_Args&&... __args) 00288 { 00289 size_type __bucket_count = this->bucket_count(); 00290 std::pair<_Base_iterator, bool> __res 00291 = _Base::emplace(std::forward<_Args>(__args)...); 00292 _M_check_rehashed(__bucket_count); 00293 return std::make_pair(iterator(__res.first, this), __res.second); 00294 } 00295 00296 template<typename... _Args> 00297 iterator 00298 emplace_hint(const_iterator __hint, _Args&&... __args) 00299 { 00300 __glibcxx_check_insert(__hint); 00301 size_type __bucket_count = this->bucket_count(); 00302 _Base_iterator __it = _Base::emplace_hint(__hint.base(), 00303 std::forward<_Args>(__args)...); 00304 _M_check_rehashed(__bucket_count); 00305 return iterator(__it, this); 00306 } 00307 00308 std::pair<iterator, bool> 00309 insert(const value_type& __obj) 00310 { 00311 size_type __bucket_count = this->bucket_count(); 00312 std::pair<_Base_iterator, bool> __res 00313 = _Base::insert(__obj); 00314 _M_check_rehashed(__bucket_count); 00315 return std::make_pair(iterator(__res.first, this), __res.second); 00316 } 00317 00318 iterator 00319 insert(const_iterator __hint, const value_type& __obj) 00320 { 00321 __glibcxx_check_insert(__hint); 00322 size_type __bucket_count = this->bucket_count(); 00323 _Base_iterator __it = _Base::insert(__hint.base(), __obj); 00324 _M_check_rehashed(__bucket_count); 00325 return iterator(__it, this); 00326 } 00327 00328 std::pair<iterator, bool> 00329 insert(value_type&& __obj) 00330 { 00331 size_type __bucket_count = this->bucket_count(); 00332 std::pair<_Base_iterator, bool> __res 00333 = _Base::insert(std::move(__obj)); 00334 _M_check_rehashed(__bucket_count); 00335 return std::make_pair(iterator(__res.first, this), __res.second); 00336 } 00337 00338 iterator 00339 insert(const_iterator __hint, value_type&& __obj) 00340 { 00341 __glibcxx_check_insert(__hint); 00342 size_type __bucket_count = this->bucket_count(); 00343 _Base_iterator __it = _Base::insert(__hint.base(), std::move(__obj)); 00344 _M_check_rehashed(__bucket_count); 00345 return iterator(__it, this); 00346 } 00347 00348 void 00349 insert(std::initializer_list<value_type> __l) 00350 { 00351 size_type __bucket_count = this->bucket_count(); 00352 _Base::insert(__l); 00353 _M_check_rehashed(__bucket_count); 00354 } 00355 00356 template<typename _InputIterator> 00357 void 00358 insert(_InputIterator __first, _InputIterator __last) 00359 { 00360 typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist; 00361 __glibcxx_check_valid_range2(__first, __last, __dist); 00362 size_type __bucket_count = this->bucket_count(); 00363 00364 if (__dist.second >= __gnu_debug::__dp_sign) 00365 _Base::insert(__gnu_debug::__unsafe(__first), 00366 __gnu_debug::__unsafe(__last)); 00367 else 00368 _Base::insert(__first, __last); 00369 00370 _M_check_rehashed(__bucket_count); 00371 } 00372 00373 #if __cplusplus > 201402L 00374 using node_type = typename _Base::node_type; 00375 using insert_return_type = _Node_insert_return<iterator, node_type>; 00376 00377 node_type 00378 extract(const_iterator __position) 00379 { 00380 __glibcxx_check_erase(__position); 00381 _Base_const_iterator __victim = __position.base(); 00382 this->_M_invalidate_if( 00383 [__victim](_Base_const_iterator __it) { return __it == __victim; } 00384 ); 00385 this->_M_invalidate_local_if( 00386 [__victim](_Base_const_local_iterator __it) { 00387 return __it._M_curr() == __victim._M_cur; 00388 }); 00389 return _Base::extract(__position.base()); 00390 } 00391 00392 node_type 00393 extract(const key_type& __key) 00394 { 00395 const auto __position = find(__key); 00396 if (__position != end()) 00397 return extract(__position); 00398 return {}; 00399 } 00400 00401 insert_return_type 00402 insert(node_type&& __nh) 00403 { 00404 auto __ret = _Base::insert(std::move(__nh)); 00405 iterator __pos = iterator(__ret.position, this); 00406 return { __pos, __ret.inserted, std::move(__ret.node) }; 00407 } 00408 00409 iterator 00410 insert(const_iterator __hint, node_type&& __nh) 00411 { 00412 __glibcxx_check_insert(__hint); 00413 return iterator(_Base::insert(__hint.base(), std::move(__nh)), this); 00414 } 00415 00416 using _Base::merge; 00417 #endif // C++17 00418 00419 iterator 00420 find(const key_type& __key) 00421 { return iterator(_Base::find(__key), this); } 00422 00423 const_iterator 00424 find(const key_type& __key) const 00425 { return const_iterator(_Base::find(__key), this); } 00426 00427 std::pair<iterator, iterator> 00428 equal_range(const key_type& __key) 00429 { 00430 std::pair<_Base_iterator, _Base_iterator> __res 00431 = _Base::equal_range(__key); 00432 return std::make_pair(iterator(__res.first, this), 00433 iterator(__res.second, this)); 00434 } 00435 00436 std::pair<const_iterator, const_iterator> 00437 equal_range(const key_type& __key) const 00438 { 00439 std::pair<_Base_const_iterator, _Base_const_iterator> 00440 __res = _Base::equal_range(__key); 00441 return std::make_pair(const_iterator(__res.first, this), 00442 const_iterator(__res.second, this)); 00443 } 00444 00445 size_type 00446 erase(const key_type& __key) 00447 { 00448 size_type __ret(0); 00449 _Base_iterator __victim(_Base::find(__key)); 00450 if (__victim != _Base::end()) 00451 { 00452 this->_M_invalidate_if( 00453 [__victim](_Base_const_iterator __it) 00454 { return __it == __victim; }); 00455 this->_M_invalidate_local_if( 00456 [__victim](_Base_const_local_iterator __it) 00457 { return __it._M_curr() == __victim._M_cur; }); 00458 size_type __bucket_count = this->bucket_count(); 00459 _Base::erase(__victim); 00460 _M_check_rehashed(__bucket_count); 00461 __ret = 1; 00462 } 00463 return __ret; 00464 } 00465 00466 iterator 00467 erase(const_iterator __it) 00468 { 00469 __glibcxx_check_erase(__it); 00470 _Base_const_iterator __victim = __it.base(); 00471 this->_M_invalidate_if( 00472 [__victim](_Base_const_iterator __it) 00473 { return __it == __victim; }); 00474 this->_M_invalidate_local_if( 00475 [__victim](_Base_const_local_iterator __it) 00476 { return __it._M_curr() == __victim._M_cur; }); 00477 size_type __bucket_count = this->bucket_count(); 00478 _Base_iterator __next = _Base::erase(__it.base()); 00479 _M_check_rehashed(__bucket_count); 00480 return iterator(__next, this); 00481 } 00482 00483 iterator 00484 erase(iterator __it) 00485 { return erase(const_iterator(__it)); } 00486 00487 iterator 00488 erase(const_iterator __first, const_iterator __last) 00489 { 00490 __glibcxx_check_erase_range(__first, __last); 00491 for (_Base_const_iterator __tmp = __first.base(); 00492 __tmp != __last.base(); ++__tmp) 00493 { 00494 _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(), 00495 _M_message(__gnu_debug::__msg_valid_range) 00496 ._M_iterator(__first, "first") 00497 ._M_iterator(__last, "last")); 00498 this->_M_invalidate_if( 00499 [__tmp](_Base_const_iterator __it) 00500 { return __it == __tmp; }); 00501 this->_M_invalidate_local_if( 00502 [__tmp](_Base_const_local_iterator __it) 00503 { return __it._M_curr() == __tmp._M_cur; }); 00504 } 00505 size_type __bucket_count = this->bucket_count(); 00506 _Base_iterator __next = _Base::erase(__first.base(), 00507 __last.base()); 00508 _M_check_rehashed(__bucket_count); 00509 return iterator(__next, this); 00510 } 00511 00512 _Base& 00513 _M_base() noexcept { return *this; } 00514 00515 const _Base& 00516 _M_base() const noexcept { return *this; } 00517 00518 private: 00519 void 00520 _M_check_rehashed(size_type __prev_count) 00521 { 00522 if (__prev_count != this->bucket_count()) 00523 this->_M_invalidate_locals(); 00524 } 00525 }; 00526 00527 #if __cpp_deduction_guides >= 201606 00528 00529 template<typename _InputIterator, 00530 typename _Hash = 00531 hash<typename iterator_traits<_InputIterator>::value_type>, 00532 typename _Pred = 00533 equal_to<typename iterator_traits<_InputIterator>::value_type>, 00534 typename _Allocator = 00535 allocator<typename iterator_traits<_InputIterator>::value_type>, 00536 typename = _RequireInputIter<_InputIterator>, 00537 typename = _RequireAllocator<_Allocator>> 00538 unordered_set(_InputIterator, _InputIterator, 00539 unordered_set<int>::size_type = {}, 00540 _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator()) 00541 -> unordered_set<typename iterator_traits<_InputIterator>::value_type, 00542 _Hash, _Pred, _Allocator>; 00543 00544 template<typename _Tp, typename _Hash = hash<_Tp>, 00545 typename _Pred = equal_to<_Tp>, 00546 typename _Allocator = allocator<_Tp>, 00547 typename = _RequireAllocator<_Allocator>> 00548 unordered_set(initializer_list<_Tp>, 00549 unordered_set<int>::size_type = {}, 00550 _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator()) 00551 -> unordered_set<_Tp, _Hash, _Pred, _Allocator>; 00552 00553 template<typename _InputIterator, typename _Allocator, 00554 typename = _RequireInputIter<_InputIterator>, 00555 typename = _RequireAllocator<_Allocator>> 00556 unordered_set(_InputIterator, _InputIterator, 00557 unordered_set<int>::size_type, _Allocator) 00558 -> unordered_set<typename iterator_traits<_InputIterator>::value_type, 00559 hash< 00560 typename iterator_traits<_InputIterator>::value_type>, 00561 equal_to< 00562 typename iterator_traits<_InputIterator>::value_type>, 00563 _Allocator>; 00564 00565 template<typename _InputIterator, typename _Hash, typename _Allocator, 00566 typename = _RequireInputIter<_InputIterator>, 00567 typename = _RequireAllocator<_Allocator>> 00568 unordered_set(_InputIterator, _InputIterator, 00569 unordered_set<int>::size_type, 00570 _Hash, _Allocator) 00571 -> unordered_set<typename iterator_traits<_InputIterator>::value_type, 00572 _Hash, 00573 equal_to< 00574 typename iterator_traits<_InputIterator>::value_type>, 00575 _Allocator>; 00576 00577 template<typename _Tp, typename _Allocator, 00578 typename = _RequireAllocator<_Allocator>> 00579 unordered_set(initializer_list<_Tp>, 00580 unordered_set<int>::size_type, _Allocator) 00581 -> unordered_set<_Tp, hash<_Tp>, equal_to<_Tp>, _Allocator>; 00582 00583 template<typename _Tp, typename _Hash, typename _Allocator, 00584 typename = _RequireAllocator<_Allocator>> 00585 unordered_set(initializer_list<_Tp>, 00586 unordered_set<int>::size_type, _Hash, _Allocator) 00587 -> unordered_set<_Tp, _Hash, equal_to<_Tp>, _Allocator>; 00588 00589 #endif 00590 00591 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc> 00592 inline void 00593 swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, 00594 unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) 00595 noexcept(noexcept(__x.swap(__y))) 00596 { __x.swap(__y); } 00597 00598 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc> 00599 inline bool 00600 operator==(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, 00601 const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) 00602 { return __x._M_base() == __y._M_base(); } 00603 00604 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc> 00605 inline bool 00606 operator!=(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, 00607 const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) 00608 { return !(__x == __y); } 00609 00610 00611 /// Class std::unordered_multiset with safety/checking/debug instrumentation. 00612 template<typename _Value, 00613 typename _Hash = std::hash<_Value>, 00614 typename _Pred = std::equal_to<_Value>, 00615 typename _Alloc = std::allocator<_Value> > 00616 class unordered_multiset 00617 : public __gnu_debug::_Safe_container< 00618 unordered_multiset<_Value, _Hash, _Pred, _Alloc>, _Alloc, 00619 __gnu_debug::_Safe_unordered_container>, 00620 public _GLIBCXX_STD_C::unordered_multiset<_Value, _Hash, _Pred, _Alloc> 00621 { 00622 typedef _GLIBCXX_STD_C::unordered_multiset< 00623 _Value, _Hash, _Pred, _Alloc> _Base; 00624 typedef __gnu_debug::_Safe_container<unordered_multiset, 00625 _Alloc, __gnu_debug::_Safe_unordered_container> _Safe; 00626 typedef typename _Base::const_iterator _Base_const_iterator; 00627 typedef typename _Base::iterator _Base_iterator; 00628 typedef typename _Base::const_local_iterator 00629 _Base_const_local_iterator; 00630 typedef typename _Base::local_iterator _Base_local_iterator; 00631 00632 public: 00633 typedef typename _Base::size_type size_type; 00634 typedef typename _Base::hasher hasher; 00635 typedef typename _Base::key_equal key_equal; 00636 typedef typename _Base::allocator_type allocator_type; 00637 00638 typedef typename _Base::key_type key_type; 00639 typedef typename _Base::value_type value_type; 00640 00641 typedef __gnu_debug::_Safe_iterator< 00642 _Base_iterator, unordered_multiset> iterator; 00643 typedef __gnu_debug::_Safe_iterator< 00644 _Base_const_iterator, unordered_multiset> const_iterator; 00645 typedef __gnu_debug::_Safe_local_iterator< 00646 _Base_local_iterator, unordered_multiset> local_iterator; 00647 typedef __gnu_debug::_Safe_local_iterator< 00648 _Base_const_local_iterator, unordered_multiset> const_local_iterator; 00649 00650 unordered_multiset() = default; 00651 00652 explicit 00653 unordered_multiset(size_type __n, 00654 const hasher& __hf = hasher(), 00655 const key_equal& __eql = key_equal(), 00656 const allocator_type& __a = allocator_type()) 00657 : _Base(__n, __hf, __eql, __a) { } 00658 00659 template<typename _InputIterator> 00660 unordered_multiset(_InputIterator __first, _InputIterator __last, 00661 size_type __n = 0, 00662 const hasher& __hf = hasher(), 00663 const key_equal& __eql = key_equal(), 00664 const allocator_type& __a = allocator_type()) 00665 : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first, 00666 __last)), 00667 __gnu_debug::__base(__last), __n, 00668 __hf, __eql, __a) { } 00669 00670 unordered_multiset(const unordered_multiset&) = default; 00671 00672 unordered_multiset(const _Base& __x) 00673 : _Base(__x) { } 00674 00675 unordered_multiset(unordered_multiset&&) = default; 00676 00677 explicit 00678 unordered_multiset(const allocator_type& __a) 00679 : _Base(__a) { } 00680 00681 unordered_multiset(const unordered_multiset& __uset, 00682 const allocator_type& __a) 00683 : _Base(__uset, __a) { } 00684 00685 unordered_multiset(unordered_multiset&& __uset, 00686 const allocator_type& __a) 00687 : _Safe(std::move(__uset._M_safe()), __a), 00688 _Base(std::move(__uset._M_base()), __a) { } 00689 00690 unordered_multiset(initializer_list<value_type> __l, 00691 size_type __n = 0, 00692 const hasher& __hf = hasher(), 00693 const key_equal& __eql = key_equal(), 00694 const allocator_type& __a = allocator_type()) 00695 : _Base(__l, __n, __hf, __eql, __a) { } 00696 00697 unordered_multiset(size_type __n, const allocator_type& __a) 00698 : unordered_multiset(__n, hasher(), key_equal(), __a) 00699 { } 00700 00701 unordered_multiset(size_type __n, const hasher& __hf, 00702 const allocator_type& __a) 00703 : unordered_multiset(__n, __hf, key_equal(), __a) 00704 { } 00705 00706 template<typename _InputIterator> 00707 unordered_multiset(_InputIterator __first, _InputIterator __last, 00708 size_type __n, 00709 const allocator_type& __a) 00710 : unordered_multiset(__first, __last, __n, hasher(), key_equal(), __a) 00711 { } 00712 00713 template<typename _InputIterator> 00714 unordered_multiset(_InputIterator __first, _InputIterator __last, 00715 size_type __n, const hasher& __hf, 00716 const allocator_type& __a) 00717 : unordered_multiset(__first, __last, __n, __hf, key_equal(), __a) 00718 { } 00719 00720 unordered_multiset(initializer_list<value_type> __l, 00721 size_type __n, 00722 const allocator_type& __a) 00723 : unordered_multiset(__l, __n, hasher(), key_equal(), __a) 00724 { } 00725 00726 unordered_multiset(initializer_list<value_type> __l, 00727 size_type __n, const hasher& __hf, 00728 const allocator_type& __a) 00729 : unordered_multiset(__l, __n, __hf, key_equal(), __a) 00730 { } 00731 00732 ~unordered_multiset() = default; 00733 00734 unordered_multiset& 00735 operator=(const unordered_multiset&) = default; 00736 00737 unordered_multiset& 00738 operator=(unordered_multiset&&) = default; 00739 00740 unordered_multiset& 00741 operator=(initializer_list<value_type> __l) 00742 { 00743 this->_M_base() = __l; 00744 this->_M_invalidate_all(); 00745 return *this; 00746 } 00747 00748 void 00749 swap(unordered_multiset& __x) 00750 noexcept( noexcept(declval<_Base&>().swap(__x)) ) 00751 { 00752 _Safe::_M_swap(__x); 00753 _Base::swap(__x); 00754 } 00755 00756 void 00757 clear() noexcept 00758 { 00759 _Base::clear(); 00760 this->_M_invalidate_all(); 00761 } 00762 00763 iterator 00764 begin() noexcept 00765 { return iterator(_Base::begin(), this); } 00766 00767 const_iterator 00768 begin() const noexcept 00769 { return const_iterator(_Base::begin(), this); } 00770 00771 iterator 00772 end() noexcept 00773 { return iterator(_Base::end(), this); } 00774 00775 const_iterator 00776 end() const noexcept 00777 { return const_iterator(_Base::end(), this); } 00778 00779 const_iterator 00780 cbegin() const noexcept 00781 { return const_iterator(_Base::begin(), this); } 00782 00783 const_iterator 00784 cend() const noexcept 00785 { return const_iterator(_Base::end(), this); } 00786 00787 // local versions 00788 local_iterator 00789 begin(size_type __b) 00790 { 00791 __glibcxx_check_bucket_index(__b); 00792 return local_iterator(_Base::begin(__b), this); 00793 } 00794 00795 local_iterator 00796 end(size_type __b) 00797 { 00798 __glibcxx_check_bucket_index(__b); 00799 return local_iterator(_Base::end(__b), this); 00800 } 00801 00802 const_local_iterator 00803 begin(size_type __b) const 00804 { 00805 __glibcxx_check_bucket_index(__b); 00806 return const_local_iterator(_Base::begin(__b), this); 00807 } 00808 00809 const_local_iterator 00810 end(size_type __b) const 00811 { 00812 __glibcxx_check_bucket_index(__b); 00813 return const_local_iterator(_Base::end(__b), this); 00814 } 00815 00816 const_local_iterator 00817 cbegin(size_type __b) const 00818 { 00819 __glibcxx_check_bucket_index(__b); 00820 return const_local_iterator(_Base::cbegin(__b), this); 00821 } 00822 00823 const_local_iterator 00824 cend(size_type __b) const 00825 { 00826 __glibcxx_check_bucket_index(__b); 00827 return const_local_iterator(_Base::cend(__b), this); 00828 } 00829 00830 size_type 00831 bucket_size(size_type __b) const 00832 { 00833 __glibcxx_check_bucket_index(__b); 00834 return _Base::bucket_size(__b); 00835 } 00836 00837 float 00838 max_load_factor() const noexcept 00839 { return _Base::max_load_factor(); } 00840 00841 void 00842 max_load_factor(float __f) 00843 { 00844 __glibcxx_check_max_load_factor(__f); 00845 _Base::max_load_factor(__f); 00846 } 00847 00848 template<typename... _Args> 00849 iterator 00850 emplace(_Args&&... __args) 00851 { 00852 size_type __bucket_count = this->bucket_count(); 00853 _Base_iterator __it 00854 = _Base::emplace(std::forward<_Args>(__args)...); 00855 _M_check_rehashed(__bucket_count); 00856 return iterator(__it, this); 00857 } 00858 00859 template<typename... _Args> 00860 iterator 00861 emplace_hint(const_iterator __hint, _Args&&... __args) 00862 { 00863 __glibcxx_check_insert(__hint); 00864 size_type __bucket_count = this->bucket_count(); 00865 _Base_iterator __it = _Base::emplace_hint(__hint.base(), 00866 std::forward<_Args>(__args)...); 00867 _M_check_rehashed(__bucket_count); 00868 return iterator(__it, this); 00869 } 00870 00871 iterator 00872 insert(const value_type& __obj) 00873 { 00874 size_type __bucket_count = this->bucket_count(); 00875 _Base_iterator __it = _Base::insert(__obj); 00876 _M_check_rehashed(__bucket_count); 00877 return iterator(__it, this); 00878 } 00879 00880 iterator 00881 insert(const_iterator __hint, const value_type& __obj) 00882 { 00883 __glibcxx_check_insert(__hint); 00884 size_type __bucket_count = this->bucket_count(); 00885 _Base_iterator __it = _Base::insert(__hint.base(), __obj); 00886 _M_check_rehashed(__bucket_count); 00887 return iterator(__it, this); 00888 } 00889 00890 iterator 00891 insert(value_type&& __obj) 00892 { 00893 size_type __bucket_count = this->bucket_count(); 00894 _Base_iterator __it = _Base::insert(std::move(__obj)); 00895 _M_check_rehashed(__bucket_count); 00896 return iterator(__it, this); 00897 } 00898 00899 iterator 00900 insert(const_iterator __hint, value_type&& __obj) 00901 { 00902 __glibcxx_check_insert(__hint); 00903 size_type __bucket_count = this->bucket_count(); 00904 _Base_iterator __it = _Base::insert(__hint.base(), std::move(__obj)); 00905 _M_check_rehashed(__bucket_count); 00906 return iterator(__it, this); 00907 } 00908 00909 void 00910 insert(std::initializer_list<value_type> __l) 00911 { 00912 size_type __bucket_count = this->bucket_count(); 00913 _Base::insert(__l); 00914 _M_check_rehashed(__bucket_count); 00915 } 00916 00917 template<typename _InputIterator> 00918 void 00919 insert(_InputIterator __first, _InputIterator __last) 00920 { 00921 typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist; 00922 __glibcxx_check_valid_range2(__first, __last, __dist); 00923 size_type __bucket_count = this->bucket_count(); 00924 00925 if (__dist.second >= __gnu_debug::__dp_sign) 00926 _Base::insert(__gnu_debug::__unsafe(__first), 00927 __gnu_debug::__unsafe(__last)); 00928 else 00929 _Base::insert(__first, __last); 00930 00931 _M_check_rehashed(__bucket_count); 00932 } 00933 00934 #if __cplusplus > 201402L 00935 using node_type = typename _Base::node_type; 00936 00937 node_type 00938 extract(const_iterator __position) 00939 { 00940 __glibcxx_check_erase(__position); 00941 _Base_const_iterator __victim = __position.base(); 00942 this->_M_invalidate_if( 00943 [__victim](_Base_const_iterator __it) { return __it == __victim; } 00944 ); 00945 this->_M_invalidate_local_if( 00946 [__victim](_Base_const_local_iterator __it) { 00947 return __it._M_curr() == __victim._M_cur; 00948 }); 00949 return _Base::extract(__position.base()); 00950 } 00951 00952 node_type 00953 extract(const key_type& __key) 00954 { 00955 const auto __position = find(__key); 00956 if (__position != end()) 00957 return extract(__position); 00958 return {}; 00959 } 00960 00961 iterator 00962 insert(node_type&& __nh) 00963 { return iterator(_Base::insert(std::move(__nh)), this); } 00964 00965 iterator 00966 insert(const_iterator __hint, node_type&& __nh) 00967 { 00968 __glibcxx_check_insert(__hint); 00969 return iterator(_Base::insert(__hint.base(), std::move(__nh)), this); 00970 } 00971 00972 using _Base::merge; 00973 #endif // C++17 00974 00975 iterator 00976 find(const key_type& __key) 00977 { return iterator(_Base::find(__key), this); } 00978 00979 const_iterator 00980 find(const key_type& __key) const 00981 { return const_iterator(_Base::find(__key), this); } 00982 00983 std::pair<iterator, iterator> 00984 equal_range(const key_type& __key) 00985 { 00986 std::pair<_Base_iterator, _Base_iterator> __res 00987 = _Base::equal_range(__key); 00988 return std::make_pair(iterator(__res.first, this), 00989 iterator(__res.second, this)); 00990 } 00991 00992 std::pair<const_iterator, const_iterator> 00993 equal_range(const key_type& __key) const 00994 { 00995 std::pair<_Base_const_iterator, _Base_const_iterator> 00996 __res = _Base::equal_range(__key); 00997 return std::make_pair(const_iterator(__res.first, this), 00998 const_iterator(__res.second, this)); 00999 } 01000 01001 size_type 01002 erase(const key_type& __key) 01003 { 01004 size_type __ret(0); 01005 std::pair<_Base_iterator, _Base_iterator> __pair = 01006 _Base::equal_range(__key); 01007 for (_Base_iterator __victim = __pair.first; __victim != __pair.second;) 01008 { 01009 this->_M_invalidate_if([__victim](_Base_const_iterator __it) 01010 { return __it == __victim; }); 01011 this->_M_invalidate_local_if( 01012 [__victim](_Base_const_local_iterator __it) 01013 { return __it._M_curr() == __victim._M_cur; }); 01014 _Base::erase(__victim++); 01015 ++__ret; 01016 } 01017 return __ret; 01018 } 01019 01020 iterator 01021 erase(const_iterator __it) 01022 { 01023 __glibcxx_check_erase(__it); 01024 _Base_const_iterator __victim = __it.base(); 01025 this->_M_invalidate_if([__victim](_Base_const_iterator __it) 01026 { return __it == __victim; }); 01027 this->_M_invalidate_local_if( 01028 [__victim](_Base_const_local_iterator __it) 01029 { return __it._M_curr() == __victim._M_cur; }); 01030 return iterator(_Base::erase(__it.base()), this); 01031 } 01032 01033 iterator 01034 erase(iterator __it) 01035 { return erase(const_iterator(__it)); } 01036 01037 iterator 01038 erase(const_iterator __first, const_iterator __last) 01039 { 01040 __glibcxx_check_erase_range(__first, __last); 01041 for (_Base_const_iterator __tmp = __first.base(); 01042 __tmp != __last.base(); ++__tmp) 01043 { 01044 _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(), 01045 _M_message(__gnu_debug::__msg_valid_range) 01046 ._M_iterator(__first, "first") 01047 ._M_iterator(__last, "last")); 01048 this->_M_invalidate_if([__tmp](_Base_const_iterator __it) 01049 { return __it == __tmp; }); 01050 this->_M_invalidate_local_if( 01051 [__tmp](_Base_const_local_iterator __it) 01052 { return __it._M_curr() == __tmp._M_cur; }); 01053 } 01054 return iterator(_Base::erase(__first.base(), 01055 __last.base()), this); 01056 } 01057 01058 _Base& 01059 _M_base() noexcept { return *this; } 01060 01061 const _Base& 01062 _M_base() const noexcept { return *this; } 01063 01064 private: 01065 void 01066 _M_check_rehashed(size_type __prev_count) 01067 { 01068 if (__prev_count != this->bucket_count()) 01069 this->_M_invalidate_locals(); 01070 } 01071 }; 01072 01073 #if __cpp_deduction_guides >= 201606 01074 01075 template<typename _InputIterator, 01076 typename _Hash = 01077 hash<typename iterator_traits<_InputIterator>::value_type>, 01078 typename _Pred = 01079 equal_to<typename iterator_traits<_InputIterator>::value_type>, 01080 typename _Allocator = 01081 allocator<typename iterator_traits<_InputIterator>::value_type>, 01082 typename = _RequireInputIter<_InputIterator>, 01083 typename = _RequireAllocator<_Allocator>> 01084 unordered_multiset(_InputIterator, _InputIterator, 01085 unordered_multiset<int>::size_type = {}, 01086 _Hash = _Hash(), _Pred = _Pred(), 01087 _Allocator = _Allocator()) 01088 -> unordered_multiset<typename iterator_traits<_InputIterator>::value_type, 01089 _Hash, _Pred, _Allocator>; 01090 01091 template<typename _Tp, typename _Hash = hash<_Tp>, 01092 typename _Pred = equal_to<_Tp>, 01093 typename _Allocator = allocator<_Tp>, 01094 typename = _RequireAllocator<_Allocator>> 01095 unordered_multiset(initializer_list<_Tp>, 01096 unordered_multiset<int>::size_type = {}, 01097 _Hash = _Hash(), _Pred = _Pred(), 01098 _Allocator = _Allocator()) 01099 -> unordered_multiset<_Tp, _Hash, _Pred, _Allocator>; 01100 01101 template<typename _InputIterator, typename _Allocator, 01102 typename = _RequireInputIter<_InputIterator>, 01103 typename = _RequireAllocator<_Allocator>> 01104 unordered_multiset(_InputIterator, _InputIterator, 01105 unordered_multiset<int>::size_type, _Allocator) 01106 -> unordered_multiset<typename iterator_traits<_InputIterator>::value_type, 01107 hash<typename 01108 iterator_traits<_InputIterator>::value_type>, 01109 equal_to<typename 01110 iterator_traits<_InputIterator>::value_type>, 01111 _Allocator>; 01112 01113 template<typename _InputIterator, typename _Hash, typename _Allocator, 01114 typename = _RequireInputIter<_InputIterator>, 01115 typename = _RequireAllocator<_Allocator>> 01116 unordered_multiset(_InputIterator, _InputIterator, 01117 unordered_multiset<int>::size_type, 01118 _Hash, _Allocator) 01119 -> unordered_multiset<typename 01120 iterator_traits<_InputIterator>::value_type, 01121 _Hash, 01122 equal_to< 01123 typename 01124 iterator_traits<_InputIterator>::value_type>, 01125 _Allocator>; 01126 01127 template<typename _Tp, typename _Allocator, 01128 typename = _RequireAllocator<_Allocator>> 01129 unordered_multiset(initializer_list<_Tp>, 01130 unordered_multiset<int>::size_type, _Allocator) 01131 -> unordered_multiset<_Tp, hash<_Tp>, equal_to<_Tp>, _Allocator>; 01132 01133 template<typename _Tp, typename _Hash, typename _Allocator, 01134 typename = _RequireAllocator<_Allocator>> 01135 unordered_multiset(initializer_list<_Tp>, 01136 unordered_multiset<int>::size_type, _Hash, _Allocator) 01137 -> unordered_multiset<_Tp, _Hash, equal_to<_Tp>, _Allocator>; 01138 01139 #endif 01140 01141 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc> 01142 inline void 01143 swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, 01144 unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) 01145 noexcept(noexcept(__x.swap(__y))) 01146 { __x.swap(__y); } 01147 01148 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc> 01149 inline bool 01150 operator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, 01151 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) 01152 { return __x._M_base() == __y._M_base(); } 01153 01154 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc> 01155 inline bool 01156 operator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, 01157 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) 01158 { return !(__x == __y); } 01159 01160 } // namespace __debug 01161 } // namespace std 01162 01163 #endif // C++11 01164 01165 #endif