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