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