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