unordered_map revision 262801
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 __table_.clear(); 835 __table_.hash_function() = __u.__table_.hash_function(); 836 __table_.key_eq() = __u.__table_.key_eq(); 837 __table_.max_load_factor() = __u.__table_.max_load_factor(); 838 __table_.__copy_assign_alloc(__u.__table_); 839 insert(__u.begin(), __u.end()); 840#endif 841 return *this; 842 } 843#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 844 unordered_map& operator=(unordered_map&& __u) 845 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value); 846#endif 847#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 848 unordered_map& operator=(initializer_list<value_type> __il); 849#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 850 851 _LIBCPP_INLINE_VISIBILITY 852 allocator_type get_allocator() const _NOEXCEPT 853 {return allocator_type(__table_.__node_alloc());} 854 855 _LIBCPP_INLINE_VISIBILITY 856 bool empty() const _NOEXCEPT {return __table_.size() == 0;} 857 _LIBCPP_INLINE_VISIBILITY 858 size_type size() const _NOEXCEPT {return __table_.size();} 859 _LIBCPP_INLINE_VISIBILITY 860 size_type max_size() const _NOEXCEPT {return __table_.max_size();} 861 862 _LIBCPP_INLINE_VISIBILITY 863 iterator begin() _NOEXCEPT {return __table_.begin();} 864 _LIBCPP_INLINE_VISIBILITY 865 iterator end() _NOEXCEPT {return __table_.end();} 866 _LIBCPP_INLINE_VISIBILITY 867 const_iterator begin() const _NOEXCEPT {return __table_.begin();} 868 _LIBCPP_INLINE_VISIBILITY 869 const_iterator end() const _NOEXCEPT {return __table_.end();} 870 _LIBCPP_INLINE_VISIBILITY 871 const_iterator cbegin() const _NOEXCEPT {return __table_.begin();} 872 _LIBCPP_INLINE_VISIBILITY 873 const_iterator cend() const _NOEXCEPT {return __table_.end();} 874 875#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 876#ifndef _LIBCPP_HAS_NO_VARIADICS 877 878 template <class... _Args> 879 pair<iterator, bool> emplace(_Args&&... __args); 880 881 template <class... _Args> 882 _LIBCPP_INLINE_VISIBILITY 883#if _LIBCPP_DEBUG_LEVEL >= 2 884 iterator emplace_hint(const_iterator __p, _Args&&... __args) 885 { 886 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 887 "unordered_map::emplace_hint(const_iterator, args...) called with an iterator not" 888 " referring to this unordered_map"); 889 return __table_.__emplace_unique(_VSTD::forward<_Args>(__args)...).first; 890 } 891#else 892 iterator emplace_hint(const_iterator, _Args&&... __args) 893 {return emplace(_VSTD::forward<_Args>(__args)...).first;} 894#endif 895#endif // _LIBCPP_HAS_NO_VARIADICS 896#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 897 _LIBCPP_INLINE_VISIBILITY 898 pair<iterator, bool> insert(const value_type& __x) 899 {return __table_.__insert_unique(__x);} 900#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 901 template <class _Pp, 902 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type> 903 _LIBCPP_INLINE_VISIBILITY 904 pair<iterator, bool> insert(_Pp&& __x) 905 {return __table_.__insert_unique(_VSTD::forward<_Pp>(__x));} 906#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 907 _LIBCPP_INLINE_VISIBILITY 908#if _LIBCPP_DEBUG_LEVEL >= 2 909 iterator insert(const_iterator __p, const value_type& __x) 910 { 911 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 912 "unordered_map::insert(const_iterator, const value_type&) called with an iterator not" 913 " referring to this unordered_map"); 914 return insert(__x).first; 915 } 916#else 917 iterator insert(const_iterator, const value_type& __x) 918 {return insert(__x).first;} 919#endif 920#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 921 template <class _Pp, 922 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type> 923 _LIBCPP_INLINE_VISIBILITY 924#if _LIBCPP_DEBUG_LEVEL >= 2 925 iterator insert(const_iterator __p, _Pp&& __x) 926 { 927 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 928 "unordered_map::insert(const_iterator, value_type&&) called with an iterator not" 929 " referring to this unordered_map"); 930 return insert(_VSTD::forward<_Pp>(__x)).first; 931 } 932#else 933 iterator insert(const_iterator, _Pp&& __x) 934 {return insert(_VSTD::forward<_Pp>(__x)).first;} 935#endif 936#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 937 template <class _InputIterator> 938 void insert(_InputIterator __first, _InputIterator __last); 939#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 940 _LIBCPP_INLINE_VISIBILITY 941 void insert(initializer_list<value_type> __il) 942 {insert(__il.begin(), __il.end());} 943#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 944 945 _LIBCPP_INLINE_VISIBILITY 946 iterator erase(const_iterator __p) {return __table_.erase(__p.__i_);} 947 _LIBCPP_INLINE_VISIBILITY 948 size_type erase(const key_type& __k) {return __table_.__erase_unique(__k);} 949 _LIBCPP_INLINE_VISIBILITY 950 iterator erase(const_iterator __first, const_iterator __last) 951 {return __table_.erase(__first.__i_, __last.__i_);} 952 _LIBCPP_INLINE_VISIBILITY 953 void clear() _NOEXCEPT {__table_.clear();} 954 955 _LIBCPP_INLINE_VISIBILITY 956 void swap(unordered_map& __u) 957 _NOEXCEPT_(__is_nothrow_swappable<__table>::value) 958 {__table_.swap(__u.__table_);} 959 960 _LIBCPP_INLINE_VISIBILITY 961 hasher hash_function() const 962 {return __table_.hash_function().hash_function();} 963 _LIBCPP_INLINE_VISIBILITY 964 key_equal key_eq() const 965 {return __table_.key_eq().key_eq();} 966 967 _LIBCPP_INLINE_VISIBILITY 968 iterator find(const key_type& __k) {return __table_.find(__k);} 969 _LIBCPP_INLINE_VISIBILITY 970 const_iterator find(const key_type& __k) const {return __table_.find(__k);} 971 _LIBCPP_INLINE_VISIBILITY 972 size_type count(const key_type& __k) const {return __table_.__count_unique(__k);} 973 _LIBCPP_INLINE_VISIBILITY 974 pair<iterator, iterator> equal_range(const key_type& __k) 975 {return __table_.__equal_range_unique(__k);} 976 _LIBCPP_INLINE_VISIBILITY 977 pair<const_iterator, const_iterator> equal_range(const key_type& __k) const 978 {return __table_.__equal_range_unique(__k);} 979 980 mapped_type& operator[](const key_type& __k); 981#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 982 mapped_type& operator[](key_type&& __k); 983#endif 984 985 mapped_type& at(const key_type& __k); 986 const mapped_type& at(const key_type& __k) const; 987 988 _LIBCPP_INLINE_VISIBILITY 989 size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();} 990 _LIBCPP_INLINE_VISIBILITY 991 size_type max_bucket_count() const _NOEXCEPT {return __table_.max_bucket_count();} 992 993 _LIBCPP_INLINE_VISIBILITY 994 size_type bucket_size(size_type __n) const 995 {return __table_.bucket_size(__n);} 996 _LIBCPP_INLINE_VISIBILITY 997 size_type bucket(const key_type& __k) const {return __table_.bucket(__k);} 998 999 _LIBCPP_INLINE_VISIBILITY 1000 local_iterator begin(size_type __n) {return __table_.begin(__n);} 1001 _LIBCPP_INLINE_VISIBILITY 1002 local_iterator end(size_type __n) {return __table_.end(__n);} 1003 _LIBCPP_INLINE_VISIBILITY 1004 const_local_iterator begin(size_type __n) const {return __table_.cbegin(__n);} 1005 _LIBCPP_INLINE_VISIBILITY 1006 const_local_iterator end(size_type __n) const {return __table_.cend(__n);} 1007 _LIBCPP_INLINE_VISIBILITY 1008 const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);} 1009 _LIBCPP_INLINE_VISIBILITY 1010 const_local_iterator cend(size_type __n) const {return __table_.cend(__n);} 1011 1012 _LIBCPP_INLINE_VISIBILITY 1013 float load_factor() const _NOEXCEPT {return __table_.load_factor();} 1014 _LIBCPP_INLINE_VISIBILITY 1015 float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();} 1016 _LIBCPP_INLINE_VISIBILITY 1017 void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);} 1018 _LIBCPP_INLINE_VISIBILITY 1019 void rehash(size_type __n) {__table_.rehash(__n);} 1020 _LIBCPP_INLINE_VISIBILITY 1021 void reserve(size_type __n) {__table_.reserve(__n);} 1022 1023#if _LIBCPP_DEBUG_LEVEL >= 2 1024 1025 bool __dereferenceable(const const_iterator* __i) const 1026 {return __table_.__dereferenceable(&__i->__i_);} 1027 bool __decrementable(const const_iterator* __i) const 1028 {return __table_.__decrementable(&__i->__i_);} 1029 bool __addable(const const_iterator* __i, ptrdiff_t __n) const 1030 {return __table_.__addable(&__i->__i_, __n);} 1031 bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const 1032 {return __table_.__addable(&__i->__i_, __n);} 1033 1034#endif // _LIBCPP_DEBUG_LEVEL >= 2 1035 1036private: 1037#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1038 __node_holder __construct_node(); 1039 template <class _A0> 1040 __node_holder 1041 __construct_node(_A0&& __a0); 1042 __node_holder __construct_node_with_key(key_type&& __k); 1043#ifndef _LIBCPP_HAS_NO_VARIADICS 1044 template <class _A0, class _A1, class ..._Args> 1045 __node_holder __construct_node(_A0&& __a0, _A1&& __a1, _Args&& ...__args); 1046#endif // _LIBCPP_HAS_NO_VARIADICS 1047#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1048 __node_holder __construct_node_with_key(const key_type& __k); 1049}; 1050 1051template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1052unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1053 size_type __n, const hasher& __hf, const key_equal& __eql) 1054 : __table_(__hf, __eql) 1055{ 1056#if _LIBCPP_DEBUG_LEVEL >= 2 1057 __get_db()->__insert_c(this); 1058#endif 1059 __table_.rehash(__n); 1060} 1061 1062template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1063unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1064 size_type __n, const hasher& __hf, const key_equal& __eql, 1065 const allocator_type& __a) 1066 : __table_(__hf, __eql, __a) 1067{ 1068#if _LIBCPP_DEBUG_LEVEL >= 2 1069 __get_db()->__insert_c(this); 1070#endif 1071 __table_.rehash(__n); 1072} 1073 1074template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1075inline _LIBCPP_INLINE_VISIBILITY 1076unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1077 const allocator_type& __a) 1078 : __table_(__a) 1079{ 1080#if _LIBCPP_DEBUG_LEVEL >= 2 1081 __get_db()->__insert_c(this); 1082#endif 1083} 1084 1085template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1086template <class _InputIterator> 1087unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1088 _InputIterator __first, _InputIterator __last) 1089{ 1090#if _LIBCPP_DEBUG_LEVEL >= 2 1091 __get_db()->__insert_c(this); 1092#endif 1093 insert(__first, __last); 1094} 1095 1096template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1097template <class _InputIterator> 1098unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1099 _InputIterator __first, _InputIterator __last, size_type __n, 1100 const hasher& __hf, const key_equal& __eql) 1101 : __table_(__hf, __eql) 1102{ 1103#if _LIBCPP_DEBUG_LEVEL >= 2 1104 __get_db()->__insert_c(this); 1105#endif 1106 __table_.rehash(__n); 1107 insert(__first, __last); 1108} 1109 1110template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1111template <class _InputIterator> 1112unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1113 _InputIterator __first, _InputIterator __last, size_type __n, 1114 const hasher& __hf, const key_equal& __eql, const allocator_type& __a) 1115 : __table_(__hf, __eql, __a) 1116{ 1117#if _LIBCPP_DEBUG_LEVEL >= 2 1118 __get_db()->__insert_c(this); 1119#endif 1120 __table_.rehash(__n); 1121 insert(__first, __last); 1122} 1123 1124template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1125unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1126 const unordered_map& __u) 1127 : __table_(__u.__table_) 1128{ 1129#if _LIBCPP_DEBUG_LEVEL >= 2 1130 __get_db()->__insert_c(this); 1131#endif 1132 __table_.rehash(__u.bucket_count()); 1133 insert(__u.begin(), __u.end()); 1134} 1135 1136template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1137unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1138 const unordered_map& __u, const allocator_type& __a) 1139 : __table_(__u.__table_, __a) 1140{ 1141#if _LIBCPP_DEBUG_LEVEL >= 2 1142 __get_db()->__insert_c(this); 1143#endif 1144 __table_.rehash(__u.bucket_count()); 1145 insert(__u.begin(), __u.end()); 1146} 1147 1148#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1149 1150template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1151inline _LIBCPP_INLINE_VISIBILITY 1152unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1153 unordered_map&& __u) 1154 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value) 1155 : __table_(_VSTD::move(__u.__table_)) 1156{ 1157#if _LIBCPP_DEBUG_LEVEL >= 2 1158 __get_db()->__insert_c(this); 1159 __get_db()->swap(this, &__u); 1160#endif 1161} 1162 1163template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1164unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1165 unordered_map&& __u, const allocator_type& __a) 1166 : __table_(_VSTD::move(__u.__table_), __a) 1167{ 1168#if _LIBCPP_DEBUG_LEVEL >= 2 1169 __get_db()->__insert_c(this); 1170#endif 1171 if (__a != __u.get_allocator()) 1172 { 1173 iterator __i = __u.begin(); 1174 while (__u.size() != 0) 1175 __table_.__insert_unique( 1176 _VSTD::move(__u.__table_.remove((__i++).__i_)->__value_) 1177 ); 1178 } 1179#if _LIBCPP_DEBUG_LEVEL >= 2 1180 else 1181 __get_db()->swap(this, &__u); 1182#endif 1183} 1184 1185#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1186 1187#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1188 1189template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1190unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1191 initializer_list<value_type> __il) 1192{ 1193#if _LIBCPP_DEBUG_LEVEL >= 2 1194 __get_db()->__insert_c(this); 1195#endif 1196 insert(__il.begin(), __il.end()); 1197} 1198 1199template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1200unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1201 initializer_list<value_type> __il, size_type __n, const hasher& __hf, 1202 const key_equal& __eql) 1203 : __table_(__hf, __eql) 1204{ 1205#if _LIBCPP_DEBUG_LEVEL >= 2 1206 __get_db()->__insert_c(this); 1207#endif 1208 __table_.rehash(__n); 1209 insert(__il.begin(), __il.end()); 1210} 1211 1212template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1213unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1214 initializer_list<value_type> __il, size_type __n, const hasher& __hf, 1215 const key_equal& __eql, const allocator_type& __a) 1216 : __table_(__hf, __eql, __a) 1217{ 1218#if _LIBCPP_DEBUG_LEVEL >= 2 1219 __get_db()->__insert_c(this); 1220#endif 1221 __table_.rehash(__n); 1222 insert(__il.begin(), __il.end()); 1223} 1224 1225#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1226 1227#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1228 1229template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1230inline _LIBCPP_INLINE_VISIBILITY 1231unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& 1232unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(unordered_map&& __u) 1233 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value) 1234{ 1235 __table_ = _VSTD::move(__u.__table_); 1236 return *this; 1237} 1238 1239#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1240 1241#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1242 1243template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1244inline _LIBCPP_INLINE_VISIBILITY 1245unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& 1246unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=( 1247 initializer_list<value_type> __il) 1248{ 1249 __table_.__assign_unique(__il.begin(), __il.end()); 1250 return *this; 1251} 1252 1253#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1254 1255#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1256 1257template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1258typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder 1259unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node() 1260{ 1261 __node_allocator& __na = __table_.__node_alloc(); 1262 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 1263 __node_traits::construct(__na, _VSTD::addressof(__h->__value_)); 1264 __h.get_deleter().__first_constructed = true; 1265 __h.get_deleter().__second_constructed = true; 1266 return __h; 1267} 1268 1269template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1270template <class _A0> 1271typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder 1272unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(_A0&& __a0) 1273{ 1274 __node_allocator& __na = __table_.__node_alloc(); 1275 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 1276 __node_traits::construct(__na, _VSTD::addressof(__h->__value_), 1277 _VSTD::forward<_A0>(__a0)); 1278 __h.get_deleter().__first_constructed = true; 1279 __h.get_deleter().__second_constructed = true; 1280 return __h; 1281} 1282 1283template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1284typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder 1285unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node_with_key(key_type&& __k) 1286{ 1287 __node_allocator& __na = __table_.__node_alloc(); 1288 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 1289 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.first), _VSTD::move(__k)); 1290 __h.get_deleter().__first_constructed = true; 1291 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.second)); 1292 __h.get_deleter().__second_constructed = true; 1293 return __h; 1294} 1295 1296#ifndef _LIBCPP_HAS_NO_VARIADICS 1297 1298template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1299template <class _A0, class _A1, class ..._Args> 1300typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder 1301unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(_A0&& __a0, 1302 _A1&& __a1, 1303 _Args&&... __args) 1304{ 1305 __node_allocator& __na = __table_.__node_alloc(); 1306 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 1307 __node_traits::construct(__na, _VSTD::addressof(__h->__value_), 1308 _VSTD::forward<_A0>(__a0), _VSTD::forward<_A1>(__a1), 1309 _VSTD::forward<_Args>(__args)...); 1310 __h.get_deleter().__first_constructed = true; 1311 __h.get_deleter().__second_constructed = true; 1312 return __h; 1313} 1314 1315template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1316template <class... _Args> 1317pair<typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::iterator, bool> 1318unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::emplace(_Args&&... __args) 1319{ 1320 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); 1321 pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get()); 1322 if (__r.second) 1323 __h.release(); 1324 return __r; 1325} 1326 1327#endif // _LIBCPP_HAS_NO_VARIADICS 1328#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1329 1330template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1331typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder 1332unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node_with_key(const key_type& __k) 1333{ 1334 __node_allocator& __na = __table_.__node_alloc(); 1335 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 1336 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.first), __k); 1337 __h.get_deleter().__first_constructed = true; 1338 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.second)); 1339 __h.get_deleter().__second_constructed = true; 1340 return _VSTD::move(__h); // explicitly moved for C++03 1341} 1342 1343template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1344template <class _InputIterator> 1345inline _LIBCPP_INLINE_VISIBILITY 1346void 1347unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, 1348 _InputIterator __last) 1349{ 1350 for (; __first != __last; ++__first) 1351 __table_.__insert_unique(*__first); 1352} 1353 1354template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1355_Tp& 1356unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](const key_type& __k) 1357{ 1358 iterator __i = find(__k); 1359 if (__i != end()) 1360 return __i->second; 1361 __node_holder __h = __construct_node_with_key(__k); 1362 pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get()); 1363 __h.release(); 1364 return __r.first->second; 1365} 1366 1367#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1368 1369template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1370_Tp& 1371unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](key_type&& __k) 1372{ 1373 iterator __i = find(__k); 1374 if (__i != end()) 1375 return __i->second; 1376 __node_holder __h = __construct_node_with_key(_VSTD::move(__k)); 1377 pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get()); 1378 __h.release(); 1379 return __r.first->second; 1380} 1381 1382#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1383 1384template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1385_Tp& 1386unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::at(const key_type& __k) 1387{ 1388 iterator __i = find(__k); 1389#ifndef _LIBCPP_NO_EXCEPTIONS 1390 if (__i == end()) 1391 throw out_of_range("unordered_map::at: key not found"); 1392#endif // _LIBCPP_NO_EXCEPTIONS 1393 return __i->second; 1394} 1395 1396template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1397const _Tp& 1398unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::at(const key_type& __k) const 1399{ 1400 const_iterator __i = find(__k); 1401#ifndef _LIBCPP_NO_EXCEPTIONS 1402 if (__i == end()) 1403 throw out_of_range("unordered_map::at: key not found"); 1404#endif // _LIBCPP_NO_EXCEPTIONS 1405 return __i->second; 1406} 1407 1408template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1409inline _LIBCPP_INLINE_VISIBILITY 1410void 1411swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 1412 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 1413 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 1414{ 1415 __x.swap(__y); 1416} 1417 1418template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1419bool 1420operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 1421 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 1422{ 1423 if (__x.size() != __y.size()) 1424 return false; 1425 typedef typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator 1426 const_iterator; 1427 for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end(); 1428 __i != __ex; ++__i) 1429 { 1430 const_iterator __j = __y.find(__i->first); 1431 if (__j == __ey || !(*__i == *__j)) 1432 return false; 1433 } 1434 return true; 1435} 1436 1437template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1438inline _LIBCPP_INLINE_VISIBILITY 1439bool 1440operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 1441 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 1442{ 1443 return !(__x == __y); 1444} 1445 1446template <class _Key, class _Tp, class _Hash = hash<_Key>, class _Pred = equal_to<_Key>, 1447 class _Alloc = allocator<pair<const _Key, _Tp> > > 1448class _LIBCPP_TYPE_VIS_ONLY unordered_multimap 1449{ 1450public: 1451 // types 1452 typedef _Key key_type; 1453 typedef _Tp mapped_type; 1454 typedef _Hash hasher; 1455 typedef _Pred key_equal; 1456 typedef _Alloc allocator_type; 1457 typedef pair<const key_type, mapped_type> value_type; 1458 typedef pair<key_type, mapped_type> __nc_value_type; 1459 typedef value_type& reference; 1460 typedef const value_type& const_reference; 1461 static_assert((is_same<value_type, typename allocator_type::value_type>::value), 1462 "Invalid allocator::value_type"); 1463 1464private: 1465 typedef __hash_value_type<key_type, mapped_type> __value_type; 1466 typedef __unordered_map_hasher<key_type, __value_type, hasher> __hasher; 1467 typedef __unordered_map_equal<key_type, __value_type, key_equal> __key_equal; 1468 typedef typename allocator_traits<allocator_type>::template 1469#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 1470 rebind_alloc<__value_type> 1471#else 1472 rebind_alloc<__value_type>::other 1473#endif 1474 __allocator_type; 1475 1476 typedef __hash_table<__value_type, __hasher, 1477 __key_equal, __allocator_type> __table; 1478 1479 __table __table_; 1480 1481 typedef typename __table::__node_traits __node_traits; 1482 typedef typename __table::__node_allocator __node_allocator; 1483 typedef typename __table::__node __node; 1484 typedef __hash_map_node_destructor<__node_allocator> _Dp; 1485 typedef unique_ptr<__node, _Dp> __node_holder; 1486 typedef allocator_traits<allocator_type> __alloc_traits; 1487public: 1488 typedef typename __alloc_traits::pointer pointer; 1489 typedef typename __alloc_traits::const_pointer const_pointer; 1490 typedef typename __alloc_traits::size_type size_type; 1491 typedef typename __alloc_traits::difference_type difference_type; 1492 1493 typedef __hash_map_iterator<typename __table::iterator> iterator; 1494 typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator; 1495 typedef __hash_map_iterator<typename __table::local_iterator> local_iterator; 1496 typedef __hash_map_const_iterator<typename __table::const_local_iterator> const_local_iterator; 1497 1498 _LIBCPP_INLINE_VISIBILITY 1499 unordered_multimap() 1500 _NOEXCEPT_(is_nothrow_default_constructible<__table>::value) 1501 { 1502#if _LIBCPP_DEBUG_LEVEL >= 2 1503 __get_db()->__insert_c(this); 1504#endif 1505 } 1506 explicit unordered_multimap(size_type __n, const hasher& __hf = hasher(), 1507 const key_equal& __eql = key_equal()); 1508 unordered_multimap(size_type __n, const hasher& __hf, 1509 const key_equal& __eql, 1510 const allocator_type& __a); 1511 template <class _InputIterator> 1512 unordered_multimap(_InputIterator __first, _InputIterator __last); 1513 template <class _InputIterator> 1514 unordered_multimap(_InputIterator __first, _InputIterator __last, 1515 size_type __n, const hasher& __hf = hasher(), 1516 const key_equal& __eql = key_equal()); 1517 template <class _InputIterator> 1518 unordered_multimap(_InputIterator __first, _InputIterator __last, 1519 size_type __n, const hasher& __hf, 1520 const key_equal& __eql, 1521 const allocator_type& __a); 1522 explicit unordered_multimap(const allocator_type& __a); 1523 unordered_multimap(const unordered_multimap& __u); 1524 unordered_multimap(const unordered_multimap& __u, const allocator_type& __a); 1525#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1526 unordered_multimap(unordered_multimap&& __u) 1527 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value); 1528 unordered_multimap(unordered_multimap&& __u, const allocator_type& __a); 1529#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1530#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1531 unordered_multimap(initializer_list<value_type> __il); 1532 unordered_multimap(initializer_list<value_type> __il, size_type __n, 1533 const hasher& __hf = hasher(), 1534 const key_equal& __eql = key_equal()); 1535 unordered_multimap(initializer_list<value_type> __il, size_type __n, 1536 const hasher& __hf, const key_equal& __eql, 1537 const allocator_type& __a); 1538#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1539#if _LIBCPP_STD_VER > 11 1540 _LIBCPP_INLINE_VISIBILITY 1541 unordered_multimap(size_type __n, const allocator_type& __a) 1542 : unordered_multimap(__n, hasher(), key_equal(), __a) {} 1543 _LIBCPP_INLINE_VISIBILITY 1544 unordered_multimap(size_type __n, const hasher& __hf, const allocator_type& __a) 1545 : unordered_multimap(__n, __hf, key_equal(), __a) {} 1546 template <class _InputIterator> 1547 _LIBCPP_INLINE_VISIBILITY 1548 unordered_multimap(_InputIterator __first, _InputIterator __last, size_type __n, const allocator_type& __a) 1549 : unordered_multimap(__first, __last, __n, hasher(), key_equal(), __a) {} 1550 template <class _InputIterator> 1551 _LIBCPP_INLINE_VISIBILITY 1552 unordered_multimap(_InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, 1553 const allocator_type& __a) 1554 : unordered_multimap(__first, __last, __n, __hf, key_equal(), __a) {} 1555 _LIBCPP_INLINE_VISIBILITY 1556 unordered_multimap(initializer_list<value_type> __il, size_type __n, const allocator_type& __a) 1557 : unordered_multimap(__il, __n, hasher(), key_equal(), __a) {} 1558 _LIBCPP_INLINE_VISIBILITY 1559 unordered_multimap(initializer_list<value_type> __il, size_type __n, const hasher& __hf, 1560 const allocator_type& __a) 1561 : unordered_multimap(__il, __n, __hf, key_equal(), __a) {} 1562#endif 1563 // ~unordered_multimap() = default; 1564 _LIBCPP_INLINE_VISIBILITY 1565 unordered_multimap& operator=(const unordered_multimap& __u) 1566 { 1567#if __cplusplus >= 201103L 1568 __table_ = __u.__table_; 1569#else 1570 __table_.clear(); 1571 __table_.hash_function() = __u.__table_.hash_function(); 1572 __table_.key_eq() = __u.__table_.key_eq(); 1573 __table_.max_load_factor() = __u.__table_.max_load_factor(); 1574 __table_.__copy_assign_alloc(__u.__table_); 1575 insert(__u.begin(), __u.end()); 1576#endif 1577 return *this; 1578 } 1579#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1580 unordered_multimap& operator=(unordered_multimap&& __u) 1581 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value); 1582#endif 1583#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1584 unordered_multimap& operator=(initializer_list<value_type> __il); 1585#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1586 1587 _LIBCPP_INLINE_VISIBILITY 1588 allocator_type get_allocator() const _NOEXCEPT 1589 {return allocator_type(__table_.__node_alloc());} 1590 1591 _LIBCPP_INLINE_VISIBILITY 1592 bool empty() const _NOEXCEPT {return __table_.size() == 0;} 1593 _LIBCPP_INLINE_VISIBILITY 1594 size_type size() const _NOEXCEPT {return __table_.size();} 1595 _LIBCPP_INLINE_VISIBILITY 1596 size_type max_size() const _NOEXCEPT {return __table_.max_size();} 1597 1598 _LIBCPP_INLINE_VISIBILITY 1599 iterator begin() _NOEXCEPT {return __table_.begin();} 1600 _LIBCPP_INLINE_VISIBILITY 1601 iterator end() _NOEXCEPT {return __table_.end();} 1602 _LIBCPP_INLINE_VISIBILITY 1603 const_iterator begin() const _NOEXCEPT {return __table_.begin();} 1604 _LIBCPP_INLINE_VISIBILITY 1605 const_iterator end() const _NOEXCEPT {return __table_.end();} 1606 _LIBCPP_INLINE_VISIBILITY 1607 const_iterator cbegin() const _NOEXCEPT {return __table_.begin();} 1608 _LIBCPP_INLINE_VISIBILITY 1609 const_iterator cend() const _NOEXCEPT {return __table_.end();} 1610 1611#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1612#ifndef _LIBCPP_HAS_NO_VARIADICS 1613 1614 template <class... _Args> 1615 iterator emplace(_Args&&... __args); 1616 1617 template <class... _Args> 1618 iterator emplace_hint(const_iterator __p, _Args&&... __args); 1619#endif // _LIBCPP_HAS_NO_VARIADICS 1620#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1621 _LIBCPP_INLINE_VISIBILITY 1622 iterator insert(const value_type& __x) {return __table_.__insert_multi(__x);} 1623#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1624 template <class _Pp, 1625 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type> 1626 _LIBCPP_INLINE_VISIBILITY 1627 iterator insert(_Pp&& __x) 1628 {return __table_.__insert_multi(_VSTD::forward<_Pp>(__x));} 1629#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1630 _LIBCPP_INLINE_VISIBILITY 1631 iterator insert(const_iterator __p, const value_type& __x) 1632 {return __table_.__insert_multi(__p.__i_, __x);} 1633#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1634 template <class _Pp, 1635 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type> 1636 _LIBCPP_INLINE_VISIBILITY 1637 iterator insert(const_iterator __p, _Pp&& __x) 1638 {return __table_.__insert_multi(__p.__i_, _VSTD::forward<_Pp>(__x));} 1639#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1640 template <class _InputIterator> 1641 void insert(_InputIterator __first, _InputIterator __last); 1642#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1643 _LIBCPP_INLINE_VISIBILITY 1644 void insert(initializer_list<value_type> __il) 1645 {insert(__il.begin(), __il.end());} 1646#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1647 1648 _LIBCPP_INLINE_VISIBILITY 1649 iterator erase(const_iterator __p) {return __table_.erase(__p.__i_);} 1650 _LIBCPP_INLINE_VISIBILITY 1651 size_type erase(const key_type& __k) {return __table_.__erase_multi(__k);} 1652 _LIBCPP_INLINE_VISIBILITY 1653 iterator erase(const_iterator __first, const_iterator __last) 1654 {return __table_.erase(__first.__i_, __last.__i_);} 1655 _LIBCPP_INLINE_VISIBILITY 1656 void clear() _NOEXCEPT {__table_.clear();} 1657 1658 _LIBCPP_INLINE_VISIBILITY 1659 void swap(unordered_multimap& __u) 1660 _NOEXCEPT_(__is_nothrow_swappable<__table>::value) 1661 {__table_.swap(__u.__table_);} 1662 1663 _LIBCPP_INLINE_VISIBILITY 1664 hasher hash_function() const 1665 {return __table_.hash_function().hash_function();} 1666 _LIBCPP_INLINE_VISIBILITY 1667 key_equal key_eq() const 1668 {return __table_.key_eq().key_eq();} 1669 1670 _LIBCPP_INLINE_VISIBILITY 1671 iterator find(const key_type& __k) {return __table_.find(__k);} 1672 _LIBCPP_INLINE_VISIBILITY 1673 const_iterator find(const key_type& __k) const {return __table_.find(__k);} 1674 _LIBCPP_INLINE_VISIBILITY 1675 size_type count(const key_type& __k) const {return __table_.__count_multi(__k);} 1676 _LIBCPP_INLINE_VISIBILITY 1677 pair<iterator, iterator> equal_range(const key_type& __k) 1678 {return __table_.__equal_range_multi(__k);} 1679 _LIBCPP_INLINE_VISIBILITY 1680 pair<const_iterator, const_iterator> equal_range(const key_type& __k) const 1681 {return __table_.__equal_range_multi(__k);} 1682 1683 _LIBCPP_INLINE_VISIBILITY 1684 size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();} 1685 _LIBCPP_INLINE_VISIBILITY 1686 size_type max_bucket_count() const _NOEXCEPT 1687 {return __table_.max_bucket_count();} 1688 1689 _LIBCPP_INLINE_VISIBILITY 1690 size_type bucket_size(size_type __n) const 1691 {return __table_.bucket_size(__n);} 1692 _LIBCPP_INLINE_VISIBILITY 1693 size_type bucket(const key_type& __k) const {return __table_.bucket(__k);} 1694 1695 _LIBCPP_INLINE_VISIBILITY 1696 local_iterator begin(size_type __n) {return __table_.begin(__n);} 1697 _LIBCPP_INLINE_VISIBILITY 1698 local_iterator end(size_type __n) {return __table_.end(__n);} 1699 _LIBCPP_INLINE_VISIBILITY 1700 const_local_iterator begin(size_type __n) const {return __table_.cbegin(__n);} 1701 _LIBCPP_INLINE_VISIBILITY 1702 const_local_iterator end(size_type __n) const {return __table_.cend(__n);} 1703 _LIBCPP_INLINE_VISIBILITY 1704 const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);} 1705 _LIBCPP_INLINE_VISIBILITY 1706 const_local_iterator cend(size_type __n) const {return __table_.cend(__n);} 1707 1708 _LIBCPP_INLINE_VISIBILITY 1709 float load_factor() const _NOEXCEPT {return __table_.load_factor();} 1710 _LIBCPP_INLINE_VISIBILITY 1711 float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();} 1712 _LIBCPP_INLINE_VISIBILITY 1713 void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);} 1714 _LIBCPP_INLINE_VISIBILITY 1715 void rehash(size_type __n) {__table_.rehash(__n);} 1716 _LIBCPP_INLINE_VISIBILITY 1717 void reserve(size_type __n) {__table_.reserve(__n);} 1718 1719#if _LIBCPP_DEBUG_LEVEL >= 2 1720 1721 bool __dereferenceable(const const_iterator* __i) const 1722 {return __table_.__dereferenceable(&__i->__i_);} 1723 bool __decrementable(const const_iterator* __i) const 1724 {return __table_.__decrementable(&__i->__i_);} 1725 bool __addable(const const_iterator* __i, ptrdiff_t __n) const 1726 {return __table_.__addable(&__i->__i_, __n);} 1727 bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const 1728 {return __table_.__addable(&__i->__i_, __n);} 1729 1730#endif // _LIBCPP_DEBUG_LEVEL >= 2 1731 1732private: 1733#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1734 __node_holder __construct_node(); 1735 template <class _A0> 1736 __node_holder 1737 __construct_node(_A0&& __a0); 1738#ifndef _LIBCPP_HAS_NO_VARIADICS 1739 template <class _A0, class _A1, class ..._Args> 1740 __node_holder __construct_node(_A0&& __a0, _A1&& __a1, _Args&& ...__args); 1741#endif // _LIBCPP_HAS_NO_VARIADICS 1742#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1743}; 1744 1745template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1746unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1747 size_type __n, const hasher& __hf, const key_equal& __eql) 1748 : __table_(__hf, __eql) 1749{ 1750#if _LIBCPP_DEBUG_LEVEL >= 2 1751 __get_db()->__insert_c(this); 1752#endif 1753 __table_.rehash(__n); 1754} 1755 1756template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1757unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1758 size_type __n, const hasher& __hf, const key_equal& __eql, 1759 const allocator_type& __a) 1760 : __table_(__hf, __eql, __a) 1761{ 1762#if _LIBCPP_DEBUG_LEVEL >= 2 1763 __get_db()->__insert_c(this); 1764#endif 1765 __table_.rehash(__n); 1766} 1767 1768template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1769template <class _InputIterator> 1770unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1771 _InputIterator __first, _InputIterator __last) 1772{ 1773#if _LIBCPP_DEBUG_LEVEL >= 2 1774 __get_db()->__insert_c(this); 1775#endif 1776 insert(__first, __last); 1777} 1778 1779template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1780template <class _InputIterator> 1781unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1782 _InputIterator __first, _InputIterator __last, size_type __n, 1783 const hasher& __hf, const key_equal& __eql) 1784 : __table_(__hf, __eql) 1785{ 1786#if _LIBCPP_DEBUG_LEVEL >= 2 1787 __get_db()->__insert_c(this); 1788#endif 1789 __table_.rehash(__n); 1790 insert(__first, __last); 1791} 1792 1793template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1794template <class _InputIterator> 1795unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1796 _InputIterator __first, _InputIterator __last, size_type __n, 1797 const hasher& __hf, const key_equal& __eql, const allocator_type& __a) 1798 : __table_(__hf, __eql, __a) 1799{ 1800#if _LIBCPP_DEBUG_LEVEL >= 2 1801 __get_db()->__insert_c(this); 1802#endif 1803 __table_.rehash(__n); 1804 insert(__first, __last); 1805} 1806 1807template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1808inline _LIBCPP_INLINE_VISIBILITY 1809unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1810 const allocator_type& __a) 1811 : __table_(__a) 1812{ 1813#if _LIBCPP_DEBUG_LEVEL >= 2 1814 __get_db()->__insert_c(this); 1815#endif 1816} 1817 1818template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1819unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1820 const unordered_multimap& __u) 1821 : __table_(__u.__table_) 1822{ 1823#if _LIBCPP_DEBUG_LEVEL >= 2 1824 __get_db()->__insert_c(this); 1825#endif 1826 __table_.rehash(__u.bucket_count()); 1827 insert(__u.begin(), __u.end()); 1828} 1829 1830template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1831unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1832 const unordered_multimap& __u, const allocator_type& __a) 1833 : __table_(__u.__table_, __a) 1834{ 1835#if _LIBCPP_DEBUG_LEVEL >= 2 1836 __get_db()->__insert_c(this); 1837#endif 1838 __table_.rehash(__u.bucket_count()); 1839 insert(__u.begin(), __u.end()); 1840} 1841 1842#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1843 1844template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1845inline _LIBCPP_INLINE_VISIBILITY 1846unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1847 unordered_multimap&& __u) 1848 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value) 1849 : __table_(_VSTD::move(__u.__table_)) 1850{ 1851#if _LIBCPP_DEBUG_LEVEL >= 2 1852 __get_db()->__insert_c(this); 1853 __get_db()->swap(this, &__u); 1854#endif 1855} 1856 1857template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1858unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1859 unordered_multimap&& __u, const allocator_type& __a) 1860 : __table_(_VSTD::move(__u.__table_), __a) 1861{ 1862#if _LIBCPP_DEBUG_LEVEL >= 2 1863 __get_db()->__insert_c(this); 1864#endif 1865 if (__a != __u.get_allocator()) 1866 { 1867 iterator __i = __u.begin(); 1868 while (__u.size() != 0) 1869 { 1870 __table_.__insert_multi( 1871 _VSTD::move(__u.__table_.remove((__i++).__i_)->__value_) 1872 ); 1873 } 1874 } 1875#if _LIBCPP_DEBUG_LEVEL >= 2 1876 else 1877 __get_db()->swap(this, &__u); 1878#endif 1879} 1880 1881#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1882 1883#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1884 1885template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1886unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1887 initializer_list<value_type> __il) 1888{ 1889#if _LIBCPP_DEBUG_LEVEL >= 2 1890 __get_db()->__insert_c(this); 1891#endif 1892 insert(__il.begin(), __il.end()); 1893} 1894 1895template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1896unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1897 initializer_list<value_type> __il, size_type __n, const hasher& __hf, 1898 const key_equal& __eql) 1899 : __table_(__hf, __eql) 1900{ 1901#if _LIBCPP_DEBUG_LEVEL >= 2 1902 __get_db()->__insert_c(this); 1903#endif 1904 __table_.rehash(__n); 1905 insert(__il.begin(), __il.end()); 1906} 1907 1908template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1909unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1910 initializer_list<value_type> __il, size_type __n, const hasher& __hf, 1911 const key_equal& __eql, const allocator_type& __a) 1912 : __table_(__hf, __eql, __a) 1913{ 1914#if _LIBCPP_DEBUG_LEVEL >= 2 1915 __get_db()->__insert_c(this); 1916#endif 1917 __table_.rehash(__n); 1918 insert(__il.begin(), __il.end()); 1919} 1920 1921#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1922 1923#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1924 1925template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1926inline _LIBCPP_INLINE_VISIBILITY 1927unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& 1928unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(unordered_multimap&& __u) 1929 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value) 1930{ 1931 __table_ = _VSTD::move(__u.__table_); 1932 return *this; 1933} 1934 1935#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1936 1937#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1938 1939template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1940inline _LIBCPP_INLINE_VISIBILITY 1941unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& 1942unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=( 1943 initializer_list<value_type> __il) 1944{ 1945 __table_.__assign_multi(__il.begin(), __il.end()); 1946 return *this; 1947} 1948 1949#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1950 1951#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1952 1953template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1954typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder 1955unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node() 1956{ 1957 __node_allocator& __na = __table_.__node_alloc(); 1958 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 1959 __node_traits::construct(__na, _VSTD::addressof(__h->__value_)); 1960 __h.get_deleter().__first_constructed = true; 1961 __h.get_deleter().__second_constructed = true; 1962 return __h; 1963} 1964 1965template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1966template <class _A0> 1967typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder 1968unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(_A0&& __a0) 1969{ 1970 __node_allocator& __na = __table_.__node_alloc(); 1971 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 1972 __node_traits::construct(__na, _VSTD::addressof(__h->__value_), 1973 _VSTD::forward<_A0>(__a0)); 1974 __h.get_deleter().__first_constructed = true; 1975 __h.get_deleter().__second_constructed = true; 1976 return __h; 1977} 1978 1979#ifndef _LIBCPP_HAS_NO_VARIADICS 1980 1981template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1982template <class _A0, class _A1, class ..._Args> 1983typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder 1984unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node( 1985 _A0&& __a0, _A1&& __a1, _Args&&... __args) 1986{ 1987 __node_allocator& __na = __table_.__node_alloc(); 1988 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 1989 __node_traits::construct(__na, _VSTD::addressof(__h->__value_), 1990 _VSTD::forward<_A0>(__a0), _VSTD::forward<_A1>(__a1), 1991 _VSTD::forward<_Args>(__args)...); 1992 __h.get_deleter().__first_constructed = true; 1993 __h.get_deleter().__second_constructed = true; 1994 return __h; 1995} 1996 1997template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1998template <class... _Args> 1999typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::iterator 2000unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::emplace(_Args&&... __args) 2001{ 2002 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); 2003 iterator __r = __table_.__node_insert_multi(__h.get()); 2004 __h.release(); 2005 return __r; 2006} 2007 2008template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2009template <class... _Args> 2010typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::iterator 2011unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::emplace_hint( 2012 const_iterator __p, _Args&&... __args) 2013{ 2014 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); 2015 iterator __r = __table_.__node_insert_multi(__p.__i_, __h.get()); 2016 __h.release(); 2017 return __r; 2018} 2019 2020#endif // _LIBCPP_HAS_NO_VARIADICS 2021#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 2022 2023template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2024template <class _InputIterator> 2025inline _LIBCPP_INLINE_VISIBILITY 2026void 2027unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, 2028 _InputIterator __last) 2029{ 2030 for (; __first != __last; ++__first) 2031 __table_.__insert_multi(*__first); 2032} 2033 2034template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2035inline _LIBCPP_INLINE_VISIBILITY 2036void 2037swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 2038 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 2039 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 2040{ 2041 __x.swap(__y); 2042} 2043 2044template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2045bool 2046operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 2047 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 2048{ 2049 if (__x.size() != __y.size()) 2050 return false; 2051 typedef typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator 2052 const_iterator; 2053 typedef pair<const_iterator, const_iterator> _EqRng; 2054 for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;) 2055 { 2056 _EqRng __xeq = __x.equal_range(__i->first); 2057 _EqRng __yeq = __y.equal_range(__i->first); 2058 if (_VSTD::distance(__xeq.first, __xeq.second) != 2059 _VSTD::distance(__yeq.first, __yeq.second) || 2060 !_VSTD::is_permutation(__xeq.first, __xeq.second, __yeq.first)) 2061 return false; 2062 __i = __xeq.second; 2063 } 2064 return true; 2065} 2066 2067template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2068inline _LIBCPP_INLINE_VISIBILITY 2069bool 2070operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 2071 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 2072{ 2073 return !(__x == __y); 2074} 2075 2076_LIBCPP_END_NAMESPACE_STD 2077 2078#endif // _LIBCPP_UNORDERED_MAP 2079