865 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___CXX03_HASH_MAP11#define _LIBCPP___CXX03_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#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) && __DEPRECATED211# if defined(_LIBCPP_WARNING)212_LIBCPP_WARNING("Use of the header <ext/hash_map> is deprecated. Migrate to <unordered_map>")213# else214# warning Use of the header <ext/hash_map> is deprecated. Migrate to <unordered_map>215# endif216#endif217 218#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)219# pragma GCC system_header220#endif221 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 bool264 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 bool285 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 bool414 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 bool418 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 // types440 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_ABI480 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_ABI486 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_ABI493 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_holder604hash_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 void634swap(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 bool640operator==(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 bool654operator!=(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 // types666 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_ABI704 hash_multimap(size_type __n, const hasher& __hf = hasher(), const key_equal& __eql = key_equal());705 _LIBCPP_HIDE_FROM_ABI706 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_ABI711 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 void829swap(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_cxx858 859#if !defined(_LIBCPP_REMOVE_TRANSITIVE_INCLUDES)860# include <__cxx03/iterator>861# include <__cxx03/type_traits>862#endif863 864#endif // _LIBCPP___CXX03_HASH_MAP865