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 #if defined(_MSC_VER) && ! defined(__clang__)
 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 namespace __gnu_cxx {
 210
 211 using namespace std;
 212
 213 template <class _Value, class _Hash = hash<_Value>, class _Pred = equal_to<_Value>,
 214           class _Alloc = allocator<_Value> >
 215 class _LIBCPP_TYPE_VIS_ONLY hash_set
 216 {
 217 public:
 218     // types
 219     typedef _Value                                                     key_type;
 220     typedef key_type                                                   value_type;
 221     typedef _Hash                                                      hasher;
 222     typedef _Pred                                                      key_equal;
 223     typedef _Alloc                                                     allocator_type;
 224     typedef value_type&                                                reference;
 225     typedef const value_type&                                          const_reference;
 226
 227 private:
 228     typedef __hash_table<value_type, hasher, key_equal, allocator_type> __table;
 229
 230     __table __table_;
 231
 232 public:
 233     typedef typename __table::pointer         pointer;
 234     typedef typename __table::const_pointer   const_pointer;
 235     typedef typename __table::size_type       size_type;
 236     typedef typename __table::difference_type difference_type;
 237
 238     typedef typename __table::const_iterator       iterator;
 239     typedef typename __table::const_iterator       const_iterator;
 240
 241     _LIBCPP_INLINE_VISIBILITY
 242     hash_set() {__table_.rehash(193);}
 243     explicit hash_set(size_type __n, const hasher& __hf = hasher(),
 244                            const key_equal& __eql = key_equal());
 245     hash_set(size_type __n, const hasher& __hf, const key_equal& __eql,
 246                   const allocator_type& __a);
 247     template <class _InputIterator>
 248         hash_set(_InputIterator __first, _InputIterator __last);
 249     template <class _InputIterator>
 250         hash_set(_InputIterator __first, _InputIterator __last,
 251                       size_type __n, const hasher& __hf = hasher(),
 252                       const key_equal& __eql = key_equal());
 253     template <class _InputIterator>
 254         hash_set(_InputIterator __first, _InputIterator __last,
 255                       size_type __n, const hasher& __hf, const key_equal& __eql,
 256                       const allocator_type& __a);
 257     hash_set(const hash_set& __u);
 258
 259     _LIBCPP_INLINE_VISIBILITY
 260     allocator_type get_allocator() const
 261         {return allocator_type(__table_.__node_alloc());}
 262
 263     _LIBCPP_INLINE_VISIBILITY
 264     bool      empty() const {return __table_.size() == 0;}
 265     _LIBCPP_INLINE_VISIBILITY
 266     size_type size() const  {return __table_.size();}
 267     _LIBCPP_INLINE_VISIBILITY
 268     size_type max_size() const {return __table_.max_size();}
 269
 270     _LIBCPP_INLINE_VISIBILITY
 271     iterator       begin()        {return __table_.begin();}
 272     _LIBCPP_INLINE_VISIBILITY
 273     iterator       end()          {return __table_.end();}
 274     _LIBCPP_INLINE_VISIBILITY
 275     const_iterator begin()  const {return __table_.begin();}
 276     _LIBCPP_INLINE_VISIBILITY
 277     const_iterator end()    const {return __table_.end();}
 278
 279     _LIBCPP_INLINE_VISIBILITY
 280     pair<iterator, bool> insert(const value_type& __x)
 281         {return __table_.__insert_unique(__x);}
 282     _LIBCPP_INLINE_VISIBILITY
 283     iterator insert(const_iterator, const value_type& __x) {return insert(__x).first;}
 284     template <class _InputIterator>
 285         void insert(_InputIterator __first, _InputIterator __last);
 286
 287     _LIBCPP_INLINE_VISIBILITY
 288     void erase(const_iterator __p) {__table_.erase(__p);}
 289     _LIBCPP_INLINE_VISIBILITY
 290     size_type erase(const key_type& __k) {return __table_.__erase_unique(__k);}
 291     _LIBCPP_INLINE_VISIBILITY
 292     void erase(const_iterator __first, const_iterator __last)
 293         {__table_.erase(__first, __last);}
 294     _LIBCPP_INLINE_VISIBILITY
 295     void clear() {__table_.clear();}
 296
 297     _LIBCPP_INLINE_VISIBILITY
 298     void swap(hash_set& __u) {__table_.swap(__u.__table_);}
 299
 300     _LIBCPP_INLINE_VISIBILITY
 301     hasher hash_funct() const {return __table_.hash_function();}
 302     _LIBCPP_INLINE_VISIBILITY
 303     key_equal key_eq() const {return __table_.key_eq();}
 304
 305     _LIBCPP_INLINE_VISIBILITY
 306     iterator       find(const key_type& __k)       {return __table_.find(__k);}
 307     _LIBCPP_INLINE_VISIBILITY
 308     const_iterator find(const key_type& __k) const {return __table_.find(__k);}
 309     _LIBCPP_INLINE_VISIBILITY
 310     size_type count(const key_type& __k) const {return __table_.__count_unique(__k);}
 311     _LIBCPP_INLINE_VISIBILITY
 312     pair<iterator, iterator>             equal_range(const key_type& __k)
 313         {return __table_.__equal_range_unique(__k);}
 314     _LIBCPP_INLINE_VISIBILITY
 315     pair<const_iterator, const_iterator> equal_range(const key_type& __k) const
 316         {return __table_.__equal_range_unique(__k);}
 317
 318     _LIBCPP_INLINE_VISIBILITY
 319     size_type bucket_count() const {return __table_.bucket_count();}
 320     _LIBCPP_INLINE_VISIBILITY
 321     size_type max_bucket_count() const {return __table_.max_bucket_count();}
 322
 323     _LIBCPP_INLINE_VISIBILITY
 324     size_type elems_in_bucket(size_type __n) const {return __table_.bucket_size(__n);}
 325
 326     _LIBCPP_INLINE_VISIBILITY
 327     void resize(size_type __n) {__table_.rehash(__n);}
 328 };
 329
 330 template <class _Value, class _Hash, class _Pred, class _Alloc>
 331 hash_set<_Value, _Hash, _Pred, _Alloc>::hash_set(size_type __n,
 332         const hasher& __hf, const key_equal& __eql)
 333     : __table_(__hf, __eql)
 334 {
 335     __table_.rehash(__n);
 336 }
 337
 338 template <class _Value, class _Hash, class _Pred, class _Alloc>
 339 hash_set<_Value, _Hash, _Pred, _Alloc>::hash_set(size_type __n,
 340         const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
 341     : __table_(__hf, __eql, __a)
 342 {
 343     __table_.rehash(__n);
 344 }
 345
 346 template <class _Value, class _Hash, class _Pred, class _Alloc>
 347 template <class _InputIterator>
 348 hash_set<_Value, _Hash, _Pred, _Alloc>::hash_set(
 349         _InputIterator __first, _InputIterator __last)
 350 {
 351     __table_.rehash(193);
 352     insert(__first, __last);
 353 }
 354
 355 template <class _Value, class _Hash, class _Pred, class _Alloc>
 356 template <class _InputIterator>
 357 hash_set<_Value, _Hash, _Pred, _Alloc>::hash_set(
 358         _InputIterator __first, _InputIterator __last, size_type __n,
 359         const hasher& __hf, const key_equal& __eql)
 360     : __table_(__hf, __eql)
 361 {
 362     __table_.rehash(__n);
 363     insert(__first, __last);
 364 }
 365
 366 template <class _Value, class _Hash, class _Pred, class _Alloc>
 367 template <class _InputIterator>
 368 hash_set<_Value, _Hash, _Pred, _Alloc>::hash_set(
 369         _InputIterator __first, _InputIterator __last, size_type __n,
 370         const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
 371     : __table_(__hf, __eql, __a)
 372 {
 373     __table_.rehash(__n);
 374     insert(__first, __last);
 375 }
 376
 377 template <class _Value, class _Hash, class _Pred, class _Alloc>
 378 hash_set<_Value, _Hash, _Pred, _Alloc>::hash_set(
 379         const hash_set& __u)
 380     : __table_(__u.__table_)
 381 {
 382     __table_.rehash(__u.bucket_count());
 383     insert(__u.begin(), __u.end());
 384 }
 385
 386 template <class _Value, class _Hash, class _Pred, class _Alloc>
 387 template <class _InputIterator>
 388 inline _LIBCPP_INLINE_VISIBILITY
 389 void
 390 hash_set<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator __first,
 391                                                     _InputIterator __last)
 392 {
 393     for (; __first != __last; ++__first)
 394         __table_.__insert_unique(*__first);
 395 }
 396
 397 template <class _Value, class _Hash, class _Pred, class _Alloc>
 398 inline _LIBCPP_INLINE_VISIBILITY
 399 void
 400 swap(hash_set<_Value, _Hash, _Pred, _Alloc>& __x,
 401      hash_set<_Value, _Hash, _Pred, _Alloc>& __y)
 402 {
 403     __x.swap(__y);
 404 }
 405
 406 template <class _Value, class _Hash, class _Pred, class _Alloc>
 407 bool
 408 operator==(const hash_set<_Value, _Hash, _Pred, _Alloc>& __x,
 409            const hash_set<_Value, _Hash, _Pred, _Alloc>& __y)
 410 {
 411     if (__x.size() != __y.size())
 412         return false;
 413     typedef typename hash_set<_Value, _Hash, _Pred, _Alloc>::const_iterator
 414                                                                  const_iterator;
 415     for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end();
 416             __i != __ex; ++__i)
 417     {
 418         const_iterator __j = __y.find(*__i);
 419         if (__j == __ey || !(*__i == *__j))
 420             return false;
 421     }
 422     return true;
 423 }
 424
 425 template <class _Value, class _Hash, class _Pred, class _Alloc>
 426 inline _LIBCPP_INLINE_VISIBILITY
 427 bool
 428 operator!=(const hash_set<_Value, _Hash, _Pred, _Alloc>& __x,
 429            const hash_set<_Value, _Hash, _Pred, _Alloc>& __y)
 430 {
 431     return !(__x == __y);
 432 }
 433
 434 template <class _Value, class _Hash = hash<_Value>, class _Pred = equal_to<_Value>,
 435           class _Alloc = allocator<_Value> >
 436 class _LIBCPP_TYPE_VIS_ONLY hash_multiset
 437 {
 438 public:
 439     // types
 440     typedef _Value                                                     key_type;
 441     typedef key_type                                                   value_type;
 442     typedef _Hash                                                      hasher;
 443     typedef _Pred                                                      key_equal;
 444     typedef _Alloc                                                     allocator_type;
 445     typedef value_type&                                                reference;
 446     typedef const value_type&                                          const_reference;
 447
 448 private:
 449     typedef __hash_table<value_type, hasher, key_equal, allocator_type> __table;
 450
 451     __table __table_;
 452
 453 public:
 454     typedef typename __table::pointer         pointer;
 455     typedef typename __table::const_pointer   const_pointer;
 456     typedef typename __table::size_type       size_type;
 457     typedef typename __table::difference_type difference_type;
 458
 459     typedef typename __table::const_iterator       iterator;
 460     typedef typename __table::const_iterator       const_iterator;
 461
 462     _LIBCPP_INLINE_VISIBILITY
 463     hash_multiset() {__table_.rehash(193);}
 464     explicit hash_multiset(size_type __n, const hasher& __hf = hasher(),
 465                                 const key_equal& __eql = key_equal());
 466     hash_multiset(size_type __n, const hasher& __hf,
 467                        const key_equal& __eql, const allocator_type& __a);
 468     template <class _InputIterator>
 469         hash_multiset(_InputIterator __first, _InputIterator __last);
 470     template <class _InputIterator>
 471         hash_multiset(_InputIterator __first, _InputIterator __last,
 472                       size_type __n, const hasher& __hf = hasher(),
 473                       const key_equal& __eql = key_equal());
 474     template <class _InputIterator>
 475         hash_multiset(_InputIterator __first, _InputIterator __last,
 476                       size_type __n , const hasher& __hf,
 477                       const key_equal& __eql, const allocator_type& __a);
 478     hash_multiset(const hash_multiset& __u);
 479
 480     _LIBCPP_INLINE_VISIBILITY
 481     allocator_type get_allocator() const
 482         {return allocator_type(__table_.__node_alloc());}
 483
 484     _LIBCPP_INLINE_VISIBILITY
 485     bool      empty() const {return __table_.size() == 0;}
 486     _LIBCPP_INLINE_VISIBILITY
 487     size_type size() const  {return __table_.size();}
 488     _LIBCPP_INLINE_VISIBILITY
 489     size_type max_size() const {return __table_.max_size();}
 490
 491     _LIBCPP_INLINE_VISIBILITY
 492     iterator       begin()        {return __table_.begin();}
 493     _LIBCPP_INLINE_VISIBILITY
 494     iterator       end()          {return __table_.end();}
 495     _LIBCPP_INLINE_VISIBILITY
 496     const_iterator begin()  const {return __table_.begin();}
 497     _LIBCPP_INLINE_VISIBILITY
 498     const_iterator end()    const {return __table_.end();}
 499
 500     _LIBCPP_INLINE_VISIBILITY
 501     iterator insert(const value_type& __x) {return __table_.__insert_multi(__x);}
 502     _LIBCPP_INLINE_VISIBILITY
 503     iterator insert(const_iterator, const value_type& __x) {return insert(__x);}
 504     template <class _InputIterator>
 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     pair<iterator, iterator>             equal_range(const key_type& __k)
 533         {return __table_.__equal_range_multi(__k);}
 534     _LIBCPP_INLINE_VISIBILITY
 535     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 _LIBCPP_INLINE_VISIBILITY
 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 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