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