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