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