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