libstdc++
|
00001 // Debugging unordered_map/unordered_multimap implementation -*- C++ -*- 00002 00003 // Copyright (C) 2003-2016 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 typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist; 00368 __glibcxx_check_valid_range2(__first, __last, __dist); 00369 size_type __bucket_count = this->bucket_count(); 00370 00371 if (__dist.second >= __gnu_debug::__dp_sign) 00372 _Base::insert(__gnu_debug::__unsafe(__first), 00373 __gnu_debug::__unsafe(__last)); 00374 else 00375 _Base::insert(__first, __last); 00376 00377 _M_check_rehashed(__bucket_count); 00378 } 00379 00380 #if __cplusplus > 201402L 00381 template <typename... _Args> 00382 pair<iterator, bool> 00383 try_emplace(const key_type& __k, _Args&&... __args) 00384 { 00385 auto __res = _Base::try_emplace(__k, 00386 std::forward<_Args>(__args)...); 00387 return { iterator(__res.first, this), __res.second }; 00388 } 00389 00390 template <typename... _Args> 00391 pair<iterator, bool> 00392 try_emplace(key_type&& __k, _Args&&... __args) 00393 { 00394 auto __res = _Base::try_emplace(std::move(__k), 00395 std::forward<_Args>(__args)...); 00396 return { iterator(__res.first, this), __res.second }; 00397 } 00398 00399 template <typename... _Args> 00400 iterator 00401 try_emplace(const_iterator __hint, const key_type& __k, 00402 _Args&&... __args) 00403 { 00404 __glibcxx_check_insert(__hint); 00405 return iterator(_Base::try_emplace(__hint.base(), __k, 00406 std::forward<_Args>(__args)...), 00407 this); 00408 } 00409 00410 template <typename... _Args> 00411 iterator 00412 try_emplace(const_iterator __hint, key_type&& __k, _Args&&... __args) 00413 { 00414 __glibcxx_check_insert(__hint); 00415 return iterator(_Base::try_emplace(__hint.base(), std::move(__k), 00416 std::forward<_Args>(__args)...), 00417 this); 00418 } 00419 00420 template <typename _Obj> 00421 pair<iterator, bool> 00422 insert_or_assign(const key_type& __k, _Obj&& __obj) 00423 { 00424 auto __res = _Base::insert_or_assign(__k, 00425 std::forward<_Obj>(__obj)); 00426 return { iterator(__res.first, this), __res.second }; 00427 } 00428 00429 template <typename _Obj> 00430 pair<iterator, bool> 00431 insert_or_assign(key_type&& __k, _Obj&& __obj) 00432 { 00433 auto __res = _Base::insert_or_assign(std::move(__k), 00434 std::forward<_Obj>(__obj)); 00435 return { iterator(__res.first, this), __res.second }; 00436 } 00437 00438 template <typename _Obj> 00439 iterator 00440 insert_or_assign(const_iterator __hint, const key_type& __k, 00441 _Obj&& __obj) 00442 { 00443 __glibcxx_check_insert(__hint); 00444 return iterator(_Base::insert_or_assign(__hint.base(), __k, 00445 std::forward<_Obj>(__obj)), 00446 this); 00447 } 00448 00449 template <typename _Obj> 00450 iterator 00451 insert_or_assign(const_iterator __hint, key_type&& __k, _Obj&& __obj) 00452 { 00453 __glibcxx_check_insert(__hint); 00454 return iterator(_Base::insert_or_assign(__hint.base(), 00455 std::move(__k), 00456 std::forward<_Obj>(__obj)), 00457 this); 00458 } 00459 #endif 00460 00461 00462 iterator 00463 find(const key_type& __key) 00464 { return iterator(_Base::find(__key), this); } 00465 00466 const_iterator 00467 find(const key_type& __key) const 00468 { return const_iterator(_Base::find(__key), this); } 00469 00470 std::pair<iterator, iterator> 00471 equal_range(const key_type& __key) 00472 { 00473 std::pair<_Base_iterator, _Base_iterator> __res = 00474 _Base::equal_range(__key); 00475 return std::make_pair(iterator(__res.first, this), 00476 iterator(__res.second, this)); 00477 } 00478 00479 std::pair<const_iterator, const_iterator> 00480 equal_range(const key_type& __key) const 00481 { 00482 std::pair<_Base_const_iterator, _Base_const_iterator> __res = 00483 _Base::equal_range(__key); 00484 return std::make_pair(const_iterator(__res.first, this), 00485 const_iterator(__res.second, this)); 00486 } 00487 00488 size_type 00489 erase(const key_type& __key) 00490 { 00491 size_type __ret(0); 00492 _Base_iterator __victim(_Base::find(__key)); 00493 if (__victim != _Base::end()) 00494 { 00495 this->_M_invalidate_if([__victim](_Base_const_iterator __it) 00496 { return __it == __victim; }); 00497 this->_M_invalidate_local_if( 00498 [__victim](_Base_const_local_iterator __it) 00499 { return __it._M_curr() == __victim._M_cur; }); 00500 size_type __bucket_count = this->bucket_count(); 00501 _Base::erase(__victim); 00502 _M_check_rehashed(__bucket_count); 00503 __ret = 1; 00504 } 00505 return __ret; 00506 } 00507 00508 iterator 00509 erase(const_iterator __it) 00510 { 00511 __glibcxx_check_erase(__it); 00512 _Base_const_iterator __victim = __it.base(); 00513 this->_M_invalidate_if([__victim](_Base_const_iterator __it) 00514 { return __it == __victim; }); 00515 this->_M_invalidate_local_if( 00516 [__victim](_Base_const_local_iterator __it) 00517 { return __it._M_curr() == __victim._M_cur; }); 00518 size_type __bucket_count = this->bucket_count(); 00519 _Base_iterator __next = _Base::erase(__it.base()); 00520 _M_check_rehashed(__bucket_count); 00521 return iterator(__next, this); 00522 } 00523 00524 iterator 00525 erase(iterator __it) 00526 { return erase(const_iterator(__it)); } 00527 00528 iterator 00529 erase(const_iterator __first, const_iterator __last) 00530 { 00531 __glibcxx_check_erase_range(__first, __last); 00532 for (_Base_const_iterator __tmp = __first.base(); 00533 __tmp != __last.base(); ++__tmp) 00534 { 00535 _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(), 00536 _M_message(__gnu_debug::__msg_valid_range) 00537 ._M_iterator(__first, "first") 00538 ._M_iterator(__last, "last")); 00539 this->_M_invalidate_if([__tmp](_Base_const_iterator __it) 00540 { return __it == __tmp; }); 00541 this->_M_invalidate_local_if( 00542 [__tmp](_Base_const_local_iterator __it) 00543 { return __it._M_curr() == __tmp._M_cur; }); 00544 } 00545 size_type __bucket_count = this->bucket_count(); 00546 _Base_iterator __next = _Base::erase(__first.base(), __last.base()); 00547 _M_check_rehashed(__bucket_count); 00548 return iterator(__next, this); 00549 } 00550 00551 _Base& 00552 _M_base() noexcept { return *this; } 00553 00554 const _Base& 00555 _M_base() const noexcept { return *this; } 00556 00557 private: 00558 void 00559 _M_check_rehashed(size_type __prev_count) 00560 { 00561 if (__prev_count != this->bucket_count()) 00562 this->_M_invalidate_locals(); 00563 } 00564 }; 00565 00566 template<typename _Key, typename _Tp, typename _Hash, 00567 typename _Pred, typename _Alloc> 00568 inline void 00569 swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 00570 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 00571 noexcept(noexcept(__x.swap(__y))) 00572 { __x.swap(__y); } 00573 00574 template<typename _Key, typename _Tp, typename _Hash, 00575 typename _Pred, typename _Alloc> 00576 inline bool 00577 operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 00578 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 00579 { return __x._M_base() == __y._M_base(); } 00580 00581 template<typename _Key, typename _Tp, typename _Hash, 00582 typename _Pred, typename _Alloc> 00583 inline bool 00584 operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 00585 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 00586 { return !(__x == __y); } 00587 00588 00589 /// Class std::unordered_multimap with safety/checking/debug instrumentation. 00590 template<typename _Key, typename _Tp, 00591 typename _Hash = std::hash<_Key>, 00592 typename _Pred = std::equal_to<_Key>, 00593 typename _Alloc = std::allocator<std::pair<const _Key, _Tp> > > 00594 class unordered_multimap 00595 : public __gnu_debug::_Safe_container< 00596 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>, _Alloc, 00597 __gnu_debug::_Safe_unordered_container>, 00598 public _GLIBCXX_STD_C::unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc> 00599 { 00600 typedef _GLIBCXX_STD_C::unordered_multimap<_Key, _Tp, _Hash, 00601 _Pred, _Alloc> _Base; 00602 typedef __gnu_debug::_Safe_container<unordered_multimap, 00603 _Alloc, __gnu_debug::_Safe_unordered_container> _Safe; 00604 typedef typename _Base::const_iterator _Base_const_iterator; 00605 typedef typename _Base::iterator _Base_iterator; 00606 typedef typename _Base::const_local_iterator _Base_const_local_iterator; 00607 typedef typename _Base::local_iterator _Base_local_iterator; 00608 00609 public: 00610 typedef typename _Base::size_type size_type; 00611 typedef typename _Base::hasher hasher; 00612 typedef typename _Base::key_equal key_equal; 00613 typedef typename _Base::allocator_type allocator_type; 00614 00615 typedef typename _Base::key_type key_type; 00616 typedef typename _Base::value_type value_type; 00617 00618 typedef __gnu_debug::_Safe_iterator< 00619 _Base_iterator, unordered_multimap> iterator; 00620 typedef __gnu_debug::_Safe_iterator< 00621 _Base_const_iterator, unordered_multimap> const_iterator; 00622 typedef __gnu_debug::_Safe_local_iterator< 00623 _Base_local_iterator, unordered_multimap> local_iterator; 00624 typedef __gnu_debug::_Safe_local_iterator< 00625 _Base_const_local_iterator, unordered_multimap> const_local_iterator; 00626 00627 unordered_multimap() = default; 00628 00629 explicit 00630 unordered_multimap(size_type __n, 00631 const hasher& __hf = hasher(), 00632 const key_equal& __eql = key_equal(), 00633 const allocator_type& __a = allocator_type()) 00634 : _Base(__n, __hf, __eql, __a) { } 00635 00636 template<typename _InputIterator> 00637 unordered_multimap(_InputIterator __first, _InputIterator __last, 00638 size_type __n = 0, 00639 const hasher& __hf = hasher(), 00640 const key_equal& __eql = key_equal(), 00641 const allocator_type& __a = allocator_type()) 00642 : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first, 00643 __last)), 00644 __gnu_debug::__base(__last), __n, 00645 __hf, __eql, __a) { } 00646 00647 unordered_multimap(const unordered_multimap&) = default; 00648 00649 unordered_multimap(const _Base& __x) 00650 : _Base(__x) { } 00651 00652 unordered_multimap(unordered_multimap&&) = default; 00653 00654 explicit 00655 unordered_multimap(const allocator_type& __a) 00656 : _Base(__a) { } 00657 00658 unordered_multimap(const unordered_multimap& __umap, 00659 const allocator_type& __a) 00660 : _Base(__umap, __a) { } 00661 00662 unordered_multimap(unordered_multimap&& __umap, 00663 const allocator_type& __a) 00664 : _Safe(std::move(__umap._M_safe()), __a), 00665 _Base(std::move(__umap._M_base()), __a) { } 00666 00667 unordered_multimap(initializer_list<value_type> __l, 00668 size_type __n = 0, 00669 const hasher& __hf = hasher(), 00670 const key_equal& __eql = key_equal(), 00671 const allocator_type& __a = allocator_type()) 00672 : _Base(__l, __n, __hf, __eql, __a) { } 00673 00674 unordered_multimap(size_type __n, const allocator_type& __a) 00675 : unordered_multimap(__n, hasher(), key_equal(), __a) 00676 { } 00677 00678 unordered_multimap(size_type __n, const hasher& __hf, 00679 const allocator_type& __a) 00680 : unordered_multimap(__n, __hf, key_equal(), __a) 00681 { } 00682 00683 template<typename _InputIterator> 00684 unordered_multimap(_InputIterator __first, _InputIterator __last, 00685 size_type __n, 00686 const allocator_type& __a) 00687 : unordered_multimap(__first, __last, __n, hasher(), key_equal(), __a) 00688 { } 00689 00690 template<typename _InputIterator> 00691 unordered_multimap(_InputIterator __first, _InputIterator __last, 00692 size_type __n, const hasher& __hf, 00693 const allocator_type& __a) 00694 : unordered_multimap(__first, __last, __n, __hf, key_equal(), __a) 00695 { } 00696 00697 unordered_multimap(initializer_list<value_type> __l, 00698 size_type __n, 00699 const allocator_type& __a) 00700 : unordered_multimap(__l, __n, hasher(), key_equal(), __a) 00701 { } 00702 00703 unordered_multimap(initializer_list<value_type> __l, 00704 size_type __n, const hasher& __hf, 00705 const allocator_type& __a) 00706 : unordered_multimap(__l, __n, __hf, key_equal(), __a) 00707 { } 00708 00709 ~unordered_multimap() = default; 00710 00711 unordered_multimap& 00712 operator=(const unordered_multimap&) = default; 00713 00714 unordered_multimap& 00715 operator=(unordered_multimap&&) = default; 00716 00717 unordered_multimap& 00718 operator=(initializer_list<value_type> __l) 00719 { 00720 this->_M_base() = __l; 00721 this->_M_invalidate_all(); 00722 return *this; 00723 } 00724 00725 void 00726 swap(unordered_multimap& __x) 00727 noexcept( noexcept(declval<_Base&>().swap(__x)) ) 00728 { 00729 _Safe::_M_swap(__x); 00730 _Base::swap(__x); 00731 } 00732 00733 void 00734 clear() noexcept 00735 { 00736 _Base::clear(); 00737 this->_M_invalidate_all(); 00738 } 00739 00740 iterator 00741 begin() noexcept 00742 { return iterator(_Base::begin(), this); } 00743 00744 const_iterator 00745 begin() const noexcept 00746 { return const_iterator(_Base::begin(), this); } 00747 00748 iterator 00749 end() noexcept 00750 { return iterator(_Base::end(), this); } 00751 00752 const_iterator 00753 end() const noexcept 00754 { return const_iterator(_Base::end(), this); } 00755 00756 const_iterator 00757 cbegin() const noexcept 00758 { return const_iterator(_Base::begin(), this); } 00759 00760 const_iterator 00761 cend() const noexcept 00762 { return const_iterator(_Base::end(), this); } 00763 00764 // local versions 00765 local_iterator 00766 begin(size_type __b) 00767 { 00768 __glibcxx_check_bucket_index(__b); 00769 return local_iterator(_Base::begin(__b), this); 00770 } 00771 00772 local_iterator 00773 end(size_type __b) 00774 { 00775 __glibcxx_check_bucket_index(__b); 00776 return local_iterator(_Base::end(__b), this); 00777 } 00778 00779 const_local_iterator 00780 begin(size_type __b) const 00781 { 00782 __glibcxx_check_bucket_index(__b); 00783 return const_local_iterator(_Base::begin(__b), this); 00784 } 00785 00786 const_local_iterator 00787 end(size_type __b) const 00788 { 00789 __glibcxx_check_bucket_index(__b); 00790 return const_local_iterator(_Base::end(__b), this); 00791 } 00792 00793 const_local_iterator 00794 cbegin(size_type __b) const 00795 { 00796 __glibcxx_check_bucket_index(__b); 00797 return const_local_iterator(_Base::cbegin(__b), this); 00798 } 00799 00800 const_local_iterator 00801 cend(size_type __b) const 00802 { 00803 __glibcxx_check_bucket_index(__b); 00804 return const_local_iterator(_Base::cend(__b), this); 00805 } 00806 00807 size_type 00808 bucket_size(size_type __b) const 00809 { 00810 __glibcxx_check_bucket_index(__b); 00811 return _Base::bucket_size(__b); 00812 } 00813 00814 float 00815 max_load_factor() const noexcept 00816 { return _Base::max_load_factor(); } 00817 00818 void 00819 max_load_factor(float __f) 00820 { 00821 __glibcxx_check_max_load_factor(__f); 00822 _Base::max_load_factor(__f); 00823 } 00824 00825 template<typename... _Args> 00826 iterator 00827 emplace(_Args&&... __args) 00828 { 00829 size_type __bucket_count = this->bucket_count(); 00830 _Base_iterator __it 00831 = _Base::emplace(std::forward<_Args>(__args)...); 00832 _M_check_rehashed(__bucket_count); 00833 return iterator(__it, this); 00834 } 00835 00836 template<typename... _Args> 00837 iterator 00838 emplace_hint(const_iterator __hint, _Args&&... __args) 00839 { 00840 __glibcxx_check_insert(__hint); 00841 size_type __bucket_count = this->bucket_count(); 00842 _Base_iterator __it = _Base::emplace_hint(__hint.base(), 00843 std::forward<_Args>(__args)...); 00844 _M_check_rehashed(__bucket_count); 00845 return iterator(__it, this); 00846 } 00847 00848 iterator 00849 insert(const value_type& __obj) 00850 { 00851 size_type __bucket_count = this->bucket_count(); 00852 _Base_iterator __it = _Base::insert(__obj); 00853 _M_check_rehashed(__bucket_count); 00854 return iterator(__it, this); 00855 } 00856 00857 iterator 00858 insert(const_iterator __hint, const value_type& __obj) 00859 { 00860 __glibcxx_check_insert(__hint); 00861 size_type __bucket_count = this->bucket_count(); 00862 _Base_iterator __it = _Base::insert(__hint.base(), __obj); 00863 _M_check_rehashed(__bucket_count); 00864 return iterator(__it, this); 00865 } 00866 00867 template<typename _Pair, typename = typename 00868 std::enable_if<std::is_constructible<value_type, 00869 _Pair&&>::value>::type> 00870 iterator 00871 insert(_Pair&& __obj) 00872 { 00873 size_type __bucket_count = this->bucket_count(); 00874 _Base_iterator __it = _Base::insert(std::forward<_Pair>(__obj)); 00875 _M_check_rehashed(__bucket_count); 00876 return iterator(__it, this); 00877 } 00878 00879 template<typename _Pair, typename = typename 00880 std::enable_if<std::is_constructible<value_type, 00881 _Pair&&>::value>::type> 00882 iterator 00883 insert(const_iterator __hint, _Pair&& __obj) 00884 { 00885 __glibcxx_check_insert(__hint); 00886 size_type __bucket_count = this->bucket_count(); 00887 _Base_iterator __it = 00888 _Base::insert(__hint.base(), std::forward<_Pair>(__obj)); 00889 _M_check_rehashed(__bucket_count); 00890 return iterator(__it, this); 00891 } 00892 00893 void 00894 insert(std::initializer_list<value_type> __l) 00895 { _Base::insert(__l); } 00896 00897 template<typename _InputIterator> 00898 void 00899 insert(_InputIterator __first, _InputIterator __last) 00900 { 00901 typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist; 00902 __glibcxx_check_valid_range2(__first, __last, __dist); 00903 size_type __bucket_count = this->bucket_count(); 00904 00905 if (__dist.second >= __gnu_debug::__dp_sign) 00906 _Base::insert(__gnu_debug::__unsafe(__first), 00907 __gnu_debug::__unsafe(__last)); 00908 else 00909 _Base::insert(__first, __last); 00910 00911 _M_check_rehashed(__bucket_count); 00912 } 00913 00914 iterator 00915 find(const key_type& __key) 00916 { return iterator(_Base::find(__key), this); } 00917 00918 const_iterator 00919 find(const key_type& __key) const 00920 { return const_iterator(_Base::find(__key), this); } 00921 00922 std::pair<iterator, iterator> 00923 equal_range(const key_type& __key) 00924 { 00925 std::pair<_Base_iterator, _Base_iterator> __res = 00926 _Base::equal_range(__key); 00927 return std::make_pair(iterator(__res.first, this), 00928 iterator(__res.second, this)); 00929 } 00930 00931 std::pair<const_iterator, const_iterator> 00932 equal_range(const key_type& __key) const 00933 { 00934 std::pair<_Base_const_iterator, _Base_const_iterator> __res = 00935 _Base::equal_range(__key); 00936 return std::make_pair(const_iterator(__res.first, this), 00937 const_iterator(__res.second, this)); 00938 } 00939 00940 size_type 00941 erase(const key_type& __key) 00942 { 00943 size_type __ret(0); 00944 size_type __bucket_count = this->bucket_count(); 00945 std::pair<_Base_iterator, _Base_iterator> __pair = 00946 _Base::equal_range(__key); 00947 for (_Base_iterator __victim = __pair.first; __victim != __pair.second;) 00948 { 00949 this->_M_invalidate_if([__victim](_Base_const_iterator __it) 00950 { return __it == __victim; }); 00951 this->_M_invalidate_local_if( 00952 [__victim](_Base_const_local_iterator __it) 00953 { return __it._M_curr() == __victim._M_cur; }); 00954 _Base::erase(__victim++); 00955 ++__ret; 00956 } 00957 _M_check_rehashed(__bucket_count); 00958 return __ret; 00959 } 00960 00961 iterator 00962 erase(const_iterator __it) 00963 { 00964 __glibcxx_check_erase(__it); 00965 _Base_const_iterator __victim = __it.base(); 00966 this->_M_invalidate_if([__victim](_Base_const_iterator __it) 00967 { return __it == __victim; }); 00968 this->_M_invalidate_local_if( 00969 [__victim](_Base_const_local_iterator __it) 00970 { return __it._M_curr() == __victim._M_cur; }); 00971 size_type __bucket_count = this->bucket_count(); 00972 _Base_iterator __next = _Base::erase(__it.base()); 00973 _M_check_rehashed(__bucket_count); 00974 return iterator(__next, this); 00975 } 00976 00977 iterator 00978 erase(iterator __it) 00979 { return erase(const_iterator(__it)); } 00980 00981 iterator 00982 erase(const_iterator __first, const_iterator __last) 00983 { 00984 __glibcxx_check_erase_range(__first, __last); 00985 for (_Base_const_iterator __tmp = __first.base(); 00986 __tmp != __last.base(); ++__tmp) 00987 { 00988 _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(), 00989 _M_message(__gnu_debug::__msg_valid_range) 00990 ._M_iterator(__first, "first") 00991 ._M_iterator(__last, "last")); 00992 this->_M_invalidate_if([__tmp](_Base_const_iterator __it) 00993 { return __it == __tmp; }); 00994 this->_M_invalidate_local_if( 00995 [__tmp](_Base_const_local_iterator __it) 00996 { return __it._M_curr() == __tmp._M_cur; }); 00997 } 00998 size_type __bucket_count = this->bucket_count(); 00999 _Base_iterator __next = _Base::erase(__first.base(), __last.base()); 01000 _M_check_rehashed(__bucket_count); 01001 return iterator(__next, this); 01002 } 01003 01004 _Base& 01005 _M_base() noexcept { return *this; } 01006 01007 const _Base& 01008 _M_base() const noexcept { return *this; } 01009 01010 private: 01011 void 01012 _M_check_rehashed(size_type __prev_count) 01013 { 01014 if (__prev_count != this->bucket_count()) 01015 this->_M_invalidate_locals(); 01016 } 01017 }; 01018 01019 template<typename _Key, typename _Tp, typename _Hash, 01020 typename _Pred, typename _Alloc> 01021 inline void 01022 swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 01023 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 01024 noexcept(noexcept(__x.swap(__y))) 01025 { __x.swap(__y); } 01026 01027 template<typename _Key, typename _Tp, typename _Hash, 01028 typename _Pred, typename _Alloc> 01029 inline bool 01030 operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 01031 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 01032 { return __x._M_base() == __y._M_base(); } 01033 01034 template<typename _Key, typename _Tp, typename _Hash, 01035 typename _Pred, typename _Alloc> 01036 inline bool 01037 operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 01038 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 01039 { return !(__x == __y); } 01040 01041 } // namespace __debug 01042 } // namespace std 01043 01044 #endif // C++11 01045 01046 #endif