contrib/libc++/include/unordered_set

   1 // -*- C++ -*-
   2 //===-------------------------- unordered_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_UNORDERED_SET
  12 #define _LIBCPP_UNORDERED_SET
  13
  14 /*
  15
  16     unordered_set synopsis
  17
  18 #include <initializer_list>
  19
  20 namespace std
  21 {
  22
  23 template <class Value, class Hash = hash<Value>, class Pred = equal_to<Value>,
  24           class Alloc = allocator<Value>>
  25 class unordered_set
  26 {
  27 public:
  28     // types
  29     typedef Value                                                      key_type;
  30     typedef key_type                                                   value_type;
  31     typedef Hash                                                       hasher;
  32     typedef Pred                                                       key_equal;
  33     typedef Alloc                                                      allocator_type;
  34     typedef value_type&                                                reference;
  35     typedef const value_type&                                          const_reference;
  36     typedef typename allocator_traits<allocator_type>::pointer         pointer;
  37     typedef typename allocator_traits<allocator_type>::const_pointer   const_pointer;
  38     typedef typename allocator_traits<allocator_type>::size_type       size_type;
  39     typedef typename allocator_traits<allocator_type>::difference_type difference_type;
  40
  41     typedef /unspecified/ iterator;
  42     typedef /unspecified/ const_iterator;
  43     typedef /unspecified/ local_iterator;
  44     typedef /unspecified/ const_local_iterator;
  45
  46     unordered_set()
  47         noexcept(
  48             is_nothrow_default_constructible<hasher>::value &&
  49             is_nothrow_default_constructible<key_equal>::value &&
  50             is_nothrow_default_constructible<allocator_type>::value);
  51     explicit unordered_set(size_type n, const hasher& hf = hasher(),
  52                            const key_equal& eql = key_equal(),
  53                            const allocator_type& a = allocator_type());
  54     template <class InputIterator>
  55         unordered_set(InputIterator f, InputIterator l,
  56                       size_type n = 0, const hasher& hf = hasher(),
  57                       const key_equal& eql = key_equal(),
  58                       const allocator_type& a = allocator_type());
  59     explicit unordered_set(const allocator_type&);
  60     unordered_set(const unordered_set&);
  61     unordered_set(const unordered_set&, const Allocator&);
  62     unordered_set(unordered_set&&)
  63         noexcept(
  64             is_nothrow_move_constructible<hasher>::value &&
  65             is_nothrow_move_constructible<key_equal>::value &&
  66             is_nothrow_move_constructible<allocator_type>::value);
  67     unordered_set(unordered_set&&, const Allocator&);
  68     unordered_set(initializer_list<value_type>, size_type n = 0,
  69                   const hasher& hf = hasher(), const key_equal& eql = key_equal(),
  70                   const allocator_type& a = allocator_type());
  71     ~unordered_set();
  72     unordered_set& operator=(const unordered_set&);
  73     unordered_set& operator=(unordered_set&&)
  74         noexcept(
  75             allocator_type::propagate_on_container_move_assignment::value &&
  76             is_nothrow_move_assignable<allocator_type>::value &&
  77             is_nothrow_move_assignable<hasher>::value &&
  78             is_nothrow_move_assignable<key_equal>::value);
  79     unordered_set& operator=(initializer_list<value_type>);
  80
  81     allocator_type get_allocator() const noexcept;
  82
  83     bool      empty() const noexcept;
  84     size_type size() const noexcept;
  85     size_type max_size() const noexcept;
  86
  87     iterator       begin() noexcept;
  88     iterator       end() noexcept;
  89     const_iterator begin()  const noexcept;
  90     const_iterator end()    const noexcept;
  91     const_iterator cbegin() const noexcept;
  92     const_iterator cend()   const noexcept;
  93
  94     template <class... Args>
  95         pair<iterator, bool> emplace(Args&&... args);
  96     template <class... Args>
  97         iterator emplace_hint(const_iterator position, Args&&... args);
  98     pair<iterator, bool> insert(const value_type& obj);
  99     pair<iterator, bool> insert(value_type&& obj);
 100     iterator insert(const_iterator hint, const value_type& obj);
 101     iterator insert(const_iterator hint, value_type&& obj);
 102     template <class InputIterator>
 103         void insert(InputIterator first, InputIterator last);
 104     void insert(initializer_list<value_type>);
 105
 106     iterator erase(const_iterator position);
 107     size_type erase(const key_type& k);
 108     iterator erase(const_iterator first, const_iterator last);
 109     void clear() noexcept;
 110
 111     void swap(unordered_set&)
 112         noexcept(
 113             (!allocator_type::propagate_on_container_swap::value ||
 114              __is_nothrow_swappable<allocator_type>::value) &&
 115             __is_nothrow_swappable<hasher>::value &&
 116             __is_nothrow_swappable<key_equal>::value);
 117
 118     hasher hash_function() const;
 119     key_equal key_eq() const;
 120
 121     iterator       find(const key_type& k);
 122     const_iterator find(const key_type& k) const;
 123     size_type count(const key_type& k) const;
 124     pair<iterator, iterator>             equal_range(const key_type& k);
 125     pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
 126
 127     size_type bucket_count() const noexcept;
 128     size_type max_bucket_count() const noexcept;
 129
 130     size_type bucket_size(size_type n) const;
 131     size_type bucket(const key_type& k) const;
 132
 133     local_iterator       begin(size_type n);
 134     local_iterator       end(size_type n);
 135     const_local_iterator begin(size_type n) const;
 136     const_local_iterator end(size_type n) const;
 137     const_local_iterator cbegin(size_type n) const;
 138     const_local_iterator cend(size_type n) const;
 139
 140     float load_factor() const noexcept;
 141     float max_load_factor() const noexcept;
 142     void max_load_factor(float z);
 143     void rehash(size_type n);
 144     void reserve(size_type n);
 145 };
 146
 147 template <class Value, class Hash, class Pred, class Alloc>
 148     void swap(unordered_set<Value, Hash, Pred, Alloc>& x,
 149               unordered_set<Value, Hash, Pred, Alloc>& y)
 150               noexcept(noexcept(x.swap(y)));
 151
 152 template <class Value, class Hash, class Pred, class Alloc>
 153     bool
 154     operator==(const unordered_set<Value, Hash, Pred, Alloc>& x,
 155                const unordered_set<Value, Hash, Pred, Alloc>& y);
 156
 157 template <class Value, class Hash, class Pred, class Alloc>
 158     bool
 159     operator!=(const unordered_set<Value, Hash, Pred, Alloc>& x,
 160                const unordered_set<Value, Hash, Pred, Alloc>& y);
 161
 162 template <class Value, class Hash = hash<Value>, class Pred = equal_to<Value>,
 163           class Alloc = allocator<Value>>
 164 class unordered_multiset
 165 {
 166 public:
 167     // types
 168     typedef Value                                                      key_type;
 169     typedef key_type                                                   value_type;
 170     typedef Hash                                                       hasher;
 171     typedef Pred                                                       key_equal;
 172     typedef Alloc                                                      allocator_type;
 173     typedef value_type&                                                reference;
 174     typedef const value_type&                                          const_reference;
 175     typedef typename allocator_traits<allocator_type>::pointer         pointer;
 176     typedef typename allocator_traits<allocator_type>::const_pointer   const_pointer;
 177     typedef typename allocator_traits<allocator_type>::size_type       size_type;
 178     typedef typename allocator_traits<allocator_type>::difference_type difference_type;
 179
 180     typedef /unspecified/ iterator;
 181     typedef /unspecified/ const_iterator;
 182     typedef /unspecified/ local_iterator;
 183     typedef /unspecified/ const_local_iterator;
 184
 185     unordered_multiset()
 186         noexcept(
 187             is_nothrow_default_constructible<hasher>::value &&
 188             is_nothrow_default_constructible<key_equal>::value &&
 189             is_nothrow_default_constructible<allocator_type>::value);
 190     explicit unordered_multiset(size_type n, const hasher& hf = hasher(),
 191                            const key_equal& eql = key_equal(),
 192                            const allocator_type& a = allocator_type());
 193     template <class InputIterator>
 194         unordered_multiset(InputIterator f, InputIterator l,
 195                       size_type n = 0, const hasher& hf = hasher(),
 196                       const key_equal& eql = key_equal(),
 197                       const allocator_type& a = allocator_type());
 198     explicit unordered_multiset(const allocator_type&);
 199     unordered_multiset(const unordered_multiset&);
 200     unordered_multiset(const unordered_multiset&, const Allocator&);
 201     unordered_multiset(unordered_multiset&&)
 202         noexcept(
 203             is_nothrow_move_constructible<hasher>::value &&
 204             is_nothrow_move_constructible<key_equal>::value &&
 205             is_nothrow_move_constructible<allocator_type>::value);
 206     unordered_multiset(unordered_multiset&&, const Allocator&);
 207     unordered_multiset(initializer_list<value_type>, size_type n = /see below/,
 208                   const hasher& hf = hasher(), const key_equal& eql = key_equal(),
 209                   const allocator_type& a = allocator_type());
 210     ~unordered_multiset();
 211     unordered_multiset& operator=(const unordered_multiset&);
 212     unordered_multiset& operator=(unordered_multiset&&)
 213         noexcept(
 214             allocator_type::propagate_on_container_move_assignment::value &&
 215             is_nothrow_move_assignable<allocator_type>::value &&
 216             is_nothrow_move_assignable<hasher>::value &&
 217             is_nothrow_move_assignable<key_equal>::value);
 218     unordered_multiset& operator=(initializer_list<value_type>);
 219
 220     allocator_type get_allocator() const noexcept;
 221
 222     bool      empty() const noexcept;
 223     size_type size() const noexcept;
 224     size_type max_size() const noexcept;
 225
 226     iterator       begin() noexcept;
 227     iterator       end() noexcept;
 228     const_iterator begin()  const noexcept;
 229     const_iterator end()    const noexcept;
 230     const_iterator cbegin() const noexcept;
 231     const_iterator cend()   const noexcept;
 232
 233     template <class... Args>
 234         iterator emplace(Args&&... args);
 235     template <class... Args>
 236         iterator emplace_hint(const_iterator position, Args&&... args);
 237     iterator insert(const value_type& obj);
 238     iterator insert(value_type&& obj);
 239     iterator insert(const_iterator hint, const value_type& obj);
 240     iterator insert(const_iterator hint, value_type&& obj);
 241     template <class InputIterator>
 242         void insert(InputIterator first, InputIterator last);
 243     void insert(initializer_list<value_type>);
 244
 245     iterator erase(const_iterator position);
 246     size_type erase(const key_type& k);
 247     iterator erase(const_iterator first, const_iterator last);
 248     void clear() noexcept;
 249
 250     void swap(unordered_multiset&)
 251         noexcept(
 252             (!allocator_type::propagate_on_container_swap::value ||
 253              __is_nothrow_swappable<allocator_type>::value) &&
 254             __is_nothrow_swappable<hasher>::value &&
 255             __is_nothrow_swappable<key_equal>::value);
 256
 257     hasher hash_function() const;
 258     key_equal key_eq() const;
 259
 260     iterator       find(const key_type& k);
 261     const_iterator find(const key_type& k) const;
 262     size_type count(const key_type& k) const;
 263     pair<iterator, iterator>             equal_range(const key_type& k);
 264     pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
 265
 266     size_type bucket_count() const noexcept;
 267     size_type max_bucket_count() const noexcept;
 268
 269     size_type bucket_size(size_type n) const;
 270     size_type bucket(const key_type& k) const;
 271
 272     local_iterator       begin(size_type n);
 273     local_iterator       end(size_type n);
 274     const_local_iterator begin(size_type n) const;
 275     const_local_iterator end(size_type n) const;
 276     const_local_iterator cbegin(size_type n) const;
 277     const_local_iterator cend(size_type n) const;
 278
 279     float load_factor() const noexcept;
 280     float max_load_factor() const noexcept;
 281     void max_load_factor(float z);
 282     void rehash(size_type n);
 283     void reserve(size_type n);
 284 };
 285
 286 template <class Value, class Hash, class Pred, class Alloc>
 287     void swap(unordered_multiset<Value, Hash, Pred, Alloc>& x,
 288               unordered_multiset<Value, Hash, Pred, Alloc>& y)
 289               noexcept(noexcept(x.swap(y)));
 290
 291 template <class Value, class Hash, class Pred, class Alloc>
 292     bool
 293     operator==(const unordered_multiset<Value, Hash, Pred, Alloc>& x,
 294                const unordered_multiset<Value, Hash, Pred, Alloc>& y);
 295
 296 template <class Value, class Hash, class Pred, class Alloc>
 297     bool
 298     operator!=(const unordered_multiset<Value, Hash, Pred, Alloc>& x,
 299                const unordered_multiset<Value, Hash, Pred, Alloc>& y);
 300 }  // std
 301
 302 */
 303
 304 #include <__config>
 305 #include <__hash_table>
 306 #include <functional>
 307
 308 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 309 #pragma GCC system_header
 310 #endif
 311
 312 _LIBCPP_BEGIN_NAMESPACE_STD
 313
 314 template <class _Value, class _Hash = hash<_Value>, class _Pred = equal_to<_Value>,
 315           class _Alloc = allocator<_Value> >
 316 class _LIBCPP_TYPE_VIS unordered_set
 317 {
 318 public:
 319     // types
 320     typedef _Value                                                     key_type;
 321     typedef key_type                                                   value_type;
 322     typedef _Hash                                                      hasher;
 323     typedef _Pred                                                      key_equal;
 324     typedef _Alloc                                                     allocator_type;
 325     typedef value_type&                                                reference;
 326     typedef const value_type&                                          const_reference;
 327
 328 private:
 329     typedef __hash_table<value_type, hasher, key_equal, allocator_type> __table;
 330
 331     __table __table_;
 332
 333 public:
 334     typedef typename __table::pointer         pointer;
 335     typedef typename __table::const_pointer   const_pointer;
 336     typedef typename __table::size_type       size_type;
 337     typedef typename __table::difference_type difference_type;
 338
 339     typedef typename __table::const_iterator       iterator;
 340     typedef typename __table::const_iterator       const_iterator;
 341     typedef typename __table::const_local_iterator local_iterator;
 342     typedef typename __table::const_local_iterator const_local_iterator;
 343
 344     _LIBCPP_INLINE_VISIBILITY
 345     unordered_set()
 346         _NOEXCEPT_(is_nothrow_default_constructible<__table>::value)
 347         {} // = default;
 348     explicit unordered_set(size_type __n, const hasher& __hf = hasher(),
 349                            const key_equal& __eql = key_equal());
 350     unordered_set(size_type __n, const hasher& __hf, const key_equal& __eql,
 351                   const allocator_type& __a);
 352     template <class _InputIterator>
 353         unordered_set(_InputIterator __first, _InputIterator __last);
 354     template <class _InputIterator>
 355         unordered_set(_InputIterator __first, _InputIterator __last,
 356                       size_type __n, const hasher& __hf = hasher(),
 357                       const key_equal& __eql = key_equal());
 358     template <class _InputIterator>
 359         unordered_set(_InputIterator __first, _InputIterator __last,
 360                       size_type __n, const hasher& __hf, const key_equal& __eql,
 361                       const allocator_type& __a);
 362     explicit unordered_set(const allocator_type& __a);
 363     unordered_set(const unordered_set& __u);
 364     unordered_set(const unordered_set& __u, const allocator_type& __a);
 365 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 366     unordered_set(unordered_set&& __u)
 367         _NOEXCEPT_(is_nothrow_move_constructible<__table>::value);
 368     unordered_set(unordered_set&& __u, const allocator_type& __a);
 369 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
 370 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
 371     unordered_set(initializer_list<value_type> __il);
 372     unordered_set(initializer_list<value_type> __il, size_type __n,
 373                   const hasher& __hf = hasher(),
 374                   const key_equal& __eql = key_equal());
 375     unordered_set(initializer_list<value_type> __il, size_type __n,
 376                   const hasher& __hf, const key_equal& __eql,
 377                   const allocator_type& __a);
 378 #endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
 379     // ~unordered_set() = default;
 380     _LIBCPP_INLINE_VISIBILITY
 381     unordered_set& operator=(const unordered_set& __u)
 382     {
 383         __table_ = __u.__table_;
 384         return *this;
 385     }
 386 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 387     unordered_set& operator=(unordered_set&& __u)
 388         _NOEXCEPT_(is_nothrow_move_assignable<__table>::value);
 389 #endif
 390 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
 391     unordered_set& operator=(initializer_list<value_type> __il);
 392 #endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
 393
 394     _LIBCPP_INLINE_VISIBILITY
 395     allocator_type get_allocator() const _NOEXCEPT
 396         {return allocator_type(__table_.__node_alloc());}
 397
 398     _LIBCPP_INLINE_VISIBILITY
 399     bool      empty() const _NOEXCEPT {return __table_.size() == 0;}
 400     _LIBCPP_INLINE_VISIBILITY
 401     size_type size() const _NOEXCEPT  {return __table_.size();}
 402     _LIBCPP_INLINE_VISIBILITY
 403     size_type max_size() const _NOEXCEPT {return __table_.max_size();}
 404
 405     _LIBCPP_INLINE_VISIBILITY
 406     iterator       begin() _NOEXCEPT        {return __table_.begin();}
 407     _LIBCPP_INLINE_VISIBILITY
 408     iterator       end() _NOEXCEPT          {return __table_.end();}
 409     _LIBCPP_INLINE_VISIBILITY
 410     const_iterator begin()  const _NOEXCEPT {return __table_.begin();}
 411     _LIBCPP_INLINE_VISIBILITY
 412     const_iterator end()    const _NOEXCEPT {return __table_.end();}
 413     _LIBCPP_INLINE_VISIBILITY
 414     const_iterator cbegin() const _NOEXCEPT {return __table_.begin();}
 415     _LIBCPP_INLINE_VISIBILITY
 416     const_iterator cend()   const _NOEXCEPT {return __table_.end();}
 417
 418 #if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
 419     template <class... _Args>
 420         _LIBCPP_INLINE_VISIBILITY
 421         pair<iterator, bool> emplace(_Args&&... __args)
 422             {return __table_.__emplace_unique(_VSTD::forward<_Args>(__args)...);}
 423     template <class... _Args>
 424         _LIBCPP_INLINE_VISIBILITY
 425         iterator emplace_hint(const_iterator, _Args&&... __args)
 426             {return __table_.__emplace_unique(_VSTD::forward<_Args>(__args)...).first;}
 427 #endif  // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
 428     _LIBCPP_INLINE_VISIBILITY
 429     pair<iterator, bool> insert(const value_type& __x)
 430         {return __table_.__insert_unique(__x);}
 431 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 432     _LIBCPP_INLINE_VISIBILITY
 433     pair<iterator, bool> insert(value_type&& __x)
 434         {return __table_.__insert_unique(_VSTD::move(__x));}
 435 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
 436     _LIBCPP_INLINE_VISIBILITY
 437     iterator insert(const_iterator, const value_type& __x)
 438         {return insert(__x).first;}
 439 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 440     _LIBCPP_INLINE_VISIBILITY
 441     iterator insert(const_iterator, value_type&& __x)
 442         {return insert(_VSTD::move(__x)).first;}
 443 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
 444     template <class _InputIterator>
 445         void insert(_InputIterator __first, _InputIterator __last);
 446 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
 447     _LIBCPP_INLINE_VISIBILITY
 448     void insert(initializer_list<value_type> __il)
 449         {insert(__il.begin(), __il.end());}
 450 #endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
 451
 452     _LIBCPP_INLINE_VISIBILITY
 453     iterator erase(const_iterator __p) {return __table_.erase(__p);}
 454     _LIBCPP_INLINE_VISIBILITY
 455     size_type erase(const key_type& __k) {return __table_.__erase_unique(__k);}
 456     _LIBCPP_INLINE_VISIBILITY
 457     iterator erase(const_iterator __first, const_iterator __last)
 458         {return __table_.erase(__first, __last);}
 459     _LIBCPP_INLINE_VISIBILITY
 460     void clear() _NOEXCEPT {__table_.clear();}
 461
 462     _LIBCPP_INLINE_VISIBILITY
 463     void swap(unordered_set& __u)
 464         _NOEXCEPT_(__is_nothrow_swappable<__table>::value)
 465         {__table_.swap(__u.__table_);}
 466
 467     _LIBCPP_INLINE_VISIBILITY
 468     hasher hash_function() const {return __table_.hash_function();}
 469     _LIBCPP_INLINE_VISIBILITY
 470     key_equal key_eq() const {return __table_.key_eq();}
 471
 472     _LIBCPP_INLINE_VISIBILITY
 473     iterator       find(const key_type& __k)       {return __table_.find(__k);}
 474     _LIBCPP_INLINE_VISIBILITY
 475     const_iterator find(const key_type& __k) const {return __table_.find(__k);}
 476     _LIBCPP_INLINE_VISIBILITY
 477     size_type count(const key_type& __k) const {return __table_.__count_unique(__k);}
 478     _LIBCPP_INLINE_VISIBILITY
 479     pair<iterator, iterator>             equal_range(const key_type& __k)
 480         {return __table_.__equal_range_unique(__k);}
 481     _LIBCPP_INLINE_VISIBILITY
 482     pair<const_iterator, const_iterator> equal_range(const key_type& __k) const
 483         {return __table_.__equal_range_unique(__k);}
 484
 485     _LIBCPP_INLINE_VISIBILITY
 486     size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();}
 487     _LIBCPP_INLINE_VISIBILITY
 488     size_type max_bucket_count() const _NOEXCEPT {return __table_.max_bucket_count();}
 489
 490     _LIBCPP_INLINE_VISIBILITY
 491     size_type bucket_size(size_type __n) const {return __table_.bucket_size(__n);}
 492     _LIBCPP_INLINE_VISIBILITY
 493     size_type bucket(const key_type& __k) const {return __table_.bucket(__k);}
 494
 495     _LIBCPP_INLINE_VISIBILITY
 496     local_iterator       begin(size_type __n)        {return __table_.begin(__n);}
 497     _LIBCPP_INLINE_VISIBILITY
 498     local_iterator       end(size_type __n)          {return __table_.end(__n);}
 499     _LIBCPP_INLINE_VISIBILITY
 500     const_local_iterator begin(size_type __n) const  {return __table_.cbegin(__n);}
 501     _LIBCPP_INLINE_VISIBILITY
 502     const_local_iterator end(size_type __n) const    {return __table_.cend(__n);}
 503     _LIBCPP_INLINE_VISIBILITY
 504     const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);}
 505     _LIBCPP_INLINE_VISIBILITY
 506     const_local_iterator cend(size_type __n) const   {return __table_.cend(__n);}
 507
 508     _LIBCPP_INLINE_VISIBILITY
 509     float load_factor() const _NOEXCEPT {return __table_.load_factor();}
 510     _LIBCPP_INLINE_VISIBILITY
 511     float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();}
 512     _LIBCPP_INLINE_VISIBILITY
 513     void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);}
 514     _LIBCPP_INLINE_VISIBILITY
 515     void rehash(size_type __n) {__table_.rehash(__n);}
 516     _LIBCPP_INLINE_VISIBILITY
 517     void reserve(size_type __n) {__table_.reserve(__n);}
 518 };
 519
 520 template <class _Value, class _Hash, class _Pred, class _Alloc>
 521 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(size_type __n,
 522         const hasher& __hf, const key_equal& __eql)
 523     : __table_(__hf, __eql)
 524 {
 525     __table_.rehash(__n);
 526 }
 527
 528 template <class _Value, class _Hash, class _Pred, class _Alloc>
 529 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(size_type __n,
 530         const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
 531     : __table_(__hf, __eql, __a)
 532 {
 533     __table_.rehash(__n);
 534 }
 535
 536 template <class _Value, class _Hash, class _Pred, class _Alloc>
 537 template <class _InputIterator>
 538 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
 539         _InputIterator __first, _InputIterator __last)
 540 {
 541     insert(__first, __last);
 542 }
 543
 544 template <class _Value, class _Hash, class _Pred, class _Alloc>
 545 template <class _InputIterator>
 546 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
 547         _InputIterator __first, _InputIterator __last, size_type __n,
 548         const hasher& __hf, const key_equal& __eql)
 549     : __table_(__hf, __eql)
 550 {
 551     __table_.rehash(__n);
 552     insert(__first, __last);
 553 }
 554
 555 template <class _Value, class _Hash, class _Pred, class _Alloc>
 556 template <class _InputIterator>
 557 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
 558         _InputIterator __first, _InputIterator __last, size_type __n,
 559         const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
 560     : __table_(__hf, __eql, __a)
 561 {
 562     __table_.rehash(__n);
 563     insert(__first, __last);
 564 }
 565
 566 template <class _Value, class _Hash, class _Pred, class _Alloc>
 567 inline _LIBCPP_INLINE_VISIBILITY
 568 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
 569         const allocator_type& __a)
 570     : __table_(__a)
 571 {
 572 }
 573
 574 template <class _Value, class _Hash, class _Pred, class _Alloc>
 575 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
 576         const unordered_set& __u)
 577     : __table_(__u.__table_)
 578 {
 579     __table_.rehash(__u.bucket_count());
 580     insert(__u.begin(), __u.end());
 581 }
 582
 583 template <class _Value, class _Hash, class _Pred, class _Alloc>
 584 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
 585         const unordered_set& __u, const allocator_type& __a)
 586     : __table_(__u.__table_, __a)
 587 {
 588     __table_.rehash(__u.bucket_count());
 589     insert(__u.begin(), __u.end());
 590 }
 591
 592 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 593
 594 template <class _Value, class _Hash, class _Pred, class _Alloc>
 595 inline _LIBCPP_INLINE_VISIBILITY
 596 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
 597         unordered_set&& __u)
 598     _NOEXCEPT_(is_nothrow_move_constructible<__table>::value)
 599     : __table_(_VSTD::move(__u.__table_))
 600 {
 601 }
 602
 603 template <class _Value, class _Hash, class _Pred, class _Alloc>
 604 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
 605         unordered_set&& __u, const allocator_type& __a)
 606     : __table_(_VSTD::move(__u.__table_), __a)
 607 {
 608     if (__a != __u.get_allocator())
 609     {
 610         iterator __i = __u.begin();
 611         while (__u.size() != 0)
 612             __table_.__insert_unique(_VSTD::move(__u.__table_.remove(__i++)->__value_));
 613     }
 614 }
 615
 616 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
 617
 618 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
 619
 620 template <class _Value, class _Hash, class _Pred, class _Alloc>
 621 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
 622         initializer_list<value_type> __il)
 623 {
 624     insert(__il.begin(), __il.end());
 625 }
 626
 627 template <class _Value, class _Hash, class _Pred, class _Alloc>
 628 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
 629         initializer_list<value_type> __il, size_type __n, const hasher& __hf,
 630         const key_equal& __eql)
 631     : __table_(__hf, __eql)
 632 {
 633     __table_.rehash(__n);
 634     insert(__il.begin(), __il.end());
 635 }
 636
 637 template <class _Value, class _Hash, class _Pred, class _Alloc>
 638 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
 639         initializer_list<value_type> __il, size_type __n, const hasher& __hf,
 640         const key_equal& __eql, const allocator_type& __a)
 641     : __table_(__hf, __eql, __a)
 642 {
 643     __table_.rehash(__n);
 644     insert(__il.begin(), __il.end());
 645 }
 646
 647 #endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
 648
 649 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 650
 651 template <class _Value, class _Hash, class _Pred, class _Alloc>
 652 inline _LIBCPP_INLINE_VISIBILITY
 653 unordered_set<_Value, _Hash, _Pred, _Alloc>&
 654 unordered_set<_Value, _Hash, _Pred, _Alloc>::operator=(unordered_set&& __u)
 655     _NOEXCEPT_(is_nothrow_move_assignable<__table>::value)
 656 {
 657     __table_ = _VSTD::move(__u.__table_);
 658     return *this;
 659 }
 660
 661 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
 662
 663 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
 664
 665 template <class _Value, class _Hash, class _Pred, class _Alloc>
 666 inline _LIBCPP_INLINE_VISIBILITY
 667 unordered_set<_Value, _Hash, _Pred, _Alloc>&
 668 unordered_set<_Value, _Hash, _Pred, _Alloc>::operator=(
 669         initializer_list<value_type> __il)
 670 {
 671     __table_.__assign_unique(__il.begin(), __il.end());
 672     return *this;
 673 }
 674
 675 #endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
 676
 677 template <class _Value, class _Hash, class _Pred, class _Alloc>
 678 template <class _InputIterator>
 679 inline _LIBCPP_INLINE_VISIBILITY
 680 void
 681 unordered_set<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator __first,
 682                                                     _InputIterator __last)
 683 {
 684     for (; __first != __last; ++__first)
 685         __table_.__insert_unique(*__first);
 686 }
 687
 688 template <class _Value, class _Hash, class _Pred, class _Alloc>
 689 inline _LIBCPP_INLINE_VISIBILITY
 690 void
 691 swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
 692      unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
 693     _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
 694 {
 695     __x.swap(__y);
 696 }
 697
 698 template <class _Value, class _Hash, class _Pred, class _Alloc>
 699 bool
 700 operator==(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
 701            const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
 702 {
 703     if (__x.size() != __y.size())
 704         return false;
 705     typedef typename unordered_set<_Value, _Hash, _Pred, _Alloc>::const_iterator
 706                                                                  const_iterator;
 707     for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end();
 708             __i != __ex; ++__i)
 709     {
 710         const_iterator __j = __y.find(*__i);
 711         if (__j == __ey || !(*__i == *__j))
 712             return false;
 713     }
 714     return true;
 715 }
 716
 717 template <class _Value, class _Hash, class _Pred, class _Alloc>
 718 inline _LIBCPP_INLINE_VISIBILITY
 719 bool
 720 operator!=(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
 721            const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
 722 {
 723     return !(__x == __y);
 724 }
 725
 726 template <class _Value, class _Hash = hash<_Value>, class _Pred = equal_to<_Value>,
 727           class _Alloc = allocator<_Value> >
 728 class _LIBCPP_TYPE_VIS unordered_multiset
 729 {
 730 public:
 731     // types
 732     typedef _Value                                                     key_type;
 733     typedef key_type                                                   value_type;
 734     typedef _Hash                                                      hasher;
 735     typedef _Pred                                                      key_equal;
 736     typedef _Alloc                                                     allocator_type;
 737     typedef value_type&                                                reference;
 738     typedef const value_type&                                          const_reference;
 739
 740 private:
 741     typedef __hash_table<value_type, hasher, key_equal, allocator_type> __table;
 742
 743     __table __table_;
 744
 745 public:
 746     typedef typename __table::pointer         pointer;
 747     typedef typename __table::const_pointer   const_pointer;
 748     typedef typename __table::size_type       size_type;
 749     typedef typename __table::difference_type difference_type;
 750
 751     typedef typename __table::const_iterator       iterator;
 752     typedef typename __table::const_iterator       const_iterator;
 753     typedef typename __table::const_local_iterator local_iterator;
 754     typedef typename __table::const_local_iterator const_local_iterator;
 755
 756     _LIBCPP_INLINE_VISIBILITY
 757     unordered_multiset()
 758         _NOEXCEPT_(is_nothrow_default_constructible<__table>::value)
 759         {} // = default
 760     explicit unordered_multiset(size_type __n, const hasher& __hf = hasher(),
 761                                 const key_equal& __eql = key_equal());
 762     unordered_multiset(size_type __n, const hasher& __hf,
 763                        const key_equal& __eql, const allocator_type& __a);
 764     template <class _InputIterator>
 765         unordered_multiset(_InputIterator __first, _InputIterator __last);
 766     template <class _InputIterator>
 767         unordered_multiset(_InputIterator __first, _InputIterator __last,
 768                       size_type __n, const hasher& __hf = hasher(),
 769                       const key_equal& __eql = key_equal());
 770     template <class _InputIterator>
 771         unordered_multiset(_InputIterator __first, _InputIterator __last,
 772                       size_type __n , const hasher& __hf,
 773                       const key_equal& __eql, const allocator_type& __a);
 774     explicit unordered_multiset(const allocator_type& __a);
 775     unordered_multiset(const unordered_multiset& __u);
 776     unordered_multiset(const unordered_multiset& __u, const allocator_type& __a);
 777 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 778     unordered_multiset(unordered_multiset&& __u)
 779         _NOEXCEPT_(is_nothrow_move_constructible<__table>::value);
 780     unordered_multiset(unordered_multiset&& __u, const allocator_type& __a);
 781 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
 782 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
 783     unordered_multiset(initializer_list<value_type> __il);
 784     unordered_multiset(initializer_list<value_type> __il, size_type __n,
 785                        const hasher& __hf = hasher(),
 786                        const key_equal& __eql = key_equal());
 787     unordered_multiset(initializer_list<value_type> __il, size_type __n,
 788                        const hasher& __hf, const key_equal& __eql,
 789                        const allocator_type& __a);
 790 #endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
 791     // ~unordered_multiset() = default;
 792     _LIBCPP_INLINE_VISIBILITY
 793     unordered_multiset& operator=(const unordered_multiset& __u)
 794     {
 795         __table_ = __u.__table_;
 796         return *this;
 797     }
 798 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 799     unordered_multiset& operator=(unordered_multiset&& __u)
 800         _NOEXCEPT_(is_nothrow_move_assignable<__table>::value);
 801 #endif
 802 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
 803     unordered_multiset& operator=(initializer_list<value_type> __il);
 804 #endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
 805
 806     _LIBCPP_INLINE_VISIBILITY
 807     allocator_type get_allocator() const _NOEXCEPT
 808         {return allocator_type(__table_.__node_alloc());}
 809
 810     _LIBCPP_INLINE_VISIBILITY
 811     bool      empty() const _NOEXCEPT {return __table_.size() == 0;}
 812     _LIBCPP_INLINE_VISIBILITY
 813     size_type size() const _NOEXCEPT  {return __table_.size();}
 814     _LIBCPP_INLINE_VISIBILITY
 815     size_type max_size() const _NOEXCEPT {return __table_.max_size();}
 816
 817     _LIBCPP_INLINE_VISIBILITY
 818     iterator       begin() _NOEXCEPT        {return __table_.begin();}
 819     _LIBCPP_INLINE_VISIBILITY
 820     iterator       end() _NOEXCEPT          {return __table_.end();}
 821     _LIBCPP_INLINE_VISIBILITY
 822     const_iterator begin()  const _NOEXCEPT {return __table_.begin();}
 823     _LIBCPP_INLINE_VISIBILITY
 824     const_iterator end()    const _NOEXCEPT {return __table_.end();}
 825     _LIBCPP_INLINE_VISIBILITY
 826     const_iterator cbegin() const _NOEXCEPT {return __table_.begin();}
 827     _LIBCPP_INLINE_VISIBILITY
 828     const_iterator cend()   const _NOEXCEPT {return __table_.end();}
 829
 830 #if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
 831     template <class... _Args>
 832         _LIBCPP_INLINE_VISIBILITY
 833         iterator emplace(_Args&&... __args)
 834             {return __table_.__emplace_multi(_VSTD::forward<_Args>(__args)...);}
 835     template <class... _Args>
 836         _LIBCPP_INLINE_VISIBILITY
 837         iterator emplace_hint(const_iterator __p, _Args&&... __args)
 838             {return __table_.__emplace_hint_multi(__p, _VSTD::forward<_Args>(__args)...);}
 839 #endif  // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
 840     _LIBCPP_INLINE_VISIBILITY
 841     iterator insert(const value_type& __x) {return __table_.__insert_multi(__x);}
 842 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 843     _LIBCPP_INLINE_VISIBILITY
 844     iterator insert(value_type&& __x) {return __table_.__insert_multi(_VSTD::move(__x));}
 845 #endif
 846     _LIBCPP_INLINE_VISIBILITY
 847     iterator insert(const_iterator __p, const value_type& __x)
 848         {return __table_.__insert_multi(__p, __x);}
 849 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 850     _LIBCPP_INLINE_VISIBILITY
 851     iterator insert(const_iterator __p, value_type&& __x)
 852         {return __table_.__insert_multi(__p, _VSTD::move(__x));}
 853 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
 854     template <class _InputIterator>
 855         void insert(_InputIterator __first, _InputIterator __last);
 856 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
 857     _LIBCPP_INLINE_VISIBILITY
 858     void insert(initializer_list<value_type> __il)
 859         {insert(__il.begin(), __il.end());}
 860 #endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
 861
 862     _LIBCPP_INLINE_VISIBILITY
 863     iterator erase(const_iterator __p) {return __table_.erase(__p);}
 864     _LIBCPP_INLINE_VISIBILITY
 865     size_type erase(const key_type& __k) {return __table_.__erase_multi(__k);}
 866     _LIBCPP_INLINE_VISIBILITY
 867     iterator erase(const_iterator __first, const_iterator __last)
 868         {return __table_.erase(__first, __last);}
 869     _LIBCPP_INLINE_VISIBILITY
 870     void clear() _NOEXCEPT {__table_.clear();}
 871
 872     _LIBCPP_INLINE_VISIBILITY
 873     void swap(unordered_multiset& __u)
 874         _NOEXCEPT_(__is_nothrow_swappable<__table>::value)
 875         {__table_.swap(__u.__table_);}
 876
 877     _LIBCPP_INLINE_VISIBILITY
 878     hasher hash_function() const {return __table_.hash_function();}
 879     _LIBCPP_INLINE_VISIBILITY
 880     key_equal key_eq() const {return __table_.key_eq();}
 881
 882     _LIBCPP_INLINE_VISIBILITY
 883     iterator       find(const key_type& __k)       {return __table_.find(__k);}
 884     _LIBCPP_INLINE_VISIBILITY
 885     const_iterator find(const key_type& __k) const {return __table_.find(__k);}
 886     _LIBCPP_INLINE_VISIBILITY
 887     size_type count(const key_type& __k) const {return __table_.__count_multi(__k);}
 888     _LIBCPP_INLINE_VISIBILITY
 889     pair<iterator, iterator>             equal_range(const key_type& __k)
 890         {return __table_.__equal_range_multi(__k);}
 891     _LIBCPP_INLINE_VISIBILITY
 892     pair<const_iterator, const_iterator> equal_range(const key_type& __k) const
 893         {return __table_.__equal_range_multi(__k);}
 894
 895     _LIBCPP_INLINE_VISIBILITY
 896     size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();}
 897     _LIBCPP_INLINE_VISIBILITY
 898     size_type max_bucket_count() const _NOEXCEPT {return __table_.max_bucket_count();}
 899
 900     _LIBCPP_INLINE_VISIBILITY
 901     size_type bucket_size(size_type __n) const {return __table_.bucket_size(__n);}
 902     _LIBCPP_INLINE_VISIBILITY
 903     size_type bucket(const key_type& __k) const {return __table_.bucket(__k);}
 904
 905     _LIBCPP_INLINE_VISIBILITY
 906     local_iterator       begin(size_type __n)        {return __table_.begin(__n);}
 907     _LIBCPP_INLINE_VISIBILITY
 908     local_iterator       end(size_type __n)          {return __table_.end(__n);}
 909     _LIBCPP_INLINE_VISIBILITY
 910     const_local_iterator begin(size_type __n) const  {return __table_.cbegin(__n);}
 911     _LIBCPP_INLINE_VISIBILITY
 912     const_local_iterator end(size_type __n) const    {return __table_.cend(__n);}
 913     _LIBCPP_INLINE_VISIBILITY
 914     const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);}
 915     _LIBCPP_INLINE_VISIBILITY
 916     const_local_iterator cend(size_type __n) const   {return __table_.cend(__n);}
 917
 918     _LIBCPP_INLINE_VISIBILITY
 919     float load_factor() const _NOEXCEPT {return __table_.load_factor();}
 920     _LIBCPP_INLINE_VISIBILITY
 921     float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();}
 922     _LIBCPP_INLINE_VISIBILITY
 923     void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);}
 924     _LIBCPP_INLINE_VISIBILITY
 925     void rehash(size_type __n) {__table_.rehash(__n);}
 926     _LIBCPP_INLINE_VISIBILITY
 927     void reserve(size_type __n) {__table_.reserve(__n);}
 928 };
 929
 930 template <class _Value, class _Hash, class _Pred, class _Alloc>
 931 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
 932         size_type __n, const hasher& __hf, const key_equal& __eql)
 933     : __table_(__hf, __eql)
 934 {
 935     __table_.rehash(__n);
 936 }
 937
 938 template <class _Value, class _Hash, class _Pred, class _Alloc>
 939 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
 940         size_type __n, const hasher& __hf, const key_equal& __eql,
 941         const allocator_type& __a)
 942     : __table_(__hf, __eql, __a)
 943 {
 944     __table_.rehash(__n);
 945 }
 946
 947 template <class _Value, class _Hash, class _Pred, class _Alloc>
 948 template <class _InputIterator>
 949 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
 950         _InputIterator __first, _InputIterator __last)
 951 {
 952     insert(__first, __last);
 953 }
 954
 955 template <class _Value, class _Hash, class _Pred, class _Alloc>
 956 template <class _InputIterator>
 957 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
 958         _InputIterator __first, _InputIterator __last, size_type __n,
 959         const hasher& __hf, const key_equal& __eql)
 960     : __table_(__hf, __eql)
 961 {
 962     __table_.rehash(__n);
 963     insert(__first, __last);
 964 }
 965
 966 template <class _Value, class _Hash, class _Pred, class _Alloc>
 967 template <class _InputIterator>
 968 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
 969         _InputIterator __first, _InputIterator __last, size_type __n,
 970         const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
 971     : __table_(__hf, __eql, __a)
 972 {
 973     __table_.rehash(__n);
 974     insert(__first, __last);
 975 }
 976
 977 template <class _Value, class _Hash, class _Pred, class _Alloc>
 978 inline _LIBCPP_INLINE_VISIBILITY
 979 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
 980         const allocator_type& __a)
 981     : __table_(__a)
 982 {
 983 }
 984
 985 template <class _Value, class _Hash, class _Pred, class _Alloc>
 986 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
 987         const unordered_multiset& __u)
 988     : __table_(__u.__table_)
 989 {
 990     __table_.rehash(__u.bucket_count());
 991     insert(__u.begin(), __u.end());
 992 }
 993
 994 template <class _Value, class _Hash, class _Pred, class _Alloc>
 995 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
 996         const unordered_multiset& __u, const allocator_type& __a)
 997     : __table_(__u.__table_, __a)
 998 {
 999     __table_.rehash(__u.bucket_count());
1000     insert(__u.begin(), __u.end());
1001 }
1002
1003 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1004
1005 template <class _Value, class _Hash, class _Pred, class _Alloc>
1006 inline _LIBCPP_INLINE_VISIBILITY
1007 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1008         unordered_multiset&& __u)
1009     _NOEXCEPT_(is_nothrow_move_constructible<__table>::value)
1010     : __table_(_VSTD::move(__u.__table_))
1011 {
1012 }
1013
1014 template <class _Value, class _Hash, class _Pred, class _Alloc>
1015 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1016         unordered_multiset&& __u, const allocator_type& __a)
1017     : __table_(_VSTD::move(__u.__table_), __a)
1018 {
1019     if (__a != __u.get_allocator())
1020     {
1021         iterator __i = __u.begin();
1022         while (__u.size() != 0)
1023             __table_.__insert_multi(_VSTD::move(__u.__table_.remove(__i++)->__value_));
1024     }
1025 }
1026
1027 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1028
1029 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1030
1031 template <class _Value, class _Hash, class _Pred, class _Alloc>
1032 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1033         initializer_list<value_type> __il)
1034 {
1035     insert(__il.begin(), __il.end());
1036 }
1037
1038 template <class _Value, class _Hash, class _Pred, class _Alloc>
1039 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1040         initializer_list<value_type> __il, size_type __n, const hasher& __hf,
1041         const key_equal& __eql)
1042     : __table_(__hf, __eql)
1043 {
1044     __table_.rehash(__n);
1045     insert(__il.begin(), __il.end());
1046 }
1047
1048 template <class _Value, class _Hash, class _Pred, class _Alloc>
1049 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1050         initializer_list<value_type> __il, size_type __n, const hasher& __hf,
1051         const key_equal& __eql, const allocator_type& __a)
1052     : __table_(__hf, __eql, __a)
1053 {
1054     __table_.rehash(__n);
1055     insert(__il.begin(), __il.end());
1056 }
1057
1058 #endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1059
1060 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1061
1062 template <class _Value, class _Hash, class _Pred, class _Alloc>
1063 inline _LIBCPP_INLINE_VISIBILITY
1064 unordered_multiset<_Value, _Hash, _Pred, _Alloc>&
1065 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::operator=(
1066         unordered_multiset&& __u)
1067     _NOEXCEPT_(is_nothrow_move_assignable<__table>::value)
1068 {
1069     __table_ = _VSTD::move(__u.__table_);
1070     return *this;
1071 }
1072
1073 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1074
1075 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1076
1077 template <class _Value, class _Hash, class _Pred, class _Alloc>
1078 inline
1079 unordered_multiset<_Value, _Hash, _Pred, _Alloc>&
1080 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::operator=(
1081         initializer_list<value_type> __il)
1082 {
1083     __table_.__assign_multi(__il.begin(), __il.end());
1084     return *this;
1085 }
1086
1087 #endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1088
1089 template <class _Value, class _Hash, class _Pred, class _Alloc>
1090 template <class _InputIterator>
1091 inline _LIBCPP_INLINE_VISIBILITY
1092 void
1093 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator __first,
1094                                                          _InputIterator __last)
1095 {
1096     for (; __first != __last; ++__first)
1097         __table_.__insert_multi(*__first);
1098 }
1099
1100 template <class _Value, class _Hash, class _Pred, class _Alloc>
1101 inline _LIBCPP_INLINE_VISIBILITY
1102 void
1103 swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1104      unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1105     _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
1106 {
1107     __x.swap(__y);
1108 }
1109
1110 template <class _Value, class _Hash, class _Pred, class _Alloc>
1111 bool
1112 operator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1113            const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1114 {
1115     if (__x.size() != __y.size())
1116         return false;
1117     typedef typename unordered_multiset<_Value, _Hash, _Pred, _Alloc>::const_iterator
1118                                                                  const_iterator;
1119     typedef pair<const_iterator, const_iterator> _EqRng;
1120     for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;)
1121     {
1122         _EqRng __xeq = __x.equal_range(*__i);
1123         _EqRng __yeq = __y.equal_range(*__i);
1124         if (_VSTD::distance(__xeq.first, __xeq.second) !=
1125             _VSTD::distance(__yeq.first, __yeq.second) ||
1126                   !_VSTD::is_permutation(__xeq.first, __xeq.second, __yeq.first))
1127             return false;
1128         __i = __xeq.second;
1129     }
1130     return true;
1131 }
1132
1133 template <class _Value, class _Hash, class _Pred, class _Alloc>
1134 inline _LIBCPP_INLINE_VISIBILITY
1135 bool
1136 operator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1137            const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1138 {
1139     return !(__x == __y);
1140 }
1141
1142 _LIBCPP_END_NAMESPACE_STD
1143
1144 #endif  // _LIBCPP_UNORDERED_SET