contrib/libc++/include/ext/hash_set

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