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