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