libstdc++
|
00001 // Debugging unordered_map/unordered_multimap implementation -*- C++ -*- 00002 00003 // Copyright (C) 2003-2014 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 #if __cplusplus < 201103L 00033 # include <bits/c++0x_warning.h> 00034 #else 00035 # include <unordered_map> 00036 00037 #include <debug/safe_unordered_container.h> 00038 #include <debug/safe_iterator.h> 00039 #include <debug/safe_local_iterator.h> 00040 00041 namespace std _GLIBCXX_VISIBILITY(default) 00042 { 00043 namespace __debug 00044 { 00045 /// Class std::unordered_map with safety/checking/debug instrumentation. 00046 template<typename _Key, typename _Tp, 00047 typename _Hash = std::hash<_Key>, 00048 typename _Pred = std::equal_to<_Key>, 00049 typename _Alloc = std::allocator<std::pair<const _Key, _Tp> > > 00050 class unordered_map 00051 : public _GLIBCXX_STD_C::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>, 00052 public __gnu_debug::_Safe_unordered_container<unordered_map<_Key, _Tp, 00053 _Hash, _Pred, _Alloc> > 00054 { 00055 typedef _GLIBCXX_STD_C::unordered_map<_Key, _Tp, _Hash, 00056 _Pred, _Alloc> _Base; 00057 typedef __gnu_debug::_Safe_unordered_container<unordered_map> _Safe_base; 00058 typedef typename _Base::const_iterator _Base_const_iterator; 00059 typedef typename _Base::iterator _Base_iterator; 00060 typedef typename _Base::const_local_iterator _Base_const_local_iterator; 00061 typedef typename _Base::local_iterator _Base_local_iterator; 00062 00063 typedef __gnu_cxx::__alloc_traits<typename 00064 _Base::allocator_type> _Alloc_traits; 00065 00066 public: 00067 typedef typename _Base::size_type size_type; 00068 typedef typename _Base::hasher hasher; 00069 typedef typename _Base::key_equal key_equal; 00070 typedef typename _Base::allocator_type allocator_type; 00071 00072 typedef typename _Base::key_type key_type; 00073 typedef typename _Base::value_type value_type; 00074 00075 typedef __gnu_debug::_Safe_iterator<_Base_iterator, 00076 unordered_map> iterator; 00077 typedef __gnu_debug::_Safe_iterator<_Base_const_iterator, 00078 unordered_map> const_iterator; 00079 typedef __gnu_debug::_Safe_local_iterator<_Base_local_iterator, 00080 unordered_map> local_iterator; 00081 typedef __gnu_debug::_Safe_local_iterator<_Base_const_local_iterator, 00082 unordered_map> const_local_iterator; 00083 00084 explicit 00085 unordered_map(size_type __n = 10, 00086 const hasher& __hf = hasher(), 00087 const key_equal& __eql = key_equal(), 00088 const allocator_type& __a = allocator_type()) 00089 : _Base(__n, __hf, __eql, __a) { } 00090 00091 template<typename _InputIterator> 00092 unordered_map(_InputIterator __first, _InputIterator __last, 00093 size_type __n = 0, 00094 const hasher& __hf = hasher(), 00095 const key_equal& __eql = key_equal(), 00096 const allocator_type& __a = allocator_type()) 00097 : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first, 00098 __last)), 00099 __gnu_debug::__base(__last), __n, 00100 __hf, __eql, __a) { } 00101 00102 unordered_map(const unordered_map&) = default; 00103 00104 unordered_map(const _Base& __x) 00105 : _Base(__x) { } 00106 00107 unordered_map(unordered_map&&) = default; 00108 00109 explicit 00110 unordered_map(const allocator_type& __a) 00111 : _Base(__a) 00112 { } 00113 00114 unordered_map(const unordered_map& __umap, 00115 const allocator_type& __a) 00116 : _Base(__umap._M_base(), __a) 00117 { } 00118 00119 unordered_map(unordered_map&& __umap, 00120 const allocator_type& __a) 00121 : _Base(std::move(__umap._M_base()), __a) 00122 { } 00123 00124 unordered_map(initializer_list<value_type> __l, 00125 size_type __n = 0, 00126 const hasher& __hf = hasher(), 00127 const key_equal& __eql = key_equal(), 00128 const allocator_type& __a = allocator_type()) 00129 : _Base(__l, __n, __hf, __eql, __a) { } 00130 00131 ~unordered_map() noexcept { } 00132 00133 unordered_map& 00134 operator=(const unordered_map& __x) 00135 { 00136 _M_base() = __x._M_base(); 00137 this->_M_invalidate_all(); 00138 return *this; 00139 } 00140 00141 unordered_map& 00142 operator=(unordered_map&& __x) 00143 noexcept(_Alloc_traits::_S_nothrow_move()) 00144 { 00145 __glibcxx_check_self_move_assign(__x); 00146 bool __xfer_memory = _Alloc_traits::_S_propagate_on_move_assign() 00147 || __x.get_allocator() == this->get_allocator(); 00148 _M_base() = std::move(__x._M_base()); 00149 if (__xfer_memory) 00150 this->_M_swap(__x); 00151 else 00152 this->_M_invalidate_all(); 00153 __x._M_invalidate_all(); 00154 return *this; 00155 } 00156 00157 unordered_map& 00158 operator=(initializer_list<value_type> __l) 00159 { 00160 _M_base() = __l; 00161 this->_M_invalidate_all(); 00162 return *this; 00163 } 00164 00165 void 00166 swap(unordered_map& __x) 00167 noexcept(_Alloc_traits::_S_nothrow_swap()) 00168 { 00169 if (!_Alloc_traits::_S_propagate_on_swap()) 00170 __glibcxx_check_equal_allocs(__x); 00171 _Base::swap(__x); 00172 _Safe_base::_M_swap(__x); 00173 } 00174 00175 void 00176 clear() noexcept 00177 { 00178 _Base::clear(); 00179 this->_M_invalidate_all(); 00180 } 00181 00182 iterator 00183 begin() noexcept 00184 { return iterator(_Base::begin(), this); } 00185 00186 const_iterator 00187 begin() const noexcept 00188 { return const_iterator(_Base::begin(), this); } 00189 00190 iterator 00191 end() noexcept 00192 { return iterator(_Base::end(), this); } 00193 00194 const_iterator 00195 end() const noexcept 00196 { return const_iterator(_Base::end(), this); } 00197 00198 const_iterator 00199 cbegin() const noexcept 00200 { return const_iterator(_Base::begin(), this); } 00201 00202 const_iterator 00203 cend() const noexcept 00204 { return const_iterator(_Base::end(), this); } 00205 00206 // local versions 00207 local_iterator 00208 begin(size_type __b) 00209 { 00210 __glibcxx_check_bucket_index(__b); 00211 return local_iterator(_Base::begin(__b), this); 00212 } 00213 00214 local_iterator 00215 end(size_type __b) 00216 { 00217 __glibcxx_check_bucket_index(__b); 00218 return local_iterator(_Base::end(__b), this); 00219 } 00220 00221 const_local_iterator 00222 begin(size_type __b) const 00223 { 00224 __glibcxx_check_bucket_index(__b); 00225 return const_local_iterator(_Base::begin(__b), this); 00226 } 00227 00228 const_local_iterator 00229 end(size_type __b) const 00230 { 00231 __glibcxx_check_bucket_index(__b); 00232 return const_local_iterator(_Base::end(__b), this); 00233 } 00234 00235 const_local_iterator 00236 cbegin(size_type __b) const 00237 { 00238 __glibcxx_check_bucket_index(__b); 00239 return const_local_iterator(_Base::cbegin(__b), this); 00240 } 00241 00242 const_local_iterator 00243 cend(size_type __b) const 00244 { 00245 __glibcxx_check_bucket_index(__b); 00246 return const_local_iterator(_Base::cend(__b), this); 00247 } 00248 00249 size_type 00250 bucket_size(size_type __b) const 00251 { 00252 __glibcxx_check_bucket_index(__b); 00253 return _Base::bucket_size(__b); 00254 } 00255 00256 float 00257 max_load_factor() const noexcept 00258 { return _Base::max_load_factor(); } 00259 00260 void 00261 max_load_factor(float __f) 00262 { 00263 __glibcxx_check_max_load_factor(__f); 00264 _Base::max_load_factor(__f); 00265 } 00266 00267 template<typename... _Args> 00268 std::pair<iterator, bool> 00269 emplace(_Args&&... __args) 00270 { 00271 size_type __bucket_count = this->bucket_count(); 00272 std::pair<_Base_iterator, bool> __res 00273 = _Base::emplace(std::forward<_Args>(__args)...); 00274 _M_check_rehashed(__bucket_count); 00275 return std::make_pair(iterator(__res.first, this), __res.second); 00276 } 00277 00278 template<typename... _Args> 00279 iterator 00280 emplace_hint(const_iterator __hint, _Args&&... __args) 00281 { 00282 __glibcxx_check_insert(__hint); 00283 size_type __bucket_count = this->bucket_count(); 00284 _Base_iterator __it = _Base::emplace_hint(__hint.base(), 00285 std::forward<_Args>(__args)...); 00286 _M_check_rehashed(__bucket_count); 00287 return iterator(__it, this); 00288 } 00289 00290 std::pair<iterator, bool> 00291 insert(const value_type& __obj) 00292 { 00293 size_type __bucket_count = this->bucket_count(); 00294 std::pair<_Base_iterator, bool> __res = _Base::insert(__obj); 00295 _M_check_rehashed(__bucket_count); 00296 return std::make_pair(iterator(__res.first, this), __res.second); 00297 } 00298 00299 iterator 00300 insert(const_iterator __hint, const value_type& __obj) 00301 { 00302 __glibcxx_check_insert(__hint); 00303 size_type __bucket_count = this->bucket_count(); 00304 _Base_iterator __it = _Base::insert(__hint.base(), __obj); 00305 _M_check_rehashed(__bucket_count); 00306 return iterator(__it, this); 00307 } 00308 00309 template<typename _Pair, typename = typename 00310 std::enable_if<std::is_constructible<value_type, 00311 _Pair&&>::value>::type> 00312 std::pair<iterator, bool> 00313 insert(_Pair&& __obj) 00314 { 00315 size_type __bucket_count = this->bucket_count(); 00316 std::pair<_Base_iterator, bool> __res = 00317 _Base::insert(std::forward<_Pair>(__obj)); 00318 _M_check_rehashed(__bucket_count); 00319 return std::make_pair(iterator(__res.first, this), __res.second); 00320 } 00321 00322 template<typename _Pair, typename = typename 00323 std::enable_if<std::is_constructible<value_type, 00324 _Pair&&>::value>::type> 00325 iterator 00326 insert(const_iterator __hint, _Pair&& __obj) 00327 { 00328 __glibcxx_check_insert(__hint); 00329 size_type __bucket_count = this->bucket_count(); 00330 _Base_iterator __it = 00331 _Base::insert(__hint.base(), std::forward<_Pair>(__obj)); 00332 _M_check_rehashed(__bucket_count); 00333 return iterator(__it, this); 00334 } 00335 00336 void 00337 insert(std::initializer_list<value_type> __l) 00338 { 00339 size_type __bucket_count = this->bucket_count(); 00340 _Base::insert(__l); 00341 _M_check_rehashed(__bucket_count); 00342 } 00343 00344 template<typename _InputIterator> 00345 void 00346 insert(_InputIterator __first, _InputIterator __last) 00347 { 00348 __glibcxx_check_valid_range(__first, __last); 00349 size_type __bucket_count = this->bucket_count(); 00350 _Base::insert(__gnu_debug::__base(__first), 00351 __gnu_debug::__base(__last)); 00352 _M_check_rehashed(__bucket_count); 00353 } 00354 00355 iterator 00356 find(const key_type& __key) 00357 { return iterator(_Base::find(__key), this); } 00358 00359 const_iterator 00360 find(const key_type& __key) const 00361 { return const_iterator(_Base::find(__key), this); } 00362 00363 std::pair<iterator, iterator> 00364 equal_range(const key_type& __key) 00365 { 00366 std::pair<_Base_iterator, _Base_iterator> __res = 00367 _Base::equal_range(__key); 00368 return std::make_pair(iterator(__res.first, this), 00369 iterator(__res.second, this)); 00370 } 00371 00372 std::pair<const_iterator, const_iterator> 00373 equal_range(const key_type& __key) const 00374 { 00375 std::pair<_Base_const_iterator, _Base_const_iterator> __res = 00376 _Base::equal_range(__key); 00377 return std::make_pair(const_iterator(__res.first, this), 00378 const_iterator(__res.second, this)); 00379 } 00380 00381 size_type 00382 erase(const key_type& __key) 00383 { 00384 size_type __ret(0); 00385 _Base_iterator __victim(_Base::find(__key)); 00386 if (__victim != _Base::end()) 00387 { 00388 this->_M_invalidate_if([__victim](_Base_const_iterator __it) 00389 { return __it == __victim; }); 00390 this->_M_invalidate_local_if( 00391 [__victim](_Base_const_local_iterator __it) 00392 { return __it._M_curr() == __victim._M_cur; }); 00393 size_type __bucket_count = this->bucket_count(); 00394 _Base::erase(__victim); 00395 _M_check_rehashed(__bucket_count); 00396 __ret = 1; 00397 } 00398 return __ret; 00399 } 00400 00401 iterator 00402 erase(const_iterator __it) 00403 { 00404 __glibcxx_check_erase(__it); 00405 _Base_const_iterator __victim = __it.base(); 00406 this->_M_invalidate_if([__victim](_Base_const_iterator __it) 00407 { return __it == __victim; }); 00408 this->_M_invalidate_local_if( 00409 [__victim](_Base_const_local_iterator __it) 00410 { return __it._M_curr() == __victim._M_cur; }); 00411 size_type __bucket_count = this->bucket_count(); 00412 _Base_iterator __next = _Base::erase(__it.base()); 00413 _M_check_rehashed(__bucket_count); 00414 return iterator(__next, this); 00415 } 00416 00417 iterator 00418 erase(iterator __it) 00419 { return erase(const_iterator(__it)); } 00420 00421 iterator 00422 erase(const_iterator __first, const_iterator __last) 00423 { 00424 __glibcxx_check_erase_range(__first, __last); 00425 for (_Base_const_iterator __tmp = __first.base(); 00426 __tmp != __last.base(); ++__tmp) 00427 { 00428 _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(), 00429 _M_message(__gnu_debug::__msg_valid_range) 00430 ._M_iterator(__first, "first") 00431 ._M_iterator(__last, "last")); 00432 this->_M_invalidate_if([__tmp](_Base_const_iterator __it) 00433 { return __it == __tmp; }); 00434 this->_M_invalidate_local_if( 00435 [__tmp](_Base_const_local_iterator __it) 00436 { return __it._M_curr() == __tmp._M_cur; }); 00437 } 00438 size_type __bucket_count = this->bucket_count(); 00439 _Base_iterator __next = _Base::erase(__first.base(), __last.base()); 00440 _M_check_rehashed(__bucket_count); 00441 return iterator(__next, this); 00442 } 00443 00444 _Base& 00445 _M_base() noexcept { return *this; } 00446 00447 const _Base& 00448 _M_base() const noexcept { return *this; } 00449 00450 private: 00451 void 00452 _M_invalidate_locals() 00453 { 00454 _Base_local_iterator __local_end = _Base::end(0); 00455 this->_M_invalidate_local_if( 00456 [__local_end](_Base_const_local_iterator __it) 00457 { return __it != __local_end; }); 00458 } 00459 00460 void 00461 _M_invalidate_all() 00462 { 00463 _Base_iterator __end = _Base::end(); 00464 this->_M_invalidate_if([__end](_Base_const_iterator __it) 00465 { return __it != __end; }); 00466 _M_invalidate_locals(); 00467 } 00468 00469 void 00470 _M_check_rehashed(size_type __prev_count) 00471 { 00472 if (__prev_count != this->bucket_count()) 00473 _M_invalidate_locals(); 00474 } 00475 }; 00476 00477 template<typename _Key, typename _Tp, typename _Hash, 00478 typename _Pred, typename _Alloc> 00479 inline void 00480 swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 00481 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 00482 { __x.swap(__y); } 00483 00484 template<typename _Key, typename _Tp, typename _Hash, 00485 typename _Pred, typename _Alloc> 00486 inline bool 00487 operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 00488 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 00489 { return __x._M_base() == __y._M_base(); } 00490 00491 template<typename _Key, typename _Tp, typename _Hash, 00492 typename _Pred, typename _Alloc> 00493 inline bool 00494 operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 00495 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 00496 { return !(__x == __y); } 00497 00498 00499 /// Class std::unordered_multimap with safety/checking/debug instrumentation. 00500 template<typename _Key, typename _Tp, 00501 typename _Hash = std::hash<_Key>, 00502 typename _Pred = std::equal_to<_Key>, 00503 typename _Alloc = std::allocator<std::pair<const _Key, _Tp> > > 00504 class unordered_multimap 00505 : public _GLIBCXX_STD_C::unordered_multimap<_Key, _Tp, _Hash, 00506 _Pred, _Alloc>, 00507 public __gnu_debug::_Safe_unordered_container<unordered_multimap<_Key, 00508 _Tp, _Hash, _Pred, _Alloc> > 00509 { 00510 typedef _GLIBCXX_STD_C::unordered_multimap<_Key, _Tp, _Hash, 00511 _Pred, _Alloc> _Base; 00512 typedef __gnu_debug::_Safe_unordered_container<unordered_multimap> 00513 _Safe_base; 00514 typedef typename _Base::const_iterator _Base_const_iterator; 00515 typedef typename _Base::iterator _Base_iterator; 00516 typedef typename _Base::const_local_iterator _Base_const_local_iterator; 00517 typedef typename _Base::local_iterator _Base_local_iterator; 00518 00519 typedef __gnu_cxx::__alloc_traits<typename 00520 _Base::allocator_type> _Alloc_traits; 00521 00522 public: 00523 typedef typename _Base::size_type size_type; 00524 typedef typename _Base::hasher hasher; 00525 typedef typename _Base::key_equal key_equal; 00526 typedef typename _Base::allocator_type allocator_type; 00527 00528 typedef typename _Base::key_type key_type; 00529 typedef typename _Base::value_type value_type; 00530 00531 typedef __gnu_debug::_Safe_iterator<_Base_iterator, 00532 unordered_multimap> iterator; 00533 typedef __gnu_debug::_Safe_iterator<_Base_const_iterator, 00534 unordered_multimap> const_iterator; 00535 typedef __gnu_debug::_Safe_local_iterator< 00536 _Base_local_iterator, unordered_multimap> local_iterator; 00537 typedef __gnu_debug::_Safe_local_iterator< 00538 _Base_const_local_iterator, unordered_multimap> const_local_iterator; 00539 00540 explicit 00541 unordered_multimap(size_type __n = 10, 00542 const hasher& __hf = hasher(), 00543 const key_equal& __eql = key_equal(), 00544 const allocator_type& __a = allocator_type()) 00545 : _Base(__n, __hf, __eql, __a) { } 00546 00547 template<typename _InputIterator> 00548 unordered_multimap(_InputIterator __first, _InputIterator __last, 00549 size_type __n = 0, 00550 const hasher& __hf = hasher(), 00551 const key_equal& __eql = key_equal(), 00552 const allocator_type& __a = allocator_type()) 00553 : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first, 00554 __last)), 00555 __gnu_debug::__base(__last), __n, 00556 __hf, __eql, __a) { } 00557 00558 unordered_multimap(const unordered_multimap&) = default; 00559 00560 unordered_multimap(const _Base& __x) 00561 : _Base(__x) { } 00562 00563 unordered_multimap(unordered_multimap&&) = default; 00564 00565 explicit 00566 unordered_multimap(const allocator_type& __a) 00567 : _Base(__a) 00568 { } 00569 00570 unordered_multimap(const unordered_multimap& __umap, 00571 const allocator_type& __a) 00572 : _Base(__umap._M_base(), __a) 00573 { } 00574 00575 unordered_multimap(unordered_multimap&& __umap, 00576 const allocator_type& __a) 00577 : _Base(std::move(__umap._M_base()), __a) 00578 { } 00579 00580 unordered_multimap(initializer_list<value_type> __l, 00581 size_type __n = 0, 00582 const hasher& __hf = hasher(), 00583 const key_equal& __eql = key_equal(), 00584 const allocator_type& __a = allocator_type()) 00585 : _Base(__l, __n, __hf, __eql, __a) { } 00586 00587 ~unordered_multimap() noexcept { } 00588 00589 unordered_multimap& 00590 operator=(const unordered_multimap& __x) 00591 { 00592 _M_base() = __x._M_base(); 00593 this->_M_invalidate_all(); 00594 return *this; 00595 } 00596 00597 unordered_multimap& 00598 operator=(unordered_multimap&& __x) 00599 noexcept(_Alloc_traits::_S_nothrow_move()) 00600 { 00601 __glibcxx_check_self_move_assign(__x); 00602 bool __xfer_memory = _Alloc_traits::_S_propagate_on_move_assign() 00603 || __x.get_allocator() == this->get_allocator(); 00604 _M_base() = std::move(__x._M_base()); 00605 if (__xfer_memory) 00606 this->_M_swap(__x); 00607 else 00608 this->_M_invalidate_all(); 00609 __x._M_invalidate_all(); 00610 return *this; 00611 } 00612 00613 unordered_multimap& 00614 operator=(initializer_list<value_type> __l) 00615 { 00616 _M_base() = __l; 00617 this->_M_invalidate_all(); 00618 return *this; 00619 } 00620 00621 void 00622 swap(unordered_multimap& __x) 00623 noexcept(_Alloc_traits::_S_nothrow_swap()) 00624 { 00625 if (!_Alloc_traits::_S_propagate_on_swap()) 00626 __glibcxx_check_equal_allocs(__x); 00627 _Base::swap(__x); 00628 _Safe_base::_M_swap(__x); 00629 } 00630 00631 void 00632 clear() noexcept 00633 { 00634 _Base::clear(); 00635 this->_M_invalidate_all(); 00636 } 00637 00638 iterator 00639 begin() noexcept 00640 { return iterator(_Base::begin(), this); } 00641 00642 const_iterator 00643 begin() const noexcept 00644 { return const_iterator(_Base::begin(), this); } 00645 00646 iterator 00647 end() noexcept 00648 { return iterator(_Base::end(), this); } 00649 00650 const_iterator 00651 end() const noexcept 00652 { return const_iterator(_Base::end(), this); } 00653 00654 const_iterator 00655 cbegin() const noexcept 00656 { return const_iterator(_Base::begin(), this); } 00657 00658 const_iterator 00659 cend() const noexcept 00660 { return const_iterator(_Base::end(), this); } 00661 00662 // local versions 00663 local_iterator 00664 begin(size_type __b) 00665 { 00666 __glibcxx_check_bucket_index(__b); 00667 return local_iterator(_Base::begin(__b), this); 00668 } 00669 00670 local_iterator 00671 end(size_type __b) 00672 { 00673 __glibcxx_check_bucket_index(__b); 00674 return local_iterator(_Base::end(__b), this); 00675 } 00676 00677 const_local_iterator 00678 begin(size_type __b) const 00679 { 00680 __glibcxx_check_bucket_index(__b); 00681 return const_local_iterator(_Base::begin(__b), this); 00682 } 00683 00684 const_local_iterator 00685 end(size_type __b) const 00686 { 00687 __glibcxx_check_bucket_index(__b); 00688 return const_local_iterator(_Base::end(__b), this); 00689 } 00690 00691 const_local_iterator 00692 cbegin(size_type __b) const 00693 { 00694 __glibcxx_check_bucket_index(__b); 00695 return const_local_iterator(_Base::cbegin(__b), this); 00696 } 00697 00698 const_local_iterator 00699 cend(size_type __b) const 00700 { 00701 __glibcxx_check_bucket_index(__b); 00702 return const_local_iterator(_Base::cend(__b), this); 00703 } 00704 00705 size_type 00706 bucket_size(size_type __b) const 00707 { 00708 __glibcxx_check_bucket_index(__b); 00709 return _Base::bucket_size(__b); 00710 } 00711 00712 float 00713 max_load_factor() const noexcept 00714 { return _Base::max_load_factor(); } 00715 00716 void 00717 max_load_factor(float __f) 00718 { 00719 __glibcxx_check_max_load_factor(__f); 00720 _Base::max_load_factor(__f); 00721 } 00722 00723 template<typename... _Args> 00724 iterator 00725 emplace(_Args&&... __args) 00726 { 00727 size_type __bucket_count = this->bucket_count(); 00728 _Base_iterator __it 00729 = _Base::emplace(std::forward<_Args>(__args)...); 00730 _M_check_rehashed(__bucket_count); 00731 return iterator(__it, this); 00732 } 00733 00734 template<typename... _Args> 00735 iterator 00736 emplace_hint(const_iterator __hint, _Args&&... __args) 00737 { 00738 __glibcxx_check_insert(__hint); 00739 size_type __bucket_count = this->bucket_count(); 00740 _Base_iterator __it = _Base::emplace_hint(__hint.base(), 00741 std::forward<_Args>(__args)...); 00742 _M_check_rehashed(__bucket_count); 00743 return iterator(__it, this); 00744 } 00745 00746 iterator 00747 insert(const value_type& __obj) 00748 { 00749 size_type __bucket_count = this->bucket_count(); 00750 _Base_iterator __it = _Base::insert(__obj); 00751 _M_check_rehashed(__bucket_count); 00752 return iterator(__it, this); 00753 } 00754 00755 iterator 00756 insert(const_iterator __hint, const value_type& __obj) 00757 { 00758 __glibcxx_check_insert(__hint); 00759 size_type __bucket_count = this->bucket_count(); 00760 _Base_iterator __it = _Base::insert(__hint.base(), __obj); 00761 _M_check_rehashed(__bucket_count); 00762 return iterator(__it, this); 00763 } 00764 00765 template<typename _Pair, typename = typename 00766 std::enable_if<std::is_constructible<value_type, 00767 _Pair&&>::value>::type> 00768 iterator 00769 insert(_Pair&& __obj) 00770 { 00771 size_type __bucket_count = this->bucket_count(); 00772 _Base_iterator __it = _Base::insert(std::forward<_Pair>(__obj)); 00773 _M_check_rehashed(__bucket_count); 00774 return iterator(__it, this); 00775 } 00776 00777 template<typename _Pair, typename = typename 00778 std::enable_if<std::is_constructible<value_type, 00779 _Pair&&>::value>::type> 00780 iterator 00781 insert(const_iterator __hint, _Pair&& __obj) 00782 { 00783 __glibcxx_check_insert(__hint); 00784 size_type __bucket_count = this->bucket_count(); 00785 _Base_iterator __it = 00786 _Base::insert(__hint.base(), std::forward<_Pair>(__obj)); 00787 _M_check_rehashed(__bucket_count); 00788 return iterator(__it, this); 00789 } 00790 00791 void 00792 insert(std::initializer_list<value_type> __l) 00793 { _Base::insert(__l); } 00794 00795 template<typename _InputIterator> 00796 void 00797 insert(_InputIterator __first, _InputIterator __last) 00798 { 00799 __glibcxx_check_valid_range(__first, __last); 00800 size_type __bucket_count = this->bucket_count(); 00801 _Base::insert(__gnu_debug::__base(__first), 00802 __gnu_debug::__base(__last)); 00803 _M_check_rehashed(__bucket_count); 00804 } 00805 00806 iterator 00807 find(const key_type& __key) 00808 { return iterator(_Base::find(__key), this); } 00809 00810 const_iterator 00811 find(const key_type& __key) const 00812 { return const_iterator(_Base::find(__key), this); } 00813 00814 std::pair<iterator, iterator> 00815 equal_range(const key_type& __key) 00816 { 00817 std::pair<_Base_iterator, _Base_iterator> __res = 00818 _Base::equal_range(__key); 00819 return std::make_pair(iterator(__res.first, this), 00820 iterator(__res.second, this)); 00821 } 00822 00823 std::pair<const_iterator, const_iterator> 00824 equal_range(const key_type& __key) const 00825 { 00826 std::pair<_Base_const_iterator, _Base_const_iterator> __res = 00827 _Base::equal_range(__key); 00828 return std::make_pair(const_iterator(__res.first, this), 00829 const_iterator(__res.second, this)); 00830 } 00831 00832 size_type 00833 erase(const key_type& __key) 00834 { 00835 size_type __ret(0); 00836 size_type __bucket_count = this->bucket_count(); 00837 std::pair<_Base_iterator, _Base_iterator> __pair = 00838 _Base::equal_range(__key); 00839 for (_Base_iterator __victim = __pair.first; __victim != __pair.second;) 00840 { 00841 this->_M_invalidate_if([__victim](_Base_const_iterator __it) 00842 { return __it == __victim; }); 00843 this->_M_invalidate_local_if( 00844 [__victim](_Base_const_local_iterator __it) 00845 { return __it._M_curr() == __victim._M_cur; }); 00846 _Base::erase(__victim++); 00847 ++__ret; 00848 } 00849 _M_check_rehashed(__bucket_count); 00850 return __ret; 00851 } 00852 00853 iterator 00854 erase(const_iterator __it) 00855 { 00856 __glibcxx_check_erase(__it); 00857 _Base_const_iterator __victim = __it.base(); 00858 this->_M_invalidate_if([__victim](_Base_const_iterator __it) 00859 { return __it == __victim; }); 00860 this->_M_invalidate_local_if( 00861 [__victim](_Base_const_local_iterator __it) 00862 { return __it._M_curr() == __victim._M_cur; }); 00863 size_type __bucket_count = this->bucket_count(); 00864 _Base_iterator __next = _Base::erase(__it.base()); 00865 _M_check_rehashed(__bucket_count); 00866 return iterator(__next, this); 00867 } 00868 00869 iterator 00870 erase(iterator __it) 00871 { return erase(const_iterator(__it)); } 00872 00873 iterator 00874 erase(const_iterator __first, const_iterator __last) 00875 { 00876 __glibcxx_check_erase_range(__first, __last); 00877 for (_Base_const_iterator __tmp = __first.base(); 00878 __tmp != __last.base(); ++__tmp) 00879 { 00880 _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(), 00881 _M_message(__gnu_debug::__msg_valid_range) 00882 ._M_iterator(__first, "first") 00883 ._M_iterator(__last, "last")); 00884 this->_M_invalidate_if([__tmp](_Base_const_iterator __it) 00885 { return __it == __tmp; }); 00886 this->_M_invalidate_local_if( 00887 [__tmp](_Base_const_local_iterator __it) 00888 { return __it._M_curr() == __tmp._M_cur; }); 00889 } 00890 size_type __bucket_count = this->bucket_count(); 00891 _Base_iterator __next = _Base::erase(__first.base(), __last.base()); 00892 _M_check_rehashed(__bucket_count); 00893 return iterator(__next, this); 00894 } 00895 00896 _Base& 00897 _M_base() noexcept { return *this; } 00898 00899 const _Base& 00900 _M_base() const noexcept { return *this; } 00901 00902 private: 00903 void 00904 _M_invalidate_locals() 00905 { 00906 _Base_local_iterator __local_end = _Base::end(0); 00907 this->_M_invalidate_local_if( 00908 [__local_end](_Base_const_local_iterator __it) 00909 { return __it != __local_end; }); 00910 } 00911 00912 void 00913 _M_invalidate_all() 00914 { 00915 _Base_iterator __end = _Base::end(); 00916 this->_M_invalidate_if([__end](_Base_const_iterator __it) 00917 { return __it != __end; }); 00918 _M_invalidate_locals(); 00919 } 00920 00921 void 00922 _M_check_rehashed(size_type __prev_count) 00923 { 00924 if (__prev_count != this->bucket_count()) 00925 _M_invalidate_locals(); 00926 } 00927 }; 00928 00929 template<typename _Key, typename _Tp, typename _Hash, 00930 typename _Pred, typename _Alloc> 00931 inline void 00932 swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 00933 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 00934 { __x.swap(__y); } 00935 00936 template<typename _Key, typename _Tp, typename _Hash, 00937 typename _Pred, typename _Alloc> 00938 inline bool 00939 operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 00940 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 00941 { return __x._M_base() == __y._M_base(); } 00942 00943 template<typename _Key, typename _Tp, typename _Hash, 00944 typename _Pred, typename _Alloc> 00945 inline bool 00946 operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 00947 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 00948 { return !(__x == __y); } 00949 00950 } // namespace __debug 00951 } // namespace std 00952 00953 #endif // C++11 00954 00955 #endif