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