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