contrib/llvm-project/libcxx/include/ext/hash_set

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