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 <__config>
 196 #include <__hash_table>
 197 #include <algorithm>
 198 #include <ext/__hash>
 199 #include <functional>
 200
 201 #if defined(__DEPRECATED) && __DEPRECATED
 202 #  if defined(_LIBCPP_WARNING)
 203 _LIBCPP_WARNING("Use of the header <ext/hash_set> is deprecated.  Migrate to <unordered_set>")
 204 #  else
 205 #    warning Use of the header <ext/hash_set> is deprecated.  Migrate to <unordered_set>
 206 #  endif
 207 #endif
 208
 209 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 210 #  pragma GCC system_header
 211 #endif
 212
 213 namespace __gnu_cxx {
 214
 215 template <class _Value,
 216           class _Hash  = hash<_Value>,
 217           class _Pred  = std::equal_to<_Value>,
 218           class _Alloc = std::allocator<_Value> >
 219 class _LIBCPP_TEMPLATE_VIS hash_set {
 220 public:
 221   // types
 222   typedef _Value key_type;
 223   typedef key_type value_type;
 224   typedef _Hash hasher;
 225   typedef _Pred key_equal;
 226   typedef _Alloc allocator_type;
 227   typedef value_type& reference;
 228   typedef const value_type& const_reference;
 229
 230 private:
 231   typedef std::__hash_table<value_type, hasher, key_equal, allocator_type> __table;
 232
 233   __table __table_;
 234
 235 public:
 236   typedef typename __table::pointer pointer;
 237   typedef typename __table::const_pointer const_pointer;
 238   typedef typename __table::size_type size_type;
 239   typedef typename __table::difference_type difference_type;
 240
 241   typedef typename __table::const_iterator iterator;
 242   typedef typename __table::const_iterator const_iterator;
 243
 244   _LIBCPP_HIDE_FROM_ABI hash_set() {}
 245   _LIBCPP_HIDE_FROM_ABI explicit hash_set(
 246       size_type __n, const hasher& __hf = hasher(), const key_equal& __eql = key_equal());
 247   _LIBCPP_HIDE_FROM_ABI hash_set(size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a);
 248   template <class _InputIterator>
 249   _LIBCPP_HIDE_FROM_ABI hash_set(_InputIterator __first, _InputIterator __last);
 250   template <class _InputIterator>
 251   _LIBCPP_HIDE_FROM_ABI
 252   hash_set(_InputIterator __first,
 253            _InputIterator __last,
 254            size_type __n,
 255            const hasher& __hf     = hasher(),
 256            const key_equal& __eql = key_equal());
 257   template <class _InputIterator>
 258   _LIBCPP_HIDE_FROM_ABI
 259   hash_set(_InputIterator __first,
 260            _InputIterator __last,
 261            size_type __n,
 262            const hasher& __hf,
 263            const key_equal& __eql,
 264            const allocator_type& __a);
 265   _LIBCPP_HIDE_FROM_ABI hash_set(const hash_set& __u);
 266
 267   _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const { return allocator_type(__table_.__node_alloc()); }
 268
 269   _LIBCPP_HIDE_FROM_ABI bool empty() const { return __table_.size() == 0; }
 270   _LIBCPP_HIDE_FROM_ABI size_type size() const { return __table_.size(); }
 271   _LIBCPP_HIDE_FROM_ABI size_type max_size() const { return __table_.max_size(); }
 272
 273   _LIBCPP_HIDE_FROM_ABI iterator begin() { return __table_.begin(); }
 274   _LIBCPP_HIDE_FROM_ABI iterator end() { return __table_.end(); }
 275   _LIBCPP_HIDE_FROM_ABI const_iterator begin() const { return __table_.begin(); }
 276   _LIBCPP_HIDE_FROM_ABI const_iterator end() const { return __table_.end(); }
 277
 278   _LIBCPP_HIDE_FROM_ABI std::pair<iterator, bool> insert(const value_type& __x) {
 279     return __table_.__insert_unique(__x);
 280   }
 281   _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator, const value_type& __x) { return insert(__x).first; }
 282   template <class _InputIterator>
 283   _LIBCPP_HIDE_FROM_ABI void insert(_InputIterator __first, _InputIterator __last);
 284
 285   _LIBCPP_HIDE_FROM_ABI void erase(const_iterator __p) { __table_.erase(__p); }
 286   _LIBCPP_HIDE_FROM_ABI size_type erase(const key_type& __k) { return __table_.__erase_unique(__k); }
 287   _LIBCPP_HIDE_FROM_ABI void erase(const_iterator __first, const_iterator __last) { __table_.erase(__first, __last); }
 288   _LIBCPP_HIDE_FROM_ABI void clear() { __table_.clear(); }
 289
 290   _LIBCPP_HIDE_FROM_ABI void swap(hash_set& __u) { __table_.swap(__u.__table_); }
 291
 292   _LIBCPP_HIDE_FROM_ABI hasher hash_funct() const { return __table_.hash_function(); }
 293   _LIBCPP_HIDE_FROM_ABI key_equal key_eq() const { return __table_.key_eq(); }
 294
 295   _LIBCPP_HIDE_FROM_ABI iterator find(const key_type& __k) { return __table_.find(__k); }
 296   _LIBCPP_HIDE_FROM_ABI const_iterator find(const key_type& __k) const { return __table_.find(__k); }
 297   _LIBCPP_HIDE_FROM_ABI size_type count(const key_type& __k) const { return __table_.__count_unique(__k); }
 298   _LIBCPP_HIDE_FROM_ABI std::pair<iterator, iterator> equal_range(const key_type& __k) {
 299     return __table_.__equal_range_unique(__k);
 300   }
 301   _LIBCPP_HIDE_FROM_ABI std::pair<const_iterator, const_iterator> equal_range(const key_type& __k) const {
 302     return __table_.__equal_range_unique(__k);
 303   }
 304
 305   _LIBCPP_HIDE_FROM_ABI size_type bucket_count() const { return __table_.bucket_count(); }
 306   _LIBCPP_HIDE_FROM_ABI size_type max_bucket_count() const { return __table_.max_bucket_count(); }
 307
 308   _LIBCPP_HIDE_FROM_ABI size_type elems_in_bucket(size_type __n) const { return __table_.bucket_size(__n); }
 309
 310   _LIBCPP_HIDE_FROM_ABI void resize(size_type __n) { __table_.__rehash_unique(__n); }
 311 };
 312
 313 template <class _Value, class _Hash, class _Pred, class _Alloc>
 314 hash_set<_Value, _Hash, _Pred, _Alloc>::hash_set(size_type __n, const hasher& __hf, const key_equal& __eql)
 315     : __table_(__hf, __eql) {
 316   __table_.__rehash_unique(__n);
 317 }
 318
 319 template <class _Value, class _Hash, class _Pred, class _Alloc>
 320 hash_set<_Value, _Hash, _Pred, _Alloc>::hash_set(
 321     size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
 322     : __table_(__hf, __eql, __a) {
 323   __table_.__rehash_unique(__n);
 324 }
 325
 326 template <class _Value, class _Hash, class _Pred, class _Alloc>
 327 template <class _InputIterator>
 328 hash_set<_Value, _Hash, _Pred, _Alloc>::hash_set(_InputIterator __first, _InputIterator __last) {
 329   insert(__first, __last);
 330 }
 331
 332 template <class _Value, class _Hash, class _Pred, class _Alloc>
 333 template <class _InputIterator>
 334 hash_set<_Value, _Hash, _Pred, _Alloc>::hash_set(
 335     _InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, const key_equal& __eql)
 336     : __table_(__hf, __eql) {
 337   __table_.__rehash_unique(__n);
 338   insert(__first, __last);
 339 }
 340
 341 template <class _Value, class _Hash, class _Pred, class _Alloc>
 342 template <class _InputIterator>
 343 hash_set<_Value, _Hash, _Pred, _Alloc>::hash_set(
 344     _InputIterator __first,
 345     _InputIterator __last,
 346     size_type __n,
 347     const hasher& __hf,
 348     const key_equal& __eql,
 349     const allocator_type& __a)
 350     : __table_(__hf, __eql, __a) {
 351   __table_.__rehash_unique(__n);
 352   insert(__first, __last);
 353 }
 354
 355 template <class _Value, class _Hash, class _Pred, class _Alloc>
 356 hash_set<_Value, _Hash, _Pred, _Alloc>::hash_set(const hash_set& __u) : __table_(__u.__table_) {
 357   __table_.__rehash_unique(__u.bucket_count());
 358   insert(__u.begin(), __u.end());
 359 }
 360
 361 template <class _Value, class _Hash, class _Pred, class _Alloc>
 362 template <class _InputIterator>
 363 inline void hash_set<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, _InputIterator __last) {
 364   for (; __first != __last; ++__first)
 365     __table_.__insert_unique(*__first);
 366 }
 367
 368 template <class _Value, class _Hash, class _Pred, class _Alloc>
 369 inline _LIBCPP_HIDE_FROM_ABI void
 370 swap(hash_set<_Value, _Hash, _Pred, _Alloc>& __x, hash_set<_Value, _Hash, _Pred, _Alloc>& __y) {
 371   __x.swap(__y);
 372 }
 373
 374 template <class _Value, class _Hash, class _Pred, class _Alloc>
 375 _LIBCPP_HIDE_FROM_ABI bool
 376 operator==(const hash_set<_Value, _Hash, _Pred, _Alloc>& __x, const hash_set<_Value, _Hash, _Pred, _Alloc>& __y) {
 377   if (__x.size() != __y.size())
 378     return false;
 379   typedef typename hash_set<_Value, _Hash, _Pred, _Alloc>::const_iterator const_iterator;
 380   for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end(); __i != __ex; ++__i) {
 381     const_iterator __j = __y.find(*__i);
 382     if (__j == __ey || !(*__i == *__j))
 383       return false;
 384   }
 385   return true;
 386 }
 387
 388 template <class _Value, class _Hash, class _Pred, class _Alloc>
 389 inline _LIBCPP_HIDE_FROM_ABI bool
 390 operator!=(const hash_set<_Value, _Hash, _Pred, _Alloc>& __x, const hash_set<_Value, _Hash, _Pred, _Alloc>& __y) {
 391   return !(__x == __y);
 392 }
 393
 394 template <class _Value,
 395           class _Hash  = hash<_Value>,
 396           class _Pred  = std::equal_to<_Value>,
 397           class _Alloc = std::allocator<_Value> >
 398 class _LIBCPP_TEMPLATE_VIS hash_multiset {
 399 public:
 400   // types
 401   typedef _Value key_type;
 402   typedef key_type value_type;
 403   typedef _Hash hasher;
 404   typedef _Pred key_equal;
 405   typedef _Alloc allocator_type;
 406   typedef value_type& reference;
 407   typedef const value_type& const_reference;
 408
 409 private:
 410   typedef std::__hash_table<value_type, hasher, key_equal, allocator_type> __table;
 411
 412   __table __table_;
 413
 414 public:
 415   typedef typename __table::pointer pointer;
 416   typedef typename __table::const_pointer const_pointer;
 417   typedef typename __table::size_type size_type;
 418   typedef typename __table::difference_type difference_type;
 419
 420   typedef typename __table::const_iterator iterator;
 421   typedef typename __table::const_iterator const_iterator;
 422
 423   _LIBCPP_HIDE_FROM_ABI hash_multiset() {}
 424   explicit _LIBCPP_HIDE_FROM_ABI
 425   hash_multiset(size_type __n, const hasher& __hf = hasher(), const key_equal& __eql = key_equal());
 426   _LIBCPP_HIDE_FROM_ABI
 427   hash_multiset(size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a);
 428   template <class _InputIterator>
 429   _LIBCPP_HIDE_FROM_ABI hash_multiset(_InputIterator __first, _InputIterator __last);
 430   template <class _InputIterator>
 431   _LIBCPP_HIDE_FROM_ABI
 432   hash_multiset(_InputIterator __first,
 433                 _InputIterator __last,
 434                 size_type __n,
 435                 const hasher& __hf     = hasher(),
 436                 const key_equal& __eql = key_equal());
 437   template <class _InputIterator>
 438   _LIBCPP_HIDE_FROM_ABI hash_multiset(
 439       _InputIterator __first,
 440       _InputIterator __last,
 441       size_type __n,
 442       const hasher& __hf,
 443       const key_equal& __eql,
 444       const allocator_type& __a);
 445   _LIBCPP_HIDE_FROM_ABI hash_multiset(const hash_multiset& __u);
 446
 447   _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const { return allocator_type(__table_.__node_alloc()); }
 448
 449   _LIBCPP_HIDE_FROM_ABI bool empty() const { return __table_.size() == 0; }
 450   _LIBCPP_HIDE_FROM_ABI size_type size() const { return __table_.size(); }
 451   _LIBCPP_HIDE_FROM_ABI size_type max_size() const { return __table_.max_size(); }
 452
 453   _LIBCPP_HIDE_FROM_ABI iterator begin() { return __table_.begin(); }
 454   _LIBCPP_HIDE_FROM_ABI iterator end() { return __table_.end(); }
 455   _LIBCPP_HIDE_FROM_ABI const_iterator begin() const { return __table_.begin(); }
 456   _LIBCPP_HIDE_FROM_ABI const_iterator end() const { return __table_.end(); }
 457
 458   _LIBCPP_HIDE_FROM_ABI iterator insert(const value_type& __x) { return __table_.__insert_multi(__x); }
 459   _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator, const value_type& __x) { return insert(__x); }
 460   template <class _InputIterator>
 461   _LIBCPP_HIDE_FROM_ABI void insert(_InputIterator __first, _InputIterator __last);
 462
 463   _LIBCPP_HIDE_FROM_ABI void erase(const_iterator __p) { __table_.erase(__p); }
 464   _LIBCPP_HIDE_FROM_ABI size_type erase(const key_type& __k) { return __table_.__erase_multi(__k); }
 465   _LIBCPP_HIDE_FROM_ABI void erase(const_iterator __first, const_iterator __last) { __table_.erase(__first, __last); }
 466   _LIBCPP_HIDE_FROM_ABI void clear() { __table_.clear(); }
 467
 468   _LIBCPP_HIDE_FROM_ABI void swap(hash_multiset& __u) { __table_.swap(__u.__table_); }
 469
 470   _LIBCPP_HIDE_FROM_ABI hasher hash_funct() const { return __table_.hash_function(); }
 471   _LIBCPP_HIDE_FROM_ABI key_equal key_eq() const { return __table_.key_eq(); }
 472
 473   _LIBCPP_HIDE_FROM_ABI iterator find(const key_type& __k) { return __table_.find(__k); }
 474   _LIBCPP_HIDE_FROM_ABI const_iterator find(const key_type& __k) const { return __table_.find(__k); }
 475   _LIBCPP_HIDE_FROM_ABI size_type count(const key_type& __k) const { return __table_.__count_multi(__k); }
 476   _LIBCPP_HIDE_FROM_ABI std::pair<iterator, iterator> equal_range(const key_type& __k) {
 477     return __table_.__equal_range_multi(__k);
 478   }
 479   _LIBCPP_HIDE_FROM_ABI std::pair<const_iterator, const_iterator> equal_range(const key_type& __k) const {
 480     return __table_.__equal_range_multi(__k);
 481   }
 482
 483   _LIBCPP_HIDE_FROM_ABI size_type bucket_count() const { return __table_.bucket_count(); }
 484   _LIBCPP_HIDE_FROM_ABI size_type max_bucket_count() const { return __table_.max_bucket_count(); }
 485
 486   _LIBCPP_HIDE_FROM_ABI size_type elems_in_bucket(size_type __n) const { return __table_.bucket_size(__n); }
 487
 488   _LIBCPP_HIDE_FROM_ABI void resize(size_type __n) { __table_.__rehash_multi(__n); }
 489 };
 490
 491 template <class _Value, class _Hash, class _Pred, class _Alloc>
 492 hash_multiset<_Value, _Hash, _Pred, _Alloc>::hash_multiset(size_type __n, const hasher& __hf, const key_equal& __eql)
 493     : __table_(__hf, __eql) {
 494   __table_.__rehash_multi(__n);
 495 }
 496
 497 template <class _Value, class _Hash, class _Pred, class _Alloc>
 498 hash_multiset<_Value, _Hash, _Pred, _Alloc>::hash_multiset(
 499     size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
 500     : __table_(__hf, __eql, __a) {
 501   __table_.__rehash_multi(__n);
 502 }
 503
 504 template <class _Value, class _Hash, class _Pred, class _Alloc>
 505 template <class _InputIterator>
 506 hash_multiset<_Value, _Hash, _Pred, _Alloc>::hash_multiset(_InputIterator __first, _InputIterator __last) {
 507   insert(__first, __last);
 508 }
 509
 510 template <class _Value, class _Hash, class _Pred, class _Alloc>
 511 template <class _InputIterator>
 512 hash_multiset<_Value, _Hash, _Pred, _Alloc>::hash_multiset(
 513     _InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, const key_equal& __eql)
 514     : __table_(__hf, __eql) {
 515   __table_.__rehash_multi(__n);
 516   insert(__first, __last);
 517 }
 518
 519 template <class _Value, class _Hash, class _Pred, class _Alloc>
 520 template <class _InputIterator>
 521 hash_multiset<_Value, _Hash, _Pred, _Alloc>::hash_multiset(
 522     _InputIterator __first,
 523     _InputIterator __last,
 524     size_type __n,
 525     const hasher& __hf,
 526     const key_equal& __eql,
 527     const allocator_type& __a)
 528     : __table_(__hf, __eql, __a) {
 529   __table_.__rehash_multi(__n);
 530   insert(__first, __last);
 531 }
 532
 533 template <class _Value, class _Hash, class _Pred, class _Alloc>
 534 hash_multiset<_Value, _Hash, _Pred, _Alloc>::hash_multiset(const hash_multiset& __u) : __table_(__u.__table_) {
 535   __table_.__rehash_multi(__u.bucket_count());
 536   insert(__u.begin(), __u.end());
 537 }
 538
 539 template <class _Value, class _Hash, class _Pred, class _Alloc>
 540 template <class _InputIterator>
 541 inline void hash_multiset<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, _InputIterator __last) {
 542   for (; __first != __last; ++__first)
 543     __table_.__insert_multi(*__first);
 544 }
 545
 546 template <class _Value, class _Hash, class _Pred, class _Alloc>
 547 inline _LIBCPP_HIDE_FROM_ABI void
 548 swap(hash_multiset<_Value, _Hash, _Pred, _Alloc>& __x, hash_multiset<_Value, _Hash, _Pred, _Alloc>& __y) {
 549   __x.swap(__y);
 550 }
 551
 552 template <class _Value, class _Hash, class _Pred, class _Alloc>
 553 _LIBCPP_HIDE_FROM_ABI bool operator==(const hash_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
 554                                       const hash_multiset<_Value, _Hash, _Pred, _Alloc>& __y) {
 555   if (__x.size() != __y.size())
 556     return false;
 557   typedef typename hash_multiset<_Value, _Hash, _Pred, _Alloc>::const_iterator const_iterator;
 558   typedef std::pair<const_iterator, const_iterator> _EqRng;
 559   for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;) {
 560     _EqRng __xeq = __x.equal_range(*__i);
 561     _EqRng __yeq = __y.equal_range(*__i);
 562     if (std::distance(__xeq.first, __xeq.second) != std::distance(__yeq.first, __yeq.second) ||
 563         !std::is_permutation(__xeq.first, __xeq.second, __yeq.first))
 564       return false;
 565     __i = __xeq.second;
 566   }
 567   return true;
 568 }
 569
 570 template <class _Value, class _Hash, class _Pred, class _Alloc>
 571 inline _LIBCPP_HIDE_FROM_ABI bool operator!=(const hash_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
 572                                              const hash_multiset<_Value, _Hash, _Pred, _Alloc>& __y) {
 573   return !(__x == __y);
 574 }
 575
 576 } // namespace __gnu_cxx
 577
 578 #if !defined(_LIBCPP_REMOVE_TRANSITIVE_INCLUDES) && _LIBCPP_STD_VER <= 20
 579 #  include <concepts>
 580 #  include <iterator>
 581 #  include <type_traits>
 582 #endif
 583
 584 #endif // _LIBCPP_HASH_SET