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