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