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(size_type n, const allocator_type& a); // C++14
  72     unordered_set(size_type n, const hasher& hf, const allocator_type& a); // C++14
  73     template <class InputIterator>
  74       unordered_set(InputIterator f, InputIterator l, size_type n, const allocator_type& a); // C++14
  75     template <class InputIterator>
  76       unordered_set(InputIterator f, InputIterator l, size_type n,
  77                     const hasher& hf,  const allocator_type& a); // C++14
  78     unordered_set(initializer_list<value_type> il, size_type n, const allocator_type& a); // C++14
  79     unordered_set(initializer_list<value_type> il, size_type n,
  80                   const hasher& hf,  const allocator_type& a); // C++14
  81     ~unordered_set();
  82     unordered_set& operator=(const unordered_set&);
  83     unordered_set& operator=(unordered_set&&)
  84         noexcept(
  85             allocator_type::propagate_on_container_move_assignment::value &&
  86             is_nothrow_move_assignable<allocator_type>::value &&
  87             is_nothrow_move_assignable<hasher>::value &&
  88             is_nothrow_move_assignable<key_equal>::value);
  89     unordered_set& operator=(initializer_list<value_type>);
  90
  91     allocator_type get_allocator() const noexcept;
  92
  93     bool      empty() const noexcept;
  94     size_type size() const noexcept;
  95     size_type max_size() const noexcept;
  96
  97     iterator       begin() noexcept;
  98     iterator       end() noexcept;
  99     const_iterator begin()  const noexcept;
 100     const_iterator end()    const noexcept;
 101     const_iterator cbegin() const noexcept;
 102     const_iterator cend()   const noexcept;
 103
 104     template <class... Args>
 105         pair<iterator, bool> emplace(Args&&... args);
 106     template <class... Args>
 107         iterator emplace_hint(const_iterator position, Args&&... args);
 108     pair<iterator, bool> insert(const value_type& obj);
 109     pair<iterator, bool> insert(value_type&& obj);
 110     iterator insert(const_iterator hint, const value_type& obj);
 111     iterator insert(const_iterator hint, value_type&& obj);
 112     template <class InputIterator>
 113         void insert(InputIterator first, InputIterator last);
 114     void insert(initializer_list<value_type>);
 115
 116     iterator erase(const_iterator position);
 117     size_type erase(const key_type& k);
 118     iterator erase(const_iterator first, const_iterator last);
 119     void clear() noexcept;
 120
 121     void swap(unordered_set&)
 122         noexcept(
 123             (!allocator_type::propagate_on_container_swap::value ||
 124              __is_nothrow_swappable<allocator_type>::value) &&
 125             __is_nothrow_swappable<hasher>::value &&
 126             __is_nothrow_swappable<key_equal>::value);
 127
 128     hasher hash_function() const;
 129     key_equal key_eq() const;
 130
 131     iterator       find(const key_type& k);
 132     const_iterator find(const key_type& k) const;
 133     size_type count(const key_type& k) const;
 134     pair<iterator, iterator>             equal_range(const key_type& k);
 135     pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
 136
 137     size_type bucket_count() const noexcept;
 138     size_type max_bucket_count() const noexcept;
 139
 140     size_type bucket_size(size_type n) const;
 141     size_type bucket(const key_type& k) const;
 142
 143     local_iterator       begin(size_type n);
 144     local_iterator       end(size_type n);
 145     const_local_iterator begin(size_type n) const;
 146     const_local_iterator end(size_type n) const;
 147     const_local_iterator cbegin(size_type n) const;
 148     const_local_iterator cend(size_type n) const;
 149
 150     float load_factor() const noexcept;
 151     float max_load_factor() const noexcept;
 152     void max_load_factor(float z);
 153     void rehash(size_type n);
 154     void reserve(size_type n);
 155 };
 156
 157 template <class Value, class Hash, class Pred, class Alloc>
 158     void swap(unordered_set<Value, Hash, Pred, Alloc>& x,
 159               unordered_set<Value, Hash, Pred, Alloc>& y)
 160               noexcept(noexcept(x.swap(y)));
 161
 162 template <class Value, class Hash, class Pred, class Alloc>
 163     bool
 164     operator==(const unordered_set<Value, Hash, Pred, Alloc>& x,
 165                const unordered_set<Value, Hash, Pred, Alloc>& y);
 166
 167 template <class Value, class Hash, class Pred, class Alloc>
 168     bool
 169     operator!=(const unordered_set<Value, Hash, Pred, Alloc>& x,
 170                const unordered_set<Value, Hash, Pred, Alloc>& y);
 171
 172 template <class Value, class Hash = hash<Value>, class Pred = equal_to<Value>,
 173           class Alloc = allocator<Value>>
 174 class unordered_multiset
 175 {
 176 public:
 177     // types
 178     typedef Value                                                      key_type;
 179     typedef key_type                                                   value_type;
 180     typedef Hash                                                       hasher;
 181     typedef Pred                                                       key_equal;
 182     typedef Alloc                                                      allocator_type;
 183     typedef value_type&                                                reference;
 184     typedef const value_type&                                          const_reference;
 185     typedef typename allocator_traits<allocator_type>::pointer         pointer;
 186     typedef typename allocator_traits<allocator_type>::const_pointer   const_pointer;
 187     typedef typename allocator_traits<allocator_type>::size_type       size_type;
 188     typedef typename allocator_traits<allocator_type>::difference_type difference_type;
 189
 190     typedef /unspecified/ iterator;
 191     typedef /unspecified/ const_iterator;
 192     typedef /unspecified/ local_iterator;
 193     typedef /unspecified/ const_local_iterator;
 194
 195     unordered_multiset()
 196         noexcept(
 197             is_nothrow_default_constructible<hasher>::value &&
 198             is_nothrow_default_constructible<key_equal>::value &&
 199             is_nothrow_default_constructible<allocator_type>::value);
 200     explicit unordered_multiset(size_type n, const hasher& hf = hasher(),
 201                            const key_equal& eql = key_equal(),
 202                            const allocator_type& a = allocator_type());
 203     template <class InputIterator>
 204         unordered_multiset(InputIterator f, InputIterator l,
 205                       size_type n = 0, const hasher& hf = hasher(),
 206                       const key_equal& eql = key_equal(),
 207                       const allocator_type& a = allocator_type());
 208     explicit unordered_multiset(const allocator_type&);
 209     unordered_multiset(const unordered_multiset&);
 210     unordered_multiset(const unordered_multiset&, const Allocator&);
 211     unordered_multiset(unordered_multiset&&)
 212         noexcept(
 213             is_nothrow_move_constructible<hasher>::value &&
 214             is_nothrow_move_constructible<key_equal>::value &&
 215             is_nothrow_move_constructible<allocator_type>::value);
 216     unordered_multiset(unordered_multiset&&, const Allocator&);
 217     unordered_multiset(initializer_list<value_type>, size_type n = /see below/,
 218                   const hasher& hf = hasher(), const key_equal& eql = key_equal(),
 219                   const allocator_type& a = allocator_type());
 220     unordered_multiset(size_type n, const allocator_type& a); // C++14
 221     unordered_multiset(size_type n, const hasher& hf, const allocator_type& a); // C++14
 222     template <class InputIterator>
 223       unordered_multiset(InputIterator f, InputIterator l, size_type n, const allocator_type& a); // C++14
 224     template <class InputIterator>
 225       unordered_multiset(InputIterator f, InputIterator l, size_type n,
 226                          const hasher& hf, const allocator_type& a); // C++14
 227     unordered_multiset(initializer_list<value_type> il, size_type n, const allocator_type& a); // C++14
 228     unordered_multiset(initializer_list<value_type> il, size_type n,
 229                        const hasher& hf,  const allocator_type& a); // C++14
 230     ~unordered_multiset();
 231     unordered_multiset& operator=(const unordered_multiset&);
 232     unordered_multiset& operator=(unordered_multiset&&)
 233         noexcept(
 234             allocator_type::propagate_on_container_move_assignment::value &&
 235             is_nothrow_move_assignable<allocator_type>::value &&
 236             is_nothrow_move_assignable<hasher>::value &&
 237             is_nothrow_move_assignable<key_equal>::value);
 238     unordered_multiset& operator=(initializer_list<value_type>);
 239
 240     allocator_type get_allocator() const noexcept;
 241
 242     bool      empty() const noexcept;
 243     size_type size() const noexcept;
 244     size_type max_size() const noexcept;
 245
 246     iterator       begin() noexcept;
 247     iterator       end() noexcept;
 248     const_iterator begin()  const noexcept;
 249     const_iterator end()    const noexcept;
 250     const_iterator cbegin() const noexcept;
 251     const_iterator cend()   const noexcept;
 252
 253     template <class... Args>
 254         iterator emplace(Args&&... args);
 255     template <class... Args>
 256         iterator emplace_hint(const_iterator position, Args&&... args);
 257     iterator insert(const value_type& obj);
 258     iterator insert(value_type&& obj);
 259     iterator insert(const_iterator hint, const value_type& obj);
 260     iterator insert(const_iterator hint, value_type&& obj);
 261     template <class InputIterator>
 262         void insert(InputIterator first, InputIterator last);
 263     void insert(initializer_list<value_type>);
 264
 265     iterator erase(const_iterator position);
 266     size_type erase(const key_type& k);
 267     iterator erase(const_iterator first, const_iterator last);
 268     void clear() noexcept;
 269
 270     void swap(unordered_multiset&)
 271         noexcept(
 272             (!allocator_type::propagate_on_container_swap::value ||
 273              __is_nothrow_swappable<allocator_type>::value) &&
 274             __is_nothrow_swappable<hasher>::value &&
 275             __is_nothrow_swappable<key_equal>::value);
 276
 277     hasher hash_function() const;
 278     key_equal key_eq() const;
 279
 280     iterator       find(const key_type& k);
 281     const_iterator find(const key_type& k) const;
 282     size_type count(const key_type& k) const;
 283     pair<iterator, iterator>             equal_range(const key_type& k);
 284     pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
 285
 286     size_type bucket_count() const noexcept;
 287     size_type max_bucket_count() const noexcept;
 288
 289     size_type bucket_size(size_type n) const;
 290     size_type bucket(const key_type& k) const;
 291
 292     local_iterator       begin(size_type n);
 293     local_iterator       end(size_type n);
 294     const_local_iterator begin(size_type n) const;
 295     const_local_iterator end(size_type n) const;
 296     const_local_iterator cbegin(size_type n) const;
 297     const_local_iterator cend(size_type n) const;
 298
 299     float load_factor() const noexcept;
 300     float max_load_factor() const noexcept;
 301     void max_load_factor(float z);
 302     void rehash(size_type n);
 303     void reserve(size_type n);
 304 };
 305
 306 template <class Value, class Hash, class Pred, class Alloc>
 307     void swap(unordered_multiset<Value, Hash, Pred, Alloc>& x,
 308               unordered_multiset<Value, Hash, Pred, Alloc>& y)
 309               noexcept(noexcept(x.swap(y)));
 310
 311 template <class Value, class Hash, class Pred, class Alloc>
 312     bool
 313     operator==(const unordered_multiset<Value, Hash, Pred, Alloc>& x,
 314                const unordered_multiset<Value, Hash, Pred, Alloc>& y);
 315
 316 template <class Value, class Hash, class Pred, class Alloc>
 317     bool
 318     operator!=(const unordered_multiset<Value, Hash, Pred, Alloc>& x,
 319                const unordered_multiset<Value, Hash, Pred, Alloc>& y);
 320 }  // std
 321
 322 */
 323
 324 #include <__config>
 325 #include <__hash_table>
 326 #include <functional>
 327
 328 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 329 #pragma GCC system_header
 330 #endif
 331
 332 _LIBCPP_BEGIN_NAMESPACE_STD
 333
 334 template <class _Value, class _Hash = hash<_Value>, class _Pred = equal_to<_Value>,
 335           class _Alloc = allocator<_Value> >
 336 class _LIBCPP_TYPE_VIS_ONLY unordered_set
 337 {
 338 public:
 339     // types
 340     typedef _Value                                                     key_type;
 341     typedef key_type                                                   value_type;
 342     typedef _Hash                                                      hasher;
 343     typedef _Pred                                                      key_equal;
 344     typedef _Alloc                                                     allocator_type;
 345     typedef value_type&                                                reference;
 346     typedef const value_type&                                          const_reference;
 347     static_assert((is_same<value_type, typename allocator_type::value_type>::value),
 348                   "Invalid allocator::value_type");
 349
 350 private:
 351     typedef __hash_table<value_type, hasher, key_equal, allocator_type> __table;
 352
 353     __table __table_;
 354
 355 public:
 356     typedef typename __table::pointer         pointer;
 357     typedef typename __table::const_pointer   const_pointer;
 358     typedef typename __table::size_type       size_type;
 359     typedef typename __table::difference_type difference_type;
 360
 361     typedef typename __table::const_iterator       iterator;
 362     typedef typename __table::const_iterator       const_iterator;
 363     typedef typename __table::const_local_iterator local_iterator;
 364     typedef typename __table::const_local_iterator const_local_iterator;
 365
 366     _LIBCPP_INLINE_VISIBILITY
 367     unordered_set()
 368         _NOEXCEPT_(is_nothrow_default_constructible<__table>::value)
 369         {
 370 #if _LIBCPP_DEBUG_LEVEL >= 2
 371             __get_db()->__insert_c(this);
 372 #endif
 373         }
 374     explicit unordered_set(size_type __n, const hasher& __hf = hasher(),
 375                            const key_equal& __eql = key_equal());
 376 #if _LIBCPP_STD_VER > 11
 377     inline _LIBCPP_INLINE_VISIBILITY
 378     unordered_set(size_type __n, const allocator_type& __a)
 379         : unordered_set(__n, hasher(), key_equal(), __a) {}
 380     inline _LIBCPP_INLINE_VISIBILITY
 381     unordered_set(size_type __n, const hasher& __hf, const allocator_type& __a)
 382         : unordered_set(__n, __hf, key_equal(), __a) {}
 383 #endif
 384     unordered_set(size_type __n, const hasher& __hf, const key_equal& __eql,
 385                   const allocator_type& __a);
 386     template <class _InputIterator>
 387         unordered_set(_InputIterator __first, _InputIterator __last);
 388     template <class _InputIterator>
 389         unordered_set(_InputIterator __first, _InputIterator __last,
 390                       size_type __n, const hasher& __hf = hasher(),
 391                       const key_equal& __eql = key_equal());
 392     template <class _InputIterator>
 393         unordered_set(_InputIterator __first, _InputIterator __last,
 394                       size_type __n, const hasher& __hf, const key_equal& __eql,
 395                       const allocator_type& __a);
 396 #if _LIBCPP_STD_VER > 11
 397     template <class _InputIterator>
 398     inline _LIBCPP_INLINE_VISIBILITY
 399         unordered_set(_InputIterator __first, _InputIterator __last,
 400                     size_type __n, const allocator_type& __a)
 401             : unordered_set(__first, __last, __n, hasher(), key_equal(), __a) {}
 402     template <class _InputIterator>
 403         unordered_set(_InputIterator __first, _InputIterator __last,
 404                       size_type __n, const hasher& __hf, const allocator_type& __a)
 405             : unordered_set(__first, __last, __n, __hf, key_equal(), __a) {}
 406 #endif
 407     explicit unordered_set(const allocator_type& __a);
 408     unordered_set(const unordered_set& __u);
 409     unordered_set(const unordered_set& __u, const allocator_type& __a);
 410 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 411     unordered_set(unordered_set&& __u)
 412         _NOEXCEPT_(is_nothrow_move_constructible<__table>::value);
 413     unordered_set(unordered_set&& __u, const allocator_type& __a);
 414 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
 415 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
 416     unordered_set(initializer_list<value_type> __il);
 417     unordered_set(initializer_list<value_type> __il, size_type __n,
 418                   const hasher& __hf = hasher(),
 419                   const key_equal& __eql = key_equal());
 420     unordered_set(initializer_list<value_type> __il, size_type __n,
 421                   const hasher& __hf, const key_equal& __eql,
 422                   const allocator_type& __a);
 423 #if _LIBCPP_STD_VER > 11
 424     inline _LIBCPP_INLINE_VISIBILITY
 425     unordered_set(initializer_list<value_type> __il, size_type __n,
 426                                                       const allocator_type& __a)
 427         : unordered_set(__il, __n, hasher(), key_equal(), __a) {}
 428     inline _LIBCPP_INLINE_VISIBILITY
 429     unordered_set(initializer_list<value_type> __il, size_type __n,
 430                                   const hasher& __hf, const allocator_type& __a)
 431         : unordered_set(__il, __n, __hf, key_equal(), __a) {}
 432 #endif
 433 #endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
 434     // ~unordered_set() = default;
 435     _LIBCPP_INLINE_VISIBILITY
 436     unordered_set& operator=(const unordered_set& __u)
 437     {
 438         __table_ = __u.__table_;
 439         return *this;
 440     }
 441 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 442     unordered_set& operator=(unordered_set&& __u)
 443         _NOEXCEPT_(is_nothrow_move_assignable<__table>::value);
 444 #endif
 445 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
 446     unordered_set& operator=(initializer_list<value_type> __il);
 447 #endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
 448
 449     _LIBCPP_INLINE_VISIBILITY
 450     allocator_type get_allocator() const _NOEXCEPT
 451         {return allocator_type(__table_.__node_alloc());}
 452
 453     _LIBCPP_INLINE_VISIBILITY
 454     bool      empty() const _NOEXCEPT {return __table_.size() == 0;}
 455     _LIBCPP_INLINE_VISIBILITY
 456     size_type size() const _NOEXCEPT  {return __table_.size();}
 457     _LIBCPP_INLINE_VISIBILITY
 458     size_type max_size() const _NOEXCEPT {return __table_.max_size();}
 459
 460     _LIBCPP_INLINE_VISIBILITY
 461     iterator       begin() _NOEXCEPT        {return __table_.begin();}
 462     _LIBCPP_INLINE_VISIBILITY
 463     iterator       end() _NOEXCEPT          {return __table_.end();}
 464     _LIBCPP_INLINE_VISIBILITY
 465     const_iterator begin()  const _NOEXCEPT {return __table_.begin();}
 466     _LIBCPP_INLINE_VISIBILITY
 467     const_iterator end()    const _NOEXCEPT {return __table_.end();}
 468     _LIBCPP_INLINE_VISIBILITY
 469     const_iterator cbegin() const _NOEXCEPT {return __table_.begin();}
 470     _LIBCPP_INLINE_VISIBILITY
 471     const_iterator cend()   const _NOEXCEPT {return __table_.end();}
 472
 473 #if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
 474     template <class... _Args>
 475         _LIBCPP_INLINE_VISIBILITY
 476         pair<iterator, bool> emplace(_Args&&... __args)
 477             {return __table_.__emplace_unique(_VSTD::forward<_Args>(__args)...);}
 478     template <class... _Args>
 479         _LIBCPP_INLINE_VISIBILITY
 480 #if _LIBCPP_DEBUG_LEVEL >= 2
 481         iterator emplace_hint(const_iterator __p, _Args&&... __args)
 482         {
 483             _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
 484                 "unordered_set::emplace_hint(const_iterator, args...) called with an iterator not"
 485                 " referring to this unordered_set");
 486             return __table_.__emplace_unique(_VSTD::forward<_Args>(__args)...).first;
 487         }
 488 #else
 489         iterator emplace_hint(const_iterator, _Args&&... __args)
 490             {return __table_.__emplace_unique(_VSTD::forward<_Args>(__args)...).first;}
 491 #endif
 492 #endif  // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
 493     _LIBCPP_INLINE_VISIBILITY
 494     pair<iterator, bool> insert(const value_type& __x)
 495         {return __table_.__insert_unique(__x);}
 496 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 497     _LIBCPP_INLINE_VISIBILITY
 498     pair<iterator, bool> insert(value_type&& __x)
 499         {return __table_.__insert_unique(_VSTD::move(__x));}
 500 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
 501     _LIBCPP_INLINE_VISIBILITY
 502 #if _LIBCPP_DEBUG_LEVEL >= 2
 503     iterator insert(const_iterator __p, const value_type& __x)
 504         {
 505             _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
 506                 "unordered_set::insert(const_iterator, const value_type&) called with an iterator not"
 507                 " referring to this unordered_set");
 508             return insert(__x).first;
 509         }
 510 #else
 511     iterator insert(const_iterator, const value_type& __x)
 512         {return insert(__x).first;}
 513 #endif
 514 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 515     _LIBCPP_INLINE_VISIBILITY
 516 #if _LIBCPP_DEBUG_LEVEL >= 2
 517     iterator insert(const_iterator __p, value_type&& __x)
 518         {
 519             _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
 520                 "unordered_set::insert(const_iterator, value_type&&) called with an iterator not"
 521                 " referring to this unordered_set");
 522             return insert(_VSTD::move(__x)).first;
 523         }
 524 #else
 525     iterator insert(const_iterator, value_type&& __x)
 526         {return insert(_VSTD::move(__x)).first;}
 527 #endif
 528 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
 529     template <class _InputIterator>
 530         void insert(_InputIterator __first, _InputIterator __last);
 531 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
 532     _LIBCPP_INLINE_VISIBILITY
 533     void insert(initializer_list<value_type> __il)
 534         {insert(__il.begin(), __il.end());}
 535 #endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
 536
 537     _LIBCPP_INLINE_VISIBILITY
 538     iterator erase(const_iterator __p) {return __table_.erase(__p);}
 539     _LIBCPP_INLINE_VISIBILITY
 540     size_type erase(const key_type& __k) {return __table_.__erase_unique(__k);}
 541     _LIBCPP_INLINE_VISIBILITY
 542     iterator erase(const_iterator __first, const_iterator __last)
 543         {return __table_.erase(__first, __last);}
 544     _LIBCPP_INLINE_VISIBILITY
 545     void clear() _NOEXCEPT {__table_.clear();}
 546
 547     _LIBCPP_INLINE_VISIBILITY
 548     void swap(unordered_set& __u)
 549         _NOEXCEPT_(__is_nothrow_swappable<__table>::value)
 550         {__table_.swap(__u.__table_);}
 551
 552     _LIBCPP_INLINE_VISIBILITY
 553     hasher hash_function() const {return __table_.hash_function();}
 554     _LIBCPP_INLINE_VISIBILITY
 555     key_equal key_eq() const {return __table_.key_eq();}
 556
 557     _LIBCPP_INLINE_VISIBILITY
 558     iterator       find(const key_type& __k)       {return __table_.find(__k);}
 559     _LIBCPP_INLINE_VISIBILITY
 560     const_iterator find(const key_type& __k) const {return __table_.find(__k);}
 561     _LIBCPP_INLINE_VISIBILITY
 562     size_type count(const key_type& __k) const {return __table_.__count_unique(__k);}
 563     _LIBCPP_INLINE_VISIBILITY
 564     pair<iterator, iterator>             equal_range(const key_type& __k)
 565         {return __table_.__equal_range_unique(__k);}
 566     _LIBCPP_INLINE_VISIBILITY
 567     pair<const_iterator, const_iterator> equal_range(const key_type& __k) const
 568         {return __table_.__equal_range_unique(__k);}
 569
 570     _LIBCPP_INLINE_VISIBILITY
 571     size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();}
 572     _LIBCPP_INLINE_VISIBILITY
 573     size_type max_bucket_count() const _NOEXCEPT {return __table_.max_bucket_count();}
 574
 575     _LIBCPP_INLINE_VISIBILITY
 576     size_type bucket_size(size_type __n) const {return __table_.bucket_size(__n);}
 577     _LIBCPP_INLINE_VISIBILITY
 578     size_type bucket(const key_type& __k) const {return __table_.bucket(__k);}
 579
 580     _LIBCPP_INLINE_VISIBILITY
 581     local_iterator       begin(size_type __n)        {return __table_.begin(__n);}
 582     _LIBCPP_INLINE_VISIBILITY
 583     local_iterator       end(size_type __n)          {return __table_.end(__n);}
 584     _LIBCPP_INLINE_VISIBILITY
 585     const_local_iterator begin(size_type __n) const  {return __table_.cbegin(__n);}
 586     _LIBCPP_INLINE_VISIBILITY
 587     const_local_iterator end(size_type __n) const    {return __table_.cend(__n);}
 588     _LIBCPP_INLINE_VISIBILITY
 589     const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);}
 590     _LIBCPP_INLINE_VISIBILITY
 591     const_local_iterator cend(size_type __n) const   {return __table_.cend(__n);}
 592
 593     _LIBCPP_INLINE_VISIBILITY
 594     float load_factor() const _NOEXCEPT {return __table_.load_factor();}
 595     _LIBCPP_INLINE_VISIBILITY
 596     float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();}
 597     _LIBCPP_INLINE_VISIBILITY
 598     void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);}
 599     _LIBCPP_INLINE_VISIBILITY
 600     void rehash(size_type __n) {__table_.rehash(__n);}
 601     _LIBCPP_INLINE_VISIBILITY
 602     void reserve(size_type __n) {__table_.reserve(__n);}
 603
 604 #if _LIBCPP_DEBUG_LEVEL >= 2
 605
 606     bool __dereferenceable(const const_iterator* __i) const
 607         {return __table_.__dereferenceable(__i);}
 608     bool __decrementable(const const_iterator* __i) const
 609         {return __table_.__decrementable(__i);}
 610     bool __addable(const const_iterator* __i, ptrdiff_t __n) const
 611         {return __table_.__addable(__i, __n);}
 612     bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const
 613         {return __table_.__addable(__i, __n);}
 614
 615 #endif  // _LIBCPP_DEBUG_LEVEL >= 2
 616
 617 };
 618
 619 template <class _Value, class _Hash, class _Pred, class _Alloc>
 620 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(size_type __n,
 621         const hasher& __hf, const key_equal& __eql)
 622     : __table_(__hf, __eql)
 623 {
 624 #if _LIBCPP_DEBUG_LEVEL >= 2
 625     __get_db()->__insert_c(this);
 626 #endif
 627     __table_.rehash(__n);
 628 }
 629
 630 template <class _Value, class _Hash, class _Pred, class _Alloc>
 631 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(size_type __n,
 632         const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
 633     : __table_(__hf, __eql, __a)
 634 {
 635 #if _LIBCPP_DEBUG_LEVEL >= 2
 636     __get_db()->__insert_c(this);
 637 #endif
 638     __table_.rehash(__n);
 639 }
 640
 641 template <class _Value, class _Hash, class _Pred, class _Alloc>
 642 template <class _InputIterator>
 643 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
 644         _InputIterator __first, _InputIterator __last)
 645 {
 646 #if _LIBCPP_DEBUG_LEVEL >= 2
 647     __get_db()->__insert_c(this);
 648 #endif
 649     insert(__first, __last);
 650 }
 651
 652 template <class _Value, class _Hash, class _Pred, class _Alloc>
 653 template <class _InputIterator>
 654 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
 655         _InputIterator __first, _InputIterator __last, size_type __n,
 656         const hasher& __hf, const key_equal& __eql)
 657     : __table_(__hf, __eql)
 658 {
 659 #if _LIBCPP_DEBUG_LEVEL >= 2
 660     __get_db()->__insert_c(this);
 661 #endif
 662     __table_.rehash(__n);
 663     insert(__first, __last);
 664 }
 665
 666 template <class _Value, class _Hash, class _Pred, class _Alloc>
 667 template <class _InputIterator>
 668 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
 669         _InputIterator __first, _InputIterator __last, size_type __n,
 670         const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
 671     : __table_(__hf, __eql, __a)
 672 {
 673 #if _LIBCPP_DEBUG_LEVEL >= 2
 674     __get_db()->__insert_c(this);
 675 #endif
 676     __table_.rehash(__n);
 677     insert(__first, __last);
 678 }
 679
 680 template <class _Value, class _Hash, class _Pred, class _Alloc>
 681 inline _LIBCPP_INLINE_VISIBILITY
 682 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
 683         const allocator_type& __a)
 684     : __table_(__a)
 685 {
 686 #if _LIBCPP_DEBUG_LEVEL >= 2
 687     __get_db()->__insert_c(this);
 688 #endif
 689 }
 690
 691 template <class _Value, class _Hash, class _Pred, class _Alloc>
 692 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
 693         const unordered_set& __u)
 694     : __table_(__u.__table_)
 695 {
 696 #if _LIBCPP_DEBUG_LEVEL >= 2
 697     __get_db()->__insert_c(this);
 698 #endif
 699     __table_.rehash(__u.bucket_count());
 700     insert(__u.begin(), __u.end());
 701 }
 702
 703 template <class _Value, class _Hash, class _Pred, class _Alloc>
 704 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
 705         const unordered_set& __u, const allocator_type& __a)
 706     : __table_(__u.__table_, __a)
 707 {
 708 #if _LIBCPP_DEBUG_LEVEL >= 2
 709     __get_db()->__insert_c(this);
 710 #endif
 711     __table_.rehash(__u.bucket_count());
 712     insert(__u.begin(), __u.end());
 713 }
 714
 715 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 716
 717 template <class _Value, class _Hash, class _Pred, class _Alloc>
 718 inline _LIBCPP_INLINE_VISIBILITY
 719 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
 720         unordered_set&& __u)
 721     _NOEXCEPT_(is_nothrow_move_constructible<__table>::value)
 722     : __table_(_VSTD::move(__u.__table_))
 723 {
 724 #if _LIBCPP_DEBUG_LEVEL >= 2
 725     __get_db()->__insert_c(this);
 726     __get_db()->swap(this, &__u);
 727 #endif
 728 }
 729
 730 template <class _Value, class _Hash, class _Pred, class _Alloc>
 731 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
 732         unordered_set&& __u, const allocator_type& __a)
 733     : __table_(_VSTD::move(__u.__table_), __a)
 734 {
 735 #if _LIBCPP_DEBUG_LEVEL >= 2
 736     __get_db()->__insert_c(this);
 737 #endif
 738     if (__a != __u.get_allocator())
 739     {
 740         iterator __i = __u.begin();
 741         while (__u.size() != 0)
 742             __table_.__insert_unique(_VSTD::move(__u.__table_.remove(__i++)->__value_));
 743     }
 744 #if _LIBCPP_DEBUG_LEVEL >= 2
 745     else
 746         __get_db()->swap(this, &__u);
 747 #endif
 748 }
 749
 750 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
 751
 752 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
 753
 754 template <class _Value, class _Hash, class _Pred, class _Alloc>
 755 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
 756         initializer_list<value_type> __il)
 757 {
 758 #if _LIBCPP_DEBUG_LEVEL >= 2
 759     __get_db()->__insert_c(this);
 760 #endif
 761     insert(__il.begin(), __il.end());
 762 }
 763
 764 template <class _Value, class _Hash, class _Pred, class _Alloc>
 765 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
 766         initializer_list<value_type> __il, size_type __n, const hasher& __hf,
 767         const key_equal& __eql)
 768     : __table_(__hf, __eql)
 769 {
 770 #if _LIBCPP_DEBUG_LEVEL >= 2
 771     __get_db()->__insert_c(this);
 772 #endif
 773     __table_.rehash(__n);
 774     insert(__il.begin(), __il.end());
 775 }
 776
 777 template <class _Value, class _Hash, class _Pred, class _Alloc>
 778 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
 779         initializer_list<value_type> __il, size_type __n, const hasher& __hf,
 780         const key_equal& __eql, const allocator_type& __a)
 781     : __table_(__hf, __eql, __a)
 782 {
 783 #if _LIBCPP_DEBUG_LEVEL >= 2
 784     __get_db()->__insert_c(this);
 785 #endif
 786     __table_.rehash(__n);
 787     insert(__il.begin(), __il.end());
 788 }
 789
 790 #endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
 791
 792 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 793
 794 template <class _Value, class _Hash, class _Pred, class _Alloc>
 795 inline _LIBCPP_INLINE_VISIBILITY
 796 unordered_set<_Value, _Hash, _Pred, _Alloc>&
 797 unordered_set<_Value, _Hash, _Pred, _Alloc>::operator=(unordered_set&& __u)
 798     _NOEXCEPT_(is_nothrow_move_assignable<__table>::value)
 799 {
 800     __table_ = _VSTD::move(__u.__table_);
 801     return *this;
 802 }
 803
 804 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
 805
 806 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
 807
 808 template <class _Value, class _Hash, class _Pred, class _Alloc>
 809 inline _LIBCPP_INLINE_VISIBILITY
 810 unordered_set<_Value, _Hash, _Pred, _Alloc>&
 811 unordered_set<_Value, _Hash, _Pred, _Alloc>::operator=(
 812         initializer_list<value_type> __il)
 813 {
 814     __table_.__assign_unique(__il.begin(), __il.end());
 815     return *this;
 816 }
 817
 818 #endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
 819
 820 template <class _Value, class _Hash, class _Pred, class _Alloc>
 821 template <class _InputIterator>
 822 inline _LIBCPP_INLINE_VISIBILITY
 823 void
 824 unordered_set<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator __first,
 825                                                     _InputIterator __last)
 826 {
 827     for (; __first != __last; ++__first)
 828         __table_.__insert_unique(*__first);
 829 }
 830
 831 template <class _Value, class _Hash, class _Pred, class _Alloc>
 832 inline _LIBCPP_INLINE_VISIBILITY
 833 void
 834 swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
 835      unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
 836     _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
 837 {
 838     __x.swap(__y);
 839 }
 840
 841 template <class _Value, class _Hash, class _Pred, class _Alloc>
 842 bool
 843 operator==(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
 844            const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
 845 {
 846     if (__x.size() != __y.size())
 847         return false;
 848     typedef typename unordered_set<_Value, _Hash, _Pred, _Alloc>::const_iterator
 849                                                                  const_iterator;
 850     for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end();
 851             __i != __ex; ++__i)
 852     {
 853         const_iterator __j = __y.find(*__i);
 854         if (__j == __ey || !(*__i == *__j))
 855             return false;
 856     }
 857     return true;
 858 }
 859
 860 template <class _Value, class _Hash, class _Pred, class _Alloc>
 861 inline _LIBCPP_INLINE_VISIBILITY
 862 bool
 863 operator!=(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
 864            const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
 865 {
 866     return !(__x == __y);
 867 }
 868
 869 template <class _Value, class _Hash = hash<_Value>, class _Pred = equal_to<_Value>,
 870           class _Alloc = allocator<_Value> >
 871 class _LIBCPP_TYPE_VIS_ONLY unordered_multiset
 872 {
 873 public:
 874     // types
 875     typedef _Value                                                     key_type;
 876     typedef key_type                                                   value_type;
 877     typedef _Hash                                                      hasher;
 878     typedef _Pred                                                      key_equal;
 879     typedef _Alloc                                                     allocator_type;
 880     typedef value_type&                                                reference;
 881     typedef const value_type&                                          const_reference;
 882     static_assert((is_same<value_type, typename allocator_type::value_type>::value),
 883                   "Invalid allocator::value_type");
 884
 885 private:
 886     typedef __hash_table<value_type, hasher, key_equal, allocator_type> __table;
 887
 888     __table __table_;
 889
 890 public:
 891     typedef typename __table::pointer         pointer;
 892     typedef typename __table::const_pointer   const_pointer;
 893     typedef typename __table::size_type       size_type;
 894     typedef typename __table::difference_type difference_type;
 895
 896     typedef typename __table::const_iterator       iterator;
 897     typedef typename __table::const_iterator       const_iterator;
 898     typedef typename __table::const_local_iterator local_iterator;
 899     typedef typename __table::const_local_iterator const_local_iterator;
 900
 901     _LIBCPP_INLINE_VISIBILITY
 902     unordered_multiset()
 903         _NOEXCEPT_(is_nothrow_default_constructible<__table>::value)
 904         {
 905 #if _LIBCPP_DEBUG_LEVEL >= 2
 906             __get_db()->__insert_c(this);
 907 #endif
 908         }
 909     explicit unordered_multiset(size_type __n, const hasher& __hf = hasher(),
 910                                 const key_equal& __eql = key_equal());
 911     unordered_multiset(size_type __n, const hasher& __hf,
 912                        const key_equal& __eql, const allocator_type& __a);
 913 #if _LIBCPP_STD_VER > 11
 914     inline _LIBCPP_INLINE_VISIBILITY
 915     unordered_multiset(size_type __n, const allocator_type& __a)
 916         : unordered_multiset(__n, hasher(), key_equal(), __a) {}
 917     inline _LIBCPP_INLINE_VISIBILITY
 918     unordered_multiset(size_type __n, const hasher& __hf, const allocator_type& __a)
 919         : unordered_multiset(__n, __hf, key_equal(), __a) {}
 920 #endif
 921     template <class _InputIterator>
 922         unordered_multiset(_InputIterator __first, _InputIterator __last);
 923     template <class _InputIterator>
 924         unordered_multiset(_InputIterator __first, _InputIterator __last,
 925                       size_type __n, const hasher& __hf = hasher(),
 926                       const key_equal& __eql = key_equal());
 927     template <class _InputIterator>
 928         unordered_multiset(_InputIterator __first, _InputIterator __last,
 929                       size_type __n , const hasher& __hf,
 930                       const key_equal& __eql, const allocator_type& __a);
 931 #if _LIBCPP_STD_VER > 11
 932     template <class _InputIterator>
 933     inline _LIBCPP_INLINE_VISIBILITY
 934     unordered_multiset(_InputIterator __first, _InputIterator __last,
 935                        size_type __n, const allocator_type& __a)
 936         : unordered_multiset(__first, __last, __n, hasher(), key_equal(), __a) {}
 937     template <class _InputIterator>
 938     inline _LIBCPP_INLINE_VISIBILITY
 939     unordered_multiset(_InputIterator __first, _InputIterator __last,
 940                        size_type __n, const hasher& __hf, const allocator_type& __a)
 941         : unordered_multiset(__first, __last, __n, __hf, key_equal(), __a) {}
 942 #endif
 943     explicit unordered_multiset(const allocator_type& __a);
 944     unordered_multiset(const unordered_multiset& __u);
 945     unordered_multiset(const unordered_multiset& __u, const allocator_type& __a);
 946 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 947     unordered_multiset(unordered_multiset&& __u)
 948         _NOEXCEPT_(is_nothrow_move_constructible<__table>::value);
 949     unordered_multiset(unordered_multiset&& __u, const allocator_type& __a);
 950 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
 951 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
 952     unordered_multiset(initializer_list<value_type> __il);
 953     unordered_multiset(initializer_list<value_type> __il, size_type __n,
 954                        const hasher& __hf = hasher(),
 955                        const key_equal& __eql = key_equal());
 956     unordered_multiset(initializer_list<value_type> __il, size_type __n,
 957                        const hasher& __hf, const key_equal& __eql,
 958                        const allocator_type& __a);
 959 #if _LIBCPP_STD_VER > 11
 960     inline _LIBCPP_INLINE_VISIBILITY
 961     unordered_multiset(initializer_list<value_type> __il, size_type __n, const allocator_type& __a)
 962       : unordered_multiset(__il, __n, hasher(), key_equal(), __a) {}
 963     inline _LIBCPP_INLINE_VISIBILITY
 964     unordered_multiset(initializer_list<value_type> __il, size_type __n, const hasher& __hf, const allocator_type& __a)
 965       : unordered_multiset(__il, __n, __hf, key_equal(), __a) {}
 966 #endif
 967 #endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
 968     // ~unordered_multiset() = default;
 969     _LIBCPP_INLINE_VISIBILITY
 970     unordered_multiset& operator=(const unordered_multiset& __u)
 971     {
 972         __table_ = __u.__table_;
 973         return *this;
 974     }
 975 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 976     unordered_multiset& operator=(unordered_multiset&& __u)
 977         _NOEXCEPT_(is_nothrow_move_assignable<__table>::value);
 978 #endif
 979 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
 980     unordered_multiset& operator=(initializer_list<value_type> __il);
 981 #endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
 982
 983     _LIBCPP_INLINE_VISIBILITY
 984     allocator_type get_allocator() const _NOEXCEPT
 985         {return allocator_type(__table_.__node_alloc());}
 986
 987     _LIBCPP_INLINE_VISIBILITY
 988     bool      empty() const _NOEXCEPT {return __table_.size() == 0;}
 989     _LIBCPP_INLINE_VISIBILITY
 990     size_type size() const _NOEXCEPT  {return __table_.size();}
 991     _LIBCPP_INLINE_VISIBILITY
 992     size_type max_size() const _NOEXCEPT {return __table_.max_size();}
 993
 994     _LIBCPP_INLINE_VISIBILITY
 995     iterator       begin() _NOEXCEPT        {return __table_.begin();}
 996     _LIBCPP_INLINE_VISIBILITY
 997     iterator       end() _NOEXCEPT          {return __table_.end();}
 998     _LIBCPP_INLINE_VISIBILITY
 999     const_iterator begin()  const _NOEXCEPT {return __table_.begin();}
1000     _LIBCPP_INLINE_VISIBILITY
1001     const_iterator end()    const _NOEXCEPT {return __table_.end();}
1002     _LIBCPP_INLINE_VISIBILITY
1003     const_iterator cbegin() const _NOEXCEPT {return __table_.begin();}
1004     _LIBCPP_INLINE_VISIBILITY
1005     const_iterator cend()   const _NOEXCEPT {return __table_.end();}
1006
1007 #if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
1008     template <class... _Args>
1009         _LIBCPP_INLINE_VISIBILITY
1010         iterator emplace(_Args&&... __args)
1011             {return __table_.__emplace_multi(_VSTD::forward<_Args>(__args)...);}
1012     template <class... _Args>
1013         _LIBCPP_INLINE_VISIBILITY
1014         iterator emplace_hint(const_iterator __p, _Args&&... __args)
1015             {return __table_.__emplace_hint_multi(__p, _VSTD::forward<_Args>(__args)...);}
1016 #endif  // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
1017     _LIBCPP_INLINE_VISIBILITY
1018     iterator insert(const value_type& __x) {return __table_.__insert_multi(__x);}
1019 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1020     _LIBCPP_INLINE_VISIBILITY
1021     iterator insert(value_type&& __x) {return __table_.__insert_multi(_VSTD::move(__x));}
1022 #endif
1023     _LIBCPP_INLINE_VISIBILITY
1024     iterator insert(const_iterator __p, const value_type& __x)
1025         {return __table_.__insert_multi(__p, __x);}
1026 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1027     _LIBCPP_INLINE_VISIBILITY
1028     iterator insert(const_iterator __p, value_type&& __x)
1029         {return __table_.__insert_multi(__p, _VSTD::move(__x));}
1030 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1031     template <class _InputIterator>
1032         void insert(_InputIterator __first, _InputIterator __last);
1033 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1034     _LIBCPP_INLINE_VISIBILITY
1035     void insert(initializer_list<value_type> __il)
1036         {insert(__il.begin(), __il.end());}
1037 #endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1038
1039     _LIBCPP_INLINE_VISIBILITY
1040     iterator erase(const_iterator __p) {return __table_.erase(__p);}
1041     _LIBCPP_INLINE_VISIBILITY
1042     size_type erase(const key_type& __k) {return __table_.__erase_multi(__k);}
1043     _LIBCPP_INLINE_VISIBILITY
1044     iterator erase(const_iterator __first, const_iterator __last)
1045         {return __table_.erase(__first, __last);}
1046     _LIBCPP_INLINE_VISIBILITY
1047     void clear() _NOEXCEPT {__table_.clear();}
1048
1049     _LIBCPP_INLINE_VISIBILITY
1050     void swap(unordered_multiset& __u)
1051         _NOEXCEPT_(__is_nothrow_swappable<__table>::value)
1052         {__table_.swap(__u.__table_);}
1053
1054     _LIBCPP_INLINE_VISIBILITY
1055     hasher hash_function() const {return __table_.hash_function();}
1056     _LIBCPP_INLINE_VISIBILITY
1057     key_equal key_eq() const {return __table_.key_eq();}
1058
1059     _LIBCPP_INLINE_VISIBILITY
1060     iterator       find(const key_type& __k)       {return __table_.find(__k);}
1061     _LIBCPP_INLINE_VISIBILITY
1062     const_iterator find(const key_type& __k) const {return __table_.find(__k);}
1063     _LIBCPP_INLINE_VISIBILITY
1064     size_type count(const key_type& __k) const {return __table_.__count_multi(__k);}
1065     _LIBCPP_INLINE_VISIBILITY
1066     pair<iterator, iterator>             equal_range(const key_type& __k)
1067         {return __table_.__equal_range_multi(__k);}
1068     _LIBCPP_INLINE_VISIBILITY
1069     pair<const_iterator, const_iterator> equal_range(const key_type& __k) const
1070         {return __table_.__equal_range_multi(__k);}
1071
1072     _LIBCPP_INLINE_VISIBILITY
1073     size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();}
1074     _LIBCPP_INLINE_VISIBILITY
1075     size_type max_bucket_count() const _NOEXCEPT {return __table_.max_bucket_count();}
1076
1077     _LIBCPP_INLINE_VISIBILITY
1078     size_type bucket_size(size_type __n) const {return __table_.bucket_size(__n);}
1079     _LIBCPP_INLINE_VISIBILITY
1080     size_type bucket(const key_type& __k) const {return __table_.bucket(__k);}
1081
1082     _LIBCPP_INLINE_VISIBILITY
1083     local_iterator       begin(size_type __n)        {return __table_.begin(__n);}
1084     _LIBCPP_INLINE_VISIBILITY
1085     local_iterator       end(size_type __n)          {return __table_.end(__n);}
1086     _LIBCPP_INLINE_VISIBILITY
1087     const_local_iterator begin(size_type __n) const  {return __table_.cbegin(__n);}
1088     _LIBCPP_INLINE_VISIBILITY
1089     const_local_iterator end(size_type __n) const    {return __table_.cend(__n);}
1090     _LIBCPP_INLINE_VISIBILITY
1091     const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);}
1092     _LIBCPP_INLINE_VISIBILITY
1093     const_local_iterator cend(size_type __n) const   {return __table_.cend(__n);}
1094
1095     _LIBCPP_INLINE_VISIBILITY
1096     float load_factor() const _NOEXCEPT {return __table_.load_factor();}
1097     _LIBCPP_INLINE_VISIBILITY
1098     float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();}
1099     _LIBCPP_INLINE_VISIBILITY
1100     void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);}
1101     _LIBCPP_INLINE_VISIBILITY
1102     void rehash(size_type __n) {__table_.rehash(__n);}
1103     _LIBCPP_INLINE_VISIBILITY
1104     void reserve(size_type __n) {__table_.reserve(__n);}
1105
1106 #if _LIBCPP_DEBUG_LEVEL >= 2
1107
1108     bool __dereferenceable(const const_iterator* __i) const
1109         {return __table_.__dereferenceable(__i);}
1110     bool __decrementable(const const_iterator* __i) const
1111         {return __table_.__decrementable(__i);}
1112     bool __addable(const const_iterator* __i, ptrdiff_t __n) const
1113         {return __table_.__addable(__i, __n);}
1114     bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const
1115         {return __table_.__addable(__i, __n);}
1116
1117 #endif  // _LIBCPP_DEBUG_LEVEL >= 2
1118
1119 };
1120
1121 template <class _Value, class _Hash, class _Pred, class _Alloc>
1122 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1123         size_type __n, const hasher& __hf, const key_equal& __eql)
1124     : __table_(__hf, __eql)
1125 {
1126 #if _LIBCPP_DEBUG_LEVEL >= 2
1127     __get_db()->__insert_c(this);
1128 #endif
1129     __table_.rehash(__n);
1130 }
1131
1132 template <class _Value, class _Hash, class _Pred, class _Alloc>
1133 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1134         size_type __n, const hasher& __hf, const key_equal& __eql,
1135         const allocator_type& __a)
1136     : __table_(__hf, __eql, __a)
1137 {
1138 #if _LIBCPP_DEBUG_LEVEL >= 2
1139     __get_db()->__insert_c(this);
1140 #endif
1141     __table_.rehash(__n);
1142 }
1143
1144 template <class _Value, class _Hash, class _Pred, class _Alloc>
1145 template <class _InputIterator>
1146 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1147         _InputIterator __first, _InputIterator __last)
1148 {
1149 #if _LIBCPP_DEBUG_LEVEL >= 2
1150     __get_db()->__insert_c(this);
1151 #endif
1152     insert(__first, __last);
1153 }
1154
1155 template <class _Value, class _Hash, class _Pred, class _Alloc>
1156 template <class _InputIterator>
1157 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1158         _InputIterator __first, _InputIterator __last, size_type __n,
1159         const hasher& __hf, const key_equal& __eql)
1160     : __table_(__hf, __eql)
1161 {
1162 #if _LIBCPP_DEBUG_LEVEL >= 2
1163     __get_db()->__insert_c(this);
1164 #endif
1165     __table_.rehash(__n);
1166     insert(__first, __last);
1167 }
1168
1169 template <class _Value, class _Hash, class _Pred, class _Alloc>
1170 template <class _InputIterator>
1171 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1172         _InputIterator __first, _InputIterator __last, size_type __n,
1173         const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
1174     : __table_(__hf, __eql, __a)
1175 {
1176 #if _LIBCPP_DEBUG_LEVEL >= 2
1177     __get_db()->__insert_c(this);
1178 #endif
1179     __table_.rehash(__n);
1180     insert(__first, __last);
1181 }
1182
1183 template <class _Value, class _Hash, class _Pred, class _Alloc>
1184 inline _LIBCPP_INLINE_VISIBILITY
1185 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1186         const allocator_type& __a)
1187     : __table_(__a)
1188 {
1189 #if _LIBCPP_DEBUG_LEVEL >= 2
1190     __get_db()->__insert_c(this);
1191 #endif
1192 }
1193
1194 template <class _Value, class _Hash, class _Pred, class _Alloc>
1195 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1196         const unordered_multiset& __u)
1197     : __table_(__u.__table_)
1198 {
1199 #if _LIBCPP_DEBUG_LEVEL >= 2
1200     __get_db()->__insert_c(this);
1201 #endif
1202     __table_.rehash(__u.bucket_count());
1203     insert(__u.begin(), __u.end());
1204 }
1205
1206 template <class _Value, class _Hash, class _Pred, class _Alloc>
1207 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1208         const unordered_multiset& __u, const allocator_type& __a)
1209     : __table_(__u.__table_, __a)
1210 {
1211 #if _LIBCPP_DEBUG_LEVEL >= 2
1212     __get_db()->__insert_c(this);
1213 #endif
1214     __table_.rehash(__u.bucket_count());
1215     insert(__u.begin(), __u.end());
1216 }
1217
1218 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1219
1220 template <class _Value, class _Hash, class _Pred, class _Alloc>
1221 inline _LIBCPP_INLINE_VISIBILITY
1222 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1223         unordered_multiset&& __u)
1224     _NOEXCEPT_(is_nothrow_move_constructible<__table>::value)
1225     : __table_(_VSTD::move(__u.__table_))
1226 {
1227 #if _LIBCPP_DEBUG_LEVEL >= 2
1228     __get_db()->__insert_c(this);
1229     __get_db()->swap(this, &__u);
1230 #endif
1231 }
1232
1233 template <class _Value, class _Hash, class _Pred, class _Alloc>
1234 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1235         unordered_multiset&& __u, const allocator_type& __a)
1236     : __table_(_VSTD::move(__u.__table_), __a)
1237 {
1238 #if _LIBCPP_DEBUG_LEVEL >= 2
1239     __get_db()->__insert_c(this);
1240 #endif
1241     if (__a != __u.get_allocator())
1242     {
1243         iterator __i = __u.begin();
1244         while (__u.size() != 0)
1245             __table_.__insert_multi(_VSTD::move(__u.__table_.remove(__i++)->__value_));
1246     }
1247 #if _LIBCPP_DEBUG_LEVEL >= 2
1248     else
1249         __get_db()->swap(this, &__u);
1250 #endif
1251 }
1252
1253 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1254
1255 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1256
1257 template <class _Value, class _Hash, class _Pred, class _Alloc>
1258 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1259         initializer_list<value_type> __il)
1260 {
1261 #if _LIBCPP_DEBUG_LEVEL >= 2
1262     __get_db()->__insert_c(this);
1263 #endif
1264     insert(__il.begin(), __il.end());
1265 }
1266
1267 template <class _Value, class _Hash, class _Pred, class _Alloc>
1268 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1269         initializer_list<value_type> __il, size_type __n, const hasher& __hf,
1270         const key_equal& __eql)
1271     : __table_(__hf, __eql)
1272 {
1273 #if _LIBCPP_DEBUG_LEVEL >= 2
1274     __get_db()->__insert_c(this);
1275 #endif
1276     __table_.rehash(__n);
1277     insert(__il.begin(), __il.end());
1278 }
1279
1280 template <class _Value, class _Hash, class _Pred, class _Alloc>
1281 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1282         initializer_list<value_type> __il, size_type __n, const hasher& __hf,
1283         const key_equal& __eql, const allocator_type& __a)
1284     : __table_(__hf, __eql, __a)
1285 {
1286 #if _LIBCPP_DEBUG_LEVEL >= 2
1287     __get_db()->__insert_c(this);
1288 #endif
1289     __table_.rehash(__n);
1290     insert(__il.begin(), __il.end());
1291 }
1292
1293 #endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1294
1295 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1296
1297 template <class _Value, class _Hash, class _Pred, class _Alloc>
1298 inline _LIBCPP_INLINE_VISIBILITY
1299 unordered_multiset<_Value, _Hash, _Pred, _Alloc>&
1300 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::operator=(
1301         unordered_multiset&& __u)
1302     _NOEXCEPT_(is_nothrow_move_assignable<__table>::value)
1303 {
1304     __table_ = _VSTD::move(__u.__table_);
1305     return *this;
1306 }
1307
1308 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1309
1310 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1311
1312 template <class _Value, class _Hash, class _Pred, class _Alloc>
1313 inline
1314 unordered_multiset<_Value, _Hash, _Pred, _Alloc>&
1315 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::operator=(
1316         initializer_list<value_type> __il)
1317 {
1318     __table_.__assign_multi(__il.begin(), __il.end());
1319     return *this;
1320 }
1321
1322 #endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1323
1324 template <class _Value, class _Hash, class _Pred, class _Alloc>
1325 template <class _InputIterator>
1326 inline _LIBCPP_INLINE_VISIBILITY
1327 void
1328 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator __first,
1329                                                          _InputIterator __last)
1330 {
1331     for (; __first != __last; ++__first)
1332         __table_.__insert_multi(*__first);
1333 }
1334
1335 template <class _Value, class _Hash, class _Pred, class _Alloc>
1336 inline _LIBCPP_INLINE_VISIBILITY
1337 void
1338 swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1339      unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1340     _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
1341 {
1342     __x.swap(__y);
1343 }
1344
1345 template <class _Value, class _Hash, class _Pred, class _Alloc>
1346 bool
1347 operator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1348            const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1349 {
1350     if (__x.size() != __y.size())
1351         return false;
1352     typedef typename unordered_multiset<_Value, _Hash, _Pred, _Alloc>::const_iterator
1353                                                                  const_iterator;
1354     typedef pair<const_iterator, const_iterator> _EqRng;
1355     for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;)
1356     {
1357         _EqRng __xeq = __x.equal_range(*__i);
1358         _EqRng __yeq = __y.equal_range(*__i);
1359         if (_VSTD::distance(__xeq.first, __xeq.second) !=
1360             _VSTD::distance(__yeq.first, __yeq.second) ||
1361                   !_VSTD::is_permutation(__xeq.first, __xeq.second, __yeq.first))
1362             return false;
1363         __i = __xeq.second;
1364     }
1365     return true;
1366 }
1367
1368 template <class _Value, class _Hash, class _Pred, class _Alloc>
1369 inline _LIBCPP_INLINE_VISIBILITY
1370 bool
1371 operator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1372            const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1373 {
1374     return !(__x == __y);
1375 }
1376
1377 _LIBCPP_END_NAMESPACE_STD
1378
1379 #endif  // _LIBCPP_UNORDERED_SET