libstdc++
|
00001 // Debugging unordered_map/unordered_multimap implementation -*- C++ -*- 00002 00003 // Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011 00004 // Free Software Foundation, Inc. 00005 // 00006 // This file is part of the GNU ISO C++ Library. This library is free 00007 // software; you can redistribute it and/or modify it under the 00008 // terms of the GNU General Public License as published by the 00009 // Free Software Foundation; either version 3, or (at your option) 00010 // any later version. 00011 00012 // This library is distributed in the hope that it will be useful, 00013 // but WITHOUT ANY WARRANTY; without even the implied warranty of 00014 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00015 // GNU General Public License for more details. 00016 00017 // Under Section 7 of GPL version 3, you are granted additional 00018 // permissions described in the GCC Runtime Library Exception, version 00019 // 3.1, as published by the Free Software Foundation. 00020 00021 // You should have received a copy of the GNU General Public License and 00022 // a copy of the GCC Runtime Library Exception along with this program; 00023 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 00024 // <http://www.gnu.org/licenses/>. 00025 00026 /** @file debug/unordered_map 00027 * This file is a GNU debug extension to the Standard C++ Library. 00028 */ 00029 00030 #ifndef _GLIBCXX_DEBUG_UNORDERED_MAP 00031 #define _GLIBCXX_DEBUG_UNORDERED_MAP 1 00032 00033 #ifndef __GXX_EXPERIMENTAL_CXX0X__ 00034 # include <bits/c++0x_warning.h> 00035 #else 00036 # include <unordered_map> 00037 00038 #include <debug/safe_unordered_container.h> 00039 #include <debug/safe_iterator.h> 00040 #include <debug/safe_local_iterator.h> 00041 00042 namespace std _GLIBCXX_VISIBILITY(default) 00043 { 00044 namespace __debug 00045 { 00046 /// Class std::unordered_map with safety/checking/debug instrumentation. 00047 template<typename _Key, typename _Tp, 00048 typename _Hash = std::hash<_Key>, 00049 typename _Pred = std::equal_to<_Key>, 00050 typename _Alloc = std::allocator<_Key> > 00051 class unordered_map 00052 : public _GLIBCXX_STD_C::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>, 00053 public __gnu_debug::_Safe_unordered_container<unordered_map<_Key, _Tp, 00054 _Hash, _Pred, _Alloc> > 00055 { 00056 typedef _GLIBCXX_STD_C::unordered_map<_Key, _Tp, _Hash, 00057 _Pred, _Alloc> _Base; 00058 typedef __gnu_debug::_Safe_unordered_container<unordered_map> _Safe_base; 00059 typedef typename _Base::const_iterator _Base_const_iterator; 00060 typedef typename _Base::iterator _Base_iterator; 00061 typedef typename _Base::const_local_iterator _Base_const_local_iterator; 00062 typedef typename _Base::local_iterator _Base_local_iterator; 00063 00064 public: 00065 typedef typename _Base::size_type size_type; 00066 typedef typename _Base::hasher hasher; 00067 typedef typename _Base::key_equal key_equal; 00068 typedef typename _Base::allocator_type allocator_type; 00069 00070 typedef typename _Base::key_type key_type; 00071 typedef typename _Base::value_type value_type; 00072 00073 typedef __gnu_debug::_Safe_iterator<_Base_iterator, 00074 unordered_map> iterator; 00075 typedef __gnu_debug::_Safe_iterator<_Base_const_iterator, 00076 unordered_map> const_iterator; 00077 typedef __gnu_debug::_Safe_local_iterator<_Base_local_iterator, 00078 unordered_map> local_iterator; 00079 typedef __gnu_debug::_Safe_local_iterator<_Base_const_local_iterator, 00080 unordered_map> const_local_iterator; 00081 00082 explicit 00083 unordered_map(size_type __n = 10, 00084 const hasher& __hf = hasher(), 00085 const key_equal& __eql = key_equal(), 00086 const allocator_type& __a = allocator_type()) 00087 : _Base(__n, __hf, __eql, __a) { } 00088 00089 template<typename _InputIterator> 00090 unordered_map(_InputIterator __first, _InputIterator __last, 00091 size_type __n = 0, 00092 const hasher& __hf = hasher(), 00093 const key_equal& __eql = key_equal(), 00094 const allocator_type& __a = allocator_type()) 00095 : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first, 00096 __last)), 00097 __gnu_debug::__base(__last), __n, 00098 __hf, __eql, __a) { } 00099 00100 unordered_map(const unordered_map& __x) 00101 : _Base(__x) { } 00102 00103 unordered_map(const _Base& __x) 00104 : _Base(__x) { } 00105 00106 unordered_map(unordered_map&& __x) 00107 : _Base(std::move(__x)) { } 00108 00109 unordered_map(initializer_list<value_type> __l, 00110 size_type __n = 0, 00111 const hasher& __hf = hasher(), 00112 const key_equal& __eql = key_equal(), 00113 const allocator_type& __a = allocator_type()) 00114 : _Base(__l, __n, __hf, __eql, __a) { } 00115 00116 ~unordered_map() noexcept { } 00117 00118 unordered_map& 00119 operator=(const unordered_map& __x) 00120 { 00121 *static_cast<_Base*>(this) = __x; 00122 this->_M_invalidate_all(); 00123 return *this; 00124 } 00125 00126 unordered_map& 00127 operator=(unordered_map&& __x) 00128 { 00129 // NB: DR 1204. 00130 // NB: DR 675. 00131 clear(); 00132 swap(__x); 00133 return *this; 00134 } 00135 00136 unordered_map& 00137 operator=(initializer_list<value_type> __l) 00138 { 00139 this->clear(); 00140 this->insert(__l); 00141 return *this; 00142 } 00143 00144 void 00145 swap(unordered_map& __x) 00146 { 00147 _Base::swap(__x); 00148 _Safe_base::_M_swap(__x); 00149 } 00150 00151 void 00152 clear() noexcept 00153 { 00154 _Base::clear(); 00155 this->_M_invalidate_all(); 00156 } 00157 00158 iterator 00159 begin() noexcept 00160 { return iterator(_Base::begin(), this); } 00161 00162 const_iterator 00163 begin() const noexcept 00164 { return const_iterator(_Base::begin(), this); } 00165 00166 iterator 00167 end() noexcept 00168 { return iterator(_Base::end(), this); } 00169 00170 const_iterator 00171 end() const noexcept 00172 { return const_iterator(_Base::end(), this); } 00173 00174 const_iterator 00175 cbegin() const noexcept 00176 { return const_iterator(_Base::begin(), this); } 00177 00178 const_iterator 00179 cend() const noexcept 00180 { return const_iterator(_Base::end(), this); } 00181 00182 // local versions 00183 local_iterator 00184 begin(size_type __b) 00185 { return local_iterator(_Base::begin(__b), __b, this); } 00186 00187 local_iterator 00188 end(size_type __b) 00189 { return local_iterator(_Base::end(__b), __b, this); } 00190 00191 const_local_iterator 00192 begin(size_type __b) const 00193 { return const_local_iterator(_Base::begin(__b), __b, this); } 00194 00195 const_local_iterator 00196 end(size_type __b) const 00197 { return const_local_iterator(_Base::end(__b), __b, this); } 00198 00199 const_local_iterator 00200 cbegin(size_type __b) const 00201 { return const_local_iterator(_Base::cbegin(__b), __b, this); } 00202 00203 const_local_iterator 00204 cend(size_type __b) const 00205 { return const_local_iterator(_Base::cend(__b), __b, this); } 00206 00207 template<typename... _Args> 00208 std::pair<iterator, bool> 00209 emplace(_Args&&... __args) 00210 { 00211 size_type __bucket_count = this->bucket_count(); 00212 std::pair<_Base_iterator, bool> __res 00213 = _Base::emplace(std::forward<_Args>(__args)...); 00214 _M_check_rehashed(__bucket_count); 00215 return std::make_pair(iterator(__res.first, this), __res.second); 00216 } 00217 00218 template<typename... _Args> 00219 iterator 00220 emplace_hint(const_iterator __hint, _Args&&... __args) 00221 { 00222 __glibcxx_check_insert(__hint); 00223 size_type __bucket_count = this->bucket_count(); 00224 _Base_iterator __it = _Base::emplace_hint(__hint.base(), 00225 std::forward<_Args>(__args)...); 00226 _M_check_rehashed(__bucket_count); 00227 return iterator(__it, this); 00228 } 00229 00230 std::pair<iterator, bool> 00231 insert(const value_type& __obj) 00232 { 00233 size_type __bucket_count = this->bucket_count(); 00234 std::pair<_Base_iterator, bool> __res = _Base::insert(__obj); 00235 _M_check_rehashed(__bucket_count); 00236 return std::make_pair(iterator(__res.first, this), __res.second); 00237 } 00238 00239 iterator 00240 insert(const_iterator __hint, const value_type& __obj) 00241 { 00242 __glibcxx_check_insert(__hint); 00243 size_type __bucket_count = this->bucket_count(); 00244 _Base_iterator __it = _Base::insert(__hint.base(), __obj); 00245 _M_check_rehashed(__bucket_count); 00246 return iterator(__it, this); 00247 } 00248 00249 template<typename _Pair, typename = typename 00250 std::enable_if<std::is_convertible<_Pair, 00251 value_type>::value>::type> 00252 std::pair<iterator, bool> 00253 insert(_Pair&& __obj) 00254 { 00255 size_type __bucket_count = this->bucket_count(); 00256 std::pair<_Base_iterator, bool> __res = 00257 _Base::insert(std::forward<_Pair>(__obj)); 00258 _M_check_rehashed(__bucket_count); 00259 return std::make_pair(iterator(__res.first, this), __res.second); 00260 } 00261 00262 template<typename _Pair, typename = typename 00263 std::enable_if<std::is_convertible<_Pair, 00264 value_type>::value>::type> 00265 iterator 00266 insert(const_iterator __hint, _Pair&& __obj) 00267 { 00268 __glibcxx_check_insert(__hint); 00269 size_type __bucket_count = this->bucket_count(); 00270 _Base_iterator __it = 00271 _Base::insert(__hint.base(), std::forward<_Pair>(__obj)); 00272 _M_check_rehashed(__bucket_count); 00273 return iterator(__it, this); 00274 } 00275 00276 void 00277 insert(std::initializer_list<value_type> __l) 00278 { 00279 size_type __bucket_count = this->bucket_count(); 00280 _Base::insert(__l); 00281 _M_check_rehashed(__bucket_count); 00282 } 00283 00284 template<typename _InputIterator> 00285 void 00286 insert(_InputIterator __first, _InputIterator __last) 00287 { 00288 __glibcxx_check_valid_range(__first, __last); 00289 size_type __bucket_count = this->bucket_count(); 00290 _Base::insert(__gnu_debug::__base(__first), 00291 __gnu_debug::__base(__last)); 00292 _M_check_rehashed(__bucket_count); 00293 } 00294 00295 iterator 00296 find(const key_type& __key) 00297 { return iterator(_Base::find(__key), this); } 00298 00299 const_iterator 00300 find(const key_type& __key) const 00301 { return const_iterator(_Base::find(__key), this); } 00302 00303 std::pair<iterator, iterator> 00304 equal_range(const key_type& __key) 00305 { 00306 std::pair<_Base_iterator, _Base_iterator> __res = 00307 _Base::equal_range(__key); 00308 return std::make_pair(iterator(__res.first, this), 00309 iterator(__res.second, this)); 00310 } 00311 00312 std::pair<const_iterator, const_iterator> 00313 equal_range(const key_type& __key) const 00314 { 00315 std::pair<_Base_const_iterator, _Base_const_iterator> __res = 00316 _Base::equal_range(__key); 00317 return std::make_pair(const_iterator(__res.first, this), 00318 const_iterator(__res.second, this)); 00319 } 00320 00321 size_type 00322 erase(const key_type& __key) 00323 { 00324 size_type __ret(0); 00325 _Base_iterator __victim(_Base::find(__key)); 00326 if (__victim != _Base::end()) 00327 { 00328 this->_M_invalidate_if([__victim](_Base_const_iterator __it) 00329 { return __it == __victim; }); 00330 _Base_local_iterator __local_victim = _S_to_local(__victim); 00331 this->_M_invalidate_local_if( 00332 [__local_victim](_Base_const_local_iterator __it) 00333 { return __it == __local_victim; }); 00334 size_type __bucket_count = this->bucket_count(); 00335 _Base::erase(__victim); 00336 _M_check_rehashed(__bucket_count); 00337 __ret = 1; 00338 } 00339 return __ret; 00340 } 00341 00342 iterator 00343 erase(const_iterator __it) 00344 { 00345 __glibcxx_check_erase(__it); 00346 _Base_const_iterator __victim = __it.base(); 00347 this->_M_invalidate_if([__victim](_Base_const_iterator __it) 00348 { return __it == __victim; }); 00349 _Base_const_local_iterator __local_victim = _S_to_local(__victim); 00350 this->_M_invalidate_local_if( 00351 [__local_victim](_Base_const_local_iterator __it) 00352 { return __it == __local_victim; }); 00353 size_type __bucket_count = this->bucket_count(); 00354 _Base_iterator __next = _Base::erase(__it.base()); 00355 _M_check_rehashed(__bucket_count); 00356 return iterator(__next, this); 00357 } 00358 00359 iterator 00360 erase(iterator __it) 00361 { return erase(const_iterator(__it)); } 00362 00363 iterator 00364 erase(const_iterator __first, const_iterator __last) 00365 { 00366 __glibcxx_check_erase_range(__first, __last); 00367 for (_Base_const_iterator __tmp = __first.base(); 00368 __tmp != __last.base(); ++__tmp) 00369 { 00370 _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(), 00371 _M_message(__gnu_debug::__msg_valid_range) 00372 ._M_iterator(__first, "first") 00373 ._M_iterator(__last, "last")); 00374 this->_M_invalidate_if([__tmp](_Base_const_iterator __it) 00375 { return __it == __tmp; }); 00376 _Base_const_local_iterator __local_tmp = _S_to_local(__tmp); 00377 this->_M_invalidate_local_if( 00378 [__local_tmp](_Base_const_local_iterator __it) 00379 { return __it == __local_tmp; }); 00380 } 00381 size_type __bucket_count = this->bucket_count(); 00382 _Base_iterator __next = _Base::erase(__first.base(), __last.base()); 00383 _M_check_rehashed(__bucket_count); 00384 return iterator(__next, this); 00385 } 00386 00387 _Base& 00388 _M_base() noexcept { return *this; } 00389 00390 const _Base& 00391 _M_base() const noexcept { return *this; } 00392 00393 private: 00394 void 00395 _M_invalidate_locals() 00396 { 00397 _Base_local_iterator __local_end = _Base::end(0); 00398 this->_M_invalidate_local_if( 00399 [__local_end](_Base_const_local_iterator __it) 00400 { return __it != __local_end; }); 00401 } 00402 00403 void 00404 _M_invalidate_all() 00405 { 00406 _Base_iterator __end = _Base::end(); 00407 this->_M_invalidate_if([__end](_Base_const_iterator __it) 00408 { return __it != __end; }); 00409 _M_invalidate_locals(); 00410 } 00411 00412 void 00413 _M_check_rehashed(size_type __prev_count) 00414 { 00415 if (__prev_count != this->bucket_count()) 00416 _M_invalidate_locals(); 00417 } 00418 00419 static _Base_local_iterator 00420 _S_to_local(_Base_iterator __it) 00421 { 00422 // The returned local iterator will not be incremented so we don't 00423 // need to compute __it's node bucket 00424 return _Base_local_iterator(__it._M_cur, 0, 0); 00425 } 00426 00427 static _Base_const_local_iterator 00428 _S_to_local(_Base_const_iterator __it) 00429 { 00430 // The returned local iterator will not be incremented so we don't 00431 // need to compute __it's node bucket 00432 return _Base_const_local_iterator(__it._M_cur, 0, 0); 00433 } 00434 }; 00435 00436 template<typename _Key, typename _Tp, typename _Hash, 00437 typename _Pred, typename _Alloc> 00438 inline void 00439 swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 00440 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 00441 { __x.swap(__y); } 00442 00443 template<typename _Key, typename _Tp, typename _Hash, 00444 typename _Pred, typename _Alloc> 00445 inline bool 00446 operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 00447 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 00448 { return __x._M_equal(__y); } 00449 00450 template<typename _Key, typename _Tp, typename _Hash, 00451 typename _Pred, typename _Alloc> 00452 inline bool 00453 operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 00454 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 00455 { return !(__x == __y); } 00456 00457 00458 /// Class std::unordered_multimap with safety/checking/debug instrumentation. 00459 template<typename _Key, typename _Tp, 00460 typename _Hash = std::hash<_Key>, 00461 typename _Pred = std::equal_to<_Key>, 00462 typename _Alloc = std::allocator<_Key> > 00463 class unordered_multimap 00464 : public _GLIBCXX_STD_C::unordered_multimap<_Key, _Tp, _Hash, 00465 _Pred, _Alloc>, 00466 public __gnu_debug::_Safe_unordered_container<unordered_multimap<_Key, 00467 _Tp, _Hash, _Pred, _Alloc> > 00468 { 00469 typedef _GLIBCXX_STD_C::unordered_multimap<_Key, _Tp, _Hash, 00470 _Pred, _Alloc> _Base; 00471 typedef __gnu_debug::_Safe_unordered_container<unordered_multimap> 00472 _Safe_base; 00473 typedef typename _Base::const_iterator _Base_const_iterator; 00474 typedef typename _Base::iterator _Base_iterator; 00475 typedef typename _Base::const_local_iterator _Base_const_local_iterator; 00476 typedef typename _Base::local_iterator _Base_local_iterator; 00477 00478 public: 00479 typedef typename _Base::size_type size_type; 00480 typedef typename _Base::hasher hasher; 00481 typedef typename _Base::key_equal key_equal; 00482 typedef typename _Base::allocator_type allocator_type; 00483 00484 typedef typename _Base::key_type key_type; 00485 typedef typename _Base::value_type value_type; 00486 00487 typedef __gnu_debug::_Safe_iterator<_Base_iterator, 00488 unordered_multimap> iterator; 00489 typedef __gnu_debug::_Safe_iterator<_Base_const_iterator, 00490 unordered_multimap> const_iterator; 00491 typedef __gnu_debug::_Safe_local_iterator< 00492 _Base_local_iterator, unordered_multimap> local_iterator; 00493 typedef __gnu_debug::_Safe_local_iterator< 00494 _Base_const_local_iterator, unordered_multimap> const_local_iterator; 00495 00496 explicit 00497 unordered_multimap(size_type __n = 10, 00498 const hasher& __hf = hasher(), 00499 const key_equal& __eql = key_equal(), 00500 const allocator_type& __a = allocator_type()) 00501 : _Base(__n, __hf, __eql, __a) { } 00502 00503 template<typename _InputIterator> 00504 unordered_multimap(_InputIterator __first, _InputIterator __last, 00505 size_type __n = 0, 00506 const hasher& __hf = hasher(), 00507 const key_equal& __eql = key_equal(), 00508 const allocator_type& __a = allocator_type()) 00509 : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first, 00510 __last)), 00511 __gnu_debug::__base(__last), __n, 00512 __hf, __eql, __a) { } 00513 00514 unordered_multimap(const unordered_multimap& __x) 00515 : _Base(__x) { } 00516 00517 unordered_multimap(const _Base& __x) 00518 : _Base(__x) { } 00519 00520 unordered_multimap(unordered_multimap&& __x) 00521 : _Base(std::move(__x)) { } 00522 00523 unordered_multimap(initializer_list<value_type> __l, 00524 size_type __n = 0, 00525 const hasher& __hf = hasher(), 00526 const key_equal& __eql = key_equal(), 00527 const allocator_type& __a = allocator_type()) 00528 : _Base(__l, __n, __hf, __eql, __a) { } 00529 00530 ~unordered_multimap() noexcept { } 00531 00532 unordered_multimap& 00533 operator=(const unordered_multimap& __x) 00534 { 00535 *static_cast<_Base*>(this) = __x; 00536 this->_M_invalidate_all(); 00537 return *this; 00538 } 00539 00540 unordered_multimap& 00541 operator=(unordered_multimap&& __x) 00542 { 00543 // NB: DR 1204. 00544 // NB: DR 675. 00545 clear(); 00546 swap(__x); 00547 return *this; 00548 } 00549 00550 unordered_multimap& 00551 operator=(initializer_list<value_type> __l) 00552 { 00553 this->clear(); 00554 this->insert(__l); 00555 return *this; 00556 } 00557 00558 void 00559 swap(unordered_multimap& __x) 00560 { 00561 _Base::swap(__x); 00562 _Safe_base::_M_swap(__x); 00563 } 00564 00565 void 00566 clear() noexcept 00567 { 00568 _Base::clear(); 00569 this->_M_invalidate_all(); 00570 } 00571 00572 iterator 00573 begin() noexcept 00574 { return iterator(_Base::begin(), this); } 00575 00576 const_iterator 00577 begin() const noexcept 00578 { return const_iterator(_Base::begin(), this); } 00579 00580 iterator 00581 end() noexcept 00582 { return iterator(_Base::end(), this); } 00583 00584 const_iterator 00585 end() const noexcept 00586 { return const_iterator(_Base::end(), this); } 00587 00588 const_iterator 00589 cbegin() const noexcept 00590 { return const_iterator(_Base::begin(), this); } 00591 00592 const_iterator 00593 cend() const noexcept 00594 { return const_iterator(_Base::end(), this); } 00595 00596 // local versions 00597 local_iterator 00598 begin(size_type __b) 00599 { return local_iterator(_Base::begin(__b), __b, this); } 00600 00601 local_iterator 00602 end(size_type __b) 00603 { return local_iterator(_Base::end(__b), __b, this); } 00604 00605 const_local_iterator 00606 begin(size_type __b) const 00607 { return const_local_iterator(_Base::begin(__b), __b, this); } 00608 00609 const_local_iterator 00610 end(size_type __b) const 00611 { return const_local_iterator(_Base::end(__b), __b, this); } 00612 00613 const_local_iterator 00614 cbegin(size_type __b) const 00615 { return const_local_iterator(_Base::cbegin(__b), __b, this); } 00616 00617 const_local_iterator 00618 cend(size_type __b) const 00619 { return const_local_iterator(_Base::cend(__b), __b, this); } 00620 00621 template<typename... _Args> 00622 iterator 00623 emplace(_Args&&... __args) 00624 { 00625 size_type __bucket_count = this->bucket_count(); 00626 _Base_iterator __it 00627 = _Base::emplace(std::forward<_Args>(__args)...); 00628 _M_check_rehashed(__bucket_count); 00629 return iterator(__it, this); 00630 } 00631 00632 template<typename... _Args> 00633 iterator 00634 emplace_hint(const_iterator __hint, _Args&&... __args) 00635 { 00636 __glibcxx_check_insert(__hint); 00637 size_type __bucket_count = this->bucket_count(); 00638 _Base_iterator __it = _Base::emplace_hint(__hint.base(), 00639 std::forward<_Args>(__args)...); 00640 _M_check_rehashed(__bucket_count); 00641 return iterator(__it, this); 00642 } 00643 00644 iterator 00645 insert(const value_type& __obj) 00646 { 00647 size_type __bucket_count = this->bucket_count(); 00648 _Base_iterator __it = _Base::insert(__obj); 00649 _M_check_rehashed(__bucket_count); 00650 return iterator(__it, this); 00651 } 00652 00653 iterator 00654 insert(const_iterator __hint, const value_type& __obj) 00655 { 00656 __glibcxx_check_insert(__hint); 00657 size_type __bucket_count = this->bucket_count(); 00658 _Base_iterator __it = _Base::insert(__hint.base(), __obj); 00659 _M_check_rehashed(__bucket_count); 00660 return iterator(__it, this); 00661 } 00662 00663 template<typename _Pair, typename = typename 00664 std::enable_if<std::is_convertible<_Pair, 00665 value_type>::value>::type> 00666 iterator 00667 insert(_Pair&& __obj) 00668 { 00669 size_type __bucket_count = this->bucket_count(); 00670 _Base_iterator __it = _Base::insert(std::forward<_Pair>(__obj)); 00671 _M_check_rehashed(__bucket_count); 00672 return iterator(__it, this); 00673 } 00674 00675 template<typename _Pair, typename = typename 00676 std::enable_if<std::is_convertible<_Pair, 00677 value_type>::value>::type> 00678 iterator 00679 insert(const_iterator __hint, _Pair&& __obj) 00680 { 00681 __glibcxx_check_insert(__hint); 00682 size_type __bucket_count = this->bucket_count(); 00683 _Base_iterator __it = 00684 _Base::insert(__hint.base(), std::forward<_Pair>(__obj)); 00685 _M_check_rehashed(__bucket_count); 00686 return iterator(__it, this); 00687 } 00688 00689 void 00690 insert(std::initializer_list<value_type> __l) 00691 { _Base::insert(__l); } 00692 00693 template<typename _InputIterator> 00694 void 00695 insert(_InputIterator __first, _InputIterator __last) 00696 { 00697 __glibcxx_check_valid_range(__first, __last); 00698 size_type __bucket_count = this->bucket_count(); 00699 _Base::insert(__gnu_debug::__base(__first), 00700 __gnu_debug::__base(__last)); 00701 _M_check_rehashed(__bucket_count); 00702 } 00703 00704 iterator 00705 find(const key_type& __key) 00706 { return iterator(_Base::find(__key), this); } 00707 00708 const_iterator 00709 find(const key_type& __key) const 00710 { return const_iterator(_Base::find(__key), this); } 00711 00712 std::pair<iterator, iterator> 00713 equal_range(const key_type& __key) 00714 { 00715 std::pair<_Base_iterator, _Base_iterator> __res = 00716 _Base::equal_range(__key); 00717 return std::make_pair(iterator(__res.first, this), 00718 iterator(__res.second, this)); 00719 } 00720 00721 std::pair<const_iterator, const_iterator> 00722 equal_range(const key_type& __key) const 00723 { 00724 std::pair<_Base_const_iterator, _Base_const_iterator> __res = 00725 _Base::equal_range(__key); 00726 return std::make_pair(const_iterator(__res.first, this), 00727 const_iterator(__res.second, this)); 00728 } 00729 00730 size_type 00731 erase(const key_type& __key) 00732 { 00733 size_type __ret(0); 00734 size_type __bucket_count = this->bucket_count(); 00735 std::pair<_Base_iterator, _Base_iterator> __pair = 00736 _Base::equal_range(__key); 00737 for (_Base_iterator __victim = __pair.first; __victim != __pair.second;) 00738 { 00739 this->_M_invalidate_if([__victim](_Base_const_iterator __it) 00740 { return __it == __victim; }); 00741 _Base_local_iterator __local_victim = _S_to_local(__victim); 00742 this->_M_invalidate_local_if( 00743 [__local_victim](_Base_const_local_iterator __it) 00744 { return __it == __local_victim; }); 00745 _Base::erase(__victim++); 00746 ++__ret; 00747 } 00748 _M_check_rehashed(__bucket_count); 00749 return __ret; 00750 } 00751 00752 iterator 00753 erase(const_iterator __it) 00754 { 00755 __glibcxx_check_erase(__it); 00756 _Base_const_iterator __victim = __it.base(); 00757 this->_M_invalidate_if([__victim](_Base_const_iterator __it) 00758 { return __it == __victim; }); 00759 _Base_const_local_iterator __local_victim = _S_to_local(__victim); 00760 this->_M_invalidate_local_if( 00761 [__local_victim](_Base_const_local_iterator __it) 00762 { return __it == __local_victim; }); 00763 size_type __bucket_count = this->bucket_count(); 00764 _Base_iterator __next = _Base::erase(__it.base()); 00765 _M_check_rehashed(__bucket_count); 00766 return iterator(__next, this); 00767 } 00768 00769 iterator 00770 erase(iterator __it) 00771 { return erase(const_iterator(__it)); } 00772 00773 iterator 00774 erase(const_iterator __first, const_iterator __last) 00775 { 00776 __glibcxx_check_erase_range(__first, __last); 00777 for (_Base_const_iterator __tmp = __first.base(); 00778 __tmp != __last.base(); ++__tmp) 00779 { 00780 _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(), 00781 _M_message(__gnu_debug::__msg_valid_range) 00782 ._M_iterator(__first, "first") 00783 ._M_iterator(__last, "last")); 00784 this->_M_invalidate_if([__tmp](_Base_const_iterator __it) 00785 { return __it == __tmp; }); 00786 _Base_const_local_iterator __local_tmp = _S_to_local(__tmp); 00787 this->_M_invalidate_local_if( 00788 [__local_tmp](_Base_const_local_iterator __it) 00789 { return __it == __local_tmp; }); 00790 } 00791 size_type __bucket_count = this->bucket_count(); 00792 _Base_iterator __next = _Base::erase(__first.base(), __last.base()); 00793 _M_check_rehashed(__bucket_count); 00794 return iterator(__next, this); 00795 } 00796 00797 _Base& 00798 _M_base() noexcept { return *this; } 00799 00800 const _Base& 00801 _M_base() const noexcept { return *this; } 00802 00803 private: 00804 void 00805 _M_invalidate_locals() 00806 { 00807 _Base_local_iterator __local_end = _Base::end(0); 00808 this->_M_invalidate_local_if( 00809 [__local_end](_Base_const_local_iterator __it) 00810 { return __it != __local_end; }); 00811 } 00812 00813 void 00814 _M_invalidate_all() 00815 { 00816 _Base_iterator __end = _Base::end(); 00817 this->_M_invalidate_if([__end](_Base_const_iterator __it) 00818 { return __it != __end; }); 00819 _M_invalidate_locals(); 00820 } 00821 00822 void 00823 _M_check_rehashed(size_type __prev_count) 00824 { 00825 if (__prev_count != this->bucket_count()) 00826 _M_invalidate_locals(); 00827 } 00828 00829 static _Base_local_iterator 00830 _S_to_local(_Base_iterator __it) 00831 { 00832 // The returned local iterator will not be incremented so we don't 00833 // need to compute __it's node bucket 00834 return _Base_local_iterator(__it._M_cur, 0, 0); 00835 } 00836 00837 static _Base_const_local_iterator 00838 _S_to_local(_Base_const_iterator __it) 00839 { 00840 // The returned local iterator will not be incremented so we don't 00841 // need to compute __it's node bucket 00842 return _Base_const_local_iterator(__it._M_cur, 0, 0); 00843 } 00844 }; 00845 00846 template<typename _Key, typename _Tp, typename _Hash, 00847 typename _Pred, typename _Alloc> 00848 inline void 00849 swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 00850 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 00851 { __x.swap(__y); } 00852 00853 template<typename _Key, typename _Tp, typename _Hash, 00854 typename _Pred, typename _Alloc> 00855 inline bool 00856 operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 00857 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 00858 { return __x._M_equal(__y); } 00859 00860 template<typename _Key, typename _Tp, typename _Hash, 00861 typename _Pred, typename _Alloc> 00862 inline bool 00863 operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 00864 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 00865 { return !(__x == __y); } 00866 00867 } // namespace __debug 00868 } // namespace std 00869 00870 #endif // __GXX_EXPERIMENTAL_CXX0X__ 00871 00872 #endif