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