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#include <type_traits> 212 213#if defined(__DEPRECATED) && __DEPRECATED 214#if defined(_LIBCPP_WARNING) 215 _LIBCPP_WARNING("Use of the header <ext/hash_map> is deprecated. Migrate to <unordered_map>") 216#else 217# warning Use of the header <ext/hash_map> is deprecated. Migrate to <unordered_map> 218#endif 219#endif 220 221#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 222# pragma GCC system_header 223#endif 224 225namespace __gnu_cxx { 226 227template <class _Tp, class _Hash, 228 bool = std::is_empty<_Hash>::value && !std::__libcpp_is_final<_Hash>::value 229 > 230class __hash_map_hasher 231 : private _Hash 232{ 233public: 234 _LIBCPP_INLINE_VISIBILITY __hash_map_hasher() : _Hash() {} 235 _LIBCPP_INLINE_VISIBILITY __hash_map_hasher(const _Hash& __h) : _Hash(__h) {} 236 _LIBCPP_INLINE_VISIBILITY const _Hash& hash_function() const {return *this;} 237 _LIBCPP_INLINE_VISIBILITY 238 size_t operator()(const _Tp& __x) const 239 {return static_cast<const _Hash&>(*this)(__x.first);} 240 _LIBCPP_INLINE_VISIBILITY 241 size_t operator()(const typename _Tp::first_type& __x) const 242 {return static_cast<const _Hash&>(*this)(__x);} 243}; 244 245template <class _Tp, class _Hash> 246class __hash_map_hasher<_Tp, _Hash, false> 247{ 248 _Hash __hash_; 249public: 250 _LIBCPP_INLINE_VISIBILITY __hash_map_hasher() : __hash_() {} 251 _LIBCPP_INLINE_VISIBILITY __hash_map_hasher(const _Hash& __h) : __hash_(__h) {} 252 _LIBCPP_INLINE_VISIBILITY const _Hash& hash_function() const {return __hash_;} 253 _LIBCPP_INLINE_VISIBILITY 254 size_t operator()(const _Tp& __x) const 255 {return __hash_(__x.first);} 256 _LIBCPP_INLINE_VISIBILITY 257 size_t operator()(const typename _Tp::first_type& __x) const 258 {return __hash_(__x);} 259}; 260 261template <class _Tp, class _Pred, 262 bool = std::is_empty<_Pred>::value && !std::__libcpp_is_final<_Pred>::value 263 > 264class __hash_map_equal 265 : private _Pred 266{ 267public: 268 _LIBCPP_INLINE_VISIBILITY __hash_map_equal() : _Pred() {} 269 _LIBCPP_INLINE_VISIBILITY __hash_map_equal(const _Pred& __p) : _Pred(__p) {} 270 _LIBCPP_INLINE_VISIBILITY const _Pred& key_eq() const {return *this;} 271 _LIBCPP_INLINE_VISIBILITY 272 bool operator()(const _Tp& __x, const _Tp& __y) const 273 {return static_cast<const _Pred&>(*this)(__x.first, __y.first);} 274 _LIBCPP_INLINE_VISIBILITY 275 bool operator()(const typename _Tp::first_type& __x, const _Tp& __y) const 276 {return static_cast<const _Pred&>(*this)(__x, __y.first);} 277 _LIBCPP_INLINE_VISIBILITY 278 bool operator()(const _Tp& __x, const typename _Tp::first_type& __y) const 279 {return static_cast<const _Pred&>(*this)(__x.first, __y);} 280 _LIBCPP_INLINE_VISIBILITY 281 bool operator()(const typename _Tp::first_type& __x, 282 const typename _Tp::first_type& __y) const 283 {return static_cast<const _Pred&>(*this)(__x, __y);} 284}; 285 286template <class _Tp, class _Pred> 287class __hash_map_equal<_Tp, _Pred, false> 288{ 289 _Pred __pred_; 290public: 291 _LIBCPP_INLINE_VISIBILITY __hash_map_equal() : __pred_() {} 292 _LIBCPP_INLINE_VISIBILITY __hash_map_equal(const _Pred& __p) : __pred_(__p) {} 293 _LIBCPP_INLINE_VISIBILITY const _Pred& key_eq() const {return __pred_;} 294 _LIBCPP_INLINE_VISIBILITY 295 bool operator()(const _Tp& __x, const _Tp& __y) const 296 {return __pred_(__x.first, __y.first);} 297 _LIBCPP_INLINE_VISIBILITY 298 bool operator()(const typename _Tp::first_type& __x, const _Tp& __y) const 299 {return __pred_(__x, __y.first);} 300 _LIBCPP_INLINE_VISIBILITY 301 bool operator()(const _Tp& __x, const typename _Tp::first_type& __y) const 302 {return __pred_(__x.first, __y);} 303 _LIBCPP_INLINE_VISIBILITY 304 bool operator()(const typename _Tp::first_type& __x, 305 const typename _Tp::first_type& __y) const 306 {return __pred_(__x, __y);} 307}; 308 309template <class _Alloc> 310class __hash_map_node_destructor 311{ 312 typedef _Alloc allocator_type; 313 typedef std::allocator_traits<allocator_type> __alloc_traits; 314 typedef typename __alloc_traits::value_type::__node_value_type value_type; 315public: 316 typedef typename __alloc_traits::pointer pointer; 317private: 318 typedef typename value_type::first_type first_type; 319 typedef typename value_type::second_type second_type; 320 321 allocator_type& __na_; 322 323public: 324 bool __first_constructed; 325 bool __second_constructed; 326 327 __hash_map_node_destructor(__hash_map_node_destructor const&) = default; 328 __hash_map_node_destructor& operator=(const __hash_map_node_destructor&) = delete; 329 330 _LIBCPP_INLINE_VISIBILITY 331 explicit __hash_map_node_destructor(allocator_type& __na) 332 : __na_(__na), 333 __first_constructed(false), 334 __second_constructed(false) 335 {} 336 337#ifndef _LIBCPP_CXX03_LANG 338 _LIBCPP_INLINE_VISIBILITY 339 __hash_map_node_destructor(std::__hash_node_destructor<allocator_type>&& __x) 340 : __na_(__x.__na_), 341 __first_constructed(__x.__value_constructed), 342 __second_constructed(__x.__value_constructed) 343 { 344 __x.__value_constructed = false; 345 } 346#else // _LIBCPP_CXX03_LANG 347 _LIBCPP_INLINE_VISIBILITY 348 __hash_map_node_destructor(const std::__hash_node_destructor<allocator_type>& __x) 349 : __na_(__x.__na_), 350 __first_constructed(__x.__value_constructed), 351 __second_constructed(__x.__value_constructed) 352 { 353 const_cast<bool&>(__x.__value_constructed) = false; 354 } 355#endif // _LIBCPP_CXX03_LANG 356 357 _LIBCPP_INLINE_VISIBILITY 358 void operator()(pointer __p) 359 { 360 if (__second_constructed) 361 __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.second)); 362 if (__first_constructed) 363 __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.first)); 364 if (__p) 365 __alloc_traits::deallocate(__na_, __p, 1); 366 } 367}; 368 369template <class _HashIterator> 370class _LIBCPP_TEMPLATE_VIS __hash_map_iterator 371{ 372 _HashIterator __i_; 373 374 typedef const typename _HashIterator::value_type::first_type key_type; 375 typedef typename _HashIterator::value_type::second_type mapped_type; 376public: 377 typedef std::forward_iterator_tag iterator_category; 378 typedef std::pair<key_type, mapped_type> value_type; 379 typedef typename _HashIterator::difference_type difference_type; 380 typedef value_type& reference; 381 typedef std::__rebind_pointer_t<typename _HashIterator::pointer, value_type> 382 pointer; 383 384 _LIBCPP_INLINE_VISIBILITY __hash_map_iterator() {} 385 386 _LIBCPP_INLINE_VISIBILITY __hash_map_iterator(_HashIterator __i) : __i_(__i) {} 387 388 _LIBCPP_INLINE_VISIBILITY reference operator*() const {return *operator->();} 389 _LIBCPP_INLINE_VISIBILITY pointer operator->() const {return (pointer)__i_.operator->();} 390 391 _LIBCPP_INLINE_VISIBILITY __hash_map_iterator& operator++() {++__i_; return *this;} 392 _LIBCPP_INLINE_VISIBILITY 393 __hash_map_iterator operator++(int) 394 { 395 __hash_map_iterator __t(*this); 396 ++(*this); 397 return __t; 398 } 399 400 friend _LIBCPP_INLINE_VISIBILITY 401 bool operator==(const __hash_map_iterator& __x, const __hash_map_iterator& __y) 402 {return __x.__i_ == __y.__i_;} 403 friend _LIBCPP_INLINE_VISIBILITY 404 bool operator!=(const __hash_map_iterator& __x, const __hash_map_iterator& __y) 405 {return __x.__i_ != __y.__i_;} 406 407 template <class, class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS hash_map; 408 template <class, class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS hash_multimap; 409 template <class> friend class _LIBCPP_TEMPLATE_VIS __hash_const_iterator; 410 template <class> friend class _LIBCPP_TEMPLATE_VIS __hash_const_local_iterator; 411 template <class> friend class _LIBCPP_TEMPLATE_VIS __hash_map_const_iterator; 412}; 413 414template <class _HashIterator> 415class _LIBCPP_TEMPLATE_VIS __hash_map_const_iterator 416{ 417 _HashIterator __i_; 418 419 typedef const typename _HashIterator::value_type::first_type key_type; 420 typedef typename _HashIterator::value_type::second_type mapped_type; 421public: 422 typedef std::forward_iterator_tag iterator_category; 423 typedef std::pair<key_type, mapped_type> value_type; 424 typedef typename _HashIterator::difference_type difference_type; 425 typedef const value_type& reference; 426 typedef std::__rebind_pointer_t<typename _HashIterator::pointer, const value_type> 427 pointer; 428 429 _LIBCPP_INLINE_VISIBILITY __hash_map_const_iterator() {} 430 431 _LIBCPP_INLINE_VISIBILITY 432 __hash_map_const_iterator(_HashIterator __i) : __i_(__i) {} 433 _LIBCPP_INLINE_VISIBILITY 434 __hash_map_const_iterator( 435 __hash_map_iterator<typename _HashIterator::__non_const_iterator> __i) 436 : __i_(__i.__i_) {} 437 438 _LIBCPP_INLINE_VISIBILITY 439 reference operator*() const {return *operator->();} 440 _LIBCPP_INLINE_VISIBILITY 441 pointer operator->() const {return (pointer)__i_.operator->();} 442 443 _LIBCPP_INLINE_VISIBILITY 444 __hash_map_const_iterator& operator++() {++__i_; return *this;} 445 _LIBCPP_INLINE_VISIBILITY 446 __hash_map_const_iterator operator++(int) 447 { 448 __hash_map_const_iterator __t(*this); 449 ++(*this); 450 return __t; 451 } 452 453 friend _LIBCPP_INLINE_VISIBILITY 454 bool operator==(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y) 455 {return __x.__i_ == __y.__i_;} 456 friend _LIBCPP_INLINE_VISIBILITY 457 bool operator!=(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y) 458 {return __x.__i_ != __y.__i_;} 459 460 template <class, class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS hash_map; 461 template <class, class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS hash_multimap; 462 template <class> friend class _LIBCPP_TEMPLATE_VIS __hash_const_iterator; 463 template <class> friend class _LIBCPP_TEMPLATE_VIS __hash_const_local_iterator; 464}; 465 466template <class _Key, class _Tp, class _Hash = hash<_Key>, class _Pred = std::equal_to<_Key>, 467 class _Alloc = std::allocator<std::pair<const _Key, _Tp> > > 468class _LIBCPP_TEMPLATE_VIS hash_map 469{ 470public: 471 // types 472 typedef _Key key_type; 473 typedef _Tp mapped_type; 474 typedef _Tp data_type; 475 typedef _Hash hasher; 476 typedef _Pred key_equal; 477 typedef _Alloc allocator_type; 478 typedef std::pair<const key_type, mapped_type> value_type; 479 typedef value_type& reference; 480 typedef const value_type& const_reference; 481 482private: 483 typedef std::pair<key_type, mapped_type> __value_type; 484 typedef __hash_map_hasher<__value_type, hasher> __hasher; 485 typedef __hash_map_equal<__value_type, key_equal> __key_equal; 486 typedef std::__rebind_alloc<std::allocator_traits<allocator_type>, __value_type> __allocator_type; 487 488 typedef std::__hash_table<__value_type, __hasher, 489 __key_equal, __allocator_type> __table; 490 491 __table __table_; 492 493 typedef typename __table::__node_pointer __node_pointer; 494 typedef typename __table::__node_const_pointer __node_const_pointer; 495 typedef typename __table::__node_traits __node_traits; 496 typedef typename __table::__node_allocator __node_allocator; 497 typedef typename __table::__node __node; 498 typedef __hash_map_node_destructor<__node_allocator> _Dp; 499 typedef std::unique_ptr<__node, _Dp> __node_holder; 500 typedef std::allocator_traits<allocator_type> __alloc_traits; 501public: 502 typedef typename __alloc_traits::pointer pointer; 503 typedef typename __alloc_traits::const_pointer const_pointer; 504 typedef typename __alloc_traits::size_type size_type; 505 typedef typename __alloc_traits::difference_type difference_type; 506 507 typedef __hash_map_iterator<typename __table::iterator> iterator; 508 typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator; 509 510 _LIBCPP_INLINE_VISIBILITY hash_map() { } 511 explicit hash_map(size_type __n, const hasher& __hf = hasher(), 512 const key_equal& __eql = key_equal()); 513 hash_map(size_type __n, const hasher& __hf, 514 const key_equal& __eql, 515 const allocator_type& __a); 516 template <class _InputIterator> 517 hash_map(_InputIterator __first, _InputIterator __last); 518 template <class _InputIterator> 519 hash_map(_InputIterator __first, _InputIterator __last, 520 size_type __n, const hasher& __hf = hasher(), 521 const key_equal& __eql = key_equal()); 522 template <class _InputIterator> 523 hash_map(_InputIterator __first, _InputIterator __last, 524 size_type __n, const hasher& __hf, 525 const key_equal& __eql, 526 const allocator_type& __a); 527 hash_map(const hash_map& __u); 528 529 _LIBCPP_INLINE_VISIBILITY 530 allocator_type get_allocator() const 531 {return allocator_type(__table_.__node_alloc());} 532 533 _LIBCPP_INLINE_VISIBILITY 534 bool empty() const {return __table_.size() == 0;} 535 _LIBCPP_INLINE_VISIBILITY 536 size_type size() const {return __table_.size();} 537 _LIBCPP_INLINE_VISIBILITY 538 size_type max_size() const {return __table_.max_size();} 539 540 _LIBCPP_INLINE_VISIBILITY 541 iterator begin() {return __table_.begin();} 542 _LIBCPP_INLINE_VISIBILITY 543 iterator end() {return __table_.end();} 544 _LIBCPP_INLINE_VISIBILITY 545 const_iterator begin() const {return __table_.begin();} 546 _LIBCPP_INLINE_VISIBILITY 547 const_iterator end() const {return __table_.end();} 548 549 _LIBCPP_INLINE_VISIBILITY 550 std::pair<iterator, bool> insert(const value_type& __x) 551 {return __table_.__insert_unique(__x);} 552 _LIBCPP_INLINE_VISIBILITY 553 iterator insert(const_iterator, const value_type& __x) {return insert(__x).first;} 554 template <class _InputIterator> 555 _LIBCPP_INLINE_VISIBILITY 556 void insert(_InputIterator __first, _InputIterator __last); 557 558 _LIBCPP_INLINE_VISIBILITY 559 void erase(const_iterator __p) {__table_.erase(__p.__i_);} 560 _LIBCPP_INLINE_VISIBILITY 561 size_type erase(const key_type& __k) {return __table_.__erase_unique(__k);} 562 _LIBCPP_INLINE_VISIBILITY 563 void erase(const_iterator __first, const_iterator __last) 564 {__table_.erase(__first.__i_, __last.__i_);} 565 _LIBCPP_INLINE_VISIBILITY 566 void clear() {__table_.clear();} 567 568 _LIBCPP_INLINE_VISIBILITY 569 void swap(hash_map& __u) {__table_.swap(__u.__table_);} 570 571 _LIBCPP_INLINE_VISIBILITY 572 hasher hash_funct() const 573 {return __table_.hash_function().hash_function();} 574 _LIBCPP_INLINE_VISIBILITY 575 key_equal key_eq() const 576 {return __table_.key_eq().key_eq();} 577 578 _LIBCPP_INLINE_VISIBILITY 579 iterator find(const key_type& __k) {return __table_.find(__k);} 580 _LIBCPP_INLINE_VISIBILITY 581 const_iterator find(const key_type& __k) const {return __table_.find(__k);} 582 _LIBCPP_INLINE_VISIBILITY 583 size_type count(const key_type& __k) const {return __table_.__count_unique(__k);} 584 _LIBCPP_INLINE_VISIBILITY 585 std::pair<iterator, iterator> equal_range(const key_type& __k) 586 {return __table_.__equal_range_unique(__k);} 587 _LIBCPP_INLINE_VISIBILITY 588 std::pair<const_iterator, const_iterator> equal_range(const key_type& __k) const 589 {return __table_.__equal_range_unique(__k);} 590 591 mapped_type& operator[](const key_type& __k); 592 593 _LIBCPP_INLINE_VISIBILITY 594 size_type bucket_count() const {return __table_.bucket_count();} 595 _LIBCPP_INLINE_VISIBILITY 596 size_type max_bucket_count() const {return __table_.max_bucket_count();} 597 598 _LIBCPP_INLINE_VISIBILITY 599 size_type elems_in_bucket(size_type __n) const 600 {return __table_.bucket_size(__n);} 601 602 _LIBCPP_INLINE_VISIBILITY 603 void resize(size_type __n) {__table_.__rehash_unique(__n);} 604 605private: 606 __node_holder __construct_node(const key_type& __k); 607}; 608 609template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 610hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_map( 611 size_type __n, const hasher& __hf, const key_equal& __eql) 612 : __table_(__hf, __eql) 613{ 614 __table_.__rehash_unique(__n); 615} 616 617template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 618hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_map( 619 size_type __n, const hasher& __hf, const key_equal& __eql, 620 const allocator_type& __a) 621 : __table_(__hf, __eql, __a) 622{ 623 __table_.__rehash_unique(__n); 624} 625 626template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 627template <class _InputIterator> 628hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_map( 629 _InputIterator __first, _InputIterator __last) 630{ 631 insert(__first, __last); 632} 633 634template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 635template <class _InputIterator> 636hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_map( 637 _InputIterator __first, _InputIterator __last, size_type __n, 638 const hasher& __hf, const key_equal& __eql) 639 : __table_(__hf, __eql) 640{ 641 __table_.__rehash_unique(__n); 642 insert(__first, __last); 643} 644 645template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 646template <class _InputIterator> 647hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_map( 648 _InputIterator __first, _InputIterator __last, size_type __n, 649 const hasher& __hf, const key_equal& __eql, const allocator_type& __a) 650 : __table_(__hf, __eql, __a) 651{ 652 __table_.__rehash_unique(__n); 653 insert(__first, __last); 654} 655 656template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 657hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_map( 658 const hash_map& __u) 659 : __table_(__u.__table_) 660{ 661 __table_.__rehash_unique(__u.bucket_count()); 662 insert(__u.begin(), __u.end()); 663} 664 665template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 666typename hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder 667hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(const key_type& __k) 668{ 669 __node_allocator& __na = __table_.__node_alloc(); 670 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 671 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.first), __k); 672 __h.get_deleter().__first_constructed = true; 673 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.second)); 674 __h.get_deleter().__second_constructed = true; 675 return __h; 676} 677 678template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 679template <class _InputIterator> 680inline 681void 682hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, 683 _InputIterator __last) 684{ 685 for (; __first != __last; ++__first) 686 __table_.__insert_unique(*__first); 687} 688 689template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 690_Tp& 691hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](const key_type& __k) 692{ 693 iterator __i = find(__k); 694 if (__i != end()) 695 return __i->second; 696 __node_holder __h = __construct_node(__k); 697 std::pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get()); 698 __h.release(); 699 return __r.first->second; 700} 701 702template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 703inline _LIBCPP_INLINE_VISIBILITY 704void 705swap(hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 706 hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 707{ 708 __x.swap(__y); 709} 710 711template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 712_LIBCPP_HIDE_FROM_ABI bool 713operator==(const hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 714 const hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 715{ 716 if (__x.size() != __y.size()) 717 return false; 718 typedef typename hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator 719 const_iterator; 720 for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end(); 721 __i != __ex; ++__i) 722 { 723 const_iterator __j = __y.find(__i->first); 724 if (__j == __ey || !(*__i == *__j)) 725 return false; 726 } 727 return true; 728} 729 730template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 731inline _LIBCPP_INLINE_VISIBILITY 732bool 733operator!=(const hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 734 const hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 735{ 736 return !(__x == __y); 737} 738 739template <class _Key, class _Tp, class _Hash = hash<_Key>, class _Pred = std::equal_to<_Key>, 740 class _Alloc = std::allocator<std::pair<const _Key, _Tp> > > 741class _LIBCPP_TEMPLATE_VIS hash_multimap 742{ 743public: 744 // types 745 typedef _Key key_type; 746 typedef _Tp mapped_type; 747 typedef _Tp data_type; 748 typedef _Hash hasher; 749 typedef _Pred key_equal; 750 typedef _Alloc allocator_type; 751 typedef std::pair<const key_type, mapped_type> value_type; 752 typedef value_type& reference; 753 typedef const value_type& const_reference; 754 755private: 756 typedef std::pair<key_type, mapped_type> __value_type; 757 typedef __hash_map_hasher<__value_type, hasher> __hasher; 758 typedef __hash_map_equal<__value_type, key_equal> __key_equal; 759 typedef std::__rebind_alloc<std::allocator_traits<allocator_type>, __value_type> __allocator_type; 760 761 typedef std::__hash_table<__value_type, __hasher, 762 __key_equal, __allocator_type> __table; 763 764 __table __table_; 765 766 typedef typename __table::__node_traits __node_traits; 767 typedef typename __table::__node_allocator __node_allocator; 768 typedef typename __table::__node __node; 769 typedef __hash_map_node_destructor<__node_allocator> _Dp; 770 typedef std::unique_ptr<__node, _Dp> __node_holder; 771 typedef std::allocator_traits<allocator_type> __alloc_traits; 772public: 773 typedef typename __alloc_traits::pointer pointer; 774 typedef typename __alloc_traits::const_pointer const_pointer; 775 typedef typename __alloc_traits::size_type size_type; 776 typedef typename __alloc_traits::difference_type difference_type; 777 778 typedef __hash_map_iterator<typename __table::iterator> iterator; 779 typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator; 780 781 _LIBCPP_INLINE_VISIBILITY 782 hash_multimap() { } 783 explicit hash_multimap(size_type __n, const hasher& __hf = hasher(), 784 const key_equal& __eql = key_equal()); 785 hash_multimap(size_type __n, const hasher& __hf, 786 const key_equal& __eql, 787 const allocator_type& __a); 788 template <class _InputIterator> 789 hash_multimap(_InputIterator __first, _InputIterator __last); 790 template <class _InputIterator> 791 hash_multimap(_InputIterator __first, _InputIterator __last, 792 size_type __n, const hasher& __hf = hasher(), 793 const key_equal& __eql = key_equal()); 794 template <class _InputIterator> 795 hash_multimap(_InputIterator __first, _InputIterator __last, 796 size_type __n, const hasher& __hf, 797 const key_equal& __eql, 798 const allocator_type& __a); 799 hash_multimap(const hash_multimap& __u); 800 801 _LIBCPP_INLINE_VISIBILITY 802 allocator_type get_allocator() const 803 {return allocator_type(__table_.__node_alloc());} 804 805 _LIBCPP_INLINE_VISIBILITY 806 bool empty() const {return __table_.size() == 0;} 807 _LIBCPP_INLINE_VISIBILITY 808 size_type size() const {return __table_.size();} 809 _LIBCPP_INLINE_VISIBILITY 810 size_type max_size() const {return __table_.max_size();} 811 812 _LIBCPP_INLINE_VISIBILITY 813 iterator begin() {return __table_.begin();} 814 _LIBCPP_INLINE_VISIBILITY 815 iterator end() {return __table_.end();} 816 _LIBCPP_INLINE_VISIBILITY 817 const_iterator begin() const {return __table_.begin();} 818 _LIBCPP_INLINE_VISIBILITY 819 const_iterator end() const {return __table_.end();} 820 821 _LIBCPP_INLINE_VISIBILITY 822 iterator insert(const value_type& __x) {return __table_.__insert_multi(__x);} 823 _LIBCPP_INLINE_VISIBILITY 824 iterator insert(const_iterator, const value_type& __x) {return insert(__x);} 825 template <class _InputIterator> 826 _LIBCPP_INLINE_VISIBILITY 827 void insert(_InputIterator __first, _InputIterator __last); 828 829 _LIBCPP_INLINE_VISIBILITY 830 void erase(const_iterator __p) {__table_.erase(__p.__i_);} 831 _LIBCPP_INLINE_VISIBILITY 832 size_type erase(const key_type& __k) {return __table_.__erase_multi(__k);} 833 _LIBCPP_INLINE_VISIBILITY 834 void erase(const_iterator __first, const_iterator __last) 835 {__table_.erase(__first.__i_, __last.__i_);} 836 _LIBCPP_INLINE_VISIBILITY 837 void clear() {__table_.clear();} 838 839 _LIBCPP_INLINE_VISIBILITY 840 void swap(hash_multimap& __u) {__table_.swap(__u.__table_);} 841 842 _LIBCPP_INLINE_VISIBILITY 843 hasher hash_funct() const 844 {return __table_.hash_function().hash_function();} 845 _LIBCPP_INLINE_VISIBILITY 846 key_equal key_eq() const 847 {return __table_.key_eq().key_eq();} 848 849 _LIBCPP_INLINE_VISIBILITY 850 iterator find(const key_type& __k) {return __table_.find(__k);} 851 _LIBCPP_INLINE_VISIBILITY 852 const_iterator find(const key_type& __k) const {return __table_.find(__k);} 853 _LIBCPP_INLINE_VISIBILITY 854 size_type count(const key_type& __k) const {return __table_.__count_multi(__k);} 855 _LIBCPP_INLINE_VISIBILITY 856 std::pair<iterator, iterator> equal_range(const key_type& __k) 857 {return __table_.__equal_range_multi(__k);} 858 _LIBCPP_INLINE_VISIBILITY 859 std::pair<const_iterator, const_iterator> equal_range(const key_type& __k) const 860 {return __table_.__equal_range_multi(__k);} 861 862 _LIBCPP_INLINE_VISIBILITY 863 size_type bucket_count() const {return __table_.bucket_count();} 864 _LIBCPP_INLINE_VISIBILITY 865 size_type max_bucket_count() const {return __table_.max_bucket_count();} 866 867 _LIBCPP_INLINE_VISIBILITY 868 size_type elems_in_bucket(size_type __n) const 869 {return __table_.bucket_size(__n);} 870 871 _LIBCPP_INLINE_VISIBILITY 872 void resize(size_type __n) {__table_.__rehash_multi(__n);} 873}; 874 875template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 876hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_multimap( 877 size_type __n, const hasher& __hf, const key_equal& __eql) 878 : __table_(__hf, __eql) 879{ 880 __table_.__rehash_multi(__n); 881} 882 883template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 884hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_multimap( 885 size_type __n, const hasher& __hf, const key_equal& __eql, 886 const allocator_type& __a) 887 : __table_(__hf, __eql, __a) 888{ 889 __table_.__rehash_multi(__n); 890} 891 892template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 893template <class _InputIterator> 894hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_multimap( 895 _InputIterator __first, _InputIterator __last) 896{ 897 insert(__first, __last); 898} 899 900template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 901template <class _InputIterator> 902hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_multimap( 903 _InputIterator __first, _InputIterator __last, size_type __n, 904 const hasher& __hf, const key_equal& __eql) 905 : __table_(__hf, __eql) 906{ 907 __table_.__rehash_multi(__n); 908 insert(__first, __last); 909} 910 911template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 912template <class _InputIterator> 913hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_multimap( 914 _InputIterator __first, _InputIterator __last, size_type __n, 915 const hasher& __hf, const key_equal& __eql, const allocator_type& __a) 916 : __table_(__hf, __eql, __a) 917{ 918 __table_.__rehash_multi(__n); 919 insert(__first, __last); 920} 921 922template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 923hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_multimap( 924 const hash_multimap& __u) 925 : __table_(__u.__table_) 926{ 927 __table_.__rehash_multi(__u.bucket_count()); 928 insert(__u.begin(), __u.end()); 929} 930 931template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 932template <class _InputIterator> 933inline 934void 935hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, 936 _InputIterator __last) 937{ 938 for (; __first != __last; ++__first) 939 __table_.__insert_multi(*__first); 940} 941 942template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 943inline _LIBCPP_INLINE_VISIBILITY 944void 945swap(hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 946 hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 947{ 948 __x.swap(__y); 949} 950 951template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 952_LIBCPP_HIDE_FROM_ABI bool 953operator==(const hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 954 const hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 955{ 956 if (__x.size() != __y.size()) 957 return false; 958 typedef typename hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator 959 const_iterator; 960 typedef std::pair<const_iterator, const_iterator> _EqRng; 961 for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;) 962 { 963 _EqRng __xeq = __x.equal_range(__i->first); 964 _EqRng __yeq = __y.equal_range(__i->first); 965 if (_VSTD::distance(__xeq.first, __xeq.second) != 966 _VSTD::distance(__yeq.first, __yeq.second) || 967 !_VSTD::is_permutation(__xeq.first, __xeq.second, __yeq.first)) 968 return false; 969 __i = __xeq.second; 970 } 971 return true; 972} 973 974template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 975inline _LIBCPP_INLINE_VISIBILITY 976bool 977operator!=(const hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 978 const hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 979{ 980 return !(__x == __y); 981} 982 983} // namespace __gnu_cxx 984 985#if !defined(_LIBCPP_REMOVE_TRANSITIVE_INCLUDES) && _LIBCPP_STD_VER <= 20 986# include <concepts> 987# include <iterator> 988#endif 989 990#endif // _LIBCPP_HASH_MAP 991