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