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