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