libcxx/include/ext/hash_map

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