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