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