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