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