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