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