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