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