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