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