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