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