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