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