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