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