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