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