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