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