1// -*- C++ -*- 2//===----------------------------------------------------------------------===// 3// 4// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 5// See https://llvm.org/LICENSE.txt for license information. 6// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 7// 8//===----------------------------------------------------------------------===// 9 10#ifndef _LIBCPP_HASH_MAP 11#define _LIBCPP_HASH_MAP 12 13/* 14 15 hash_map synopsis 16 17namespace __gnu_cxx 18{ 19 20template <class Key, class T, class Hash = hash<Key>, class Pred = equal_to<Key>, 21 class Alloc = allocator<pair<const Key, T>>> 22class hash_map 23{ 24public: 25 // types 26 typedef Key key_type; 27 typedef T mapped_type; 28 typedef Hash hasher; 29 typedef Pred key_equal; 30 typedef Alloc allocator_type; 31 typedef pair<const key_type, mapped_type> value_type; 32 typedef value_type& reference; 33 typedef const value_type& const_reference; 34 typedef typename allocator_traits<allocator_type>::pointer pointer; 35 typedef typename allocator_traits<allocator_type>::const_pointer const_pointer; 36 typedef typename allocator_traits<allocator_type>::size_type size_type; 37 typedef typename allocator_traits<allocator_type>::difference_type difference_type; 38 39 typedef /unspecified/ iterator; 40 typedef /unspecified/ const_iterator; 41 42 hash_map(); 43 explicit hash_map(size_type n, 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 template <class InputIterator> 49 hash_map(InputIterator f, InputIterator l, 50 size_type n, const hasher& hf = hasher(), 51 const key_equal& eql = key_equal(), 52 const allocator_type& a = allocator_type()); 53 hash_map(const hash_map&); 54 ~hash_map(); 55 hash_map& operator=(const hash_map&); 56 57 allocator_type get_allocator() const; 58 59 bool empty() const; 60 size_type size() const; 61 size_type max_size() const; 62 63 iterator begin(); 64 iterator end(); 65 const_iterator begin() const; 66 const_iterator end() const; 67 68 pair<iterator, bool> insert(const value_type& obj); 69 template <class InputIterator> 70 void insert(InputIterator first, InputIterator last); 71 72 void erase(const_iterator position); 73 size_type erase(const key_type& k); 74 void erase(const_iterator first, const_iterator last); 75 void clear(); 76 77 void swap(hash_map&); 78 79 hasher hash_funct() const; 80 key_equal key_eq() const; 81 82 iterator find(const key_type& k); 83 const_iterator find(const key_type& k) const; 84 size_type count(const key_type& k) const; 85 pair<iterator, iterator> equal_range(const key_type& k); 86 pair<const_iterator, const_iterator> equal_range(const key_type& k) const; 87 88 mapped_type& operator[](const key_type& k); 89 90 size_type bucket_count() const; 91 size_type max_bucket_count() const; 92 93 size_type elems_in_bucket(size_type n) const; 94 95 void resize(size_type n); 96}; 97 98template <class Key, class T, class Hash, class Pred, class Alloc> 99 void swap(hash_map<Key, T, Hash, Pred, Alloc>& x, 100 hash_map<Key, T, Hash, Pred, Alloc>& y); 101 102template <class Key, class T, class Hash, class Pred, class Alloc> 103 bool 104 operator==(const hash_map<Key, T, Hash, Pred, Alloc>& x, 105 const hash_map<Key, T, Hash, Pred, Alloc>& y); 106 107template <class Key, class T, class Hash, class Pred, class Alloc> 108 bool 109 operator!=(const hash_map<Key, T, Hash, Pred, Alloc>& x, 110 const hash_map<Key, T, Hash, Pred, Alloc>& y); 111 112template <class Key, class T, class Hash = hash<Key>, class Pred = equal_to<Key>, 113 class Alloc = allocator<pair<const Key, T>>> 114class hash_multimap 115{ 116public: 117 // types 118 typedef Key key_type; 119 typedef T mapped_type; 120 typedef Hash hasher; 121 typedef Pred key_equal; 122 typedef Alloc allocator_type; 123 typedef pair<const key_type, mapped_type> value_type; 124 typedef value_type& reference; 125 typedef const value_type& const_reference; 126 typedef typename allocator_traits<allocator_type>::pointer pointer; 127 typedef typename allocator_traits<allocator_type>::const_pointer const_pointer; 128 typedef typename allocator_traits<allocator_type>::size_type size_type; 129 typedef typename allocator_traits<allocator_type>::difference_type difference_type; 130 131 typedef /unspecified/ iterator; 132 typedef /unspecified/ const_iterator; 133 134 explicit hash_multimap(size_type n = 193, const hasher& hf = hasher(), 135 const key_equal& eql = key_equal(), 136 const allocator_type& a = allocator_type()); 137 template <class InputIterator> 138 hash_multimap(InputIterator f, InputIterator l, 139 size_type n = 193, const hasher& hf = hasher(), 140 const key_equal& eql = key_equal(), 141 const allocator_type& a = allocator_type()); 142 explicit hash_multimap(const allocator_type&); 143 hash_multimap(const hash_multimap&); 144 ~hash_multimap(); 145 hash_multimap& operator=(const hash_multimap&); 146 147 allocator_type get_allocator() const; 148 149 bool empty() const; 150 size_type size() const; 151 size_type max_size() const; 152 153 iterator begin(); 154 iterator end(); 155 const_iterator begin() const; 156 const_iterator end() const; 157 158 iterator insert(const value_type& obj); 159 template <class InputIterator> 160 void insert(InputIterator first, InputIterator last); 161 162 void erase(const_iterator position); 163 size_type erase(const key_type& k); 164 void erase(const_iterator first, const_iterator last); 165 void clear(); 166 167 void swap(hash_multimap&); 168 169 hasher hash_funct() const; 170 key_equal key_eq() const; 171 172 iterator find(const key_type& k); 173 const_iterator find(const key_type& k) const; 174 size_type count(const key_type& k) const; 175 pair<iterator, iterator> equal_range(const key_type& k); 176 pair<const_iterator, const_iterator> equal_range(const key_type& k) const; 177 178 size_type bucket_count() const; 179 size_type max_bucket_count() const; 180 181 size_type elems_in_bucket(size_type n) const; 182 183 void resize(size_type n); 184}; 185 186template <class Key, class T, class Hash, class Pred, class Alloc> 187 void swap(hash_multimap<Key, T, Hash, Pred, Alloc>& x, 188 hash_multimap<Key, T, Hash, Pred, Alloc>& y); 189 190template <class Key, class T, class Hash, class Pred, class Alloc> 191 bool 192 operator==(const hash_multimap<Key, T, Hash, Pred, Alloc>& x, 193 const hash_multimap<Key, T, Hash, Pred, Alloc>& y); 194 195template <class Key, class T, class Hash, class Pred, class Alloc> 196 bool 197 operator!=(const hash_multimap<Key, T, Hash, Pred, Alloc>& x, 198 const hash_multimap<Key, T, Hash, Pred, Alloc>& y); 199 200} // __gnu_cxx 201 202*/ 203 204#if __cplusplus < 201103L && defined(_LIBCPP_USE_FROZEN_CXX03_HEADERS) 205# include <__cxx03/ext/hash_map> 206#else 207# include <__config> 208# include <__hash_table> 209# include <algorithm> 210# include <ext/__hash> 211# include <functional> 212 213# if defined(__DEPRECATED) && __DEPRECATED 214# if defined(_LIBCPP_WARNING) 215_LIBCPP_WARNING("Use of the header <ext/hash_map> is deprecated. Migrate to <unordered_map>") 216# else 217# warning Use of the header <ext/hash_map> is deprecated. Migrate to <unordered_map> 218# endif 219# endif 220 221# if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 222# pragma GCC system_header 223# endif 224 225namespace __gnu_cxx { 226 227template <class _Tp, class _Hash, bool = std::is_empty<_Hash>::value && !std::__libcpp_is_final<_Hash>::value > 228class __hash_map_hasher : private _Hash { 229public: 230 _LIBCPP_HIDE_FROM_ABI __hash_map_hasher() : _Hash() {} 231 _LIBCPP_HIDE_FROM_ABI __hash_map_hasher(const _Hash& __h) : _Hash(__h) {} 232 _LIBCPP_HIDE_FROM_ABI const _Hash& hash_function() const { return *this; } 233 _LIBCPP_HIDE_FROM_ABI size_t operator()(const _Tp& __x) const { return static_cast<const _Hash&>(*this)(__x.first); } 234 _LIBCPP_HIDE_FROM_ABI size_t operator()(const typename _Tp::first_type& __x) const { 235 return static_cast<const _Hash&>(*this)(__x); 236 } 237}; 238 239template <class _Tp, class _Hash> 240class __hash_map_hasher<_Tp, _Hash, false> { 241 _Hash __hash_; 242 243public: 244 _LIBCPP_HIDE_FROM_ABI __hash_map_hasher() : __hash_() {} 245 _LIBCPP_HIDE_FROM_ABI __hash_map_hasher(const _Hash& __h) : __hash_(__h) {} 246 _LIBCPP_HIDE_FROM_ABI const _Hash& hash_function() const { return __hash_; } 247 _LIBCPP_HIDE_FROM_ABI size_t operator()(const _Tp& __x) const { return __hash_(__x.first); } 248 _LIBCPP_HIDE_FROM_ABI size_t operator()(const typename _Tp::first_type& __x) const { return __hash_(__x); } 249}; 250 251template <class _Tp, class _Pred, bool = std::is_empty<_Pred>::value && !std::__libcpp_is_final<_Pred>::value > 252class __hash_map_equal : private _Pred { 253public: 254 _LIBCPP_HIDE_FROM_ABI __hash_map_equal() : _Pred() {} 255 _LIBCPP_HIDE_FROM_ABI __hash_map_equal(const _Pred& __p) : _Pred(__p) {} 256 _LIBCPP_HIDE_FROM_ABI const _Pred& key_eq() const { return *this; } 257 _LIBCPP_HIDE_FROM_ABI bool operator()(const _Tp& __x, const _Tp& __y) const { 258 return static_cast<const _Pred&>(*this)(__x.first, __y.first); 259 } 260 _LIBCPP_HIDE_FROM_ABI bool operator()(const typename _Tp::first_type& __x, const _Tp& __y) const { 261 return static_cast<const _Pred&>(*this)(__x, __y.first); 262 } 263 _LIBCPP_HIDE_FROM_ABI bool operator()(const _Tp& __x, const typename _Tp::first_type& __y) const { 264 return static_cast<const _Pred&>(*this)(__x.first, __y); 265 } 266 _LIBCPP_HIDE_FROM_ABI bool 267 operator()(const typename _Tp::first_type& __x, const typename _Tp::first_type& __y) const { 268 return static_cast<const _Pred&>(*this)(__x, __y); 269 } 270}; 271 272template <class _Tp, class _Pred> 273class __hash_map_equal<_Tp, _Pred, false> { 274 _Pred __pred_; 275 276public: 277 _LIBCPP_HIDE_FROM_ABI __hash_map_equal() : __pred_() {} 278 _LIBCPP_HIDE_FROM_ABI __hash_map_equal(const _Pred& __p) : __pred_(__p) {} 279 _LIBCPP_HIDE_FROM_ABI const _Pred& key_eq() const { return __pred_; } 280 _LIBCPP_HIDE_FROM_ABI bool operator()(const _Tp& __x, const _Tp& __y) const { return __pred_(__x.first, __y.first); } 281 _LIBCPP_HIDE_FROM_ABI bool operator()(const typename _Tp::first_type& __x, const _Tp& __y) const { 282 return __pred_(__x, __y.first); 283 } 284 _LIBCPP_HIDE_FROM_ABI bool operator()(const _Tp& __x, const typename _Tp::first_type& __y) const { 285 return __pred_(__x.first, __y); 286 } 287 _LIBCPP_HIDE_FROM_ABI bool 288 operator()(const typename _Tp::first_type& __x, const typename _Tp::first_type& __y) const { 289 return __pred_(__x, __y); 290 } 291}; 292 293template <class _Alloc> 294class __hash_map_node_destructor { 295 typedef _Alloc allocator_type; 296 typedef std::allocator_traits<allocator_type> __alloc_traits; 297 typedef typename __alloc_traits::value_type::__node_value_type value_type; 298 299public: 300 typedef typename __alloc_traits::pointer pointer; 301 302private: 303 typedef typename value_type::first_type first_type; 304 typedef typename value_type::second_type second_type; 305 306 allocator_type& __na_; 307 308public: 309 bool __first_constructed; 310 bool __second_constructed; 311 312 _LIBCPP_HIDE_FROM_ABI __hash_map_node_destructor(__hash_map_node_destructor const&) = default; 313 __hash_map_node_destructor& operator=(const __hash_map_node_destructor&) = delete; 314 315 _LIBCPP_HIDE_FROM_ABI explicit __hash_map_node_destructor(allocator_type& __na) 316 : __na_(__na), __first_constructed(false), __second_constructed(false) {} 317 318# ifndef _LIBCPP_CXX03_LANG 319 _LIBCPP_HIDE_FROM_ABI __hash_map_node_destructor(std::__hash_node_destructor<allocator_type>&& __x) 320 : __na_(__x.__na_), __first_constructed(__x.__value_constructed), __second_constructed(__x.__value_constructed) { 321 __x.__value_constructed = false; 322 } 323# else // _LIBCPP_CXX03_LANG 324 _LIBCPP_HIDE_FROM_ABI __hash_map_node_destructor(const std::__hash_node_destructor<allocator_type>& __x) 325 : __na_(__x.__na_), __first_constructed(__x.__value_constructed), __second_constructed(__x.__value_constructed) { 326 const_cast<bool&>(__x.__value_constructed) = false; 327 } 328# endif // _LIBCPP_CXX03_LANG 329 330 _LIBCPP_HIDE_FROM_ABI void operator()(pointer __p) { 331 if (__second_constructed) 332 __alloc_traits::destroy(__na_, std::addressof(__p->__get_value().second)); 333 if (__first_constructed) 334 __alloc_traits::destroy(__na_, std::addressof(__p->__get_value().first)); 335 if (__p) 336 __alloc_traits::deallocate(__na_, __p, 1); 337 } 338}; 339 340template <class _HashIterator> 341class _LIBCPP_TEMPLATE_VIS __hash_map_iterator { 342 _HashIterator __i_; 343 344 typedef const typename _HashIterator::value_type::first_type key_type; 345 typedef typename _HashIterator::value_type::second_type mapped_type; 346 347public: 348 typedef std::forward_iterator_tag iterator_category; 349 typedef std::pair<key_type, mapped_type> value_type; 350 typedef typename _HashIterator::difference_type difference_type; 351 typedef value_type& reference; 352 typedef std::__rebind_pointer_t<typename _HashIterator::pointer, value_type> pointer; 353 354 _LIBCPP_HIDE_FROM_ABI __hash_map_iterator() {} 355 356 _LIBCPP_HIDE_FROM_ABI __hash_map_iterator(_HashIterator __i) : __i_(__i) {} 357 358 _LIBCPP_HIDE_FROM_ABI reference operator*() const { return *operator->(); } 359 _LIBCPP_HIDE_FROM_ABI pointer operator->() const { return (pointer)__i_.operator->(); } 360 361 _LIBCPP_HIDE_FROM_ABI __hash_map_iterator& operator++() { 362 ++__i_; 363 return *this; 364 } 365 _LIBCPP_HIDE_FROM_ABI __hash_map_iterator operator++(int) { 366 __hash_map_iterator __t(*this); 367 ++(*this); 368 return __t; 369 } 370 371 friend _LIBCPP_HIDE_FROM_ABI bool operator==(const __hash_map_iterator& __x, const __hash_map_iterator& __y) { 372 return __x.__i_ == __y.__i_; 373 } 374 friend _LIBCPP_HIDE_FROM_ABI bool operator!=(const __hash_map_iterator& __x, const __hash_map_iterator& __y) { 375 return __x.__i_ != __y.__i_; 376 } 377 378 template <class, class, class, class, class> 379 friend class _LIBCPP_TEMPLATE_VIS hash_map; 380 template <class, class, class, class, class> 381 friend class _LIBCPP_TEMPLATE_VIS hash_multimap; 382 template <class> 383 friend class _LIBCPP_TEMPLATE_VIS __hash_const_iterator; 384 template <class> 385 friend class _LIBCPP_TEMPLATE_VIS __hash_const_local_iterator; 386 template <class> 387 friend class _LIBCPP_TEMPLATE_VIS __hash_map_const_iterator; 388}; 389 390template <class _HashIterator> 391class _LIBCPP_TEMPLATE_VIS __hash_map_const_iterator { 392 _HashIterator __i_; 393 394 typedef const typename _HashIterator::value_type::first_type key_type; 395 typedef typename _HashIterator::value_type::second_type mapped_type; 396 397public: 398 typedef std::forward_iterator_tag iterator_category; 399 typedef std::pair<key_type, mapped_type> value_type; 400 typedef typename _HashIterator::difference_type difference_type; 401 typedef const value_type& reference; 402 typedef std::__rebind_pointer_t<typename _HashIterator::pointer, const value_type> pointer; 403 404 _LIBCPP_HIDE_FROM_ABI __hash_map_const_iterator() {} 405 406 _LIBCPP_HIDE_FROM_ABI __hash_map_const_iterator(_HashIterator __i) : __i_(__i) {} 407 _LIBCPP_HIDE_FROM_ABI __hash_map_const_iterator(__hash_map_iterator<typename _HashIterator::__non_const_iterator> __i) 408 : __i_(__i.__i_) {} 409 410 _LIBCPP_HIDE_FROM_ABI reference operator*() const { return *operator->(); } 411 _LIBCPP_HIDE_FROM_ABI pointer operator->() const { return (pointer)__i_.operator->(); } 412 413 _LIBCPP_HIDE_FROM_ABI __hash_map_const_iterator& operator++() { 414 ++__i_; 415 return *this; 416 } 417 _LIBCPP_HIDE_FROM_ABI __hash_map_const_iterator operator++(int) { 418 __hash_map_const_iterator __t(*this); 419 ++(*this); 420 return __t; 421 } 422 423 friend _LIBCPP_HIDE_FROM_ABI bool 424 operator==(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y) { 425 return __x.__i_ == __y.__i_; 426 } 427 friend _LIBCPP_HIDE_FROM_ABI bool 428 operator!=(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y) { 429 return __x.__i_ != __y.__i_; 430 } 431 432 template <class, class, class, class, class> 433 friend class _LIBCPP_TEMPLATE_VIS hash_map; 434 template <class, class, class, class, class> 435 friend class _LIBCPP_TEMPLATE_VIS hash_multimap; 436 template <class> 437 friend class _LIBCPP_TEMPLATE_VIS __hash_const_iterator; 438 template <class> 439 friend class _LIBCPP_TEMPLATE_VIS __hash_const_local_iterator; 440}; 441 442template <class _Key, 443 class _Tp, 444 class _Hash = hash<_Key>, 445 class _Pred = std::equal_to<_Key>, 446 class _Alloc = std::allocator<std::pair<const _Key, _Tp> > > 447class _LIBCPP_TEMPLATE_VIS hash_map { 448public: 449 // types 450 typedef _Key key_type; 451 typedef _Tp mapped_type; 452 typedef _Tp data_type; 453 typedef _Hash hasher; 454 typedef _Pred key_equal; 455 typedef _Alloc allocator_type; 456 typedef std::pair<const key_type, mapped_type> value_type; 457 typedef value_type& reference; 458 typedef const value_type& const_reference; 459 460private: 461 typedef std::pair<key_type, mapped_type> __value_type; 462 typedef __hash_map_hasher<__value_type, hasher> __hasher; 463 typedef __hash_map_equal<__value_type, key_equal> __key_equal; 464 typedef std::__rebind_alloc<std::allocator_traits<allocator_type>, __value_type> __allocator_type; 465 466 typedef std::__hash_table<__value_type, __hasher, __key_equal, __allocator_type> __table; 467 468 __table __table_; 469 470 typedef typename __table::__node_pointer __node_pointer; 471 typedef typename __table::__node_const_pointer __node_const_pointer; 472 typedef typename __table::__node_traits __node_traits; 473 typedef typename __table::__node_allocator __node_allocator; 474 typedef typename __table::__node __node; 475 typedef __hash_map_node_destructor<__node_allocator> _Dp; 476 typedef std::unique_ptr<__node, _Dp> __node_holder; 477 typedef std::allocator_traits<allocator_type> __alloc_traits; 478 479public: 480 typedef typename __alloc_traits::pointer pointer; 481 typedef typename __alloc_traits::const_pointer const_pointer; 482 typedef typename __alloc_traits::size_type size_type; 483 typedef typename __alloc_traits::difference_type difference_type; 484 485 typedef __hash_map_iterator<typename __table::iterator> iterator; 486 typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator; 487 488 _LIBCPP_HIDE_FROM_ABI hash_map() {} 489 explicit _LIBCPP_HIDE_FROM_ABI 490 hash_map(size_type __n, const hasher& __hf = hasher(), const key_equal& __eql = key_equal()); 491 _LIBCPP_HIDE_FROM_ABI hash_map(size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a); 492 template <class _InputIterator> 493 _LIBCPP_HIDE_FROM_ABI hash_map(_InputIterator __first, _InputIterator __last); 494 template <class _InputIterator> 495 _LIBCPP_HIDE_FROM_ABI 496 hash_map(_InputIterator __first, 497 _InputIterator __last, 498 size_type __n, 499 const hasher& __hf = hasher(), 500 const key_equal& __eql = key_equal()); 501 template <class _InputIterator> 502 _LIBCPP_HIDE_FROM_ABI 503 hash_map(_InputIterator __first, 504 _InputIterator __last, 505 size_type __n, 506 const hasher& __hf, 507 const key_equal& __eql, 508 const allocator_type& __a); 509 _LIBCPP_HIDE_FROM_ABI hash_map(const hash_map& __u); 510 511 _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const { return allocator_type(__table_.__node_alloc()); } 512 513 _LIBCPP_HIDE_FROM_ABI bool empty() const { return __table_.size() == 0; } 514 _LIBCPP_HIDE_FROM_ABI size_type size() const { return __table_.size(); } 515 _LIBCPP_HIDE_FROM_ABI size_type max_size() const { return __table_.max_size(); } 516 517 _LIBCPP_HIDE_FROM_ABI iterator begin() { return __table_.begin(); } 518 _LIBCPP_HIDE_FROM_ABI iterator end() { return __table_.end(); } 519 _LIBCPP_HIDE_FROM_ABI const_iterator begin() const { return __table_.begin(); } 520 _LIBCPP_HIDE_FROM_ABI const_iterator end() const { return __table_.end(); } 521 522 _LIBCPP_HIDE_FROM_ABI std::pair<iterator, bool> insert(const value_type& __x) { 523 return __table_.__insert_unique(__x); 524 } 525 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator, const value_type& __x) { return insert(__x).first; } 526 template <class _InputIterator> 527 _LIBCPP_HIDE_FROM_ABI void insert(_InputIterator __first, _InputIterator __last); 528 529 _LIBCPP_HIDE_FROM_ABI void erase(const_iterator __p) { __table_.erase(__p.__i_); } 530 _LIBCPP_HIDE_FROM_ABI size_type erase(const key_type& __k) { return __table_.__erase_unique(__k); } 531 _LIBCPP_HIDE_FROM_ABI void erase(const_iterator __first, const_iterator __last) { 532 __table_.erase(__first.__i_, __last.__i_); 533 } 534 _LIBCPP_HIDE_FROM_ABI void clear() { __table_.clear(); } 535 536 _LIBCPP_HIDE_FROM_ABI void swap(hash_map& __u) { __table_.swap(__u.__table_); } 537 538 _LIBCPP_HIDE_FROM_ABI hasher hash_funct() const { return __table_.hash_function().hash_function(); } 539 _LIBCPP_HIDE_FROM_ABI key_equal key_eq() const { return __table_.key_eq().key_eq(); } 540 541 _LIBCPP_HIDE_FROM_ABI iterator find(const key_type& __k) { return __table_.find(__k); } 542 _LIBCPP_HIDE_FROM_ABI const_iterator find(const key_type& __k) const { return __table_.find(__k); } 543 _LIBCPP_HIDE_FROM_ABI size_type count(const key_type& __k) const { return __table_.__count_unique(__k); } 544 _LIBCPP_HIDE_FROM_ABI std::pair<iterator, iterator> equal_range(const key_type& __k) { 545 return __table_.__equal_range_unique(__k); 546 } 547 _LIBCPP_HIDE_FROM_ABI std::pair<const_iterator, const_iterator> equal_range(const key_type& __k) const { 548 return __table_.__equal_range_unique(__k); 549 } 550 551 _LIBCPP_HIDE_FROM_ABI mapped_type& operator[](const key_type& __k); 552 553 _LIBCPP_HIDE_FROM_ABI size_type bucket_count() const { return __table_.bucket_count(); } 554 _LIBCPP_HIDE_FROM_ABI size_type max_bucket_count() const { return __table_.max_bucket_count(); } 555 556 _LIBCPP_HIDE_FROM_ABI size_type elems_in_bucket(size_type __n) const { return __table_.bucket_size(__n); } 557 558 _LIBCPP_HIDE_FROM_ABI void resize(size_type __n) { __table_.__rehash_unique(__n); } 559 560private: 561 _LIBCPP_HIDE_FROM_ABI __node_holder __construct_node(const key_type& __k); 562}; 563 564template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 565hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_map(size_type __n, const hasher& __hf, const key_equal& __eql) 566 : __table_(__hf, __eql) { 567 __table_.__rehash_unique(__n); 568} 569 570template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 571hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_map( 572 size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a) 573 : __table_(__hf, __eql, __a) { 574 __table_.__rehash_unique(__n); 575} 576 577template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 578template <class _InputIterator> 579hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_map(_InputIterator __first, _InputIterator __last) { 580 insert(__first, __last); 581} 582 583template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 584template <class _InputIterator> 585hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_map( 586 _InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, const key_equal& __eql) 587 : __table_(__hf, __eql) { 588 __table_.__rehash_unique(__n); 589 insert(__first, __last); 590} 591 592template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 593template <class _InputIterator> 594hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_map( 595 _InputIterator __first, 596 _InputIterator __last, 597 size_type __n, 598 const hasher& __hf, 599 const key_equal& __eql, 600 const allocator_type& __a) 601 : __table_(__hf, __eql, __a) { 602 __table_.__rehash_unique(__n); 603 insert(__first, __last); 604} 605 606template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 607hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_map(const hash_map& __u) : __table_(__u.__table_) { 608 __table_.__rehash_unique(__u.bucket_count()); 609 insert(__u.begin(), __u.end()); 610} 611 612template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 613typename hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder 614hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(const key_type& __k) { 615 __node_allocator& __na = __table_.__node_alloc(); 616 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 617 __node_traits::construct(__na, std::addressof(__h->__get_value().first), __k); 618 __h.get_deleter().__first_constructed = true; 619 __node_traits::construct(__na, std::addressof(__h->__get_value().second)); 620 __h.get_deleter().__second_constructed = true; 621 return __h; 622} 623 624template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 625template <class _InputIterator> 626inline void hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, _InputIterator __last) { 627 for (; __first != __last; ++__first) 628 __table_.__insert_unique(*__first); 629} 630 631template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 632_Tp& hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](const key_type& __k) { 633 iterator __i = find(__k); 634 if (__i != end()) 635 return __i->second; 636 __node_holder __h = __construct_node(__k); 637 std::pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get()); 638 __h.release(); 639 return __r.first->second; 640} 641 642template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 643inline _LIBCPP_HIDE_FROM_ABI void 644swap(hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) { 645 __x.swap(__y); 646} 647 648template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 649_LIBCPP_HIDE_FROM_ABI bool 650operator==(const hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, const hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) { 651 if (__x.size() != __y.size()) 652 return false; 653 typedef typename hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator const_iterator; 654 for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end(); __i != __ex; ++__i) { 655 const_iterator __j = __y.find(__i->first); 656 if (__j == __ey || !(*__i == *__j)) 657 return false; 658 } 659 return true; 660} 661 662template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 663inline _LIBCPP_HIDE_FROM_ABI bool 664operator!=(const hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, const hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) { 665 return !(__x == __y); 666} 667 668template <class _Key, 669 class _Tp, 670 class _Hash = hash<_Key>, 671 class _Pred = std::equal_to<_Key>, 672 class _Alloc = std::allocator<std::pair<const _Key, _Tp> > > 673class _LIBCPP_TEMPLATE_VIS hash_multimap { 674public: 675 // types 676 typedef _Key key_type; 677 typedef _Tp mapped_type; 678 typedef _Tp data_type; 679 typedef _Hash hasher; 680 typedef _Pred key_equal; 681 typedef _Alloc allocator_type; 682 typedef std::pair<const key_type, mapped_type> value_type; 683 typedef value_type& reference; 684 typedef const value_type& const_reference; 685 686private: 687 typedef std::pair<key_type, mapped_type> __value_type; 688 typedef __hash_map_hasher<__value_type, hasher> __hasher; 689 typedef __hash_map_equal<__value_type, key_equal> __key_equal; 690 typedef std::__rebind_alloc<std::allocator_traits<allocator_type>, __value_type> __allocator_type; 691 692 typedef std::__hash_table<__value_type, __hasher, __key_equal, __allocator_type> __table; 693 694 __table __table_; 695 696 typedef typename __table::__node_traits __node_traits; 697 typedef typename __table::__node_allocator __node_allocator; 698 typedef typename __table::__node __node; 699 typedef __hash_map_node_destructor<__node_allocator> _Dp; 700 typedef std::unique_ptr<__node, _Dp> __node_holder; 701 typedef std::allocator_traits<allocator_type> __alloc_traits; 702 703public: 704 typedef typename __alloc_traits::pointer pointer; 705 typedef typename __alloc_traits::const_pointer const_pointer; 706 typedef typename __alloc_traits::size_type size_type; 707 typedef typename __alloc_traits::difference_type difference_type; 708 709 typedef __hash_map_iterator<typename __table::iterator> iterator; 710 typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator; 711 712 _LIBCPP_HIDE_FROM_ABI hash_multimap() {} 713 explicit _LIBCPP_HIDE_FROM_ABI 714 hash_multimap(size_type __n, const hasher& __hf = hasher(), const key_equal& __eql = key_equal()); 715 _LIBCPP_HIDE_FROM_ABI 716 hash_multimap(size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a); 717 template <class _InputIterator> 718 _LIBCPP_HIDE_FROM_ABI hash_multimap(_InputIterator __first, _InputIterator __last); 719 template <class _InputIterator> 720 _LIBCPP_HIDE_FROM_ABI 721 hash_multimap(_InputIterator __first, 722 _InputIterator __last, 723 size_type __n, 724 const hasher& __hf = hasher(), 725 const key_equal& __eql = key_equal()); 726 template <class _InputIterator> 727 _LIBCPP_HIDE_FROM_ABI hash_multimap( 728 _InputIterator __first, 729 _InputIterator __last, 730 size_type __n, 731 const hasher& __hf, 732 const key_equal& __eql, 733 const allocator_type& __a); 734 _LIBCPP_HIDE_FROM_ABI hash_multimap(const hash_multimap& __u); 735 736 _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const { return allocator_type(__table_.__node_alloc()); } 737 738 _LIBCPP_HIDE_FROM_ABI bool empty() const { return __table_.size() == 0; } 739 _LIBCPP_HIDE_FROM_ABI size_type size() const { return __table_.size(); } 740 _LIBCPP_HIDE_FROM_ABI size_type max_size() const { return __table_.max_size(); } 741 742 _LIBCPP_HIDE_FROM_ABI iterator begin() { return __table_.begin(); } 743 _LIBCPP_HIDE_FROM_ABI iterator end() { return __table_.end(); } 744 _LIBCPP_HIDE_FROM_ABI const_iterator begin() const { return __table_.begin(); } 745 _LIBCPP_HIDE_FROM_ABI const_iterator end() const { return __table_.end(); } 746 747 _LIBCPP_HIDE_FROM_ABI iterator insert(const value_type& __x) { return __table_.__insert_multi(__x); } 748 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator, const value_type& __x) { return insert(__x); } 749 template <class _InputIterator> 750 _LIBCPP_HIDE_FROM_ABI void insert(_InputIterator __first, _InputIterator __last); 751 752 _LIBCPP_HIDE_FROM_ABI void erase(const_iterator __p) { __table_.erase(__p.__i_); } 753 _LIBCPP_HIDE_FROM_ABI size_type erase(const key_type& __k) { return __table_.__erase_multi(__k); } 754 _LIBCPP_HIDE_FROM_ABI void erase(const_iterator __first, const_iterator __last) { 755 __table_.erase(__first.__i_, __last.__i_); 756 } 757 _LIBCPP_HIDE_FROM_ABI void clear() { __table_.clear(); } 758 759 _LIBCPP_HIDE_FROM_ABI void swap(hash_multimap& __u) { __table_.swap(__u.__table_); } 760 761 _LIBCPP_HIDE_FROM_ABI hasher hash_funct() const { return __table_.hash_function().hash_function(); } 762 _LIBCPP_HIDE_FROM_ABI key_equal key_eq() const { return __table_.key_eq().key_eq(); } 763 764 _LIBCPP_HIDE_FROM_ABI iterator find(const key_type& __k) { return __table_.find(__k); } 765 _LIBCPP_HIDE_FROM_ABI const_iterator find(const key_type& __k) const { return __table_.find(__k); } 766 _LIBCPP_HIDE_FROM_ABI size_type count(const key_type& __k) const { return __table_.__count_multi(__k); } 767 _LIBCPP_HIDE_FROM_ABI std::pair<iterator, iterator> equal_range(const key_type& __k) { 768 return __table_.__equal_range_multi(__k); 769 } 770 _LIBCPP_HIDE_FROM_ABI std::pair<const_iterator, const_iterator> equal_range(const key_type& __k) const { 771 return __table_.__equal_range_multi(__k); 772 } 773 774 _LIBCPP_HIDE_FROM_ABI size_type bucket_count() const { return __table_.bucket_count(); } 775 _LIBCPP_HIDE_FROM_ABI size_type max_bucket_count() const { return __table_.max_bucket_count(); } 776 777 _LIBCPP_HIDE_FROM_ABI size_type elems_in_bucket(size_type __n) const { return __table_.bucket_size(__n); } 778 779 _LIBCPP_HIDE_FROM_ABI void resize(size_type __n) { __table_.__rehash_multi(__n); } 780}; 781 782template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 783hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_multimap(size_type __n, const hasher& __hf, const key_equal& __eql) 784 : __table_(__hf, __eql) { 785 __table_.__rehash_multi(__n); 786} 787 788template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 789hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_multimap( 790 size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a) 791 : __table_(__hf, __eql, __a) { 792 __table_.__rehash_multi(__n); 793} 794 795template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 796template <class _InputIterator> 797hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_multimap(_InputIterator __first, _InputIterator __last) { 798 insert(__first, __last); 799} 800 801template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 802template <class _InputIterator> 803hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_multimap( 804 _InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, const key_equal& __eql) 805 : __table_(__hf, __eql) { 806 __table_.__rehash_multi(__n); 807 insert(__first, __last); 808} 809 810template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 811template <class _InputIterator> 812hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_multimap( 813 _InputIterator __first, 814 _InputIterator __last, 815 size_type __n, 816 const hasher& __hf, 817 const key_equal& __eql, 818 const allocator_type& __a) 819 : __table_(__hf, __eql, __a) { 820 __table_.__rehash_multi(__n); 821 insert(__first, __last); 822} 823 824template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 825hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_multimap(const hash_multimap& __u) : __table_(__u.__table_) { 826 __table_.__rehash_multi(__u.bucket_count()); 827 insert(__u.begin(), __u.end()); 828} 829 830template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 831template <class _InputIterator> 832inline void hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, _InputIterator __last) { 833 for (; __first != __last; ++__first) 834 __table_.__insert_multi(*__first); 835} 836 837template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 838inline _LIBCPP_HIDE_FROM_ABI void 839swap(hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) { 840 __x.swap(__y); 841} 842 843template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 844_LIBCPP_HIDE_FROM_ABI bool operator==(const hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 845 const hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) { 846 if (__x.size() != __y.size()) 847 return false; 848 typedef typename hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator const_iterator; 849 typedef std::pair<const_iterator, const_iterator> _EqRng; 850 for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;) { 851 _EqRng __xeq = __x.equal_range(__i->first); 852 _EqRng __yeq = __y.equal_range(__i->first); 853 if (std::distance(__xeq.first, __xeq.second) != std::distance(__yeq.first, __yeq.second) || 854 !std::is_permutation(__xeq.first, __xeq.second, __yeq.first)) 855 return false; 856 __i = __xeq.second; 857 } 858 return true; 859} 860 861template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 862inline _LIBCPP_HIDE_FROM_ABI bool operator!=(const hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 863 const hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) { 864 return !(__x == __y); 865} 866 867} // namespace __gnu_cxx 868 869# if !defined(_LIBCPP_REMOVE_TRANSITIVE_INCLUDES) && _LIBCPP_STD_VER <= 20 870# include <concepts> 871# include <iterator> 872# include <type_traits> 873# endif 874#endif // __cplusplus < 201103L && defined(_LIBCPP_USE_FROZEN_CXX03_HEADERS) 875 876#endif // _LIBCPP_HASH_MAP 877