unordered_map revision 263272
1// -*- C++ -*- 2//===-------------------------- unordered_map -----------------------------===// 3// 4// The LLVM Compiler Infrastructure 5// 6// This file is dual licensed under the MIT and the University of Illinois Open 7// Source Licenses. See LICENSE.TXT for details. 8// 9//===----------------------------------------------------------------------===// 10 11#ifndef _LIBCPP_UNORDERED_MAP 12#define _LIBCPP_UNORDERED_MAP 13 14/* 15 16 unordered_map synopsis 17 18#include <initializer_list> 19 20namespace std 21{ 22 23template <class Key, class T, class Hash = hash<Key>, class Pred = equal_to<Key>, 24 class Alloc = allocator<pair<const Key, T>>> 25class unordered_map 26{ 27public: 28 // types 29 typedef Key key_type; 30 typedef T mapped_type; 31 typedef Hash hasher; 32 typedef Pred key_equal; 33 typedef Alloc allocator_type; 34 typedef pair<const key_type, mapped_type> value_type; 35 typedef value_type& reference; 36 typedef const value_type& const_reference; 37 typedef typename allocator_traits<allocator_type>::pointer pointer; 38 typedef typename allocator_traits<allocator_type>::const_pointer const_pointer; 39 typedef typename allocator_traits<allocator_type>::size_type size_type; 40 typedef typename allocator_traits<allocator_type>::difference_type difference_type; 41 42 typedef /unspecified/ iterator; 43 typedef /unspecified/ const_iterator; 44 typedef /unspecified/ local_iterator; 45 typedef /unspecified/ const_local_iterator; 46 47 unordered_map() 48 noexcept( 49 is_nothrow_default_constructible<hasher>::value && 50 is_nothrow_default_constructible<key_equal>::value && 51 is_nothrow_default_constructible<allocator_type>::value); 52 explicit unordered_map(size_type n, const hasher& hf = hasher(), 53 const key_equal& eql = key_equal(), 54 const allocator_type& a = allocator_type()); 55 template <class InputIterator> 56 unordered_map(InputIterator f, InputIterator l, 57 size_type n = 0, const hasher& hf = hasher(), 58 const key_equal& eql = key_equal(), 59 const allocator_type& a = allocator_type()); 60 explicit unordered_map(const allocator_type&); 61 unordered_map(const unordered_map&); 62 unordered_map(const unordered_map&, const Allocator&); 63 unordered_map(unordered_map&&) 64 noexcept( 65 is_nothrow_move_constructible<hasher>::value && 66 is_nothrow_move_constructible<key_equal>::value && 67 is_nothrow_move_constructible<allocator_type>::value); 68 unordered_map(unordered_map&&, const Allocator&); 69 unordered_map(initializer_list<value_type>, size_type n = 0, 70 const hasher& hf = hasher(), const key_equal& eql = key_equal(), 71 const allocator_type& a = allocator_type()); 72 unordered_map(size_type n, const allocator_type& a) 73 : unordered_map(n, hasher(), key_equal(), a) {} // C++14 74 unordered_map(size_type n, const hasher& hf, const allocator_type& a) 75 : unordered_map(n, hf, key_equal(), a) {} // C++14 76 template <class InputIterator> 77 unordered_map(InputIterator f, InputIterator l, size_type n, const allocator_type& a) 78 : unordered_map(f, l, n, hasher(), key_equal(), a) {} // C++14 79 template <class InputIterator> 80 unordered_map(InputIterator f, InputIterator l, size_type n, const hasher& hf, 81 const allocator_type& a) 82 : unordered_map(f, l, n, hf, key_equal(), a) {} // C++14 83 unordered_map(initializer_list<value_type> il, size_type n, const allocator_type& a) 84 : unordered_map(il, n, hasher(), key_equal(), a) {} // C++14 85 unordered_map(initializer_list<value_type> il, size_type n, const hasher& hf, 86 const allocator_type& a) 87 : unordered_map(il, n, hf, key_equal(), a) {} // C++14 88 ~unordered_map(); 89 unordered_map& operator=(const unordered_map&); 90 unordered_map& operator=(unordered_map&&) 91 noexcept( 92 allocator_type::propagate_on_container_move_assignment::value && 93 is_nothrow_move_assignable<allocator_type>::value && 94 is_nothrow_move_assignable<hasher>::value && 95 is_nothrow_move_assignable<key_equal>::value); 96 unordered_map& operator=(initializer_list<value_type>); 97 98 allocator_type get_allocator() const noexcept; 99 100 bool empty() const noexcept; 101 size_type size() const noexcept; 102 size_type max_size() const noexcept; 103 104 iterator begin() noexcept; 105 iterator end() noexcept; 106 const_iterator begin() const noexcept; 107 const_iterator end() const noexcept; 108 const_iterator cbegin() const noexcept; 109 const_iterator cend() const noexcept; 110 111 template <class... Args> 112 pair<iterator, bool> emplace(Args&&... args); 113 template <class... Args> 114 iterator emplace_hint(const_iterator position, Args&&... args); 115 pair<iterator, bool> insert(const value_type& obj); 116 template <class P> 117 pair<iterator, bool> insert(P&& obj); 118 iterator insert(const_iterator hint, const value_type& obj); 119 template <class P> 120 iterator insert(const_iterator hint, P&& obj); 121 template <class InputIterator> 122 void insert(InputIterator first, InputIterator last); 123 void insert(initializer_list<value_type>); 124 125 iterator erase(const_iterator position); 126 size_type erase(const key_type& k); 127 iterator erase(const_iterator first, const_iterator last); 128 void clear() noexcept; 129 130 void swap(unordered_map&) 131 noexcept( 132 (!allocator_type::propagate_on_container_swap::value || 133 __is_nothrow_swappable<allocator_type>::value) && 134 __is_nothrow_swappable<hasher>::value && 135 __is_nothrow_swappable<key_equal>::value); 136 137 hasher hash_function() const; 138 key_equal key_eq() const; 139 140 iterator find(const key_type& k); 141 const_iterator find(const key_type& k) const; 142 size_type count(const key_type& k) const; 143 pair<iterator, iterator> equal_range(const key_type& k); 144 pair<const_iterator, const_iterator> equal_range(const key_type& k) const; 145 146 mapped_type& operator[](const key_type& k); 147 mapped_type& operator[](key_type&& k); 148 149 mapped_type& at(const key_type& k); 150 const mapped_type& at(const key_type& k) const; 151 152 size_type bucket_count() const noexcept; 153 size_type max_bucket_count() const noexcept; 154 155 size_type bucket_size(size_type n) const; 156 size_type bucket(const key_type& k) const; 157 158 local_iterator begin(size_type n); 159 local_iterator end(size_type n); 160 const_local_iterator begin(size_type n) const; 161 const_local_iterator end(size_type n) const; 162 const_local_iterator cbegin(size_type n) const; 163 const_local_iterator cend(size_type n) const; 164 165 float load_factor() const noexcept; 166 float max_load_factor() const noexcept; 167 void max_load_factor(float z); 168 void rehash(size_type n); 169 void reserve(size_type n); 170}; 171 172template <class Key, class T, class Hash, class Pred, class Alloc> 173 void swap(unordered_map<Key, T, Hash, Pred, Alloc>& x, 174 unordered_map<Key, T, Hash, Pred, Alloc>& y) 175 noexcept(noexcept(x.swap(y))); 176 177template <class Key, class T, class Hash, class Pred, class Alloc> 178 bool 179 operator==(const unordered_map<Key, T, Hash, Pred, Alloc>& x, 180 const unordered_map<Key, T, Hash, Pred, Alloc>& y); 181 182template <class Key, class T, class Hash, class Pred, class Alloc> 183 bool 184 operator!=(const unordered_map<Key, T, Hash, Pred, Alloc>& x, 185 const unordered_map<Key, T, Hash, Pred, Alloc>& y); 186 187template <class Key, class T, class Hash = hash<Key>, class Pred = equal_to<Key>, 188 class Alloc = allocator<pair<const Key, T>>> 189class unordered_multimap 190{ 191public: 192 // types 193 typedef Key key_type; 194 typedef T mapped_type; 195 typedef Hash hasher; 196 typedef Pred key_equal; 197 typedef Alloc allocator_type; 198 typedef pair<const key_type, mapped_type> value_type; 199 typedef value_type& reference; 200 typedef const value_type& const_reference; 201 typedef typename allocator_traits<allocator_type>::pointer pointer; 202 typedef typename allocator_traits<allocator_type>::const_pointer const_pointer; 203 typedef typename allocator_traits<allocator_type>::size_type size_type; 204 typedef typename allocator_traits<allocator_type>::difference_type difference_type; 205 206 typedef /unspecified/ iterator; 207 typedef /unspecified/ const_iterator; 208 typedef /unspecified/ local_iterator; 209 typedef /unspecified/ const_local_iterator; 210 211 unordered_multimap() 212 noexcept( 213 is_nothrow_default_constructible<hasher>::value && 214 is_nothrow_default_constructible<key_equal>::value && 215 is_nothrow_default_constructible<allocator_type>::value); 216 explicit unordered_multimap(size_type n, const hasher& hf = hasher(), 217 const key_equal& eql = key_equal(), 218 const allocator_type& a = allocator_type()); 219 template <class InputIterator> 220 unordered_multimap(InputIterator f, InputIterator l, 221 size_type n = 0, const hasher& hf = hasher(), 222 const key_equal& eql = key_equal(), 223 const allocator_type& a = allocator_type()); 224 explicit unordered_multimap(const allocator_type&); 225 unordered_multimap(const unordered_multimap&); 226 unordered_multimap(const unordered_multimap&, const Allocator&); 227 unordered_multimap(unordered_multimap&&) 228 noexcept( 229 is_nothrow_move_constructible<hasher>::value && 230 is_nothrow_move_constructible<key_equal>::value && 231 is_nothrow_move_constructible<allocator_type>::value); 232 unordered_multimap(unordered_multimap&&, const Allocator&); 233 unordered_multimap(initializer_list<value_type>, size_type n = 0, 234 const hasher& hf = hasher(), const key_equal& eql = key_equal(), 235 const allocator_type& a = allocator_type()); 236 unordered_multimap(size_type n, const allocator_type& a) 237 : unordered_multimap(n, hasher(), key_equal(), a) {} // C++14 238 unordered_multimap(size_type n, const hasher& hf, const allocator_type& a) 239 : unordered_multimap(n, hf, key_equal(), a) {} // C++14 240 template <class InputIterator> 241 unordered_multimap(InputIterator f, InputIterator l, size_type n, const allocator_type& a) 242 : unordered_multimap(f, l, n, hasher(), key_equal(), a) {} // C++14 243 template <class InputIterator> 244 unordered_multimap(InputIterator f, InputIterator l, size_type n, const hasher& hf, 245 const allocator_type& a) 246 : unordered_multimap(f, l, n, hf, key_equal(), a) {} // C++14 247 unordered_multimap(initializer_list<value_type> il, size_type n, const allocator_type& a) 248 : unordered_multimap(il, n, hasher(), key_equal(), a) {} // C++14 249 unordered_multimap(initializer_list<value_type> il, size_type n, const hasher& hf, 250 const allocator_type& a) 251 : unordered_multimap(il, n, hf, key_equal(), a) {} // C++14 252 ~unordered_multimap(); 253 unordered_multimap& operator=(const unordered_multimap&); 254 unordered_multimap& operator=(unordered_multimap&&) 255 noexcept( 256 allocator_type::propagate_on_container_move_assignment::value && 257 is_nothrow_move_assignable<allocator_type>::value && 258 is_nothrow_move_assignable<hasher>::value && 259 is_nothrow_move_assignable<key_equal>::value); 260 unordered_multimap& operator=(initializer_list<value_type>); 261 262 allocator_type get_allocator() const noexcept; 263 264 bool empty() const noexcept; 265 size_type size() const noexcept; 266 size_type max_size() const noexcept; 267 268 iterator begin() noexcept; 269 iterator end() noexcept; 270 const_iterator begin() const noexcept; 271 const_iterator end() const noexcept; 272 const_iterator cbegin() const noexcept; 273 const_iterator cend() const noexcept; 274 275 template <class... Args> 276 iterator emplace(Args&&... args); 277 template <class... Args> 278 iterator emplace_hint(const_iterator position, Args&&... args); 279 iterator insert(const value_type& obj); 280 template <class P> 281 iterator insert(P&& obj); 282 iterator insert(const_iterator hint, const value_type& obj); 283 template <class P> 284 iterator insert(const_iterator hint, P&& obj); 285 template <class InputIterator> 286 void insert(InputIterator first, InputIterator last); 287 void insert(initializer_list<value_type>); 288 289 iterator erase(const_iterator position); 290 size_type erase(const key_type& k); 291 iterator erase(const_iterator first, const_iterator last); 292 void clear() noexcept; 293 294 void swap(unordered_multimap&) 295 noexcept( 296 (!allocator_type::propagate_on_container_swap::value || 297 __is_nothrow_swappable<allocator_type>::value) && 298 __is_nothrow_swappable<hasher>::value && 299 __is_nothrow_swappable<key_equal>::value); 300 301 hasher hash_function() const; 302 key_equal key_eq() const; 303 304 iterator find(const key_type& k); 305 const_iterator find(const key_type& k) const; 306 size_type count(const key_type& k) const; 307 pair<iterator, iterator> equal_range(const key_type& k); 308 pair<const_iterator, const_iterator> equal_range(const key_type& k) const; 309 310 size_type bucket_count() const noexcept; 311 size_type max_bucket_count() const noexcept; 312 313 size_type bucket_size(size_type n) const; 314 size_type bucket(const key_type& k) const; 315 316 local_iterator begin(size_type n); 317 local_iterator end(size_type n); 318 const_local_iterator begin(size_type n) const; 319 const_local_iterator end(size_type n) const; 320 const_local_iterator cbegin(size_type n) const; 321 const_local_iterator cend(size_type n) const; 322 323 float load_factor() const noexcept; 324 float max_load_factor() const noexcept; 325 void max_load_factor(float z); 326 void rehash(size_type n); 327 void reserve(size_type n); 328}; 329 330template <class Key, class T, class Hash, class Pred, class Alloc> 331 void swap(unordered_multimap<Key, T, Hash, Pred, Alloc>& x, 332 unordered_multimap<Key, T, Hash, Pred, Alloc>& y) 333 noexcept(noexcept(x.swap(y))); 334 335template <class Key, class T, class Hash, class Pred, class Alloc> 336 bool 337 operator==(const unordered_multimap<Key, T, Hash, Pred, Alloc>& x, 338 const unordered_multimap<Key, T, Hash, Pred, Alloc>& y); 339 340template <class Key, class T, class Hash, class Pred, class Alloc> 341 bool 342 operator!=(const unordered_multimap<Key, T, Hash, Pred, Alloc>& x, 343 const unordered_multimap<Key, T, Hash, Pred, Alloc>& y); 344 345} // std 346 347*/ 348 349#include <__config> 350#include <__hash_table> 351#include <functional> 352#include <stdexcept> 353 354#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 355#pragma GCC system_header 356#endif 357 358_LIBCPP_BEGIN_NAMESPACE_STD 359 360template <class _Key, class _Cp, class _Hash, bool = is_empty<_Hash>::value 361#if __has_feature(is_final) 362 && !__is_final(_Hash) 363#endif 364 > 365class __unordered_map_hasher 366 : private _Hash 367{ 368public: 369 _LIBCPP_INLINE_VISIBILITY 370 __unordered_map_hasher() 371 _NOEXCEPT_(is_nothrow_default_constructible<_Hash>::value) 372 : _Hash() {} 373 _LIBCPP_INLINE_VISIBILITY 374 __unordered_map_hasher(const _Hash& __h) 375 _NOEXCEPT_(is_nothrow_copy_constructible<_Hash>::value) 376 : _Hash(__h) {} 377 _LIBCPP_INLINE_VISIBILITY 378 const _Hash& hash_function() const _NOEXCEPT {return *this;} 379 _LIBCPP_INLINE_VISIBILITY 380 size_t operator()(const _Cp& __x) const 381 {return static_cast<const _Hash&>(*this)(__x.__cc.first);} 382 _LIBCPP_INLINE_VISIBILITY 383 size_t operator()(const _Key& __x) const 384 {return static_cast<const _Hash&>(*this)(__x);} 385}; 386 387template <class _Key, class _Cp, class _Hash> 388class __unordered_map_hasher<_Key, _Cp, _Hash, false> 389{ 390 _Hash __hash_; 391 392public: 393 _LIBCPP_INLINE_VISIBILITY 394 __unordered_map_hasher() 395 _NOEXCEPT_(is_nothrow_default_constructible<_Hash>::value) 396 : __hash_() {} 397 _LIBCPP_INLINE_VISIBILITY 398 __unordered_map_hasher(const _Hash& __h) 399 _NOEXCEPT_(is_nothrow_copy_constructible<_Hash>::value) 400 : __hash_(__h) {} 401 _LIBCPP_INLINE_VISIBILITY 402 const _Hash& hash_function() const _NOEXCEPT {return __hash_;} 403 _LIBCPP_INLINE_VISIBILITY 404 size_t operator()(const _Cp& __x) const 405 {return __hash_(__x.__cc.first);} 406 _LIBCPP_INLINE_VISIBILITY 407 size_t operator()(const _Key& __x) const 408 {return __hash_(__x);} 409}; 410 411template <class _Key, class _Cp, class _Pred, bool = is_empty<_Pred>::value 412#if __has_feature(is_final) 413 && !__is_final(_Pred) 414#endif 415 > 416class __unordered_map_equal 417 : private _Pred 418{ 419public: 420 _LIBCPP_INLINE_VISIBILITY 421 __unordered_map_equal() 422 _NOEXCEPT_(is_nothrow_default_constructible<_Pred>::value) 423 : _Pred() {} 424 _LIBCPP_INLINE_VISIBILITY 425 __unordered_map_equal(const _Pred& __p) 426 _NOEXCEPT_(is_nothrow_copy_constructible<_Pred>::value) 427 : _Pred(__p) {} 428 _LIBCPP_INLINE_VISIBILITY 429 const _Pred& key_eq() const _NOEXCEPT {return *this;} 430 _LIBCPP_INLINE_VISIBILITY 431 bool operator()(const _Cp& __x, const _Cp& __y) const 432 {return static_cast<const _Pred&>(*this)(__x.__cc.first, __y.__cc.first);} 433 _LIBCPP_INLINE_VISIBILITY 434 bool operator()(const _Cp& __x, const _Key& __y) const 435 {return static_cast<const _Pred&>(*this)(__x.__cc.first, __y);} 436 _LIBCPP_INLINE_VISIBILITY 437 bool operator()(const _Key& __x, const _Cp& __y) const 438 {return static_cast<const _Pred&>(*this)(__x, __y.__cc.first);} 439}; 440 441template <class _Key, class _Cp, class _Pred> 442class __unordered_map_equal<_Key, _Cp, _Pred, false> 443{ 444 _Pred __pred_; 445 446public: 447 _LIBCPP_INLINE_VISIBILITY 448 __unordered_map_equal() 449 _NOEXCEPT_(is_nothrow_default_constructible<_Pred>::value) 450 : __pred_() {} 451 _LIBCPP_INLINE_VISIBILITY 452 __unordered_map_equal(const _Pred& __p) 453 _NOEXCEPT_(is_nothrow_copy_constructible<_Pred>::value) 454 : __pred_(__p) {} 455 _LIBCPP_INLINE_VISIBILITY 456 const _Pred& key_eq() const _NOEXCEPT {return __pred_;} 457 _LIBCPP_INLINE_VISIBILITY 458 bool operator()(const _Cp& __x, const _Cp& __y) const 459 {return __pred_(__x.__cc.first, __y.__cc.first);} 460 _LIBCPP_INLINE_VISIBILITY 461 bool operator()(const _Cp& __x, const _Key& __y) const 462 {return __pred_(__x.__cc.first, __y);} 463 _LIBCPP_INLINE_VISIBILITY 464 bool operator()(const _Key& __x, const _Cp& __y) const 465 {return __pred_(__x, __y.__cc.first);} 466}; 467 468template <class _Alloc> 469class __hash_map_node_destructor 470{ 471 typedef _Alloc allocator_type; 472 typedef allocator_traits<allocator_type> __alloc_traits; 473 typedef typename __alloc_traits::value_type::value_type value_type; 474public: 475 typedef typename __alloc_traits::pointer pointer; 476private: 477 typedef typename value_type::value_type::first_type first_type; 478 typedef typename value_type::value_type::second_type second_type; 479 480 allocator_type& __na_; 481 482 __hash_map_node_destructor& operator=(const __hash_map_node_destructor&); 483 484public: 485 bool __first_constructed; 486 bool __second_constructed; 487 488 _LIBCPP_INLINE_VISIBILITY 489 explicit __hash_map_node_destructor(allocator_type& __na) _NOEXCEPT 490 : __na_(__na), 491 __first_constructed(false), 492 __second_constructed(false) 493 {} 494 495#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 496 _LIBCPP_INLINE_VISIBILITY 497 __hash_map_node_destructor(__hash_node_destructor<allocator_type>&& __x) 498 _NOEXCEPT 499 : __na_(__x.__na_), 500 __first_constructed(__x.__value_constructed), 501 __second_constructed(__x.__value_constructed) 502 { 503 __x.__value_constructed = false; 504 } 505#else // _LIBCPP_HAS_NO_RVALUE_REFERENCES 506 _LIBCPP_INLINE_VISIBILITY 507 __hash_map_node_destructor(const __hash_node_destructor<allocator_type>& __x) 508 : __na_(__x.__na_), 509 __first_constructed(__x.__value_constructed), 510 __second_constructed(__x.__value_constructed) 511 { 512 const_cast<bool&>(__x.__value_constructed) = false; 513 } 514#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 515 516 _LIBCPP_INLINE_VISIBILITY 517 void operator()(pointer __p) _NOEXCEPT 518 { 519 if (__second_constructed) 520 __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.__cc.second)); 521 if (__first_constructed) 522 __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.__cc.first)); 523 if (__p) 524 __alloc_traits::deallocate(__na_, __p, 1); 525 } 526}; 527 528#if __cplusplus >= 201103L 529 530template <class _Key, class _Tp> 531union __hash_value_type 532{ 533 typedef _Key key_type; 534 typedef _Tp mapped_type; 535 typedef pair<const key_type, mapped_type> value_type; 536 typedef pair<key_type, mapped_type> __nc_value_type; 537 538 value_type __cc; 539 __nc_value_type __nc; 540 541 template <class ..._Args> 542 _LIBCPP_INLINE_VISIBILITY 543 __hash_value_type(_Args&& ...__args) 544 : __cc(std::forward<_Args>(__args)...) {} 545 546 _LIBCPP_INLINE_VISIBILITY 547 __hash_value_type(const __hash_value_type& __v) 548 : __cc(__v.__cc) {} 549 550 _LIBCPP_INLINE_VISIBILITY 551 __hash_value_type(__hash_value_type&& __v) 552 : __nc(std::move(__v.__nc)) {} 553 554 _LIBCPP_INLINE_VISIBILITY 555 __hash_value_type& operator=(const __hash_value_type& __v) 556 {__nc = __v.__cc; return *this;} 557 558 _LIBCPP_INLINE_VISIBILITY 559 __hash_value_type& operator=(__hash_value_type&& __v) 560 {__nc = std::move(__v.__nc); return *this;} 561 562 _LIBCPP_INLINE_VISIBILITY 563 ~__hash_value_type() {__cc.~value_type();} 564}; 565 566#else 567 568template <class _Key, class _Tp> 569struct __hash_value_type 570{ 571 typedef _Key key_type; 572 typedef _Tp mapped_type; 573 typedef pair<const key_type, mapped_type> value_type; 574 575 value_type __cc; 576 577 _LIBCPP_INLINE_VISIBILITY 578 __hash_value_type() {} 579 580 template <class _A0> 581 _LIBCPP_INLINE_VISIBILITY 582 __hash_value_type(const _A0& __a0) 583 : __cc(__a0) {} 584 585 template <class _A0, class _A1> 586 _LIBCPP_INLINE_VISIBILITY 587 __hash_value_type(const _A0& __a0, const _A1& __a1) 588 : __cc(__a0, __a1) {} 589}; 590 591#endif 592 593template <class _HashIterator> 594class _LIBCPP_TYPE_VIS_ONLY __hash_map_iterator 595{ 596 _HashIterator __i_; 597 598 typedef pointer_traits<typename _HashIterator::pointer> __pointer_traits; 599 typedef const typename _HashIterator::value_type::value_type::first_type key_type; 600 typedef typename _HashIterator::value_type::value_type::second_type mapped_type; 601public: 602 typedef forward_iterator_tag iterator_category; 603 typedef pair<key_type, mapped_type> value_type; 604 typedef typename _HashIterator::difference_type difference_type; 605 typedef value_type& reference; 606 typedef typename __pointer_traits::template 607#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 608 rebind<value_type> 609#else 610 rebind<value_type>::other 611#endif 612 pointer; 613 614 _LIBCPP_INLINE_VISIBILITY 615 __hash_map_iterator() _NOEXCEPT {} 616 617 _LIBCPP_INLINE_VISIBILITY 618 __hash_map_iterator(_HashIterator __i) _NOEXCEPT : __i_(__i) {} 619 620 _LIBCPP_INLINE_VISIBILITY 621 reference operator*() const {return __i_->__cc;} 622 _LIBCPP_INLINE_VISIBILITY 623 pointer operator->() const {return pointer_traits<pointer>::pointer_to(__i_->__cc);} 624 625 _LIBCPP_INLINE_VISIBILITY 626 __hash_map_iterator& operator++() {++__i_; return *this;} 627 _LIBCPP_INLINE_VISIBILITY 628 __hash_map_iterator operator++(int) 629 { 630 __hash_map_iterator __t(*this); 631 ++(*this); 632 return __t; 633 } 634 635 friend _LIBCPP_INLINE_VISIBILITY 636 bool operator==(const __hash_map_iterator& __x, const __hash_map_iterator& __y) 637 {return __x.__i_ == __y.__i_;} 638 friend _LIBCPP_INLINE_VISIBILITY 639 bool operator!=(const __hash_map_iterator& __x, const __hash_map_iterator& __y) 640 {return __x.__i_ != __y.__i_;} 641 642 template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY unordered_map; 643 template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY unordered_multimap; 644 template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_const_iterator; 645 template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_const_local_iterator; 646 template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_map_const_iterator; 647}; 648 649template <class _HashIterator> 650class _LIBCPP_TYPE_VIS_ONLY __hash_map_const_iterator 651{ 652 _HashIterator __i_; 653 654 typedef pointer_traits<typename _HashIterator::pointer> __pointer_traits; 655 typedef const typename _HashIterator::value_type::value_type::first_type key_type; 656 typedef typename _HashIterator::value_type::value_type::second_type mapped_type; 657public: 658 typedef forward_iterator_tag iterator_category; 659 typedef pair<key_type, mapped_type> value_type; 660 typedef typename _HashIterator::difference_type difference_type; 661 typedef const value_type& reference; 662 typedef typename __pointer_traits::template 663#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 664 rebind<const value_type> 665#else 666 rebind<const value_type>::other 667#endif 668 pointer; 669 670 _LIBCPP_INLINE_VISIBILITY 671 __hash_map_const_iterator() _NOEXCEPT {} 672 673 _LIBCPP_INLINE_VISIBILITY 674 __hash_map_const_iterator(_HashIterator __i) _NOEXCEPT : __i_(__i) {} 675 _LIBCPP_INLINE_VISIBILITY 676 __hash_map_const_iterator( 677 __hash_map_iterator<typename _HashIterator::__non_const_iterator> __i) 678 _NOEXCEPT 679 : __i_(__i.__i_) {} 680 681 _LIBCPP_INLINE_VISIBILITY 682 reference operator*() const {return __i_->__cc;} 683 _LIBCPP_INLINE_VISIBILITY 684 pointer operator->() const {return pointer_traits<pointer>::pointer_to(__i_->__cc);} 685 686 _LIBCPP_INLINE_VISIBILITY 687 __hash_map_const_iterator& operator++() {++__i_; return *this;} 688 _LIBCPP_INLINE_VISIBILITY 689 __hash_map_const_iterator operator++(int) 690 { 691 __hash_map_const_iterator __t(*this); 692 ++(*this); 693 return __t; 694 } 695 696 friend _LIBCPP_INLINE_VISIBILITY 697 bool operator==(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y) 698 {return __x.__i_ == __y.__i_;} 699 friend _LIBCPP_INLINE_VISIBILITY 700 bool operator!=(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y) 701 {return __x.__i_ != __y.__i_;} 702 703 template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY unordered_map; 704 template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY unordered_multimap; 705 template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_const_iterator; 706 template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_const_local_iterator; 707}; 708 709template <class _Key, class _Tp, class _Hash = hash<_Key>, class _Pred = equal_to<_Key>, 710 class _Alloc = allocator<pair<const _Key, _Tp> > > 711class _LIBCPP_TYPE_VIS_ONLY unordered_map 712{ 713public: 714 // types 715 typedef _Key key_type; 716 typedef _Tp mapped_type; 717 typedef _Hash hasher; 718 typedef _Pred key_equal; 719 typedef _Alloc allocator_type; 720 typedef pair<const key_type, mapped_type> value_type; 721 typedef pair<key_type, mapped_type> __nc_value_type; 722 typedef value_type& reference; 723 typedef const value_type& const_reference; 724 static_assert((is_same<value_type, typename allocator_type::value_type>::value), 725 "Invalid allocator::value_type"); 726 727private: 728 typedef __hash_value_type<key_type, mapped_type> __value_type; 729 typedef __unordered_map_hasher<key_type, __value_type, hasher> __hasher; 730 typedef __unordered_map_equal<key_type, __value_type, key_equal> __key_equal; 731 typedef typename allocator_traits<allocator_type>::template 732#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 733 rebind_alloc<__value_type> 734#else 735 rebind_alloc<__value_type>::other 736#endif 737 __allocator_type; 738 739 typedef __hash_table<__value_type, __hasher, 740 __key_equal, __allocator_type> __table; 741 742 __table __table_; 743 744 typedef typename __table::__node_pointer __node_pointer; 745 typedef typename __table::__node_const_pointer __node_const_pointer; 746 typedef typename __table::__node_traits __node_traits; 747 typedef typename __table::__node_allocator __node_allocator; 748 typedef typename __table::__node __node; 749 typedef __hash_map_node_destructor<__node_allocator> _Dp; 750 typedef unique_ptr<__node, _Dp> __node_holder; 751 typedef allocator_traits<allocator_type> __alloc_traits; 752public: 753 typedef typename __alloc_traits::pointer pointer; 754 typedef typename __alloc_traits::const_pointer const_pointer; 755 typedef typename __alloc_traits::size_type size_type; 756 typedef typename __alloc_traits::difference_type difference_type; 757 758 typedef __hash_map_iterator<typename __table::iterator> iterator; 759 typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator; 760 typedef __hash_map_iterator<typename __table::local_iterator> local_iterator; 761 typedef __hash_map_const_iterator<typename __table::const_local_iterator> const_local_iterator; 762 763 _LIBCPP_INLINE_VISIBILITY 764 unordered_map() 765 _NOEXCEPT_(is_nothrow_default_constructible<__table>::value) 766 { 767#if _LIBCPP_DEBUG_LEVEL >= 2 768 __get_db()->__insert_c(this); 769#endif 770 } 771 explicit unordered_map(size_type __n, const hasher& __hf = hasher(), 772 const key_equal& __eql = key_equal()); 773 unordered_map(size_type __n, const hasher& __hf, 774 const key_equal& __eql, 775 const allocator_type& __a); 776 template <class _InputIterator> 777 unordered_map(_InputIterator __first, _InputIterator __last); 778 template <class _InputIterator> 779 unordered_map(_InputIterator __first, _InputIterator __last, 780 size_type __n, const hasher& __hf = hasher(), 781 const key_equal& __eql = key_equal()); 782 template <class _InputIterator> 783 unordered_map(_InputIterator __first, _InputIterator __last, 784 size_type __n, const hasher& __hf, 785 const key_equal& __eql, 786 const allocator_type& __a); 787 explicit unordered_map(const allocator_type& __a); 788 unordered_map(const unordered_map& __u); 789 unordered_map(const unordered_map& __u, const allocator_type& __a); 790#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 791 unordered_map(unordered_map&& __u) 792 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value); 793 unordered_map(unordered_map&& __u, const allocator_type& __a); 794#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 795#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 796 unordered_map(initializer_list<value_type> __il); 797 unordered_map(initializer_list<value_type> __il, size_type __n, 798 const hasher& __hf = hasher(), const key_equal& __eql = key_equal()); 799 unordered_map(initializer_list<value_type> __il, size_type __n, 800 const hasher& __hf, const key_equal& __eql, 801 const allocator_type& __a); 802#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 803#if _LIBCPP_STD_VER > 11 804 _LIBCPP_INLINE_VISIBILITY 805 unordered_map(size_type __n, const allocator_type& __a) 806 : unordered_map(__n, hasher(), key_equal(), __a) {} 807 _LIBCPP_INLINE_VISIBILITY 808 unordered_map(size_type __n, const hasher& __hf, const allocator_type& __a) 809 : unordered_map(__n, __hf, key_equal(), __a) {} 810 template <class _InputIterator> 811 _LIBCPP_INLINE_VISIBILITY 812 unordered_map(_InputIterator __first, _InputIterator __last, size_type __n, const allocator_type& __a) 813 : unordered_map(__first, __last, __n, hasher(), key_equal(), __a) {} 814 template <class _InputIterator> 815 _LIBCPP_INLINE_VISIBILITY 816 unordered_map(_InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, 817 const allocator_type& __a) 818 : unordered_map(__first, __last, __n, __hf, key_equal(), __a) {} 819 _LIBCPP_INLINE_VISIBILITY 820 unordered_map(initializer_list<value_type> __il, size_type __n, const allocator_type& __a) 821 : unordered_map(__il, __n, hasher(), key_equal(), __a) {} 822 _LIBCPP_INLINE_VISIBILITY 823 unordered_map(initializer_list<value_type> __il, size_type __n, const hasher& __hf, 824 const allocator_type& __a) 825 : unordered_map(__il, __n, __hf, key_equal(), __a) {} 826#endif 827 // ~unordered_map() = default; 828 _LIBCPP_INLINE_VISIBILITY 829 unordered_map& operator=(const unordered_map& __u) 830 { 831#if __cplusplus >= 201103L 832 __table_ = __u.__table_; 833#else 834 if (this != &__u) { 835 __table_.clear(); 836 __table_.hash_function() = __u.__table_.hash_function(); 837 __table_.key_eq() = __u.__table_.key_eq(); 838 __table_.max_load_factor() = __u.__table_.max_load_factor(); 839 __table_.__copy_assign_alloc(__u.__table_); 840 insert(__u.begin(), __u.end()); 841 } 842#endif 843 return *this; 844 } 845#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 846 unordered_map& operator=(unordered_map&& __u) 847 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value); 848#endif 849#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 850 unordered_map& operator=(initializer_list<value_type> __il); 851#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 852 853 _LIBCPP_INLINE_VISIBILITY 854 allocator_type get_allocator() const _NOEXCEPT 855 {return allocator_type(__table_.__node_alloc());} 856 857 _LIBCPP_INLINE_VISIBILITY 858 bool empty() const _NOEXCEPT {return __table_.size() == 0;} 859 _LIBCPP_INLINE_VISIBILITY 860 size_type size() const _NOEXCEPT {return __table_.size();} 861 _LIBCPP_INLINE_VISIBILITY 862 size_type max_size() const _NOEXCEPT {return __table_.max_size();} 863 864 _LIBCPP_INLINE_VISIBILITY 865 iterator begin() _NOEXCEPT {return __table_.begin();} 866 _LIBCPP_INLINE_VISIBILITY 867 iterator end() _NOEXCEPT {return __table_.end();} 868 _LIBCPP_INLINE_VISIBILITY 869 const_iterator begin() const _NOEXCEPT {return __table_.begin();} 870 _LIBCPP_INLINE_VISIBILITY 871 const_iterator end() const _NOEXCEPT {return __table_.end();} 872 _LIBCPP_INLINE_VISIBILITY 873 const_iterator cbegin() const _NOEXCEPT {return __table_.begin();} 874 _LIBCPP_INLINE_VISIBILITY 875 const_iterator cend() const _NOEXCEPT {return __table_.end();} 876 877#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 878#ifndef _LIBCPP_HAS_NO_VARIADICS 879 880 template <class... _Args> 881 pair<iterator, bool> emplace(_Args&&... __args); 882 883 template <class... _Args> 884 _LIBCPP_INLINE_VISIBILITY 885#if _LIBCPP_DEBUG_LEVEL >= 2 886 iterator emplace_hint(const_iterator __p, _Args&&... __args) 887 { 888 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 889 "unordered_map::emplace_hint(const_iterator, args...) called with an iterator not" 890 " referring to this unordered_map"); 891 return __table_.__emplace_unique(_VSTD::forward<_Args>(__args)...).first; 892 } 893#else 894 iterator emplace_hint(const_iterator, _Args&&... __args) 895 {return emplace(_VSTD::forward<_Args>(__args)...).first;} 896#endif 897#endif // _LIBCPP_HAS_NO_VARIADICS 898#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 899 _LIBCPP_INLINE_VISIBILITY 900 pair<iterator, bool> insert(const value_type& __x) 901 {return __table_.__insert_unique(__x);} 902#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 903 template <class _Pp, 904 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type> 905 _LIBCPP_INLINE_VISIBILITY 906 pair<iterator, bool> insert(_Pp&& __x) 907 {return __table_.__insert_unique(_VSTD::forward<_Pp>(__x));} 908#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 909 _LIBCPP_INLINE_VISIBILITY 910#if _LIBCPP_DEBUG_LEVEL >= 2 911 iterator insert(const_iterator __p, const value_type& __x) 912 { 913 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 914 "unordered_map::insert(const_iterator, const value_type&) called with an iterator not" 915 " referring to this unordered_map"); 916 return insert(__x).first; 917 } 918#else 919 iterator insert(const_iterator, const value_type& __x) 920 {return insert(__x).first;} 921#endif 922#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 923 template <class _Pp, 924 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type> 925 _LIBCPP_INLINE_VISIBILITY 926#if _LIBCPP_DEBUG_LEVEL >= 2 927 iterator insert(const_iterator __p, _Pp&& __x) 928 { 929 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 930 "unordered_map::insert(const_iterator, value_type&&) called with an iterator not" 931 " referring to this unordered_map"); 932 return insert(_VSTD::forward<_Pp>(__x)).first; 933 } 934#else 935 iterator insert(const_iterator, _Pp&& __x) 936 {return insert(_VSTD::forward<_Pp>(__x)).first;} 937#endif 938#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 939 template <class _InputIterator> 940 void insert(_InputIterator __first, _InputIterator __last); 941#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 942 _LIBCPP_INLINE_VISIBILITY 943 void insert(initializer_list<value_type> __il) 944 {insert(__il.begin(), __il.end());} 945#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 946 947 _LIBCPP_INLINE_VISIBILITY 948 iterator erase(const_iterator __p) {return __table_.erase(__p.__i_);} 949 _LIBCPP_INLINE_VISIBILITY 950 size_type erase(const key_type& __k) {return __table_.__erase_unique(__k);} 951 _LIBCPP_INLINE_VISIBILITY 952 iterator erase(const_iterator __first, const_iterator __last) 953 {return __table_.erase(__first.__i_, __last.__i_);} 954 _LIBCPP_INLINE_VISIBILITY 955 void clear() _NOEXCEPT {__table_.clear();} 956 957 _LIBCPP_INLINE_VISIBILITY 958 void swap(unordered_map& __u) 959 _NOEXCEPT_(__is_nothrow_swappable<__table>::value) 960 {__table_.swap(__u.__table_);} 961 962 _LIBCPP_INLINE_VISIBILITY 963 hasher hash_function() const 964 {return __table_.hash_function().hash_function();} 965 _LIBCPP_INLINE_VISIBILITY 966 key_equal key_eq() const 967 {return __table_.key_eq().key_eq();} 968 969 _LIBCPP_INLINE_VISIBILITY 970 iterator find(const key_type& __k) {return __table_.find(__k);} 971 _LIBCPP_INLINE_VISIBILITY 972 const_iterator find(const key_type& __k) const {return __table_.find(__k);} 973 _LIBCPP_INLINE_VISIBILITY 974 size_type count(const key_type& __k) const {return __table_.__count_unique(__k);} 975 _LIBCPP_INLINE_VISIBILITY 976 pair<iterator, iterator> equal_range(const key_type& __k) 977 {return __table_.__equal_range_unique(__k);} 978 _LIBCPP_INLINE_VISIBILITY 979 pair<const_iterator, const_iterator> equal_range(const key_type& __k) const 980 {return __table_.__equal_range_unique(__k);} 981 982 mapped_type& operator[](const key_type& __k); 983#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 984 mapped_type& operator[](key_type&& __k); 985#endif 986 987 mapped_type& at(const key_type& __k); 988 const mapped_type& at(const key_type& __k) const; 989 990 _LIBCPP_INLINE_VISIBILITY 991 size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();} 992 _LIBCPP_INLINE_VISIBILITY 993 size_type max_bucket_count() const _NOEXCEPT {return __table_.max_bucket_count();} 994 995 _LIBCPP_INLINE_VISIBILITY 996 size_type bucket_size(size_type __n) const 997 {return __table_.bucket_size(__n);} 998 _LIBCPP_INLINE_VISIBILITY 999 size_type bucket(const key_type& __k) const {return __table_.bucket(__k);} 1000 1001 _LIBCPP_INLINE_VISIBILITY 1002 local_iterator begin(size_type __n) {return __table_.begin(__n);} 1003 _LIBCPP_INLINE_VISIBILITY 1004 local_iterator end(size_type __n) {return __table_.end(__n);} 1005 _LIBCPP_INLINE_VISIBILITY 1006 const_local_iterator begin(size_type __n) const {return __table_.cbegin(__n);} 1007 _LIBCPP_INLINE_VISIBILITY 1008 const_local_iterator end(size_type __n) const {return __table_.cend(__n);} 1009 _LIBCPP_INLINE_VISIBILITY 1010 const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);} 1011 _LIBCPP_INLINE_VISIBILITY 1012 const_local_iterator cend(size_type __n) const {return __table_.cend(__n);} 1013 1014 _LIBCPP_INLINE_VISIBILITY 1015 float load_factor() const _NOEXCEPT {return __table_.load_factor();} 1016 _LIBCPP_INLINE_VISIBILITY 1017 float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();} 1018 _LIBCPP_INLINE_VISIBILITY 1019 void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);} 1020 _LIBCPP_INLINE_VISIBILITY 1021 void rehash(size_type __n) {__table_.rehash(__n);} 1022 _LIBCPP_INLINE_VISIBILITY 1023 void reserve(size_type __n) {__table_.reserve(__n);} 1024 1025#if _LIBCPP_DEBUG_LEVEL >= 2 1026 1027 bool __dereferenceable(const const_iterator* __i) const 1028 {return __table_.__dereferenceable(&__i->__i_);} 1029 bool __decrementable(const const_iterator* __i) const 1030 {return __table_.__decrementable(&__i->__i_);} 1031 bool __addable(const const_iterator* __i, ptrdiff_t __n) const 1032 {return __table_.__addable(&__i->__i_, __n);} 1033 bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const 1034 {return __table_.__addable(&__i->__i_, __n);} 1035 1036#endif // _LIBCPP_DEBUG_LEVEL >= 2 1037 1038private: 1039#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1040 __node_holder __construct_node(); 1041 template <class _A0> 1042 __node_holder 1043 __construct_node(_A0&& __a0); 1044 __node_holder __construct_node_with_key(key_type&& __k); 1045#ifndef _LIBCPP_HAS_NO_VARIADICS 1046 template <class _A0, class _A1, class ..._Args> 1047 __node_holder __construct_node(_A0&& __a0, _A1&& __a1, _Args&& ...__args); 1048#endif // _LIBCPP_HAS_NO_VARIADICS 1049#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1050 __node_holder __construct_node_with_key(const key_type& __k); 1051}; 1052 1053template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1054unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1055 size_type __n, const hasher& __hf, const key_equal& __eql) 1056 : __table_(__hf, __eql) 1057{ 1058#if _LIBCPP_DEBUG_LEVEL >= 2 1059 __get_db()->__insert_c(this); 1060#endif 1061 __table_.rehash(__n); 1062} 1063 1064template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1065unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1066 size_type __n, const hasher& __hf, const key_equal& __eql, 1067 const allocator_type& __a) 1068 : __table_(__hf, __eql, __a) 1069{ 1070#if _LIBCPP_DEBUG_LEVEL >= 2 1071 __get_db()->__insert_c(this); 1072#endif 1073 __table_.rehash(__n); 1074} 1075 1076template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1077inline _LIBCPP_INLINE_VISIBILITY 1078unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1079 const allocator_type& __a) 1080 : __table_(__a) 1081{ 1082#if _LIBCPP_DEBUG_LEVEL >= 2 1083 __get_db()->__insert_c(this); 1084#endif 1085} 1086 1087template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1088template <class _InputIterator> 1089unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1090 _InputIterator __first, _InputIterator __last) 1091{ 1092#if _LIBCPP_DEBUG_LEVEL >= 2 1093 __get_db()->__insert_c(this); 1094#endif 1095 insert(__first, __last); 1096} 1097 1098template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1099template <class _InputIterator> 1100unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1101 _InputIterator __first, _InputIterator __last, size_type __n, 1102 const hasher& __hf, const key_equal& __eql) 1103 : __table_(__hf, __eql) 1104{ 1105#if _LIBCPP_DEBUG_LEVEL >= 2 1106 __get_db()->__insert_c(this); 1107#endif 1108 __table_.rehash(__n); 1109 insert(__first, __last); 1110} 1111 1112template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1113template <class _InputIterator> 1114unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1115 _InputIterator __first, _InputIterator __last, size_type __n, 1116 const hasher& __hf, const key_equal& __eql, const allocator_type& __a) 1117 : __table_(__hf, __eql, __a) 1118{ 1119#if _LIBCPP_DEBUG_LEVEL >= 2 1120 __get_db()->__insert_c(this); 1121#endif 1122 __table_.rehash(__n); 1123 insert(__first, __last); 1124} 1125 1126template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1127unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1128 const unordered_map& __u) 1129 : __table_(__u.__table_) 1130{ 1131#if _LIBCPP_DEBUG_LEVEL >= 2 1132 __get_db()->__insert_c(this); 1133#endif 1134 __table_.rehash(__u.bucket_count()); 1135 insert(__u.begin(), __u.end()); 1136} 1137 1138template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1139unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1140 const unordered_map& __u, const allocator_type& __a) 1141 : __table_(__u.__table_, __a) 1142{ 1143#if _LIBCPP_DEBUG_LEVEL >= 2 1144 __get_db()->__insert_c(this); 1145#endif 1146 __table_.rehash(__u.bucket_count()); 1147 insert(__u.begin(), __u.end()); 1148} 1149 1150#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1151 1152template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1153inline _LIBCPP_INLINE_VISIBILITY 1154unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1155 unordered_map&& __u) 1156 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value) 1157 : __table_(_VSTD::move(__u.__table_)) 1158{ 1159#if _LIBCPP_DEBUG_LEVEL >= 2 1160 __get_db()->__insert_c(this); 1161 __get_db()->swap(this, &__u); 1162#endif 1163} 1164 1165template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1166unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1167 unordered_map&& __u, const allocator_type& __a) 1168 : __table_(_VSTD::move(__u.__table_), __a) 1169{ 1170#if _LIBCPP_DEBUG_LEVEL >= 2 1171 __get_db()->__insert_c(this); 1172#endif 1173 if (__a != __u.get_allocator()) 1174 { 1175 iterator __i = __u.begin(); 1176 while (__u.size() != 0) 1177 __table_.__insert_unique( 1178 _VSTD::move(__u.__table_.remove((__i++).__i_)->__value_) 1179 ); 1180 } 1181#if _LIBCPP_DEBUG_LEVEL >= 2 1182 else 1183 __get_db()->swap(this, &__u); 1184#endif 1185} 1186 1187#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1188 1189#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1190 1191template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1192unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1193 initializer_list<value_type> __il) 1194{ 1195#if _LIBCPP_DEBUG_LEVEL >= 2 1196 __get_db()->__insert_c(this); 1197#endif 1198 insert(__il.begin(), __il.end()); 1199} 1200 1201template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1202unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1203 initializer_list<value_type> __il, size_type __n, const hasher& __hf, 1204 const key_equal& __eql) 1205 : __table_(__hf, __eql) 1206{ 1207#if _LIBCPP_DEBUG_LEVEL >= 2 1208 __get_db()->__insert_c(this); 1209#endif 1210 __table_.rehash(__n); 1211 insert(__il.begin(), __il.end()); 1212} 1213 1214template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1215unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1216 initializer_list<value_type> __il, size_type __n, const hasher& __hf, 1217 const key_equal& __eql, const allocator_type& __a) 1218 : __table_(__hf, __eql, __a) 1219{ 1220#if _LIBCPP_DEBUG_LEVEL >= 2 1221 __get_db()->__insert_c(this); 1222#endif 1223 __table_.rehash(__n); 1224 insert(__il.begin(), __il.end()); 1225} 1226 1227#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1228 1229#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1230 1231template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1232inline _LIBCPP_INLINE_VISIBILITY 1233unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& 1234unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(unordered_map&& __u) 1235 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value) 1236{ 1237 __table_ = _VSTD::move(__u.__table_); 1238 return *this; 1239} 1240 1241#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1242 1243#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1244 1245template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1246inline _LIBCPP_INLINE_VISIBILITY 1247unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& 1248unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=( 1249 initializer_list<value_type> __il) 1250{ 1251 __table_.__assign_unique(__il.begin(), __il.end()); 1252 return *this; 1253} 1254 1255#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1256 1257#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1258 1259template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1260typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder 1261unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node() 1262{ 1263 __node_allocator& __na = __table_.__node_alloc(); 1264 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 1265 __node_traits::construct(__na, _VSTD::addressof(__h->__value_)); 1266 __h.get_deleter().__first_constructed = true; 1267 __h.get_deleter().__second_constructed = true; 1268 return __h; 1269} 1270 1271template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1272template <class _A0> 1273typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder 1274unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(_A0&& __a0) 1275{ 1276 __node_allocator& __na = __table_.__node_alloc(); 1277 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 1278 __node_traits::construct(__na, _VSTD::addressof(__h->__value_), 1279 _VSTD::forward<_A0>(__a0)); 1280 __h.get_deleter().__first_constructed = true; 1281 __h.get_deleter().__second_constructed = true; 1282 return __h; 1283} 1284 1285template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1286typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder 1287unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node_with_key(key_type&& __k) 1288{ 1289 __node_allocator& __na = __table_.__node_alloc(); 1290 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 1291 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.first), _VSTD::move(__k)); 1292 __h.get_deleter().__first_constructed = true; 1293 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.second)); 1294 __h.get_deleter().__second_constructed = true; 1295 return __h; 1296} 1297 1298#ifndef _LIBCPP_HAS_NO_VARIADICS 1299 1300template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1301template <class _A0, class _A1, class ..._Args> 1302typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder 1303unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(_A0&& __a0, 1304 _A1&& __a1, 1305 _Args&&... __args) 1306{ 1307 __node_allocator& __na = __table_.__node_alloc(); 1308 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 1309 __node_traits::construct(__na, _VSTD::addressof(__h->__value_), 1310 _VSTD::forward<_A0>(__a0), _VSTD::forward<_A1>(__a1), 1311 _VSTD::forward<_Args>(__args)...); 1312 __h.get_deleter().__first_constructed = true; 1313 __h.get_deleter().__second_constructed = true; 1314 return __h; 1315} 1316 1317template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1318template <class... _Args> 1319pair<typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::iterator, bool> 1320unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::emplace(_Args&&... __args) 1321{ 1322 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); 1323 pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get()); 1324 if (__r.second) 1325 __h.release(); 1326 return __r; 1327} 1328 1329#endif // _LIBCPP_HAS_NO_VARIADICS 1330#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1331 1332template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1333typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder 1334unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node_with_key(const key_type& __k) 1335{ 1336 __node_allocator& __na = __table_.__node_alloc(); 1337 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 1338 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.first), __k); 1339 __h.get_deleter().__first_constructed = true; 1340 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.second)); 1341 __h.get_deleter().__second_constructed = true; 1342 return _VSTD::move(__h); // explicitly moved for C++03 1343} 1344 1345template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1346template <class _InputIterator> 1347inline _LIBCPP_INLINE_VISIBILITY 1348void 1349unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, 1350 _InputIterator __last) 1351{ 1352 for (; __first != __last; ++__first) 1353 __table_.__insert_unique(*__first); 1354} 1355 1356template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1357_Tp& 1358unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](const key_type& __k) 1359{ 1360 iterator __i = find(__k); 1361 if (__i != end()) 1362 return __i->second; 1363 __node_holder __h = __construct_node_with_key(__k); 1364 pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get()); 1365 __h.release(); 1366 return __r.first->second; 1367} 1368 1369#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1370 1371template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1372_Tp& 1373unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](key_type&& __k) 1374{ 1375 iterator __i = find(__k); 1376 if (__i != end()) 1377 return __i->second; 1378 __node_holder __h = __construct_node_with_key(_VSTD::move(__k)); 1379 pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get()); 1380 __h.release(); 1381 return __r.first->second; 1382} 1383 1384#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1385 1386template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1387_Tp& 1388unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::at(const key_type& __k) 1389{ 1390 iterator __i = find(__k); 1391#ifndef _LIBCPP_NO_EXCEPTIONS 1392 if (__i == end()) 1393 throw out_of_range("unordered_map::at: key not found"); 1394#endif // _LIBCPP_NO_EXCEPTIONS 1395 return __i->second; 1396} 1397 1398template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1399const _Tp& 1400unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::at(const key_type& __k) const 1401{ 1402 const_iterator __i = find(__k); 1403#ifndef _LIBCPP_NO_EXCEPTIONS 1404 if (__i == end()) 1405 throw out_of_range("unordered_map::at: key not found"); 1406#endif // _LIBCPP_NO_EXCEPTIONS 1407 return __i->second; 1408} 1409 1410template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1411inline _LIBCPP_INLINE_VISIBILITY 1412void 1413swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 1414 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 1415 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 1416{ 1417 __x.swap(__y); 1418} 1419 1420template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1421bool 1422operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 1423 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 1424{ 1425 if (__x.size() != __y.size()) 1426 return false; 1427 typedef typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator 1428 const_iterator; 1429 for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end(); 1430 __i != __ex; ++__i) 1431 { 1432 const_iterator __j = __y.find(__i->first); 1433 if (__j == __ey || !(*__i == *__j)) 1434 return false; 1435 } 1436 return true; 1437} 1438 1439template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1440inline _LIBCPP_INLINE_VISIBILITY 1441bool 1442operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 1443 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 1444{ 1445 return !(__x == __y); 1446} 1447 1448template <class _Key, class _Tp, class _Hash = hash<_Key>, class _Pred = equal_to<_Key>, 1449 class _Alloc = allocator<pair<const _Key, _Tp> > > 1450class _LIBCPP_TYPE_VIS_ONLY unordered_multimap 1451{ 1452public: 1453 // types 1454 typedef _Key key_type; 1455 typedef _Tp mapped_type; 1456 typedef _Hash hasher; 1457 typedef _Pred key_equal; 1458 typedef _Alloc allocator_type; 1459 typedef pair<const key_type, mapped_type> value_type; 1460 typedef pair<key_type, mapped_type> __nc_value_type; 1461 typedef value_type& reference; 1462 typedef const value_type& const_reference; 1463 static_assert((is_same<value_type, typename allocator_type::value_type>::value), 1464 "Invalid allocator::value_type"); 1465 1466private: 1467 typedef __hash_value_type<key_type, mapped_type> __value_type; 1468 typedef __unordered_map_hasher<key_type, __value_type, hasher> __hasher; 1469 typedef __unordered_map_equal<key_type, __value_type, key_equal> __key_equal; 1470 typedef typename allocator_traits<allocator_type>::template 1471#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 1472 rebind_alloc<__value_type> 1473#else 1474 rebind_alloc<__value_type>::other 1475#endif 1476 __allocator_type; 1477 1478 typedef __hash_table<__value_type, __hasher, 1479 __key_equal, __allocator_type> __table; 1480 1481 __table __table_; 1482 1483 typedef typename __table::__node_traits __node_traits; 1484 typedef typename __table::__node_allocator __node_allocator; 1485 typedef typename __table::__node __node; 1486 typedef __hash_map_node_destructor<__node_allocator> _Dp; 1487 typedef unique_ptr<__node, _Dp> __node_holder; 1488 typedef allocator_traits<allocator_type> __alloc_traits; 1489public: 1490 typedef typename __alloc_traits::pointer pointer; 1491 typedef typename __alloc_traits::const_pointer const_pointer; 1492 typedef typename __alloc_traits::size_type size_type; 1493 typedef typename __alloc_traits::difference_type difference_type; 1494 1495 typedef __hash_map_iterator<typename __table::iterator> iterator; 1496 typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator; 1497 typedef __hash_map_iterator<typename __table::local_iterator> local_iterator; 1498 typedef __hash_map_const_iterator<typename __table::const_local_iterator> const_local_iterator; 1499 1500 _LIBCPP_INLINE_VISIBILITY 1501 unordered_multimap() 1502 _NOEXCEPT_(is_nothrow_default_constructible<__table>::value) 1503 { 1504#if _LIBCPP_DEBUG_LEVEL >= 2 1505 __get_db()->__insert_c(this); 1506#endif 1507 } 1508 explicit unordered_multimap(size_type __n, const hasher& __hf = hasher(), 1509 const key_equal& __eql = key_equal()); 1510 unordered_multimap(size_type __n, const hasher& __hf, 1511 const key_equal& __eql, 1512 const allocator_type& __a); 1513 template <class _InputIterator> 1514 unordered_multimap(_InputIterator __first, _InputIterator __last); 1515 template <class _InputIterator> 1516 unordered_multimap(_InputIterator __first, _InputIterator __last, 1517 size_type __n, const hasher& __hf = hasher(), 1518 const key_equal& __eql = key_equal()); 1519 template <class _InputIterator> 1520 unordered_multimap(_InputIterator __first, _InputIterator __last, 1521 size_type __n, const hasher& __hf, 1522 const key_equal& __eql, 1523 const allocator_type& __a); 1524 explicit unordered_multimap(const allocator_type& __a); 1525 unordered_multimap(const unordered_multimap& __u); 1526 unordered_multimap(const unordered_multimap& __u, const allocator_type& __a); 1527#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1528 unordered_multimap(unordered_multimap&& __u) 1529 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value); 1530 unordered_multimap(unordered_multimap&& __u, const allocator_type& __a); 1531#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1532#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1533 unordered_multimap(initializer_list<value_type> __il); 1534 unordered_multimap(initializer_list<value_type> __il, size_type __n, 1535 const hasher& __hf = hasher(), 1536 const key_equal& __eql = key_equal()); 1537 unordered_multimap(initializer_list<value_type> __il, size_type __n, 1538 const hasher& __hf, const key_equal& __eql, 1539 const allocator_type& __a); 1540#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1541#if _LIBCPP_STD_VER > 11 1542 _LIBCPP_INLINE_VISIBILITY 1543 unordered_multimap(size_type __n, const allocator_type& __a) 1544 : unordered_multimap(__n, hasher(), key_equal(), __a) {} 1545 _LIBCPP_INLINE_VISIBILITY 1546 unordered_multimap(size_type __n, const hasher& __hf, const allocator_type& __a) 1547 : unordered_multimap(__n, __hf, key_equal(), __a) {} 1548 template <class _InputIterator> 1549 _LIBCPP_INLINE_VISIBILITY 1550 unordered_multimap(_InputIterator __first, _InputIterator __last, size_type __n, const allocator_type& __a) 1551 : unordered_multimap(__first, __last, __n, hasher(), key_equal(), __a) {} 1552 template <class _InputIterator> 1553 _LIBCPP_INLINE_VISIBILITY 1554 unordered_multimap(_InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, 1555 const allocator_type& __a) 1556 : unordered_multimap(__first, __last, __n, __hf, key_equal(), __a) {} 1557 _LIBCPP_INLINE_VISIBILITY 1558 unordered_multimap(initializer_list<value_type> __il, size_type __n, const allocator_type& __a) 1559 : unordered_multimap(__il, __n, hasher(), key_equal(), __a) {} 1560 _LIBCPP_INLINE_VISIBILITY 1561 unordered_multimap(initializer_list<value_type> __il, size_type __n, const hasher& __hf, 1562 const allocator_type& __a) 1563 : unordered_multimap(__il, __n, __hf, key_equal(), __a) {} 1564#endif 1565 // ~unordered_multimap() = default; 1566 _LIBCPP_INLINE_VISIBILITY 1567 unordered_multimap& operator=(const unordered_multimap& __u) 1568 { 1569#if __cplusplus >= 201103L 1570 __table_ = __u.__table_; 1571#else 1572 if (this != &__u) { 1573 __table_.clear(); 1574 __table_.hash_function() = __u.__table_.hash_function(); 1575 __table_.key_eq() = __u.__table_.key_eq(); 1576 __table_.max_load_factor() = __u.__table_.max_load_factor(); 1577 __table_.__copy_assign_alloc(__u.__table_); 1578 insert(__u.begin(), __u.end()); 1579 } 1580#endif 1581 return *this; 1582 } 1583#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1584 unordered_multimap& operator=(unordered_multimap&& __u) 1585 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value); 1586#endif 1587#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1588 unordered_multimap& operator=(initializer_list<value_type> __il); 1589#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1590 1591 _LIBCPP_INLINE_VISIBILITY 1592 allocator_type get_allocator() const _NOEXCEPT 1593 {return allocator_type(__table_.__node_alloc());} 1594 1595 _LIBCPP_INLINE_VISIBILITY 1596 bool empty() const _NOEXCEPT {return __table_.size() == 0;} 1597 _LIBCPP_INLINE_VISIBILITY 1598 size_type size() const _NOEXCEPT {return __table_.size();} 1599 _LIBCPP_INLINE_VISIBILITY 1600 size_type max_size() const _NOEXCEPT {return __table_.max_size();} 1601 1602 _LIBCPP_INLINE_VISIBILITY 1603 iterator begin() _NOEXCEPT {return __table_.begin();} 1604 _LIBCPP_INLINE_VISIBILITY 1605 iterator end() _NOEXCEPT {return __table_.end();} 1606 _LIBCPP_INLINE_VISIBILITY 1607 const_iterator begin() const _NOEXCEPT {return __table_.begin();} 1608 _LIBCPP_INLINE_VISIBILITY 1609 const_iterator end() const _NOEXCEPT {return __table_.end();} 1610 _LIBCPP_INLINE_VISIBILITY 1611 const_iterator cbegin() const _NOEXCEPT {return __table_.begin();} 1612 _LIBCPP_INLINE_VISIBILITY 1613 const_iterator cend() const _NOEXCEPT {return __table_.end();} 1614 1615#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1616#ifndef _LIBCPP_HAS_NO_VARIADICS 1617 1618 template <class... _Args> 1619 iterator emplace(_Args&&... __args); 1620 1621 template <class... _Args> 1622 iterator emplace_hint(const_iterator __p, _Args&&... __args); 1623#endif // _LIBCPP_HAS_NO_VARIADICS 1624#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1625 _LIBCPP_INLINE_VISIBILITY 1626 iterator insert(const value_type& __x) {return __table_.__insert_multi(__x);} 1627#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1628 template <class _Pp, 1629 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type> 1630 _LIBCPP_INLINE_VISIBILITY 1631 iterator insert(_Pp&& __x) 1632 {return __table_.__insert_multi(_VSTD::forward<_Pp>(__x));} 1633#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1634 _LIBCPP_INLINE_VISIBILITY 1635 iterator insert(const_iterator __p, const value_type& __x) 1636 {return __table_.__insert_multi(__p.__i_, __x);} 1637#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1638 template <class _Pp, 1639 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type> 1640 _LIBCPP_INLINE_VISIBILITY 1641 iterator insert(const_iterator __p, _Pp&& __x) 1642 {return __table_.__insert_multi(__p.__i_, _VSTD::forward<_Pp>(__x));} 1643#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1644 template <class _InputIterator> 1645 void insert(_InputIterator __first, _InputIterator __last); 1646#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1647 _LIBCPP_INLINE_VISIBILITY 1648 void insert(initializer_list<value_type> __il) 1649 {insert(__il.begin(), __il.end());} 1650#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1651 1652 _LIBCPP_INLINE_VISIBILITY 1653 iterator erase(const_iterator __p) {return __table_.erase(__p.__i_);} 1654 _LIBCPP_INLINE_VISIBILITY 1655 size_type erase(const key_type& __k) {return __table_.__erase_multi(__k);} 1656 _LIBCPP_INLINE_VISIBILITY 1657 iterator erase(const_iterator __first, const_iterator __last) 1658 {return __table_.erase(__first.__i_, __last.__i_);} 1659 _LIBCPP_INLINE_VISIBILITY 1660 void clear() _NOEXCEPT {__table_.clear();} 1661 1662 _LIBCPP_INLINE_VISIBILITY 1663 void swap(unordered_multimap& __u) 1664 _NOEXCEPT_(__is_nothrow_swappable<__table>::value) 1665 {__table_.swap(__u.__table_);} 1666 1667 _LIBCPP_INLINE_VISIBILITY 1668 hasher hash_function() const 1669 {return __table_.hash_function().hash_function();} 1670 _LIBCPP_INLINE_VISIBILITY 1671 key_equal key_eq() const 1672 {return __table_.key_eq().key_eq();} 1673 1674 _LIBCPP_INLINE_VISIBILITY 1675 iterator find(const key_type& __k) {return __table_.find(__k);} 1676 _LIBCPP_INLINE_VISIBILITY 1677 const_iterator find(const key_type& __k) const {return __table_.find(__k);} 1678 _LIBCPP_INLINE_VISIBILITY 1679 size_type count(const key_type& __k) const {return __table_.__count_multi(__k);} 1680 _LIBCPP_INLINE_VISIBILITY 1681 pair<iterator, iterator> equal_range(const key_type& __k) 1682 {return __table_.__equal_range_multi(__k);} 1683 _LIBCPP_INLINE_VISIBILITY 1684 pair<const_iterator, const_iterator> equal_range(const key_type& __k) const 1685 {return __table_.__equal_range_multi(__k);} 1686 1687 _LIBCPP_INLINE_VISIBILITY 1688 size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();} 1689 _LIBCPP_INLINE_VISIBILITY 1690 size_type max_bucket_count() const _NOEXCEPT 1691 {return __table_.max_bucket_count();} 1692 1693 _LIBCPP_INLINE_VISIBILITY 1694 size_type bucket_size(size_type __n) const 1695 {return __table_.bucket_size(__n);} 1696 _LIBCPP_INLINE_VISIBILITY 1697 size_type bucket(const key_type& __k) const {return __table_.bucket(__k);} 1698 1699 _LIBCPP_INLINE_VISIBILITY 1700 local_iterator begin(size_type __n) {return __table_.begin(__n);} 1701 _LIBCPP_INLINE_VISIBILITY 1702 local_iterator end(size_type __n) {return __table_.end(__n);} 1703 _LIBCPP_INLINE_VISIBILITY 1704 const_local_iterator begin(size_type __n) const {return __table_.cbegin(__n);} 1705 _LIBCPP_INLINE_VISIBILITY 1706 const_local_iterator end(size_type __n) const {return __table_.cend(__n);} 1707 _LIBCPP_INLINE_VISIBILITY 1708 const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);} 1709 _LIBCPP_INLINE_VISIBILITY 1710 const_local_iterator cend(size_type __n) const {return __table_.cend(__n);} 1711 1712 _LIBCPP_INLINE_VISIBILITY 1713 float load_factor() const _NOEXCEPT {return __table_.load_factor();} 1714 _LIBCPP_INLINE_VISIBILITY 1715 float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();} 1716 _LIBCPP_INLINE_VISIBILITY 1717 void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);} 1718 _LIBCPP_INLINE_VISIBILITY 1719 void rehash(size_type __n) {__table_.rehash(__n);} 1720 _LIBCPP_INLINE_VISIBILITY 1721 void reserve(size_type __n) {__table_.reserve(__n);} 1722 1723#if _LIBCPP_DEBUG_LEVEL >= 2 1724 1725 bool __dereferenceable(const const_iterator* __i) const 1726 {return __table_.__dereferenceable(&__i->__i_);} 1727 bool __decrementable(const const_iterator* __i) const 1728 {return __table_.__decrementable(&__i->__i_);} 1729 bool __addable(const const_iterator* __i, ptrdiff_t __n) const 1730 {return __table_.__addable(&__i->__i_, __n);} 1731 bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const 1732 {return __table_.__addable(&__i->__i_, __n);} 1733 1734#endif // _LIBCPP_DEBUG_LEVEL >= 2 1735 1736private: 1737#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1738 __node_holder __construct_node(); 1739 template <class _A0> 1740 __node_holder 1741 __construct_node(_A0&& __a0); 1742#ifndef _LIBCPP_HAS_NO_VARIADICS 1743 template <class _A0, class _A1, class ..._Args> 1744 __node_holder __construct_node(_A0&& __a0, _A1&& __a1, _Args&& ...__args); 1745#endif // _LIBCPP_HAS_NO_VARIADICS 1746#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1747}; 1748 1749template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1750unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1751 size_type __n, const hasher& __hf, const key_equal& __eql) 1752 : __table_(__hf, __eql) 1753{ 1754#if _LIBCPP_DEBUG_LEVEL >= 2 1755 __get_db()->__insert_c(this); 1756#endif 1757 __table_.rehash(__n); 1758} 1759 1760template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1761unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1762 size_type __n, const hasher& __hf, const key_equal& __eql, 1763 const allocator_type& __a) 1764 : __table_(__hf, __eql, __a) 1765{ 1766#if _LIBCPP_DEBUG_LEVEL >= 2 1767 __get_db()->__insert_c(this); 1768#endif 1769 __table_.rehash(__n); 1770} 1771 1772template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1773template <class _InputIterator> 1774unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1775 _InputIterator __first, _InputIterator __last) 1776{ 1777#if _LIBCPP_DEBUG_LEVEL >= 2 1778 __get_db()->__insert_c(this); 1779#endif 1780 insert(__first, __last); 1781} 1782 1783template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1784template <class _InputIterator> 1785unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1786 _InputIterator __first, _InputIterator __last, size_type __n, 1787 const hasher& __hf, const key_equal& __eql) 1788 : __table_(__hf, __eql) 1789{ 1790#if _LIBCPP_DEBUG_LEVEL >= 2 1791 __get_db()->__insert_c(this); 1792#endif 1793 __table_.rehash(__n); 1794 insert(__first, __last); 1795} 1796 1797template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1798template <class _InputIterator> 1799unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1800 _InputIterator __first, _InputIterator __last, size_type __n, 1801 const hasher& __hf, const key_equal& __eql, const allocator_type& __a) 1802 : __table_(__hf, __eql, __a) 1803{ 1804#if _LIBCPP_DEBUG_LEVEL >= 2 1805 __get_db()->__insert_c(this); 1806#endif 1807 __table_.rehash(__n); 1808 insert(__first, __last); 1809} 1810 1811template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1812inline _LIBCPP_INLINE_VISIBILITY 1813unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1814 const allocator_type& __a) 1815 : __table_(__a) 1816{ 1817#if _LIBCPP_DEBUG_LEVEL >= 2 1818 __get_db()->__insert_c(this); 1819#endif 1820} 1821 1822template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1823unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1824 const unordered_multimap& __u) 1825 : __table_(__u.__table_) 1826{ 1827#if _LIBCPP_DEBUG_LEVEL >= 2 1828 __get_db()->__insert_c(this); 1829#endif 1830 __table_.rehash(__u.bucket_count()); 1831 insert(__u.begin(), __u.end()); 1832} 1833 1834template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1835unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1836 const unordered_multimap& __u, const allocator_type& __a) 1837 : __table_(__u.__table_, __a) 1838{ 1839#if _LIBCPP_DEBUG_LEVEL >= 2 1840 __get_db()->__insert_c(this); 1841#endif 1842 __table_.rehash(__u.bucket_count()); 1843 insert(__u.begin(), __u.end()); 1844} 1845 1846#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1847 1848template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1849inline _LIBCPP_INLINE_VISIBILITY 1850unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1851 unordered_multimap&& __u) 1852 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value) 1853 : __table_(_VSTD::move(__u.__table_)) 1854{ 1855#if _LIBCPP_DEBUG_LEVEL >= 2 1856 __get_db()->__insert_c(this); 1857 __get_db()->swap(this, &__u); 1858#endif 1859} 1860 1861template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1862unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1863 unordered_multimap&& __u, const allocator_type& __a) 1864 : __table_(_VSTD::move(__u.__table_), __a) 1865{ 1866#if _LIBCPP_DEBUG_LEVEL >= 2 1867 __get_db()->__insert_c(this); 1868#endif 1869 if (__a != __u.get_allocator()) 1870 { 1871 iterator __i = __u.begin(); 1872 while (__u.size() != 0) 1873 { 1874 __table_.__insert_multi( 1875 _VSTD::move(__u.__table_.remove((__i++).__i_)->__value_) 1876 ); 1877 } 1878 } 1879#if _LIBCPP_DEBUG_LEVEL >= 2 1880 else 1881 __get_db()->swap(this, &__u); 1882#endif 1883} 1884 1885#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1886 1887#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1888 1889template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1890unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1891 initializer_list<value_type> __il) 1892{ 1893#if _LIBCPP_DEBUG_LEVEL >= 2 1894 __get_db()->__insert_c(this); 1895#endif 1896 insert(__il.begin(), __il.end()); 1897} 1898 1899template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1900unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1901 initializer_list<value_type> __il, size_type __n, const hasher& __hf, 1902 const key_equal& __eql) 1903 : __table_(__hf, __eql) 1904{ 1905#if _LIBCPP_DEBUG_LEVEL >= 2 1906 __get_db()->__insert_c(this); 1907#endif 1908 __table_.rehash(__n); 1909 insert(__il.begin(), __il.end()); 1910} 1911 1912template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1913unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1914 initializer_list<value_type> __il, size_type __n, const hasher& __hf, 1915 const key_equal& __eql, const allocator_type& __a) 1916 : __table_(__hf, __eql, __a) 1917{ 1918#if _LIBCPP_DEBUG_LEVEL >= 2 1919 __get_db()->__insert_c(this); 1920#endif 1921 __table_.rehash(__n); 1922 insert(__il.begin(), __il.end()); 1923} 1924 1925#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1926 1927#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1928 1929template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1930inline _LIBCPP_INLINE_VISIBILITY 1931unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& 1932unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(unordered_multimap&& __u) 1933 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value) 1934{ 1935 __table_ = _VSTD::move(__u.__table_); 1936 return *this; 1937} 1938 1939#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1940 1941#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1942 1943template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1944inline _LIBCPP_INLINE_VISIBILITY 1945unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& 1946unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=( 1947 initializer_list<value_type> __il) 1948{ 1949 __table_.__assign_multi(__il.begin(), __il.end()); 1950 return *this; 1951} 1952 1953#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1954 1955#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1956 1957template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1958typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder 1959unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node() 1960{ 1961 __node_allocator& __na = __table_.__node_alloc(); 1962 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 1963 __node_traits::construct(__na, _VSTD::addressof(__h->__value_)); 1964 __h.get_deleter().__first_constructed = true; 1965 __h.get_deleter().__second_constructed = true; 1966 return __h; 1967} 1968 1969template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1970template <class _A0> 1971typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder 1972unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(_A0&& __a0) 1973{ 1974 __node_allocator& __na = __table_.__node_alloc(); 1975 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 1976 __node_traits::construct(__na, _VSTD::addressof(__h->__value_), 1977 _VSTD::forward<_A0>(__a0)); 1978 __h.get_deleter().__first_constructed = true; 1979 __h.get_deleter().__second_constructed = true; 1980 return __h; 1981} 1982 1983#ifndef _LIBCPP_HAS_NO_VARIADICS 1984 1985template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1986template <class _A0, class _A1, class ..._Args> 1987typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder 1988unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node( 1989 _A0&& __a0, _A1&& __a1, _Args&&... __args) 1990{ 1991 __node_allocator& __na = __table_.__node_alloc(); 1992 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 1993 __node_traits::construct(__na, _VSTD::addressof(__h->__value_), 1994 _VSTD::forward<_A0>(__a0), _VSTD::forward<_A1>(__a1), 1995 _VSTD::forward<_Args>(__args)...); 1996 __h.get_deleter().__first_constructed = true; 1997 __h.get_deleter().__second_constructed = true; 1998 return __h; 1999} 2000 2001template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2002template <class... _Args> 2003typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::iterator 2004unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::emplace(_Args&&... __args) 2005{ 2006 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); 2007 iterator __r = __table_.__node_insert_multi(__h.get()); 2008 __h.release(); 2009 return __r; 2010} 2011 2012template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2013template <class... _Args> 2014typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::iterator 2015unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::emplace_hint( 2016 const_iterator __p, _Args&&... __args) 2017{ 2018 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); 2019 iterator __r = __table_.__node_insert_multi(__p.__i_, __h.get()); 2020 __h.release(); 2021 return __r; 2022} 2023 2024#endif // _LIBCPP_HAS_NO_VARIADICS 2025#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 2026 2027template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2028template <class _InputIterator> 2029inline _LIBCPP_INLINE_VISIBILITY 2030void 2031unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, 2032 _InputIterator __last) 2033{ 2034 for (; __first != __last; ++__first) 2035 __table_.__insert_multi(*__first); 2036} 2037 2038template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2039inline _LIBCPP_INLINE_VISIBILITY 2040void 2041swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 2042 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 2043 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 2044{ 2045 __x.swap(__y); 2046} 2047 2048template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2049bool 2050operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 2051 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 2052{ 2053 if (__x.size() != __y.size()) 2054 return false; 2055 typedef typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator 2056 const_iterator; 2057 typedef pair<const_iterator, const_iterator> _EqRng; 2058 for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;) 2059 { 2060 _EqRng __xeq = __x.equal_range(__i->first); 2061 _EqRng __yeq = __y.equal_range(__i->first); 2062 if (_VSTD::distance(__xeq.first, __xeq.second) != 2063 _VSTD::distance(__yeq.first, __yeq.second) || 2064 !_VSTD::is_permutation(__xeq.first, __xeq.second, __yeq.first)) 2065 return false; 2066 __i = __xeq.second; 2067 } 2068 return true; 2069} 2070 2071template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2072inline _LIBCPP_INLINE_VISIBILITY 2073bool 2074operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 2075 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 2076{ 2077 return !(__x == __y); 2078} 2079 2080_LIBCPP_END_NAMESPACE_STD 2081 2082#endif // _LIBCPP_UNORDERED_MAP 2083