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