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