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