1// -*- C++ -*- 2//===----------------------------------------------------------------------===// 3// 4// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 5// See https://llvm.org/LICENSE.txt for license information. 6// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 7// 8//===----------------------------------------------------------------------===// 9 10#ifndef _LIBCPP_HASH_MAP 11#define _LIBCPP_HASH_MAP 12 13/* 14 15 hash_map synopsis 16 17namespace __gnu_cxx 18{ 19 20template <class Key, class T, class Hash = hash<Key>, class Pred = equal_to<Key>, 21 class Alloc = allocator<pair<const Key, T>>> 22class hash_map 23{ 24public: 25 // types 26 typedef Key key_type; 27 typedef T mapped_type; 28 typedef Hash hasher; 29 typedef Pred key_equal; 30 typedef Alloc allocator_type; 31 typedef pair<const key_type, mapped_type> value_type; 32 typedef value_type& reference; 33 typedef const value_type& const_reference; 34 typedef typename allocator_traits<allocator_type>::pointer pointer; 35 typedef typename allocator_traits<allocator_type>::const_pointer const_pointer; 36 typedef typename allocator_traits<allocator_type>::size_type size_type; 37 typedef typename allocator_traits<allocator_type>::difference_type difference_type; 38 39 typedef /unspecified/ iterator; 40 typedef /unspecified/ const_iterator; 41 42 hash_map(); 43 explicit hash_map(size_type n, const hasher& hf = hasher(), 44 const key_equal& eql = key_equal(), 45 const allocator_type& a = allocator_type()); 46 template <class InputIterator> 47 hash_map(InputIterator f, InputIterator l); 48 template <class InputIterator> 49 hash_map(InputIterator f, InputIterator l, 50 size_type n, const hasher& hf = hasher(), 51 const key_equal& eql = key_equal(), 52 const allocator_type& a = allocator_type()); 53 hash_map(const hash_map&); 54 ~hash_map(); 55 hash_map& operator=(const hash_map&); 56 57 allocator_type get_allocator() const; 58 59 bool empty() const; 60 size_type size() const; 61 size_type max_size() const; 62 63 iterator begin(); 64 iterator end(); 65 const_iterator begin() const; 66 const_iterator end() const; 67 68 pair<iterator, bool> insert(const value_type& obj); 69 template <class InputIterator> 70 void insert(InputIterator first, InputIterator last); 71 72 void erase(const_iterator position); 73 size_type erase(const key_type& k); 74 void erase(const_iterator first, const_iterator last); 75 void clear(); 76 77 void swap(hash_map&); 78 79 hasher hash_funct() const; 80 key_equal key_eq() const; 81 82 iterator find(const key_type& k); 83 const_iterator find(const key_type& k) const; 84 size_type count(const key_type& k) const; 85 pair<iterator, iterator> equal_range(const key_type& k); 86 pair<const_iterator, const_iterator> equal_range(const key_type& k) const; 87 88 mapped_type& operator[](const key_type& k); 89 90 size_type bucket_count() const; 91 size_type max_bucket_count() const; 92 93 size_type elems_in_bucket(size_type n) const; 94 95 void resize(size_type n); 96}; 97 98template <class Key, class T, class Hash, class Pred, class Alloc> 99 void swap(hash_map<Key, T, Hash, Pred, Alloc>& x, 100 hash_map<Key, T, Hash, Pred, Alloc>& y); 101 102template <class Key, class T, class Hash, class Pred, class Alloc> 103 bool 104 operator==(const hash_map<Key, T, Hash, Pred, Alloc>& x, 105 const hash_map<Key, T, Hash, Pred, Alloc>& y); 106 107template <class Key, class T, class Hash, class Pred, class Alloc> 108 bool 109 operator!=(const hash_map<Key, T, Hash, Pred, Alloc>& x, 110 const hash_map<Key, T, Hash, Pred, Alloc>& y); 111 112template <class Key, class T, class Hash = hash<Key>, class Pred = equal_to<Key>, 113 class Alloc = allocator<pair<const Key, T>>> 114class hash_multimap 115{ 116public: 117 // types 118 typedef Key key_type; 119 typedef T mapped_type; 120 typedef Hash hasher; 121 typedef Pred key_equal; 122 typedef Alloc allocator_type; 123 typedef pair<const key_type, mapped_type> value_type; 124 typedef value_type& reference; 125 typedef const value_type& const_reference; 126 typedef typename allocator_traits<allocator_type>::pointer pointer; 127 typedef typename allocator_traits<allocator_type>::const_pointer const_pointer; 128 typedef typename allocator_traits<allocator_type>::size_type size_type; 129 typedef typename allocator_traits<allocator_type>::difference_type difference_type; 130 131 typedef /unspecified/ iterator; 132 typedef /unspecified/ const_iterator; 133 134 explicit hash_multimap(size_type n = 193, const hasher& hf = hasher(), 135 const key_equal& eql = key_equal(), 136 const allocator_type& a = allocator_type()); 137 template <class InputIterator> 138 hash_multimap(InputIterator f, InputIterator l, 139 size_type n = 193, const hasher& hf = hasher(), 140 const key_equal& eql = key_equal(), 141 const allocator_type& a = allocator_type()); 142 explicit hash_multimap(const allocator_type&); 143 hash_multimap(const hash_multimap&); 144 ~hash_multimap(); 145 hash_multimap& operator=(const hash_multimap&); 146 147 allocator_type get_allocator() const; 148 149 bool empty() const; 150 size_type size() const; 151 size_type max_size() const; 152 153 iterator begin(); 154 iterator end(); 155 const_iterator begin() const; 156 const_iterator end() const; 157 158 iterator insert(const value_type& obj); 159 template <class InputIterator> 160 void insert(InputIterator first, InputIterator last); 161 162 void erase(const_iterator position); 163 size_type erase(const key_type& k); 164 void erase(const_iterator first, const_iterator last); 165 void clear(); 166 167 void swap(hash_multimap&); 168 169 hasher hash_funct() const; 170 key_equal key_eq() const; 171 172 iterator find(const key_type& k); 173 const_iterator find(const key_type& k) const; 174 size_type count(const key_type& k) const; 175 pair<iterator, iterator> equal_range(const key_type& k); 176 pair<const_iterator, const_iterator> equal_range(const key_type& k) const; 177 178 size_type bucket_count() const; 179 size_type max_bucket_count() const; 180 181 size_type elems_in_bucket(size_type n) const; 182 183 void resize(size_type n); 184}; 185 186template <class Key, class T, class Hash, class Pred, class Alloc> 187 void swap(hash_multimap<Key, T, Hash, Pred, Alloc>& x, 188 hash_multimap<Key, T, Hash, Pred, Alloc>& y); 189 190template <class Key, class T, class Hash, class Pred, class Alloc> 191 bool 192 operator==(const hash_multimap<Key, T, Hash, Pred, Alloc>& x, 193 const hash_multimap<Key, T, Hash, Pred, Alloc>& y); 194 195template <class Key, class T, class Hash, class Pred, class Alloc> 196 bool 197 operator!=(const hash_multimap<Key, T, Hash, Pred, Alloc>& x, 198 const hash_multimap<Key, T, Hash, Pred, Alloc>& y); 199 200} // __gnu_cxx 201 202*/ 203 204#include <__assert> // all public C++ headers provide the assertion handler 205#include <__config> 206#include <__hash_table> 207#include <algorithm> 208#include <ext/__hash> 209#include <functional> 210#include <stdexcept> 211 212#if defined(__DEPRECATED) && __DEPRECATED 213#if defined(_LIBCPP_WARNING) 214 _LIBCPP_WARNING("Use of the header <ext/hash_map> is deprecated. Migrate to <unordered_map>") 215#else 216# warning Use of the header <ext/hash_map> is deprecated. Migrate to <unordered_map> 217#endif 218#endif 219 220#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 221# pragma GCC system_header 222#endif 223 224namespace __gnu_cxx { 225 226template <class _Tp, class _Hash, 227 bool = std::is_empty<_Hash>::value && !std::__libcpp_is_final<_Hash>::value 228 > 229class __hash_map_hasher 230 : private _Hash 231{ 232public: 233 _LIBCPP_INLINE_VISIBILITY __hash_map_hasher() : _Hash() {} 234 _LIBCPP_INLINE_VISIBILITY __hash_map_hasher(const _Hash& __h) : _Hash(__h) {} 235 _LIBCPP_INLINE_VISIBILITY const _Hash& hash_function() const {return *this;} 236 _LIBCPP_INLINE_VISIBILITY 237 size_t operator()(const _Tp& __x) const 238 {return static_cast<const _Hash&>(*this)(__x.first);} 239 _LIBCPP_INLINE_VISIBILITY 240 size_t operator()(const typename _Tp::first_type& __x) const 241 {return static_cast<const _Hash&>(*this)(__x);} 242}; 243 244template <class _Tp, class _Hash> 245class __hash_map_hasher<_Tp, _Hash, false> 246{ 247 _Hash __hash_; 248public: 249 _LIBCPP_INLINE_VISIBILITY __hash_map_hasher() : __hash_() {} 250 _LIBCPP_INLINE_VISIBILITY __hash_map_hasher(const _Hash& __h) : __hash_(__h) {} 251 _LIBCPP_INLINE_VISIBILITY const _Hash& hash_function() const {return __hash_;} 252 _LIBCPP_INLINE_VISIBILITY 253 size_t operator()(const _Tp& __x) const 254 {return __hash_(__x.first);} 255 _LIBCPP_INLINE_VISIBILITY 256 size_t operator()(const typename _Tp::first_type& __x) const 257 {return __hash_(__x);} 258}; 259 260template <class _Tp, class _Pred, 261 bool = std::is_empty<_Pred>::value && !std::__libcpp_is_final<_Pred>::value 262 > 263class __hash_map_equal 264 : private _Pred 265{ 266public: 267 _LIBCPP_INLINE_VISIBILITY __hash_map_equal() : _Pred() {} 268 _LIBCPP_INLINE_VISIBILITY __hash_map_equal(const _Pred& __p) : _Pred(__p) {} 269 _LIBCPP_INLINE_VISIBILITY const _Pred& key_eq() const {return *this;} 270 _LIBCPP_INLINE_VISIBILITY 271 bool operator()(const _Tp& __x, const _Tp& __y) const 272 {return static_cast<const _Pred&>(*this)(__x.first, __y.first);} 273 _LIBCPP_INLINE_VISIBILITY 274 bool operator()(const typename _Tp::first_type& __x, const _Tp& __y) const 275 {return static_cast<const _Pred&>(*this)(__x, __y.first);} 276 _LIBCPP_INLINE_VISIBILITY 277 bool operator()(const _Tp& __x, const typename _Tp::first_type& __y) const 278 {return static_cast<const _Pred&>(*this)(__x.first, __y);} 279 _LIBCPP_INLINE_VISIBILITY 280 bool operator()(const typename _Tp::first_type& __x, 281 const typename _Tp::first_type& __y) const 282 {return static_cast<const _Pred&>(*this)(__x, __y);} 283}; 284 285template <class _Tp, class _Pred> 286class __hash_map_equal<_Tp, _Pred, false> 287{ 288 _Pred __pred_; 289public: 290 _LIBCPP_INLINE_VISIBILITY __hash_map_equal() : __pred_() {} 291 _LIBCPP_INLINE_VISIBILITY __hash_map_equal(const _Pred& __p) : __pred_(__p) {} 292 _LIBCPP_INLINE_VISIBILITY const _Pred& key_eq() const {return __pred_;} 293 _LIBCPP_INLINE_VISIBILITY 294 bool operator()(const _Tp& __x, const _Tp& __y) const 295 {return __pred_(__x.first, __y.first);} 296 _LIBCPP_INLINE_VISIBILITY 297 bool operator()(const typename _Tp::first_type& __x, const _Tp& __y) const 298 {return __pred_(__x, __y.first);} 299 _LIBCPP_INLINE_VISIBILITY 300 bool operator()(const _Tp& __x, const typename _Tp::first_type& __y) const 301 {return __pred_(__x.first, __y);} 302 _LIBCPP_INLINE_VISIBILITY 303 bool operator()(const typename _Tp::first_type& __x, 304 const typename _Tp::first_type& __y) const 305 {return __pred_(__x, __y);} 306}; 307 308template <class _Alloc> 309class __hash_map_node_destructor 310{ 311 typedef _Alloc allocator_type; 312 typedef std::allocator_traits<allocator_type> __alloc_traits; 313 typedef typename __alloc_traits::value_type::__node_value_type value_type; 314public: 315 typedef typename __alloc_traits::pointer pointer; 316private: 317 typedef typename value_type::first_type first_type; 318 typedef typename value_type::second_type second_type; 319 320 allocator_type& __na_; 321 322public: 323 bool __first_constructed; 324 bool __second_constructed; 325 326 _LIBCPP_HIDE_FROM_ABI __hash_map_node_destructor(__hash_map_node_destructor const&) = default; 327 __hash_map_node_destructor& operator=(const __hash_map_node_destructor&) = delete; 328 329 _LIBCPP_INLINE_VISIBILITY 330 explicit __hash_map_node_destructor(allocator_type& __na) 331 : __na_(__na), 332 __first_constructed(false), 333 __second_constructed(false) 334 {} 335 336#ifndef _LIBCPP_CXX03_LANG 337 _LIBCPP_INLINE_VISIBILITY 338 __hash_map_node_destructor(std::__hash_node_destructor<allocator_type>&& __x) 339 : __na_(__x.__na_), 340 __first_constructed(__x.__value_constructed), 341 __second_constructed(__x.__value_constructed) 342 { 343 __x.__value_constructed = false; 344 } 345#else // _LIBCPP_CXX03_LANG 346 _LIBCPP_INLINE_VISIBILITY 347 __hash_map_node_destructor(const std::__hash_node_destructor<allocator_type>& __x) 348 : __na_(__x.__na_), 349 __first_constructed(__x.__value_constructed), 350 __second_constructed(__x.__value_constructed) 351 { 352 const_cast<bool&>(__x.__value_constructed) = false; 353 } 354#endif // _LIBCPP_CXX03_LANG 355 356 _LIBCPP_INLINE_VISIBILITY 357 void operator()(pointer __p) 358 { 359 if (__second_constructed) 360 __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.second)); 361 if (__first_constructed) 362 __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.first)); 363 if (__p) 364 __alloc_traits::deallocate(__na_, __p, 1); 365 } 366}; 367 368template <class _HashIterator> 369class _LIBCPP_TEMPLATE_VIS __hash_map_iterator 370{ 371 _HashIterator __i_; 372 373 typedef const typename _HashIterator::value_type::first_type key_type; 374 typedef typename _HashIterator::value_type::second_type mapped_type; 375public: 376 typedef std::forward_iterator_tag iterator_category; 377 typedef std::pair<key_type, mapped_type> value_type; 378 typedef typename _HashIterator::difference_type difference_type; 379 typedef value_type& reference; 380 typedef std::__rebind_pointer_t<typename _HashIterator::pointer, value_type> 381 pointer; 382 383 _LIBCPP_INLINE_VISIBILITY __hash_map_iterator() {} 384 385 _LIBCPP_INLINE_VISIBILITY __hash_map_iterator(_HashIterator __i) : __i_(__i) {} 386 387 _LIBCPP_INLINE_VISIBILITY reference operator*() const {return *operator->();} 388 _LIBCPP_INLINE_VISIBILITY pointer operator->() const {return (pointer)__i_.operator->();} 389 390 _LIBCPP_INLINE_VISIBILITY __hash_map_iterator& operator++() {++__i_; return *this;} 391 _LIBCPP_INLINE_VISIBILITY 392 __hash_map_iterator operator++(int) 393 { 394 __hash_map_iterator __t(*this); 395 ++(*this); 396 return __t; 397 } 398 399 friend _LIBCPP_INLINE_VISIBILITY 400 bool operator==(const __hash_map_iterator& __x, const __hash_map_iterator& __y) 401 {return __x.__i_ == __y.__i_;} 402 friend _LIBCPP_INLINE_VISIBILITY 403 bool operator!=(const __hash_map_iterator& __x, const __hash_map_iterator& __y) 404 {return __x.__i_ != __y.__i_;} 405 406 template <class, class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS hash_map; 407 template <class, class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS hash_multimap; 408 template <class> friend class _LIBCPP_TEMPLATE_VIS __hash_const_iterator; 409 template <class> friend class _LIBCPP_TEMPLATE_VIS __hash_const_local_iterator; 410 template <class> friend class _LIBCPP_TEMPLATE_VIS __hash_map_const_iterator; 411}; 412 413template <class _HashIterator> 414class _LIBCPP_TEMPLATE_VIS __hash_map_const_iterator 415{ 416 _HashIterator __i_; 417 418 typedef const typename _HashIterator::value_type::first_type key_type; 419 typedef typename _HashIterator::value_type::second_type mapped_type; 420public: 421 typedef std::forward_iterator_tag iterator_category; 422 typedef std::pair<key_type, mapped_type> value_type; 423 typedef typename _HashIterator::difference_type difference_type; 424 typedef const value_type& reference; 425 typedef std::__rebind_pointer_t<typename _HashIterator::pointer, const value_type> 426 pointer; 427 428 _LIBCPP_INLINE_VISIBILITY __hash_map_const_iterator() {} 429 430 _LIBCPP_INLINE_VISIBILITY 431 __hash_map_const_iterator(_HashIterator __i) : __i_(__i) {} 432 _LIBCPP_INLINE_VISIBILITY 433 __hash_map_const_iterator( 434 __hash_map_iterator<typename _HashIterator::__non_const_iterator> __i) 435 : __i_(__i.__i_) {} 436 437 _LIBCPP_INLINE_VISIBILITY 438 reference operator*() const {return *operator->();} 439 _LIBCPP_INLINE_VISIBILITY 440 pointer operator->() const {return (pointer)__i_.operator->();} 441 442 _LIBCPP_INLINE_VISIBILITY 443 __hash_map_const_iterator& operator++() {++__i_; return *this;} 444 _LIBCPP_INLINE_VISIBILITY 445 __hash_map_const_iterator operator++(int) 446 { 447 __hash_map_const_iterator __t(*this); 448 ++(*this); 449 return __t; 450 } 451 452 friend _LIBCPP_INLINE_VISIBILITY 453 bool operator==(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y) 454 {return __x.__i_ == __y.__i_;} 455 friend _LIBCPP_INLINE_VISIBILITY 456 bool operator!=(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y) 457 {return __x.__i_ != __y.__i_;} 458 459 template <class, class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS hash_map; 460 template <class, class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS hash_multimap; 461 template <class> friend class _LIBCPP_TEMPLATE_VIS __hash_const_iterator; 462 template <class> friend class _LIBCPP_TEMPLATE_VIS __hash_const_local_iterator; 463}; 464 465template <class _Key, class _Tp, class _Hash = hash<_Key>, class _Pred = std::equal_to<_Key>, 466 class _Alloc = std::allocator<std::pair<const _Key, _Tp> > > 467class _LIBCPP_TEMPLATE_VIS hash_map 468{ 469public: 470 // types 471 typedef _Key key_type; 472 typedef _Tp mapped_type; 473 typedef _Tp data_type; 474 typedef _Hash hasher; 475 typedef _Pred key_equal; 476 typedef _Alloc allocator_type; 477 typedef std::pair<const key_type, mapped_type> value_type; 478 typedef value_type& reference; 479 typedef const value_type& const_reference; 480 481private: 482 typedef std::pair<key_type, mapped_type> __value_type; 483 typedef __hash_map_hasher<__value_type, hasher> __hasher; 484 typedef __hash_map_equal<__value_type, key_equal> __key_equal; 485 typedef std::__rebind_alloc<std::allocator_traits<allocator_type>, __value_type> __allocator_type; 486 487 typedef std::__hash_table<__value_type, __hasher, 488 __key_equal, __allocator_type> __table; 489 490 __table __table_; 491 492 typedef typename __table::__node_pointer __node_pointer; 493 typedef typename __table::__node_const_pointer __node_const_pointer; 494 typedef typename __table::__node_traits __node_traits; 495 typedef typename __table::__node_allocator __node_allocator; 496 typedef typename __table::__node __node; 497 typedef __hash_map_node_destructor<__node_allocator> _Dp; 498 typedef std::unique_ptr<__node, _Dp> __node_holder; 499 typedef std::allocator_traits<allocator_type> __alloc_traits; 500public: 501 typedef typename __alloc_traits::pointer pointer; 502 typedef typename __alloc_traits::const_pointer const_pointer; 503 typedef typename __alloc_traits::size_type size_type; 504 typedef typename __alloc_traits::difference_type difference_type; 505 506 typedef __hash_map_iterator<typename __table::iterator> iterator; 507 typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator; 508 509 _LIBCPP_INLINE_VISIBILITY hash_map() { } 510 explicit _LIBCPP_HIDE_FROM_ABI hash_map(size_type __n, const hasher& __hf = hasher(), 511 const key_equal& __eql = key_equal()); 512 _LIBCPP_HIDE_FROM_ABI hash_map(size_type __n, const hasher& __hf, 513 const key_equal& __eql, 514 const allocator_type& __a); 515 template <class _InputIterator> 516 _LIBCPP_HIDE_FROM_ABI hash_map(_InputIterator __first, _InputIterator __last); 517 template <class _InputIterator> 518 _LIBCPP_HIDE_FROM_ABI hash_map(_InputIterator __first, _InputIterator __last, 519 size_type __n, const hasher& __hf = hasher(), 520 const key_equal& __eql = key_equal()); 521 template <class _InputIterator> 522 _LIBCPP_HIDE_FROM_ABI hash_map(_InputIterator __first, _InputIterator __last, 523 size_type __n, const hasher& __hf, 524 const key_equal& __eql, 525 const allocator_type& __a); 526 _LIBCPP_HIDE_FROM_ABI hash_map(const hash_map& __u); 527 528 _LIBCPP_INLINE_VISIBILITY 529 allocator_type get_allocator() const 530 {return allocator_type(__table_.__node_alloc());} 531 532 _LIBCPP_INLINE_VISIBILITY 533 bool empty() const {return __table_.size() == 0;} 534 _LIBCPP_INLINE_VISIBILITY 535 size_type size() const {return __table_.size();} 536 _LIBCPP_INLINE_VISIBILITY 537 size_type max_size() const {return __table_.max_size();} 538 539 _LIBCPP_INLINE_VISIBILITY 540 iterator begin() {return __table_.begin();} 541 _LIBCPP_INLINE_VISIBILITY 542 iterator end() {return __table_.end();} 543 _LIBCPP_INLINE_VISIBILITY 544 const_iterator begin() const {return __table_.begin();} 545 _LIBCPP_INLINE_VISIBILITY 546 const_iterator end() const {return __table_.end();} 547 548 _LIBCPP_INLINE_VISIBILITY 549 std::pair<iterator, bool> insert(const value_type& __x) 550 {return __table_.__insert_unique(__x);} 551 _LIBCPP_INLINE_VISIBILITY 552 iterator insert(const_iterator, const value_type& __x) {return insert(__x).first;} 553 template <class _InputIterator> 554 _LIBCPP_INLINE_VISIBILITY 555 void insert(_InputIterator __first, _InputIterator __last); 556 557 _LIBCPP_INLINE_VISIBILITY 558 void erase(const_iterator __p) {__table_.erase(__p.__i_);} 559 _LIBCPP_INLINE_VISIBILITY 560 size_type erase(const key_type& __k) {return __table_.__erase_unique(__k);} 561 _LIBCPP_INLINE_VISIBILITY 562 void erase(const_iterator __first, const_iterator __last) 563 {__table_.erase(__first.__i_, __last.__i_);} 564 _LIBCPP_INLINE_VISIBILITY 565 void clear() {__table_.clear();} 566 567 _LIBCPP_INLINE_VISIBILITY 568 void swap(hash_map& __u) {__table_.swap(__u.__table_);} 569 570 _LIBCPP_INLINE_VISIBILITY 571 hasher hash_funct() const 572 {return __table_.hash_function().hash_function();} 573 _LIBCPP_INLINE_VISIBILITY 574 key_equal key_eq() const 575 {return __table_.key_eq().key_eq();} 576 577 _LIBCPP_INLINE_VISIBILITY 578 iterator find(const key_type& __k) {return __table_.find(__k);} 579 _LIBCPP_INLINE_VISIBILITY 580 const_iterator find(const key_type& __k) const {return __table_.find(__k);} 581 _LIBCPP_INLINE_VISIBILITY 582 size_type count(const key_type& __k) const {return __table_.__count_unique(__k);} 583 _LIBCPP_INLINE_VISIBILITY 584 std::pair<iterator, iterator> equal_range(const key_type& __k) 585 {return __table_.__equal_range_unique(__k);} 586 _LIBCPP_INLINE_VISIBILITY 587 std::pair<const_iterator, const_iterator> equal_range(const key_type& __k) const 588 {return __table_.__equal_range_unique(__k);} 589 590 _LIBCPP_HIDE_FROM_ABI mapped_type& operator[](const key_type& __k); 591 592 _LIBCPP_INLINE_VISIBILITY 593 size_type bucket_count() const {return __table_.bucket_count();} 594 _LIBCPP_INLINE_VISIBILITY 595 size_type max_bucket_count() const {return __table_.max_bucket_count();} 596 597 _LIBCPP_INLINE_VISIBILITY 598 size_type elems_in_bucket(size_type __n) const 599 {return __table_.bucket_size(__n);} 600 601 _LIBCPP_INLINE_VISIBILITY 602 void resize(size_type __n) {__table_.__rehash_unique(__n);} 603 604private: 605 _LIBCPP_HIDE_FROM_ABI __node_holder __construct_node(const key_type& __k); 606}; 607 608template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 609hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_map( 610 size_type __n, const hasher& __hf, const key_equal& __eql) 611 : __table_(__hf, __eql) 612{ 613 __table_.__rehash_unique(__n); 614} 615 616template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 617hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_map( 618 size_type __n, const hasher& __hf, const key_equal& __eql, 619 const allocator_type& __a) 620 : __table_(__hf, __eql, __a) 621{ 622 __table_.__rehash_unique(__n); 623} 624 625template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 626template <class _InputIterator> 627hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_map( 628 _InputIterator __first, _InputIterator __last) 629{ 630 insert(__first, __last); 631} 632 633template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 634template <class _InputIterator> 635hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_map( 636 _InputIterator __first, _InputIterator __last, size_type __n, 637 const hasher& __hf, const key_equal& __eql) 638 : __table_(__hf, __eql) 639{ 640 __table_.__rehash_unique(__n); 641 insert(__first, __last); 642} 643 644template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 645template <class _InputIterator> 646hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_map( 647 _InputIterator __first, _InputIterator __last, size_type __n, 648 const hasher& __hf, const key_equal& __eql, const allocator_type& __a) 649 : __table_(__hf, __eql, __a) 650{ 651 __table_.__rehash_unique(__n); 652 insert(__first, __last); 653} 654 655template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 656hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_map( 657 const hash_map& __u) 658 : __table_(__u.__table_) 659{ 660 __table_.__rehash_unique(__u.bucket_count()); 661 insert(__u.begin(), __u.end()); 662} 663 664template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 665typename hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder 666hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(const key_type& __k) 667{ 668 __node_allocator& __na = __table_.__node_alloc(); 669 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 670 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.first), __k); 671 __h.get_deleter().__first_constructed = true; 672 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.second)); 673 __h.get_deleter().__second_constructed = true; 674 return __h; 675} 676 677template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 678template <class _InputIterator> 679inline 680void 681hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, 682 _InputIterator __last) 683{ 684 for (; __first != __last; ++__first) 685 __table_.__insert_unique(*__first); 686} 687 688template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 689_Tp& 690hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](const key_type& __k) 691{ 692 iterator __i = find(__k); 693 if (__i != end()) 694 return __i->second; 695 __node_holder __h = __construct_node(__k); 696 std::pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get()); 697 __h.release(); 698 return __r.first->second; 699} 700 701template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 702inline _LIBCPP_INLINE_VISIBILITY 703void 704swap(hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 705 hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 706{ 707 __x.swap(__y); 708} 709 710template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 711_LIBCPP_HIDE_FROM_ABI bool 712operator==(const hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 713 const hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 714{ 715 if (__x.size() != __y.size()) 716 return false; 717 typedef typename hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator 718 const_iterator; 719 for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end(); 720 __i != __ex; ++__i) 721 { 722 const_iterator __j = __y.find(__i->first); 723 if (__j == __ey || !(*__i == *__j)) 724 return false; 725 } 726 return true; 727} 728 729template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 730inline _LIBCPP_INLINE_VISIBILITY 731bool 732operator!=(const hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 733 const hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 734{ 735 return !(__x == __y); 736} 737 738template <class _Key, class _Tp, class _Hash = hash<_Key>, class _Pred = std::equal_to<_Key>, 739 class _Alloc = std::allocator<std::pair<const _Key, _Tp> > > 740class _LIBCPP_TEMPLATE_VIS hash_multimap 741{ 742public: 743 // types 744 typedef _Key key_type; 745 typedef _Tp mapped_type; 746 typedef _Tp data_type; 747 typedef _Hash hasher; 748 typedef _Pred key_equal; 749 typedef _Alloc allocator_type; 750 typedef std::pair<const key_type, mapped_type> value_type; 751 typedef value_type& reference; 752 typedef const value_type& const_reference; 753 754private: 755 typedef std::pair<key_type, mapped_type> __value_type; 756 typedef __hash_map_hasher<__value_type, hasher> __hasher; 757 typedef __hash_map_equal<__value_type, key_equal> __key_equal; 758 typedef std::__rebind_alloc<std::allocator_traits<allocator_type>, __value_type> __allocator_type; 759 760 typedef std::__hash_table<__value_type, __hasher, 761 __key_equal, __allocator_type> __table; 762 763 __table __table_; 764 765 typedef typename __table::__node_traits __node_traits; 766 typedef typename __table::__node_allocator __node_allocator; 767 typedef typename __table::__node __node; 768 typedef __hash_map_node_destructor<__node_allocator> _Dp; 769 typedef std::unique_ptr<__node, _Dp> __node_holder; 770 typedef std::allocator_traits<allocator_type> __alloc_traits; 771public: 772 typedef typename __alloc_traits::pointer pointer; 773 typedef typename __alloc_traits::const_pointer const_pointer; 774 typedef typename __alloc_traits::size_type size_type; 775 typedef typename __alloc_traits::difference_type difference_type; 776 777 typedef __hash_map_iterator<typename __table::iterator> iterator; 778 typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator; 779 780 _LIBCPP_INLINE_VISIBILITY 781 hash_multimap() { } 782 explicit _LIBCPP_HIDE_FROM_ABI hash_multimap(size_type __n, const hasher& __hf = hasher(), 783 const key_equal& __eql = key_equal()); 784 _LIBCPP_HIDE_FROM_ABI hash_multimap(size_type __n, const hasher& __hf, 785 const key_equal& __eql, 786 const allocator_type& __a); 787 template <class _InputIterator> 788 _LIBCPP_HIDE_FROM_ABI hash_multimap(_InputIterator __first, _InputIterator __last); 789 template <class _InputIterator> 790 _LIBCPP_HIDE_FROM_ABI hash_multimap(_InputIterator __first, _InputIterator __last, 791 size_type __n, const hasher& __hf = hasher(), 792 const key_equal& __eql = key_equal()); 793 template <class _InputIterator> 794 _LIBCPP_HIDE_FROM_ABI hash_multimap(_InputIterator __first, _InputIterator __last, 795 size_type __n, const hasher& __hf, 796 const key_equal& __eql, 797 const allocator_type& __a); 798 _LIBCPP_HIDE_FROM_ABI hash_multimap(const hash_multimap& __u); 799 800 _LIBCPP_INLINE_VISIBILITY 801 allocator_type get_allocator() const 802 {return allocator_type(__table_.__node_alloc());} 803 804 _LIBCPP_INLINE_VISIBILITY 805 bool empty() const {return __table_.size() == 0;} 806 _LIBCPP_INLINE_VISIBILITY 807 size_type size() const {return __table_.size();} 808 _LIBCPP_INLINE_VISIBILITY 809 size_type max_size() const {return __table_.max_size();} 810 811 _LIBCPP_INLINE_VISIBILITY 812 iterator begin() {return __table_.begin();} 813 _LIBCPP_INLINE_VISIBILITY 814 iterator end() {return __table_.end();} 815 _LIBCPP_INLINE_VISIBILITY 816 const_iterator begin() const {return __table_.begin();} 817 _LIBCPP_INLINE_VISIBILITY 818 const_iterator end() const {return __table_.end();} 819 820 _LIBCPP_INLINE_VISIBILITY 821 iterator insert(const value_type& __x) {return __table_.__insert_multi(__x);} 822 _LIBCPP_INLINE_VISIBILITY 823 iterator insert(const_iterator, const value_type& __x) {return insert(__x);} 824 template <class _InputIterator> 825 _LIBCPP_INLINE_VISIBILITY 826 void insert(_InputIterator __first, _InputIterator __last); 827 828 _LIBCPP_INLINE_VISIBILITY 829 void erase(const_iterator __p) {__table_.erase(__p.__i_);} 830 _LIBCPP_INLINE_VISIBILITY 831 size_type erase(const key_type& __k) {return __table_.__erase_multi(__k);} 832 _LIBCPP_INLINE_VISIBILITY 833 void erase(const_iterator __first, const_iterator __last) 834 {__table_.erase(__first.__i_, __last.__i_);} 835 _LIBCPP_INLINE_VISIBILITY 836 void clear() {__table_.clear();} 837 838 _LIBCPP_INLINE_VISIBILITY 839 void swap(hash_multimap& __u) {__table_.swap(__u.__table_);} 840 841 _LIBCPP_INLINE_VISIBILITY 842 hasher hash_funct() const 843 {return __table_.hash_function().hash_function();} 844 _LIBCPP_INLINE_VISIBILITY 845 key_equal key_eq() const 846 {return __table_.key_eq().key_eq();} 847 848 _LIBCPP_INLINE_VISIBILITY 849 iterator find(const key_type& __k) {return __table_.find(__k);} 850 _LIBCPP_INLINE_VISIBILITY 851 const_iterator find(const key_type& __k) const {return __table_.find(__k);} 852 _LIBCPP_INLINE_VISIBILITY 853 size_type count(const key_type& __k) const {return __table_.__count_multi(__k);} 854 _LIBCPP_INLINE_VISIBILITY 855 std::pair<iterator, iterator> equal_range(const key_type& __k) 856 {return __table_.__equal_range_multi(__k);} 857 _LIBCPP_INLINE_VISIBILITY 858 std::pair<const_iterator, const_iterator> equal_range(const key_type& __k) const 859 {return __table_.__equal_range_multi(__k);} 860 861 _LIBCPP_INLINE_VISIBILITY 862 size_type bucket_count() const {return __table_.bucket_count();} 863 _LIBCPP_INLINE_VISIBILITY 864 size_type max_bucket_count() const {return __table_.max_bucket_count();} 865 866 _LIBCPP_INLINE_VISIBILITY 867 size_type elems_in_bucket(size_type __n) const 868 {return __table_.bucket_size(__n);} 869 870 _LIBCPP_INLINE_VISIBILITY 871 void resize(size_type __n) {__table_.__rehash_multi(__n);} 872}; 873 874template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 875hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_multimap( 876 size_type __n, const hasher& __hf, const key_equal& __eql) 877 : __table_(__hf, __eql) 878{ 879 __table_.__rehash_multi(__n); 880} 881 882template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 883hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_multimap( 884 size_type __n, const hasher& __hf, const key_equal& __eql, 885 const allocator_type& __a) 886 : __table_(__hf, __eql, __a) 887{ 888 __table_.__rehash_multi(__n); 889} 890 891template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 892template <class _InputIterator> 893hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_multimap( 894 _InputIterator __first, _InputIterator __last) 895{ 896 insert(__first, __last); 897} 898 899template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 900template <class _InputIterator> 901hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_multimap( 902 _InputIterator __first, _InputIterator __last, size_type __n, 903 const hasher& __hf, const key_equal& __eql) 904 : __table_(__hf, __eql) 905{ 906 __table_.__rehash_multi(__n); 907 insert(__first, __last); 908} 909 910template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 911template <class _InputIterator> 912hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_multimap( 913 _InputIterator __first, _InputIterator __last, size_type __n, 914 const hasher& __hf, const key_equal& __eql, const allocator_type& __a) 915 : __table_(__hf, __eql, __a) 916{ 917 __table_.__rehash_multi(__n); 918 insert(__first, __last); 919} 920 921template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 922hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_multimap( 923 const hash_multimap& __u) 924 : __table_(__u.__table_) 925{ 926 __table_.__rehash_multi(__u.bucket_count()); 927 insert(__u.begin(), __u.end()); 928} 929 930template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 931template <class _InputIterator> 932inline 933void 934hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, 935 _InputIterator __last) 936{ 937 for (; __first != __last; ++__first) 938 __table_.__insert_multi(*__first); 939} 940 941template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 942inline _LIBCPP_INLINE_VISIBILITY 943void 944swap(hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 945 hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 946{ 947 __x.swap(__y); 948} 949 950template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 951_LIBCPP_HIDE_FROM_ABI bool 952operator==(const hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 953 const hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 954{ 955 if (__x.size() != __y.size()) 956 return false; 957 typedef typename hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator 958 const_iterator; 959 typedef std::pair<const_iterator, const_iterator> _EqRng; 960 for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;) 961 { 962 _EqRng __xeq = __x.equal_range(__i->first); 963 _EqRng __yeq = __y.equal_range(__i->first); 964 if (_VSTD::distance(__xeq.first, __xeq.second) != 965 _VSTD::distance(__yeq.first, __yeq.second) || 966 !_VSTD::is_permutation(__xeq.first, __xeq.second, __yeq.first)) 967 return false; 968 __i = __xeq.second; 969 } 970 return true; 971} 972 973template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 974inline _LIBCPP_INLINE_VISIBILITY 975bool 976operator!=(const hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 977 const hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 978{ 979 return !(__x == __y); 980} 981 982} // namespace __gnu_cxx 983 984#if !defined(_LIBCPP_REMOVE_TRANSITIVE_INCLUDES) && _LIBCPP_STD_VER <= 20 985# include <concepts> 986# include <iterator> 987# include <type_traits> 988#endif 989 990#endif // _LIBCPP_HASH_MAP 991