xref: /freebsd/contrib/llvm-project/libcxx/include/unordered_set (revision cb14a3fe5122c879eae1fb480ed7ce82a699ddb6)
10b57cec5SDimitry Andric// -*- C++ -*-
2349cc55cSDimitry Andric//===----------------------------------------------------------------------===//
30b57cec5SDimitry Andric//
40b57cec5SDimitry Andric// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
50b57cec5SDimitry Andric// See https://llvm.org/LICENSE.txt for license information.
60b57cec5SDimitry Andric// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
70b57cec5SDimitry Andric//
80b57cec5SDimitry Andric//===----------------------------------------------------------------------===//
90b57cec5SDimitry Andric
100b57cec5SDimitry Andric#ifndef _LIBCPP_UNORDERED_SET
110b57cec5SDimitry Andric#define _LIBCPP_UNORDERED_SET
120b57cec5SDimitry Andric
135f757f3fSDimitry Andric// clang-format off
145f757f3fSDimitry Andric
150b57cec5SDimitry Andric/*
160b57cec5SDimitry Andric
170b57cec5SDimitry Andric    unordered_set synopsis
180b57cec5SDimitry Andric
190b57cec5SDimitry Andric#include <initializer_list>
200b57cec5SDimitry Andric
210b57cec5SDimitry Andricnamespace std
220b57cec5SDimitry Andric{
230b57cec5SDimitry Andric
240b57cec5SDimitry Andrictemplate <class Value, class Hash = hash<Value>, class Pred = equal_to<Value>,
250b57cec5SDimitry Andric          class Alloc = allocator<Value>>
260b57cec5SDimitry Andricclass unordered_set
270b57cec5SDimitry Andric{
280b57cec5SDimitry Andricpublic:
290b57cec5SDimitry Andric    // types
300b57cec5SDimitry Andric    typedef Value                                                      key_type;
310b57cec5SDimitry Andric    typedef key_type                                                   value_type;
320b57cec5SDimitry Andric    typedef Hash                                                       hasher;
330b57cec5SDimitry Andric    typedef Pred                                                       key_equal;
340b57cec5SDimitry Andric    typedef Alloc                                                      allocator_type;
350b57cec5SDimitry Andric    typedef value_type&                                                reference;
360b57cec5SDimitry Andric    typedef const value_type&                                          const_reference;
370b57cec5SDimitry Andric    typedef typename allocator_traits<allocator_type>::pointer         pointer;
380b57cec5SDimitry Andric    typedef typename allocator_traits<allocator_type>::const_pointer   const_pointer;
390b57cec5SDimitry Andric    typedef typename allocator_traits<allocator_type>::size_type       size_type;
400b57cec5SDimitry Andric    typedef typename allocator_traits<allocator_type>::difference_type difference_type;
410b57cec5SDimitry Andric
420b57cec5SDimitry Andric    typedef /unspecified/ iterator;
430b57cec5SDimitry Andric    typedef /unspecified/ const_iterator;
440b57cec5SDimitry Andric    typedef /unspecified/ local_iterator;
450b57cec5SDimitry Andric    typedef /unspecified/ const_local_iterator;
460b57cec5SDimitry Andric
470b57cec5SDimitry Andric    typedef unspecified node_type unspecified;                            // C++17
480b57cec5SDimitry Andric    typedef INSERT_RETURN_TYPE<iterator, node_type> insert_return_type;   // C++17
490b57cec5SDimitry Andric
500b57cec5SDimitry Andric    unordered_set()
510b57cec5SDimitry Andric        noexcept(
520b57cec5SDimitry Andric            is_nothrow_default_constructible<hasher>::value &&
530b57cec5SDimitry Andric            is_nothrow_default_constructible<key_equal>::value &&
540b57cec5SDimitry Andric            is_nothrow_default_constructible<allocator_type>::value);
550b57cec5SDimitry Andric    explicit unordered_set(size_type n, const hasher& hf = hasher(),
560b57cec5SDimitry Andric                           const key_equal& eql = key_equal(),
570b57cec5SDimitry Andric                           const allocator_type& a = allocator_type());
580b57cec5SDimitry Andric    template <class InputIterator>
590b57cec5SDimitry Andric        unordered_set(InputIterator f, InputIterator l,
600b57cec5SDimitry Andric                      size_type n = 0, const hasher& hf = hasher(),
610b57cec5SDimitry Andric                      const key_equal& eql = key_equal(),
620b57cec5SDimitry Andric                      const allocator_type& a = allocator_type());
6306c3fb27SDimitry Andric    template<container-compatible-range<value_type> R>
6406c3fb27SDimitry Andric      unordered_set(from_range_t, R&& rg, size_type n = see below,
6506c3fb27SDimitry Andric        const hasher& hf = hasher(), const key_equal& eql = key_equal(),
6606c3fb27SDimitry Andric        const allocator_type& a = allocator_type()); // C++23
670b57cec5SDimitry Andric    explicit unordered_set(const allocator_type&);
680b57cec5SDimitry Andric    unordered_set(const unordered_set&);
690b57cec5SDimitry Andric    unordered_set(const unordered_set&, const Allocator&);
700b57cec5SDimitry Andric    unordered_set(unordered_set&&)
710b57cec5SDimitry Andric        noexcept(
720b57cec5SDimitry Andric            is_nothrow_move_constructible<hasher>::value &&
730b57cec5SDimitry Andric            is_nothrow_move_constructible<key_equal>::value &&
740b57cec5SDimitry Andric            is_nothrow_move_constructible<allocator_type>::value);
750b57cec5SDimitry Andric    unordered_set(unordered_set&&, const Allocator&);
760b57cec5SDimitry Andric    unordered_set(initializer_list<value_type>, size_type n = 0,
770b57cec5SDimitry Andric                  const hasher& hf = hasher(), const key_equal& eql = key_equal(),
780b57cec5SDimitry Andric                  const allocator_type& a = allocator_type());
790b57cec5SDimitry Andric    unordered_set(size_type n, const allocator_type& a); // C++14
800b57cec5SDimitry Andric    unordered_set(size_type n, const hasher& hf, const allocator_type& a); // C++14
810b57cec5SDimitry Andric    template <class InputIterator>
820b57cec5SDimitry Andric      unordered_set(InputIterator f, InputIterator l, size_type n, const allocator_type& a); // C++14
830b57cec5SDimitry Andric    template <class InputIterator>
840b57cec5SDimitry Andric      unordered_set(InputIterator f, InputIterator l, size_type n,
850b57cec5SDimitry Andric                    const hasher& hf,  const allocator_type& a); // C++14
8606c3fb27SDimitry Andric    template<container-compatible-range<value_type> R>
8706c3fb27SDimitry Andric      unordered_set(from_range_t, R&& rg, size_type n, const allocator_type& a)
8806c3fb27SDimitry Andric        : unordered_set(from_range, std::forward<R>(rg), n, hasher(), key_equal(), a) { } // C++23
8906c3fb27SDimitry Andric    template<container-compatible-range<value_type> R>
9006c3fb27SDimitry Andric      unordered_set(from_range_t, R&& rg, size_type n, const hasher& hf, const allocator_type& a)
9106c3fb27SDimitry Andric        : unordered_set(from_range, std::forward<R>(rg), n, hf, key_equal(), a) { }       // C++23
920b57cec5SDimitry Andric    unordered_set(initializer_list<value_type> il, size_type n, const allocator_type& a); // C++14
930b57cec5SDimitry Andric    unordered_set(initializer_list<value_type> il, size_type n,
940b57cec5SDimitry Andric                  const hasher& hf,  const allocator_type& a); // C++14
950b57cec5SDimitry Andric    ~unordered_set();
960b57cec5SDimitry Andric    unordered_set& operator=(const unordered_set&);
970b57cec5SDimitry Andric    unordered_set& operator=(unordered_set&&)
980b57cec5SDimitry Andric        noexcept(
990b57cec5SDimitry Andric            allocator_type::propagate_on_container_move_assignment::value &&
1000b57cec5SDimitry Andric            is_nothrow_move_assignable<allocator_type>::value &&
1010b57cec5SDimitry Andric            is_nothrow_move_assignable<hasher>::value &&
1020b57cec5SDimitry Andric            is_nothrow_move_assignable<key_equal>::value);
1030b57cec5SDimitry Andric    unordered_set& operator=(initializer_list<value_type>);
1040b57cec5SDimitry Andric
1050b57cec5SDimitry Andric    allocator_type get_allocator() const noexcept;
1060b57cec5SDimitry Andric
1070b57cec5SDimitry Andric    bool      empty() const noexcept;
1080b57cec5SDimitry Andric    size_type size() const noexcept;
1090b57cec5SDimitry Andric    size_type max_size() const noexcept;
1100b57cec5SDimitry Andric
1110b57cec5SDimitry Andric    iterator       begin() noexcept;
1120b57cec5SDimitry Andric    iterator       end() noexcept;
1130b57cec5SDimitry Andric    const_iterator begin()  const noexcept;
1140b57cec5SDimitry Andric    const_iterator end()    const noexcept;
1150b57cec5SDimitry Andric    const_iterator cbegin() const noexcept;
1160b57cec5SDimitry Andric    const_iterator cend()   const noexcept;
1170b57cec5SDimitry Andric
1180b57cec5SDimitry Andric    template <class... Args>
1190b57cec5SDimitry Andric        pair<iterator, bool> emplace(Args&&... args);
1200b57cec5SDimitry Andric    template <class... Args>
1210b57cec5SDimitry Andric        iterator emplace_hint(const_iterator position, Args&&... args);
1220b57cec5SDimitry Andric    pair<iterator, bool> insert(const value_type& obj);
1230b57cec5SDimitry Andric    pair<iterator, bool> insert(value_type&& obj);
1240b57cec5SDimitry Andric    iterator insert(const_iterator hint, const value_type& obj);
1250b57cec5SDimitry Andric    iterator insert(const_iterator hint, value_type&& obj);
1260b57cec5SDimitry Andric    template <class InputIterator>
1270b57cec5SDimitry Andric        void insert(InputIterator first, InputIterator last);
12806c3fb27SDimitry Andric    template<container-compatible-range<value_type> R>
12906c3fb27SDimitry Andric      void insert_range(R&& rg);                                      // C++23
1300b57cec5SDimitry Andric    void insert(initializer_list<value_type>);
1310b57cec5SDimitry Andric
1320b57cec5SDimitry Andric    node_type extract(const_iterator position);                       // C++17
1330b57cec5SDimitry Andric    node_type extract(const key_type& x);                             // C++17
1340b57cec5SDimitry Andric    insert_return_type insert(node_type&& nh);                        // C++17
1350b57cec5SDimitry Andric    iterator           insert(const_iterator hint, node_type&& nh);   // C++17
1360b57cec5SDimitry Andric
1370b57cec5SDimitry Andric    iterator erase(const_iterator position);
1380b57cec5SDimitry Andric    iterator erase(iterator position);  // C++14
1390b57cec5SDimitry Andric    size_type erase(const key_type& k);
1400b57cec5SDimitry Andric    iterator erase(const_iterator first, const_iterator last);
1410b57cec5SDimitry Andric    void clear() noexcept;
1420b57cec5SDimitry Andric
1430b57cec5SDimitry Andric    template<class H2, class P2>
1440b57cec5SDimitry Andric      void merge(unordered_set<Key, H2, P2, Allocator>& source);         // C++17
1450b57cec5SDimitry Andric    template<class H2, class P2>
1460b57cec5SDimitry Andric      void merge(unordered_set<Key, H2, P2, Allocator>&& source);        // C++17
1470b57cec5SDimitry Andric    template<class H2, class P2>
1480b57cec5SDimitry Andric      void merge(unordered_multiset<Key, H2, P2, Allocator>& source);    // C++17
1490b57cec5SDimitry Andric    template<class H2, class P2>
1500b57cec5SDimitry Andric      void merge(unordered_multiset<Key, H2, P2, Allocator>&& source);   // C++17
1510b57cec5SDimitry Andric
1520b57cec5SDimitry Andric    void swap(unordered_set&)
1530b57cec5SDimitry Andric       noexcept(allocator_traits<Allocator>::is_always_equal::value &&
1540b57cec5SDimitry Andric                 noexcept(swap(declval<hasher&>(), declval<hasher&>())) &&
1550b57cec5SDimitry Andric                 noexcept(swap(declval<key_equal&>(), declval<key_equal&>()))); // C++17
1560b57cec5SDimitry Andric
1570b57cec5SDimitry Andric    hasher hash_function() const;
1580b57cec5SDimitry Andric    key_equal key_eq() const;
1590b57cec5SDimitry Andric
1600b57cec5SDimitry Andric    iterator       find(const key_type& k);
1610b57cec5SDimitry Andric    const_iterator find(const key_type& k) const;
162e8d8bef9SDimitry Andric    template<typename K>
163e8d8bef9SDimitry Andric        iterator find(const K& x);              // C++20
164e8d8bef9SDimitry Andric    template<typename K>
165e8d8bef9SDimitry Andric        const_iterator find(const K& x) const;  // C++20
1660b57cec5SDimitry Andric    size_type count(const key_type& k) const;
167e8d8bef9SDimitry Andric    template<typename K>
168e8d8bef9SDimitry Andric        size_type count(const K& k) const; // C++20
1690b57cec5SDimitry Andric    bool contains(const key_type& k) const; // C++20
170e8d8bef9SDimitry Andric    template<typename K>
171e8d8bef9SDimitry Andric        bool contains(const K& k) const; // C++20
1720b57cec5SDimitry Andric    pair<iterator, iterator>             equal_range(const key_type& k);
1730b57cec5SDimitry Andric    pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
174e8d8bef9SDimitry Andric    template<typename K>
175e8d8bef9SDimitry Andric        pair<iterator, iterator>             equal_range(const K& k); // C++20
176e8d8bef9SDimitry Andric    template<typename K>
177e8d8bef9SDimitry Andric        pair<const_iterator, const_iterator> equal_range(const K& k) const; // C++20
1780b57cec5SDimitry Andric
1790b57cec5SDimitry Andric    size_type bucket_count() const noexcept;
1800b57cec5SDimitry Andric    size_type max_bucket_count() const noexcept;
1810b57cec5SDimitry Andric
1820b57cec5SDimitry Andric    size_type bucket_size(size_type n) const;
1830b57cec5SDimitry Andric    size_type bucket(const key_type& k) const;
1840b57cec5SDimitry Andric
1850b57cec5SDimitry Andric    local_iterator       begin(size_type n);
1860b57cec5SDimitry Andric    local_iterator       end(size_type n);
1870b57cec5SDimitry Andric    const_local_iterator begin(size_type n) const;
1880b57cec5SDimitry Andric    const_local_iterator end(size_type n) const;
1890b57cec5SDimitry Andric    const_local_iterator cbegin(size_type n) const;
1900b57cec5SDimitry Andric    const_local_iterator cend(size_type n) const;
1910b57cec5SDimitry Andric
1920b57cec5SDimitry Andric    float load_factor() const noexcept;
1930b57cec5SDimitry Andric    float max_load_factor() const noexcept;
1940b57cec5SDimitry Andric    void max_load_factor(float z);
1950b57cec5SDimitry Andric    void rehash(size_type n);
1960b57cec5SDimitry Andric    void reserve(size_type n);
1970b57cec5SDimitry Andric};
1980b57cec5SDimitry Andric
199349cc55cSDimitry Andrictemplate<class InputIterator,
200349cc55cSDimitry Andric    class Hash = hash<typename iterator_traits<InputIterator>::value_type>,
201349cc55cSDimitry Andric    class Pred = equal_to<typename iterator_traits<InputIterator>::value_type>,
202349cc55cSDimitry Andric    class Allocator = allocator<typename iterator_traits<InputIterator>::value_type>>
203349cc55cSDimitry Andricunordered_set(InputIterator, InputIterator, typename see below::size_type = see below,
204349cc55cSDimitry Andric    Hash = Hash(), Pred = Pred(), Allocator = Allocator())
205349cc55cSDimitry Andric  -> unordered_set<typename iterator_traits<InputIterator>::value_type,
206349cc55cSDimitry Andric        Hash, Pred, Allocator>; // C++17
207349cc55cSDimitry Andric
20806c3fb27SDimitry Andrictemplate<ranges::input_range R,
20906c3fb27SDimitry Andric         class Hash = hash<ranges::range_value_t<R>>,
21006c3fb27SDimitry Andric         class Pred = equal_to<ranges::range_value_t<R>>,
21106c3fb27SDimitry Andric         class Allocator = allocator<ranges::range_value_t<R>>>
21206c3fb27SDimitry Andric  unordered_set(from_range_t, R&&, typename see below::size_type = see below, Hash = Hash(), Pred = Pred(), Allocator = Allocator())
21306c3fb27SDimitry Andric    -> unordered_set<ranges::range_value_t<R>, Hash, Pred, Allocator>; // C++23
21406c3fb27SDimitry Andric
215349cc55cSDimitry Andrictemplate<class T, class Hash = hash<T>,
216349cc55cSDimitry Andric          class Pred = equal_to<T>, class Allocator = allocator<T>>
217349cc55cSDimitry Andricunordered_set(initializer_list<T>, typename see below::size_type = see below,
218349cc55cSDimitry Andric    Hash = Hash(), Pred = Pred(), Allocator = Allocator())
219349cc55cSDimitry Andric  -> unordered_set<T, Hash, Pred, Allocator>; // C++17
220349cc55cSDimitry Andric
221349cc55cSDimitry Andrictemplate<class InputIterator,  class Allocator>
222349cc55cSDimitry Andricunordered_set(InputIterator, InputIterator, typename see below::size_type, Allocator)
223349cc55cSDimitry Andric  -> unordered_set<typename iterator_traits<InputIterator>::value_type,
224349cc55cSDimitry Andric        hash<typename iterator_traits<InputIterator>::value_type>,
225349cc55cSDimitry Andric        equal_to<typename iterator_traits<InputIterator>::value_type>,
226349cc55cSDimitry Andric        Allocator>; // C++17
227349cc55cSDimitry Andric
228349cc55cSDimitry Andrictemplate<class InputIterator, class Hash, class Allocator>
229349cc55cSDimitry Andricunordered_set(InputIterator, InputIterator, typename see below::size_type,
230349cc55cSDimitry Andric    Hash, Allocator)
231349cc55cSDimitry Andric  -> unordered_set<typename iterator_traits<InputIterator>::value_type, Hash,
232349cc55cSDimitry Andric        equal_to<typename iterator_traits<InputIterator>::value_type>,
233349cc55cSDimitry Andric        Allocator>; // C++17
234349cc55cSDimitry Andric
23506c3fb27SDimitry Andrictemplate<ranges::input_range R, class Allocator>
23606c3fb27SDimitry Andric  unordered_set(from_range_t, R&&, typename see below::size_type, Allocator)
23706c3fb27SDimitry Andric    -> unordered_set<ranges::range_value_t<R>, hash<ranges::range_value_t<R>>,
23806c3fb27SDimitry Andric                      equal_to<ranges::range_value_t<R>>, Allocator>; // C++23
23906c3fb27SDimitry Andric
24006c3fb27SDimitry Andrictemplate<ranges::input_range R, class Allocator>
24106c3fb27SDimitry Andric  unordered_set(from_range_t, R&&, Allocator)
24206c3fb27SDimitry Andric    -> unordered_set<ranges::range_value_t<R>, hash<ranges::range_value_t<R>>,
24306c3fb27SDimitry Andric                      equal_to<ranges::range_value_t<R>>, Allocator>; // C++23
24406c3fb27SDimitry Andric
24506c3fb27SDimitry Andrictemplate<ranges::input_range R, class Hash, class Allocator>
24606c3fb27SDimitry Andric  unordered_set(from_range_t, R&&, typename see below::size_type, Hash, Allocator)
24706c3fb27SDimitry Andric    -> unordered_set<ranges::range_value_t<R>, Hash,
24806c3fb27SDimitry Andric                      equal_to<ranges::range_value_t<R>>, Allocator>; // C++23
24906c3fb27SDimitry Andric
250349cc55cSDimitry Andrictemplate<class T, class Allocator>
251349cc55cSDimitry Andricunordered_set(initializer_list<T>, typename see below::size_type, Allocator)
252349cc55cSDimitry Andric  -> unordered_set<T, hash<T>, equal_to<T>, Allocator>; // C++17
253349cc55cSDimitry Andric
254349cc55cSDimitry Andrictemplate<class T, class Hash, class Allocator>
255349cc55cSDimitry Andricunordered_set(initializer_list<T>, typename see below::size_type, Hash, Allocator)
256349cc55cSDimitry Andric  -> unordered_set<T, Hash, equal_to<T>, Allocator>; // C++17
257349cc55cSDimitry Andric
2580b57cec5SDimitry Andrictemplate <class Value, class Hash, class Pred, class Alloc>
2590b57cec5SDimitry Andric    void swap(unordered_set<Value, Hash, Pred, Alloc>& x,
2600b57cec5SDimitry Andric              unordered_set<Value, Hash, Pred, Alloc>& y)
2610b57cec5SDimitry Andric              noexcept(noexcept(x.swap(y)));
2620b57cec5SDimitry Andric
2630b57cec5SDimitry Andrictemplate <class Value, class Hash, class Pred, class Alloc>
2640b57cec5SDimitry Andric    bool
2650b57cec5SDimitry Andric    operator==(const unordered_set<Value, Hash, Pred, Alloc>& x,
2660b57cec5SDimitry Andric               const unordered_set<Value, Hash, Pred, Alloc>& y);
2670b57cec5SDimitry Andric
2680b57cec5SDimitry Andrictemplate <class Value, class Hash, class Pred, class Alloc>
2690b57cec5SDimitry Andric    bool
2700b57cec5SDimitry Andric    operator!=(const unordered_set<Value, Hash, Pred, Alloc>& x,
27106c3fb27SDimitry Andric               const unordered_set<Value, Hash, Pred, Alloc>& y); // removed in C++20
2720b57cec5SDimitry Andric
2730b57cec5SDimitry Andrictemplate <class Value, class Hash = hash<Value>, class Pred = equal_to<Value>,
2740b57cec5SDimitry Andric          class Alloc = allocator<Value>>
2750b57cec5SDimitry Andricclass unordered_multiset
2760b57cec5SDimitry Andric{
2770b57cec5SDimitry Andricpublic:
2780b57cec5SDimitry Andric    // types
2790b57cec5SDimitry Andric    typedef Value                                                      key_type;
2800b57cec5SDimitry Andric    typedef key_type                                                   value_type;
2810b57cec5SDimitry Andric    typedef Hash                                                       hasher;
2820b57cec5SDimitry Andric    typedef Pred                                                       key_equal;
2830b57cec5SDimitry Andric    typedef Alloc                                                      allocator_type;
2840b57cec5SDimitry Andric    typedef value_type&                                                reference;
2850b57cec5SDimitry Andric    typedef const value_type&                                          const_reference;
2860b57cec5SDimitry Andric    typedef typename allocator_traits<allocator_type>::pointer         pointer;
2870b57cec5SDimitry Andric    typedef typename allocator_traits<allocator_type>::const_pointer   const_pointer;
2880b57cec5SDimitry Andric    typedef typename allocator_traits<allocator_type>::size_type       size_type;
2890b57cec5SDimitry Andric    typedef typename allocator_traits<allocator_type>::difference_type difference_type;
2900b57cec5SDimitry Andric
2910b57cec5SDimitry Andric    typedef /unspecified/ iterator;
2920b57cec5SDimitry Andric    typedef /unspecified/ const_iterator;
2930b57cec5SDimitry Andric    typedef /unspecified/ local_iterator;
2940b57cec5SDimitry Andric    typedef /unspecified/ const_local_iterator;
2950b57cec5SDimitry Andric
2960b57cec5SDimitry Andric    typedef unspecified node_type unspecified;   // C++17
2970b57cec5SDimitry Andric
2980b57cec5SDimitry Andric    unordered_multiset()
2990b57cec5SDimitry Andric        noexcept(
3000b57cec5SDimitry Andric            is_nothrow_default_constructible<hasher>::value &&
3010b57cec5SDimitry Andric            is_nothrow_default_constructible<key_equal>::value &&
3020b57cec5SDimitry Andric            is_nothrow_default_constructible<allocator_type>::value);
3030b57cec5SDimitry Andric    explicit unordered_multiset(size_type n, const hasher& hf = hasher(),
3040b57cec5SDimitry Andric                           const key_equal& eql = key_equal(),
3050b57cec5SDimitry Andric                           const allocator_type& a = allocator_type());
3060b57cec5SDimitry Andric    template <class InputIterator>
3070b57cec5SDimitry Andric        unordered_multiset(InputIterator f, InputIterator l,
3080b57cec5SDimitry Andric                      size_type n = 0, const hasher& hf = hasher(),
3090b57cec5SDimitry Andric                      const key_equal& eql = key_equal(),
3100b57cec5SDimitry Andric                      const allocator_type& a = allocator_type());
31106c3fb27SDimitry Andric    template<container-compatible-range<value_type> R>
31206c3fb27SDimitry Andric      unordered_multiset(from_range_t, R&& rg, size_type n = see below,
31306c3fb27SDimitry Andric        const hasher& hf = hasher(), const key_equal& eql = key_equal(),
31406c3fb27SDimitry Andric        const allocator_type& a = allocator_type()); // C++23
3150b57cec5SDimitry Andric    explicit unordered_multiset(const allocator_type&);
3160b57cec5SDimitry Andric    unordered_multiset(const unordered_multiset&);
3170b57cec5SDimitry Andric    unordered_multiset(const unordered_multiset&, const Allocator&);
3180b57cec5SDimitry Andric    unordered_multiset(unordered_multiset&&)
3190b57cec5SDimitry Andric        noexcept(
3200b57cec5SDimitry Andric            is_nothrow_move_constructible<hasher>::value &&
3210b57cec5SDimitry Andric            is_nothrow_move_constructible<key_equal>::value &&
3220b57cec5SDimitry Andric            is_nothrow_move_constructible<allocator_type>::value);
3230b57cec5SDimitry Andric    unordered_multiset(unordered_multiset&&, const Allocator&);
3240b57cec5SDimitry Andric    unordered_multiset(initializer_list<value_type>, size_type n = /see below/,
3250b57cec5SDimitry Andric                  const hasher& hf = hasher(), const key_equal& eql = key_equal(),
3260b57cec5SDimitry Andric                  const allocator_type& a = allocator_type());
3270b57cec5SDimitry Andric    unordered_multiset(size_type n, const allocator_type& a); // C++14
3280b57cec5SDimitry Andric    unordered_multiset(size_type n, const hasher& hf, const allocator_type& a); // C++14
3290b57cec5SDimitry Andric    template <class InputIterator>
3300b57cec5SDimitry Andric      unordered_multiset(InputIterator f, InputIterator l, size_type n, const allocator_type& a); // C++14
3310b57cec5SDimitry Andric    template <class InputIterator>
3320b57cec5SDimitry Andric      unordered_multiset(InputIterator f, InputIterator l, size_type n,
3330b57cec5SDimitry Andric                         const hasher& hf, const allocator_type& a); // C++14
33406c3fb27SDimitry Andric    template<container-compatible-range<value_type> R>
33506c3fb27SDimitry Andric      unordered_multiset(from_range_t, R&& rg, size_type n, const allocator_type& a)
33606c3fb27SDimitry Andric        : unordered_multiset(from_range, std::forward<R>(rg), n, hasher(), key_equal(), a) { } // C++23
33706c3fb27SDimitry Andric    template<container-compatible-range<value_type> R>
33806c3fb27SDimitry Andric      unordered_multiset(from_range_t, R&& rg, size_type n, const hasher& hf, const allocator_type& a)
33906c3fb27SDimitry Andric        : unordered_multiset(from_range, std::forward<R>(rg), n, hf, key_equal(), a) { }       // C++23
3400b57cec5SDimitry Andric    unordered_multiset(initializer_list<value_type> il, size_type n, const allocator_type& a); // C++14
3410b57cec5SDimitry Andric    unordered_multiset(initializer_list<value_type> il, size_type n,
3420b57cec5SDimitry Andric                       const hasher& hf,  const allocator_type& a); // C++14
3430b57cec5SDimitry Andric    ~unordered_multiset();
3440b57cec5SDimitry Andric    unordered_multiset& operator=(const unordered_multiset&);
3450b57cec5SDimitry Andric    unordered_multiset& operator=(unordered_multiset&&)
3460b57cec5SDimitry Andric        noexcept(
3470b57cec5SDimitry Andric            allocator_type::propagate_on_container_move_assignment::value &&
3480b57cec5SDimitry Andric            is_nothrow_move_assignable<allocator_type>::value &&
3490b57cec5SDimitry Andric            is_nothrow_move_assignable<hasher>::value &&
3500b57cec5SDimitry Andric            is_nothrow_move_assignable<key_equal>::value);
3510b57cec5SDimitry Andric    unordered_multiset& operator=(initializer_list<value_type>);
3520b57cec5SDimitry Andric
3530b57cec5SDimitry Andric    allocator_type get_allocator() const noexcept;
3540b57cec5SDimitry Andric
3550b57cec5SDimitry Andric    bool      empty() const noexcept;
3560b57cec5SDimitry Andric    size_type size() const noexcept;
3570b57cec5SDimitry Andric    size_type max_size() const noexcept;
3580b57cec5SDimitry Andric
3590b57cec5SDimitry Andric    iterator       begin() noexcept;
3600b57cec5SDimitry Andric    iterator       end() noexcept;
3610b57cec5SDimitry Andric    const_iterator begin()  const noexcept;
3620b57cec5SDimitry Andric    const_iterator end()    const noexcept;
3630b57cec5SDimitry Andric    const_iterator cbegin() const noexcept;
3640b57cec5SDimitry Andric    const_iterator cend()   const noexcept;
3650b57cec5SDimitry Andric
3660b57cec5SDimitry Andric    template <class... Args>
3670b57cec5SDimitry Andric        iterator emplace(Args&&... args);
3680b57cec5SDimitry Andric    template <class... Args>
3690b57cec5SDimitry Andric        iterator emplace_hint(const_iterator position, Args&&... args);
3700b57cec5SDimitry Andric    iterator insert(const value_type& obj);
3710b57cec5SDimitry Andric    iterator insert(value_type&& obj);
3720b57cec5SDimitry Andric    iterator insert(const_iterator hint, const value_type& obj);
3730b57cec5SDimitry Andric    iterator insert(const_iterator hint, value_type&& obj);
3740b57cec5SDimitry Andric    template <class InputIterator>
3750b57cec5SDimitry Andric        void insert(InputIterator first, InputIterator last);
37606c3fb27SDimitry Andric    template<container-compatible-range<value_type> R>
37706c3fb27SDimitry Andric      void insert_range(R&& rg);                            // C++23
3780b57cec5SDimitry Andric    void insert(initializer_list<value_type>);
3790b57cec5SDimitry Andric
3800b57cec5SDimitry Andric    node_type extract(const_iterator position);             // C++17
3810b57cec5SDimitry Andric    node_type extract(const key_type& x);                   // C++17
3820b57cec5SDimitry Andric    iterator insert(node_type&& nh);                        // C++17
3830b57cec5SDimitry Andric    iterator insert(const_iterator hint, node_type&& nh);   // C++17
3840b57cec5SDimitry Andric
3850b57cec5SDimitry Andric    iterator erase(const_iterator position);
3860b57cec5SDimitry Andric    iterator erase(iterator position);  // C++14
3870b57cec5SDimitry Andric    size_type erase(const key_type& k);
3880b57cec5SDimitry Andric    iterator erase(const_iterator first, const_iterator last);
3890b57cec5SDimitry Andric    void clear() noexcept;
3900b57cec5SDimitry Andric
3910b57cec5SDimitry Andric    template<class H2, class P2>
3920b57cec5SDimitry Andric      void merge(unordered_multiset<Key, H2, P2, Allocator>& source);    // C++17
3930b57cec5SDimitry Andric    template<class H2, class P2>
3940b57cec5SDimitry Andric      void merge(unordered_multiset<Key, H2, P2, Allocator>&& source);   // C++17
3950b57cec5SDimitry Andric    template<class H2, class P2>
3960b57cec5SDimitry Andric      void merge(unordered_set<Key, H2, P2, Allocator>& source);         // C++17
3970b57cec5SDimitry Andric    template<class H2, class P2>
3980b57cec5SDimitry Andric      void merge(unordered_set<Key, H2, P2, Allocator>&& source);        // C++17
3990b57cec5SDimitry Andric
4000b57cec5SDimitry Andric    void swap(unordered_multiset&)
4010b57cec5SDimitry Andric       noexcept(allocator_traits<Allocator>::is_always_equal::value &&
4020b57cec5SDimitry Andric                 noexcept(swap(declval<hasher&>(), declval<hasher&>())) &&
4030b57cec5SDimitry Andric                 noexcept(swap(declval<key_equal&>(), declval<key_equal&>()))); // C++17
4040b57cec5SDimitry Andric
4050b57cec5SDimitry Andric    hasher hash_function() const;
4060b57cec5SDimitry Andric    key_equal key_eq() const;
4070b57cec5SDimitry Andric
4080b57cec5SDimitry Andric    iterator       find(const key_type& k);
4090b57cec5SDimitry Andric    const_iterator find(const key_type& k) const;
410e8d8bef9SDimitry Andric    template<typename K>
411e8d8bef9SDimitry Andric        iterator find(const K& x);              // C++20
412e8d8bef9SDimitry Andric    template<typename K>
413e8d8bef9SDimitry Andric        const_iterator find(const K& x) const;  // C++20
4140b57cec5SDimitry Andric    size_type count(const key_type& k) const;
415e8d8bef9SDimitry Andric    template<typename K>
416e8d8bef9SDimitry Andric        size_type count(const K& k) const; // C++20
4170b57cec5SDimitry Andric    bool contains(const key_type& k) const; // C++20
418e8d8bef9SDimitry Andric    template<typename K>
419e8d8bef9SDimitry Andric        bool contains(const K& k) const; // C++20
4200b57cec5SDimitry Andric    pair<iterator, iterator>             equal_range(const key_type& k);
4210b57cec5SDimitry Andric    pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
422e8d8bef9SDimitry Andric    template<typename K>
423e8d8bef9SDimitry Andric        pair<iterator, iterator>             equal_range(const K& k); // C++20
424e8d8bef9SDimitry Andric    template<typename K>
425e8d8bef9SDimitry Andric        pair<const_iterator, const_iterator> equal_range(const K& k) const; // C++20
4260b57cec5SDimitry Andric
4270b57cec5SDimitry Andric    size_type bucket_count() const noexcept;
4280b57cec5SDimitry Andric    size_type max_bucket_count() const noexcept;
4290b57cec5SDimitry Andric
4300b57cec5SDimitry Andric    size_type bucket_size(size_type n) const;
4310b57cec5SDimitry Andric    size_type bucket(const key_type& k) const;
4320b57cec5SDimitry Andric
4330b57cec5SDimitry Andric    local_iterator       begin(size_type n);
4340b57cec5SDimitry Andric    local_iterator       end(size_type n);
4350b57cec5SDimitry Andric    const_local_iterator begin(size_type n) const;
4360b57cec5SDimitry Andric    const_local_iterator end(size_type n) const;
4370b57cec5SDimitry Andric    const_local_iterator cbegin(size_type n) const;
4380b57cec5SDimitry Andric    const_local_iterator cend(size_type n) const;
4390b57cec5SDimitry Andric
4400b57cec5SDimitry Andric    float load_factor() const noexcept;
4410b57cec5SDimitry Andric    float max_load_factor() const noexcept;
4420b57cec5SDimitry Andric    void max_load_factor(float z);
4430b57cec5SDimitry Andric    void rehash(size_type n);
4440b57cec5SDimitry Andric    void reserve(size_type n);
4450b57cec5SDimitry Andric};
4460b57cec5SDimitry Andric
447349cc55cSDimitry Andrictemplate<class InputIterator,
448349cc55cSDimitry Andric    class Hash = hash<typename iterator_traits<InputIterator>::value_type>,
449349cc55cSDimitry Andric    class Pred = equal_to<typename iterator_traits<InputIterator>::value_type>,
450349cc55cSDimitry Andric    class Allocator = allocator<typename iterator_traits<InputIterator>::value_type>>
451349cc55cSDimitry Andricunordered_multiset(InputIterator, InputIterator, see below::size_type = see below,
452349cc55cSDimitry Andric    Hash = Hash(), Pred = Pred(), Allocator = Allocator())
453349cc55cSDimitry Andric  -> unordered_multiset<typename iterator_traits<InputIterator>::value_type,
454349cc55cSDimitry Andric        Hash, Pred, Allocator>; // C++17
455349cc55cSDimitry Andric
45606c3fb27SDimitry Andrictemplate<ranges::input_range R,
45706c3fb27SDimitry Andric         class Hash = hash<ranges::range_value_t<R>>,
45806c3fb27SDimitry Andric         class Pred = equal_to<ranges::range_value_t<R>>,
45906c3fb27SDimitry Andric         class Allocator = allocator<ranges::range_value_t<R>>>
46006c3fb27SDimitry Andric  unordered_multiset(from_range_t, R&&, typename see below::size_type = see below, Hash = Hash(), Pred = Pred(), Allocator = Allocator())
46106c3fb27SDimitry Andric    -> unordered_multiset<ranges::range_value_t<R>, Hash, Pred, Allocator>; // C++23
46206c3fb27SDimitry Andric
463349cc55cSDimitry Andrictemplate<class T, class Hash = hash<T>,
464349cc55cSDimitry Andric          class Pred = equal_to<T>, class Allocator = allocator<T>>
465349cc55cSDimitry Andricunordered_multiset(initializer_list<T>, typename see below::size_type = see below,
466349cc55cSDimitry Andric    Hash = Hash(), Pred = Pred(), Allocator = Allocator())
467349cc55cSDimitry Andric  -> unordered_multiset<T, Hash, Pred, Allocator>; // C++17
468349cc55cSDimitry Andric
469349cc55cSDimitry Andrictemplate<class InputIterator,  class Allocator>
470349cc55cSDimitry Andricunordered_multiset(InputIterator, InputIterator, typename see below::size_type, Allocator)
471349cc55cSDimitry Andric  -> unordered_multiset<typename iterator_traits<InputIterator>::value_type,
472349cc55cSDimitry Andric        hash<typename iterator_traits<InputIterator>::value_type>,
473349cc55cSDimitry Andric        equal_to<typename iterator_traits<InputIterator>::value_type>,
474349cc55cSDimitry Andric        Allocator>; // C++17
475349cc55cSDimitry Andric
476349cc55cSDimitry Andrictemplate<class InputIterator,  class Hash, class Allocator>
477349cc55cSDimitry Andricunordered_multiset(InputIterator, InputIterator, typename see below::size_type,
478349cc55cSDimitry Andric    Hash, Allocator)
479349cc55cSDimitry Andric  -> unordered_multiset<typename iterator_traits<InputIterator>::value_type, Hash,
480349cc55cSDimitry Andric        equal_to<typename iterator_traits<InputIterator>::value_type>, Allocator>; // C++17
481349cc55cSDimitry Andric
48206c3fb27SDimitry Andrictemplate<ranges::input_range R, class Allocator>
48306c3fb27SDimitry Andric  unordered_multiset(from_range_t, R&&, typename see below::size_type, Allocator)
48406c3fb27SDimitry Andric    -> unordered_multiset<ranges::range_value_t<R>, hash<ranges::range_value_t<R>>,
48506c3fb27SDimitry Andric                      equal_to<ranges::range_value_t<R>>, Allocator>; // C++23
48606c3fb27SDimitry Andric
48706c3fb27SDimitry Andrictemplate<ranges::input_range R, class Allocator>
48806c3fb27SDimitry Andric  unordered_multiset(from_range_t, R&&, Allocator)
48906c3fb27SDimitry Andric    -> unordered_multiset<ranges::range_value_t<R>, hash<ranges::range_value_t<R>>,
49006c3fb27SDimitry Andric                      equal_to<ranges::range_value_t<R>>, Allocator>; // C++23
49106c3fb27SDimitry Andric
49206c3fb27SDimitry Andrictemplate<ranges::input_range R, class Hash, class Allocator>
49306c3fb27SDimitry Andric  unordered_multiset(from_range_t, R&&, typename see below::size_type, Hash, Allocator)
49406c3fb27SDimitry Andric    -> unordered_multiset<ranges::range_value_t<R>, Hash,
49506c3fb27SDimitry Andric                      equal_to<ranges::range_value_t<R>>, Allocator>; // C++23
49606c3fb27SDimitry Andric
497349cc55cSDimitry Andrictemplate<class T, class Allocator>
498349cc55cSDimitry Andricunordered_multiset(initializer_list<T>, typename see below::size_type, Allocator)
499349cc55cSDimitry Andric  -> unordered_multiset<T, hash<T>, equal_to<T>, Allocator>; // C++17
500349cc55cSDimitry Andric
501349cc55cSDimitry Andrictemplate<class T, class Hash, class Allocator>
502349cc55cSDimitry Andricunordered_multiset(initializer_list<T>, typename see below::size_type, Hash, Allocator)
503349cc55cSDimitry Andric  -> unordered_multiset<T, Hash, equal_to<T>, Allocator>; // C++17
504349cc55cSDimitry Andric
5050b57cec5SDimitry Andrictemplate <class Value, class Hash, class Pred, class Alloc>
5060b57cec5SDimitry Andric    void swap(unordered_multiset<Value, Hash, Pred, Alloc>& x,
5070b57cec5SDimitry Andric              unordered_multiset<Value, Hash, Pred, Alloc>& y)
5080b57cec5SDimitry Andric              noexcept(noexcept(x.swap(y)));
5090b57cec5SDimitry Andric
5100b57cec5SDimitry Andrictemplate <class K, class T, class H, class P, class A, class Predicate>
5115ffd83dbSDimitry Andric    typename unordered_set<K, T, H, P, A>::size_type
5125ffd83dbSDimitry Andric    erase_if(unordered_set<K, T, H, P, A>& c, Predicate pred);       // C++20
5130b57cec5SDimitry Andric
5140b57cec5SDimitry Andrictemplate <class K, class T, class H, class P, class A, class Predicate>
5155ffd83dbSDimitry Andric    typename unordered_multiset<K, T, H, P, A>::size_type
5165ffd83dbSDimitry Andric    erase_if(unordered_multiset<K, T, H, P, A>& c, Predicate pred);  // C++20
5170b57cec5SDimitry Andric
5180b57cec5SDimitry Andric
5190b57cec5SDimitry Andrictemplate <class Value, class Hash, class Pred, class Alloc>
5200b57cec5SDimitry Andric    bool
5210b57cec5SDimitry Andric    operator==(const unordered_multiset<Value, Hash, Pred, Alloc>& x,
5220b57cec5SDimitry Andric               const unordered_multiset<Value, Hash, Pred, Alloc>& y);
5230b57cec5SDimitry Andric
5240b57cec5SDimitry Andrictemplate <class Value, class Hash, class Pred, class Alloc>
5250b57cec5SDimitry Andric    bool
5260b57cec5SDimitry Andric    operator!=(const unordered_multiset<Value, Hash, Pred, Alloc>& x,
52706c3fb27SDimitry Andric               const unordered_multiset<Value, Hash, Pred, Alloc>& y); // removed in C++20
5280b57cec5SDimitry Andric}  // std
5290b57cec5SDimitry Andric
5300b57cec5SDimitry Andric*/
5310b57cec5SDimitry Andric
5325f757f3fSDimitry Andric// clang-format on
5335f757f3fSDimitry Andric
53481ad6265SDimitry Andric#include <__algorithm/is_permutation.h>
53581ad6265SDimitry Andric#include <__assert> // all public C++ headers provide the assertion handler
53606c3fb27SDimitry Andric#include <__availability>
5370b57cec5SDimitry Andric#include <__config>
538fe6060f1SDimitry Andric#include <__functional/is_transparent.h>
53981ad6265SDimitry Andric#include <__functional/operations.h>
5400b57cec5SDimitry Andric#include <__hash_table>
54181ad6265SDimitry Andric#include <__iterator/distance.h>
54281ad6265SDimitry Andric#include <__iterator/erase_if_container.h>
54381ad6265SDimitry Andric#include <__iterator/iterator_traits.h>
54406c3fb27SDimitry Andric#include <__iterator/ranges_iterator_traits.h>
54504eeddc0SDimitry Andric#include <__memory/addressof.h>
546bdd1243dSDimitry Andric#include <__memory/allocator.h>
547bdd1243dSDimitry Andric#include <__memory_resource/polymorphic_allocator.h>
5480b57cec5SDimitry Andric#include <__node_handle>
54906c3fb27SDimitry Andric#include <__ranges/concepts.h>
55006c3fb27SDimitry Andric#include <__ranges/container_compatible_range.h>
55106c3fb27SDimitry Andric#include <__ranges/from_range.h>
552bdd1243dSDimitry Andric#include <__type_traits/is_allocator.h>
553fe6060f1SDimitry Andric#include <__utility/forward.h>
5540b57cec5SDimitry Andric#include <version>
5550b57cec5SDimitry Andric
55681ad6265SDimitry Andric// standard-mandated includes
55781ad6265SDimitry Andric
55881ad6265SDimitry Andric// [iterator.range]
55981ad6265SDimitry Andric#include <__iterator/access.h>
56081ad6265SDimitry Andric#include <__iterator/data.h>
56181ad6265SDimitry Andric#include <__iterator/empty.h>
56281ad6265SDimitry Andric#include <__iterator/reverse_access.h>
56381ad6265SDimitry Andric#include <__iterator/size.h>
56481ad6265SDimitry Andric
56581ad6265SDimitry Andric// [unord.set.syn]
56681ad6265SDimitry Andric#include <compare>
56781ad6265SDimitry Andric#include <initializer_list>
56881ad6265SDimitry Andric
5690b57cec5SDimitry Andric#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
5700b57cec5SDimitry Andric#  pragma GCC system_header
5710b57cec5SDimitry Andric#endif
5720b57cec5SDimitry Andric
5730b57cec5SDimitry Andric_LIBCPP_BEGIN_NAMESPACE_STD
5740b57cec5SDimitry Andric
5750b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc>
5760b57cec5SDimitry Andricclass unordered_multiset;
5770b57cec5SDimitry Andric
578*cb14a3feSDimitry Andrictemplate <class _Value, class _Hash = hash<_Value>, class _Pred = equal_to<_Value>, class _Alloc = allocator<_Value> >
579*cb14a3feSDimitry Andricclass _LIBCPP_TEMPLATE_VIS unordered_set {
5800b57cec5SDimitry Andricpublic:
5810b57cec5SDimitry Andric  // types
5820b57cec5SDimitry Andric  typedef _Value key_type;
5830b57cec5SDimitry Andric  typedef key_type value_type;
58481ad6265SDimitry Andric  typedef __type_identity_t<_Hash> hasher;
58581ad6265SDimitry Andric  typedef __type_identity_t<_Pred> key_equal;
58681ad6265SDimitry Andric  typedef __type_identity_t<_Alloc> allocator_type;
5870b57cec5SDimitry Andric  typedef value_type& reference;
5880b57cec5SDimitry Andric  typedef const value_type& const_reference;
5890b57cec5SDimitry Andric  static_assert((is_same<value_type, typename allocator_type::value_type>::value),
59006c3fb27SDimitry Andric                "Allocator::value_type must be same type as value_type");
5910b57cec5SDimitry Andric
592bdd1243dSDimitry Andric  static_assert(is_same<allocator_type, __rebind_alloc<allocator_traits<allocator_type>, value_type> >::value,
593bdd1243dSDimitry Andric                "[allocator.requirements] states that rebinding an allocator to the same type should result in the "
594bdd1243dSDimitry Andric                "original allocator");
595bdd1243dSDimitry Andric
5960b57cec5SDimitry Andricprivate:
5970b57cec5SDimitry Andric  typedef __hash_table<value_type, hasher, key_equal, allocator_type> __table;
5980b57cec5SDimitry Andric
5990b57cec5SDimitry Andric  __table __table_;
6000b57cec5SDimitry Andric
6010b57cec5SDimitry Andricpublic:
6020b57cec5SDimitry Andric  typedef typename __table::pointer pointer;
6030b57cec5SDimitry Andric  typedef typename __table::const_pointer const_pointer;
6040b57cec5SDimitry Andric  typedef typename __table::size_type size_type;
6050b57cec5SDimitry Andric  typedef typename __table::difference_type difference_type;
6060b57cec5SDimitry Andric
6070b57cec5SDimitry Andric  typedef typename __table::const_iterator iterator;
6080b57cec5SDimitry Andric  typedef typename __table::const_iterator const_iterator;
6090b57cec5SDimitry Andric  typedef typename __table::const_local_iterator local_iterator;
6100b57cec5SDimitry Andric  typedef typename __table::const_local_iterator const_local_iterator;
6110b57cec5SDimitry Andric
61206c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 17
6130b57cec5SDimitry Andric  typedef __set_node_handle<typename __table::__node, allocator_type> node_type;
6140b57cec5SDimitry Andric  typedef __insert_return_type<iterator, node_type> insert_return_type;
6150b57cec5SDimitry Andric#endif
6160b57cec5SDimitry Andric
6170b57cec5SDimitry Andric  template <class _Value2, class _Hash2, class _Pred2, class _Alloc2>
6180b57cec5SDimitry Andric  friend class _LIBCPP_TEMPLATE_VIS unordered_set;
6190b57cec5SDimitry Andric  template <class _Value2, class _Hash2, class _Pred2, class _Alloc2>
6200b57cec5SDimitry Andric  friend class _LIBCPP_TEMPLATE_VIS unordered_multiset;
6210b57cec5SDimitry Andric
622*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI unordered_set() _NOEXCEPT_(is_nothrow_default_constructible<__table>::value) {}
623*cb14a3feSDimitry Andric  explicit _LIBCPP_HIDE_FROM_ABI
624*cb14a3feSDimitry Andric  unordered_set(size_type __n, const hasher& __hf = hasher(), const key_equal& __eql = key_equal());
62506c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 14
626*cb14a3feSDimitry Andric  inline _LIBCPP_HIDE_FROM_ABI unordered_set(size_type __n, const allocator_type& __a)
6270b57cec5SDimitry Andric      : unordered_set(__n, hasher(), key_equal(), __a) {}
628*cb14a3feSDimitry Andric  inline _LIBCPP_HIDE_FROM_ABI unordered_set(size_type __n, const hasher& __hf, const allocator_type& __a)
6290b57cec5SDimitry Andric      : unordered_set(__n, __hf, key_equal(), __a) {}
6300b57cec5SDimitry Andric#endif
631*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI
632*cb14a3feSDimitry Andric  unordered_set(size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a);
6330b57cec5SDimitry Andric  template <class _InputIterator>
63406c3fb27SDimitry Andric  _LIBCPP_HIDE_FROM_ABI unordered_set(_InputIterator __first, _InputIterator __last);
6350b57cec5SDimitry Andric  template <class _InputIterator>
636*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI
637*cb14a3feSDimitry Andric  unordered_set(_InputIterator __first,
638*cb14a3feSDimitry Andric                _InputIterator __last,
639*cb14a3feSDimitry Andric                size_type __n,
640*cb14a3feSDimitry Andric                const hasher& __hf     = hasher(),
6410b57cec5SDimitry Andric                const key_equal& __eql = key_equal());
6420b57cec5SDimitry Andric  template <class _InputIterator>
643*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI unordered_set(
644*cb14a3feSDimitry Andric      _InputIterator __first,
645*cb14a3feSDimitry Andric      _InputIterator __last,
646*cb14a3feSDimitry Andric      size_type __n,
647*cb14a3feSDimitry Andric      const hasher& __hf,
648*cb14a3feSDimitry Andric      const key_equal& __eql,
6490b57cec5SDimitry Andric      const allocator_type& __a);
65006c3fb27SDimitry Andric
65106c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 23
65206c3fb27SDimitry Andric  template <_ContainerCompatibleRange<value_type> _Range>
653*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI unordered_set(
654*cb14a3feSDimitry Andric      from_range_t,
655*cb14a3feSDimitry Andric      _Range&& __range,
656*cb14a3feSDimitry Andric      size_type __n             = /*implementation-defined*/ 0,
657*cb14a3feSDimitry Andric      const hasher& __hf        = hasher(),
658*cb14a3feSDimitry Andric      const key_equal& __eql    = key_equal(),
65906c3fb27SDimitry Andric      const allocator_type& __a = allocator_type())
66006c3fb27SDimitry Andric      : __table_(__hf, __eql, __a) {
66106c3fb27SDimitry Andric    if (__n > 0) {
66206c3fb27SDimitry Andric      __table_.__rehash_unique(__n);
66306c3fb27SDimitry Andric    }
66406c3fb27SDimitry Andric    insert_range(std::forward<_Range>(__range));
66506c3fb27SDimitry Andric  }
66606c3fb27SDimitry Andric#endif
66706c3fb27SDimitry Andric
66806c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 14
6690b57cec5SDimitry Andric  template <class _InputIterator>
6705f757f3fSDimitry Andric  inline _LIBCPP_HIDE_FROM_ABI
671*cb14a3feSDimitry Andric  unordered_set(_InputIterator __first, _InputIterator __last, size_type __n, const allocator_type& __a)
6720b57cec5SDimitry Andric      : unordered_set(__first, __last, __n, hasher(), key_equal(), __a) {}
6730b57cec5SDimitry Andric  template <class _InputIterator>
674*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI unordered_set(
675*cb14a3feSDimitry Andric      _InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, const allocator_type& __a)
6760b57cec5SDimitry Andric      : unordered_set(__first, __last, __n, __hf, key_equal(), __a) {}
6770b57cec5SDimitry Andric#endif
67806c3fb27SDimitry Andric
67906c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 23
68006c3fb27SDimitry Andric  template <_ContainerCompatibleRange<value_type> _Range>
681*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI unordered_set(from_range_t, _Range&& __range, size_type __n, const allocator_type& __a)
68206c3fb27SDimitry Andric      : unordered_set(from_range, std::forward<_Range>(__range), __n, hasher(), key_equal(), __a) {}
68306c3fb27SDimitry Andric
68406c3fb27SDimitry Andric  template <_ContainerCompatibleRange<value_type> _Range>
68506c3fb27SDimitry Andric  _LIBCPP_HIDE_FROM_ABI
68606c3fb27SDimitry Andric  unordered_set(from_range_t, _Range&& __range, size_type __n, const hasher& __hf, const allocator_type& __a)
68706c3fb27SDimitry Andric      : unordered_set(from_range, std::forward<_Range>(__range), __n, __hf, key_equal(), __a) {}
68806c3fb27SDimitry Andric#endif
68906c3fb27SDimitry Andric
690*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI explicit unordered_set(const allocator_type& __a);
69106c3fb27SDimitry Andric  _LIBCPP_HIDE_FROM_ABI unordered_set(const unordered_set& __u);
69206c3fb27SDimitry Andric  _LIBCPP_HIDE_FROM_ABI unordered_set(const unordered_set& __u, const allocator_type& __a);
6930b57cec5SDimitry Andric#ifndef _LIBCPP_CXX03_LANG
694*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI unordered_set(unordered_set&& __u) _NOEXCEPT_(is_nothrow_move_constructible<__table>::value);
69506c3fb27SDimitry Andric  _LIBCPP_HIDE_FROM_ABI unordered_set(unordered_set&& __u, const allocator_type& __a);
69606c3fb27SDimitry Andric  _LIBCPP_HIDE_FROM_ABI unordered_set(initializer_list<value_type> __il);
697*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI
698*cb14a3feSDimitry Andric  unordered_set(initializer_list<value_type> __il,
699*cb14a3feSDimitry Andric                size_type __n,
7000b57cec5SDimitry Andric                const hasher& __hf     = hasher(),
7010b57cec5SDimitry Andric                const key_equal& __eql = key_equal());
702*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI unordered_set(
703*cb14a3feSDimitry Andric      initializer_list<value_type> __il,
704*cb14a3feSDimitry Andric      size_type __n,
705*cb14a3feSDimitry Andric      const hasher& __hf,
706*cb14a3feSDimitry Andric      const key_equal& __eql,
7070b57cec5SDimitry Andric      const allocator_type& __a);
70806c3fb27SDimitry Andric#  if _LIBCPP_STD_VER >= 14
7095f757f3fSDimitry Andric  inline _LIBCPP_HIDE_FROM_ABI
710*cb14a3feSDimitry Andric  unordered_set(initializer_list<value_type> __il, size_type __n, const allocator_type& __a)
7110b57cec5SDimitry Andric      : unordered_set(__il, __n, hasher(), key_equal(), __a) {}
7125f757f3fSDimitry Andric  inline _LIBCPP_HIDE_FROM_ABI
713*cb14a3feSDimitry Andric  unordered_set(initializer_list<value_type> __il, size_type __n, const hasher& __hf, const allocator_type& __a)
7140b57cec5SDimitry Andric      : unordered_set(__il, __n, __hf, key_equal(), __a) {}
7150b57cec5SDimitry Andric#  endif
7160b57cec5SDimitry Andric#endif // _LIBCPP_CXX03_LANG
717*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI ~unordered_set() {
718bdd1243dSDimitry Andric    static_assert(sizeof(std::__diagnose_unordered_container_requirements<_Value, _Hash, _Pred>(0)), "");
7190b57cec5SDimitry Andric  }
7200b57cec5SDimitry Andric
721*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI unordered_set& operator=(const unordered_set& __u) {
7220b57cec5SDimitry Andric    __table_ = __u.__table_;
7230b57cec5SDimitry Andric    return *this;
7240b57cec5SDimitry Andric  }
7250b57cec5SDimitry Andric#ifndef _LIBCPP_CXX03_LANG
726*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI unordered_set& operator=(unordered_set&& __u)
7270b57cec5SDimitry Andric      _NOEXCEPT_(is_nothrow_move_assignable<__table>::value);
728*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI unordered_set& operator=(initializer_list<value_type> __il);
7290b57cec5SDimitry Andric#endif // _LIBCPP_CXX03_LANG
7300b57cec5SDimitry Andric
731*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const _NOEXCEPT {
732*cb14a3feSDimitry Andric    return allocator_type(__table_.__node_alloc());
733*cb14a3feSDimitry Andric  }
7340b57cec5SDimitry Andric
735*cb14a3feSDimitry Andric  _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_HIDE_FROM_ABI bool empty() const _NOEXCEPT { return __table_.size() == 0; }
736*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI size_type size() const _NOEXCEPT { return __table_.size(); }
737*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI size_type max_size() const _NOEXCEPT { return __table_.max_size(); }
7380b57cec5SDimitry Andric
739*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI iterator begin() _NOEXCEPT { return __table_.begin(); }
740*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI iterator end() _NOEXCEPT { return __table_.end(); }
741*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI const_iterator begin() const _NOEXCEPT { return __table_.begin(); }
742*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI const_iterator end() const _NOEXCEPT { return __table_.end(); }
743*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI const_iterator cbegin() const _NOEXCEPT { return __table_.begin(); }
744*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI const_iterator cend() const _NOEXCEPT { return __table_.end(); }
7450b57cec5SDimitry Andric
7460b57cec5SDimitry Andric#ifndef _LIBCPP_CXX03_LANG
7470b57cec5SDimitry Andric  template <class... _Args>
748*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> emplace(_Args&&... __args) {
749*cb14a3feSDimitry Andric    return __table_.__emplace_unique(std::forward<_Args>(__args)...);
750*cb14a3feSDimitry Andric  }
7510b57cec5SDimitry Andric  template <class... _Args>
752*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI iterator emplace_hint(const_iterator, _Args&&... __args) {
75381ad6265SDimitry Andric    return __table_.__emplace_unique(std::forward<_Args>(__args)...).first;
7540b57cec5SDimitry Andric  }
7550b57cec5SDimitry Andric
756*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert(value_type&& __x) {
757*cb14a3feSDimitry Andric    return __table_.__insert_unique(std::move(__x));
7580b57cec5SDimitry Andric  }
759*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator, value_type&& __x) { return insert(std::move(__x)).first; }
76081ad6265SDimitry Andric
761*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI void insert(initializer_list<value_type> __il) { insert(__il.begin(), __il.end()); }
7620b57cec5SDimitry Andric#endif // _LIBCPP_CXX03_LANG
763*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert(const value_type& __x) { return __table_.__insert_unique(__x); }
7640b57cec5SDimitry Andric
765*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator, const value_type& __x) { return insert(__x).first; }
7660b57cec5SDimitry Andric  template <class _InputIterator>
767*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI void insert(_InputIterator __first, _InputIterator __last);
7680b57cec5SDimitry Andric
76906c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 23
77006c3fb27SDimitry Andric  template <_ContainerCompatibleRange<value_type> _Range>
771*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI void insert_range(_Range&& __range) {
77206c3fb27SDimitry Andric    for (auto&& __element : __range) {
77306c3fb27SDimitry Andric      __table_.__insert_unique(std::forward<decltype(__element)>(__element));
77406c3fb27SDimitry Andric    }
77506c3fb27SDimitry Andric  }
77606c3fb27SDimitry Andric#endif
77706c3fb27SDimitry Andric
778*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __p) { return __table_.erase(__p); }
779*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI size_type erase(const key_type& __k) { return __table_.__erase_unique(__k); }
780*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __first, const_iterator __last) {
781*cb14a3feSDimitry Andric    return __table_.erase(__first, __last);
782*cb14a3feSDimitry Andric  }
783*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT { __table_.clear(); }
7840b57cec5SDimitry Andric
78506c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 17
786*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI insert_return_type insert(node_type&& __nh) {
78706c3fb27SDimitry Andric    _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(),
7880b57cec5SDimitry Andric                                        "node_type with incompatible allocator passed to unordered_set::insert()");
789*cb14a3feSDimitry Andric    return __table_.template __node_handle_insert_unique< node_type, insert_return_type>(std::move(__nh));
7900b57cec5SDimitry Andric  }
791*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __h, node_type&& __nh) {
79206c3fb27SDimitry Andric    _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(),
7930b57cec5SDimitry Andric                                        "node_type with incompatible allocator passed to unordered_set::insert()");
794*cb14a3feSDimitry Andric    return __table_.template __node_handle_insert_unique<node_type>(__h, std::move(__nh));
7950b57cec5SDimitry Andric  }
796*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI node_type extract(key_type const& __key) {
7970b57cec5SDimitry Andric    return __table_.template __node_handle_extract<node_type>(__key);
7980b57cec5SDimitry Andric  }
799*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI node_type extract(const_iterator __it) {
8000b57cec5SDimitry Andric    return __table_.template __node_handle_extract<node_type>(__it);
8010b57cec5SDimitry Andric  }
8020b57cec5SDimitry Andric
8030b57cec5SDimitry Andric  template <class _H2, class _P2>
804*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI void merge(unordered_set<key_type, _H2, _P2, allocator_type>& __source) {
805*cb14a3feSDimitry Andric    _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
806*cb14a3feSDimitry Andric        __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
8070b57cec5SDimitry Andric    __table_.__node_handle_merge_unique(__source.__table_);
8080b57cec5SDimitry Andric  }
8090b57cec5SDimitry Andric  template <class _H2, class _P2>
810*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI void merge(unordered_set<key_type, _H2, _P2, allocator_type>&& __source) {
811*cb14a3feSDimitry Andric    _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
812*cb14a3feSDimitry Andric        __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
8130b57cec5SDimitry Andric    __table_.__node_handle_merge_unique(__source.__table_);
8140b57cec5SDimitry Andric  }
8150b57cec5SDimitry Andric  template <class _H2, class _P2>
816*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI void merge(unordered_multiset<key_type, _H2, _P2, allocator_type>& __source) {
817*cb14a3feSDimitry Andric    _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
818*cb14a3feSDimitry Andric        __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
8190b57cec5SDimitry Andric    __table_.__node_handle_merge_unique(__source.__table_);
8200b57cec5SDimitry Andric  }
8210b57cec5SDimitry Andric  template <class _H2, class _P2>
822*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI void merge(unordered_multiset<key_type, _H2, _P2, allocator_type>&& __source) {
823*cb14a3feSDimitry Andric    _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
824*cb14a3feSDimitry Andric        __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
8250b57cec5SDimitry Andric    __table_.__node_handle_merge_unique(__source.__table_);
8260b57cec5SDimitry Andric  }
8270b57cec5SDimitry Andric#endif
8280b57cec5SDimitry Andric
829*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI void swap(unordered_set& __u) _NOEXCEPT_(__is_nothrow_swappable<__table>::value) {
830*cb14a3feSDimitry Andric    __table_.swap(__u.__table_);
831*cb14a3feSDimitry Andric  }
8320b57cec5SDimitry Andric
833*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI hasher hash_function() const { return __table_.hash_function(); }
834*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI key_equal key_eq() const { return __table_.key_eq(); }
8350b57cec5SDimitry Andric
836*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI iterator find(const key_type& __k) { return __table_.find(__k); }
837*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI const_iterator find(const key_type& __k) const { return __table_.find(__k); }
83806c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 20
839*cb14a3feSDimitry Andric  template <class _K2,
840*cb14a3feSDimitry Andric            enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr>
841*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI iterator find(const _K2& __k) {
842*cb14a3feSDimitry Andric    return __table_.find(__k);
843*cb14a3feSDimitry Andric  }
844*cb14a3feSDimitry Andric  template <class _K2,
845*cb14a3feSDimitry Andric            enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr>
846*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI const_iterator find(const _K2& __k) const {
847*cb14a3feSDimitry Andric    return __table_.find(__k);
848*cb14a3feSDimitry Andric  }
84906c3fb27SDimitry Andric#endif // _LIBCPP_STD_VER >= 20
850349cc55cSDimitry Andric
851*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI size_type count(const key_type& __k) const { return __table_.__count_unique(__k); }
85206c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 20
853*cb14a3feSDimitry Andric  template <class _K2,
854*cb14a3feSDimitry Andric            enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr>
855*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI size_type count(const _K2& __k) const {
856*cb14a3feSDimitry Andric    return __table_.__count_unique(__k);
857*cb14a3feSDimitry Andric  }
85806c3fb27SDimitry Andric#endif // _LIBCPP_STD_VER >= 20
859349cc55cSDimitry Andric
86006c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 20
861*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI bool contains(const key_type& __k) const { return find(__k) != end(); }
862e8d8bef9SDimitry Andric
863*cb14a3feSDimitry Andric  template <class _K2,
864*cb14a3feSDimitry Andric            enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr>
865*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI bool contains(const _K2& __k) const {
866*cb14a3feSDimitry Andric    return find(__k) != end();
867*cb14a3feSDimitry Andric  }
86806c3fb27SDimitry Andric#endif // _LIBCPP_STD_VER >= 20
869349cc55cSDimitry Andric
870*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const key_type& __k) {
871*cb14a3feSDimitry Andric    return __table_.__equal_range_unique(__k);
872*cb14a3feSDimitry Andric  }
873*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const key_type& __k) const {
874*cb14a3feSDimitry Andric    return __table_.__equal_range_unique(__k);
875*cb14a3feSDimitry Andric  }
87606c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 20
877*cb14a3feSDimitry Andric  template <class _K2,
878*cb14a3feSDimitry Andric            enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr>
879*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const _K2& __k) {
880*cb14a3feSDimitry Andric    return __table_.__equal_range_unique(__k);
881*cb14a3feSDimitry Andric  }
882*cb14a3feSDimitry Andric  template <class _K2,
883*cb14a3feSDimitry Andric            enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr>
884*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const _K2& __k) const {
885*cb14a3feSDimitry Andric    return __table_.__equal_range_unique(__k);
886*cb14a3feSDimitry Andric  }
88706c3fb27SDimitry Andric#endif // _LIBCPP_STD_VER >= 20
8880b57cec5SDimitry Andric
889*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI size_type bucket_count() const _NOEXCEPT { return __table_.bucket_count(); }
890*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI size_type max_bucket_count() const _NOEXCEPT { return __table_.max_bucket_count(); }
8910b57cec5SDimitry Andric
892*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI size_type bucket_size(size_type __n) const { return __table_.bucket_size(__n); }
893*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI size_type bucket(const key_type& __k) const { return __table_.bucket(__k); }
8940b57cec5SDimitry Andric
895*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI local_iterator begin(size_type __n) { return __table_.begin(__n); }
896*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI local_iterator end(size_type __n) { return __table_.end(__n); }
897*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI const_local_iterator begin(size_type __n) const { return __table_.cbegin(__n); }
898*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI const_local_iterator end(size_type __n) const { return __table_.cend(__n); }
899*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI const_local_iterator cbegin(size_type __n) const { return __table_.cbegin(__n); }
900*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI const_local_iterator cend(size_type __n) const { return __table_.cend(__n); }
9010b57cec5SDimitry Andric
902*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI float load_factor() const _NOEXCEPT { return __table_.load_factor(); }
903*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI float max_load_factor() const _NOEXCEPT { return __table_.max_load_factor(); }
904*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI void max_load_factor(float __mlf) { __table_.max_load_factor(__mlf); }
905*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI void rehash(size_type __n) { __table_.__rehash_unique(__n); }
906*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI void reserve(size_type __n) { __table_.__reserve_unique(__n); }
9070b57cec5SDimitry Andric};
9080b57cec5SDimitry Andric
909349cc55cSDimitry Andric#if _LIBCPP_STD_VER >= 17
9100b57cec5SDimitry Andrictemplate <class _InputIterator,
9110b57cec5SDimitry Andric          class _Hash      = hash<__iter_value_type<_InputIterator>>,
9120b57cec5SDimitry Andric          class _Pred      = equal_to<__iter_value_type<_InputIterator>>,
9130b57cec5SDimitry Andric          class _Allocator = allocator<__iter_value_type<_InputIterator>>,
91406c3fb27SDimitry Andric          class            = enable_if_t<__has_input_iterator_category<_InputIterator>::value>,
915349cc55cSDimitry Andric          class            = enable_if_t<!__is_allocator<_Hash>::value>,
916349cc55cSDimitry Andric          class            = enable_if_t<!is_integral<_Hash>::value>,
917349cc55cSDimitry Andric          class            = enable_if_t<!__is_allocator<_Pred>::value>,
918349cc55cSDimitry Andric          class            = enable_if_t<__is_allocator<_Allocator>::value>>
919*cb14a3feSDimitry Andricunordered_set(_InputIterator,
920*cb14a3feSDimitry Andric              _InputIterator,
921*cb14a3feSDimitry Andric              typename allocator_traits<_Allocator>::size_type = 0,
922*cb14a3feSDimitry Andric              _Hash                                            = _Hash(),
923*cb14a3feSDimitry Andric              _Pred                                            = _Pred(),
924*cb14a3feSDimitry Andric              _Allocator = _Allocator()) -> unordered_set<__iter_value_type<_InputIterator>, _Hash, _Pred, _Allocator>;
9250b57cec5SDimitry Andric
92606c3fb27SDimitry Andric#  if _LIBCPP_STD_VER >= 23
92706c3fb27SDimitry Andrictemplate <ranges::input_range _Range,
92806c3fb27SDimitry Andric          class _Hash      = hash<ranges::range_value_t<_Range>>,
92906c3fb27SDimitry Andric          class _Pred      = equal_to<ranges::range_value_t<_Range>>,
93006c3fb27SDimitry Andric          class _Allocator = allocator<ranges::range_value_t<_Range>>,
93106c3fb27SDimitry Andric          class            = enable_if_t<!__is_allocator<_Hash>::value>,
93206c3fb27SDimitry Andric          class            = enable_if_t<!is_integral<_Hash>::value>,
93306c3fb27SDimitry Andric          class            = enable_if_t<!__is_allocator<_Pred>::value>,
93406c3fb27SDimitry Andric          class            = enable_if_t<__is_allocator<_Allocator>::value>>
935*cb14a3feSDimitry Andricunordered_set(from_range_t,
936*cb14a3feSDimitry Andric              _Range&&,
937*cb14a3feSDimitry Andric              typename allocator_traits<_Allocator>::size_type = 0,
938*cb14a3feSDimitry Andric              _Hash                                            = _Hash(),
939*cb14a3feSDimitry Andric              _Pred                                            = _Pred(),
940*cb14a3feSDimitry Andric              _Allocator                                       = _Allocator())
94106c3fb27SDimitry Andric    -> unordered_set<ranges::range_value_t<_Range>, _Hash, _Pred, _Allocator>; // C++23
94206c3fb27SDimitry Andric#  endif
94306c3fb27SDimitry Andric
944*cb14a3feSDimitry Andrictemplate <class _Tp,
945*cb14a3feSDimitry Andric          class _Hash      = hash<_Tp>,
9460b57cec5SDimitry Andric          class _Pred      = equal_to<_Tp>,
9470b57cec5SDimitry Andric          class _Allocator = allocator<_Tp>,
948349cc55cSDimitry Andric          class            = enable_if_t<!__is_allocator<_Hash>::value>,
949349cc55cSDimitry Andric          class            = enable_if_t<!is_integral<_Hash>::value>,
950349cc55cSDimitry Andric          class            = enable_if_t<!__is_allocator<_Pred>::value>,
951349cc55cSDimitry Andric          class            = enable_if_t<__is_allocator<_Allocator>::value>>
952*cb14a3feSDimitry Andricunordered_set(initializer_list<_Tp>,
953*cb14a3feSDimitry Andric              typename allocator_traits<_Allocator>::size_type = 0,
954*cb14a3feSDimitry Andric              _Hash                                            = _Hash(),
955*cb14a3feSDimitry Andric              _Pred                                            = _Pred(),
956*cb14a3feSDimitry Andric              _Allocator = _Allocator()) -> unordered_set<_Tp, _Hash, _Pred, _Allocator>;
9570b57cec5SDimitry Andric
958*cb14a3feSDimitry Andrictemplate <class _InputIterator,
959*cb14a3feSDimitry Andric          class _Allocator,
96006c3fb27SDimitry Andric          class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>,
961349cc55cSDimitry Andric          class = enable_if_t<__is_allocator<_Allocator>::value>>
962*cb14a3feSDimitry Andricunordered_set(_InputIterator, _InputIterator, typename allocator_traits<_Allocator>::size_type, _Allocator)
9630b57cec5SDimitry Andric    -> unordered_set<__iter_value_type<_InputIterator>,
9640b57cec5SDimitry Andric                     hash<__iter_value_type<_InputIterator>>,
9650b57cec5SDimitry Andric                     equal_to<__iter_value_type<_InputIterator>>,
9660b57cec5SDimitry Andric                     _Allocator>;
9670b57cec5SDimitry Andric
968*cb14a3feSDimitry Andrictemplate <class _InputIterator,
969*cb14a3feSDimitry Andric          class _Hash,
970*cb14a3feSDimitry Andric          class _Allocator,
97106c3fb27SDimitry Andric          class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>,
972349cc55cSDimitry Andric          class = enable_if_t<!__is_allocator<_Hash>::value>,
973349cc55cSDimitry Andric          class = enable_if_t<!is_integral<_Hash>::value>,
974349cc55cSDimitry Andric          class = enable_if_t<__is_allocator<_Allocator>::value>>
975*cb14a3feSDimitry Andricunordered_set(_InputIterator, _InputIterator, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator)
976*cb14a3feSDimitry Andric    -> unordered_set<__iter_value_type<_InputIterator>, _Hash, equal_to<__iter_value_type<_InputIterator>>, _Allocator>;
9770b57cec5SDimitry Andric
97806c3fb27SDimitry Andric#  if _LIBCPP_STD_VER >= 23
97906c3fb27SDimitry Andric
980*cb14a3feSDimitry Andrictemplate <ranges::input_range _Range, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value>>
98106c3fb27SDimitry Andricunordered_set(from_range_t, _Range&&, typename allocator_traits<_Allocator>::size_type, _Allocator)
982*cb14a3feSDimitry Andric    -> unordered_set<ranges::range_value_t<_Range>,
983*cb14a3feSDimitry Andric                     hash<ranges::range_value_t<_Range>>,
984*cb14a3feSDimitry Andric                     equal_to<ranges::range_value_t<_Range>>,
985*cb14a3feSDimitry Andric                     _Allocator>;
98606c3fb27SDimitry Andric
987*cb14a3feSDimitry Andrictemplate <ranges::input_range _Range, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value>>
98806c3fb27SDimitry Andricunordered_set(from_range_t, _Range&&, _Allocator)
989*cb14a3feSDimitry Andric    -> unordered_set<ranges::range_value_t<_Range>,
990*cb14a3feSDimitry Andric                     hash<ranges::range_value_t<_Range>>,
991*cb14a3feSDimitry Andric                     equal_to<ranges::range_value_t<_Range>>,
992*cb14a3feSDimitry Andric                     _Allocator>;
99306c3fb27SDimitry Andric
994*cb14a3feSDimitry Andrictemplate <ranges::input_range _Range,
995*cb14a3feSDimitry Andric          class _Hash,
996*cb14a3feSDimitry Andric          class _Allocator,
99706c3fb27SDimitry Andric          class = enable_if_t<!__is_allocator<_Hash>::value>,
99806c3fb27SDimitry Andric          class = enable_if_t<!is_integral<_Hash>::value>,
99906c3fb27SDimitry Andric          class = enable_if_t<__is_allocator<_Allocator>::value>>
100006c3fb27SDimitry Andricunordered_set(from_range_t, _Range&&, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator)
100106c3fb27SDimitry Andric    -> unordered_set<ranges::range_value_t<_Range>, _Hash, equal_to<ranges::range_value_t<_Range>>, _Allocator>;
100206c3fb27SDimitry Andric
100306c3fb27SDimitry Andric#  endif
100406c3fb27SDimitry Andric
1005*cb14a3feSDimitry Andrictemplate <class _Tp, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value>>
10060b57cec5SDimitry Andricunordered_set(initializer_list<_Tp>, typename allocator_traits<_Allocator>::size_type, _Allocator)
10070b57cec5SDimitry Andric    -> unordered_set<_Tp, hash<_Tp>, equal_to<_Tp>, _Allocator>;
10080b57cec5SDimitry Andric
1009*cb14a3feSDimitry Andrictemplate <class _Tp,
1010*cb14a3feSDimitry Andric          class _Hash,
1011*cb14a3feSDimitry Andric          class _Allocator,
1012349cc55cSDimitry Andric          class = enable_if_t<!__is_allocator<_Hash>::value>,
1013349cc55cSDimitry Andric          class = enable_if_t<!is_integral<_Hash>::value>,
1014349cc55cSDimitry Andric          class = enable_if_t<__is_allocator<_Allocator>::value>>
10150b57cec5SDimitry Andricunordered_set(initializer_list<_Tp>, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator)
10160b57cec5SDimitry Andric    -> unordered_set<_Tp, _Hash, equal_to<_Tp>, _Allocator>;
10170b57cec5SDimitry Andric#endif
10180b57cec5SDimitry Andric
10190b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc>
1020*cb14a3feSDimitry Andricunordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(size_type __n, const hasher& __hf, const key_equal& __eql)
1021*cb14a3feSDimitry Andric    : __table_(__hf, __eql) {
1022753f127fSDimitry Andric  __table_.__rehash_unique(__n);
10230b57cec5SDimitry Andric}
10240b57cec5SDimitry Andric
10250b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc>
1026*cb14a3feSDimitry Andricunordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
1027*cb14a3feSDimitry Andric    size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
1028*cb14a3feSDimitry Andric    : __table_(__hf, __eql, __a) {
1029753f127fSDimitry Andric  __table_.__rehash_unique(__n);
10300b57cec5SDimitry Andric}
10310b57cec5SDimitry Andric
10320b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc>
10330b57cec5SDimitry Andrictemplate <class _InputIterator>
1034*cb14a3feSDimitry Andricunordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(_InputIterator __first, _InputIterator __last) {
10350b57cec5SDimitry Andric  insert(__first, __last);
10360b57cec5SDimitry Andric}
10370b57cec5SDimitry Andric
10380b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc>
10390b57cec5SDimitry Andrictemplate <class _InputIterator>
10400b57cec5SDimitry Andricunordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
1041*cb14a3feSDimitry Andric    _InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, const key_equal& __eql)
1042*cb14a3feSDimitry Andric    : __table_(__hf, __eql) {
1043753f127fSDimitry Andric  __table_.__rehash_unique(__n);
10440b57cec5SDimitry Andric  insert(__first, __last);
10450b57cec5SDimitry Andric}
10460b57cec5SDimitry Andric
10470b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc>
10480b57cec5SDimitry Andrictemplate <class _InputIterator>
10490b57cec5SDimitry Andricunordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
1050*cb14a3feSDimitry Andric    _InputIterator __first,
1051*cb14a3feSDimitry Andric    _InputIterator __last,
1052*cb14a3feSDimitry Andric    size_type __n,
1053*cb14a3feSDimitry Andric    const hasher& __hf,
1054*cb14a3feSDimitry Andric    const key_equal& __eql,
10550b57cec5SDimitry Andric    const allocator_type& __a)
1056*cb14a3feSDimitry Andric    : __table_(__hf, __eql, __a) {
1057*cb14a3feSDimitry Andric  __table_.__rehash_unique(__n);
1058*cb14a3feSDimitry Andric  insert(__first, __last);
10590b57cec5SDimitry Andric}
10600b57cec5SDimitry Andric
10610b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc>
1062*cb14a3feSDimitry Andricinline unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(const allocator_type& __a) : __table_(__a) {}
1063*cb14a3feSDimitry Andric
1064*cb14a3feSDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc>
1065*cb14a3feSDimitry Andricunordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(const unordered_set& __u) : __table_(__u.__table_) {
1066753f127fSDimitry Andric  __table_.__rehash_unique(__u.bucket_count());
10670b57cec5SDimitry Andric  insert(__u.begin(), __u.end());
10680b57cec5SDimitry Andric}
10690b57cec5SDimitry Andric
10700b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc>
1071*cb14a3feSDimitry Andricunordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(const unordered_set& __u, const allocator_type& __a)
1072*cb14a3feSDimitry Andric    : __table_(__u.__table_, __a) {
1073753f127fSDimitry Andric  __table_.__rehash_unique(__u.bucket_count());
10740b57cec5SDimitry Andric  insert(__u.begin(), __u.end());
10750b57cec5SDimitry Andric}
10760b57cec5SDimitry Andric
10770b57cec5SDimitry Andric#ifndef _LIBCPP_CXX03_LANG
10780b57cec5SDimitry Andric
10790b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc>
1080*cb14a3feSDimitry Andricinline unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(unordered_set&& __u)
10810b57cec5SDimitry Andric    _NOEXCEPT_(is_nothrow_move_constructible<__table>::value)
1082*cb14a3feSDimitry Andric    : __table_(std::move(__u.__table_)) {}
10830b57cec5SDimitry Andric
10840b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc>
1085*cb14a3feSDimitry Andricunordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(unordered_set&& __u, const allocator_type& __a)
1086*cb14a3feSDimitry Andric    : __table_(std::move(__u.__table_), __a) {
1087*cb14a3feSDimitry Andric  if (__a != __u.get_allocator()) {
10880b57cec5SDimitry Andric    iterator __i = __u.begin();
10890b57cec5SDimitry Andric    while (__u.size() != 0)
10905f757f3fSDimitry Andric      __table_.__insert_unique(std::move(__u.__table_.remove(__i++)->__get_value()));
10910b57cec5SDimitry Andric  }
10920b57cec5SDimitry Andric}
10930b57cec5SDimitry Andric
10940b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc>
1095*cb14a3feSDimitry Andricunordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(initializer_list<value_type> __il) {
10960b57cec5SDimitry Andric  insert(__il.begin(), __il.end());
10970b57cec5SDimitry Andric}
10980b57cec5SDimitry Andric
10990b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc>
11000b57cec5SDimitry Andricunordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
1101*cb14a3feSDimitry Andric    initializer_list<value_type> __il, size_type __n, const hasher& __hf, const key_equal& __eql)
1102*cb14a3feSDimitry Andric    : __table_(__hf, __eql) {
1103753f127fSDimitry Andric  __table_.__rehash_unique(__n);
11040b57cec5SDimitry Andric  insert(__il.begin(), __il.end());
11050b57cec5SDimitry Andric}
11060b57cec5SDimitry Andric
11070b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc>
11080b57cec5SDimitry Andricunordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
1109*cb14a3feSDimitry Andric    initializer_list<value_type> __il,
1110*cb14a3feSDimitry Andric    size_type __n,
1111*cb14a3feSDimitry Andric    const hasher& __hf,
1112*cb14a3feSDimitry Andric    const key_equal& __eql,
1113*cb14a3feSDimitry Andric    const allocator_type& __a)
1114*cb14a3feSDimitry Andric    : __table_(__hf, __eql, __a) {
1115753f127fSDimitry Andric  __table_.__rehash_unique(__n);
11160b57cec5SDimitry Andric  insert(__il.begin(), __il.end());
11170b57cec5SDimitry Andric}
11180b57cec5SDimitry Andric
11190b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc>
1120*cb14a3feSDimitry Andricinline unordered_set<_Value, _Hash, _Pred, _Alloc>&
11210b57cec5SDimitry Andricunordered_set<_Value, _Hash, _Pred, _Alloc>::operator=(unordered_set&& __u)
1122*cb14a3feSDimitry Andric    _NOEXCEPT_(is_nothrow_move_assignable<__table>::value) {
11235f757f3fSDimitry Andric  __table_ = std::move(__u.__table_);
11240b57cec5SDimitry Andric  return *this;
11250b57cec5SDimitry Andric}
11260b57cec5SDimitry Andric
11270b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc>
1128*cb14a3feSDimitry Andricinline unordered_set<_Value, _Hash, _Pred, _Alloc>&
1129*cb14a3feSDimitry Andricunordered_set<_Value, _Hash, _Pred, _Alloc>::operator=(initializer_list<value_type> __il) {
11300b57cec5SDimitry Andric  __table_.__assign_unique(__il.begin(), __il.end());
11310b57cec5SDimitry Andric  return *this;
11320b57cec5SDimitry Andric}
11330b57cec5SDimitry Andric
11340b57cec5SDimitry Andric#endif // _LIBCPP_CXX03_LANG
11350b57cec5SDimitry Andric
11360b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc>
11370b57cec5SDimitry Andrictemplate <class _InputIterator>
1138*cb14a3feSDimitry Andricinline void unordered_set<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, _InputIterator __last) {
11390b57cec5SDimitry Andric  for (; __first != __last; ++__first)
11400b57cec5SDimitry Andric    __table_.__insert_unique(*__first);
11410b57cec5SDimitry Andric}
11420b57cec5SDimitry Andric
11430b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc>
1144*cb14a3feSDimitry Andricinline _LIBCPP_HIDE_FROM_ABI void
1145*cb14a3feSDimitry Andricswap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
1146*cb14a3feSDimitry Andric    _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) {
11470b57cec5SDimitry Andric  __x.swap(__y);
11480b57cec5SDimitry Andric}
11490b57cec5SDimitry Andric
115006c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 20
1151*cb14a3feSDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc, class _Predicate>
1152*cb14a3feSDimitry Andricinline _LIBCPP_HIDE_FROM_ABI typename unordered_set<_Value, _Hash, _Pred, _Alloc>::size_type
1153*cb14a3feSDimitry Andricerase_if(unordered_set<_Value, _Hash, _Pred, _Alloc>& __c, _Predicate __pred) {
11545f757f3fSDimitry Andric  return std::__libcpp_erase_if_container(__c, __pred);
11555ffd83dbSDimitry Andric}
11560b57cec5SDimitry Andric#endif
11570b57cec5SDimitry Andric
11580b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc>
1159*cb14a3feSDimitry Andric_LIBCPP_HIDE_FROM_ABI bool operator==(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
1160*cb14a3feSDimitry Andric                                      const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) {
11610b57cec5SDimitry Andric  if (__x.size() != __y.size())
11620b57cec5SDimitry Andric    return false;
1163*cb14a3feSDimitry Andric  typedef typename unordered_set<_Value, _Hash, _Pred, _Alloc>::const_iterator const_iterator;
1164*cb14a3feSDimitry Andric  for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end(); __i != __ex; ++__i) {
11650b57cec5SDimitry Andric    const_iterator __j = __y.find(*__i);
11660b57cec5SDimitry Andric    if (__j == __ey || !(*__i == *__j))
11670b57cec5SDimitry Andric      return false;
11680b57cec5SDimitry Andric  }
11690b57cec5SDimitry Andric  return true;
11700b57cec5SDimitry Andric}
11710b57cec5SDimitry Andric
117206c3fb27SDimitry Andric#if _LIBCPP_STD_VER <= 17
117306c3fb27SDimitry Andric
11740b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc>
1175*cb14a3feSDimitry Andricinline _LIBCPP_HIDE_FROM_ABI bool operator!=(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
1176*cb14a3feSDimitry Andric                                             const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) {
11770b57cec5SDimitry Andric  return !(__x == __y);
11780b57cec5SDimitry Andric}
11790b57cec5SDimitry Andric
118006c3fb27SDimitry Andric#endif
118106c3fb27SDimitry Andric
1182*cb14a3feSDimitry Andrictemplate <class _Value, class _Hash = hash<_Value>, class _Pred = equal_to<_Value>, class _Alloc = allocator<_Value> >
1183*cb14a3feSDimitry Andricclass _LIBCPP_TEMPLATE_VIS unordered_multiset {
11840b57cec5SDimitry Andricpublic:
11850b57cec5SDimitry Andric  // types
11860b57cec5SDimitry Andric  typedef _Value key_type;
11870b57cec5SDimitry Andric  typedef key_type value_type;
118881ad6265SDimitry Andric  typedef __type_identity_t<_Hash> hasher;
118981ad6265SDimitry Andric  typedef __type_identity_t<_Pred> key_equal;
119081ad6265SDimitry Andric  typedef __type_identity_t<_Alloc> allocator_type;
11910b57cec5SDimitry Andric  typedef value_type& reference;
11920b57cec5SDimitry Andric  typedef const value_type& const_reference;
11930b57cec5SDimitry Andric  static_assert((is_same<value_type, typename allocator_type::value_type>::value),
119406c3fb27SDimitry Andric                "Allocator::value_type must be same type as value_type");
11950b57cec5SDimitry Andric
11960b57cec5SDimitry Andricprivate:
11970b57cec5SDimitry Andric  typedef __hash_table<value_type, hasher, key_equal, allocator_type> __table;
11980b57cec5SDimitry Andric
11990b57cec5SDimitry Andric  __table __table_;
12000b57cec5SDimitry Andric
12010b57cec5SDimitry Andricpublic:
12020b57cec5SDimitry Andric  typedef typename __table::pointer pointer;
12030b57cec5SDimitry Andric  typedef typename __table::const_pointer const_pointer;
12040b57cec5SDimitry Andric  typedef typename __table::size_type size_type;
12050b57cec5SDimitry Andric  typedef typename __table::difference_type difference_type;
12060b57cec5SDimitry Andric
12070b57cec5SDimitry Andric  typedef typename __table::const_iterator iterator;
12080b57cec5SDimitry Andric  typedef typename __table::const_iterator const_iterator;
12090b57cec5SDimitry Andric  typedef typename __table::const_local_iterator local_iterator;
12100b57cec5SDimitry Andric  typedef typename __table::const_local_iterator const_local_iterator;
12110b57cec5SDimitry Andric
121206c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 17
12130b57cec5SDimitry Andric  typedef __set_node_handle<typename __table::__node, allocator_type> node_type;
12140b57cec5SDimitry Andric#endif
12150b57cec5SDimitry Andric
12160b57cec5SDimitry Andric  template <class _Value2, class _Hash2, class _Pred2, class _Alloc2>
12170b57cec5SDimitry Andric  friend class _LIBCPP_TEMPLATE_VIS unordered_set;
12180b57cec5SDimitry Andric  template <class _Value2, class _Hash2, class _Pred2, class _Alloc2>
12190b57cec5SDimitry Andric  friend class _LIBCPP_TEMPLATE_VIS unordered_multiset;
12200b57cec5SDimitry Andric
1221*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI unordered_multiset() _NOEXCEPT_(is_nothrow_default_constructible<__table>::value) {}
1222*cb14a3feSDimitry Andric  explicit _LIBCPP_HIDE_FROM_ABI
1223*cb14a3feSDimitry Andric  unordered_multiset(size_type __n, const hasher& __hf = hasher(), const key_equal& __eql = key_equal());
12245f757f3fSDimitry Andric  _LIBCPP_HIDE_FROM_ABI
1225*cb14a3feSDimitry Andric  unordered_multiset(size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a);
122606c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 14
1227*cb14a3feSDimitry Andric  inline _LIBCPP_HIDE_FROM_ABI unordered_multiset(size_type __n, const allocator_type& __a)
12280b57cec5SDimitry Andric      : unordered_multiset(__n, hasher(), key_equal(), __a) {}
1229*cb14a3feSDimitry Andric  inline _LIBCPP_HIDE_FROM_ABI unordered_multiset(size_type __n, const hasher& __hf, const allocator_type& __a)
12300b57cec5SDimitry Andric      : unordered_multiset(__n, __hf, key_equal(), __a) {}
12310b57cec5SDimitry Andric#endif
12320b57cec5SDimitry Andric  template <class _InputIterator>
123306c3fb27SDimitry Andric  _LIBCPP_HIDE_FROM_ABI unordered_multiset(_InputIterator __first, _InputIterator __last);
12340b57cec5SDimitry Andric  template <class _InputIterator>
1235*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI unordered_multiset(
1236*cb14a3feSDimitry Andric      _InputIterator __first,
1237*cb14a3feSDimitry Andric      _InputIterator __last,
1238*cb14a3feSDimitry Andric      size_type __n,
1239*cb14a3feSDimitry Andric      const hasher& __hf     = hasher(),
12400b57cec5SDimitry Andric      const key_equal& __eql = key_equal());
12410b57cec5SDimitry Andric  template <class _InputIterator>
1242*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI unordered_multiset(
1243*cb14a3feSDimitry Andric      _InputIterator __first,
1244*cb14a3feSDimitry Andric      _InputIterator __last,
1245*cb14a3feSDimitry Andric      size_type __n,
1246*cb14a3feSDimitry Andric      const hasher& __hf,
1247*cb14a3feSDimitry Andric      const key_equal& __eql,
1248*cb14a3feSDimitry Andric      const allocator_type& __a);
124906c3fb27SDimitry Andric
125006c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 23
125106c3fb27SDimitry Andric  template <_ContainerCompatibleRange<value_type> _Range>
1252*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI unordered_multiset(
1253*cb14a3feSDimitry Andric      from_range_t,
1254*cb14a3feSDimitry Andric      _Range&& __range,
1255*cb14a3feSDimitry Andric      size_type __n             = /*implementation-defined*/ 0,
1256*cb14a3feSDimitry Andric      const hasher& __hf        = hasher(),
1257*cb14a3feSDimitry Andric      const key_equal& __eql    = key_equal(),
125806c3fb27SDimitry Andric      const allocator_type& __a = allocator_type())
125906c3fb27SDimitry Andric      : __table_(__hf, __eql, __a) {
126006c3fb27SDimitry Andric    if (__n > 0) {
126106c3fb27SDimitry Andric      __table_.__rehash_multi(__n);
126206c3fb27SDimitry Andric    }
126306c3fb27SDimitry Andric    insert_range(std::forward<_Range>(__range));
126406c3fb27SDimitry Andric  }
126506c3fb27SDimitry Andric#endif
126606c3fb27SDimitry Andric
126706c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 14
12680b57cec5SDimitry Andric  template <class _InputIterator>
12695f757f3fSDimitry Andric  inline _LIBCPP_HIDE_FROM_ABI
1270*cb14a3feSDimitry Andric  unordered_multiset(_InputIterator __first, _InputIterator __last, size_type __n, const allocator_type& __a)
12710b57cec5SDimitry Andric      : unordered_multiset(__first, __last, __n, hasher(), key_equal(), __a) {}
12720b57cec5SDimitry Andric  template <class _InputIterator>
1273*cb14a3feSDimitry Andric  inline _LIBCPP_HIDE_FROM_ABI unordered_multiset(
1274*cb14a3feSDimitry Andric      _InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, const allocator_type& __a)
12750b57cec5SDimitry Andric      : unordered_multiset(__first, __last, __n, __hf, key_equal(), __a) {}
12760b57cec5SDimitry Andric#endif
127706c3fb27SDimitry Andric
127806c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 23
127906c3fb27SDimitry Andric  template <_ContainerCompatibleRange<value_type> _Range>
1280*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI unordered_multiset(from_range_t, _Range&& __range, size_type __n, const allocator_type& __a)
128106c3fb27SDimitry Andric      : unordered_multiset(from_range, std::forward<_Range>(__range), __n, hasher(), key_equal(), __a) {}
128206c3fb27SDimitry Andric
128306c3fb27SDimitry Andric  template <_ContainerCompatibleRange<value_type> _Range>
128406c3fb27SDimitry Andric  _LIBCPP_HIDE_FROM_ABI
128506c3fb27SDimitry Andric  unordered_multiset(from_range_t, _Range&& __range, size_type __n, const hasher& __hf, const allocator_type& __a)
128606c3fb27SDimitry Andric      : unordered_multiset(from_range, std::forward<_Range>(__range), __n, __hf, key_equal(), __a) {}
128706c3fb27SDimitry Andric#endif
128806c3fb27SDimitry Andric
1289*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI explicit unordered_multiset(const allocator_type& __a);
129006c3fb27SDimitry Andric  _LIBCPP_HIDE_FROM_ABI unordered_multiset(const unordered_multiset& __u);
129106c3fb27SDimitry Andric  _LIBCPP_HIDE_FROM_ABI unordered_multiset(const unordered_multiset& __u, const allocator_type& __a);
12920b57cec5SDimitry Andric#ifndef _LIBCPP_CXX03_LANG
1293*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI unordered_multiset(unordered_multiset&& __u)
12940b57cec5SDimitry Andric      _NOEXCEPT_(is_nothrow_move_constructible<__table>::value);
129506c3fb27SDimitry Andric  _LIBCPP_HIDE_FROM_ABI unordered_multiset(unordered_multiset&& __u, const allocator_type& __a);
129606c3fb27SDimitry Andric  _LIBCPP_HIDE_FROM_ABI unordered_multiset(initializer_list<value_type> __il);
1297*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI unordered_multiset(
1298*cb14a3feSDimitry Andric      initializer_list<value_type> __il,
1299*cb14a3feSDimitry Andric      size_type __n,
13000b57cec5SDimitry Andric      const hasher& __hf     = hasher(),
13010b57cec5SDimitry Andric      const key_equal& __eql = key_equal());
1302*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI unordered_multiset(
1303*cb14a3feSDimitry Andric      initializer_list<value_type> __il,
1304*cb14a3feSDimitry Andric      size_type __n,
1305*cb14a3feSDimitry Andric      const hasher& __hf,
1306*cb14a3feSDimitry Andric      const key_equal& __eql,
13070b57cec5SDimitry Andric      const allocator_type& __a);
130806c3fb27SDimitry Andric#  if _LIBCPP_STD_VER >= 14
13095f757f3fSDimitry Andric  inline _LIBCPP_HIDE_FROM_ABI
13100b57cec5SDimitry Andric  unordered_multiset(initializer_list<value_type> __il, size_type __n, const allocator_type& __a)
13110b57cec5SDimitry Andric      : unordered_multiset(__il, __n, hasher(), key_equal(), __a) {}
13125f757f3fSDimitry Andric  inline _LIBCPP_HIDE_FROM_ABI
13130b57cec5SDimitry Andric  unordered_multiset(initializer_list<value_type> __il, size_type __n, const hasher& __hf, const allocator_type& __a)
13140b57cec5SDimitry Andric      : unordered_multiset(__il, __n, __hf, key_equal(), __a) {}
13150b57cec5SDimitry Andric#  endif
13160b57cec5SDimitry Andric#endif // _LIBCPP_CXX03_LANG
1317*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI ~unordered_multiset() {
1318bdd1243dSDimitry Andric    static_assert(sizeof(std::__diagnose_unordered_container_requirements<_Value, _Hash, _Pred>(0)), "");
13190b57cec5SDimitry Andric  }
13200b57cec5SDimitry Andric
1321*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI unordered_multiset& operator=(const unordered_multiset& __u) {
13220b57cec5SDimitry Andric    __table_ = __u.__table_;
13230b57cec5SDimitry Andric    return *this;
13240b57cec5SDimitry Andric  }
13250b57cec5SDimitry Andric#ifndef _LIBCPP_CXX03_LANG
1326*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI unordered_multiset& operator=(unordered_multiset&& __u)
13270b57cec5SDimitry Andric      _NOEXCEPT_(is_nothrow_move_assignable<__table>::value);
132806c3fb27SDimitry Andric  _LIBCPP_HIDE_FROM_ABI unordered_multiset& operator=(initializer_list<value_type> __il);
13290b57cec5SDimitry Andric#endif // _LIBCPP_CXX03_LANG
13300b57cec5SDimitry Andric
1331*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const _NOEXCEPT {
1332*cb14a3feSDimitry Andric    return allocator_type(__table_.__node_alloc());
1333*cb14a3feSDimitry Andric  }
13340b57cec5SDimitry Andric
1335*cb14a3feSDimitry Andric  _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_HIDE_FROM_ABI bool empty() const _NOEXCEPT { return __table_.size() == 0; }
1336*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI size_type size() const _NOEXCEPT { return __table_.size(); }
1337*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI size_type max_size() const _NOEXCEPT { return __table_.max_size(); }
13380b57cec5SDimitry Andric
1339*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI iterator begin() _NOEXCEPT { return __table_.begin(); }
1340*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI iterator end() _NOEXCEPT { return __table_.end(); }
1341*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI const_iterator begin() const _NOEXCEPT { return __table_.begin(); }
1342*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI const_iterator end() const _NOEXCEPT { return __table_.end(); }
1343*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI const_iterator cbegin() const _NOEXCEPT { return __table_.begin(); }
1344*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI const_iterator cend() const _NOEXCEPT { return __table_.end(); }
13450b57cec5SDimitry Andric
13460b57cec5SDimitry Andric#ifndef _LIBCPP_CXX03_LANG
13470b57cec5SDimitry Andric  template <class... _Args>
1348*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI iterator emplace(_Args&&... __args) {
1349*cb14a3feSDimitry Andric    return __table_.__emplace_multi(std::forward<_Args>(__args)...);
1350*cb14a3feSDimitry Andric  }
13510b57cec5SDimitry Andric  template <class... _Args>
1352*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI iterator emplace_hint(const_iterator __p, _Args&&... __args) {
1353*cb14a3feSDimitry Andric    return __table_.__emplace_hint_multi(__p, std::forward<_Args>(__args)...);
1354*cb14a3feSDimitry Andric  }
13550b57cec5SDimitry Andric
1356*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI iterator insert(value_type&& __x) { return __table_.__insert_multi(std::move(__x)); }
1357*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, value_type&& __x) {
1358*cb14a3feSDimitry Andric    return __table_.__insert_multi(__p, std::move(__x));
1359*cb14a3feSDimitry Andric  }
1360*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI void insert(initializer_list<value_type> __il) { insert(__il.begin(), __il.end()); }
13610b57cec5SDimitry Andric#endif // _LIBCPP_CXX03_LANG
13620b57cec5SDimitry Andric
1363*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI iterator insert(const value_type& __x) { return __table_.__insert_multi(__x); }
13640b57cec5SDimitry Andric
1365*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, const value_type& __x) {
1366*cb14a3feSDimitry Andric    return __table_.__insert_multi(__p, __x);
1367*cb14a3feSDimitry Andric  }
13680b57cec5SDimitry Andric
13690b57cec5SDimitry Andric  template <class _InputIterator>
1370*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI void insert(_InputIterator __first, _InputIterator __last);
13710b57cec5SDimitry Andric
137206c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 23
137306c3fb27SDimitry Andric  template <_ContainerCompatibleRange<value_type> _Range>
1374*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI void insert_range(_Range&& __range) {
137506c3fb27SDimitry Andric    for (auto&& __element : __range) {
137606c3fb27SDimitry Andric      __table_.__insert_multi(std::forward<decltype(__element)>(__element));
137706c3fb27SDimitry Andric    }
137806c3fb27SDimitry Andric  }
137906c3fb27SDimitry Andric#endif
138006c3fb27SDimitry Andric
138106c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 17
1382*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI iterator insert(node_type&& __nh) {
138306c3fb27SDimitry Andric    _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(),
13840b57cec5SDimitry Andric                                        "node_type with incompatible allocator passed to unordered_multiset::insert()");
1385*cb14a3feSDimitry Andric    return __table_.template __node_handle_insert_multi<node_type>(std::move(__nh));
13860b57cec5SDimitry Andric  }
1387*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __hint, node_type&& __nh) {
138806c3fb27SDimitry Andric    _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(),
13890b57cec5SDimitry Andric                                        "node_type with incompatible allocator passed to unordered_multiset::insert()");
1390*cb14a3feSDimitry Andric    return __table_.template __node_handle_insert_multi<node_type>(__hint, std::move(__nh));
13910b57cec5SDimitry Andric  }
1392*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI node_type extract(const_iterator __position) {
1393*cb14a3feSDimitry Andric    return __table_.template __node_handle_extract<node_type>(__position);
13940b57cec5SDimitry Andric  }
1395*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI node_type extract(key_type const& __key) {
13960b57cec5SDimitry Andric    return __table_.template __node_handle_extract<node_type>(__key);
13970b57cec5SDimitry Andric  }
13980b57cec5SDimitry Andric
13990b57cec5SDimitry Andric  template <class _H2, class _P2>
1400*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI void merge(unordered_multiset<key_type, _H2, _P2, allocator_type>& __source) {
1401*cb14a3feSDimitry Andric    _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
1402*cb14a3feSDimitry Andric        __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
14030b57cec5SDimitry Andric    return __table_.__node_handle_merge_multi(__source.__table_);
14040b57cec5SDimitry Andric  }
14050b57cec5SDimitry Andric  template <class _H2, class _P2>
1406*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI void merge(unordered_multiset<key_type, _H2, _P2, allocator_type>&& __source) {
1407*cb14a3feSDimitry Andric    _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
1408*cb14a3feSDimitry Andric        __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
14090b57cec5SDimitry Andric    return __table_.__node_handle_merge_multi(__source.__table_);
14100b57cec5SDimitry Andric  }
14110b57cec5SDimitry Andric  template <class _H2, class _P2>
1412*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI void merge(unordered_set<key_type, _H2, _P2, allocator_type>& __source) {
1413*cb14a3feSDimitry Andric    _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
1414*cb14a3feSDimitry Andric        __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
14150b57cec5SDimitry Andric    return __table_.__node_handle_merge_multi(__source.__table_);
14160b57cec5SDimitry Andric  }
14170b57cec5SDimitry Andric  template <class _H2, class _P2>
1418*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI void merge(unordered_set<key_type, _H2, _P2, allocator_type>&& __source) {
1419*cb14a3feSDimitry Andric    _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
1420*cb14a3feSDimitry Andric        __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
14210b57cec5SDimitry Andric    return __table_.__node_handle_merge_multi(__source.__table_);
14220b57cec5SDimitry Andric  }
14230b57cec5SDimitry Andric#endif
14240b57cec5SDimitry Andric
1425*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __p) { return __table_.erase(__p); }
1426*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI size_type erase(const key_type& __k) { return __table_.__erase_multi(__k); }
1427*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __first, const_iterator __last) {
1428*cb14a3feSDimitry Andric    return __table_.erase(__first, __last);
1429*cb14a3feSDimitry Andric  }
1430*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT { __table_.clear(); }
14310b57cec5SDimitry Andric
1432*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI void swap(unordered_multiset& __u) _NOEXCEPT_(__is_nothrow_swappable<__table>::value) {
1433*cb14a3feSDimitry Andric    __table_.swap(__u.__table_);
1434*cb14a3feSDimitry Andric  }
14350b57cec5SDimitry Andric
1436*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI hasher hash_function() const { return __table_.hash_function(); }
1437*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI key_equal key_eq() const { return __table_.key_eq(); }
14380b57cec5SDimitry Andric
1439*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI iterator find(const key_type& __k) { return __table_.find(__k); }
1440*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI const_iterator find(const key_type& __k) const { return __table_.find(__k); }
144106c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 20
1442*cb14a3feSDimitry Andric  template <class _K2,
1443*cb14a3feSDimitry Andric            enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr>
1444*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI iterator find(const _K2& __k) {
1445*cb14a3feSDimitry Andric    return __table_.find(__k);
1446*cb14a3feSDimitry Andric  }
1447*cb14a3feSDimitry Andric  template <class _K2,
1448*cb14a3feSDimitry Andric            enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr>
1449*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI const_iterator find(const _K2& __k) const {
1450*cb14a3feSDimitry Andric    return __table_.find(__k);
1451*cb14a3feSDimitry Andric  }
145206c3fb27SDimitry Andric#endif // _LIBCPP_STD_VER >= 20
1453349cc55cSDimitry Andric
1454*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI size_type count(const key_type& __k) const { return __table_.__count_multi(__k); }
145506c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 20
1456*cb14a3feSDimitry Andric  template <class _K2,
1457*cb14a3feSDimitry Andric            enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr>
1458*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI size_type count(const _K2& __k) const {
1459*cb14a3feSDimitry Andric    return __table_.__count_multi(__k);
1460*cb14a3feSDimitry Andric  }
146106c3fb27SDimitry Andric#endif // _LIBCPP_STD_VER >= 20
1462349cc55cSDimitry Andric
146306c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 20
1464*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI bool contains(const key_type& __k) const { return find(__k) != end(); }
1465e8d8bef9SDimitry Andric
1466*cb14a3feSDimitry Andric  template <class _K2,
1467*cb14a3feSDimitry Andric            enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr>
1468*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI bool contains(const _K2& __k) const {
1469*cb14a3feSDimitry Andric    return find(__k) != end();
1470*cb14a3feSDimitry Andric  }
147106c3fb27SDimitry Andric#endif // _LIBCPP_STD_VER >= 20
1472349cc55cSDimitry Andric
1473*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const key_type& __k) {
1474*cb14a3feSDimitry Andric    return __table_.__equal_range_multi(__k);
1475*cb14a3feSDimitry Andric  }
1476*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const key_type& __k) const {
1477*cb14a3feSDimitry Andric    return __table_.__equal_range_multi(__k);
1478*cb14a3feSDimitry Andric  }
147906c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 20
1480*cb14a3feSDimitry Andric  template <class _K2,
1481*cb14a3feSDimitry Andric            enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr>
1482*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const _K2& __k) {
1483*cb14a3feSDimitry Andric    return __table_.__equal_range_multi(__k);
1484*cb14a3feSDimitry Andric  }
1485*cb14a3feSDimitry Andric  template <class _K2,
1486*cb14a3feSDimitry Andric            enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr>
1487*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const _K2& __k) const {
1488*cb14a3feSDimitry Andric    return __table_.__equal_range_multi(__k);
1489*cb14a3feSDimitry Andric  }
149006c3fb27SDimitry Andric#endif // _LIBCPP_STD_VER >= 20
14910b57cec5SDimitry Andric
1492*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI size_type bucket_count() const _NOEXCEPT { return __table_.bucket_count(); }
1493*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI size_type max_bucket_count() const _NOEXCEPT { return __table_.max_bucket_count(); }
14940b57cec5SDimitry Andric
1495*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI size_type bucket_size(size_type __n) const { return __table_.bucket_size(__n); }
1496*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI size_type bucket(const key_type& __k) const { return __table_.bucket(__k); }
14970b57cec5SDimitry Andric
1498*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI local_iterator begin(size_type __n) { return __table_.begin(__n); }
1499*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI local_iterator end(size_type __n) { return __table_.end(__n); }
1500*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI const_local_iterator begin(size_type __n) const { return __table_.cbegin(__n); }
1501*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI const_local_iterator end(size_type __n) const { return __table_.cend(__n); }
1502*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI const_local_iterator cbegin(size_type __n) const { return __table_.cbegin(__n); }
1503*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI const_local_iterator cend(size_type __n) const { return __table_.cend(__n); }
15040b57cec5SDimitry Andric
1505*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI float load_factor() const _NOEXCEPT { return __table_.load_factor(); }
1506*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI float max_load_factor() const _NOEXCEPT { return __table_.max_load_factor(); }
1507*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI void max_load_factor(float __mlf) { __table_.max_load_factor(__mlf); }
1508*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI void rehash(size_type __n) { __table_.__rehash_multi(__n); }
1509*cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI void reserve(size_type __n) { __table_.__reserve_multi(__n); }
15100b57cec5SDimitry Andric};
15110b57cec5SDimitry Andric
1512349cc55cSDimitry Andric#if _LIBCPP_STD_VER >= 17
15130b57cec5SDimitry Andrictemplate <class _InputIterator,
15140b57cec5SDimitry Andric          class _Hash      = hash<__iter_value_type<_InputIterator>>,
15150b57cec5SDimitry Andric          class _Pred      = equal_to<__iter_value_type<_InputIterator>>,
15160b57cec5SDimitry Andric          class _Allocator = allocator<__iter_value_type<_InputIterator>>,
151706c3fb27SDimitry Andric          class            = enable_if_t<__has_input_iterator_category<_InputIterator>::value>,
1518349cc55cSDimitry Andric          class            = enable_if_t<!__is_allocator<_Hash>::value>,
1519349cc55cSDimitry Andric          class            = enable_if_t<!is_integral<_Hash>::value>,
1520349cc55cSDimitry Andric          class            = enable_if_t<!__is_allocator<_Pred>::value>,
1521349cc55cSDimitry Andric          class            = enable_if_t<__is_allocator<_Allocator>::value>>
1522*cb14a3feSDimitry Andricunordered_multiset(
1523*cb14a3feSDimitry Andric    _InputIterator,
1524*cb14a3feSDimitry Andric    _InputIterator,
1525*cb14a3feSDimitry Andric    typename allocator_traits<_Allocator>::size_type = 0,
1526*cb14a3feSDimitry Andric    _Hash                                            = _Hash(),
1527*cb14a3feSDimitry Andric    _Pred                                            = _Pred(),
1528*cb14a3feSDimitry Andric    _Allocator = _Allocator()) -> unordered_multiset<__iter_value_type<_InputIterator>, _Hash, _Pred, _Allocator>;
15290b57cec5SDimitry Andric
153006c3fb27SDimitry Andric#  if _LIBCPP_STD_VER >= 23
153106c3fb27SDimitry Andrictemplate <ranges::input_range _Range,
153206c3fb27SDimitry Andric          class _Hash      = hash<ranges::range_value_t<_Range>>,
153306c3fb27SDimitry Andric          class _Pred      = equal_to<ranges::range_value_t<_Range>>,
153406c3fb27SDimitry Andric          class _Allocator = allocator<ranges::range_value_t<_Range>>,
153506c3fb27SDimitry Andric          class            = enable_if_t<!__is_allocator<_Hash>::value>,
153606c3fb27SDimitry Andric          class            = enable_if_t<!is_integral<_Hash>::value>,
153706c3fb27SDimitry Andric          class            = enable_if_t<!__is_allocator<_Pred>::value>,
153806c3fb27SDimitry Andric          class            = enable_if_t<__is_allocator<_Allocator>::value>>
1539*cb14a3feSDimitry Andricunordered_multiset(
1540*cb14a3feSDimitry Andric    from_range_t,
1541*cb14a3feSDimitry Andric    _Range&&,
1542*cb14a3feSDimitry Andric    typename allocator_traits<_Allocator>::size_type = 0,
1543*cb14a3feSDimitry Andric    _Hash                                            = _Hash(),
1544*cb14a3feSDimitry Andric    _Pred                                            = _Pred(),
1545*cb14a3feSDimitry Andric    _Allocator = _Allocator()) -> unordered_multiset<ranges::range_value_t<_Range>, _Hash, _Pred, _Allocator>; // C++23
154606c3fb27SDimitry Andric#  endif
154706c3fb27SDimitry Andric
1548*cb14a3feSDimitry Andrictemplate <class _Tp,
1549*cb14a3feSDimitry Andric          class _Hash      = hash<_Tp>,
1550*cb14a3feSDimitry Andric          class _Pred      = equal_to<_Tp>,
1551*cb14a3feSDimitry Andric          class _Allocator = allocator<_Tp>,
1552349cc55cSDimitry Andric          class            = enable_if_t<!__is_allocator<_Hash>::value>,
1553349cc55cSDimitry Andric          class            = enable_if_t<!is_integral<_Hash>::value>,
1554349cc55cSDimitry Andric          class            = enable_if_t<!__is_allocator<_Pred>::value>,
1555349cc55cSDimitry Andric          class            = enable_if_t<__is_allocator<_Allocator>::value>>
1556*cb14a3feSDimitry Andricunordered_multiset(initializer_list<_Tp>,
1557*cb14a3feSDimitry Andric                   typename allocator_traits<_Allocator>::size_type = 0,
1558*cb14a3feSDimitry Andric                   _Hash                                            = _Hash(),
1559*cb14a3feSDimitry Andric                   _Pred                                            = _Pred(),
1560*cb14a3feSDimitry Andric                   _Allocator = _Allocator()) -> unordered_multiset<_Tp, _Hash, _Pred, _Allocator>;
15610b57cec5SDimitry Andric
1562*cb14a3feSDimitry Andrictemplate <class _InputIterator,
1563*cb14a3feSDimitry Andric          class _Allocator,
156406c3fb27SDimitry Andric          class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>,
1565349cc55cSDimitry Andric          class = enable_if_t<__is_allocator<_Allocator>::value>>
15660b57cec5SDimitry Andricunordered_multiset(_InputIterator, _InputIterator, typename allocator_traits<_Allocator>::size_type, _Allocator)
15670b57cec5SDimitry Andric    -> unordered_multiset<__iter_value_type<_InputIterator>,
15680b57cec5SDimitry Andric                          hash<__iter_value_type<_InputIterator>>,
15690b57cec5SDimitry Andric                          equal_to<__iter_value_type<_InputIterator>>,
15700b57cec5SDimitry Andric                          _Allocator>;
15710b57cec5SDimitry Andric
1572*cb14a3feSDimitry Andrictemplate <class _InputIterator,
1573*cb14a3feSDimitry Andric          class _Hash,
1574*cb14a3feSDimitry Andric          class _Allocator,
157506c3fb27SDimitry Andric          class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>,
1576349cc55cSDimitry Andric          class = enable_if_t<!__is_allocator<_Hash>::value>,
1577349cc55cSDimitry Andric          class = enable_if_t<!is_integral<_Hash>::value>,
1578349cc55cSDimitry Andric          class = enable_if_t<__is_allocator<_Allocator>::value>>
1579*cb14a3feSDimitry Andricunordered_multiset(_InputIterator, _InputIterator, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator)
1580*cb14a3feSDimitry Andric    -> unordered_multiset<__iter_value_type<_InputIterator>,
1581*cb14a3feSDimitry Andric                          _Hash,
15820b57cec5SDimitry Andric                          equal_to<__iter_value_type<_InputIterator>>,
15830b57cec5SDimitry Andric                          _Allocator>;
15840b57cec5SDimitry Andric
158506c3fb27SDimitry Andric#  if _LIBCPP_STD_VER >= 23
158606c3fb27SDimitry Andric
1587*cb14a3feSDimitry Andrictemplate <ranges::input_range _Range, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value>>
158806c3fb27SDimitry Andricunordered_multiset(from_range_t, _Range&&, typename allocator_traits<_Allocator>::size_type, _Allocator)
1589*cb14a3feSDimitry Andric    -> unordered_multiset<ranges::range_value_t<_Range>,
1590*cb14a3feSDimitry Andric                          hash<ranges::range_value_t<_Range>>,
1591*cb14a3feSDimitry Andric                          equal_to<ranges::range_value_t<_Range>>,
1592*cb14a3feSDimitry Andric                          _Allocator>;
159306c3fb27SDimitry Andric
1594*cb14a3feSDimitry Andrictemplate <ranges::input_range _Range, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value>>
159506c3fb27SDimitry Andricunordered_multiset(from_range_t, _Range&&, _Allocator)
1596*cb14a3feSDimitry Andric    -> unordered_multiset<ranges::range_value_t<_Range>,
1597*cb14a3feSDimitry Andric                          hash<ranges::range_value_t<_Range>>,
1598*cb14a3feSDimitry Andric                          equal_to<ranges::range_value_t<_Range>>,
1599*cb14a3feSDimitry Andric                          _Allocator>;
160006c3fb27SDimitry Andric
1601*cb14a3feSDimitry Andrictemplate <ranges::input_range _Range,
1602*cb14a3feSDimitry Andric          class _Hash,
1603*cb14a3feSDimitry Andric          class _Allocator,
160406c3fb27SDimitry Andric          class = enable_if_t<!__is_allocator<_Hash>::value>,
160506c3fb27SDimitry Andric          class = enable_if_t<!is_integral<_Hash>::value>,
160606c3fb27SDimitry Andric          class = enable_if_t<__is_allocator<_Allocator>::value>>
160706c3fb27SDimitry Andricunordered_multiset(from_range_t, _Range&&, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator)
160806c3fb27SDimitry Andric    -> unordered_multiset<ranges::range_value_t<_Range>, _Hash, equal_to<ranges::range_value_t<_Range>>, _Allocator>;
160906c3fb27SDimitry Andric
161006c3fb27SDimitry Andric#  endif
161106c3fb27SDimitry Andric
1612*cb14a3feSDimitry Andrictemplate <class _Tp, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value>>
16130b57cec5SDimitry Andricunordered_multiset(initializer_list<_Tp>, typename allocator_traits<_Allocator>::size_type, _Allocator)
16140b57cec5SDimitry Andric    -> unordered_multiset<_Tp, hash<_Tp>, equal_to<_Tp>, _Allocator>;
16150b57cec5SDimitry Andric
1616*cb14a3feSDimitry Andrictemplate <class _Tp,
1617*cb14a3feSDimitry Andric          class _Hash,
1618*cb14a3feSDimitry Andric          class _Allocator,
1619349cc55cSDimitry Andric          class = enable_if_t<!__is_allocator<_Hash>::value>,
1620349cc55cSDimitry Andric          class = enable_if_t<!is_integral<_Hash>::value>,
1621349cc55cSDimitry Andric          class = enable_if_t<__is_allocator<_Allocator>::value>>
16220b57cec5SDimitry Andricunordered_multiset(initializer_list<_Tp>, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator)
16230b57cec5SDimitry Andric    -> unordered_multiset<_Tp, _Hash, equal_to<_Tp>, _Allocator>;
16240b57cec5SDimitry Andric#endif
16250b57cec5SDimitry Andric
16260b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc>
16270b57cec5SDimitry Andricunordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
16280b57cec5SDimitry Andric    size_type __n, const hasher& __hf, const key_equal& __eql)
1629*cb14a3feSDimitry Andric    : __table_(__hf, __eql) {
1630753f127fSDimitry Andric  __table_.__rehash_multi(__n);
16310b57cec5SDimitry Andric}
16320b57cec5SDimitry Andric
16330b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc>
16340b57cec5SDimitry Andricunordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1635*cb14a3feSDimitry Andric    size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
1636*cb14a3feSDimitry Andric    : __table_(__hf, __eql, __a) {
1637*cb14a3feSDimitry Andric  __table_.__rehash_multi(__n);
1638*cb14a3feSDimitry Andric}
1639*cb14a3feSDimitry Andric
1640*cb14a3feSDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc>
1641*cb14a3feSDimitry Andrictemplate <class _InputIterator>
1642*cb14a3feSDimitry Andricunordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(_InputIterator __first, _InputIterator __last) {
1643*cb14a3feSDimitry Andric  insert(__first, __last);
1644*cb14a3feSDimitry Andric}
1645*cb14a3feSDimitry Andric
1646*cb14a3feSDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc>
1647*cb14a3feSDimitry Andrictemplate <class _InputIterator>
1648*cb14a3feSDimitry Andricunordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1649*cb14a3feSDimitry Andric    _InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, const key_equal& __eql)
1650*cb14a3feSDimitry Andric    : __table_(__hf, __eql) {
1651*cb14a3feSDimitry Andric  __table_.__rehash_multi(__n);
1652*cb14a3feSDimitry Andric  insert(__first, __last);
1653*cb14a3feSDimitry Andric}
1654*cb14a3feSDimitry Andric
1655*cb14a3feSDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc>
1656*cb14a3feSDimitry Andrictemplate <class _InputIterator>
1657*cb14a3feSDimitry Andricunordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1658*cb14a3feSDimitry Andric    _InputIterator __first,
1659*cb14a3feSDimitry Andric    _InputIterator __last,
1660*cb14a3feSDimitry Andric    size_type __n,
1661*cb14a3feSDimitry Andric    const hasher& __hf,
1662*cb14a3feSDimitry Andric    const key_equal& __eql,
16630b57cec5SDimitry Andric    const allocator_type& __a)
1664*cb14a3feSDimitry Andric    : __table_(__hf, __eql, __a) {
1665753f127fSDimitry Andric  __table_.__rehash_multi(__n);
16660b57cec5SDimitry Andric  insert(__first, __last);
16670b57cec5SDimitry Andric}
16680b57cec5SDimitry Andric
16690b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc>
1670*cb14a3feSDimitry Andricinline unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(const allocator_type& __a)
1671*cb14a3feSDimitry Andric    : __table_(__a) {}
16720b57cec5SDimitry Andric
16730b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc>
1674*cb14a3feSDimitry Andricunordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(const unordered_multiset& __u)
1675*cb14a3feSDimitry Andric    : __table_(__u.__table_) {
1676753f127fSDimitry Andric  __table_.__rehash_multi(__u.bucket_count());
16770b57cec5SDimitry Andric  insert(__u.begin(), __u.end());
16780b57cec5SDimitry Andric}
16790b57cec5SDimitry Andric
16800b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc>
16810b57cec5SDimitry Andricunordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
16820b57cec5SDimitry Andric    const unordered_multiset& __u, const allocator_type& __a)
1683*cb14a3feSDimitry Andric    : __table_(__u.__table_, __a) {
1684753f127fSDimitry Andric  __table_.__rehash_multi(__u.bucket_count());
16850b57cec5SDimitry Andric  insert(__u.begin(), __u.end());
16860b57cec5SDimitry Andric}
16870b57cec5SDimitry Andric
16880b57cec5SDimitry Andric#ifndef _LIBCPP_CXX03_LANG
16890b57cec5SDimitry Andric
16900b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc>
1691*cb14a3feSDimitry Andricinline unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(unordered_multiset&& __u)
16920b57cec5SDimitry Andric    _NOEXCEPT_(is_nothrow_move_constructible<__table>::value)
1693*cb14a3feSDimitry Andric    : __table_(std::move(__u.__table_)) {}
16940b57cec5SDimitry Andric
16950b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc>
16960b57cec5SDimitry Andricunordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
16970b57cec5SDimitry Andric    unordered_multiset&& __u, const allocator_type& __a)
1698*cb14a3feSDimitry Andric    : __table_(std::move(__u.__table_), __a) {
1699*cb14a3feSDimitry Andric  if (__a != __u.get_allocator()) {
17000b57cec5SDimitry Andric    iterator __i = __u.begin();
17010b57cec5SDimitry Andric    while (__u.size() != 0)
17025f757f3fSDimitry Andric      __table_.__insert_multi(std::move(__u.__table_.remove(__i++)->__get_value()));
17030b57cec5SDimitry Andric  }
17040b57cec5SDimitry Andric}
17050b57cec5SDimitry Andric
17060b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc>
1707*cb14a3feSDimitry Andricunordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(initializer_list<value_type> __il) {
17080b57cec5SDimitry Andric  insert(__il.begin(), __il.end());
17090b57cec5SDimitry Andric}
17100b57cec5SDimitry Andric
17110b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc>
17120b57cec5SDimitry Andricunordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1713*cb14a3feSDimitry Andric    initializer_list<value_type> __il, size_type __n, const hasher& __hf, const key_equal& __eql)
1714*cb14a3feSDimitry Andric    : __table_(__hf, __eql) {
1715753f127fSDimitry Andric  __table_.__rehash_multi(__n);
17160b57cec5SDimitry Andric  insert(__il.begin(), __il.end());
17170b57cec5SDimitry Andric}
17180b57cec5SDimitry Andric
17190b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc>
17200b57cec5SDimitry Andricunordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1721*cb14a3feSDimitry Andric    initializer_list<value_type> __il,
1722*cb14a3feSDimitry Andric    size_type __n,
1723*cb14a3feSDimitry Andric    const hasher& __hf,
1724*cb14a3feSDimitry Andric    const key_equal& __eql,
1725*cb14a3feSDimitry Andric    const allocator_type& __a)
1726*cb14a3feSDimitry Andric    : __table_(__hf, __eql, __a) {
1727753f127fSDimitry Andric  __table_.__rehash_multi(__n);
17280b57cec5SDimitry Andric  insert(__il.begin(), __il.end());
17290b57cec5SDimitry Andric}
17300b57cec5SDimitry Andric
17310b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc>
1732*cb14a3feSDimitry Andricinline unordered_multiset<_Value, _Hash, _Pred, _Alloc>&
1733*cb14a3feSDimitry Andricunordered_multiset<_Value, _Hash, _Pred, _Alloc>::operator=(unordered_multiset&& __u)
1734*cb14a3feSDimitry Andric    _NOEXCEPT_(is_nothrow_move_assignable<__table>::value) {
17355f757f3fSDimitry Andric  __table_ = std::move(__u.__table_);
17360b57cec5SDimitry Andric  return *this;
17370b57cec5SDimitry Andric}
17380b57cec5SDimitry Andric
17390b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc>
1740*cb14a3feSDimitry Andricinline unordered_multiset<_Value, _Hash, _Pred, _Alloc>&
1741*cb14a3feSDimitry Andricunordered_multiset<_Value, _Hash, _Pred, _Alloc>::operator=(initializer_list<value_type> __il) {
17420b57cec5SDimitry Andric  __table_.__assign_multi(__il.begin(), __il.end());
17430b57cec5SDimitry Andric  return *this;
17440b57cec5SDimitry Andric}
17450b57cec5SDimitry Andric
17460b57cec5SDimitry Andric#endif // _LIBCPP_CXX03_LANG
17470b57cec5SDimitry Andric
17480b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc>
17490b57cec5SDimitry Andrictemplate <class _InputIterator>
1750*cb14a3feSDimitry Andricinline void unordered_multiset<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, _InputIterator __last) {
17510b57cec5SDimitry Andric  for (; __first != __last; ++__first)
17520b57cec5SDimitry Andric    __table_.__insert_multi(*__first);
17530b57cec5SDimitry Andric}
17540b57cec5SDimitry Andric
17550b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc>
1756*cb14a3feSDimitry Andricinline _LIBCPP_HIDE_FROM_ABI void
1757*cb14a3feSDimitry Andricswap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1758*cb14a3feSDimitry Andric    _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) {
17590b57cec5SDimitry Andric  __x.swap(__y);
17600b57cec5SDimitry Andric}
17610b57cec5SDimitry Andric
176206c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 20
1763*cb14a3feSDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc, class _Predicate>
1764*cb14a3feSDimitry Andricinline _LIBCPP_HIDE_FROM_ABI typename unordered_multiset<_Value, _Hash, _Pred, _Alloc>::size_type
1765*cb14a3feSDimitry Andricerase_if(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __c, _Predicate __pred) {
17665f757f3fSDimitry Andric  return std::__libcpp_erase_if_container(__c, __pred);
17675ffd83dbSDimitry Andric}
17680b57cec5SDimitry Andric#endif
17690b57cec5SDimitry Andric
17700b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc>
1771*cb14a3feSDimitry Andric_LIBCPP_HIDE_FROM_ABI bool operator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1772*cb14a3feSDimitry Andric                                      const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) {
17730b57cec5SDimitry Andric  if (__x.size() != __y.size())
17740b57cec5SDimitry Andric    return false;
1775*cb14a3feSDimitry Andric  typedef typename unordered_multiset<_Value, _Hash, _Pred, _Alloc>::const_iterator const_iterator;
17760b57cec5SDimitry Andric  typedef pair<const_iterator, const_iterator> _EqRng;
1777*cb14a3feSDimitry Andric  for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;) {
17780b57cec5SDimitry Andric    _EqRng __xeq = __x.equal_range(*__i);
17790b57cec5SDimitry Andric    _EqRng __yeq = __y.equal_range(*__i);
1780*cb14a3feSDimitry Andric    if (std::distance(__xeq.first, __xeq.second) != std::distance(__yeq.first, __yeq.second) ||
17815f757f3fSDimitry Andric        !std::is_permutation(__xeq.first, __xeq.second, __yeq.first))
17820b57cec5SDimitry Andric      return false;
17830b57cec5SDimitry Andric    __i = __xeq.second;
17840b57cec5SDimitry Andric  }
17850b57cec5SDimitry Andric  return true;
17860b57cec5SDimitry Andric}
17870b57cec5SDimitry Andric
178806c3fb27SDimitry Andric#if _LIBCPP_STD_VER <= 17
178906c3fb27SDimitry Andric
17900b57cec5SDimitry Andrictemplate <class _Value, class _Hash, class _Pred, class _Alloc>
1791*cb14a3feSDimitry Andricinline _LIBCPP_HIDE_FROM_ABI bool operator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1792*cb14a3feSDimitry Andric                                             const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) {
17930b57cec5SDimitry Andric  return !(__x == __y);
17940b57cec5SDimitry Andric}
17950b57cec5SDimitry Andric
179606c3fb27SDimitry Andric#endif
179706c3fb27SDimitry Andric
17980b57cec5SDimitry Andric_LIBCPP_END_NAMESPACE_STD
17990b57cec5SDimitry Andric
180006c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 17
1801bdd1243dSDimitry Andric_LIBCPP_BEGIN_NAMESPACE_STD
1802bdd1243dSDimitry Andricnamespace pmr {
1803bdd1243dSDimitry Andrictemplate <class _KeyT, class _HashT = std::hash<_KeyT>, class _PredT = std::equal_to<_KeyT>>
180406c3fb27SDimitry Andricusing unordered_set _LIBCPP_AVAILABILITY_PMR = std::unordered_set<_KeyT, _HashT, _PredT, polymorphic_allocator<_KeyT>>;
1805bdd1243dSDimitry Andric
1806bdd1243dSDimitry Andrictemplate <class _KeyT, class _HashT = std::hash<_KeyT>, class _PredT = std::equal_to<_KeyT>>
1807*cb14a3feSDimitry Andricusing unordered_multiset _LIBCPP_AVAILABILITY_PMR =
1808*cb14a3feSDimitry Andric    std::unordered_multiset<_KeyT, _HashT, _PredT, polymorphic_allocator<_KeyT>>;
1809bdd1243dSDimitry Andric} // namespace pmr
1810bdd1243dSDimitry Andric_LIBCPP_END_NAMESPACE_STD
1811bdd1243dSDimitry Andric#endif
1812bdd1243dSDimitry Andric
1813bdd1243dSDimitry Andric#if !defined(_LIBCPP_REMOVE_TRANSITIVE_INCLUDES) && _LIBCPP_STD_VER <= 20
1814bdd1243dSDimitry Andric#  include <concepts>
181506c3fb27SDimitry Andric#  include <cstdlib>
1816bdd1243dSDimitry Andric#  include <functional>
1817bdd1243dSDimitry Andric#  include <iterator>
18185f757f3fSDimitry Andric#  include <stdexcept>
181906c3fb27SDimitry Andric#  include <type_traits>
1820bdd1243dSDimitry Andric#endif
1821bdd1243dSDimitry Andric
18220b57cec5SDimitry Andric#endif // _LIBCPP_UNORDERED_SET
1823