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_TYPE_VIS_ONLY __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_TYPE_VIS_ONLY unordered_map; 686 template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY unordered_multimap; 687 template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_const_iterator; 688 template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_const_local_iterator; 689 template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_map_const_iterator; 690}; 691 692template <class _HashIterator> 693class _LIBCPP_TYPE_VIS_ONLY __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_TYPE_VIS_ONLY unordered_map; 740 template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY unordered_multimap; 741 template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_const_iterator; 742 template <class> friend class _LIBCPP_TYPE_VIS_ONLY __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_TYPE_VIS_ONLY 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#endif 926 return insert(__x).first; 927 } 928 929 template <class _InputIterator> 930 _LIBCPP_INLINE_VISIBILITY 931 void insert(_InputIterator __first, _InputIterator __last); 932 933#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 934 _LIBCPP_INLINE_VISIBILITY 935 void insert(initializer_list<value_type> __il) 936 {insert(__il.begin(), __il.end());} 937#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 938 939#ifndef _LIBCPP_CXX03_LANG 940 _LIBCPP_INLINE_VISIBILITY 941 pair<iterator, bool> insert(value_type&& __x) 942 {return __table_.__insert_unique(_VSTD::move(__x));} 943 944 iterator insert(const_iterator __p, value_type&& __x) { 945#if _LIBCPP_DEBUG_LEVEL >= 2 946 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 947 "unordered_map::insert(const_iterator, const value_type&) called with an iterator not" 948 " referring to this unordered_map"); 949#endif 950 return __table_.__insert_unique(_VSTD::move(__x)).first; 951 } 952 953 template <class _Pp, 954 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type> 955 _LIBCPP_INLINE_VISIBILITY 956 pair<iterator, bool> insert(_Pp&& __x) 957 {return __table_.__insert_unique(_VSTD::forward<_Pp>(__x));} 958 959 template <class _Pp, 960 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type> 961 _LIBCPP_INLINE_VISIBILITY 962 iterator insert(const_iterator __p, _Pp&& __x) 963 { 964#if _LIBCPP_DEBUG_LEVEL >= 2 965 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 966 "unordered_map::insert(const_iterator, value_type&&) called with an iterator not" 967 " referring to this unordered_map"); 968#endif 969 return insert(_VSTD::forward<_Pp>(__x)).first; 970 } 971 972 template <class... _Args> 973 _LIBCPP_INLINE_VISIBILITY 974 pair<iterator, bool> emplace(_Args&&... __args) { 975 return __table_.__emplace_unique(_VSTD::forward<_Args>(__args)...); 976 } 977 978 template <class... _Args> 979 _LIBCPP_INLINE_VISIBILITY 980 iterator emplace_hint(const_iterator __p, _Args&&... __args) { 981#if _LIBCPP_DEBUG_LEVEL >= 2 982 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 983 "unordered_map::emplace_hint(const_iterator, args...) called with an iterator not" 984 " referring to this unordered_map"); 985#endif 986 return __table_.__emplace_unique(_VSTD::forward<_Args>(__args)...).first; 987 } 988 989#endif // _LIBCPP_CXX03_LANG 990 991#if _LIBCPP_STD_VER > 14 992 template <class... _Args> 993 _LIBCPP_INLINE_VISIBILITY 994 pair<iterator, bool> try_emplace(const key_type& __k, _Args&&... __args) 995 { 996 return __table_.__emplace_unique_key_args(__k, _VSTD::piecewise_construct, 997 _VSTD::forward_as_tuple(__k), 998 _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...)); 999 } 1000 1001 template <class... _Args> 1002 _LIBCPP_INLINE_VISIBILITY 1003 pair<iterator, bool> try_emplace(key_type&& __k, _Args&&... __args) 1004 { 1005 return __table_.__emplace_unique_key_args(__k, _VSTD::piecewise_construct, 1006 _VSTD::forward_as_tuple(_VSTD::move(__k)), 1007 _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...)); 1008 } 1009 1010 template <class... _Args> 1011 _LIBCPP_INLINE_VISIBILITY 1012 iterator try_emplace(const_iterator __h, const key_type& __k, _Args&&... __args) 1013 { 1014#if _LIBCPP_DEBUG_LEVEL >= 2 1015 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 1016 "unordered_map::try_emplace(const_iterator, key, args...) called with an iterator not" 1017 " referring to this unordered_map"); 1018#endif 1019 return try_emplace(__k, _VSTD::forward<_Args>(__args)...).first; 1020 } 1021 1022 template <class... _Args> 1023 _LIBCPP_INLINE_VISIBILITY 1024 iterator try_emplace(const_iterator __h, key_type&& __k, _Args&&... __args) 1025 { 1026#if _LIBCPP_DEBUG_LEVEL >= 2 1027 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 1028 "unordered_map::try_emplace(const_iterator, key, args...) called with an iterator not" 1029 " referring to this unordered_map"); 1030#endif 1031 return try_emplace(_VSTD::move(__k), _VSTD::forward<_Args>(__args)...).first; 1032 } 1033 1034 template <class _Vp> 1035 _LIBCPP_INLINE_VISIBILITY 1036 pair<iterator, bool> insert_or_assign(const key_type& __k, _Vp&& __v) 1037 { 1038 pair<iterator, bool> __res = __table_.__emplace_unique_key_args(__k, 1039 __k, _VSTD::forward<_Vp>(__v)); 1040 if (!__res.second) { 1041 __res.first->second = _VSTD::forward<_Vp>(__v); 1042 } 1043 return __res; 1044 } 1045 1046 template <class _Vp> 1047 _LIBCPP_INLINE_VISIBILITY 1048 pair<iterator, bool> insert_or_assign(key_type&& __k, _Vp&& __v) 1049 { 1050 pair<iterator, bool> __res = __table_.__emplace_unique_key_args(__k, 1051 _VSTD::move(__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 iterator insert_or_assign(const_iterator __h, const key_type& __k, _Vp&& __v) 1061 { 1062 return insert_or_assign(__k, _VSTD::forward<_Vp>(__v)).first; 1063 } 1064 1065 template <class _Vp> 1066 _LIBCPP_INLINE_VISIBILITY 1067 iterator insert_or_assign(const_iterator __h, key_type&& __k, _Vp&& __v) 1068 { 1069 return insert_or_assign(_VSTD::move(__k), _VSTD::forward<_Vp>(__v)).first; 1070 } 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_CXX03_LANG 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 1168#ifdef _LIBCPP_CXX03_LANG 1169 __node_holder __construct_node_with_key(const key_type& __k); 1170#endif 1171}; 1172 1173template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1174unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1175 size_type __n, const hasher& __hf, const key_equal& __eql) 1176 : __table_(__hf, __eql) 1177{ 1178#if _LIBCPP_DEBUG_LEVEL >= 2 1179 __get_db()->__insert_c(this); 1180#endif 1181 __table_.rehash(__n); 1182} 1183 1184template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1185unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1186 size_type __n, const hasher& __hf, const key_equal& __eql, 1187 const allocator_type& __a) 1188 : __table_(__hf, __eql, typename __table::allocator_type(__a)) 1189{ 1190#if _LIBCPP_DEBUG_LEVEL >= 2 1191 __get_db()->__insert_c(this); 1192#endif 1193 __table_.rehash(__n); 1194} 1195 1196template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1197inline 1198unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1199 const allocator_type& __a) 1200 : __table_(typename __table::allocator_type(__a)) 1201{ 1202#if _LIBCPP_DEBUG_LEVEL >= 2 1203 __get_db()->__insert_c(this); 1204#endif 1205} 1206 1207template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1208template <class _InputIterator> 1209unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1210 _InputIterator __first, _InputIterator __last) 1211{ 1212#if _LIBCPP_DEBUG_LEVEL >= 2 1213 __get_db()->__insert_c(this); 1214#endif 1215 insert(__first, __last); 1216} 1217 1218template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1219template <class _InputIterator> 1220unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1221 _InputIterator __first, _InputIterator __last, size_type __n, 1222 const hasher& __hf, const key_equal& __eql) 1223 : __table_(__hf, __eql) 1224{ 1225#if _LIBCPP_DEBUG_LEVEL >= 2 1226 __get_db()->__insert_c(this); 1227#endif 1228 __table_.rehash(__n); 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, const allocator_type& __a) 1237 : __table_(__hf, __eql, typename __table::allocator_type(__a)) 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> 1247unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1248 const unordered_map& __u) 1249 : __table_(__u.__table_) 1250{ 1251#if _LIBCPP_DEBUG_LEVEL >= 2 1252 __get_db()->__insert_c(this); 1253#endif 1254 __table_.rehash(__u.bucket_count()); 1255 insert(__u.begin(), __u.end()); 1256} 1257 1258template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1259unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1260 const unordered_map& __u, const allocator_type& __a) 1261 : __table_(__u.__table_, typename __table::allocator_type(__a)) 1262{ 1263#if _LIBCPP_DEBUG_LEVEL >= 2 1264 __get_db()->__insert_c(this); 1265#endif 1266 __table_.rehash(__u.bucket_count()); 1267 insert(__u.begin(), __u.end()); 1268} 1269 1270#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1271 1272template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1273inline 1274unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1275 unordered_map&& __u) 1276 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value) 1277 : __table_(_VSTD::move(__u.__table_)) 1278{ 1279#if _LIBCPP_DEBUG_LEVEL >= 2 1280 __get_db()->__insert_c(this); 1281 __get_db()->swap(this, &__u); 1282#endif 1283} 1284 1285template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1286unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1287 unordered_map&& __u, const allocator_type& __a) 1288 : __table_(_VSTD::move(__u.__table_), typename __table::allocator_type(__a)) 1289{ 1290#if _LIBCPP_DEBUG_LEVEL >= 2 1291 __get_db()->__insert_c(this); 1292#endif 1293 if (__a != __u.get_allocator()) 1294 { 1295 iterator __i = __u.begin(); 1296 while (__u.size() != 0) { 1297 __table_.__emplace_unique(_VSTD::move( 1298 __u.__table_.remove((__i++).__i_)->__value_.__nc)); 1299 } 1300 } 1301#if _LIBCPP_DEBUG_LEVEL >= 2 1302 else 1303 __get_db()->swap(this, &__u); 1304#endif 1305} 1306 1307#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1308 1309#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1310 1311template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1312unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1313 initializer_list<value_type> __il) 1314{ 1315#if _LIBCPP_DEBUG_LEVEL >= 2 1316 __get_db()->__insert_c(this); 1317#endif 1318 insert(__il.begin(), __il.end()); 1319} 1320 1321template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1322unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1323 initializer_list<value_type> __il, size_type __n, const hasher& __hf, 1324 const key_equal& __eql) 1325 : __table_(__hf, __eql) 1326{ 1327#if _LIBCPP_DEBUG_LEVEL >= 2 1328 __get_db()->__insert_c(this); 1329#endif 1330 __table_.rehash(__n); 1331 insert(__il.begin(), __il.end()); 1332} 1333 1334template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1335unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( 1336 initializer_list<value_type> __il, size_type __n, const hasher& __hf, 1337 const key_equal& __eql, const allocator_type& __a) 1338 : __table_(__hf, __eql, typename __table::allocator_type(__a)) 1339{ 1340#if _LIBCPP_DEBUG_LEVEL >= 2 1341 __get_db()->__insert_c(this); 1342#endif 1343 __table_.rehash(__n); 1344 insert(__il.begin(), __il.end()); 1345} 1346 1347#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1348 1349#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1350 1351template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1352inline 1353unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& 1354unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(unordered_map&& __u) 1355 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value) 1356{ 1357 __table_ = _VSTD::move(__u.__table_); 1358 return *this; 1359} 1360 1361#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1362 1363#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 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=( 1369 initializer_list<value_type> __il) 1370{ 1371 __table_.__assign_unique(__il.begin(), __il.end()); 1372 return *this; 1373} 1374 1375#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1376 1377#ifdef _LIBCPP_CXX03_LANG 1378template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1379typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder 1380unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node_with_key(const key_type& __k) 1381{ 1382 __node_allocator& __na = __table_.__node_alloc(); 1383 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 1384 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.first), __k); 1385 __h.get_deleter().__first_constructed = true; 1386 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.second)); 1387 __h.get_deleter().__second_constructed = true; 1388 return _LIBCPP_EXPLICIT_MOVE(__h); // explicitly moved for C++03 1389} 1390#endif 1391 1392template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1393template <class _InputIterator> 1394inline 1395void 1396unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, 1397 _InputIterator __last) 1398{ 1399 for (; __first != __last; ++__first) 1400 __table_.__insert_unique(*__first); 1401} 1402 1403#ifdef _LIBCPP_CXX03_LANG 1404template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1405_Tp& 1406unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](const key_type& __k) 1407{ 1408 iterator __i = find(__k); 1409 if (__i != end()) 1410 return __i->second; 1411 __node_holder __h = __construct_node_with_key(__k); 1412 pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get()); 1413 __h.release(); 1414 return __r.first->second; 1415} 1416#else 1417 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 return __table_.__emplace_unique_key_args(__k, 1423 std::piecewise_construct, std::forward_as_tuple(__k), 1424 std::forward_as_tuple()).first->__cc.second; 1425} 1426 1427template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1428_Tp& 1429unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](key_type&& __k) 1430{ 1431 return __table_.__emplace_unique_key_args(__k, 1432 std::piecewise_construct, std::forward_as_tuple(std::move(__k)), 1433 std::forward_as_tuple()).first->__cc.second; 1434} 1435 1436#endif // !_LIBCPP_CXX03_MODE 1437 1438template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1439_Tp& 1440unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::at(const key_type& __k) 1441{ 1442 iterator __i = find(__k); 1443#ifndef _LIBCPP_NO_EXCEPTIONS 1444 if (__i == end()) 1445 throw out_of_range("unordered_map::at: key not found"); 1446#endif // _LIBCPP_NO_EXCEPTIONS 1447 return __i->second; 1448} 1449 1450template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1451const _Tp& 1452unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::at(const key_type& __k) const 1453{ 1454 const_iterator __i = find(__k); 1455#ifndef _LIBCPP_NO_EXCEPTIONS 1456 if (__i == end()) 1457 throw out_of_range("unordered_map::at: key not found"); 1458#endif // _LIBCPP_NO_EXCEPTIONS 1459 return __i->second; 1460} 1461 1462template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1463inline _LIBCPP_INLINE_VISIBILITY 1464void 1465swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 1466 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 1467 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 1468{ 1469 __x.swap(__y); 1470} 1471 1472template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1473bool 1474operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 1475 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 1476{ 1477 if (__x.size() != __y.size()) 1478 return false; 1479 typedef typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator 1480 const_iterator; 1481 for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end(); 1482 __i != __ex; ++__i) 1483 { 1484 const_iterator __j = __y.find(__i->first); 1485 if (__j == __ey || !(*__i == *__j)) 1486 return false; 1487 } 1488 return true; 1489} 1490 1491template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1492inline _LIBCPP_INLINE_VISIBILITY 1493bool 1494operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 1495 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 1496{ 1497 return !(__x == __y); 1498} 1499 1500template <class _Key, class _Tp, class _Hash = hash<_Key>, class _Pred = equal_to<_Key>, 1501 class _Alloc = allocator<pair<const _Key, _Tp> > > 1502class _LIBCPP_TYPE_VIS_ONLY unordered_multimap 1503{ 1504public: 1505 // types 1506 typedef _Key key_type; 1507 typedef _Tp mapped_type; 1508 typedef _Hash hasher; 1509 typedef _Pred key_equal; 1510 typedef _Alloc allocator_type; 1511 typedef pair<const key_type, mapped_type> value_type; 1512 typedef pair<key_type, mapped_type> __nc_value_type; 1513 typedef value_type& reference; 1514 typedef const value_type& const_reference; 1515 static_assert((is_same<value_type, typename allocator_type::value_type>::value), 1516 "Invalid allocator::value_type"); 1517 1518private: 1519 typedef __hash_value_type<key_type, mapped_type> __value_type; 1520 typedef __unordered_map_hasher<key_type, __value_type, hasher> __hasher; 1521 typedef __unordered_map_equal<key_type, __value_type, key_equal> __key_equal; 1522 typedef typename __rebind_alloc_helper<allocator_traits<allocator_type>, 1523 __value_type>::type __allocator_type; 1524 1525 typedef __hash_table<__value_type, __hasher, 1526 __key_equal, __allocator_type> __table; 1527 1528 __table __table_; 1529 1530 typedef typename __table::_NodeTypes _NodeTypes; 1531 typedef typename __table::__node_traits __node_traits; 1532 typedef typename __table::__node_allocator __node_allocator; 1533 typedef typename __table::__node __node; 1534 typedef __hash_map_node_destructor<__node_allocator> _Dp; 1535 typedef unique_ptr<__node, _Dp> __node_holder; 1536 typedef allocator_traits<allocator_type> __alloc_traits; 1537 static_assert((is_same<typename __node_traits::size_type, 1538 typename __alloc_traits::size_type>::value), 1539 "Allocator uses different size_type for different types"); 1540public: 1541 typedef typename __alloc_traits::pointer pointer; 1542 typedef typename __alloc_traits::const_pointer const_pointer; 1543 typedef typename __table::size_type size_type; 1544 typedef typename __table::difference_type difference_type; 1545 1546 typedef __hash_map_iterator<typename __table::iterator> iterator; 1547 typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator; 1548 typedef __hash_map_iterator<typename __table::local_iterator> local_iterator; 1549 typedef __hash_map_const_iterator<typename __table::const_local_iterator> const_local_iterator; 1550 1551 _LIBCPP_INLINE_VISIBILITY 1552 unordered_multimap() 1553 _NOEXCEPT_(is_nothrow_default_constructible<__table>::value) 1554 { 1555#if _LIBCPP_DEBUG_LEVEL >= 2 1556 __get_db()->__insert_c(this); 1557#endif 1558 } 1559 explicit unordered_multimap(size_type __n, const hasher& __hf = hasher(), 1560 const key_equal& __eql = key_equal()); 1561 unordered_multimap(size_type __n, const hasher& __hf, 1562 const key_equal& __eql, 1563 const allocator_type& __a); 1564 template <class _InputIterator> 1565 unordered_multimap(_InputIterator __first, _InputIterator __last); 1566 template <class _InputIterator> 1567 unordered_multimap(_InputIterator __first, _InputIterator __last, 1568 size_type __n, const hasher& __hf = hasher(), 1569 const key_equal& __eql = key_equal()); 1570 template <class _InputIterator> 1571 unordered_multimap(_InputIterator __first, _InputIterator __last, 1572 size_type __n, const hasher& __hf, 1573 const key_equal& __eql, 1574 const allocator_type& __a); 1575 _LIBCPP_INLINE_VISIBILITY 1576 explicit unordered_multimap(const allocator_type& __a); 1577 unordered_multimap(const unordered_multimap& __u); 1578 unordered_multimap(const unordered_multimap& __u, const allocator_type& __a); 1579#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1580 _LIBCPP_INLINE_VISIBILITY 1581 unordered_multimap(unordered_multimap&& __u) 1582 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value); 1583 unordered_multimap(unordered_multimap&& __u, const allocator_type& __a); 1584#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1585#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1586 unordered_multimap(initializer_list<value_type> __il); 1587 unordered_multimap(initializer_list<value_type> __il, size_type __n, 1588 const hasher& __hf = hasher(), 1589 const key_equal& __eql = key_equal()); 1590 unordered_multimap(initializer_list<value_type> __il, size_type __n, 1591 const hasher& __hf, const key_equal& __eql, 1592 const allocator_type& __a); 1593#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1594#if _LIBCPP_STD_VER > 11 1595 _LIBCPP_INLINE_VISIBILITY 1596 unordered_multimap(size_type __n, const allocator_type& __a) 1597 : unordered_multimap(__n, hasher(), key_equal(), __a) {} 1598 _LIBCPP_INLINE_VISIBILITY 1599 unordered_multimap(size_type __n, const hasher& __hf, const allocator_type& __a) 1600 : unordered_multimap(__n, __hf, key_equal(), __a) {} 1601 template <class _InputIterator> 1602 _LIBCPP_INLINE_VISIBILITY 1603 unordered_multimap(_InputIterator __first, _InputIterator __last, size_type __n, const allocator_type& __a) 1604 : unordered_multimap(__first, __last, __n, hasher(), key_equal(), __a) {} 1605 template <class _InputIterator> 1606 _LIBCPP_INLINE_VISIBILITY 1607 unordered_multimap(_InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, 1608 const allocator_type& __a) 1609 : unordered_multimap(__first, __last, __n, __hf, key_equal(), __a) {} 1610 _LIBCPP_INLINE_VISIBILITY 1611 unordered_multimap(initializer_list<value_type> __il, size_type __n, const allocator_type& __a) 1612 : unordered_multimap(__il, __n, hasher(), key_equal(), __a) {} 1613 _LIBCPP_INLINE_VISIBILITY 1614 unordered_multimap(initializer_list<value_type> __il, size_type __n, const hasher& __hf, 1615 const allocator_type& __a) 1616 : unordered_multimap(__il, __n, __hf, key_equal(), __a) {} 1617#endif 1618 // ~unordered_multimap() = default; 1619 _LIBCPP_INLINE_VISIBILITY 1620 unordered_multimap& operator=(const unordered_multimap& __u) 1621 { 1622#ifndef _LIBCPP_CXX03_LANG 1623 __table_ = __u.__table_; 1624#else 1625 if (this != &__u) { 1626 __table_.clear(); 1627 __table_.hash_function() = __u.__table_.hash_function(); 1628 __table_.key_eq() = __u.__table_.key_eq(); 1629 __table_.max_load_factor() = __u.__table_.max_load_factor(); 1630 __table_.__copy_assign_alloc(__u.__table_); 1631 insert(__u.begin(), __u.end()); 1632 } 1633#endif 1634 return *this; 1635 } 1636#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1637 _LIBCPP_INLINE_VISIBILITY 1638 unordered_multimap& operator=(unordered_multimap&& __u) 1639 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value); 1640#endif 1641#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1642 _LIBCPP_INLINE_VISIBILITY 1643 unordered_multimap& operator=(initializer_list<value_type> __il); 1644#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1645 1646 _LIBCPP_INLINE_VISIBILITY 1647 allocator_type get_allocator() const _NOEXCEPT 1648 {return allocator_type(__table_.__node_alloc());} 1649 1650 _LIBCPP_INLINE_VISIBILITY 1651 bool empty() const _NOEXCEPT {return __table_.size() == 0;} 1652 _LIBCPP_INLINE_VISIBILITY 1653 size_type size() const _NOEXCEPT {return __table_.size();} 1654 _LIBCPP_INLINE_VISIBILITY 1655 size_type max_size() const _NOEXCEPT {return __table_.max_size();} 1656 1657 _LIBCPP_INLINE_VISIBILITY 1658 iterator begin() _NOEXCEPT {return __table_.begin();} 1659 _LIBCPP_INLINE_VISIBILITY 1660 iterator end() _NOEXCEPT {return __table_.end();} 1661 _LIBCPP_INLINE_VISIBILITY 1662 const_iterator begin() const _NOEXCEPT {return __table_.begin();} 1663 _LIBCPP_INLINE_VISIBILITY 1664 const_iterator end() const _NOEXCEPT {return __table_.end();} 1665 _LIBCPP_INLINE_VISIBILITY 1666 const_iterator cbegin() const _NOEXCEPT {return __table_.begin();} 1667 _LIBCPP_INLINE_VISIBILITY 1668 const_iterator cend() const _NOEXCEPT {return __table_.end();} 1669 1670 _LIBCPP_INLINE_VISIBILITY 1671 iterator insert(const value_type& __x) {return __table_.__insert_multi(__x);} 1672 1673 _LIBCPP_INLINE_VISIBILITY 1674 iterator insert(const_iterator __p, const value_type& __x) 1675 {return __table_.__insert_multi(__p.__i_, __x);} 1676 1677 template <class _InputIterator> 1678 _LIBCPP_INLINE_VISIBILITY 1679 void insert(_InputIterator __first, _InputIterator __last); 1680 1681#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1682 _LIBCPP_INLINE_VISIBILITY 1683 void insert(initializer_list<value_type> __il) 1684 {insert(__il.begin(), __il.end());} 1685#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1686 1687#ifndef _LIBCPP_CXX03_LANG 1688 _LIBCPP_INLINE_VISIBILITY 1689 iterator insert(value_type&& __x) {return __table_.__insert_multi(_VSTD::move(__x));} 1690 1691 _LIBCPP_INLINE_VISIBILITY 1692 iterator insert(const_iterator __p, value_type&& __x) 1693 {return __table_.__insert_multi(__p.__i_, _VSTD::move(__x));} 1694 1695 template <class _Pp, 1696 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type> 1697 _LIBCPP_INLINE_VISIBILITY 1698 iterator insert(_Pp&& __x) 1699 {return __table_.__insert_multi(_VSTD::forward<_Pp>(__x));} 1700 1701 template <class _Pp, 1702 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type> 1703 _LIBCPP_INLINE_VISIBILITY 1704 iterator insert(const_iterator __p, _Pp&& __x) 1705 {return __table_.__insert_multi(__p.__i_, _VSTD::forward<_Pp>(__x));} 1706 1707 template <class... _Args> 1708 iterator emplace(_Args&&... __args) { 1709 return __table_.__emplace_multi(_VSTD::forward<_Args>(__args)...); 1710 } 1711 1712 template <class... _Args> 1713 iterator emplace_hint(const_iterator __p, _Args&&... __args) { 1714 return __table_.__emplace_hint_multi(__p.__i_, _VSTD::forward<_Args>(__args)...); 1715 } 1716#endif // _LIBCPP_CXX03_LANG 1717 1718 1719 _LIBCPP_INLINE_VISIBILITY 1720 iterator erase(const_iterator __p) {return __table_.erase(__p.__i_);} 1721 _LIBCPP_INLINE_VISIBILITY 1722 iterator erase(iterator __p) {return __table_.erase(__p.__i_);} 1723 _LIBCPP_INLINE_VISIBILITY 1724 size_type erase(const key_type& __k) {return __table_.__erase_multi(__k);} 1725 _LIBCPP_INLINE_VISIBILITY 1726 iterator erase(const_iterator __first, const_iterator __last) 1727 {return __table_.erase(__first.__i_, __last.__i_);} 1728 _LIBCPP_INLINE_VISIBILITY 1729 void clear() _NOEXCEPT {__table_.clear();} 1730 1731 _LIBCPP_INLINE_VISIBILITY 1732 void swap(unordered_multimap& __u) 1733 _NOEXCEPT_(__is_nothrow_swappable<__table>::value) 1734 {__table_.swap(__u.__table_);} 1735 1736 _LIBCPP_INLINE_VISIBILITY 1737 hasher hash_function() const 1738 {return __table_.hash_function().hash_function();} 1739 _LIBCPP_INLINE_VISIBILITY 1740 key_equal key_eq() const 1741 {return __table_.key_eq().key_eq();} 1742 1743 _LIBCPP_INLINE_VISIBILITY 1744 iterator find(const key_type& __k) {return __table_.find(__k);} 1745 _LIBCPP_INLINE_VISIBILITY 1746 const_iterator find(const key_type& __k) const {return __table_.find(__k);} 1747 _LIBCPP_INLINE_VISIBILITY 1748 size_type count(const key_type& __k) const {return __table_.__count_multi(__k);} 1749 _LIBCPP_INLINE_VISIBILITY 1750 pair<iterator, iterator> equal_range(const key_type& __k) 1751 {return __table_.__equal_range_multi(__k);} 1752 _LIBCPP_INLINE_VISIBILITY 1753 pair<const_iterator, const_iterator> equal_range(const key_type& __k) const 1754 {return __table_.__equal_range_multi(__k);} 1755 1756 _LIBCPP_INLINE_VISIBILITY 1757 size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();} 1758 _LIBCPP_INLINE_VISIBILITY 1759 size_type max_bucket_count() const _NOEXCEPT 1760 {return __table_.max_bucket_count();} 1761 1762 _LIBCPP_INLINE_VISIBILITY 1763 size_type bucket_size(size_type __n) const 1764 {return __table_.bucket_size(__n);} 1765 _LIBCPP_INLINE_VISIBILITY 1766 size_type bucket(const key_type& __k) const {return __table_.bucket(__k);} 1767 1768 _LIBCPP_INLINE_VISIBILITY 1769 local_iterator begin(size_type __n) {return __table_.begin(__n);} 1770 _LIBCPP_INLINE_VISIBILITY 1771 local_iterator end(size_type __n) {return __table_.end(__n);} 1772 _LIBCPP_INLINE_VISIBILITY 1773 const_local_iterator begin(size_type __n) const {return __table_.cbegin(__n);} 1774 _LIBCPP_INLINE_VISIBILITY 1775 const_local_iterator end(size_type __n) const {return __table_.cend(__n);} 1776 _LIBCPP_INLINE_VISIBILITY 1777 const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);} 1778 _LIBCPP_INLINE_VISIBILITY 1779 const_local_iterator cend(size_type __n) const {return __table_.cend(__n);} 1780 1781 _LIBCPP_INLINE_VISIBILITY 1782 float load_factor() const _NOEXCEPT {return __table_.load_factor();} 1783 _LIBCPP_INLINE_VISIBILITY 1784 float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();} 1785 _LIBCPP_INLINE_VISIBILITY 1786 void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);} 1787 _LIBCPP_INLINE_VISIBILITY 1788 void rehash(size_type __n) {__table_.rehash(__n);} 1789 _LIBCPP_INLINE_VISIBILITY 1790 void reserve(size_type __n) {__table_.reserve(__n);} 1791 1792#if _LIBCPP_DEBUG_LEVEL >= 2 1793 1794 bool __dereferenceable(const const_iterator* __i) const 1795 {return __table_.__dereferenceable(&__i->__i_);} 1796 bool __decrementable(const const_iterator* __i) const 1797 {return __table_.__decrementable(&__i->__i_);} 1798 bool __addable(const const_iterator* __i, ptrdiff_t __n) const 1799 {return __table_.__addable(&__i->__i_, __n);} 1800 bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const 1801 {return __table_.__addable(&__i->__i_, __n);} 1802 1803#endif // _LIBCPP_DEBUG_LEVEL >= 2 1804 1805 1806}; 1807 1808template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1809unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1810 size_type __n, const hasher& __hf, const key_equal& __eql) 1811 : __table_(__hf, __eql) 1812{ 1813#if _LIBCPP_DEBUG_LEVEL >= 2 1814 __get_db()->__insert_c(this); 1815#endif 1816 __table_.rehash(__n); 1817} 1818 1819template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1820unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1821 size_type __n, const hasher& __hf, const key_equal& __eql, 1822 const allocator_type& __a) 1823 : __table_(__hf, __eql, typename __table::allocator_type(__a)) 1824{ 1825#if _LIBCPP_DEBUG_LEVEL >= 2 1826 __get_db()->__insert_c(this); 1827#endif 1828 __table_.rehash(__n); 1829} 1830 1831template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1832template <class _InputIterator> 1833unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1834 _InputIterator __first, _InputIterator __last) 1835{ 1836#if _LIBCPP_DEBUG_LEVEL >= 2 1837 __get_db()->__insert_c(this); 1838#endif 1839 insert(__first, __last); 1840} 1841 1842template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1843template <class _InputIterator> 1844unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1845 _InputIterator __first, _InputIterator __last, size_type __n, 1846 const hasher& __hf, const key_equal& __eql) 1847 : __table_(__hf, __eql) 1848{ 1849#if _LIBCPP_DEBUG_LEVEL >= 2 1850 __get_db()->__insert_c(this); 1851#endif 1852 __table_.rehash(__n); 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, const allocator_type& __a) 1861 : __table_(__hf, __eql, typename __table::allocator_type(__a)) 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> 1871inline 1872unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1873 const allocator_type& __a) 1874 : __table_(typename __table::allocator_type(__a)) 1875{ 1876#if _LIBCPP_DEBUG_LEVEL >= 2 1877 __get_db()->__insert_c(this); 1878#endif 1879} 1880 1881template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1882unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1883 const unordered_multimap& __u) 1884 : __table_(__u.__table_) 1885{ 1886#if _LIBCPP_DEBUG_LEVEL >= 2 1887 __get_db()->__insert_c(this); 1888#endif 1889 __table_.rehash(__u.bucket_count()); 1890 insert(__u.begin(), __u.end()); 1891} 1892 1893template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1894unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1895 const unordered_multimap& __u, const allocator_type& __a) 1896 : __table_(__u.__table_, typename __table::allocator_type(__a)) 1897{ 1898#if _LIBCPP_DEBUG_LEVEL >= 2 1899 __get_db()->__insert_c(this); 1900#endif 1901 __table_.rehash(__u.bucket_count()); 1902 insert(__u.begin(), __u.end()); 1903} 1904 1905#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1906 1907template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1908inline 1909unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1910 unordered_multimap&& __u) 1911 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value) 1912 : __table_(_VSTD::move(__u.__table_)) 1913{ 1914#if _LIBCPP_DEBUG_LEVEL >= 2 1915 __get_db()->__insert_c(this); 1916 __get_db()->swap(this, &__u); 1917#endif 1918} 1919 1920template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1921unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1922 unordered_multimap&& __u, const allocator_type& __a) 1923 : __table_(_VSTD::move(__u.__table_), typename __table::allocator_type(__a)) 1924{ 1925#if _LIBCPP_DEBUG_LEVEL >= 2 1926 __get_db()->__insert_c(this); 1927#endif 1928 if (__a != __u.get_allocator()) 1929 { 1930 iterator __i = __u.begin(); 1931 while (__u.size() != 0) 1932 { 1933 __table_.__insert_multi( 1934 _VSTD::move(__u.__table_.remove((__i++).__i_)->__value_.__nc) 1935 ); 1936 } 1937 } 1938#if _LIBCPP_DEBUG_LEVEL >= 2 1939 else 1940 __get_db()->swap(this, &__u); 1941#endif 1942} 1943 1944#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1945 1946#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1947 1948template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1949unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1950 initializer_list<value_type> __il) 1951{ 1952#if _LIBCPP_DEBUG_LEVEL >= 2 1953 __get_db()->__insert_c(this); 1954#endif 1955 insert(__il.begin(), __il.end()); 1956} 1957 1958template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1959unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1960 initializer_list<value_type> __il, size_type __n, const hasher& __hf, 1961 const key_equal& __eql) 1962 : __table_(__hf, __eql) 1963{ 1964#if _LIBCPP_DEBUG_LEVEL >= 2 1965 __get_db()->__insert_c(this); 1966#endif 1967 __table_.rehash(__n); 1968 insert(__il.begin(), __il.end()); 1969} 1970 1971template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1972unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( 1973 initializer_list<value_type> __il, size_type __n, const hasher& __hf, 1974 const key_equal& __eql, const allocator_type& __a) 1975 : __table_(__hf, __eql, typename __table::allocator_type(__a)) 1976{ 1977#if _LIBCPP_DEBUG_LEVEL >= 2 1978 __get_db()->__insert_c(this); 1979#endif 1980 __table_.rehash(__n); 1981 insert(__il.begin(), __il.end()); 1982} 1983 1984#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1985 1986#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1987 1988template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1989inline 1990unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& 1991unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(unordered_multimap&& __u) 1992 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value) 1993{ 1994 __table_ = _VSTD::move(__u.__table_); 1995 return *this; 1996} 1997 1998#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1999 2000#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 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=( 2006 initializer_list<value_type> __il) 2007{ 2008 __table_.__assign_multi(__il.begin(), __il.end()); 2009 return *this; 2010} 2011 2012#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 2013 2014 2015 2016template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2017template <class _InputIterator> 2018inline 2019void 2020unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, 2021 _InputIterator __last) 2022{ 2023 for (; __first != __last; ++__first) 2024 __table_.__insert_multi(*__first); 2025} 2026 2027template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2028inline _LIBCPP_INLINE_VISIBILITY 2029void 2030swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 2031 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 2032 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 2033{ 2034 __x.swap(__y); 2035} 2036 2037template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2038bool 2039operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 2040 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 2041{ 2042 if (__x.size() != __y.size()) 2043 return false; 2044 typedef typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator 2045 const_iterator; 2046 typedef pair<const_iterator, const_iterator> _EqRng; 2047 for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;) 2048 { 2049 _EqRng __xeq = __x.equal_range(__i->first); 2050 _EqRng __yeq = __y.equal_range(__i->first); 2051 if (_VSTD::distance(__xeq.first, __xeq.second) != 2052 _VSTD::distance(__yeq.first, __yeq.second) || 2053 !_VSTD::is_permutation(__xeq.first, __xeq.second, __yeq.first)) 2054 return false; 2055 __i = __xeq.second; 2056 } 2057 return true; 2058} 2059 2060template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2061inline _LIBCPP_INLINE_VISIBILITY 2062bool 2063operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 2064 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 2065{ 2066 return !(__x == __y); 2067} 2068 2069_LIBCPP_END_NAMESPACE_STD 2070 2071#endif // _LIBCPP_UNORDERED_MAP 2072