libstdc++
|
00001 // Debugging unordered_map/unordered_multimap implementation -*- C++ -*- 00002 00003 // Copyright (C) 2003-2019 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 #pragma GCC system_header 00033 00034 #if __cplusplus < 201103L 00035 # include <bits/c++0x_warning.h> 00036 #else 00037 # include <bits/c++config.h> 00038 namespace std _GLIBCXX_VISIBILITY(default) { namespace __debug { 00039 template<typename _Key, typename _Tp, typename _Hash, typename _Pred, 00040 typename _Allocator> 00041 class unordered_map; 00042 template<typename _Key, typename _Tp, typename _Hash, typename _Pred, 00043 typename _Allocator> 00044 class unordered_multimap; 00045 } } // namespace std::__debug 00046 00047 # include <unordered_map> 00048 00049 #include <debug/safe_unordered_container.h> 00050 #include <debug/safe_container.h> 00051 #include <debug/safe_iterator.h> 00052 #include <debug/safe_local_iterator.h> 00053 00054 namespace std _GLIBCXX_VISIBILITY(default) 00055 { 00056 namespace __debug 00057 { 00058 /// Class std::unordered_map with safety/checking/debug instrumentation. 00059 template<typename _Key, typename _Tp, 00060 typename _Hash = std::hash<_Key>, 00061 typename _Pred = std::equal_to<_Key>, 00062 typename _Alloc = std::allocator<std::pair<const _Key, _Tp> > > 00063 class unordered_map 00064 : public __gnu_debug::_Safe_container< 00065 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>, _Alloc, 00066 __gnu_debug::_Safe_unordered_container>, 00067 public _GLIBCXX_STD_C::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc> 00068 { 00069 typedef _GLIBCXX_STD_C::unordered_map<_Key, _Tp, _Hash, 00070 _Pred, _Alloc> _Base; 00071 typedef __gnu_debug::_Safe_container<unordered_map, 00072 _Alloc, __gnu_debug::_Safe_unordered_container> _Safe; 00073 typedef typename _Base::const_iterator _Base_const_iterator; 00074 typedef typename _Base::iterator _Base_iterator; 00075 typedef typename _Base::const_local_iterator 00076 _Base_const_local_iterator; 00077 typedef typename _Base::local_iterator _Base_local_iterator; 00078 00079 template<typename _ItT, typename _SeqT, typename _CatT> 00080 friend class ::__gnu_debug::_Safe_iterator; 00081 template<typename _ItT, typename _SeqT> 00082 friend class ::__gnu_debug::_Safe_local_iterator; 00083 00084 public: 00085 typedef typename _Base::size_type size_type; 00086 typedef typename _Base::hasher hasher; 00087 typedef typename _Base::key_equal key_equal; 00088 typedef typename _Base::allocator_type allocator_type; 00089 00090 typedef typename _Base::key_type key_type; 00091 typedef typename _Base::value_type value_type; 00092 00093 typedef __gnu_debug::_Safe_iterator< 00094 _Base_iterator, unordered_map> iterator; 00095 typedef __gnu_debug::_Safe_iterator< 00096 _Base_const_iterator, unordered_map> const_iterator; 00097 typedef __gnu_debug::_Safe_local_iterator< 00098 _Base_local_iterator, unordered_map> local_iterator; 00099 typedef __gnu_debug::_Safe_local_iterator< 00100 _Base_const_local_iterator, unordered_map> const_local_iterator; 00101 00102 unordered_map() = default; 00103 00104 explicit 00105 unordered_map(size_type __n, 00106 const hasher& __hf = hasher(), 00107 const key_equal& __eql = key_equal(), 00108 const allocator_type& __a = allocator_type()) 00109 : _Base(__n, __hf, __eql, __a) { } 00110 00111 template<typename _InputIterator> 00112 unordered_map(_InputIterator __first, _InputIterator __last, 00113 size_type __n = 0, 00114 const hasher& __hf = hasher(), 00115 const key_equal& __eql = key_equal(), 00116 const allocator_type& __a = allocator_type()) 00117 : _Base(__gnu_debug::__base( 00118 __glibcxx_check_valid_constructor_range(__first, __last)), 00119 __gnu_debug::__base(__last), __n, 00120 __hf, __eql, __a) { } 00121 00122 unordered_map(const unordered_map&) = default; 00123 00124 unordered_map(const _Base& __x) 00125 : _Base(__x) { } 00126 00127 unordered_map(unordered_map&&) = default; 00128 00129 explicit 00130 unordered_map(const allocator_type& __a) 00131 : _Base(__a) { } 00132 00133 unordered_map(const unordered_map& __umap, 00134 const allocator_type& __a) 00135 : _Base(__umap, __a) { } 00136 00137 unordered_map(unordered_map&& __umap, 00138 const allocator_type& __a) 00139 : _Safe(std::move(__umap._M_safe()), __a), 00140 _Base(std::move(__umap._M_base()), __a) { } 00141 00142 unordered_map(initializer_list<value_type> __l, 00143 size_type __n = 0, 00144 const hasher& __hf = hasher(), 00145 const key_equal& __eql = key_equal(), 00146 const allocator_type& __a = allocator_type()) 00147 : _Base(__l, __n, __hf, __eql, __a) { } 00148 00149 unordered_map(size_type __n, const allocator_type& __a) 00150 : unordered_map(__n, hasher(), key_equal(), __a) 00151 { } 00152 00153 unordered_map(size_type __n, 00154 const hasher& __hf, 00155 const allocator_type& __a) 00156 : unordered_map(__n, __hf, key_equal(), __a) 00157 { } 00158 00159 template<typename _InputIterator> 00160 unordered_map(_InputIterator __first, _InputIterator __last, 00161 size_type __n, 00162 const allocator_type& __a) 00163 : unordered_map(__first, __last, __n, hasher(), key_equal(), __a) 00164 { } 00165 00166 template<typename _InputIterator> 00167 unordered_map(_InputIterator __first, _InputIterator __last, 00168 size_type __n, 00169 const hasher& __hf, 00170 const allocator_type& __a) 00171 : unordered_map(__first, __last, __n, __hf, key_equal(), __a) 00172 { } 00173 00174 unordered_map(initializer_list<value_type> __l, 00175 size_type __n, 00176 const allocator_type& __a) 00177 : unordered_map(__l, __n, hasher(), key_equal(), __a) 00178 { } 00179 00180 unordered_map(initializer_list<value_type> __l, 00181 size_type __n, 00182 const hasher& __hf, 00183 const allocator_type& __a) 00184 : unordered_map(__l, __n, __hf, key_equal(), __a) 00185 { } 00186 00187 ~unordered_map() = default; 00188 00189 unordered_map& 00190 operator=(const unordered_map&) = default; 00191 00192 unordered_map& 00193 operator=(unordered_map&&) = default; 00194 00195 unordered_map& 00196 operator=(initializer_list<value_type> __l) 00197 { 00198 _M_base() = __l; 00199 this->_M_invalidate_all(); 00200 return *this; 00201 } 00202 00203 void 00204 swap(unordered_map& __x) 00205 noexcept( noexcept(declval<_Base&>().swap(__x)) ) 00206 { 00207 _Safe::_M_swap(__x); 00208 _Base::swap(__x); 00209 } 00210 00211 void 00212 clear() noexcept 00213 { 00214 _Base::clear(); 00215 this->_M_invalidate_all(); 00216 } 00217 00218 iterator 00219 begin() noexcept 00220 { return { _Base::begin(), this }; } 00221 00222 const_iterator 00223 begin() const noexcept 00224 { return { _Base::begin(), this }; } 00225 00226 iterator 00227 end() noexcept 00228 { return { _Base::end(), this }; } 00229 00230 const_iterator 00231 end() const noexcept 00232 { return { _Base::end(), this }; } 00233 00234 const_iterator 00235 cbegin() const noexcept 00236 { return { _Base::cbegin(), this }; } 00237 00238 const_iterator 00239 cend() const noexcept 00240 { return { _Base::cend(), this }; } 00241 00242 // local versions 00243 local_iterator 00244 begin(size_type __b) 00245 { 00246 __glibcxx_check_bucket_index(__b); 00247 return { _Base::begin(__b), this }; 00248 } 00249 00250 local_iterator 00251 end(size_type __b) 00252 { 00253 __glibcxx_check_bucket_index(__b); 00254 return { _Base::end(__b), this }; 00255 } 00256 00257 const_local_iterator 00258 begin(size_type __b) const 00259 { 00260 __glibcxx_check_bucket_index(__b); 00261 return { _Base::begin(__b), this }; 00262 } 00263 00264 const_local_iterator 00265 end(size_type __b) const 00266 { 00267 __glibcxx_check_bucket_index(__b); 00268 return { _Base::end(__b), this }; 00269 } 00270 00271 const_local_iterator 00272 cbegin(size_type __b) const 00273 { 00274 __glibcxx_check_bucket_index(__b); 00275 return { _Base::cbegin(__b), this }; 00276 } 00277 00278 const_local_iterator 00279 cend(size_type __b) const 00280 { 00281 __glibcxx_check_bucket_index(__b); 00282 return { _Base::cend(__b), this }; 00283 } 00284 00285 size_type 00286 bucket_size(size_type __b) const 00287 { 00288 __glibcxx_check_bucket_index(__b); 00289 return _Base::bucket_size(__b); 00290 } 00291 00292 float 00293 max_load_factor() const noexcept 00294 { return _Base::max_load_factor(); } 00295 00296 void 00297 max_load_factor(float __f) 00298 { 00299 __glibcxx_check_max_load_factor(__f); 00300 _Base::max_load_factor(__f); 00301 } 00302 00303 template<typename... _Args> 00304 std::pair<iterator, bool> 00305 emplace(_Args&&... __args) 00306 { 00307 size_type __bucket_count = this->bucket_count(); 00308 auto __res = _Base::emplace(std::forward<_Args>(__args)...); 00309 _M_check_rehashed(__bucket_count); 00310 return { { __res.first, this }, __res.second }; 00311 } 00312 00313 template<typename... _Args> 00314 iterator 00315 emplace_hint(const_iterator __hint, _Args&&... __args) 00316 { 00317 __glibcxx_check_insert(__hint); 00318 size_type __bucket_count = this->bucket_count(); 00319 auto __it = _Base::emplace_hint(__hint.base(), 00320 std::forward<_Args>(__args)...); 00321 _M_check_rehashed(__bucket_count); 00322 return { __it, this }; 00323 } 00324 00325 std::pair<iterator, bool> 00326 insert(const value_type& __obj) 00327 { 00328 size_type __bucket_count = this->bucket_count(); 00329 auto __res = _Base::insert(__obj); 00330 _M_check_rehashed(__bucket_count); 00331 return { { __res.first, this }, __res.second }; 00332 } 00333 00334 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00335 // 2354. Unnecessary copying when inserting into maps with braced-init 00336 std::pair<iterator, bool> 00337 insert(value_type&& __x) 00338 { 00339 size_type __bucket_count = this->bucket_count(); 00340 auto __res = _Base::insert(std::move(__x)); 00341 _M_check_rehashed(__bucket_count); 00342 return { { __res.first, this }, __res.second }; 00343 } 00344 00345 template<typename _Pair, typename = typename 00346 std::enable_if<std::is_constructible<value_type, 00347 _Pair&&>::value>::type> 00348 std::pair<iterator, bool> 00349 insert(_Pair&& __obj) 00350 { 00351 size_type __bucket_count = this->bucket_count(); 00352 auto __res = _Base::insert(std::forward<_Pair>(__obj)); 00353 _M_check_rehashed(__bucket_count); 00354 return { { __res.first, this }, __res.second }; 00355 } 00356 00357 iterator 00358 insert(const_iterator __hint, const value_type& __obj) 00359 { 00360 __glibcxx_check_insert(__hint); 00361 size_type __bucket_count = this->bucket_count(); 00362 auto __it = _Base::insert(__hint.base(), __obj); 00363 _M_check_rehashed(__bucket_count); 00364 return { __it, this }; 00365 } 00366 00367 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00368 // 2354. Unnecessary copying when inserting into maps with braced-init 00369 iterator 00370 insert(const_iterator __hint, value_type&& __x) 00371 { 00372 __glibcxx_check_insert(__hint); 00373 size_type __bucket_count = this->bucket_count(); 00374 auto __it = _Base::insert(__hint.base(), std::move(__x)); 00375 _M_check_rehashed(__bucket_count); 00376 return { __it, this }; 00377 } 00378 00379 template<typename _Pair, typename = typename 00380 std::enable_if<std::is_constructible<value_type, 00381 _Pair&&>::value>::type> 00382 iterator 00383 insert(const_iterator __hint, _Pair&& __obj) 00384 { 00385 __glibcxx_check_insert(__hint); 00386 size_type __bucket_count = this->bucket_count(); 00387 auto __it = _Base::insert(__hint.base(), std::forward<_Pair>(__obj)); 00388 _M_check_rehashed(__bucket_count); 00389 return { __it, this }; 00390 } 00391 00392 void 00393 insert(std::initializer_list<value_type> __l) 00394 { 00395 size_type __bucket_count = this->bucket_count(); 00396 _Base::insert(__l); 00397 _M_check_rehashed(__bucket_count); 00398 } 00399 00400 template<typename _InputIterator> 00401 void 00402 insert(_InputIterator __first, _InputIterator __last) 00403 { 00404 typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist; 00405 __glibcxx_check_valid_range2(__first, __last, __dist); 00406 size_type __bucket_count = this->bucket_count(); 00407 00408 if (__dist.second >= __gnu_debug::__dp_sign) 00409 _Base::insert(__gnu_debug::__unsafe(__first), 00410 __gnu_debug::__unsafe(__last)); 00411 else 00412 _Base::insert(__first, __last); 00413 00414 _M_check_rehashed(__bucket_count); 00415 } 00416 00417 #if __cplusplus > 201402L 00418 template <typename... _Args> 00419 pair<iterator, bool> 00420 try_emplace(const key_type& __k, _Args&&... __args) 00421 { 00422 auto __res = _Base::try_emplace(__k, 00423 std::forward<_Args>(__args)...); 00424 return { { __res.first, this }, __res.second }; 00425 } 00426 00427 template <typename... _Args> 00428 pair<iterator, bool> 00429 try_emplace(key_type&& __k, _Args&&... __args) 00430 { 00431 auto __res = _Base::try_emplace(std::move(__k), 00432 std::forward<_Args>(__args)...); 00433 return { { __res.first, this }, __res.second }; 00434 } 00435 00436 template <typename... _Args> 00437 iterator 00438 try_emplace(const_iterator __hint, const key_type& __k, 00439 _Args&&... __args) 00440 { 00441 __glibcxx_check_insert(__hint); 00442 return { _Base::try_emplace(__hint.base(), __k, 00443 std::forward<_Args>(__args)...), 00444 this }; 00445 } 00446 00447 template <typename... _Args> 00448 iterator 00449 try_emplace(const_iterator __hint, key_type&& __k, _Args&&... __args) 00450 { 00451 __glibcxx_check_insert(__hint); 00452 return { _Base::try_emplace(__hint.base(), std::move(__k), 00453 std::forward<_Args>(__args)...), 00454 this }; 00455 } 00456 00457 template <typename _Obj> 00458 pair<iterator, bool> 00459 insert_or_assign(const key_type& __k, _Obj&& __obj) 00460 { 00461 auto __res = _Base::insert_or_assign(__k, 00462 std::forward<_Obj>(__obj)); 00463 return { { __res.first, this }, __res.second }; 00464 } 00465 00466 template <typename _Obj> 00467 pair<iterator, bool> 00468 insert_or_assign(key_type&& __k, _Obj&& __obj) 00469 { 00470 auto __res = _Base::insert_or_assign(std::move(__k), 00471 std::forward<_Obj>(__obj)); 00472 return { { __res.first, this }, __res.second }; 00473 } 00474 00475 template <typename _Obj> 00476 iterator 00477 insert_or_assign(const_iterator __hint, const key_type& __k, 00478 _Obj&& __obj) 00479 { 00480 __glibcxx_check_insert(__hint); 00481 return { _Base::insert_or_assign(__hint.base(), __k, 00482 std::forward<_Obj>(__obj)), 00483 this }; 00484 } 00485 00486 template <typename _Obj> 00487 iterator 00488 insert_or_assign(const_iterator __hint, key_type&& __k, _Obj&& __obj) 00489 { 00490 __glibcxx_check_insert(__hint); 00491 return { _Base::insert_or_assign(__hint.base(), std::move(__k), 00492 std::forward<_Obj>(__obj)), 00493 this }; 00494 } 00495 #endif // C++17 00496 00497 #if __cplusplus > 201402L 00498 using node_type = typename _Base::node_type; 00499 using insert_return_type = _Node_insert_return<iterator, node_type>; 00500 00501 node_type 00502 extract(const_iterator __position) 00503 { 00504 __glibcxx_check_erase(__position); 00505 return _M_extract(__position.base()); 00506 } 00507 00508 node_type 00509 extract(const key_type& __key) 00510 { 00511 const auto __position = _Base::find(__key); 00512 if (__position != _Base::end()) 00513 return _M_extract(__position); 00514 return {}; 00515 } 00516 00517 insert_return_type 00518 insert(node_type&& __nh) 00519 { 00520 auto __ret = _Base::insert(std::move(__nh)); 00521 return 00522 { { __ret.position, this }, __ret.inserted, std::move(__ret.node) }; 00523 } 00524 00525 iterator 00526 insert(const_iterator __hint, node_type&& __nh) 00527 { 00528 __glibcxx_check_insert(__hint); 00529 return { _Base::insert(__hint.base(), std::move(__nh)), this }; 00530 } 00531 00532 using _Base::merge; 00533 #endif // C++17 00534 00535 iterator 00536 find(const key_type& __key) 00537 { return { _Base::find(__key), this }; } 00538 00539 const_iterator 00540 find(const key_type& __key) const 00541 { return { _Base::find(__key), this }; } 00542 00543 std::pair<iterator, iterator> 00544 equal_range(const key_type& __key) 00545 { 00546 auto __res = _Base::equal_range(__key); 00547 return { { __res.first, this }, { __res.second, this } }; 00548 } 00549 00550 std::pair<const_iterator, const_iterator> 00551 equal_range(const key_type& __key) const 00552 { 00553 auto __res = _Base::equal_range(__key); 00554 return { { __res.first, this }, { __res.second, this } }; 00555 } 00556 00557 size_type 00558 erase(const key_type& __key) 00559 { 00560 size_type __ret(0); 00561 auto __victim = _Base::find(__key); 00562 if (__victim != _Base::end()) 00563 { 00564 _M_erase(__victim); 00565 __ret = 1; 00566 } 00567 return __ret; 00568 } 00569 00570 iterator 00571 erase(const_iterator __it) 00572 { 00573 __glibcxx_check_erase(__it); 00574 return { _M_erase(__it.base()), this }; 00575 } 00576 00577 iterator 00578 erase(iterator __it) 00579 { 00580 __glibcxx_check_erase(__it); 00581 return { _M_erase(__it.base()), this }; 00582 } 00583 00584 iterator 00585 erase(const_iterator __first, const_iterator __last) 00586 { 00587 __glibcxx_check_erase_range(__first, __last); 00588 for (auto __tmp = __first.base(); __tmp != __last.base(); ++__tmp) 00589 { 00590 _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::cend(), 00591 _M_message(__gnu_debug::__msg_valid_range) 00592 ._M_iterator(__first, "first") 00593 ._M_iterator(__last, "last")); 00594 _M_invalidate(__tmp); 00595 } 00596 00597 size_type __bucket_count = this->bucket_count(); 00598 auto __next = _Base::erase(__first.base(), __last.base()); 00599 _M_check_rehashed(__bucket_count); 00600 return { __next, this }; 00601 } 00602 00603 _Base& 00604 _M_base() noexcept { return *this; } 00605 00606 const _Base& 00607 _M_base() const noexcept { return *this; } 00608 00609 private: 00610 void 00611 _M_check_rehashed(size_type __prev_count) 00612 { 00613 if (__prev_count != this->bucket_count()) 00614 this->_M_invalidate_all(); 00615 } 00616 00617 void 00618 _M_invalidate(_Base_const_iterator __victim) 00619 { 00620 this->_M_invalidate_if( 00621 [__victim](_Base_const_iterator __it) { return __it == __victim; }); 00622 this->_M_invalidate_local_if( 00623 [__victim](_Base_const_local_iterator __it) 00624 { return __it._M_curr() == __victim._M_cur; }); 00625 } 00626 00627 _Base_iterator 00628 _M_erase(_Base_const_iterator __victim) 00629 { 00630 _M_invalidate(__victim); 00631 size_type __bucket_count = this->bucket_count(); 00632 _Base_iterator __next = _Base::erase(__victim); 00633 _M_check_rehashed(__bucket_count); 00634 return __next; 00635 } 00636 00637 #if __cplusplus > 201402L 00638 node_type 00639 _M_extract(_Base_const_iterator __victim) 00640 { 00641 _M_invalidate(__victim); 00642 return _Base::extract(__victim); 00643 } 00644 #endif 00645 }; 00646 00647 #if __cpp_deduction_guides >= 201606 00648 00649 template<typename _InputIterator, 00650 typename _Hash = hash<__iter_key_t<_InputIterator>>, 00651 typename _Pred = equal_to<__iter_key_t<_InputIterator>>, 00652 typename _Allocator = allocator<__iter_to_alloc_t<_InputIterator>>, 00653 typename = _RequireInputIter<_InputIterator>, 00654 typename = _RequireNotAllocatorOrIntegral<_Hash>, 00655 typename = _RequireNotAllocator<_Pred>, 00656 typename = _RequireAllocator<_Allocator>> 00657 unordered_map(_InputIterator, _InputIterator, 00658 typename unordered_map<int, int>::size_type = {}, 00659 _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator()) 00660 -> unordered_map<__iter_key_t<_InputIterator>, 00661 __iter_val_t<_InputIterator>, 00662 _Hash, _Pred, _Allocator>; 00663 00664 template<typename _Key, typename _Tp, typename _Hash = hash<_Key>, 00665 typename _Pred = equal_to<_Key>, 00666 typename _Allocator = allocator<pair<const _Key, _Tp>>, 00667 typename = _RequireNotAllocatorOrIntegral<_Hash>, 00668 typename = _RequireNotAllocator<_Pred>, 00669 typename = _RequireAllocator<_Allocator>> 00670 unordered_map(initializer_list<pair<_Key, _Tp>>, 00671 typename unordered_map<int, int>::size_type = {}, 00672 _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator()) 00673 -> unordered_map<_Key, _Tp, _Hash, _Pred, _Allocator>; 00674 00675 template<typename _InputIterator, typename _Allocator, 00676 typename = _RequireInputIter<_InputIterator>, 00677 typename = _RequireAllocator<_Allocator>> 00678 unordered_map(_InputIterator, _InputIterator, 00679 typename unordered_map<int, int>::size_type, _Allocator) 00680 -> unordered_map<__iter_key_t<_InputIterator>, 00681 __iter_val_t<_InputIterator>, 00682 hash<__iter_key_t<_InputIterator>>, 00683 equal_to<__iter_key_t<_InputIterator>>, 00684 _Allocator>; 00685 00686 template<typename _InputIterator, typename _Allocator, 00687 typename = _RequireInputIter<_InputIterator>, 00688 typename = _RequireAllocator<_Allocator>> 00689 unordered_map(_InputIterator, _InputIterator, _Allocator) 00690 -> unordered_map<__iter_key_t<_InputIterator>, 00691 __iter_val_t<_InputIterator>, 00692 hash<__iter_key_t<_InputIterator>>, 00693 equal_to<__iter_key_t<_InputIterator>>, 00694 _Allocator>; 00695 00696 template<typename _InputIterator, typename _Hash, typename _Allocator, 00697 typename = _RequireInputIter<_InputIterator>, 00698 typename = _RequireNotAllocatorOrIntegral<_Hash>, 00699 typename = _RequireAllocator<_Allocator>> 00700 unordered_map(_InputIterator, _InputIterator, 00701 typename unordered_map<int, int>::size_type, 00702 _Hash, _Allocator) 00703 -> unordered_map<__iter_key_t<_InputIterator>, 00704 __iter_val_t<_InputIterator>, _Hash, 00705 equal_to<__iter_key_t<_InputIterator>>, _Allocator>; 00706 00707 template<typename _Key, typename _Tp, typename _Allocator, 00708 typename = _RequireAllocator<_Allocator>> 00709 unordered_map(initializer_list<pair<_Key, _Tp>>, 00710 typename unordered_map<int, int>::size_type, 00711 _Allocator) 00712 -> unordered_map<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>; 00713 00714 template<typename _Key, typename _Tp, typename _Allocator, 00715 typename = _RequireAllocator<_Allocator>> 00716 unordered_map(initializer_list<pair<_Key, _Tp>>, _Allocator) 00717 -> unordered_map<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>; 00718 00719 template<typename _Key, typename _Tp, typename _Hash, typename _Allocator, 00720 typename = _RequireNotAllocatorOrIntegral<_Hash>, 00721 typename = _RequireAllocator<_Allocator>> 00722 unordered_map(initializer_list<pair<_Key, _Tp>>, 00723 typename unordered_map<int, int>::size_type, 00724 _Hash, _Allocator) 00725 -> unordered_map<_Key, _Tp, _Hash, equal_to<_Key>, _Allocator>; 00726 00727 #endif 00728 00729 template<typename _Key, typename _Tp, typename _Hash, 00730 typename _Pred, typename _Alloc> 00731 inline void 00732 swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 00733 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 00734 noexcept(noexcept(__x.swap(__y))) 00735 { __x.swap(__y); } 00736 00737 template<typename _Key, typename _Tp, typename _Hash, 00738 typename _Pred, typename _Alloc> 00739 inline bool 00740 operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 00741 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 00742 { return __x._M_base() == __y._M_base(); } 00743 00744 template<typename _Key, typename _Tp, typename _Hash, 00745 typename _Pred, typename _Alloc> 00746 inline bool 00747 operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 00748 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 00749 { return !(__x == __y); } 00750 00751 00752 /// Class std::unordered_multimap with safety/checking/debug instrumentation. 00753 template<typename _Key, typename _Tp, 00754 typename _Hash = std::hash<_Key>, 00755 typename _Pred = std::equal_to<_Key>, 00756 typename _Alloc = std::allocator<std::pair<const _Key, _Tp> > > 00757 class unordered_multimap 00758 : public __gnu_debug::_Safe_container< 00759 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>, _Alloc, 00760 __gnu_debug::_Safe_unordered_container>, 00761 public _GLIBCXX_STD_C::unordered_multimap< 00762 _Key, _Tp, _Hash, _Pred, _Alloc> 00763 { 00764 typedef _GLIBCXX_STD_C::unordered_multimap<_Key, _Tp, _Hash, 00765 _Pred, _Alloc> _Base; 00766 typedef __gnu_debug::_Safe_container<unordered_multimap, 00767 _Alloc, __gnu_debug::_Safe_unordered_container> _Safe; 00768 typedef typename _Base::const_iterator _Base_const_iterator; 00769 typedef typename _Base::iterator _Base_iterator; 00770 typedef typename _Base::const_local_iterator _Base_const_local_iterator; 00771 typedef typename _Base::local_iterator _Base_local_iterator; 00772 00773 template<typename _ItT, typename _SeqT, typename _CatT> 00774 friend class ::__gnu_debug::_Safe_iterator; 00775 template<typename _ItT, typename _SeqT> 00776 friend class ::__gnu_debug::_Safe_local_iterator; 00777 00778 public: 00779 typedef typename _Base::size_type size_type; 00780 typedef typename _Base::hasher hasher; 00781 typedef typename _Base::key_equal key_equal; 00782 typedef typename _Base::allocator_type allocator_type; 00783 00784 typedef typename _Base::key_type key_type; 00785 typedef typename _Base::value_type value_type; 00786 00787 typedef __gnu_debug::_Safe_iterator< 00788 _Base_iterator, unordered_multimap> iterator; 00789 typedef __gnu_debug::_Safe_iterator< 00790 _Base_const_iterator, unordered_multimap> const_iterator; 00791 typedef __gnu_debug::_Safe_local_iterator< 00792 _Base_local_iterator, unordered_multimap> local_iterator; 00793 typedef __gnu_debug::_Safe_local_iterator< 00794 _Base_const_local_iterator, unordered_multimap> const_local_iterator; 00795 00796 unordered_multimap() = default; 00797 00798 explicit 00799 unordered_multimap(size_type __n, 00800 const hasher& __hf = hasher(), 00801 const key_equal& __eql = key_equal(), 00802 const allocator_type& __a = allocator_type()) 00803 : _Base(__n, __hf, __eql, __a) { } 00804 00805 template<typename _InputIterator> 00806 unordered_multimap(_InputIterator __first, _InputIterator __last, 00807 size_type __n = 0, 00808 const hasher& __hf = hasher(), 00809 const key_equal& __eql = key_equal(), 00810 const allocator_type& __a = allocator_type()) 00811 : _Base(__gnu_debug::__base( 00812 __glibcxx_check_valid_constructor_range(__first, __last)), 00813 __gnu_debug::__base(__last), __n, 00814 __hf, __eql, __a) { } 00815 00816 unordered_multimap(const unordered_multimap&) = default; 00817 00818 unordered_multimap(const _Base& __x) 00819 : _Base(__x) { } 00820 00821 unordered_multimap(unordered_multimap&&) = default; 00822 00823 explicit 00824 unordered_multimap(const allocator_type& __a) 00825 : _Base(__a) { } 00826 00827 unordered_multimap(const unordered_multimap& __umap, 00828 const allocator_type& __a) 00829 : _Base(__umap, __a) { } 00830 00831 unordered_multimap(unordered_multimap&& __umap, 00832 const allocator_type& __a) 00833 : _Safe(std::move(__umap._M_safe()), __a), 00834 _Base(std::move(__umap._M_base()), __a) { } 00835 00836 unordered_multimap(initializer_list<value_type> __l, 00837 size_type __n = 0, 00838 const hasher& __hf = hasher(), 00839 const key_equal& __eql = key_equal(), 00840 const allocator_type& __a = allocator_type()) 00841 : _Base(__l, __n, __hf, __eql, __a) { } 00842 00843 unordered_multimap(size_type __n, const allocator_type& __a) 00844 : unordered_multimap(__n, hasher(), key_equal(), __a) 00845 { } 00846 00847 unordered_multimap(size_type __n, const hasher& __hf, 00848 const allocator_type& __a) 00849 : unordered_multimap(__n, __hf, key_equal(), __a) 00850 { } 00851 00852 template<typename _InputIterator> 00853 unordered_multimap(_InputIterator __first, _InputIterator __last, 00854 size_type __n, 00855 const allocator_type& __a) 00856 : unordered_multimap(__first, __last, __n, hasher(), key_equal(), __a) 00857 { } 00858 00859 template<typename _InputIterator> 00860 unordered_multimap(_InputIterator __first, _InputIterator __last, 00861 size_type __n, const hasher& __hf, 00862 const allocator_type& __a) 00863 : unordered_multimap(__first, __last, __n, __hf, key_equal(), __a) 00864 { } 00865 00866 unordered_multimap(initializer_list<value_type> __l, 00867 size_type __n, 00868 const allocator_type& __a) 00869 : unordered_multimap(__l, __n, hasher(), key_equal(), __a) 00870 { } 00871 00872 unordered_multimap(initializer_list<value_type> __l, 00873 size_type __n, const hasher& __hf, 00874 const allocator_type& __a) 00875 : unordered_multimap(__l, __n, __hf, key_equal(), __a) 00876 { } 00877 00878 ~unordered_multimap() = default; 00879 00880 unordered_multimap& 00881 operator=(const unordered_multimap&) = default; 00882 00883 unordered_multimap& 00884 operator=(unordered_multimap&&) = default; 00885 00886 unordered_multimap& 00887 operator=(initializer_list<value_type> __l) 00888 { 00889 this->_M_base() = __l; 00890 this->_M_invalidate_all(); 00891 return *this; 00892 } 00893 00894 void 00895 swap(unordered_multimap& __x) 00896 noexcept( noexcept(declval<_Base&>().swap(__x)) ) 00897 { 00898 _Safe::_M_swap(__x); 00899 _Base::swap(__x); 00900 } 00901 00902 void 00903 clear() noexcept 00904 { 00905 _Base::clear(); 00906 this->_M_invalidate_all(); 00907 } 00908 00909 iterator 00910 begin() noexcept 00911 { return { _Base::begin(), this }; } 00912 00913 const_iterator 00914 begin() const noexcept 00915 { return { _Base::begin(), this }; } 00916 00917 iterator 00918 end() noexcept 00919 { return { _Base::end(), this }; } 00920 00921 const_iterator 00922 end() const noexcept 00923 { return { _Base::end(), this }; } 00924 00925 const_iterator 00926 cbegin() const noexcept 00927 { return { _Base::cbegin(), this }; } 00928 00929 const_iterator 00930 cend() const noexcept 00931 { return { _Base::cend(), this }; } 00932 00933 // local versions 00934 local_iterator 00935 begin(size_type __b) 00936 { 00937 __glibcxx_check_bucket_index(__b); 00938 return { _Base::begin(__b), this }; 00939 } 00940 00941 local_iterator 00942 end(size_type __b) 00943 { 00944 __glibcxx_check_bucket_index(__b); 00945 return { _Base::end(__b), this }; 00946 } 00947 00948 const_local_iterator 00949 begin(size_type __b) const 00950 { 00951 __glibcxx_check_bucket_index(__b); 00952 return { _Base::begin(__b), this }; 00953 } 00954 00955 const_local_iterator 00956 end(size_type __b) const 00957 { 00958 __glibcxx_check_bucket_index(__b); 00959 return { _Base::end(__b), this }; 00960 } 00961 00962 const_local_iterator 00963 cbegin(size_type __b) const 00964 { 00965 __glibcxx_check_bucket_index(__b); 00966 return { _Base::cbegin(__b), this }; 00967 } 00968 00969 const_local_iterator 00970 cend(size_type __b) const 00971 { 00972 __glibcxx_check_bucket_index(__b); 00973 return { _Base::cend(__b), this }; 00974 } 00975 00976 size_type 00977 bucket_size(size_type __b) const 00978 { 00979 __glibcxx_check_bucket_index(__b); 00980 return _Base::bucket_size(__b); 00981 } 00982 00983 float 00984 max_load_factor() const noexcept 00985 { return _Base::max_load_factor(); } 00986 00987 void 00988 max_load_factor(float __f) 00989 { 00990 __glibcxx_check_max_load_factor(__f); 00991 _Base::max_load_factor(__f); 00992 } 00993 00994 template<typename... _Args> 00995 iterator 00996 emplace(_Args&&... __args) 00997 { 00998 size_type __bucket_count = this->bucket_count(); 00999 auto __it = _Base::emplace(std::forward<_Args>(__args)...); 01000 _M_check_rehashed(__bucket_count); 01001 return { __it, this }; 01002 } 01003 01004 template<typename... _Args> 01005 iterator 01006 emplace_hint(const_iterator __hint, _Args&&... __args) 01007 { 01008 __glibcxx_check_insert(__hint); 01009 size_type __bucket_count = this->bucket_count(); 01010 auto __it = _Base::emplace_hint(__hint.base(), 01011 std::forward<_Args>(__args)...); 01012 _M_check_rehashed(__bucket_count); 01013 return { __it, this }; 01014 } 01015 01016 iterator 01017 insert(const value_type& __obj) 01018 { 01019 size_type __bucket_count = this->bucket_count(); 01020 auto __it = _Base::insert(__obj); 01021 _M_check_rehashed(__bucket_count); 01022 return { __it, this }; 01023 } 01024 01025 // _GLIBCXX_RESOLVE_LIB_DEFECTS 01026 // 2354. Unnecessary copying when inserting into maps with braced-init 01027 iterator 01028 insert(value_type&& __x) 01029 { 01030 size_type __bucket_count = this->bucket_count(); 01031 auto __it = _Base::insert(std::move(__x)); 01032 _M_check_rehashed(__bucket_count); 01033 return { __it, this }; 01034 } 01035 01036 iterator 01037 insert(const_iterator __hint, const value_type& __obj) 01038 { 01039 __glibcxx_check_insert(__hint); 01040 size_type __bucket_count = this->bucket_count(); 01041 auto __it = _Base::insert(__hint.base(), __obj); 01042 _M_check_rehashed(__bucket_count); 01043 return { __it, this }; 01044 } 01045 01046 // _GLIBCXX_RESOLVE_LIB_DEFECTS 01047 // 2354. Unnecessary copying when inserting into maps with braced-init 01048 iterator 01049 insert(const_iterator __hint, value_type&& __x) 01050 { 01051 __glibcxx_check_insert(__hint); 01052 size_type __bucket_count = this->bucket_count(); 01053 auto __it = _Base::insert(__hint.base(), std::move(__x)); 01054 _M_check_rehashed(__bucket_count); 01055 return { __it, this }; 01056 } 01057 01058 template<typename _Pair, typename = typename 01059 std::enable_if<std::is_constructible<value_type, 01060 _Pair&&>::value>::type> 01061 iterator 01062 insert(_Pair&& __obj) 01063 { 01064 size_type __bucket_count = this->bucket_count(); 01065 auto __it = _Base::insert(std::forward<_Pair>(__obj)); 01066 _M_check_rehashed(__bucket_count); 01067 return { __it, this }; 01068 } 01069 01070 template<typename _Pair, typename = typename 01071 std::enable_if<std::is_constructible<value_type, 01072 _Pair&&>::value>::type> 01073 iterator 01074 insert(const_iterator __hint, _Pair&& __obj) 01075 { 01076 __glibcxx_check_insert(__hint); 01077 size_type __bucket_count = this->bucket_count(); 01078 auto __it = _Base::insert(__hint.base(), std::forward<_Pair>(__obj)); 01079 _M_check_rehashed(__bucket_count); 01080 return { __it, this }; 01081 } 01082 01083 void 01084 insert(std::initializer_list<value_type> __l) 01085 { _Base::insert(__l); } 01086 01087 template<typename _InputIterator> 01088 void 01089 insert(_InputIterator __first, _InputIterator __last) 01090 { 01091 typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist; 01092 __glibcxx_check_valid_range2(__first, __last, __dist); 01093 size_type __bucket_count = this->bucket_count(); 01094 01095 if (__dist.second >= __gnu_debug::__dp_sign) 01096 _Base::insert(__gnu_debug::__unsafe(__first), 01097 __gnu_debug::__unsafe(__last)); 01098 else 01099 _Base::insert(__first, __last); 01100 01101 _M_check_rehashed(__bucket_count); 01102 } 01103 01104 #if __cplusplus > 201402L 01105 using node_type = typename _Base::node_type; 01106 01107 node_type 01108 extract(const_iterator __position) 01109 { 01110 __glibcxx_check_erase(__position); 01111 return _M_extract(__position.base()); 01112 } 01113 01114 node_type 01115 extract(const key_type& __key) 01116 { 01117 const auto __position = _Base::find(__key); 01118 if (__position != _Base::end()) 01119 return _M_extract(__position); 01120 return {}; 01121 } 01122 01123 iterator 01124 insert(node_type&& __nh) 01125 { return { _Base::insert(std::move(__nh)), this }; } 01126 01127 iterator 01128 insert(const_iterator __hint, node_type&& __nh) 01129 { 01130 __glibcxx_check_insert(__hint); 01131 return { _Base::insert(__hint.base(), std::move(__nh)), this }; 01132 } 01133 01134 using _Base::merge; 01135 #endif // C++17 01136 01137 iterator 01138 find(const key_type& __key) 01139 { return { _Base::find(__key), this }; } 01140 01141 const_iterator 01142 find(const key_type& __key) const 01143 { return { _Base::find(__key), this }; } 01144 01145 std::pair<iterator, iterator> 01146 equal_range(const key_type& __key) 01147 { 01148 auto __res = _Base::equal_range(__key); 01149 return { { __res.first, this }, { __res.second, this } }; 01150 } 01151 01152 std::pair<const_iterator, const_iterator> 01153 equal_range(const key_type& __key) const 01154 { 01155 auto __res = _Base::equal_range(__key); 01156 return { { __res.first, this }, { __res.second, this } }; 01157 } 01158 01159 size_type 01160 erase(const key_type& __key) 01161 { 01162 size_type __ret(0); 01163 size_type __bucket_count = this->bucket_count(); 01164 auto __pair = _Base::equal_range(__key); 01165 for (auto __victim = __pair.first; __victim != __pair.second;) 01166 { 01167 _M_invalidate(__victim); 01168 __victim = _Base::erase(__victim); 01169 ++__ret; 01170 } 01171 01172 _M_check_rehashed(__bucket_count); 01173 return __ret; 01174 } 01175 01176 iterator 01177 erase(const_iterator __it) 01178 { 01179 __glibcxx_check_erase(__it); 01180 return { _M_erase(__it.base()), this }; 01181 } 01182 01183 iterator 01184 erase(iterator __it) 01185 { 01186 __glibcxx_check_erase(__it); 01187 return { _M_erase(__it.base()), this }; 01188 } 01189 01190 iterator 01191 erase(const_iterator __first, const_iterator __last) 01192 { 01193 __glibcxx_check_erase_range(__first, __last); 01194 for (auto __tmp = __first.base(); __tmp != __last.base(); ++__tmp) 01195 { 01196 _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::cend(), 01197 _M_message(__gnu_debug::__msg_valid_range) 01198 ._M_iterator(__first, "first") 01199 ._M_iterator(__last, "last")); 01200 _M_invalidate(__tmp); 01201 } 01202 01203 size_type __bucket_count = this->bucket_count(); 01204 auto __next = _Base::erase(__first.base(), __last.base()); 01205 _M_check_rehashed(__bucket_count); 01206 return { __next, this }; 01207 } 01208 01209 _Base& 01210 _M_base() noexcept { return *this; } 01211 01212 const _Base& 01213 _M_base() const noexcept { return *this; } 01214 01215 private: 01216 void 01217 _M_check_rehashed(size_type __prev_count) 01218 { 01219 if (__prev_count != this->bucket_count()) 01220 this->_M_invalidate_all(); 01221 } 01222 01223 void 01224 _M_invalidate(_Base_const_iterator __victim) 01225 { 01226 this->_M_invalidate_if( 01227 [__victim](_Base_const_iterator __it) { return __it == __victim; }); 01228 this->_M_invalidate_local_if( 01229 [__victim](_Base_const_local_iterator __it) 01230 { return __it._M_curr() == __victim._M_cur; }); 01231 } 01232 01233 _Base_iterator 01234 _M_erase(_Base_const_iterator __victim) 01235 { 01236 _M_invalidate(__victim); 01237 size_type __bucket_count = this->bucket_count(); 01238 _Base_iterator __next = _Base::erase(__victim); 01239 _M_check_rehashed(__bucket_count); 01240 return __next; 01241 } 01242 01243 #if __cplusplus > 201402L 01244 node_type 01245 _M_extract(_Base_const_iterator __victim) 01246 { 01247 _M_invalidate(__victim); 01248 return _Base::extract(__victim); 01249 } 01250 #endif 01251 }; 01252 01253 #if __cpp_deduction_guides >= 201606 01254 01255 template<typename _InputIterator, 01256 typename _Hash = hash<__iter_key_t<_InputIterator>>, 01257 typename _Pred = equal_to<__iter_key_t<_InputIterator>>, 01258 typename _Allocator = allocator<__iter_to_alloc_t<_InputIterator>>, 01259 typename = _RequireInputIter<_InputIterator>, 01260 typename = _RequireNotAllocatorOrIntegral<_Hash>, 01261 typename = _RequireNotAllocator<_Pred>, 01262 typename = _RequireAllocator<_Allocator>> 01263 unordered_multimap(_InputIterator, _InputIterator, 01264 unordered_multimap<int, int>::size_type = {}, 01265 _Hash = _Hash(), _Pred = _Pred(), 01266 _Allocator = _Allocator()) 01267 -> unordered_multimap<__iter_key_t<_InputIterator>, 01268 __iter_val_t<_InputIterator>, _Hash, _Pred, 01269 _Allocator>; 01270 01271 template<typename _Key, typename _Tp, typename _Hash = hash<_Key>, 01272 typename _Pred = equal_to<_Key>, 01273 typename _Allocator = allocator<pair<const _Key, _Tp>>, 01274 typename = _RequireNotAllocatorOrIntegral<_Hash>, 01275 typename = _RequireNotAllocator<_Pred>, 01276 typename = _RequireAllocator<_Allocator>> 01277 unordered_multimap(initializer_list<pair<_Key, _Tp>>, 01278 unordered_multimap<int, int>::size_type = {}, 01279 _Hash = _Hash(), _Pred = _Pred(), 01280 _Allocator = _Allocator()) 01281 -> unordered_multimap<_Key, _Tp, _Hash, _Pred, _Allocator>; 01282 01283 template<typename _InputIterator, typename _Allocator, 01284 typename = _RequireInputIter<_InputIterator>, 01285 typename = _RequireAllocator<_Allocator>> 01286 unordered_multimap(_InputIterator, _InputIterator, 01287 unordered_multimap<int, int>::size_type, _Allocator) 01288 -> unordered_multimap<__iter_key_t<_InputIterator>, 01289 __iter_val_t<_InputIterator>, 01290 hash<__iter_key_t<_InputIterator>>, 01291 equal_to<__iter_key_t<_InputIterator>>, _Allocator>; 01292 01293 template<typename _InputIterator, typename _Allocator, 01294 typename = _RequireInputIter<_InputIterator>, 01295 typename = _RequireAllocator<_Allocator>> 01296 unordered_multimap(_InputIterator, _InputIterator, _Allocator) 01297 -> unordered_multimap<__iter_key_t<_InputIterator>, 01298 __iter_val_t<_InputIterator>, 01299 hash<__iter_key_t<_InputIterator>>, 01300 equal_to<__iter_key_t<_InputIterator>>, _Allocator>; 01301 01302 template<typename _InputIterator, typename _Hash, typename _Allocator, 01303 typename = _RequireInputIter<_InputIterator>, 01304 typename = _RequireNotAllocatorOrIntegral<_Hash>, 01305 typename = _RequireAllocator<_Allocator>> 01306 unordered_multimap(_InputIterator, _InputIterator, 01307 unordered_multimap<int, int>::size_type, _Hash, 01308 _Allocator) 01309 -> unordered_multimap<__iter_key_t<_InputIterator>, 01310 __iter_val_t<_InputIterator>, _Hash, 01311 equal_to<__iter_key_t<_InputIterator>>, _Allocator>; 01312 01313 template<typename _Key, typename _Tp, typename _Allocator, 01314 typename = _RequireAllocator<_Allocator>> 01315 unordered_multimap(initializer_list<pair<_Key, _Tp>>, 01316 unordered_multimap<int, int>::size_type, 01317 _Allocator) 01318 -> unordered_multimap<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>; 01319 01320 template<typename _Key, typename _Tp, typename _Allocator, 01321 typename = _RequireAllocator<_Allocator>> 01322 unordered_multimap(initializer_list<pair<_Key, _Tp>>, _Allocator) 01323 -> unordered_multimap<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>; 01324 01325 template<typename _Key, typename _Tp, typename _Hash, typename _Allocator, 01326 typename = _RequireNotAllocatorOrIntegral<_Hash>, 01327 typename = _RequireAllocator<_Allocator>> 01328 unordered_multimap(initializer_list<pair<_Key, _Tp>>, 01329 unordered_multimap<int, int>::size_type, 01330 _Hash, _Allocator) 01331 -> unordered_multimap<_Key, _Tp, _Hash, equal_to<_Key>, _Allocator>; 01332 01333 #endif 01334 01335 template<typename _Key, typename _Tp, typename _Hash, 01336 typename _Pred, typename _Alloc> 01337 inline void 01338 swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 01339 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 01340 noexcept(noexcept(__x.swap(__y))) 01341 { __x.swap(__y); } 01342 01343 template<typename _Key, typename _Tp, typename _Hash, 01344 typename _Pred, typename _Alloc> 01345 inline bool 01346 operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 01347 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 01348 { return __x._M_base() == __y._M_base(); } 01349 01350 template<typename _Key, typename _Tp, typename _Hash, 01351 typename _Pred, typename _Alloc> 01352 inline bool 01353 operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 01354 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 01355 { return !(__x == __y); } 01356 01357 } // namespace __debug 01358 } // namespace std 01359 01360 #endif // C++11 01361 01362 #endif