libcxx/include/ext/hash_set

   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_SET
  11 #define _LIBCPP_HASH_SET
  12
  13 /*
  14
  15     hash_set synopsis
  16
  17 namespace __gnu_cxx
  18 {
  19
  20 template <class Value, class Hash = hash<Value>, class Pred = equal_to<Value>,
  21           class Alloc = allocator<Value>>
  22 class hash_set
  23 {
  24 public:
  25     // types
  26     typedef Value                                                      key_type;
  27     typedef key_type                                                   value_type;
  28     typedef Hash                                                       hasher;
  29     typedef Pred                                                       key_equal;
  30     typedef Alloc                                                      allocator_type;
  31     typedef value_type&                                                reference;
  32     typedef const value_type&                                          const_reference;
  33     typedef typename allocator_traits<allocator_type>::pointer         pointer;
  34     typedef typename allocator_traits<allocator_type>::const_pointer   const_pointer;
  35     typedef typename allocator_traits<allocator_type>::size_type       size_type;
  36     typedef typename allocator_traits<allocator_type>::difference_type difference_type;
  37
  38     typedef /unspecified/ iterator;
  39     typedef /unspecified/ const_iterator;
  40
  41     explicit hash_set(size_type n = 193, const hasher& hf = hasher(),
  42                            const key_equal& eql = key_equal(),
  43                            const allocator_type& a = allocator_type());
  44     template <class InputIterator>
  45         hash_set(InputIterator f, InputIterator l,
  46                       size_type n = 193, const hasher& hf = hasher(),
  47                       const key_equal& eql = key_equal(),
  48                       const allocator_type& a = allocator_type());
  49     hash_set(const hash_set&);
  50     ~hash_set();
  51     hash_set& operator=(const hash_set&);
  52
  53     allocator_type get_allocator() const;
  54
  55     bool      empty() const;
  56     size_type size() const;
  57     size_type max_size() const;
  58
  59     iterator       begin();
  60     iterator       end();
  61     const_iterator begin()  const;
  62     const_iterator end()    const;
  63
  64     pair<iterator, bool> insert(const value_type& obj);
  65     template <class InputIterator>
  66         void insert(InputIterator first, InputIterator last);
  67
  68     void erase(const_iterator position);
  69     size_type erase(const key_type& k);
  70     void erase(const_iterator first, const_iterator last);
  71     void clear();
  72
  73     void swap(hash_set&);
  74
  75     hasher hash_funct() const;
  76     key_equal key_eq() const;
  77
  78     iterator       find(const key_type& k);
  79     const_iterator find(const key_type& k) const;
  80     size_type count(const key_type& k) const;
  81     pair<iterator, iterator>             equal_range(const key_type& k);
  82     pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
  83
  84     size_type bucket_count() const;
  85     size_type max_bucket_count() const;
  86
  87     size_type elems_in_bucket(size_type n) const;
  88
  89     void resize(size_type n);
  90 };
  91
  92 template <class Value, class Hash, class Pred, class Alloc>
  93     void swap(hash_set<Value, Hash, Pred, Alloc>& x,
  94               hash_set<Value, Hash, Pred, Alloc>& y);
  95
  96 template <class Value, class Hash, class Pred, class Alloc>
  97     bool
  98     operator==(const hash_set<Value, Hash, Pred, Alloc>& x,
  99                const hash_set<Value, Hash, Pred, Alloc>& y);
 100
 101 template <class Value, class Hash, class Pred, class Alloc>
 102     bool
 103     operator!=(const hash_set<Value, Hash, Pred, Alloc>& x,
 104                const hash_set<Value, Hash, Pred, Alloc>& y);
 105
 106 template <class Value, class Hash = hash<Value>, class Pred = equal_to<Value>,
 107           class Alloc = allocator<Value>>
 108 class hash_multiset
 109 {
 110 public:
 111     // types
 112     typedef Value                                                      key_type;
 113     typedef key_type                                                   value_type;
 114     typedef Hash                                                       hasher;
 115     typedef Pred                                                       key_equal;
 116     typedef Alloc                                                      allocator_type;
 117     typedef value_type&                                                reference;
 118     typedef const value_type&                                          const_reference;
 119     typedef typename allocator_traits<allocator_type>::pointer         pointer;
 120     typedef typename allocator_traits<allocator_type>::const_pointer   const_pointer;
 121     typedef typename allocator_traits<allocator_type>::size_type       size_type;
 122     typedef typename allocator_traits<allocator_type>::difference_type difference_type;
 123
 124     typedef /unspecified/ iterator;
 125     typedef /unspecified/ const_iterator;
 126
 127     explicit hash_multiset(size_type n = 193, const hasher& hf = hasher(),
 128                            const key_equal& eql = key_equal(),
 129                            const allocator_type& a = allocator_type());
 130     template <class InputIterator>
 131         hash_multiset(InputIterator f, InputIterator l,
 132                       size_type n = 193, const hasher& hf = hasher(),
 133                       const key_equal& eql = key_equal(),
 134                       const allocator_type& a = allocator_type());
 135     hash_multiset(const hash_multiset&);
 136     ~hash_multiset();
 137     hash_multiset& operator=(const hash_multiset&);
 138
 139     allocator_type get_allocator() const;
 140
 141     bool      empty() const;
 142     size_type size() const;
 143     size_type max_size() const;
 144
 145     iterator       begin();
 146     iterator       end();
 147     const_iterator begin()  const;
 148     const_iterator end()    const;
 149
 150     iterator insert(const value_type& obj);
 151     template <class InputIterator>
 152         void insert(InputIterator first, InputIterator last);
 153
 154     void erase(const_iterator position);
 155     size_type erase(const key_type& k);
 156     void erase(const_iterator first, const_iterator last);
 157     void clear();
 158
 159     void swap(hash_multiset&);
 160
 161     hasher hash_funct() const;
 162     key_equal key_eq() const;
 163
 164     iterator       find(const key_type& k);
 165     const_iterator find(const key_type& k) const;
 166     size_type count(const key_type& k) const;
 167     pair<iterator, iterator>             equal_range(const key_type& k);
 168     pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
 169
 170     size_type bucket_count() const;
 171     size_type max_bucket_count() const;
 172
 173     size_type elems_in_bucket(size_type n) const;
 174
 175     void resize(size_type n);
 176 };
 177
 178 template <class Value, class Hash, class Pred, class Alloc>
 179     void swap(hash_multiset<Value, Hash, Pred, Alloc>& x,
 180               hash_multiset<Value, Hash, Pred, Alloc>& y);
 181
 182 template <class Value, class Hash, class Pred, class Alloc>
 183     bool
 184     operator==(const hash_multiset<Value, Hash, Pred, Alloc>& x,
 185                const hash_multiset<Value, Hash, Pred, Alloc>& y);
 186
 187 template <class Value, class Hash, class Pred, class Alloc>
 188     bool
 189     operator!=(const hash_multiset<Value, Hash, Pred, Alloc>& x,
 190                const hash_multiset<Value, Hash, Pred, Alloc>& y);
 191 }  // __gnu_cxx
 192
 193 */
 194
 195 #include <__assert> // all public C++ headers provide the assertion handler
 196 #include <__config>
 197 #include <__hash_table>
 198 #include <algorithm>
 199 #include <ext/__hash>
 200 #include <functional>
 201
 202 #if defined(__DEPRECATED) && __DEPRECATED
 203 #if defined(_LIBCPP_WARNING)
 204     _LIBCPP_WARNING("Use of the header <ext/hash_set> is deprecated.  Migrate to <unordered_set>")
 205 #else
 206 #   warning Use of the header <ext/hash_set> is deprecated.  Migrate to <unordered_set>
 207 #endif
 208 #endif
 209
 210 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 211 #  pragma GCC system_header
 212 #endif
 213
 214 namespace __gnu_cxx {
 215
 216
 217 template <class _Value, class _Hash = hash<_Value>, class _Pred = std::equal_to<_Value>,
 218           class _Alloc = std::allocator<_Value> >
 219 class _LIBCPP_TEMPLATE_VIS hash_set
 220 {
 221 public:
 222     // types
 223     typedef _Value                                                     key_type;
 224     typedef key_type                                                   value_type;
 225     typedef _Hash                                                      hasher;
 226     typedef _Pred                                                      key_equal;
 227     typedef _Alloc                                                     allocator_type;
 228     typedef value_type&                                                reference;
 229     typedef const value_type&                                          const_reference;
 230
 231 private:
 232     typedef std::__hash_table<value_type, hasher, key_equal, allocator_type> __table;
 233
 234     __table __table_;
 235
 236 public:
 237     typedef typename __table::pointer         pointer;
 238     typedef typename __table::const_pointer   const_pointer;
 239     typedef typename __table::size_type       size_type;
 240     typedef typename __table::difference_type difference_type;
 241
 242     typedef typename __table::const_iterator       iterator;
 243     typedef typename __table::const_iterator       const_iterator;
 244
 245     _LIBCPP_INLINE_VISIBILITY
 246     hash_set() { }
 247     _LIBCPP_HIDE_FROM_ABI explicit hash_set(size_type __n, const hasher& __hf = hasher(),
 248                            const key_equal& __eql = key_equal());
 249     _LIBCPP_HIDE_FROM_ABI hash_set(size_type __n, const hasher& __hf, const key_equal& __eql,
 250                   const allocator_type& __a);
 251     template <class _InputIterator>
 252     _LIBCPP_HIDE_FROM_ABI hash_set(_InputIterator __first, _InputIterator __last);
 253     template <class _InputIterator>
 254     _LIBCPP_HIDE_FROM_ABI hash_set(_InputIterator __first, _InputIterator __last,
 255                       size_type __n, const hasher& __hf = hasher(),
 256                       const key_equal& __eql = key_equal());
 257     template <class _InputIterator>
 258     _LIBCPP_HIDE_FROM_ABI hash_set(_InputIterator __first, _InputIterator __last,
 259                       size_type __n, const hasher& __hf, const key_equal& __eql,
 260                       const allocator_type& __a);
 261     _LIBCPP_HIDE_FROM_ABI hash_set(const hash_set& __u);
 262
 263     _LIBCPP_INLINE_VISIBILITY
 264     allocator_type get_allocator() const
 265         {return allocator_type(__table_.__node_alloc());}
 266
 267     _LIBCPP_INLINE_VISIBILITY
 268     bool      empty() const {return __table_.size() == 0;}
 269     _LIBCPP_INLINE_VISIBILITY
 270     size_type size() const  {return __table_.size();}
 271     _LIBCPP_INLINE_VISIBILITY
 272     size_type max_size() const {return __table_.max_size();}
 273
 274     _LIBCPP_INLINE_VISIBILITY
 275     iterator       begin()        {return __table_.begin();}
 276     _LIBCPP_INLINE_VISIBILITY
 277     iterator       end()          {return __table_.end();}
 278     _LIBCPP_INLINE_VISIBILITY
 279     const_iterator begin()  const {return __table_.begin();}
 280     _LIBCPP_INLINE_VISIBILITY
 281     const_iterator end()    const {return __table_.end();}
 282
 283     _LIBCPP_INLINE_VISIBILITY
 284     std::pair<iterator, bool> insert(const value_type& __x)
 285         {return __table_.__insert_unique(__x);}
 286     _LIBCPP_INLINE_VISIBILITY
 287     iterator insert(const_iterator, const value_type& __x) {return insert(__x).first;}
 288     template <class _InputIterator>
 289         _LIBCPP_INLINE_VISIBILITY
 290         void insert(_InputIterator __first, _InputIterator __last);
 291
 292     _LIBCPP_INLINE_VISIBILITY
 293     void erase(const_iterator __p) {__table_.erase(__p);}
 294     _LIBCPP_INLINE_VISIBILITY
 295     size_type erase(const key_type& __k) {return __table_.__erase_unique(__k);}
 296     _LIBCPP_INLINE_VISIBILITY
 297     void erase(const_iterator __first, const_iterator __last)
 298         {__table_.erase(__first, __last);}
 299     _LIBCPP_INLINE_VISIBILITY
 300     void clear() {__table_.clear();}
 301
 302     _LIBCPP_INLINE_VISIBILITY
 303     void swap(hash_set& __u) {__table_.swap(__u.__table_);}
 304
 305     _LIBCPP_INLINE_VISIBILITY
 306     hasher hash_funct() const {return __table_.hash_function();}
 307     _LIBCPP_INLINE_VISIBILITY
 308     key_equal key_eq() const {return __table_.key_eq();}
 309
 310     _LIBCPP_INLINE_VISIBILITY
 311     iterator       find(const key_type& __k)       {return __table_.find(__k);}
 312     _LIBCPP_INLINE_VISIBILITY
 313     const_iterator find(const key_type& __k) const {return __table_.find(__k);}
 314     _LIBCPP_INLINE_VISIBILITY
 315     size_type count(const key_type& __k) const {return __table_.__count_unique(__k);}
 316     _LIBCPP_INLINE_VISIBILITY
 317     std::pair<iterator, iterator>             equal_range(const key_type& __k)
 318         {return __table_.__equal_range_unique(__k);}
 319     _LIBCPP_INLINE_VISIBILITY
 320     std::pair<const_iterator, const_iterator> equal_range(const key_type& __k) const
 321         {return __table_.__equal_range_unique(__k);}
 322
 323     _LIBCPP_INLINE_VISIBILITY
 324     size_type bucket_count() const {return __table_.bucket_count();}
 325     _LIBCPP_INLINE_VISIBILITY
 326     size_type max_bucket_count() const {return __table_.max_bucket_count();}
 327
 328     _LIBCPP_INLINE_VISIBILITY
 329     size_type elems_in_bucket(size_type __n) const {return __table_.bucket_size(__n);}
 330
 331     _LIBCPP_INLINE_VISIBILITY
 332     void resize(size_type __n) {__table_.__rehash_unique(__n);}
 333 };
 334
 335 template <class _Value, class _Hash, class _Pred, class _Alloc>
 336 hash_set<_Value, _Hash, _Pred, _Alloc>::hash_set(size_type __n,
 337         const hasher& __hf, const key_equal& __eql)
 338     : __table_(__hf, __eql)
 339 {
 340     __table_.__rehash_unique(__n);
 341 }
 342
 343 template <class _Value, class _Hash, class _Pred, class _Alloc>
 344 hash_set<_Value, _Hash, _Pred, _Alloc>::hash_set(size_type __n,
 345         const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
 346     : __table_(__hf, __eql, __a)
 347 {
 348     __table_.__rehash_unique(__n);
 349 }
 350
 351 template <class _Value, class _Hash, class _Pred, class _Alloc>
 352 template <class _InputIterator>
 353 hash_set<_Value, _Hash, _Pred, _Alloc>::hash_set(
 354         _InputIterator __first, _InputIterator __last)
 355 {
 356     insert(__first, __last);
 357 }
 358
 359 template <class _Value, class _Hash, class _Pred, class _Alloc>
 360 template <class _InputIterator>
 361 hash_set<_Value, _Hash, _Pred, _Alloc>::hash_set(
 362         _InputIterator __first, _InputIterator __last, size_type __n,
 363         const hasher& __hf, const key_equal& __eql)
 364     : __table_(__hf, __eql)
 365 {
 366     __table_.__rehash_unique(__n);
 367     insert(__first, __last);
 368 }
 369
 370 template <class _Value, class _Hash, class _Pred, class _Alloc>
 371 template <class _InputIterator>
 372 hash_set<_Value, _Hash, _Pred, _Alloc>::hash_set(
 373         _InputIterator __first, _InputIterator __last, size_type __n,
 374         const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
 375     : __table_(__hf, __eql, __a)
 376 {
 377     __table_.__rehash_unique(__n);
 378     insert(__first, __last);
 379 }
 380
 381 template <class _Value, class _Hash, class _Pred, class _Alloc>
 382 hash_set<_Value, _Hash, _Pred, _Alloc>::hash_set(
 383         const hash_set& __u)
 384     : __table_(__u.__table_)
 385 {
 386     __table_.__rehash_unique(__u.bucket_count());
 387     insert(__u.begin(), __u.end());
 388 }
 389
 390 template <class _Value, class _Hash, class _Pred, class _Alloc>
 391 template <class _InputIterator>
 392 inline
 393 void
 394 hash_set<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator __first,
 395                                                     _InputIterator __last)
 396 {
 397     for (; __first != __last; ++__first)
 398         __table_.__insert_unique(*__first);
 399 }
 400
 401 template <class _Value, class _Hash, class _Pred, class _Alloc>
 402 inline _LIBCPP_INLINE_VISIBILITY
 403 void
 404 swap(hash_set<_Value, _Hash, _Pred, _Alloc>& __x,
 405      hash_set<_Value, _Hash, _Pred, _Alloc>& __y)
 406 {
 407     __x.swap(__y);
 408 }
 409
 410 template <class _Value, class _Hash, class _Pred, class _Alloc>
 411 _LIBCPP_HIDE_FROM_ABI bool
 412 operator==(const hash_set<_Value, _Hash, _Pred, _Alloc>& __x,
 413            const hash_set<_Value, _Hash, _Pred, _Alloc>& __y)
 414 {
 415     if (__x.size() != __y.size())
 416         return false;
 417     typedef typename hash_set<_Value, _Hash, _Pred, _Alloc>::const_iterator
 418                                                                  const_iterator;
 419     for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end();
 420             __i != __ex; ++__i)
 421     {
 422         const_iterator __j = __y.find(*__i);
 423         if (__j == __ey || !(*__i == *__j))
 424             return false;
 425     }
 426     return true;
 427 }
 428
 429 template <class _Value, class _Hash, class _Pred, class _Alloc>
 430 inline _LIBCPP_INLINE_VISIBILITY
 431 bool
 432 operator!=(const hash_set<_Value, _Hash, _Pred, _Alloc>& __x,
 433            const hash_set<_Value, _Hash, _Pred, _Alloc>& __y)
 434 {
 435     return !(__x == __y);
 436 }
 437
 438 template <class _Value, class _Hash = hash<_Value>, class _Pred = std::equal_to<_Value>,
 439           class _Alloc = std::allocator<_Value> >
 440 class _LIBCPP_TEMPLATE_VIS hash_multiset
 441 {
 442 public:
 443     // types
 444     typedef _Value                                                     key_type;
 445     typedef key_type                                                   value_type;
 446     typedef _Hash                                                      hasher;
 447     typedef _Pred                                                      key_equal;
 448     typedef _Alloc                                                     allocator_type;
 449     typedef value_type&                                                reference;
 450     typedef const value_type&                                          const_reference;
 451
 452 private:
 453     typedef std::__hash_table<value_type, hasher, key_equal, allocator_type> __table;
 454
 455     __table __table_;
 456
 457 public:
 458     typedef typename __table::pointer         pointer;
 459     typedef typename __table::const_pointer   const_pointer;
 460     typedef typename __table::size_type       size_type;
 461     typedef typename __table::difference_type difference_type;
 462
 463     typedef typename __table::const_iterator       iterator;
 464     typedef typename __table::const_iterator       const_iterator;
 465
 466     _LIBCPP_INLINE_VISIBILITY
 467     hash_multiset() { }
 468     explicit _LIBCPP_HIDE_FROM_ABI hash_multiset(size_type __n, const hasher& __hf = hasher(),
 469                                 const key_equal& __eql = key_equal());
 470     _LIBCPP_HIDE_FROM_ABI hash_multiset(size_type __n, const hasher& __hf,
 471                        const key_equal& __eql, const allocator_type& __a);
 472     template <class _InputIterator>
 473     _LIBCPP_HIDE_FROM_ABI hash_multiset(_InputIterator __first, _InputIterator __last);
 474     template <class _InputIterator>
 475     _LIBCPP_HIDE_FROM_ABI hash_multiset(_InputIterator __first, _InputIterator __last,
 476                       size_type __n, const hasher& __hf = hasher(),
 477                       const key_equal& __eql = key_equal());
 478     template <class _InputIterator>
 479     _LIBCPP_HIDE_FROM_ABI hash_multiset(_InputIterator __first, _InputIterator __last,
 480                       size_type __n , const hasher& __hf,
 481                       const key_equal& __eql, const allocator_type& __a);
 482     _LIBCPP_HIDE_FROM_ABI hash_multiset(const hash_multiset& __u);
 483
 484     _LIBCPP_INLINE_VISIBILITY
 485     allocator_type get_allocator() const
 486         {return allocator_type(__table_.__node_alloc());}
 487
 488     _LIBCPP_INLINE_VISIBILITY
 489     bool      empty() const {return __table_.size() == 0;}
 490     _LIBCPP_INLINE_VISIBILITY
 491     size_type size() const  {return __table_.size();}
 492     _LIBCPP_INLINE_VISIBILITY
 493     size_type max_size() const {return __table_.max_size();}
 494
 495     _LIBCPP_INLINE_VISIBILITY
 496     iterator       begin()        {return __table_.begin();}
 497     _LIBCPP_INLINE_VISIBILITY
 498     iterator       end()          {return __table_.end();}
 499     _LIBCPP_INLINE_VISIBILITY
 500     const_iterator begin()  const {return __table_.begin();}
 501     _LIBCPP_INLINE_VISIBILITY
 502     const_iterator end()    const {return __table_.end();}
 503
 504     _LIBCPP_INLINE_VISIBILITY
 505     iterator insert(const value_type& __x) {return __table_.__insert_multi(__x);}
 506     _LIBCPP_INLINE_VISIBILITY
 507     iterator insert(const_iterator, const value_type& __x) {return insert(__x);}
 508     template <class _InputIterator>
 509         _LIBCPP_INLINE_VISIBILITY
 510         void insert(_InputIterator __first, _InputIterator __last);
 511
 512     _LIBCPP_INLINE_VISIBILITY
 513     void erase(const_iterator __p) {__table_.erase(__p);}
 514     _LIBCPP_INLINE_VISIBILITY
 515     size_type erase(const key_type& __k) {return __table_.__erase_multi(__k);}
 516     _LIBCPP_INLINE_VISIBILITY
 517     void erase(const_iterator __first, const_iterator __last)
 518         {__table_.erase(__first, __last);}
 519     _LIBCPP_INLINE_VISIBILITY
 520     void clear() {__table_.clear();}
 521
 522     _LIBCPP_INLINE_VISIBILITY
 523     void swap(hash_multiset& __u) {__table_.swap(__u.__table_);}
 524
 525     _LIBCPP_INLINE_VISIBILITY
 526     hasher hash_funct() const {return __table_.hash_function();}
 527     _LIBCPP_INLINE_VISIBILITY
 528     key_equal key_eq() const {return __table_.key_eq();}
 529
 530     _LIBCPP_INLINE_VISIBILITY
 531     iterator       find(const key_type& __k)       {return __table_.find(__k);}
 532     _LIBCPP_INLINE_VISIBILITY
 533     const_iterator find(const key_type& __k) const {return __table_.find(__k);}
 534     _LIBCPP_INLINE_VISIBILITY
 535     size_type count(const key_type& __k) const {return __table_.__count_multi(__k);}
 536     _LIBCPP_INLINE_VISIBILITY
 537     std::pair<iterator, iterator>             equal_range(const key_type& __k)
 538         {return __table_.__equal_range_multi(__k);}
 539     _LIBCPP_INLINE_VISIBILITY
 540     std::pair<const_iterator, const_iterator> equal_range(const key_type& __k) const
 541         {return __table_.__equal_range_multi(__k);}
 542
 543     _LIBCPP_INLINE_VISIBILITY
 544     size_type bucket_count() const {return __table_.bucket_count();}
 545     _LIBCPP_INLINE_VISIBILITY
 546     size_type max_bucket_count() const {return __table_.max_bucket_count();}
 547
 548     _LIBCPP_INLINE_VISIBILITY
 549     size_type elems_in_bucket(size_type __n) const {return __table_.bucket_size(__n);}
 550
 551     _LIBCPP_INLINE_VISIBILITY
 552     void resize(size_type __n) {__table_.__rehash_multi(__n);}
 553 };
 554
 555 template <class _Value, class _Hash, class _Pred, class _Alloc>
 556 hash_multiset<_Value, _Hash, _Pred, _Alloc>::hash_multiset(
 557         size_type __n, const hasher& __hf, const key_equal& __eql)
 558     : __table_(__hf, __eql)
 559 {
 560     __table_.__rehash_multi(__n);
 561 }
 562
 563 template <class _Value, class _Hash, class _Pred, class _Alloc>
 564 hash_multiset<_Value, _Hash, _Pred, _Alloc>::hash_multiset(
 565         size_type __n, const hasher& __hf, const key_equal& __eql,
 566         const allocator_type& __a)
 567     : __table_(__hf, __eql, __a)
 568 {
 569     __table_.__rehash_multi(__n);
 570 }
 571
 572 template <class _Value, class _Hash, class _Pred, class _Alloc>
 573 template <class _InputIterator>
 574 hash_multiset<_Value, _Hash, _Pred, _Alloc>::hash_multiset(
 575         _InputIterator __first, _InputIterator __last)
 576 {
 577     insert(__first, __last);
 578 }
 579
 580 template <class _Value, class _Hash, class _Pred, class _Alloc>
 581 template <class _InputIterator>
 582 hash_multiset<_Value, _Hash, _Pred, _Alloc>::hash_multiset(
 583         _InputIterator __first, _InputIterator __last, size_type __n,
 584         const hasher& __hf, const key_equal& __eql)
 585     : __table_(__hf, __eql)
 586 {
 587     __table_.__rehash_multi(__n);
 588     insert(__first, __last);
 589 }
 590
 591 template <class _Value, class _Hash, class _Pred, class _Alloc>
 592 template <class _InputIterator>
 593 hash_multiset<_Value, _Hash, _Pred, _Alloc>::hash_multiset(
 594         _InputIterator __first, _InputIterator __last, size_type __n,
 595         const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
 596     : __table_(__hf, __eql, __a)
 597 {
 598     __table_.__rehash_multi(__n);
 599     insert(__first, __last);
 600 }
 601
 602 template <class _Value, class _Hash, class _Pred, class _Alloc>
 603 hash_multiset<_Value, _Hash, _Pred, _Alloc>::hash_multiset(
 604         const hash_multiset& __u)
 605     : __table_(__u.__table_)
 606 {
 607     __table_.__rehash_multi(__u.bucket_count());
 608     insert(__u.begin(), __u.end());
 609 }
 610
 611 template <class _Value, class _Hash, class _Pred, class _Alloc>
 612 template <class _InputIterator>
 613 inline
 614 void
 615 hash_multiset<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator __first,
 616                                                     _InputIterator __last)
 617 {
 618     for (; __first != __last; ++__first)
 619         __table_.__insert_multi(*__first);
 620 }
 621
 622 template <class _Value, class _Hash, class _Pred, class _Alloc>
 623 inline _LIBCPP_INLINE_VISIBILITY
 624 void
 625 swap(hash_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
 626      hash_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
 627 {
 628     __x.swap(__y);
 629 }
 630
 631 template <class _Value, class _Hash, class _Pred, class _Alloc>
 632 _LIBCPP_HIDE_FROM_ABI bool
 633 operator==(const hash_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
 634            const hash_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
 635 {
 636     if (__x.size() != __y.size())
 637         return false;
 638     typedef typename hash_multiset<_Value, _Hash, _Pred, _Alloc>::const_iterator
 639                                                                  const_iterator;
 640     typedef std::pair<const_iterator, const_iterator> _EqRng;
 641     for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;)
 642     {
 643         _EqRng __xeq = __x.equal_range(*__i);
 644         _EqRng __yeq = __y.equal_range(*__i);
 645         if (_VSTD::distance(__xeq.first, __xeq.second) !=
 646             _VSTD::distance(__yeq.first, __yeq.second) ||
 647                   !_VSTD::is_permutation(__xeq.first, __xeq.second, __yeq.first))
 648             return false;
 649         __i = __xeq.second;
 650     }
 651     return true;
 652 }
 653
 654 template <class _Value, class _Hash, class _Pred, class _Alloc>
 655 inline _LIBCPP_INLINE_VISIBILITY
 656 bool
 657 operator!=(const hash_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
 658            const hash_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
 659 {
 660     return !(__x == __y);
 661 }
 662
 663 } // namespace __gnu_cxx
 664
 665 #if !defined(_LIBCPP_REMOVE_TRANSITIVE_INCLUDES) && _LIBCPP_STD_VER <= 20
 666 #  include <concepts>
 667 #  include <iterator>
 668 #  include <type_traits>
 669 #endif
 670
 671 #endif // _LIBCPP_HASH_SET