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