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() {__table_.rehash(193);}
 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     __table_.rehash(193);
 351     insert(__first, __last);
 352 }
 353
 354 template <class _Value, class _Hash, class _Pred, class _Alloc>
 355 template <class _InputIterator>
 356 hash_set<_Value, _Hash, _Pred, _Alloc>::hash_set(
 357         _InputIterator __first, _InputIterator __last, size_type __n,
 358         const hasher& __hf, const key_equal& __eql)
 359     : __table_(__hf, __eql)
 360 {
 361     __table_.rehash(__n);
 362     insert(__first, __last);
 363 }
 364
 365 template <class _Value, class _Hash, class _Pred, class _Alloc>
 366 template <class _InputIterator>
 367 hash_set<_Value, _Hash, _Pred, _Alloc>::hash_set(
 368         _InputIterator __first, _InputIterator __last, size_type __n,
 369         const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
 370     : __table_(__hf, __eql, __a)
 371 {
 372     __table_.rehash(__n);
 373     insert(__first, __last);
 374 }
 375
 376 template <class _Value, class _Hash, class _Pred, class _Alloc>
 377 hash_set<_Value, _Hash, _Pred, _Alloc>::hash_set(
 378         const hash_set& __u)
 379     : __table_(__u.__table_)
 380 {
 381     __table_.rehash(__u.bucket_count());
 382     insert(__u.begin(), __u.end());
 383 }
 384
 385 template <class _Value, class _Hash, class _Pred, class _Alloc>
 386 template <class _InputIterator>
 387 inline
 388 void
 389 hash_set<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator __first,
 390                                                     _InputIterator __last)
 391 {
 392     for (; __first != __last; ++__first)
 393         __table_.__insert_unique(*__first);
 394 }
 395
 396 template <class _Value, class _Hash, class _Pred, class _Alloc>
 397 inline _LIBCPP_INLINE_VISIBILITY
 398 void
 399 swap(hash_set<_Value, _Hash, _Pred, _Alloc>& __x,
 400      hash_set<_Value, _Hash, _Pred, _Alloc>& __y)
 401 {
 402     __x.swap(__y);
 403 }
 404
 405 template <class _Value, class _Hash, class _Pred, class _Alloc>
 406 bool
 407 operator==(const hash_set<_Value, _Hash, _Pred, _Alloc>& __x,
 408            const hash_set<_Value, _Hash, _Pred, _Alloc>& __y)
 409 {
 410     if (__x.size() != __y.size())
 411         return false;
 412     typedef typename hash_set<_Value, _Hash, _Pred, _Alloc>::const_iterator
 413                                                                  const_iterator;
 414     for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end();
 415             __i != __ex; ++__i)
 416     {
 417         const_iterator __j = __y.find(*__i);
 418         if (__j == __ey || !(*__i == *__j))
 419             return false;
 420     }
 421     return true;
 422 }
 423
 424 template <class _Value, class _Hash, class _Pred, class _Alloc>
 425 inline _LIBCPP_INLINE_VISIBILITY
 426 bool
 427 operator!=(const hash_set<_Value, _Hash, _Pred, _Alloc>& __x,
 428            const hash_set<_Value, _Hash, _Pred, _Alloc>& __y)
 429 {
 430     return !(__x == __y);
 431 }
 432
 433 template <class _Value, class _Hash = hash<_Value>, class _Pred = std::equal_to<_Value>,
 434           class _Alloc = std::allocator<_Value> >
 435 class _LIBCPP_TEMPLATE_VIS hash_multiset
 436 {
 437 public:
 438     // types
 439     typedef _Value                                                     key_type;
 440     typedef key_type                                                   value_type;
 441     typedef _Hash                                                      hasher;
 442     typedef _Pred                                                      key_equal;
 443     typedef _Alloc                                                     allocator_type;
 444     typedef value_type&                                                reference;
 445     typedef const value_type&                                          const_reference;
 446
 447 private:
 448     typedef std::__hash_table<value_type, hasher, key_equal, allocator_type> __table;
 449
 450     __table __table_;
 451
 452 public:
 453     typedef typename __table::pointer         pointer;
 454     typedef typename __table::const_pointer   const_pointer;
 455     typedef typename __table::size_type       size_type;
 456     typedef typename __table::difference_type difference_type;
 457
 458     typedef typename __table::const_iterator       iterator;
 459     typedef typename __table::const_iterator       const_iterator;
 460
 461     _LIBCPP_INLINE_VISIBILITY
 462     hash_multiset() {__table_.rehash(193);}
 463     explicit hash_multiset(size_type __n, const hasher& __hf = hasher(),
 464                                 const key_equal& __eql = key_equal());
 465     hash_multiset(size_type __n, const hasher& __hf,
 466                        const key_equal& __eql, const allocator_type& __a);
 467     template <class _InputIterator>
 468         hash_multiset(_InputIterator __first, _InputIterator __last);
 469     template <class _InputIterator>
 470         hash_multiset(_InputIterator __first, _InputIterator __last,
 471                       size_type __n, const hasher& __hf = hasher(),
 472                       const key_equal& __eql = key_equal());
 473     template <class _InputIterator>
 474         hash_multiset(_InputIterator __first, _InputIterator __last,
 475                       size_type __n , const hasher& __hf,
 476                       const key_equal& __eql, const allocator_type& __a);
 477     hash_multiset(const hash_multiset& __u);
 478
 479     _LIBCPP_INLINE_VISIBILITY
 480     allocator_type get_allocator() const
 481         {return allocator_type(__table_.__node_alloc());}
 482
 483     _LIBCPP_INLINE_VISIBILITY
 484     bool      empty() const {return __table_.size() == 0;}
 485     _LIBCPP_INLINE_VISIBILITY
 486     size_type size() const  {return __table_.size();}
 487     _LIBCPP_INLINE_VISIBILITY
 488     size_type max_size() const {return __table_.max_size();}
 489
 490     _LIBCPP_INLINE_VISIBILITY
 491     iterator       begin()        {return __table_.begin();}
 492     _LIBCPP_INLINE_VISIBILITY
 493     iterator       end()          {return __table_.end();}
 494     _LIBCPP_INLINE_VISIBILITY
 495     const_iterator begin()  const {return __table_.begin();}
 496     _LIBCPP_INLINE_VISIBILITY
 497     const_iterator end()    const {return __table_.end();}
 498
 499     _LIBCPP_INLINE_VISIBILITY
 500     iterator insert(const value_type& __x) {return __table_.__insert_multi(__x);}
 501     _LIBCPP_INLINE_VISIBILITY
 502     iterator insert(const_iterator, const value_type& __x) {return insert(__x);}
 503     template <class _InputIterator>
 504         _LIBCPP_INLINE_VISIBILITY
 505         void insert(_InputIterator __first, _InputIterator __last);
 506
 507     _LIBCPP_INLINE_VISIBILITY
 508     void erase(const_iterator __p) {__table_.erase(__p);}
 509     _LIBCPP_INLINE_VISIBILITY
 510     size_type erase(const key_type& __k) {return __table_.__erase_multi(__k);}
 511     _LIBCPP_INLINE_VISIBILITY
 512     void erase(const_iterator __first, const_iterator __last)
 513         {__table_.erase(__first, __last);}
 514     _LIBCPP_INLINE_VISIBILITY
 515     void clear() {__table_.clear();}
 516
 517     _LIBCPP_INLINE_VISIBILITY
 518     void swap(hash_multiset& __u) {__table_.swap(__u.__table_);}
 519
 520     _LIBCPP_INLINE_VISIBILITY
 521     hasher hash_funct() const {return __table_.hash_function();}
 522     _LIBCPP_INLINE_VISIBILITY
 523     key_equal key_eq() const {return __table_.key_eq();}
 524
 525     _LIBCPP_INLINE_VISIBILITY
 526     iterator       find(const key_type& __k)       {return __table_.find(__k);}
 527     _LIBCPP_INLINE_VISIBILITY
 528     const_iterator find(const key_type& __k) const {return __table_.find(__k);}
 529     _LIBCPP_INLINE_VISIBILITY
 530     size_type count(const key_type& __k) const {return __table_.__count_multi(__k);}
 531     _LIBCPP_INLINE_VISIBILITY
 532     std::pair<iterator, iterator>             equal_range(const key_type& __k)
 533         {return __table_.__equal_range_multi(__k);}
 534     _LIBCPP_INLINE_VISIBILITY
 535     std::pair<const_iterator, const_iterator> equal_range(const key_type& __k) const
 536         {return __table_.__equal_range_multi(__k);}
 537
 538     _LIBCPP_INLINE_VISIBILITY
 539     size_type bucket_count() const {return __table_.bucket_count();}
 540     _LIBCPP_INLINE_VISIBILITY
 541     size_type max_bucket_count() const {return __table_.max_bucket_count();}
 542
 543     _LIBCPP_INLINE_VISIBILITY
 544     size_type elems_in_bucket(size_type __n) const {return __table_.bucket_size(__n);}
 545
 546     _LIBCPP_INLINE_VISIBILITY
 547     void resize(size_type __n) {__table_.rehash(__n);}
 548 };
 549
 550 template <class _Value, class _Hash, class _Pred, class _Alloc>
 551 hash_multiset<_Value, _Hash, _Pred, _Alloc>::hash_multiset(
 552         size_type __n, const hasher& __hf, const key_equal& __eql)
 553     : __table_(__hf, __eql)
 554 {
 555     __table_.rehash(__n);
 556 }
 557
 558 template <class _Value, class _Hash, class _Pred, class _Alloc>
 559 hash_multiset<_Value, _Hash, _Pred, _Alloc>::hash_multiset(
 560         size_type __n, const hasher& __hf, const key_equal& __eql,
 561         const allocator_type& __a)
 562     : __table_(__hf, __eql, __a)
 563 {
 564     __table_.rehash(__n);
 565 }
 566
 567 template <class _Value, class _Hash, class _Pred, class _Alloc>
 568 template <class _InputIterator>
 569 hash_multiset<_Value, _Hash, _Pred, _Alloc>::hash_multiset(
 570         _InputIterator __first, _InputIterator __last)
 571 {
 572     __table_.rehash(193);
 573     insert(__first, __last);
 574 }
 575
 576 template <class _Value, class _Hash, class _Pred, class _Alloc>
 577 template <class _InputIterator>
 578 hash_multiset<_Value, _Hash, _Pred, _Alloc>::hash_multiset(
 579         _InputIterator __first, _InputIterator __last, size_type __n,
 580         const hasher& __hf, const key_equal& __eql)
 581     : __table_(__hf, __eql)
 582 {
 583     __table_.rehash(__n);
 584     insert(__first, __last);
 585 }
 586
 587 template <class _Value, class _Hash, class _Pred, class _Alloc>
 588 template <class _InputIterator>
 589 hash_multiset<_Value, _Hash, _Pred, _Alloc>::hash_multiset(
 590         _InputIterator __first, _InputIterator __last, size_type __n,
 591         const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
 592     : __table_(__hf, __eql, __a)
 593 {
 594     __table_.rehash(__n);
 595     insert(__first, __last);
 596 }
 597
 598 template <class _Value, class _Hash, class _Pred, class _Alloc>
 599 hash_multiset<_Value, _Hash, _Pred, _Alloc>::hash_multiset(
 600         const hash_multiset& __u)
 601     : __table_(__u.__table_)
 602 {
 603     __table_.rehash(__u.bucket_count());
 604     insert(__u.begin(), __u.end());
 605 }
 606
 607 template <class _Value, class _Hash, class _Pred, class _Alloc>
 608 template <class _InputIterator>
 609 inline
 610 void
 611 hash_multiset<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator __first,
 612                                                     _InputIterator __last)
 613 {
 614     for (; __first != __last; ++__first)
 615         __table_.__insert_multi(*__first);
 616 }
 617
 618 template <class _Value, class _Hash, class _Pred, class _Alloc>
 619 inline _LIBCPP_INLINE_VISIBILITY
 620 void
 621 swap(hash_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
 622      hash_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
 623 {
 624     __x.swap(__y);
 625 }
 626
 627 template <class _Value, class _Hash, class _Pred, class _Alloc>
 628 bool
 629 operator==(const hash_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
 630            const hash_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
 631 {
 632     if (__x.size() != __y.size())
 633         return false;
 634     typedef typename hash_multiset<_Value, _Hash, _Pred, _Alloc>::const_iterator
 635                                                                  const_iterator;
 636     typedef std::pair<const_iterator, const_iterator> _EqRng;
 637     for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;)
 638     {
 639         _EqRng __xeq = __x.equal_range(*__i);
 640         _EqRng __yeq = __y.equal_range(*__i);
 641         if (_VSTD::distance(__xeq.first, __xeq.second) !=
 642             _VSTD::distance(__yeq.first, __yeq.second) ||
 643                   !_VSTD::is_permutation(__xeq.first, __xeq.second, __yeq.first))
 644             return false;
 645         __i = __xeq.second;
 646     }
 647     return true;
 648 }
 649
 650 template <class _Value, class _Hash, class _Pred, class _Alloc>
 651 inline _LIBCPP_INLINE_VISIBILITY
 652 bool
 653 operator!=(const hash_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
 654            const hash_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
 655 {
 656     return !(__x == __y);
 657 }
 658
 659 } // __gnu_cxx
 660
 661 #endif  // _LIBCPP_HASH_SET