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