xref: /freebsd/contrib/llvm-project/libcxx/include/unordered_map (revision b3edf4467982447620505a28fc82e38a414c07dc)
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_MAP
110b57cec5SDimitry Andric#define _LIBCPP_UNORDERED_MAP
120b57cec5SDimitry Andric
130b57cec5SDimitry Andric/*
140b57cec5SDimitry Andric
150b57cec5SDimitry Andric    unordered_map synopsis
160b57cec5SDimitry Andric
170b57cec5SDimitry Andric#include <initializer_list>
180b57cec5SDimitry Andric
190b57cec5SDimitry Andricnamespace std
200b57cec5SDimitry Andric{
210b57cec5SDimitry Andric
220b57cec5SDimitry Andrictemplate <class Key, class T, class Hash = hash<Key>, class Pred = equal_to<Key>,
230b57cec5SDimitry Andric          class Alloc = allocator<pair<const Key, T>>>
240b57cec5SDimitry Andricclass unordered_map
250b57cec5SDimitry Andric{
260b57cec5SDimitry Andricpublic:
270b57cec5SDimitry Andric    // types
280b57cec5SDimitry Andric    typedef Key                                                        key_type;
290b57cec5SDimitry Andric    typedef T                                                          mapped_type;
300b57cec5SDimitry Andric    typedef Hash                                                       hasher;
310b57cec5SDimitry Andric    typedef Pred                                                       key_equal;
320b57cec5SDimitry Andric    typedef Alloc                                                      allocator_type;
330b57cec5SDimitry Andric    typedef pair<const key_type, mapped_type>                          value_type;
340b57cec5SDimitry Andric    typedef value_type&                                                reference;
350b57cec5SDimitry Andric    typedef const value_type&                                          const_reference;
360b57cec5SDimitry Andric    typedef typename allocator_traits<allocator_type>::pointer         pointer;
370b57cec5SDimitry Andric    typedef typename allocator_traits<allocator_type>::const_pointer   const_pointer;
380b57cec5SDimitry Andric    typedef typename allocator_traits<allocator_type>::size_type       size_type;
390b57cec5SDimitry Andric    typedef typename allocator_traits<allocator_type>::difference_type difference_type;
400b57cec5SDimitry Andric
410b57cec5SDimitry Andric    typedef /unspecified/ iterator;
420b57cec5SDimitry Andric    typedef /unspecified/ const_iterator;
430b57cec5SDimitry Andric    typedef /unspecified/ local_iterator;
440b57cec5SDimitry Andric    typedef /unspecified/ const_local_iterator;
450b57cec5SDimitry Andric
460b57cec5SDimitry Andric    typedef unspecified                             node_type;            // C++17
470b57cec5SDimitry Andric    typedef INSERT_RETURN_TYPE<iterator, node_type> insert_return_type;   // C++17
480b57cec5SDimitry Andric
490b57cec5SDimitry Andric    unordered_map()
500b57cec5SDimitry Andric        noexcept(
510b57cec5SDimitry Andric            is_nothrow_default_constructible<hasher>::value &&
520b57cec5SDimitry Andric            is_nothrow_default_constructible<key_equal>::value &&
530b57cec5SDimitry Andric            is_nothrow_default_constructible<allocator_type>::value);
540b57cec5SDimitry Andric    explicit unordered_map(size_type n, const hasher& hf = hasher(),
550b57cec5SDimitry Andric                           const key_equal& eql = key_equal(),
560b57cec5SDimitry Andric                           const allocator_type& a = allocator_type());
570b57cec5SDimitry Andric    template <class InputIterator>
580b57cec5SDimitry Andric        unordered_map(InputIterator f, InputIterator l,
590b57cec5SDimitry Andric                      size_type n = 0, const hasher& hf = hasher(),
600b57cec5SDimitry Andric                      const key_equal& eql = key_equal(),
610b57cec5SDimitry Andric                      const allocator_type& a = allocator_type());
6206c3fb27SDimitry Andric    template<container-compatible-range<value_type> R>
6306c3fb27SDimitry Andric      unordered_map(from_range_t, R&& rg, size_type n = see below,
6406c3fb27SDimitry Andric        const hasher& hf = hasher(), const key_equal& eql = key_equal(),
6506c3fb27SDimitry Andric        const allocator_type& a = allocator_type()); // C++23
6606c3fb27SDimitry Andric
670b57cec5SDimitry Andric    explicit unordered_map(const allocator_type&);
680b57cec5SDimitry Andric    unordered_map(const unordered_map&);
690b57cec5SDimitry Andric    unordered_map(const unordered_map&, const Allocator&);
700b57cec5SDimitry Andric    unordered_map(unordered_map&&)
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_map(unordered_map&&, const Allocator&);
760b57cec5SDimitry Andric    unordered_map(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_map(size_type n, const allocator_type& a)
800b57cec5SDimitry Andric      : unordered_map(n, hasher(), key_equal(), a) {}  // C++14
810b57cec5SDimitry Andric    unordered_map(size_type n, const hasher& hf, const allocator_type& a)
820b57cec5SDimitry Andric      : unordered_map(n, hf, key_equal(), a) {}  // C++14
830b57cec5SDimitry Andric    template <class InputIterator>
840b57cec5SDimitry Andric      unordered_map(InputIterator f, InputIterator l, size_type n, const allocator_type& a)
850b57cec5SDimitry Andric      : unordered_map(f, l, n, hasher(), key_equal(), a) {}  // C++14
860b57cec5SDimitry Andric    template <class InputIterator>
870b57cec5SDimitry Andric      unordered_map(InputIterator f, InputIterator l, size_type n, const hasher& hf,
880b57cec5SDimitry Andric        const allocator_type& a)
890b57cec5SDimitry Andric      : unordered_map(f, l, n, hf, key_equal(), a) {}  // C++14
9006c3fb27SDimitry Andric    template<container-compatible-range<value_type> R>
9106c3fb27SDimitry Andric      unordered_map(from_range_t, R&& rg, size_type n, const allocator_type& a)
9206c3fb27SDimitry Andric        : unordered_map(from_range, std::forward<R>(rg), n, hasher(), key_equal(), a) { } // C++23
9306c3fb27SDimitry Andric    template<container-compatible-range<value_type> R>
9406c3fb27SDimitry Andric      unordered_map(from_range_t, R&& rg, size_type n, const hasher& hf, const allocator_type& a)
9506c3fb27SDimitry Andric        : unordered_map(from_range, std::forward<R>(rg), n, hf, key_equal(), a) { }       // C++23
960b57cec5SDimitry Andric    unordered_map(initializer_list<value_type> il, size_type n, const allocator_type& a)
970b57cec5SDimitry Andric      : unordered_map(il, n, hasher(), key_equal(), a) {}  // C++14
980b57cec5SDimitry Andric    unordered_map(initializer_list<value_type> il, size_type n, const hasher& hf,
990b57cec5SDimitry Andric      const allocator_type& a)
1000b57cec5SDimitry Andric      : unordered_map(il, n, hf, key_equal(), a) {}  // C++14
1010b57cec5SDimitry Andric    ~unordered_map();
1020b57cec5SDimitry Andric    unordered_map& operator=(const unordered_map&);
1030b57cec5SDimitry Andric    unordered_map& operator=(unordered_map&&)
1040b57cec5SDimitry Andric        noexcept(
1050b57cec5SDimitry Andric            allocator_type::propagate_on_container_move_assignment::value &&
1060b57cec5SDimitry Andric            is_nothrow_move_assignable<allocator_type>::value &&
1070b57cec5SDimitry Andric            is_nothrow_move_assignable<hasher>::value &&
1080b57cec5SDimitry Andric            is_nothrow_move_assignable<key_equal>::value);
1090b57cec5SDimitry Andric    unordered_map& operator=(initializer_list<value_type>);
1100b57cec5SDimitry Andric
1110b57cec5SDimitry Andric    allocator_type get_allocator() const noexcept;
1120b57cec5SDimitry Andric
1130b57cec5SDimitry Andric    bool      empty() const noexcept;
1140b57cec5SDimitry Andric    size_type size() const noexcept;
1150b57cec5SDimitry Andric    size_type max_size() const noexcept;
1160b57cec5SDimitry Andric
1170b57cec5SDimitry Andric    iterator       begin() noexcept;
1180b57cec5SDimitry Andric    iterator       end() noexcept;
1190b57cec5SDimitry Andric    const_iterator begin()  const noexcept;
1200b57cec5SDimitry Andric    const_iterator end()    const noexcept;
1210b57cec5SDimitry Andric    const_iterator cbegin() const noexcept;
1220b57cec5SDimitry Andric    const_iterator cend()   const noexcept;
1230b57cec5SDimitry Andric
1240b57cec5SDimitry Andric    template <class... Args>
1250b57cec5SDimitry Andric        pair<iterator, bool> emplace(Args&&... args);
1260b57cec5SDimitry Andric    template <class... Args>
1270b57cec5SDimitry Andric        iterator emplace_hint(const_iterator position, Args&&... args);
1280b57cec5SDimitry Andric    pair<iterator, bool> insert(const value_type& obj);
1290b57cec5SDimitry Andric    template <class P>
1300b57cec5SDimitry Andric        pair<iterator, bool> insert(P&& obj);
1310b57cec5SDimitry Andric    iterator insert(const_iterator hint, const value_type& obj);
1320b57cec5SDimitry Andric    template <class P>
1330b57cec5SDimitry Andric        iterator insert(const_iterator hint, P&& obj);
1340b57cec5SDimitry Andric    template <class InputIterator>
1350b57cec5SDimitry Andric        void insert(InputIterator first, InputIterator last);
13606c3fb27SDimitry Andric    template<container-compatible-range<value_type> R>
13706c3fb27SDimitry Andric      void insert_range(R&& rg);                                                      // C++23
1380b57cec5SDimitry Andric    void insert(initializer_list<value_type>);
1390b57cec5SDimitry Andric
1400b57cec5SDimitry Andric    node_type extract(const_iterator position);                                       // C++17
1410b57cec5SDimitry Andric    node_type extract(const key_type& x);                                             // C++17
1420b57cec5SDimitry Andric    insert_return_type insert(node_type&& nh);                                        // C++17
1430b57cec5SDimitry Andric    iterator           insert(const_iterator hint, node_type&& nh);                   // C++17
1440b57cec5SDimitry Andric
1450b57cec5SDimitry Andric    template <class... Args>
1460b57cec5SDimitry Andric        pair<iterator, bool> try_emplace(const key_type& k, Args&&... args);          // C++17
1470b57cec5SDimitry Andric    template <class... Args>
1480b57cec5SDimitry Andric        pair<iterator, bool> try_emplace(key_type&& k, Args&&... args);               // C++17
1490b57cec5SDimitry Andric    template <class... Args>
1500b57cec5SDimitry Andric        iterator try_emplace(const_iterator hint, const key_type& k, Args&&... args); // C++17
1510b57cec5SDimitry Andric    template <class... Args>
1520b57cec5SDimitry Andric        iterator try_emplace(const_iterator hint, key_type&& k, Args&&... args);      // C++17
1530b57cec5SDimitry Andric    template <class M>
1540b57cec5SDimitry Andric        pair<iterator, bool> insert_or_assign(const key_type& k, M&& obj);            // C++17
1550b57cec5SDimitry Andric    template <class M>
1560b57cec5SDimitry Andric        pair<iterator, bool> insert_or_assign(key_type&& k, M&& obj);                 // C++17
1570b57cec5SDimitry Andric    template <class M>
1580b57cec5SDimitry Andric        iterator insert_or_assign(const_iterator hint, const key_type& k, M&& obj);   // C++17
1590b57cec5SDimitry Andric    template <class M>
1600b57cec5SDimitry Andric        iterator insert_or_assign(const_iterator hint, key_type&& k, M&& obj);        // C++17
1610b57cec5SDimitry Andric
1620b57cec5SDimitry Andric    iterator erase(const_iterator position);
1630b57cec5SDimitry Andric    iterator erase(iterator position);  // C++14
1640b57cec5SDimitry Andric    size_type erase(const key_type& k);
1650b57cec5SDimitry Andric    iterator erase(const_iterator first, const_iterator last);
1660b57cec5SDimitry Andric    void clear() noexcept;
1670b57cec5SDimitry Andric
1680b57cec5SDimitry Andric    template<class H2, class P2>
1690b57cec5SDimitry Andric      void merge(unordered_map<Key, T, H2, P2, Allocator>& source);         // C++17
1700b57cec5SDimitry Andric    template<class H2, class P2>
1710b57cec5SDimitry Andric      void merge(unordered_map<Key, T, H2, P2, Allocator>&& source);        // C++17
1720b57cec5SDimitry Andric    template<class H2, class P2>
1730b57cec5SDimitry Andric      void merge(unordered_multimap<Key, T, H2, P2, Allocator>& source);    // C++17
1740b57cec5SDimitry Andric    template<class H2, class P2>
1750b57cec5SDimitry Andric      void merge(unordered_multimap<Key, T, H2, P2, Allocator>&& source);   // C++17
1760b57cec5SDimitry Andric
1770b57cec5SDimitry Andric    void swap(unordered_map&)
1780b57cec5SDimitry Andric        noexcept(
1790b57cec5SDimitry Andric            (!allocator_type::propagate_on_container_swap::value ||
1800b57cec5SDimitry Andric             __is_nothrow_swappable<allocator_type>::value) &&
1810b57cec5SDimitry Andric            __is_nothrow_swappable<hasher>::value &&
1820b57cec5SDimitry Andric            __is_nothrow_swappable<key_equal>::value);
1830b57cec5SDimitry Andric
1840b57cec5SDimitry Andric    hasher hash_function() const;
1850b57cec5SDimitry Andric    key_equal key_eq() const;
1860b57cec5SDimitry Andric
1870b57cec5SDimitry Andric    iterator       find(const key_type& k);
1880b57cec5SDimitry Andric    const_iterator find(const key_type& k) const;
189e8d8bef9SDimitry Andric    template<typename K>
190e8d8bef9SDimitry Andric        iterator find(const K& x);              // C++20
191e8d8bef9SDimitry Andric    template<typename K>
192e8d8bef9SDimitry Andric        const_iterator find(const K& x) const;  // C++20
1930b57cec5SDimitry Andric    size_type count(const key_type& k) const;
194e8d8bef9SDimitry Andric    template<typename K>
195e8d8bef9SDimitry Andric        size_type count(const K& k) const; // C++20
1960b57cec5SDimitry Andric    bool contains(const key_type& k) const; // C++20
197e8d8bef9SDimitry Andric    template<typename K>
198e8d8bef9SDimitry Andric        bool contains(const K& k) const; // C++20
1990b57cec5SDimitry Andric    pair<iterator, iterator>             equal_range(const key_type& k);
2000b57cec5SDimitry Andric    pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
201e8d8bef9SDimitry Andric    template<typename K>
202e8d8bef9SDimitry Andric        pair<iterator, iterator>             equal_range(const K& k); // C++20
203e8d8bef9SDimitry Andric    template<typename K>
204e8d8bef9SDimitry Andric        pair<const_iterator, const_iterator> equal_range(const K& k) const; // C++20
2050b57cec5SDimitry Andric
2060b57cec5SDimitry Andric    mapped_type& operator[](const key_type& k);
2070b57cec5SDimitry Andric    mapped_type& operator[](key_type&& k);
2080b57cec5SDimitry Andric
2090b57cec5SDimitry Andric    mapped_type&       at(const key_type& k);
2100b57cec5SDimitry Andric    const mapped_type& at(const key_type& k) const;
2110b57cec5SDimitry Andric
2120b57cec5SDimitry Andric    size_type bucket_count() const noexcept;
2130b57cec5SDimitry Andric    size_type max_bucket_count() const noexcept;
2140b57cec5SDimitry Andric
2150b57cec5SDimitry Andric    size_type bucket_size(size_type n) const;
2160b57cec5SDimitry Andric    size_type bucket(const key_type& k) const;
2170b57cec5SDimitry Andric
2180b57cec5SDimitry Andric    local_iterator       begin(size_type n);
2190b57cec5SDimitry Andric    local_iterator       end(size_type n);
2200b57cec5SDimitry Andric    const_local_iterator begin(size_type n) const;
2210b57cec5SDimitry Andric    const_local_iterator end(size_type n) const;
2220b57cec5SDimitry Andric    const_local_iterator cbegin(size_type n) const;
2230b57cec5SDimitry Andric    const_local_iterator cend(size_type n) const;
2240b57cec5SDimitry Andric
2250b57cec5SDimitry Andric    float load_factor() const noexcept;
2260b57cec5SDimitry Andric    float max_load_factor() const noexcept;
2270b57cec5SDimitry Andric    void max_load_factor(float z);
2280b57cec5SDimitry Andric    void rehash(size_type n);
2290b57cec5SDimitry Andric    void reserve(size_type n);
2300b57cec5SDimitry Andric};
2310b57cec5SDimitry Andric
232349cc55cSDimitry Andrictemplate<class InputIterator,
233349cc55cSDimitry Andric    class Hash = hash<iter_key_t<InputIterator>>, class Pred = equal_to<iter_key_t<InputIterator>>,
234349cc55cSDimitry Andric    class Allocator = allocator<iter_to_alloc_t<InputIterator>>>
235349cc55cSDimitry Andricunordered_map(InputIterator, InputIterator, typename see below::size_type = see below,
236349cc55cSDimitry Andric    Hash = Hash(), Pred = Pred(), Allocator = Allocator())
237349cc55cSDimitry Andric  -> unordered_map<iter_key_t<InputIterator>, iter_value_t<InputIterator>, Hash, Pred,
238349cc55cSDimitry Andric    Allocator>; // C++17
239349cc55cSDimitry Andric
24006c3fb27SDimitry Andrictemplate<ranges::input_range R, class Hash = hash<range-key-type<R>>,
24106c3fb27SDimitry Andric         class Pred = equal_to<range-key-type<R>>,
24206c3fb27SDimitry Andric         class Allocator = allocator<range-to-alloc-type<R>>>
24306c3fb27SDimitry Andric  unordered_map(from_range_t, R&&, typename see below::size_type = see below,
24406c3fb27SDimitry Andric                Hash = Hash(), Pred = Pred(), Allocator = Allocator())
24506c3fb27SDimitry Andric    -> unordered_map<range-key-type<R>, range-mapped-type<R>, Hash, Pred, Allocator>; // C++23
24606c3fb27SDimitry Andric
247349cc55cSDimitry Andrictemplate<class Key, class T, class Hash = hash<Key>,
248349cc55cSDimitry Andric    class Pred = equal_to<Key>, class Allocator = allocator<pair<const Key, T>>>
249349cc55cSDimitry Andricunordered_map(initializer_list<pair<const Key, T>>, typename see below::size_type = see below,
250349cc55cSDimitry Andric    Hash = Hash(), Pred = Pred(), Allocator = Allocator())
251349cc55cSDimitry Andric  -> unordered_map<Key, T, Hash, Pred, Allocator>; // C++17
252349cc55cSDimitry Andric
253349cc55cSDimitry Andrictemplate<class InputIterator, class Allocator>
254349cc55cSDimitry Andricunordered_map(InputIterator, InputIterator, typename see below::size_type, Allocator)
255349cc55cSDimitry Andric  -> unordered_map<iter_key_t<InputIterator>, iter_val_t<InputIterator>,
256349cc55cSDimitry Andric        hash<iter_key_t<InputIterator>>, equal_to<iter_key_t<InputIterator>>, Allocator>; // C++17
257349cc55cSDimitry Andric
258349cc55cSDimitry Andrictemplate<class InputIterator, class Allocator>
259349cc55cSDimitry Andricunordered_map(InputIterator, InputIterator, Allocator)
260349cc55cSDimitry Andric  -> unordered_map<iter_key_t<InputIterator>, iter_val_t<InputIterator>,
261349cc55cSDimitry Andric        hash<iter_key_t<InputIterator>>, equal_to<iter_key_t<InputIterator>>, Allocator>; // C++17
262349cc55cSDimitry Andric
263349cc55cSDimitry Andrictemplate<class InputIterator, class Hash, class Allocator>
264349cc55cSDimitry Andricunordered_map(InputIterator, InputIterator, typename see below::size_type, Hash, Allocator)
265349cc55cSDimitry Andric  -> unordered_map<iter_key_t<InputIterator>, iter_val_t<InputIterator>, Hash,
266349cc55cSDimitry Andric          equal_to<iter_key_t<InputIterator>>, Allocator>; // C++17
267349cc55cSDimitry Andric
26806c3fb27SDimitry Andrictemplate<ranges::input_range R, class Allocator>
26906c3fb27SDimitry Andric  unordered_map(from_range_t, R&&, typename see below::size_type, Allocator)
27006c3fb27SDimitry Andric    -> unordered_map<range-key-type<R>, range-mapped-type<R>, hash<range-key-type<R>>,
27106c3fb27SDimitry Andric                      equal_to<range-key-type<R>>, Allocator>;   // C++23
27206c3fb27SDimitry Andric
27306c3fb27SDimitry Andrictemplate<ranges::input_range R, class Allocator>
27406c3fb27SDimitry Andric  unordered_map(from_range_t, R&&, Allocator)
27506c3fb27SDimitry Andric    -> unordered_map<range-key-type<R>, range-mapped-type<R>, hash<range-key-type<R>>,
27606c3fb27SDimitry Andric                      equal_to<range-key-type<R>>, Allocator>;   // C++23
27706c3fb27SDimitry Andric
27806c3fb27SDimitry Andrictemplate<ranges::input_range R, class Hash, class Allocator>
27906c3fb27SDimitry Andric  unordered_map(from_range_t, R&&, typename see below::size_type, Hash, Allocator)
28006c3fb27SDimitry Andric    -> unordered_map<range-key-type<R>, range-mapped-type<R>, Hash,
28106c3fb27SDimitry Andric                      equal_to<range-key-type<R>>, Allocator>;   // C++23
28206c3fb27SDimitry Andric
283349cc55cSDimitry Andrictemplate<class Key, class T, typename Allocator>
284349cc55cSDimitry Andricunordered_map(initializer_list<pair<const Key, T>>, typename see below::size_type, Allocator)
285349cc55cSDimitry Andric  -> unordered_map<Key, T, hash<Key>, equal_to<Key>, Allocator>; // C++17
286349cc55cSDimitry Andric
287349cc55cSDimitry Andrictemplate<class Key, class T, typename Allocator>
288349cc55cSDimitry Andricunordered_map(initializer_list<pair<const Key, T>>, Allocator)
289349cc55cSDimitry Andric  -> unordered_map<Key, T, hash<Key>, equal_to<Key>, Allocator>; // C++17
290349cc55cSDimitry Andric
291349cc55cSDimitry Andrictemplate<class Key, class T, class Hash, class Allocator>
292349cc55cSDimitry Andricunordered_map(initializer_list<pair<const Key, T>>, typename see below::size_type, Hash, Allocator)
293349cc55cSDimitry Andric  -> unordered_map<Key, T, Hash, equal_to<Key>, Allocator>; // C++17
294349cc55cSDimitry Andric
2950b57cec5SDimitry Andrictemplate <class Key, class T, class Hash, class Pred, class Alloc>
2960b57cec5SDimitry Andric    void swap(unordered_map<Key, T, Hash, Pred, Alloc>& x,
2970b57cec5SDimitry Andric              unordered_map<Key, T, Hash, Pred, Alloc>& y)
2980b57cec5SDimitry Andric              noexcept(noexcept(x.swap(y)));
2990b57cec5SDimitry Andric
3000b57cec5SDimitry Andrictemplate <class Key, class T, class Hash, class Pred, class Alloc>
3010b57cec5SDimitry Andric    bool
3020b57cec5SDimitry Andric    operator==(const unordered_map<Key, T, Hash, Pred, Alloc>& x,
3030b57cec5SDimitry Andric               const unordered_map<Key, T, Hash, Pred, Alloc>& y);
3040b57cec5SDimitry Andric
3050b57cec5SDimitry Andrictemplate <class Key, class T, class Hash, class Pred, class Alloc>
3060b57cec5SDimitry Andric    bool
3070b57cec5SDimitry Andric    operator!=(const unordered_map<Key, T, Hash, Pred, Alloc>& x,
30806c3fb27SDimitry Andric               const unordered_map<Key, T, Hash, Pred, Alloc>& y); // Removed in C++20
3090b57cec5SDimitry Andric
3100b57cec5SDimitry Andrictemplate <class Key, class T, class Hash = hash<Key>, class Pred = equal_to<Key>,
3110b57cec5SDimitry Andric          class Alloc = allocator<pair<const Key, T>>>
3120b57cec5SDimitry Andricclass unordered_multimap
3130b57cec5SDimitry Andric{
3140b57cec5SDimitry Andricpublic:
3150b57cec5SDimitry Andric    // types
3160b57cec5SDimitry Andric    typedef Key                                                        key_type;
3170b57cec5SDimitry Andric    typedef T                                                          mapped_type;
3180b57cec5SDimitry Andric    typedef Hash                                                       hasher;
3190b57cec5SDimitry Andric    typedef Pred                                                       key_equal;
3200b57cec5SDimitry Andric    typedef Alloc                                                      allocator_type;
3210b57cec5SDimitry Andric    typedef pair<const key_type, mapped_type>                          value_type;
3220b57cec5SDimitry Andric    typedef value_type&                                                reference;
3230b57cec5SDimitry Andric    typedef const value_type&                                          const_reference;
3240b57cec5SDimitry Andric    typedef typename allocator_traits<allocator_type>::pointer         pointer;
3250b57cec5SDimitry Andric    typedef typename allocator_traits<allocator_type>::const_pointer   const_pointer;
3260b57cec5SDimitry Andric    typedef typename allocator_traits<allocator_type>::size_type       size_type;
3270b57cec5SDimitry Andric    typedef typename allocator_traits<allocator_type>::difference_type difference_type;
3280b57cec5SDimitry Andric
3290b57cec5SDimitry Andric    typedef /unspecified/ iterator;
3300b57cec5SDimitry Andric    typedef /unspecified/ const_iterator;
3310b57cec5SDimitry Andric    typedef /unspecified/ local_iterator;
3320b57cec5SDimitry Andric    typedef /unspecified/ const_local_iterator;
3330b57cec5SDimitry Andric
3340b57cec5SDimitry Andric    typedef unspecified node_type;    // C++17
3350b57cec5SDimitry Andric
3360b57cec5SDimitry Andric    unordered_multimap()
3370b57cec5SDimitry Andric        noexcept(
3380b57cec5SDimitry Andric            is_nothrow_default_constructible<hasher>::value &&
3390b57cec5SDimitry Andric            is_nothrow_default_constructible<key_equal>::value &&
3400b57cec5SDimitry Andric            is_nothrow_default_constructible<allocator_type>::value);
3410b57cec5SDimitry Andric    explicit unordered_multimap(size_type n, const hasher& hf = hasher(),
3420b57cec5SDimitry Andric                           const key_equal& eql = key_equal(),
3430b57cec5SDimitry Andric                           const allocator_type& a = allocator_type());
3440b57cec5SDimitry Andric    template <class InputIterator>
3450b57cec5SDimitry Andric        unordered_multimap(InputIterator f, InputIterator l,
3460b57cec5SDimitry Andric                      size_type n = 0, const hasher& hf = hasher(),
3470b57cec5SDimitry Andric                      const key_equal& eql = key_equal(),
3480b57cec5SDimitry Andric                      const allocator_type& a = allocator_type());
34906c3fb27SDimitry Andric    template<container-compatible-range<value_type> R>
35006c3fb27SDimitry Andric      unordered_multimap(from_range_t, R&& rg, size_type n = see below,
35106c3fb27SDimitry Andric        const hasher& hf = hasher(), const key_equal& eql = key_equal(),
35206c3fb27SDimitry Andric        const allocator_type& a = allocator_type()); // C++23
3530b57cec5SDimitry Andric    explicit unordered_multimap(const allocator_type&);
3540b57cec5SDimitry Andric    unordered_multimap(const unordered_multimap&);
3550b57cec5SDimitry Andric    unordered_multimap(const unordered_multimap&, const Allocator&);
3560b57cec5SDimitry Andric    unordered_multimap(unordered_multimap&&)
3570b57cec5SDimitry Andric        noexcept(
3580b57cec5SDimitry Andric            is_nothrow_move_constructible<hasher>::value &&
3590b57cec5SDimitry Andric            is_nothrow_move_constructible<key_equal>::value &&
3600b57cec5SDimitry Andric            is_nothrow_move_constructible<allocator_type>::value);
3610b57cec5SDimitry Andric    unordered_multimap(unordered_multimap&&, const Allocator&);
3620b57cec5SDimitry Andric    unordered_multimap(initializer_list<value_type>, size_type n = 0,
3630b57cec5SDimitry Andric                  const hasher& hf = hasher(), const key_equal& eql = key_equal(),
3640b57cec5SDimitry Andric                  const allocator_type& a = allocator_type());
3650b57cec5SDimitry Andric    unordered_multimap(size_type n, const allocator_type& a)
3660b57cec5SDimitry Andric      : unordered_multimap(n, hasher(), key_equal(), a) {}  // C++14
3670b57cec5SDimitry Andric    unordered_multimap(size_type n, const hasher& hf, const allocator_type& a)
3680b57cec5SDimitry Andric      : unordered_multimap(n, hf, key_equal(), a) {}  // C++14
3690b57cec5SDimitry Andric    template <class InputIterator>
3700b57cec5SDimitry Andric      unordered_multimap(InputIterator f, InputIterator l, size_type n, const allocator_type& a)
3710b57cec5SDimitry Andric      : unordered_multimap(f, l, n, hasher(), key_equal(), a) {}  // C++14
3720b57cec5SDimitry Andric    template <class InputIterator>
3730b57cec5SDimitry Andric      unordered_multimap(InputIterator f, InputIterator l, size_type n, const hasher& hf,
3740b57cec5SDimitry Andric        const allocator_type& a)
3750b57cec5SDimitry Andric      : unordered_multimap(f, l, n, hf, key_equal(), a) {}  // C++14
37606c3fb27SDimitry Andric    template<container-compatible-range<value_type> R>
37706c3fb27SDimitry Andric      unordered_multimap(from_range_t, R&& rg, size_type n, const allocator_type& a)
37806c3fb27SDimitry Andric        : unordered_multimap(from_range, std::forward<R>(rg), n, hasher(), key_equal(), a) { } // C++23
37906c3fb27SDimitry Andric    template<container-compatible-range<value_type> R>
38006c3fb27SDimitry Andric      unordered_multimap(from_range_t, R&& rg, size_type n, const hasher& hf, const allocator_type& a)
38106c3fb27SDimitry Andric        : unordered_multimap(from_range, std::forward<R>(rg), n, hf, key_equal(), a) { }       // C++23
3820b57cec5SDimitry Andric    unordered_multimap(initializer_list<value_type> il, size_type n, const allocator_type& a)
3830b57cec5SDimitry Andric      : unordered_multimap(il, n, hasher(), key_equal(), a) {}  // C++14
3840b57cec5SDimitry Andric    unordered_multimap(initializer_list<value_type> il, size_type n, const hasher& hf,
3850b57cec5SDimitry Andric      const allocator_type& a)
3860b57cec5SDimitry Andric      : unordered_multimap(il, n, hf, key_equal(), a) {}  // C++14
3870b57cec5SDimitry Andric    ~unordered_multimap();
3880b57cec5SDimitry Andric    unordered_multimap& operator=(const unordered_multimap&);
3890b57cec5SDimitry Andric    unordered_multimap& operator=(unordered_multimap&&)
3900b57cec5SDimitry Andric        noexcept(
3910b57cec5SDimitry Andric            allocator_type::propagate_on_container_move_assignment::value &&
3920b57cec5SDimitry Andric            is_nothrow_move_assignable<allocator_type>::value &&
3930b57cec5SDimitry Andric            is_nothrow_move_assignable<hasher>::value &&
3940b57cec5SDimitry Andric            is_nothrow_move_assignable<key_equal>::value);
3950b57cec5SDimitry Andric    unordered_multimap& operator=(initializer_list<value_type>);
3960b57cec5SDimitry Andric
3970b57cec5SDimitry Andric    allocator_type get_allocator() const noexcept;
3980b57cec5SDimitry Andric
3990b57cec5SDimitry Andric    bool      empty() const noexcept;
4000b57cec5SDimitry Andric    size_type size() const noexcept;
4010b57cec5SDimitry Andric    size_type max_size() const noexcept;
4020b57cec5SDimitry Andric
4030b57cec5SDimitry Andric    iterator       begin() noexcept;
4040b57cec5SDimitry Andric    iterator       end() noexcept;
4050b57cec5SDimitry Andric    const_iterator begin()  const noexcept;
4060b57cec5SDimitry Andric    const_iterator end()    const noexcept;
4070b57cec5SDimitry Andric    const_iterator cbegin() const noexcept;
4080b57cec5SDimitry Andric    const_iterator cend()   const noexcept;
4090b57cec5SDimitry Andric
4100b57cec5SDimitry Andric    template <class... Args>
4110b57cec5SDimitry Andric        iterator emplace(Args&&... args);
4120b57cec5SDimitry Andric    template <class... Args>
4130b57cec5SDimitry Andric        iterator emplace_hint(const_iterator position, Args&&... args);
4140b57cec5SDimitry Andric    iterator insert(const value_type& obj);
4150b57cec5SDimitry Andric    template <class P>
4160b57cec5SDimitry Andric        iterator insert(P&& obj);
4170b57cec5SDimitry Andric    iterator insert(const_iterator hint, const value_type& obj);
4180b57cec5SDimitry Andric    template <class P>
4190b57cec5SDimitry Andric        iterator insert(const_iterator hint, P&& obj);
4200b57cec5SDimitry Andric    template <class InputIterator>
4210b57cec5SDimitry Andric        void insert(InputIterator first, InputIterator last);
42206c3fb27SDimitry Andric    template<container-compatible-range<value_type> R>
42306c3fb27SDimitry Andric      void insert_range(R&& rg);                               // C++23
4240b57cec5SDimitry Andric    void insert(initializer_list<value_type>);
4250b57cec5SDimitry Andric
4260b57cec5SDimitry Andric    node_type extract(const_iterator position);                // C++17
4270b57cec5SDimitry Andric    node_type extract(const key_type& x);                      // C++17
4280b57cec5SDimitry Andric    iterator insert(node_type&& nh);                           // C++17
4290b57cec5SDimitry Andric    iterator insert(const_iterator hint, node_type&& nh);      // C++17
4300b57cec5SDimitry Andric
4310b57cec5SDimitry Andric    iterator erase(const_iterator position);
4320b57cec5SDimitry Andric    iterator erase(iterator position);  // C++14
4330b57cec5SDimitry Andric    size_type erase(const key_type& k);
4340b57cec5SDimitry Andric    iterator erase(const_iterator first, const_iterator last);
4350b57cec5SDimitry Andric    void clear() noexcept;
4360b57cec5SDimitry Andric
4370b57cec5SDimitry Andric    template<class H2, class P2>
4380b57cec5SDimitry Andric      void merge(unordered_multimap<Key, T, H2, P2, Allocator>& source);    // C++17
4390b57cec5SDimitry Andric    template<class H2, class P2>
4400b57cec5SDimitry Andric      void merge(unordered_multimap<Key, T, H2, P2, Allocator>&& source);   // C++17
4410b57cec5SDimitry Andric    template<class H2, class P2>
4420b57cec5SDimitry Andric      void merge(unordered_map<Key, T, H2, P2, Allocator>& source);         // C++17
4430b57cec5SDimitry Andric    template<class H2, class P2>
4440b57cec5SDimitry Andric      void merge(unordered_map<Key, T, H2, P2, Allocator>&& source);        // C++17
4450b57cec5SDimitry Andric
4460b57cec5SDimitry Andric    void swap(unordered_multimap&)
4470b57cec5SDimitry Andric        noexcept(
4480b57cec5SDimitry Andric            (!allocator_type::propagate_on_container_swap::value ||
4490b57cec5SDimitry Andric             __is_nothrow_swappable<allocator_type>::value) &&
4500b57cec5SDimitry Andric            __is_nothrow_swappable<hasher>::value &&
4510b57cec5SDimitry Andric            __is_nothrow_swappable<key_equal>::value);
4520b57cec5SDimitry Andric
4530b57cec5SDimitry Andric    hasher hash_function() const;
4540b57cec5SDimitry Andric    key_equal key_eq() const;
4550b57cec5SDimitry Andric
4560b57cec5SDimitry Andric    iterator       find(const key_type& k);
4570b57cec5SDimitry Andric    const_iterator find(const key_type& k) const;
458e8d8bef9SDimitry Andric    template<typename K>
459e8d8bef9SDimitry Andric        iterator find(const K& x);              // C++20
460e8d8bef9SDimitry Andric    template<typename K>
461e8d8bef9SDimitry Andric        const_iterator find(const K& x) const;  // C++20
4620b57cec5SDimitry Andric    size_type count(const key_type& k) const;
463e8d8bef9SDimitry Andric    template<typename K>
464e8d8bef9SDimitry Andric        size_type count(const K& k) const; // C++20
4650b57cec5SDimitry Andric    bool contains(const key_type& k) const; // C++20
466e8d8bef9SDimitry Andric    template<typename K>
467e8d8bef9SDimitry Andric        bool contains(const K& k) const; // C++20
4680b57cec5SDimitry Andric    pair<iterator, iterator>             equal_range(const key_type& k);
4690b57cec5SDimitry Andric    pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
470e8d8bef9SDimitry Andric    template<typename K>
471e8d8bef9SDimitry Andric        pair<iterator, iterator>             equal_range(const K& k); // C++20
472e8d8bef9SDimitry Andric    template<typename K>
473e8d8bef9SDimitry Andric        pair<const_iterator, const_iterator> equal_range(const K& k) const; // C++20
4740b57cec5SDimitry Andric
4750b57cec5SDimitry Andric    size_type bucket_count() const noexcept;
4760b57cec5SDimitry Andric    size_type max_bucket_count() const noexcept;
4770b57cec5SDimitry Andric
4780b57cec5SDimitry Andric    size_type bucket_size(size_type n) const;
4790b57cec5SDimitry Andric    size_type bucket(const key_type& k) const;
4800b57cec5SDimitry Andric
4810b57cec5SDimitry Andric    local_iterator       begin(size_type n);
4820b57cec5SDimitry Andric    local_iterator       end(size_type n);
4830b57cec5SDimitry Andric    const_local_iterator begin(size_type n) const;
4840b57cec5SDimitry Andric    const_local_iterator end(size_type n) const;
4850b57cec5SDimitry Andric    const_local_iterator cbegin(size_type n) const;
4860b57cec5SDimitry Andric    const_local_iterator cend(size_type n) const;
4870b57cec5SDimitry Andric
4880b57cec5SDimitry Andric    float load_factor() const noexcept;
4890b57cec5SDimitry Andric    float max_load_factor() const noexcept;
4900b57cec5SDimitry Andric    void max_load_factor(float z);
4910b57cec5SDimitry Andric    void rehash(size_type n);
4920b57cec5SDimitry Andric    void reserve(size_type n);
4930b57cec5SDimitry Andric};
4940b57cec5SDimitry Andric
495349cc55cSDimitry Andrictemplate<class InputIterator,
496349cc55cSDimitry Andric    class Hash = hash<iter_key_t<InputIterator>>, class Pred = equal_to<iter_key_t<InputIterator>>,
497349cc55cSDimitry Andric    class Allocator = allocator<iter_to_alloc_t<InputIterator>>>
498349cc55cSDimitry Andricunordered_multimap(InputIterator, InputIterator, typename see below::size_type = see below,
499349cc55cSDimitry Andric    Hash = Hash(), Pred = Pred(), Allocator = Allocator())
500349cc55cSDimitry Andric  -> unordered_multimap<iter_key_t<InputIterator>, iter_value_t<InputIterator>, Hash, Pred,
501349cc55cSDimitry Andric    Allocator>; // C++17
502349cc55cSDimitry Andric
50306c3fb27SDimitry Andrictemplate<ranges::input_range R, class Hash = hash<range-key-type<R>>,
50406c3fb27SDimitry Andric         class Pred = equal_to<range-key-type<R>>,
50506c3fb27SDimitry Andric         class Allocator = allocator<range-to-alloc-type<R>>>
50606c3fb27SDimitry Andric  unordered_multimap(from_range_t, R&&, typename see below::size_type = see below,
50706c3fb27SDimitry Andric                Hash = Hash(), Pred = Pred(), Allocator = Allocator())
50806c3fb27SDimitry Andric    -> unordered_multimap<range-key-type<R>, range-mapped-type<R>, Hash, Pred, Allocator>; // C++23
50906c3fb27SDimitry Andric
510349cc55cSDimitry Andrictemplate<class Key, class T, class Hash = hash<Key>,
511349cc55cSDimitry Andric    class Pred = equal_to<Key>, class Allocator = allocator<pair<const Key, T>>>
512349cc55cSDimitry Andricunordered_multimap(initializer_list<pair<const Key, T>>, typename see below::size_type = see below,
513349cc55cSDimitry Andric    Hash = Hash(), Pred = Pred(), Allocator = Allocator())
514349cc55cSDimitry Andric  -> unordered_multimap<Key, T, Hash, Pred, Allocator>; // C++17
515349cc55cSDimitry Andric
516349cc55cSDimitry Andrictemplate<class InputIterator, class Allocator>
517349cc55cSDimitry Andricunordered_multimap(InputIterator, InputIterator, typename see below::size_type, Allocator)
518349cc55cSDimitry Andric  -> unordered_multimap<iter_key_t<InputIterator>, iter_val_t<InputIterator>,
519349cc55cSDimitry Andric        hash<iter_key_t<InputIterator>>, equal_to<iter_key_t<InputIterator>>, Allocator>; // C++17
520349cc55cSDimitry Andric
521349cc55cSDimitry Andrictemplate<class InputIterator, class Allocator>
522349cc55cSDimitry Andricunordered_multimap(InputIterator, InputIterator, Allocator)
523349cc55cSDimitry Andric  -> unordered_multimap<iter_key_t<InputIterator>, iter_val_t<InputIterator>,
524349cc55cSDimitry Andric        hash<iter_key_t<InputIterator>>, equal_to<iter_key_t<InputIterator>>, Allocator>; // C++17
525349cc55cSDimitry Andric
526349cc55cSDimitry Andrictemplate<class InputIterator, class Hash, class Allocator>
527349cc55cSDimitry Andricunordered_multimap(InputIterator, InputIterator, typename see below::size_type, Hash, Allocator)
528349cc55cSDimitry Andric  -> unordered_multimap<iter_key_t<InputIterator>, iter_val_t<InputIterator>, Hash,
529349cc55cSDimitry Andric          equal_to<iter_key_t<InputIterator>>, Allocator>; // C++17
530349cc55cSDimitry Andric
53106c3fb27SDimitry Andrictemplate<ranges::input_range R, class Allocator>
53206c3fb27SDimitry Andric  unordered_multimap(from_range_t, R&&, typename see below::size_type, Allocator)
53306c3fb27SDimitry Andric    -> unordered_multimap<range-key-type<R>, range-mapped-type<R>, hash<range-key-type<R>>,
53406c3fb27SDimitry Andric                      equal_to<range-key-type<R>>, Allocator>;   // C++23
53506c3fb27SDimitry Andric
53606c3fb27SDimitry Andrictemplate<ranges::input_range R, class Allocator>
53706c3fb27SDimitry Andric  unordered_multimap(from_range_t, R&&, Allocator)
53806c3fb27SDimitry Andric    -> unordered_multimap<range-key-type<R>, range-mapped-type<R>, hash<range-key-type<R>>,
53906c3fb27SDimitry Andric                      equal_to<range-key-type<R>>, Allocator>;   // C++23
54006c3fb27SDimitry Andric
54106c3fb27SDimitry Andrictemplate<ranges::input_range R, class Hash, class Allocator>
54206c3fb27SDimitry Andric  unordered_multimap(from_range_t, R&&, typename see below::size_type, Hash, Allocator)
54306c3fb27SDimitry Andric    -> unordered_multimap<range-key-type<R>, range-mapped-type<R>, Hash,
54406c3fb27SDimitry Andric                      equal_to<range-key-type<R>>, Allocator>;   // C++23
54506c3fb27SDimitry Andric
546349cc55cSDimitry Andrictemplate<class Key, class T, typename Allocator>
547349cc55cSDimitry Andricunordered_multimap(initializer_list<pair<const Key, T>>, typename see below::size_type, Allocator)
548349cc55cSDimitry Andric  -> unordered_multimap<Key, T, hash<Key>, equal_to<Key>, Allocator>; // C++17
549349cc55cSDimitry Andric
550349cc55cSDimitry Andrictemplate<class Key, class T, typename Allocator>
551349cc55cSDimitry Andricunordered_multimap(initializer_list<pair<const Key, T>>, Allocator)
552349cc55cSDimitry Andric  -> unordered_multimap<Key, T, hash<Key>, equal_to<Key>, Allocator>; // C++17
553349cc55cSDimitry Andric
554349cc55cSDimitry Andrictemplate<class Key, class T, class Hash, class Allocator>
555349cc55cSDimitry Andricunordered_multimap(initializer_list<pair<const Key, T>>, typename see below::size_type, Hash,
556349cc55cSDimitry Andric    Allocator)
557349cc55cSDimitry Andric  -> unordered_multimap<Key, T, Hash, equal_to<Key>, Allocator>; // C++17
558349cc55cSDimitry Andric
5590b57cec5SDimitry Andrictemplate <class Key, class T, class Hash, class Pred, class Alloc>
5600b57cec5SDimitry Andric    void swap(unordered_multimap<Key, T, Hash, Pred, Alloc>& x,
5610b57cec5SDimitry Andric              unordered_multimap<Key, T, Hash, Pred, Alloc>& y)
5620b57cec5SDimitry Andric              noexcept(noexcept(x.swap(y)));
5630b57cec5SDimitry Andric
5640b57cec5SDimitry Andrictemplate <class K, class T, class H, class P, class A, class Predicate>
5655ffd83dbSDimitry Andric    typename unordered_map<K, T, H, P, A>::size_type
5665ffd83dbSDimitry Andric    erase_if(unordered_map<K, T, H, P, A>& c, Predicate pred);       // C++20
5670b57cec5SDimitry Andric
5680b57cec5SDimitry Andrictemplate <class K, class T, class H, class P, class A, class Predicate>
5695ffd83dbSDimitry Andric    typename unordered_multimap<K, T, H, P, A>::size_type
5705ffd83dbSDimitry Andric    erase_if(unordered_multimap<K, T, H, P, A>& c, Predicate pred);  // C++20
5710b57cec5SDimitry Andric
5720b57cec5SDimitry Andrictemplate <class Key, class T, class Hash, class Pred, class Alloc>
5730b57cec5SDimitry Andric    bool
5740b57cec5SDimitry Andric    operator==(const unordered_multimap<Key, T, Hash, Pred, Alloc>& x,
5750b57cec5SDimitry Andric               const unordered_multimap<Key, T, Hash, Pred, Alloc>& y);
5760b57cec5SDimitry Andric
5770b57cec5SDimitry Andrictemplate <class Key, class T, class Hash, class Pred, class Alloc>
5780b57cec5SDimitry Andric    bool
5790b57cec5SDimitry Andric    operator!=(const unordered_multimap<Key, T, Hash, Pred, Alloc>& x,
58006c3fb27SDimitry Andric               const unordered_multimap<Key, T, Hash, Pred, Alloc>& y); // Removed in C++20
5810b57cec5SDimitry Andric
5820b57cec5SDimitry Andric}  // std
5830b57cec5SDimitry Andric
5840b57cec5SDimitry Andric*/
5850b57cec5SDimitry Andric
58681ad6265SDimitry Andric#include <__algorithm/is_permutation.h>
58781ad6265SDimitry Andric#include <__assert> // all public C++ headers provide the assertion handler
58806c3fb27SDimitry Andric#include <__availability>
5890b57cec5SDimitry Andric#include <__config>
590fe6060f1SDimitry Andric#include <__functional/is_transparent.h>
59181ad6265SDimitry Andric#include <__functional/operations.h>
5920b57cec5SDimitry Andric#include <__hash_table>
59381ad6265SDimitry Andric#include <__iterator/distance.h>
59481ad6265SDimitry Andric#include <__iterator/erase_if_container.h>
59504eeddc0SDimitry Andric#include <__iterator/iterator_traits.h>
59606c3fb27SDimitry Andric#include <__iterator/ranges_iterator_traits.h>
59704eeddc0SDimitry Andric#include <__memory/addressof.h>
598bdd1243dSDimitry Andric#include <__memory/allocator.h>
599bdd1243dSDimitry Andric#include <__memory_resource/polymorphic_allocator.h>
6000b57cec5SDimitry Andric#include <__node_handle>
60106c3fb27SDimitry Andric#include <__ranges/concepts.h>
60206c3fb27SDimitry Andric#include <__ranges/container_compatible_range.h>
60306c3fb27SDimitry Andric#include <__ranges/from_range.h>
604bdd1243dSDimitry Andric#include <__type_traits/is_allocator.h>
60506c3fb27SDimitry Andric#include <__type_traits/type_identity.h>
606fe6060f1SDimitry Andric#include <__utility/forward.h>
6070b57cec5SDimitry Andric#include <stdexcept>
6080b57cec5SDimitry Andric#include <tuple>
6090b57cec5SDimitry Andric#include <version>
6100b57cec5SDimitry Andric
61181ad6265SDimitry Andric// standard-mandated includes
61281ad6265SDimitry Andric
61381ad6265SDimitry Andric// [iterator.range]
61481ad6265SDimitry Andric#include <__iterator/access.h>
61581ad6265SDimitry Andric#include <__iterator/data.h>
61681ad6265SDimitry Andric#include <__iterator/empty.h>
61781ad6265SDimitry Andric#include <__iterator/reverse_access.h>
61881ad6265SDimitry Andric#include <__iterator/size.h>
61981ad6265SDimitry Andric
62081ad6265SDimitry Andric// [unord.map.syn]
62181ad6265SDimitry Andric#include <compare>
62281ad6265SDimitry Andric#include <initializer_list>
62381ad6265SDimitry Andric
6240b57cec5SDimitry Andric#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
6250b57cec5SDimitry Andric#  pragma GCC system_header
6260b57cec5SDimitry Andric#endif
6270b57cec5SDimitry Andric
628*b3edf446SDimitry Andric_LIBCPP_PUSH_MACROS
629*b3edf446SDimitry Andric#include <__undef_macros>
630*b3edf446SDimitry Andric
6310b57cec5SDimitry Andric_LIBCPP_BEGIN_NAMESPACE_STD
6320b57cec5SDimitry Andric
633cb14a3feSDimitry Andrictemplate <class _Key,
634cb14a3feSDimitry Andric          class _Cp,
635cb14a3feSDimitry Andric          class _Hash,
636cb14a3feSDimitry Andric          class _Pred,
6370b57cec5SDimitry Andric          bool = is_empty<_Hash>::value && !__libcpp_is_final<_Hash>::value>
638cb14a3feSDimitry Andricclass __unordered_map_hasher : private _Hash {
6390b57cec5SDimitry Andricpublic:
640cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI __unordered_map_hasher() _NOEXCEPT_(is_nothrow_default_constructible<_Hash>::value) : _Hash() {}
641cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI __unordered_map_hasher(const _Hash& __h) _NOEXCEPT_(is_nothrow_copy_constructible<_Hash>::value)
6420b57cec5SDimitry Andric      : _Hash(__h) {}
643cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI const _Hash& hash_function() const _NOEXCEPT { return *this; }
644cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI size_t operator()(const _Cp& __x) const {
645cb14a3feSDimitry Andric    return static_cast<const _Hash&>(*this)(__x.__get_value().first);
646cb14a3feSDimitry Andric  }
647cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI size_t operator()(const _Key& __x) const { return static_cast<const _Hash&>(*this)(__x); }
64806c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 20
649349cc55cSDimitry Andric  template <typename _K2>
650cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI size_t operator()(const _K2& __x) const {
651cb14a3feSDimitry Andric    return static_cast<const _Hash&>(*this)(__x);
652cb14a3feSDimitry Andric  }
653e8d8bef9SDimitry Andric#endif
654cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI void swap(__unordered_map_hasher& __y) _NOEXCEPT_(__is_nothrow_swappable<_Hash>::value) {
6555f757f3fSDimitry Andric    using std::swap;
6560b57cec5SDimitry Andric    swap(static_cast<_Hash&>(*this), static_cast<_Hash&>(__y));
6570b57cec5SDimitry Andric  }
6580b57cec5SDimitry Andric};
6590b57cec5SDimitry Andric
660e8d8bef9SDimitry Andrictemplate <class _Key, class _Cp, class _Hash, class _Pred>
661cb14a3feSDimitry Andricclass __unordered_map_hasher<_Key, _Cp, _Hash, _Pred, false> {
6620b57cec5SDimitry Andric  _Hash __hash_;
663cb14a3feSDimitry Andric
6640b57cec5SDimitry Andricpublic:
665cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI __unordered_map_hasher() _NOEXCEPT_(is_nothrow_default_constructible<_Hash>::value)
6660b57cec5SDimitry Andric      : __hash_() {}
667cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI __unordered_map_hasher(const _Hash& __h) _NOEXCEPT_(is_nothrow_copy_constructible<_Hash>::value)
6680b57cec5SDimitry Andric      : __hash_(__h) {}
669cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI const _Hash& hash_function() const _NOEXCEPT { return __hash_; }
670cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI size_t operator()(const _Cp& __x) const { return __hash_(__x.__get_value().first); }
671cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI size_t operator()(const _Key& __x) const { return __hash_(__x); }
67206c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 20
673349cc55cSDimitry Andric  template <typename _K2>
674cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI size_t operator()(const _K2& __x) const {
675cb14a3feSDimitry Andric    return __hash_(__x);
676cb14a3feSDimitry Andric  }
677e8d8bef9SDimitry Andric#endif
678cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI void swap(__unordered_map_hasher& __y) _NOEXCEPT_(__is_nothrow_swappable<_Hash>::value) {
6795f757f3fSDimitry Andric    using std::swap;
6800b57cec5SDimitry Andric    swap(__hash_, __y.__hash_);
6810b57cec5SDimitry Andric  }
6820b57cec5SDimitry Andric};
6830b57cec5SDimitry Andric
684e8d8bef9SDimitry Andrictemplate <class _Key, class _Cp, class _Hash, class _Pred, bool __b>
685cb14a3feSDimitry Andricinline _LIBCPP_HIDE_FROM_ABI void
686e8d8bef9SDimitry Andricswap(__unordered_map_hasher<_Key, _Cp, _Hash, _Pred, __b>& __x,
687cb14a3feSDimitry Andric     __unordered_map_hasher<_Key, _Cp, _Hash, _Pred, __b>& __y) _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) {
6880b57cec5SDimitry Andric  __x.swap(__y);
6890b57cec5SDimitry Andric}
6900b57cec5SDimitry Andric
691cb14a3feSDimitry Andrictemplate <class _Key,
692cb14a3feSDimitry Andric          class _Cp,
693cb14a3feSDimitry Andric          class _Pred,
694cb14a3feSDimitry Andric          class _Hash,
6950b57cec5SDimitry Andric          bool = is_empty<_Pred>::value && !__libcpp_is_final<_Pred>::value>
696cb14a3feSDimitry Andricclass __unordered_map_equal : private _Pred {
6970b57cec5SDimitry Andricpublic:
698cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI __unordered_map_equal() _NOEXCEPT_(is_nothrow_default_constructible<_Pred>::value) : _Pred() {}
699cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI __unordered_map_equal(const _Pred& __p) _NOEXCEPT_(is_nothrow_copy_constructible<_Pred>::value)
7000b57cec5SDimitry Andric      : _Pred(__p) {}
701cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI const _Pred& key_eq() const _NOEXCEPT { return *this; }
702cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI bool operator()(const _Cp& __x, const _Cp& __y) const {
703cb14a3feSDimitry Andric    return static_cast<const _Pred&>(*this)(__x.__get_value().first, __y.__get_value().first);
704cb14a3feSDimitry Andric  }
705cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI bool operator()(const _Cp& __x, const _Key& __y) const {
706cb14a3feSDimitry Andric    return static_cast<const _Pred&>(*this)(__x.__get_value().first, __y);
707cb14a3feSDimitry Andric  }
708cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI bool operator()(const _Key& __x, const _Cp& __y) const {
709cb14a3feSDimitry Andric    return static_cast<const _Pred&>(*this)(__x, __y.__get_value().first);
710cb14a3feSDimitry Andric  }
71106c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 20
712349cc55cSDimitry Andric  template <typename _K2>
713cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI bool operator()(const _Cp& __x, const _K2& __y) const {
714cb14a3feSDimitry Andric    return static_cast<const _Pred&>(*this)(__x.__get_value().first, __y);
715cb14a3feSDimitry Andric  }
716349cc55cSDimitry Andric  template <typename _K2>
717cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI bool operator()(const _K2& __x, const _Cp& __y) const {
718cb14a3feSDimitry Andric    return static_cast<const _Pred&>(*this)(__x, __y.__get_value().first);
719cb14a3feSDimitry Andric  }
720349cc55cSDimitry Andric  template <typename _K2>
721cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI bool operator()(const _Key& __x, const _K2& __y) const {
722cb14a3feSDimitry Andric    return static_cast<const _Pred&>(*this)(__x, __y);
723cb14a3feSDimitry Andric  }
724349cc55cSDimitry Andric  template <typename _K2>
725cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI bool operator()(const _K2& __x, const _Key& __y) const {
726cb14a3feSDimitry Andric    return static_cast<const _Pred&>(*this)(__x, __y);
727cb14a3feSDimitry Andric  }
728e8d8bef9SDimitry Andric#endif
729cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI void swap(__unordered_map_equal& __y) _NOEXCEPT_(__is_nothrow_swappable<_Pred>::value) {
7305f757f3fSDimitry Andric    using std::swap;
7310b57cec5SDimitry Andric    swap(static_cast<_Pred&>(*this), static_cast<_Pred&>(__y));
7320b57cec5SDimitry Andric  }
7330b57cec5SDimitry Andric};
7340b57cec5SDimitry Andric
735e8d8bef9SDimitry Andrictemplate <class _Key, class _Cp, class _Pred, class _Hash>
736cb14a3feSDimitry Andricclass __unordered_map_equal<_Key, _Cp, _Pred, _Hash, false> {
7370b57cec5SDimitry Andric  _Pred __pred_;
738cb14a3feSDimitry Andric
7390b57cec5SDimitry Andricpublic:
740cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI __unordered_map_equal() _NOEXCEPT_(is_nothrow_default_constructible<_Pred>::value)
7410b57cec5SDimitry Andric      : __pred_() {}
742cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI __unordered_map_equal(const _Pred& __p) _NOEXCEPT_(is_nothrow_copy_constructible<_Pred>::value)
7430b57cec5SDimitry Andric      : __pred_(__p) {}
744cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI const _Pred& key_eq() const _NOEXCEPT { return __pred_; }
745cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI bool operator()(const _Cp& __x, const _Cp& __y) const {
746cb14a3feSDimitry Andric    return __pred_(__x.__get_value().first, __y.__get_value().first);
747cb14a3feSDimitry Andric  }
748cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI bool operator()(const _Cp& __x, const _Key& __y) const {
749cb14a3feSDimitry Andric    return __pred_(__x.__get_value().first, __y);
750cb14a3feSDimitry Andric  }
751cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI bool operator()(const _Key& __x, const _Cp& __y) const {
752cb14a3feSDimitry Andric    return __pred_(__x, __y.__get_value().first);
753cb14a3feSDimitry Andric  }
75406c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 20
755349cc55cSDimitry Andric  template <typename _K2>
756cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI bool operator()(const _Cp& __x, const _K2& __y) const {
757cb14a3feSDimitry Andric    return __pred_(__x.__get_value().first, __y);
758cb14a3feSDimitry Andric  }
759349cc55cSDimitry Andric  template <typename _K2>
760cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI bool operator()(const _K2& __x, const _Cp& __y) const {
761cb14a3feSDimitry Andric    return __pred_(__x, __y.__get_value().first);
762cb14a3feSDimitry Andric  }
763349cc55cSDimitry Andric  template <typename _K2>
764cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI bool operator()(const _Key& __x, const _K2& __y) const {
765cb14a3feSDimitry Andric    return __pred_(__x, __y);
766cb14a3feSDimitry Andric  }
767349cc55cSDimitry Andric  template <typename _K2>
768cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI bool operator()(const _K2& __x, const _Key& __y) const {
769cb14a3feSDimitry Andric    return __pred_(__x, __y);
770cb14a3feSDimitry Andric  }
771e8d8bef9SDimitry Andric#endif
772cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI void swap(__unordered_map_equal& __y) _NOEXCEPT_(__is_nothrow_swappable<_Pred>::value) {
7735f757f3fSDimitry Andric    using std::swap;
7740b57cec5SDimitry Andric    swap(__pred_, __y.__pred_);
7750b57cec5SDimitry Andric  }
7760b57cec5SDimitry Andric};
7770b57cec5SDimitry Andric
778e8d8bef9SDimitry Andrictemplate <class _Key, class _Cp, class _Pred, class _Hash, bool __b>
779cb14a3feSDimitry Andricinline _LIBCPP_HIDE_FROM_ABI void
780cb14a3feSDimitry Andricswap(__unordered_map_equal<_Key, _Cp, _Pred, _Hash, __b>& __x, __unordered_map_equal<_Key, _Cp, _Pred, _Hash, __b>& __y)
781cb14a3feSDimitry Andric    _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) {
7820b57cec5SDimitry Andric  __x.swap(__y);
7830b57cec5SDimitry Andric}
7840b57cec5SDimitry Andric
7850b57cec5SDimitry Andrictemplate <class _Alloc>
786cb14a3feSDimitry Andricclass __hash_map_node_destructor {
7870b57cec5SDimitry Andric  typedef _Alloc allocator_type;
7880b57cec5SDimitry Andric  typedef allocator_traits<allocator_type> __alloc_traits;
7890b57cec5SDimitry Andric
7900b57cec5SDimitry Andricpublic:
7910b57cec5SDimitry Andric  typedef typename __alloc_traits::pointer pointer;
7920b57cec5SDimitry Andric
793cb14a3feSDimitry Andricprivate:
7940b57cec5SDimitry Andric  allocator_type& __na_;
7950b57cec5SDimitry Andric
7960b57cec5SDimitry Andric  __hash_map_node_destructor& operator=(const __hash_map_node_destructor&);
7970b57cec5SDimitry Andric
7980b57cec5SDimitry Andricpublic:
7990b57cec5SDimitry Andric  bool __first_constructed;
8000b57cec5SDimitry Andric  bool __second_constructed;
8010b57cec5SDimitry Andric
802cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI explicit __hash_map_node_destructor(allocator_type& __na) _NOEXCEPT
8030b57cec5SDimitry Andric      : __na_(__na),
8040b57cec5SDimitry Andric        __first_constructed(false),
805cb14a3feSDimitry Andric        __second_constructed(false) {}
8060b57cec5SDimitry Andric
8070b57cec5SDimitry Andric#ifndef _LIBCPP_CXX03_LANG
808cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI __hash_map_node_destructor(__hash_node_destructor<allocator_type>&& __x) _NOEXCEPT
8090b57cec5SDimitry Andric      : __na_(__x.__na_),
8100b57cec5SDimitry Andric        __first_constructed(__x.__value_constructed),
811cb14a3feSDimitry Andric        __second_constructed(__x.__value_constructed) {
8120b57cec5SDimitry Andric    __x.__value_constructed = false;
8130b57cec5SDimitry Andric  }
8140b57cec5SDimitry Andric#else  // _LIBCPP_CXX03_LANG
815cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI __hash_map_node_destructor(const __hash_node_destructor<allocator_type>& __x)
816cb14a3feSDimitry Andric      : __na_(__x.__na_), __first_constructed(__x.__value_constructed), __second_constructed(__x.__value_constructed) {
8170b57cec5SDimitry Andric    const_cast<bool&>(__x.__value_constructed) = false;
8180b57cec5SDimitry Andric  }
8190b57cec5SDimitry Andric#endif // _LIBCPP_CXX03_LANG
8200b57cec5SDimitry Andric
821cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI void operator()(pointer __p) _NOEXCEPT {
8220b57cec5SDimitry Andric    if (__second_constructed)
8235f757f3fSDimitry Andric      __alloc_traits::destroy(__na_, std::addressof(__p->__get_value().__get_value().second));
8240b57cec5SDimitry Andric    if (__first_constructed)
8255f757f3fSDimitry Andric      __alloc_traits::destroy(__na_, std::addressof(__p->__get_value().__get_value().first));
8260b57cec5SDimitry Andric    if (__p)
8270b57cec5SDimitry Andric      __alloc_traits::deallocate(__na_, __p, 1);
8280b57cec5SDimitry Andric  }
8290b57cec5SDimitry Andric};
8300b57cec5SDimitry Andric
8310b57cec5SDimitry Andric#ifndef _LIBCPP_CXX03_LANG
8320b57cec5SDimitry Andrictemplate <class _Key, class _Tp>
833cb14a3feSDimitry Andricstruct _LIBCPP_STANDALONE_DEBUG __hash_value_type {
8340b57cec5SDimitry Andric  typedef _Key key_type;
8350b57cec5SDimitry Andric  typedef _Tp mapped_type;
8360b57cec5SDimitry Andric  typedef pair<const key_type, mapped_type> value_type;
8370b57cec5SDimitry Andric  typedef pair<key_type&, mapped_type&> __nc_ref_pair_type;
8380b57cec5SDimitry Andric  typedef pair<key_type&&, mapped_type&&> __nc_rref_pair_type;
8390b57cec5SDimitry Andric
8400b57cec5SDimitry Andricprivate:
841bdd1243dSDimitry Andric  value_type __cc_;
8420b57cec5SDimitry Andric
8430b57cec5SDimitry Andricpublic:
844cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI value_type& __get_value() {
84506c3fb27SDimitry Andric#  if _LIBCPP_STD_VER >= 17
8465f757f3fSDimitry Andric    return *std::launder(std::addressof(__cc_));
8470b57cec5SDimitry Andric#  else
848bdd1243dSDimitry Andric    return __cc_;
8490b57cec5SDimitry Andric#  endif
8500b57cec5SDimitry Andric  }
8510b57cec5SDimitry Andric
852cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI const value_type& __get_value() const {
85306c3fb27SDimitry Andric#  if _LIBCPP_STD_VER >= 17
8545f757f3fSDimitry Andric    return *std::launder(std::addressof(__cc_));
8550b57cec5SDimitry Andric#  else
856bdd1243dSDimitry Andric    return __cc_;
8570b57cec5SDimitry Andric#  endif
8580b57cec5SDimitry Andric  }
8590b57cec5SDimitry Andric
860cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI __nc_ref_pair_type __ref() {
8610b57cec5SDimitry Andric    value_type& __v = __get_value();
8620b57cec5SDimitry Andric    return __nc_ref_pair_type(const_cast<key_type&>(__v.first), __v.second);
8630b57cec5SDimitry Andric  }
8640b57cec5SDimitry Andric
865cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI __nc_rref_pair_type __move() {
8660b57cec5SDimitry Andric    value_type& __v = __get_value();
867cb14a3feSDimitry Andric    return __nc_rref_pair_type(std::move(const_cast<key_type&>(__v.first)), std::move(__v.second));
8680b57cec5SDimitry Andric  }
8690b57cec5SDimitry Andric
870cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI __hash_value_type& operator=(const __hash_value_type& __v) {
8710b57cec5SDimitry Andric    __ref() = __v.__get_value();
8720b57cec5SDimitry Andric    return *this;
8730b57cec5SDimitry Andric  }
8740b57cec5SDimitry Andric
875cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI __hash_value_type& operator=(__hash_value_type&& __v) {
8760b57cec5SDimitry Andric    __ref() = __v.__move();
8770b57cec5SDimitry Andric    return *this;
8780b57cec5SDimitry Andric  }
8790b57cec5SDimitry Andric
880cb14a3feSDimitry Andric  template <class _ValueTp, class = __enable_if_t<__is_same_uncvref<_ValueTp, value_type>::value> >
881cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI __hash_value_type& operator=(_ValueTp&& __v) {
8825f757f3fSDimitry Andric    __ref() = std::forward<_ValueTp>(__v);
8830b57cec5SDimitry Andric    return *this;
8840b57cec5SDimitry Andric  }
8850b57cec5SDimitry Andric
8860b57cec5SDimitry Andricprivate:
8870b57cec5SDimitry Andric  __hash_value_type(const __hash_value_type& __v) = delete;
8880b57cec5SDimitry Andric  __hash_value_type(__hash_value_type&& __v)      = delete;
8890b57cec5SDimitry Andric  template <class... _Args>
8900b57cec5SDimitry Andric  explicit __hash_value_type(_Args&&... __args) = delete;
8910b57cec5SDimitry Andric
8920b57cec5SDimitry Andric  ~__hash_value_type() = delete;
8930b57cec5SDimitry Andric};
8940b57cec5SDimitry Andric
8950b57cec5SDimitry Andric#else
8960b57cec5SDimitry Andric
8970b57cec5SDimitry Andrictemplate <class _Key, class _Tp>
898cb14a3feSDimitry Andricstruct __hash_value_type {
8990b57cec5SDimitry Andric  typedef _Key key_type;
9000b57cec5SDimitry Andric  typedef _Tp mapped_type;
9010b57cec5SDimitry Andric  typedef pair<const key_type, mapped_type> value_type;
9020b57cec5SDimitry Andric
9030b57cec5SDimitry Andricprivate:
904bdd1243dSDimitry Andric  value_type __cc_;
9050b57cec5SDimitry Andric
9060b57cec5SDimitry Andricpublic:
907cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI value_type& __get_value() { return __cc_; }
908cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI const value_type& __get_value() const { return __cc_; }
9090b57cec5SDimitry Andric
9100b57cec5SDimitry Andricprivate:
9110b57cec5SDimitry Andric  ~__hash_value_type();
9120b57cec5SDimitry Andric};
9130b57cec5SDimitry Andric
9140b57cec5SDimitry Andric#endif
9150b57cec5SDimitry Andric
9160b57cec5SDimitry Andrictemplate <class _HashIterator>
917cb14a3feSDimitry Andricclass _LIBCPP_TEMPLATE_VIS __hash_map_iterator {
9180b57cec5SDimitry Andric  _HashIterator __i_;
9190b57cec5SDimitry Andric
9200b57cec5SDimitry Andric  typedef __hash_node_types_from_iterator<_HashIterator> _NodeTypes;
9210b57cec5SDimitry Andric
9220b57cec5SDimitry Andricpublic:
9230b57cec5SDimitry Andric  typedef forward_iterator_tag iterator_category;
9240b57cec5SDimitry Andric  typedef typename _NodeTypes::__map_value_type value_type;
9250b57cec5SDimitry Andric  typedef typename _NodeTypes::difference_type difference_type;
9260b57cec5SDimitry Andric  typedef value_type& reference;
9270b57cec5SDimitry Andric  typedef typename _NodeTypes::__map_value_type_pointer pointer;
9280b57cec5SDimitry Andric
929cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI __hash_map_iterator() _NOEXCEPT {}
9300b57cec5SDimitry Andric
931cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI __hash_map_iterator(_HashIterator __i) _NOEXCEPT : __i_(__i) {}
9320b57cec5SDimitry Andric
933cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI reference operator*() const { return __i_->__get_value(); }
934cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI pointer operator->() const { return pointer_traits<pointer>::pointer_to(__i_->__get_value()); }
9350b57cec5SDimitry Andric
936cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI __hash_map_iterator& operator++() {
937cb14a3feSDimitry Andric    ++__i_;
938cb14a3feSDimitry Andric    return *this;
939cb14a3feSDimitry Andric  }
940cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI __hash_map_iterator operator++(int) {
9410b57cec5SDimitry Andric    __hash_map_iterator __t(*this);
9420b57cec5SDimitry Andric    ++(*this);
9430b57cec5SDimitry Andric    return __t;
9440b57cec5SDimitry Andric  }
9450b57cec5SDimitry Andric
946cb14a3feSDimitry Andric  friend _LIBCPP_HIDE_FROM_ABI bool operator==(const __hash_map_iterator& __x, const __hash_map_iterator& __y) {
947cb14a3feSDimitry Andric    return __x.__i_ == __y.__i_;
948cb14a3feSDimitry Andric  }
94906c3fb27SDimitry Andric#if _LIBCPP_STD_VER <= 17
950cb14a3feSDimitry Andric  friend _LIBCPP_HIDE_FROM_ABI bool operator!=(const __hash_map_iterator& __x, const __hash_map_iterator& __y) {
951cb14a3feSDimitry Andric    return __x.__i_ != __y.__i_;
952cb14a3feSDimitry Andric  }
95306c3fb27SDimitry Andric#endif
9540b57cec5SDimitry Andric
955cb14a3feSDimitry Andric  template <class, class, class, class, class>
956cb14a3feSDimitry Andric  friend class _LIBCPP_TEMPLATE_VIS unordered_map;
957cb14a3feSDimitry Andric  template <class, class, class, class, class>
958cb14a3feSDimitry Andric  friend class _LIBCPP_TEMPLATE_VIS unordered_multimap;
959cb14a3feSDimitry Andric  template <class>
960cb14a3feSDimitry Andric  friend class _LIBCPP_TEMPLATE_VIS __hash_const_iterator;
961cb14a3feSDimitry Andric  template <class>
962cb14a3feSDimitry Andric  friend class _LIBCPP_TEMPLATE_VIS __hash_const_local_iterator;
963cb14a3feSDimitry Andric  template <class>
964cb14a3feSDimitry Andric  friend class _LIBCPP_TEMPLATE_VIS __hash_map_const_iterator;
9650b57cec5SDimitry Andric};
9660b57cec5SDimitry Andric
9670b57cec5SDimitry Andrictemplate <class _HashIterator>
968cb14a3feSDimitry Andricclass _LIBCPP_TEMPLATE_VIS __hash_map_const_iterator {
9690b57cec5SDimitry Andric  _HashIterator __i_;
9700b57cec5SDimitry Andric
9710b57cec5SDimitry Andric  typedef __hash_node_types_from_iterator<_HashIterator> _NodeTypes;
9720b57cec5SDimitry Andric
9730b57cec5SDimitry Andricpublic:
9740b57cec5SDimitry Andric  typedef forward_iterator_tag iterator_category;
9750b57cec5SDimitry Andric  typedef typename _NodeTypes::__map_value_type value_type;
9760b57cec5SDimitry Andric  typedef typename _NodeTypes::difference_type difference_type;
9770b57cec5SDimitry Andric  typedef const value_type& reference;
9780b57cec5SDimitry Andric  typedef typename _NodeTypes::__const_map_value_type_pointer pointer;
9790b57cec5SDimitry Andric
980cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI __hash_map_const_iterator() _NOEXCEPT {}
9810b57cec5SDimitry Andric
982cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI __hash_map_const_iterator(_HashIterator __i) _NOEXCEPT : __i_(__i) {}
9835f757f3fSDimitry Andric  _LIBCPP_HIDE_FROM_ABI
984cb14a3feSDimitry Andric  __hash_map_const_iterator(__hash_map_iterator<typename _HashIterator::__non_const_iterator> __i) _NOEXCEPT
9850b57cec5SDimitry Andric      : __i_(__i.__i_) {}
9860b57cec5SDimitry Andric
987cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI reference operator*() const { return __i_->__get_value(); }
988cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI pointer operator->() const { return pointer_traits<pointer>::pointer_to(__i_->__get_value()); }
9890b57cec5SDimitry Andric
990cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI __hash_map_const_iterator& operator++() {
991cb14a3feSDimitry Andric    ++__i_;
992cb14a3feSDimitry Andric    return *this;
993cb14a3feSDimitry Andric  }
994cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI __hash_map_const_iterator operator++(int) {
9950b57cec5SDimitry Andric    __hash_map_const_iterator __t(*this);
9960b57cec5SDimitry Andric    ++(*this);
9970b57cec5SDimitry Andric    return __t;
9980b57cec5SDimitry Andric  }
9990b57cec5SDimitry Andric
1000cb14a3feSDimitry Andric  friend _LIBCPP_HIDE_FROM_ABI bool
1001cb14a3feSDimitry Andric  operator==(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y) {
1002cb14a3feSDimitry Andric    return __x.__i_ == __y.__i_;
1003cb14a3feSDimitry Andric  }
100406c3fb27SDimitry Andric#if _LIBCPP_STD_VER <= 17
1005cb14a3feSDimitry Andric  friend _LIBCPP_HIDE_FROM_ABI bool
1006cb14a3feSDimitry Andric  operator!=(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y) {
1007cb14a3feSDimitry Andric    return __x.__i_ != __y.__i_;
1008cb14a3feSDimitry Andric  }
100906c3fb27SDimitry Andric#endif
10100b57cec5SDimitry Andric
1011cb14a3feSDimitry Andric  template <class, class, class, class, class>
1012cb14a3feSDimitry Andric  friend class _LIBCPP_TEMPLATE_VIS unordered_map;
1013cb14a3feSDimitry Andric  template <class, class, class, class, class>
1014cb14a3feSDimitry Andric  friend class _LIBCPP_TEMPLATE_VIS unordered_multimap;
1015cb14a3feSDimitry Andric  template <class>
1016cb14a3feSDimitry Andric  friend class _LIBCPP_TEMPLATE_VIS __hash_const_iterator;
1017cb14a3feSDimitry Andric  template <class>
1018cb14a3feSDimitry Andric  friend class _LIBCPP_TEMPLATE_VIS __hash_const_local_iterator;
10190b57cec5SDimitry Andric};
10200b57cec5SDimitry Andric
10210b57cec5SDimitry Andrictemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
10220b57cec5SDimitry Andricclass unordered_multimap;
10230b57cec5SDimitry Andric
1024cb14a3feSDimitry Andrictemplate <class _Key,
1025cb14a3feSDimitry Andric          class _Tp,
1026cb14a3feSDimitry Andric          class _Hash  = hash<_Key>,
1027cb14a3feSDimitry Andric          class _Pred  = equal_to<_Key>,
10280b57cec5SDimitry Andric          class _Alloc = allocator<pair<const _Key, _Tp> > >
1029cb14a3feSDimitry Andricclass _LIBCPP_TEMPLATE_VIS unordered_map {
10300b57cec5SDimitry Andricpublic:
10310b57cec5SDimitry Andric  // types
10320b57cec5SDimitry Andric  typedef _Key key_type;
10330b57cec5SDimitry Andric  typedef _Tp mapped_type;
103481ad6265SDimitry Andric  typedef __type_identity_t<_Hash> hasher;
103581ad6265SDimitry Andric  typedef __type_identity_t<_Pred> key_equal;
103681ad6265SDimitry Andric  typedef __type_identity_t<_Alloc> allocator_type;
10370b57cec5SDimitry Andric  typedef pair<const key_type, mapped_type> value_type;
10380b57cec5SDimitry Andric  typedef value_type& reference;
10390b57cec5SDimitry Andric  typedef const value_type& const_reference;
10400b57cec5SDimitry Andric  static_assert((is_same<value_type, typename allocator_type::value_type>::value),
104106c3fb27SDimitry Andric                "Allocator::value_type must be same type as value_type");
10420b57cec5SDimitry Andric
10430b57cec5SDimitry Andricprivate:
10440b57cec5SDimitry Andric  typedef __hash_value_type<key_type, mapped_type> __value_type;
1045e8d8bef9SDimitry Andric  typedef __unordered_map_hasher<key_type, __value_type, hasher, key_equal> __hasher;
1046e8d8bef9SDimitry Andric  typedef __unordered_map_equal<key_type, __value_type, key_equal, hasher> __key_equal;
1047bdd1243dSDimitry Andric  typedef __rebind_alloc<allocator_traits<allocator_type>, __value_type> __allocator_type;
10480b57cec5SDimitry Andric
1049cb14a3feSDimitry Andric  typedef __hash_table<__value_type, __hasher, __key_equal, __allocator_type> __table;
10500b57cec5SDimitry Andric
10510b57cec5SDimitry Andric  __table __table_;
10520b57cec5SDimitry Andric
10530b57cec5SDimitry Andric  typedef typename __table::_NodeTypes _NodeTypes;
10540b57cec5SDimitry Andric  typedef typename __table::__node_pointer __node_pointer;
10550b57cec5SDimitry Andric  typedef typename __table::__node_const_pointer __node_const_pointer;
10560b57cec5SDimitry Andric  typedef typename __table::__node_traits __node_traits;
10570b57cec5SDimitry Andric  typedef typename __table::__node_allocator __node_allocator;
10580b57cec5SDimitry Andric  typedef typename __table::__node __node;
10590b57cec5SDimitry Andric  typedef __hash_map_node_destructor<__node_allocator> _Dp;
10600b57cec5SDimitry Andric  typedef unique_ptr<__node, _Dp> __node_holder;
10610b57cec5SDimitry Andric  typedef allocator_traits<allocator_type> __alloc_traits;
10620b57cec5SDimitry Andric
1063bdd1243dSDimitry Andric  static_assert(is_same<allocator_type, __rebind_alloc<__alloc_traits, value_type> >::value,
1064bdd1243dSDimitry Andric                "[allocator.requirements] states that rebinding an allocator to the same type should result in the "
1065bdd1243dSDimitry Andric                "original allocator");
1066bdd1243dSDimitry Andric
10670b57cec5SDimitry Andric  static_assert((is_same<typename __table::__container_value_type, value_type>::value), "");
10680b57cec5SDimitry Andric  static_assert((is_same<typename __table::__node_value_type, __value_type>::value), "");
1069cb14a3feSDimitry Andric
10700b57cec5SDimitry Andricpublic:
10710b57cec5SDimitry Andric  typedef typename __alloc_traits::pointer pointer;
10720b57cec5SDimitry Andric  typedef typename __alloc_traits::const_pointer const_pointer;
10730b57cec5SDimitry Andric  typedef typename __table::size_type size_type;
10740b57cec5SDimitry Andric  typedef typename __table::difference_type difference_type;
10750b57cec5SDimitry Andric
10760b57cec5SDimitry Andric  typedef __hash_map_iterator<typename __table::iterator> iterator;
10770b57cec5SDimitry Andric  typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator;
10780b57cec5SDimitry Andric  typedef __hash_map_iterator<typename __table::local_iterator> local_iterator;
10790b57cec5SDimitry Andric  typedef __hash_map_const_iterator<typename __table::const_local_iterator> const_local_iterator;
10800b57cec5SDimitry Andric
108106c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 17
10820b57cec5SDimitry Andric  typedef __map_node_handle<__node, allocator_type> node_type;
10830b57cec5SDimitry Andric  typedef __insert_return_type<iterator, node_type> insert_return_type;
10840b57cec5SDimitry Andric#endif
10850b57cec5SDimitry Andric
10860b57cec5SDimitry Andric  template <class _Key2, class _Tp2, class _Hash2, class _Pred2, class _Alloc2>
10870b57cec5SDimitry Andric  friend class _LIBCPP_TEMPLATE_VIS unordered_map;
10880b57cec5SDimitry Andric  template <class _Key2, class _Tp2, class _Hash2, class _Pred2, class _Alloc2>
10890b57cec5SDimitry Andric  friend class _LIBCPP_TEMPLATE_VIS unordered_multimap;
10900b57cec5SDimitry Andric
1091cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI unordered_map() _NOEXCEPT_(is_nothrow_default_constructible<__table>::value) {}
1092cb14a3feSDimitry Andric  explicit _LIBCPP_HIDE_FROM_ABI
1093cb14a3feSDimitry Andric  unordered_map(size_type __n, const hasher& __hf = hasher(), const key_equal& __eql = key_equal());
10945f757f3fSDimitry Andric  _LIBCPP_HIDE_FROM_ABI
1095cb14a3feSDimitry Andric  unordered_map(size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a);
10960b57cec5SDimitry Andric  template <class _InputIterator>
109706c3fb27SDimitry Andric  _LIBCPP_HIDE_FROM_ABI unordered_map(_InputIterator __first, _InputIterator __last);
10980b57cec5SDimitry Andric  template <class _InputIterator>
1099cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI
1100cb14a3feSDimitry Andric  unordered_map(_InputIterator __first,
1101cb14a3feSDimitry Andric                _InputIterator __last,
1102cb14a3feSDimitry Andric                size_type __n,
1103cb14a3feSDimitry Andric                const hasher& __hf     = hasher(),
11040b57cec5SDimitry Andric                const key_equal& __eql = key_equal());
11050b57cec5SDimitry Andric  template <class _InputIterator>
1106cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI unordered_map(
1107cb14a3feSDimitry Andric      _InputIterator __first,
1108cb14a3feSDimitry Andric      _InputIterator __last,
1109cb14a3feSDimitry Andric      size_type __n,
1110cb14a3feSDimitry Andric      const hasher& __hf,
11110b57cec5SDimitry Andric      const key_equal& __eql,
11120b57cec5SDimitry Andric      const allocator_type& __a);
111306c3fb27SDimitry Andric
111406c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 23
111506c3fb27SDimitry Andric  template <_ContainerCompatibleRange<value_type> _Range>
1116cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI unordered_map(
1117cb14a3feSDimitry Andric      from_range_t,
1118cb14a3feSDimitry Andric      _Range&& __range,
1119cb14a3feSDimitry Andric      size_type __n             = /*implementation-defined*/ 0,
1120cb14a3feSDimitry Andric      const hasher& __hf        = hasher(),
1121cb14a3feSDimitry Andric      const key_equal& __eql    = key_equal(),
112206c3fb27SDimitry Andric      const allocator_type& __a = allocator_type())
112306c3fb27SDimitry Andric      : __table_(__hf, __eql, typename __table::allocator_type(__a)) {
112406c3fb27SDimitry Andric    if (__n > 0) {
112506c3fb27SDimitry Andric      __table_.__rehash_unique(__n);
112606c3fb27SDimitry Andric    }
112706c3fb27SDimitry Andric    insert_range(std::forward<_Range>(__range));
112806c3fb27SDimitry Andric  }
112906c3fb27SDimitry Andric#endif
113006c3fb27SDimitry Andric
1131cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI explicit unordered_map(const allocator_type& __a);
113206c3fb27SDimitry Andric  _LIBCPP_HIDE_FROM_ABI unordered_map(const unordered_map& __u);
113306c3fb27SDimitry Andric  _LIBCPP_HIDE_FROM_ABI unordered_map(const unordered_map& __u, const allocator_type& __a);
11340b57cec5SDimitry Andric#ifndef _LIBCPP_CXX03_LANG
1135cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI unordered_map(unordered_map&& __u) _NOEXCEPT_(is_nothrow_move_constructible<__table>::value);
113606c3fb27SDimitry Andric  _LIBCPP_HIDE_FROM_ABI unordered_map(unordered_map&& __u, const allocator_type& __a);
113706c3fb27SDimitry Andric  _LIBCPP_HIDE_FROM_ABI unordered_map(initializer_list<value_type> __il);
1138cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI
1139cb14a3feSDimitry Andric  unordered_map(initializer_list<value_type> __il,
1140cb14a3feSDimitry Andric                size_type __n,
1141cb14a3feSDimitry Andric                const hasher& __hf     = hasher(),
1142cb14a3feSDimitry Andric                const key_equal& __eql = key_equal());
1143cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI unordered_map(
1144cb14a3feSDimitry Andric      initializer_list<value_type> __il,
1145cb14a3feSDimitry Andric      size_type __n,
1146cb14a3feSDimitry Andric      const hasher& __hf,
1147cb14a3feSDimitry Andric      const key_equal& __eql,
11480b57cec5SDimitry Andric      const allocator_type& __a);
11490b57cec5SDimitry Andric#endif // _LIBCPP_CXX03_LANG
115006c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 14
1151cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI unordered_map(size_type __n, const allocator_type& __a)
11520b57cec5SDimitry Andric      : unordered_map(__n, hasher(), key_equal(), __a) {}
1153cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI unordered_map(size_type __n, const hasher& __hf, const allocator_type& __a)
11540b57cec5SDimitry Andric      : unordered_map(__n, __hf, key_equal(), __a) {}
11550b57cec5SDimitry Andric  template <class _InputIterator>
11565f757f3fSDimitry Andric  _LIBCPP_HIDE_FROM_ABI
11570b57cec5SDimitry Andric  unordered_map(_InputIterator __first, _InputIterator __last, size_type __n, const allocator_type& __a)
11580b57cec5SDimitry Andric      : unordered_map(__first, __last, __n, hasher(), key_equal(), __a) {}
11590b57cec5SDimitry Andric  template <class _InputIterator>
1160cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI unordered_map(
1161cb14a3feSDimitry Andric      _InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, const allocator_type& __a)
11620b57cec5SDimitry Andric      : unordered_map(__first, __last, __n, __hf, key_equal(), __a) {}
116306c3fb27SDimitry Andric
116406c3fb27SDimitry Andric#  if _LIBCPP_STD_VER >= 23
116506c3fb27SDimitry Andric  template <_ContainerCompatibleRange<value_type> _Range>
1166cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI unordered_map(from_range_t, _Range&& __range, size_type __n, const allocator_type& __a)
116706c3fb27SDimitry Andric      : unordered_map(from_range, std::forward<_Range>(__range), __n, hasher(), key_equal(), __a) {}
116806c3fb27SDimitry Andric
116906c3fb27SDimitry Andric  template <_ContainerCompatibleRange<value_type> _Range>
117006c3fb27SDimitry Andric  _LIBCPP_HIDE_FROM_ABI
117106c3fb27SDimitry Andric  unordered_map(from_range_t, _Range&& __range, size_type __n, const hasher& __hf, const allocator_type& __a)
117206c3fb27SDimitry Andric      : unordered_map(from_range, std::forward<_Range>(__range), __n, __hf, key_equal(), __a) {}
117306c3fb27SDimitry Andric#  endif
117406c3fb27SDimitry Andric
1175cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI unordered_map(initializer_list<value_type> __il, size_type __n, const allocator_type& __a)
11760b57cec5SDimitry Andric      : unordered_map(__il, __n, hasher(), key_equal(), __a) {}
11775f757f3fSDimitry Andric  _LIBCPP_HIDE_FROM_ABI
1178cb14a3feSDimitry Andric  unordered_map(initializer_list<value_type> __il, size_type __n, const hasher& __hf, const allocator_type& __a)
11790b57cec5SDimitry Andric      : unordered_map(__il, __n, __hf, key_equal(), __a) {}
11800b57cec5SDimitry Andric#endif
1181cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI ~unordered_map() {
1182bdd1243dSDimitry Andric    static_assert(sizeof(std::__diagnose_unordered_container_requirements<_Key, _Hash, _Pred>(0)), "");
11830b57cec5SDimitry Andric  }
11840b57cec5SDimitry Andric
1185cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI unordered_map& operator=(const unordered_map& __u) {
11860b57cec5SDimitry Andric#ifndef _LIBCPP_CXX03_LANG
11870b57cec5SDimitry Andric    __table_ = __u.__table_;
11880b57cec5SDimitry Andric#else
11895f757f3fSDimitry Andric    if (this != std::addressof(__u)) {
11900b57cec5SDimitry Andric      __table_.clear();
11910b57cec5SDimitry Andric      __table_.hash_function()   = __u.__table_.hash_function();
11920b57cec5SDimitry Andric      __table_.key_eq()          = __u.__table_.key_eq();
11930b57cec5SDimitry Andric      __table_.max_load_factor() = __u.__table_.max_load_factor();
11940b57cec5SDimitry Andric      __table_.__copy_assign_alloc(__u.__table_);
11950b57cec5SDimitry Andric      insert(__u.begin(), __u.end());
11960b57cec5SDimitry Andric    }
11970b57cec5SDimitry Andric#endif
11980b57cec5SDimitry Andric    return *this;
11990b57cec5SDimitry Andric  }
12000b57cec5SDimitry Andric#ifndef _LIBCPP_CXX03_LANG
1201cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI unordered_map& operator=(unordered_map&& __u)
12020b57cec5SDimitry Andric      _NOEXCEPT_(is_nothrow_move_assignable<__table>::value);
1203cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI unordered_map& operator=(initializer_list<value_type> __il);
12040b57cec5SDimitry Andric#endif // _LIBCPP_CXX03_LANG
12050b57cec5SDimitry Andric
1206cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const _NOEXCEPT {
1207cb14a3feSDimitry Andric    return allocator_type(__table_.__node_alloc());
12080b57cec5SDimitry Andric  }
12090b57cec5SDimitry Andric
1210cb14a3feSDimitry Andric  _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_HIDE_FROM_ABI bool empty() const _NOEXCEPT { return __table_.size() == 0; }
1211cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI size_type size() const _NOEXCEPT { return __table_.size(); }
1212cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI size_type max_size() const _NOEXCEPT { return __table_.max_size(); }
1213cb14a3feSDimitry Andric
1214cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI iterator begin() _NOEXCEPT { return __table_.begin(); }
1215cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI iterator end() _NOEXCEPT { return __table_.end(); }
1216cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI const_iterator begin() const _NOEXCEPT { return __table_.begin(); }
1217cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI const_iterator end() const _NOEXCEPT { return __table_.end(); }
1218cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI const_iterator cbegin() const _NOEXCEPT { return __table_.begin(); }
1219cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI const_iterator cend() const _NOEXCEPT { return __table_.end(); }
1220cb14a3feSDimitry Andric
1221cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert(const value_type& __x) { return __table_.__insert_unique(__x); }
1222cb14a3feSDimitry Andric
1223cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator, const value_type& __x) { return insert(__x).first; }
1224cb14a3feSDimitry Andric
12250b57cec5SDimitry Andric  template <class _InputIterator>
1226cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI void insert(_InputIterator __first, _InputIterator __last);
12270b57cec5SDimitry Andric
122806c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 23
122906c3fb27SDimitry Andric  template <_ContainerCompatibleRange<value_type> _Range>
1230cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI void insert_range(_Range&& __range) {
123106c3fb27SDimitry Andric    for (auto&& __element : __range) {
123206c3fb27SDimitry Andric      __table_.__insert_unique(std::forward<decltype(__element)>(__element));
123306c3fb27SDimitry Andric    }
123406c3fb27SDimitry Andric  }
123506c3fb27SDimitry Andric#endif
123606c3fb27SDimitry Andric
12370b57cec5SDimitry Andric#ifndef _LIBCPP_CXX03_LANG
1238cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI void insert(initializer_list<value_type> __il) { insert(__il.begin(), __il.end()); }
12390b57cec5SDimitry Andric
1240cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert(value_type&& __x) {
1241cb14a3feSDimitry Andric    return __table_.__insert_unique(std::move(__x));
1242cb14a3feSDimitry Andric  }
12430b57cec5SDimitry Andric
124406c3fb27SDimitry Andric  _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator, value_type&& __x) {
12455f757f3fSDimitry Andric    return __table_.__insert_unique(std::move(__x)).first;
12460b57cec5SDimitry Andric  }
12470b57cec5SDimitry Andric
1248cb14a3feSDimitry Andric  template <class _Pp, class = __enable_if_t<is_constructible<value_type, _Pp>::value> >
1249cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert(_Pp&& __x) {
1250cb14a3feSDimitry Andric    return __table_.__insert_unique(std::forward<_Pp>(__x));
1251cb14a3feSDimitry Andric  }
12520b57cec5SDimitry Andric
1253cb14a3feSDimitry Andric  template <class _Pp, class = __enable_if_t<is_constructible<value_type, _Pp>::value> >
1254cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator, _Pp&& __x) {
12555f757f3fSDimitry Andric    return insert(std::forward<_Pp>(__x)).first;
12560b57cec5SDimitry Andric  }
12570b57cec5SDimitry Andric
12580b57cec5SDimitry Andric  template <class... _Args>
1259cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> emplace(_Args&&... __args) {
12605f757f3fSDimitry Andric    return __table_.__emplace_unique(std::forward<_Args>(__args)...);
12610b57cec5SDimitry Andric  }
12620b57cec5SDimitry Andric
12630b57cec5SDimitry Andric  template <class... _Args>
1264cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI iterator emplace_hint(const_iterator, _Args&&... __args) {
12655f757f3fSDimitry Andric    return __table_.__emplace_unique(std::forward<_Args>(__args)...).first;
12660b57cec5SDimitry Andric  }
12670b57cec5SDimitry Andric
12680b57cec5SDimitry Andric#endif // _LIBCPP_CXX03_LANG
12690b57cec5SDimitry Andric
127006c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 17
12710b57cec5SDimitry Andric  template <class... _Args>
1272cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> try_emplace(const key_type& __k, _Args&&... __args) {
1273cb14a3feSDimitry Andric    return __table_.__emplace_unique_key_args(
1274cb14a3feSDimitry Andric        __k, piecewise_construct, std::forward_as_tuple(__k), std::forward_as_tuple(std::forward<_Args>(__args)...));
12750b57cec5SDimitry Andric  }
12760b57cec5SDimitry Andric
12770b57cec5SDimitry Andric  template <class... _Args>
1278cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> try_emplace(key_type&& __k, _Args&&... __args) {
1279cb14a3feSDimitry Andric    return __table_.__emplace_unique_key_args(
1280cb14a3feSDimitry Andric        __k,
1281cb14a3feSDimitry Andric        piecewise_construct,
12825f757f3fSDimitry Andric        std::forward_as_tuple(std::move(__k)),
12835f757f3fSDimitry Andric        std::forward_as_tuple(std::forward<_Args>(__args)...));
12840b57cec5SDimitry Andric  }
12850b57cec5SDimitry Andric
12860b57cec5SDimitry Andric  template <class... _Args>
1287cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI iterator try_emplace(const_iterator, const key_type& __k, _Args&&... __args) {
12885f757f3fSDimitry Andric    return try_emplace(__k, std::forward<_Args>(__args)...).first;
12890b57cec5SDimitry Andric  }
12900b57cec5SDimitry Andric
12910b57cec5SDimitry Andric  template <class... _Args>
1292cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI iterator try_emplace(const_iterator, key_type&& __k, _Args&&... __args) {
12935f757f3fSDimitry Andric    return try_emplace(std::move(__k), std::forward<_Args>(__args)...).first;
12940b57cec5SDimitry Andric  }
12950b57cec5SDimitry Andric
12960b57cec5SDimitry Andric  template <class _Vp>
1297cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert_or_assign(const key_type& __k, _Vp&& __v) {
1298cb14a3feSDimitry Andric    pair<iterator, bool> __res = __table_.__emplace_unique_key_args(__k, __k, std::forward<_Vp>(__v));
12990b57cec5SDimitry Andric    if (!__res.second) {
13005f757f3fSDimitry Andric      __res.first->second = std::forward<_Vp>(__v);
13010b57cec5SDimitry Andric    }
13020b57cec5SDimitry Andric    return __res;
13030b57cec5SDimitry Andric  }
13040b57cec5SDimitry Andric
13050b57cec5SDimitry Andric  template <class _Vp>
1306cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert_or_assign(key_type&& __k, _Vp&& __v) {
1307cb14a3feSDimitry Andric    pair<iterator, bool> __res = __table_.__emplace_unique_key_args(__k, std::move(__k), std::forward<_Vp>(__v));
13080b57cec5SDimitry Andric    if (!__res.second) {
13095f757f3fSDimitry Andric      __res.first->second = std::forward<_Vp>(__v);
13100b57cec5SDimitry Andric    }
13110b57cec5SDimitry Andric    return __res;
13120b57cec5SDimitry Andric  }
13130b57cec5SDimitry Andric
13140b57cec5SDimitry Andric  template <class _Vp>
1315cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI iterator insert_or_assign(const_iterator, const key_type& __k, _Vp&& __v) {
13165f757f3fSDimitry Andric    return insert_or_assign(__k, std::forward<_Vp>(__v)).first;
13170b57cec5SDimitry Andric  }
13180b57cec5SDimitry Andric
13190b57cec5SDimitry Andric  template <class _Vp>
1320cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI iterator insert_or_assign(const_iterator, key_type&& __k, _Vp&& __v) {
13215f757f3fSDimitry Andric    return insert_or_assign(std::move(__k), std::forward<_Vp>(__v)).first;
13220b57cec5SDimitry Andric  }
132306c3fb27SDimitry Andric#endif // _LIBCPP_STD_VER >= 17
13240b57cec5SDimitry Andric
1325cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __p) { return __table_.erase(__p.__i_); }
1326cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI iterator erase(iterator __p) { return __table_.erase(__p.__i_); }
1327cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI size_type erase(const key_type& __k) { return __table_.__erase_unique(__k); }
1328cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __first, const_iterator __last) {
1329cb14a3feSDimitry Andric    return __table_.erase(__first.__i_, __last.__i_);
1330cb14a3feSDimitry Andric  }
1331cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT { __table_.clear(); }
13320b57cec5SDimitry Andric
133306c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 17
1334cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI insert_return_type insert(node_type&& __nh) {
133506c3fb27SDimitry Andric    _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(),
13360b57cec5SDimitry Andric                                        "node_type with incompatible allocator passed to unordered_map::insert()");
1337cb14a3feSDimitry Andric    return __table_.template __node_handle_insert_unique< node_type, insert_return_type>(std::move(__nh));
13380b57cec5SDimitry Andric  }
1339cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __hint, node_type&& __nh) {
134006c3fb27SDimitry Andric    _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(),
13410b57cec5SDimitry Andric                                        "node_type with incompatible allocator passed to unordered_map::insert()");
1342cb14a3feSDimitry Andric    return __table_.template __node_handle_insert_unique<node_type>(__hint.__i_, std::move(__nh));
13430b57cec5SDimitry Andric  }
1344cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI node_type extract(key_type const& __key) {
13450b57cec5SDimitry Andric    return __table_.template __node_handle_extract<node_type>(__key);
13460b57cec5SDimitry Andric  }
1347cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI node_type extract(const_iterator __it) {
1348cb14a3feSDimitry Andric    return __table_.template __node_handle_extract<node_type>(__it.__i_);
13490b57cec5SDimitry Andric  }
13500b57cec5SDimitry Andric
13510b57cec5SDimitry Andric  template <class _H2, class _P2>
1352cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI void merge(unordered_map<key_type, mapped_type, _H2, _P2, allocator_type>& __source) {
1353cb14a3feSDimitry Andric    _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
1354cb14a3feSDimitry Andric        __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
13550b57cec5SDimitry Andric    return __table_.__node_handle_merge_unique(__source.__table_);
13560b57cec5SDimitry Andric  }
13570b57cec5SDimitry Andric  template <class _H2, class _P2>
1358cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI void merge(unordered_map<key_type, mapped_type, _H2, _P2, allocator_type>&& __source) {
1359cb14a3feSDimitry Andric    _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
1360cb14a3feSDimitry Andric        __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
13610b57cec5SDimitry Andric    return __table_.__node_handle_merge_unique(__source.__table_);
13620b57cec5SDimitry Andric  }
13630b57cec5SDimitry Andric  template <class _H2, class _P2>
1364cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI void merge(unordered_multimap<key_type, mapped_type, _H2, _P2, allocator_type>& __source) {
1365cb14a3feSDimitry Andric    _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
1366cb14a3feSDimitry Andric        __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
13670b57cec5SDimitry Andric    return __table_.__node_handle_merge_unique(__source.__table_);
13680b57cec5SDimitry Andric  }
13690b57cec5SDimitry Andric  template <class _H2, class _P2>
1370cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI void merge(unordered_multimap<key_type, mapped_type, _H2, _P2, allocator_type>&& __source) {
1371cb14a3feSDimitry Andric    _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
1372cb14a3feSDimitry Andric        __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
13730b57cec5SDimitry Andric    return __table_.__node_handle_merge_unique(__source.__table_);
13740b57cec5SDimitry Andric  }
13750b57cec5SDimitry Andric#endif
13760b57cec5SDimitry Andric
1377cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI void swap(unordered_map& __u) _NOEXCEPT_(__is_nothrow_swappable<__table>::value) {
1378cb14a3feSDimitry Andric    __table_.swap(__u.__table_);
1379cb14a3feSDimitry Andric  }
13800b57cec5SDimitry Andric
1381cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI hasher hash_function() const { return __table_.hash_function().hash_function(); }
1382cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI key_equal key_eq() const { return __table_.key_eq().key_eq(); }
13830b57cec5SDimitry Andric
1384cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI iterator find(const key_type& __k) { return __table_.find(__k); }
1385cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI const_iterator find(const key_type& __k) const { return __table_.find(__k); }
138606c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 20
1387cb14a3feSDimitry Andric  template <class _K2,
1388cb14a3feSDimitry Andric            enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr>
1389cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI iterator find(const _K2& __k) {
1390cb14a3feSDimitry Andric    return __table_.find(__k);
1391cb14a3feSDimitry Andric  }
1392cb14a3feSDimitry Andric  template <class _K2,
1393cb14a3feSDimitry Andric            enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr>
1394cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI const_iterator find(const _K2& __k) const {
1395cb14a3feSDimitry Andric    return __table_.find(__k);
1396cb14a3feSDimitry Andric  }
139706c3fb27SDimitry Andric#endif // _LIBCPP_STD_VER >= 20
1398e8d8bef9SDimitry Andric
1399cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI size_type count(const key_type& __k) const { return __table_.__count_unique(__k); }
140006c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 20
1401cb14a3feSDimitry Andric  template <class _K2,
1402cb14a3feSDimitry Andric            enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr>
1403cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI size_type count(const _K2& __k) const {
1404cb14a3feSDimitry Andric    return __table_.__count_unique(__k);
1405cb14a3feSDimitry Andric  }
140606c3fb27SDimitry Andric#endif // _LIBCPP_STD_VER >= 20
1407349cc55cSDimitry Andric
140806c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 20
1409cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI bool contains(const key_type& __k) const { return find(__k) != end(); }
1410e8d8bef9SDimitry Andric
1411cb14a3feSDimitry Andric  template <class _K2,
1412cb14a3feSDimitry Andric            enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr>
1413cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI bool contains(const _K2& __k) const {
1414cb14a3feSDimitry Andric    return find(__k) != end();
1415cb14a3feSDimitry Andric  }
141606c3fb27SDimitry Andric#endif // _LIBCPP_STD_VER >= 20
1417349cc55cSDimitry Andric
1418cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const key_type& __k) {
1419cb14a3feSDimitry Andric    return __table_.__equal_range_unique(__k);
1420cb14a3feSDimitry Andric  }
1421cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const key_type& __k) const {
1422cb14a3feSDimitry Andric    return __table_.__equal_range_unique(__k);
1423cb14a3feSDimitry Andric  }
142406c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 20
1425cb14a3feSDimitry Andric  template <class _K2,
1426cb14a3feSDimitry Andric            enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr>
1427cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const _K2& __k) {
1428cb14a3feSDimitry Andric    return __table_.__equal_range_unique(__k);
1429cb14a3feSDimitry Andric  }
1430cb14a3feSDimitry Andric  template <class _K2,
1431cb14a3feSDimitry Andric            enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr>
1432cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const _K2& __k) const {
1433cb14a3feSDimitry Andric    return __table_.__equal_range_unique(__k);
1434cb14a3feSDimitry Andric  }
143506c3fb27SDimitry Andric#endif // _LIBCPP_STD_VER >= 20
14360b57cec5SDimitry Andric
143706c3fb27SDimitry Andric  _LIBCPP_HIDE_FROM_ABI mapped_type& operator[](const key_type& __k);
14380b57cec5SDimitry Andric#ifndef _LIBCPP_CXX03_LANG
143906c3fb27SDimitry Andric  _LIBCPP_HIDE_FROM_ABI mapped_type& operator[](key_type&& __k);
14400b57cec5SDimitry Andric#endif
14410b57cec5SDimitry Andric
144206c3fb27SDimitry Andric  _LIBCPP_HIDE_FROM_ABI mapped_type& at(const key_type& __k);
144306c3fb27SDimitry Andric  _LIBCPP_HIDE_FROM_ABI const mapped_type& at(const key_type& __k) const;
14440b57cec5SDimitry Andric
1445cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI size_type bucket_count() const _NOEXCEPT { return __table_.bucket_count(); }
1446cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI size_type max_bucket_count() const _NOEXCEPT { return __table_.max_bucket_count(); }
14470b57cec5SDimitry Andric
1448cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI size_type bucket_size(size_type __n) const { return __table_.bucket_size(__n); }
1449cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI size_type bucket(const key_type& __k) const { return __table_.bucket(__k); }
14500b57cec5SDimitry Andric
1451cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI local_iterator begin(size_type __n) { return __table_.begin(__n); }
1452cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI local_iterator end(size_type __n) { return __table_.end(__n); }
1453cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI const_local_iterator begin(size_type __n) const { return __table_.cbegin(__n); }
1454cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI const_local_iterator end(size_type __n) const { return __table_.cend(__n); }
1455cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI const_local_iterator cbegin(size_type __n) const { return __table_.cbegin(__n); }
1456cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI const_local_iterator cend(size_type __n) const { return __table_.cend(__n); }
14570b57cec5SDimitry Andric
1458cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI float load_factor() const _NOEXCEPT { return __table_.load_factor(); }
1459cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI float max_load_factor() const _NOEXCEPT { return __table_.max_load_factor(); }
1460cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI void max_load_factor(float __mlf) { __table_.max_load_factor(__mlf); }
1461cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI void rehash(size_type __n) { __table_.__rehash_unique(__n); }
1462cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI void reserve(size_type __n) { __table_.__reserve_unique(__n); }
14630b57cec5SDimitry Andric
14640b57cec5SDimitry Andricprivate:
14650b57cec5SDimitry Andric#ifdef _LIBCPP_CXX03_LANG
146606c3fb27SDimitry Andric  _LIBCPP_HIDE_FROM_ABI __node_holder __construct_node_with_key(const key_type& __k);
14670b57cec5SDimitry Andric#endif
14680b57cec5SDimitry Andric};
14690b57cec5SDimitry Andric
1470349cc55cSDimitry Andric#if _LIBCPP_STD_VER >= 17
14710b57cec5SDimitry Andrictemplate <class _InputIterator,
14720b57cec5SDimitry Andric          class _Hash      = hash<__iter_key_type<_InputIterator>>,
14730b57cec5SDimitry Andric          class _Pred      = equal_to<__iter_key_type<_InputIterator>>,
14740b57cec5SDimitry Andric          class _Allocator = allocator<__iter_to_alloc_type<_InputIterator>>,
147506c3fb27SDimitry Andric          class            = enable_if_t<__has_input_iterator_category<_InputIterator>::value>,
1476349cc55cSDimitry Andric          class            = enable_if_t<!__is_allocator<_Hash>::value>,
1477349cc55cSDimitry Andric          class            = enable_if_t<!is_integral<_Hash>::value>,
1478349cc55cSDimitry Andric          class            = enable_if_t<!__is_allocator<_Pred>::value>,
1479349cc55cSDimitry Andric          class            = enable_if_t<__is_allocator<_Allocator>::value>>
1480cb14a3feSDimitry Andricunordered_map(_InputIterator,
1481cb14a3feSDimitry Andric              _InputIterator,
1482cb14a3feSDimitry Andric              typename allocator_traits<_Allocator>::size_type = 0,
1483cb14a3feSDimitry Andric              _Hash                                            = _Hash(),
1484cb14a3feSDimitry Andric              _Pred                                            = _Pred(),
1485cb14a3feSDimitry Andric              _Allocator                                       = _Allocator())
14860b57cec5SDimitry Andric    -> unordered_map<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>, _Hash, _Pred, _Allocator>;
14870b57cec5SDimitry Andric
148806c3fb27SDimitry Andric#  if _LIBCPP_STD_VER >= 23
148906c3fb27SDimitry Andrictemplate <ranges::input_range _Range,
149006c3fb27SDimitry Andric          class _Hash      = hash<__range_key_type<_Range>>,
149106c3fb27SDimitry Andric          class _Pred      = equal_to<__range_key_type<_Range>>,
149206c3fb27SDimitry Andric          class _Allocator = allocator<__range_to_alloc_type<_Range>>,
149306c3fb27SDimitry Andric          class            = enable_if_t<!__is_allocator<_Hash>::value>,
149406c3fb27SDimitry Andric          class            = enable_if_t<!is_integral<_Hash>::value>,
149506c3fb27SDimitry Andric          class            = enable_if_t<!__is_allocator<_Pred>::value>,
149606c3fb27SDimitry Andric          class            = enable_if_t<__is_allocator<_Allocator>::value>>
1497cb14a3feSDimitry Andricunordered_map(from_range_t,
1498cb14a3feSDimitry Andric              _Range&&,
1499cb14a3feSDimitry Andric              typename allocator_traits<_Allocator>::size_type = 0,
1500cb14a3feSDimitry Andric              _Hash                                            = _Hash(),
1501cb14a3feSDimitry Andric              _Pred                                            = _Pred(),
1502cb14a3feSDimitry Andric              _Allocator                                       = _Allocator())
150306c3fb27SDimitry Andric    -> unordered_map<__range_key_type<_Range>, __range_mapped_type<_Range>, _Hash, _Pred, _Allocator>; // C++23
150406c3fb27SDimitry Andric#  endif
150506c3fb27SDimitry Andric
1506cb14a3feSDimitry Andrictemplate <class _Key,
1507cb14a3feSDimitry Andric          class _Tp,
1508cb14a3feSDimitry Andric          class _Hash      = hash<remove_const_t<_Key>>,
15090b57cec5SDimitry Andric          class _Pred      = equal_to<remove_const_t<_Key>>,
15100b57cec5SDimitry Andric          class _Allocator = allocator<pair<const _Key, _Tp>>,
1511349cc55cSDimitry Andric          class            = enable_if_t<!__is_allocator<_Hash>::value>,
1512349cc55cSDimitry Andric          class            = enable_if_t<!is_integral<_Hash>::value>,
1513349cc55cSDimitry Andric          class            = enable_if_t<!__is_allocator<_Pred>::value>,
1514349cc55cSDimitry Andric          class            = enable_if_t<__is_allocator<_Allocator>::value>>
1515cb14a3feSDimitry Andricunordered_map(initializer_list<pair<_Key, _Tp>>,
1516cb14a3feSDimitry Andric              typename allocator_traits<_Allocator>::size_type = 0,
1517cb14a3feSDimitry Andric              _Hash                                            = _Hash(),
1518cb14a3feSDimitry Andric              _Pred                                            = _Pred(),
1519cb14a3feSDimitry Andric              _Allocator = _Allocator()) -> unordered_map<remove_const_t<_Key>, _Tp, _Hash, _Pred, _Allocator>;
15200b57cec5SDimitry Andric
1521cb14a3feSDimitry Andrictemplate <class _InputIterator,
1522cb14a3feSDimitry Andric          class _Allocator,
152306c3fb27SDimitry Andric          class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>,
1524349cc55cSDimitry Andric          class = enable_if_t<__is_allocator<_Allocator>::value>>
15250b57cec5SDimitry Andricunordered_map(_InputIterator, _InputIterator, typename allocator_traits<_Allocator>::size_type, _Allocator)
1526cb14a3feSDimitry Andric    -> unordered_map<__iter_key_type<_InputIterator>,
1527cb14a3feSDimitry Andric                     __iter_mapped_type<_InputIterator>,
1528cb14a3feSDimitry Andric                     hash<__iter_key_type<_InputIterator>>,
1529cb14a3feSDimitry Andric                     equal_to<__iter_key_type<_InputIterator>>,
1530cb14a3feSDimitry Andric                     _Allocator>;
15310b57cec5SDimitry Andric
1532cb14a3feSDimitry Andrictemplate <class _InputIterator,
1533cb14a3feSDimitry Andric          class _Allocator,
153406c3fb27SDimitry Andric          class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>,
1535349cc55cSDimitry Andric          class = enable_if_t<__is_allocator<_Allocator>::value>>
15360b57cec5SDimitry Andricunordered_map(_InputIterator, _InputIterator, _Allocator)
1537cb14a3feSDimitry Andric    -> unordered_map<__iter_key_type<_InputIterator>,
1538cb14a3feSDimitry Andric                     __iter_mapped_type<_InputIterator>,
1539cb14a3feSDimitry Andric                     hash<__iter_key_type<_InputIterator>>,
1540cb14a3feSDimitry Andric                     equal_to<__iter_key_type<_InputIterator>>,
1541cb14a3feSDimitry Andric                     _Allocator>;
15420b57cec5SDimitry Andric
1543cb14a3feSDimitry Andrictemplate <class _InputIterator,
1544cb14a3feSDimitry Andric          class _Hash,
1545cb14a3feSDimitry Andric          class _Allocator,
154606c3fb27SDimitry Andric          class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>,
1547349cc55cSDimitry Andric          class = enable_if_t<!__is_allocator<_Hash>::value>,
1548349cc55cSDimitry Andric          class = enable_if_t<!is_integral<_Hash>::value>,
1549349cc55cSDimitry Andric          class = enable_if_t<__is_allocator<_Allocator>::value>>
15500b57cec5SDimitry Andricunordered_map(_InputIterator, _InputIterator, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator)
1551cb14a3feSDimitry Andric    -> unordered_map<__iter_key_type<_InputIterator>,
1552cb14a3feSDimitry Andric                     __iter_mapped_type<_InputIterator>,
1553cb14a3feSDimitry Andric                     _Hash,
1554cb14a3feSDimitry Andric                     equal_to<__iter_key_type<_InputIterator>>,
1555cb14a3feSDimitry Andric                     _Allocator>;
15560b57cec5SDimitry Andric
155706c3fb27SDimitry Andric#  if _LIBCPP_STD_VER >= 23
155806c3fb27SDimitry Andric
1559cb14a3feSDimitry Andrictemplate <ranges::input_range _Range, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value>>
156006c3fb27SDimitry Andricunordered_map(from_range_t, _Range&&, typename allocator_traits<_Allocator>::size_type, _Allocator)
1561cb14a3feSDimitry Andric    -> unordered_map<__range_key_type<_Range>,
1562cb14a3feSDimitry Andric                     __range_mapped_type<_Range>,
1563cb14a3feSDimitry Andric                     hash<__range_key_type<_Range>>,
1564cb14a3feSDimitry Andric                     equal_to<__range_key_type<_Range>>,
1565cb14a3feSDimitry Andric                     _Allocator>;
156606c3fb27SDimitry Andric
1567cb14a3feSDimitry Andrictemplate <ranges::input_range _Range, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value>>
156806c3fb27SDimitry Andricunordered_map(from_range_t, _Range&&, _Allocator)
1569cb14a3feSDimitry Andric    -> unordered_map<__range_key_type<_Range>,
1570cb14a3feSDimitry Andric                     __range_mapped_type<_Range>,
1571cb14a3feSDimitry Andric                     hash<__range_key_type<_Range>>,
1572cb14a3feSDimitry Andric                     equal_to<__range_key_type<_Range>>,
1573cb14a3feSDimitry Andric                     _Allocator>;
157406c3fb27SDimitry Andric
1575cb14a3feSDimitry Andrictemplate <ranges::input_range _Range,
1576cb14a3feSDimitry Andric          class _Hash,
1577cb14a3feSDimitry Andric          class _Allocator,
157806c3fb27SDimitry Andric          class = enable_if_t<!__is_allocator<_Hash>::value>,
157906c3fb27SDimitry Andric          class = enable_if_t<!is_integral<_Hash>::value>,
158006c3fb27SDimitry Andric          class = enable_if_t<__is_allocator<_Allocator>::value>>
158106c3fb27SDimitry Andricunordered_map(from_range_t, _Range&&, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator)
1582cb14a3feSDimitry Andric    -> unordered_map<__range_key_type<_Range>,
1583cb14a3feSDimitry Andric                     __range_mapped_type<_Range>,
1584cb14a3feSDimitry Andric                     _Hash,
1585cb14a3feSDimitry Andric                     equal_to<__range_key_type<_Range>>,
1586cb14a3feSDimitry Andric                     _Allocator>;
158706c3fb27SDimitry Andric
158806c3fb27SDimitry Andric#  endif
158906c3fb27SDimitry Andric
1590cb14a3feSDimitry Andrictemplate <class _Key, class _Tp, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value>>
15910b57cec5SDimitry Andricunordered_map(initializer_list<pair<_Key, _Tp>>, typename allocator_traits<_Allocator>::size_type, _Allocator)
1592cb14a3feSDimitry Andric    -> unordered_map<remove_const_t<_Key>, _Tp, hash<remove_const_t<_Key>>, equal_to<remove_const_t<_Key>>, _Allocator>;
15930b57cec5SDimitry Andric
1594cb14a3feSDimitry Andrictemplate <class _Key, class _Tp, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value>>
15950b57cec5SDimitry Andricunordered_map(initializer_list<pair<_Key, _Tp>>, _Allocator)
1596cb14a3feSDimitry Andric    -> unordered_map<remove_const_t<_Key>, _Tp, hash<remove_const_t<_Key>>, equal_to<remove_const_t<_Key>>, _Allocator>;
15970b57cec5SDimitry Andric
1598cb14a3feSDimitry Andrictemplate <class _Key,
1599cb14a3feSDimitry Andric          class _Tp,
1600cb14a3feSDimitry Andric          class _Hash,
1601cb14a3feSDimitry Andric          class _Allocator,
1602349cc55cSDimitry Andric          class = enable_if_t<!__is_allocator<_Hash>::value>,
1603349cc55cSDimitry Andric          class = enable_if_t<!is_integral<_Hash>::value>,
1604349cc55cSDimitry Andric          class = enable_if_t<__is_allocator<_Allocator>::value>>
16050b57cec5SDimitry Andricunordered_map(initializer_list<pair<_Key, _Tp>>, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator)
1606cb14a3feSDimitry Andric    -> unordered_map<remove_const_t<_Key>, _Tp, _Hash, equal_to<remove_const_t<_Key>>, _Allocator>;
16070b57cec5SDimitry Andric#endif
16080b57cec5SDimitry Andric
16090b57cec5SDimitry Andrictemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1610cb14a3feSDimitry Andricunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(size_type __n, const hasher& __hf, const key_equal& __eql)
1611cb14a3feSDimitry Andric    : __table_(__hf, __eql) {
1612753f127fSDimitry Andric  __table_.__rehash_unique(__n);
16130b57cec5SDimitry Andric}
16140b57cec5SDimitry Andric
16150b57cec5SDimitry Andrictemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
16160b57cec5SDimitry Andricunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1617cb14a3feSDimitry Andric    size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
1618cb14a3feSDimitry Andric    : __table_(__hf, __eql, typename __table::allocator_type(__a)) {
1619cb14a3feSDimitry Andric  __table_.__rehash_unique(__n);
1620cb14a3feSDimitry Andric}
1621cb14a3feSDimitry Andric
1622cb14a3feSDimitry Andrictemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1623cb14a3feSDimitry Andricinline unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(const allocator_type& __a)
1624cb14a3feSDimitry Andric    : __table_(typename __table::allocator_type(__a)) {}
1625cb14a3feSDimitry Andric
1626cb14a3feSDimitry Andrictemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1627cb14a3feSDimitry Andrictemplate <class _InputIterator>
1628cb14a3feSDimitry Andricunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(_InputIterator __first, _InputIterator __last) {
1629cb14a3feSDimitry Andric  insert(__first, __last);
1630cb14a3feSDimitry Andric}
1631cb14a3feSDimitry Andric
1632cb14a3feSDimitry Andrictemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1633cb14a3feSDimitry Andrictemplate <class _InputIterator>
1634cb14a3feSDimitry Andricunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1635cb14a3feSDimitry Andric    _InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, const key_equal& __eql)
1636cb14a3feSDimitry Andric    : __table_(__hf, __eql) {
1637cb14a3feSDimitry Andric  __table_.__rehash_unique(__n);
1638cb14a3feSDimitry Andric  insert(__first, __last);
1639cb14a3feSDimitry Andric}
1640cb14a3feSDimitry Andric
1641cb14a3feSDimitry Andrictemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1642cb14a3feSDimitry Andrictemplate <class _InputIterator>
1643cb14a3feSDimitry Andricunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1644cb14a3feSDimitry Andric    _InputIterator __first,
1645cb14a3feSDimitry Andric    _InputIterator __last,
1646cb14a3feSDimitry Andric    size_type __n,
1647cb14a3feSDimitry Andric    const hasher& __hf,
1648cb14a3feSDimitry Andric    const key_equal& __eql,
16490b57cec5SDimitry Andric    const allocator_type& __a)
1650cb14a3feSDimitry Andric    : __table_(__hf, __eql, typename __table::allocator_type(__a)) {
1651753f127fSDimitry Andric  __table_.__rehash_unique(__n);
16520b57cec5SDimitry Andric  insert(__first, __last);
16530b57cec5SDimitry Andric}
16540b57cec5SDimitry Andric
16550b57cec5SDimitry Andrictemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1656cb14a3feSDimitry Andricunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(const unordered_map& __u) : __table_(__u.__table_) {
1657753f127fSDimitry Andric  __table_.__rehash_unique(__u.bucket_count());
16580b57cec5SDimitry Andric  insert(__u.begin(), __u.end());
16590b57cec5SDimitry Andric}
16600b57cec5SDimitry Andric
16610b57cec5SDimitry Andrictemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1662cb14a3feSDimitry Andricunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(const unordered_map& __u, const allocator_type& __a)
1663cb14a3feSDimitry Andric    : __table_(__u.__table_, typename __table::allocator_type(__a)) {
1664753f127fSDimitry Andric  __table_.__rehash_unique(__u.bucket_count());
16650b57cec5SDimitry Andric  insert(__u.begin(), __u.end());
16660b57cec5SDimitry Andric}
16670b57cec5SDimitry Andric
16680b57cec5SDimitry Andric#ifndef _LIBCPP_CXX03_LANG
16690b57cec5SDimitry Andric
16700b57cec5SDimitry Andrictemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1671cb14a3feSDimitry Andricinline unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(unordered_map&& __u)
16720b57cec5SDimitry Andric    _NOEXCEPT_(is_nothrow_move_constructible<__table>::value)
1673cb14a3feSDimitry Andric    : __table_(std::move(__u.__table_)) {}
16740b57cec5SDimitry Andric
16750b57cec5SDimitry Andrictemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1676cb14a3feSDimitry Andricunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(unordered_map&& __u, const allocator_type& __a)
1677cb14a3feSDimitry Andric    : __table_(std::move(__u.__table_), typename __table::allocator_type(__a)) {
1678cb14a3feSDimitry Andric  if (__a != __u.get_allocator()) {
16790b57cec5SDimitry Andric    iterator __i = __u.begin();
16800b57cec5SDimitry Andric    while (__u.size() != 0) {
1681cb14a3feSDimitry Andric      __table_.__emplace_unique(__u.__table_.remove((__i++).__i_)->__get_value().__move());
16820b57cec5SDimitry Andric    }
16830b57cec5SDimitry Andric  }
16840b57cec5SDimitry Andric}
16850b57cec5SDimitry Andric
16860b57cec5SDimitry Andrictemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1687cb14a3feSDimitry Andricunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(initializer_list<value_type> __il) {
16880b57cec5SDimitry Andric  insert(__il.begin(), __il.end());
16890b57cec5SDimitry Andric}
16900b57cec5SDimitry Andric
16910b57cec5SDimitry Andrictemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
16920b57cec5SDimitry Andricunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1693cb14a3feSDimitry Andric    initializer_list<value_type> __il, size_type __n, const hasher& __hf, const key_equal& __eql)
1694cb14a3feSDimitry Andric    : __table_(__hf, __eql) {
1695753f127fSDimitry Andric  __table_.__rehash_unique(__n);
16960b57cec5SDimitry Andric  insert(__il.begin(), __il.end());
16970b57cec5SDimitry Andric}
16980b57cec5SDimitry Andric
16990b57cec5SDimitry Andrictemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
17000b57cec5SDimitry Andricunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(
1701cb14a3feSDimitry Andric    initializer_list<value_type> __il,
1702cb14a3feSDimitry Andric    size_type __n,
1703cb14a3feSDimitry Andric    const hasher& __hf,
1704cb14a3feSDimitry Andric    const key_equal& __eql,
1705cb14a3feSDimitry Andric    const allocator_type& __a)
1706cb14a3feSDimitry Andric    : __table_(__hf, __eql, typename __table::allocator_type(__a)) {
1707753f127fSDimitry Andric  __table_.__rehash_unique(__n);
17080b57cec5SDimitry Andric  insert(__il.begin(), __il.end());
17090b57cec5SDimitry Andric}
17100b57cec5SDimitry Andric
17110b57cec5SDimitry Andrictemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1712cb14a3feSDimitry Andricinline unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>&
17130b57cec5SDimitry Andricunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(unordered_map&& __u)
1714cb14a3feSDimitry Andric    _NOEXCEPT_(is_nothrow_move_assignable<__table>::value) {
17155f757f3fSDimitry Andric  __table_ = std::move(__u.__table_);
17160b57cec5SDimitry Andric  return *this;
17170b57cec5SDimitry Andric}
17180b57cec5SDimitry Andric
17190b57cec5SDimitry Andrictemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1720cb14a3feSDimitry Andricinline unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>&
1721cb14a3feSDimitry Andricunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(initializer_list<value_type> __il) {
17220b57cec5SDimitry Andric  __table_.__assign_unique(__il.begin(), __il.end());
17230b57cec5SDimitry Andric  return *this;
17240b57cec5SDimitry Andric}
17250b57cec5SDimitry Andric
17260b57cec5SDimitry Andric#endif // _LIBCPP_CXX03_LANG
17270b57cec5SDimitry Andric
17280b57cec5SDimitry Andrictemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
17290b57cec5SDimitry Andrictemplate <class _InputIterator>
1730cb14a3feSDimitry Andricinline void unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, _InputIterator __last) {
17310b57cec5SDimitry Andric  for (; __first != __last; ++__first)
17320b57cec5SDimitry Andric    __table_.__insert_unique(*__first);
17330b57cec5SDimitry Andric}
17340b57cec5SDimitry Andric
17350b57cec5SDimitry Andric#ifndef _LIBCPP_CXX03_LANG
17360b57cec5SDimitry Andric
17370b57cec5SDimitry Andrictemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1738cb14a3feSDimitry Andric_Tp& unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](const key_type& __k) {
1739cb14a3feSDimitry Andric  return __table_
1740cb14a3feSDimitry Andric      .__emplace_unique_key_args(__k, piecewise_construct, std::forward_as_tuple(__k), std::forward_as_tuple())
1741cb14a3feSDimitry Andric      .first->__get_value()
1742cb14a3feSDimitry Andric      .second;
17430b57cec5SDimitry Andric}
17440b57cec5SDimitry Andric
17450b57cec5SDimitry Andrictemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1746cb14a3feSDimitry Andric_Tp& unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](key_type&& __k) {
1747cb14a3feSDimitry Andric  return __table_
1748cb14a3feSDimitry Andric      .__emplace_unique_key_args(
1749cb14a3feSDimitry Andric          __k, piecewise_construct, std::forward_as_tuple(std::move(__k)), std::forward_as_tuple())
1750cb14a3feSDimitry Andric      .first->__get_value()
1751cb14a3feSDimitry Andric      .second;
17520b57cec5SDimitry Andric}
17530b57cec5SDimitry Andric#else // _LIBCPP_CXX03_LANG
17540b57cec5SDimitry Andric
17550b57cec5SDimitry Andrictemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
17560b57cec5SDimitry Andrictypename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder
1757cb14a3feSDimitry Andricunordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node_with_key(const key_type& __k) {
17580b57cec5SDimitry Andric  __node_allocator& __na = __table_.__node_alloc();
17590b57cec5SDimitry Andric  __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
17605f757f3fSDimitry Andric  __node_traits::construct(__na, std::addressof(__h->__get_value().__get_value().first), __k);
17610b57cec5SDimitry Andric  __h.get_deleter().__first_constructed = true;
17625f757f3fSDimitry Andric  __node_traits::construct(__na, std::addressof(__h->__get_value().__get_value().second));
17630b57cec5SDimitry Andric  __h.get_deleter().__second_constructed = true;
1764e8d8bef9SDimitry Andric  return __h;
17650b57cec5SDimitry Andric}
17660b57cec5SDimitry Andric
17670b57cec5SDimitry Andrictemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1768cb14a3feSDimitry Andric_Tp& unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](const key_type& __k) {
17690b57cec5SDimitry Andric  iterator __i = find(__k);
17700b57cec5SDimitry Andric  if (__i != end())
17710b57cec5SDimitry Andric    return __i->second;
17720b57cec5SDimitry Andric  __node_holder __h        = __construct_node_with_key(__k);
17730b57cec5SDimitry Andric  pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get());
17740b57cec5SDimitry Andric  __h.release();
17750b57cec5SDimitry Andric  return __r.first->second;
17760b57cec5SDimitry Andric}
17770b57cec5SDimitry Andric
1778fe6060f1SDimitry Andric#endif // _LIBCPP_CXX03_LANG
17790b57cec5SDimitry Andric
17800b57cec5SDimitry Andrictemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1781cb14a3feSDimitry Andric_Tp& unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::at(const key_type& __k) {
17820b57cec5SDimitry Andric  iterator __i = find(__k);
17830b57cec5SDimitry Andric  if (__i == end())
17840b57cec5SDimitry Andric    __throw_out_of_range("unordered_map::at: key not found");
17850b57cec5SDimitry Andric  return __i->second;
17860b57cec5SDimitry Andric}
17870b57cec5SDimitry Andric
17880b57cec5SDimitry Andrictemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1789cb14a3feSDimitry Andricconst _Tp& unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::at(const key_type& __k) const {
17900b57cec5SDimitry Andric  const_iterator __i = find(__k);
17910b57cec5SDimitry Andric  if (__i == end())
17920b57cec5SDimitry Andric    __throw_out_of_range("unordered_map::at: key not found");
17930b57cec5SDimitry Andric  return __i->second;
17940b57cec5SDimitry Andric}
17950b57cec5SDimitry Andric
17960b57cec5SDimitry Andrictemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1797cb14a3feSDimitry Andricinline _LIBCPP_HIDE_FROM_ABI void
1798cb14a3feSDimitry Andricswap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1799cb14a3feSDimitry Andric    _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) {
18000b57cec5SDimitry Andric  __x.swap(__y);
18010b57cec5SDimitry Andric}
18020b57cec5SDimitry Andric
180306c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 20
1804cb14a3feSDimitry Andrictemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc, class _Predicate>
1805cb14a3feSDimitry Andricinline _LIBCPP_HIDE_FROM_ABI typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::size_type
1806cb14a3feSDimitry Andricerase_if(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __c, _Predicate __pred) {
18075f757f3fSDimitry Andric  return std::__libcpp_erase_if_container(__c, __pred);
18085ffd83dbSDimitry Andric}
18090b57cec5SDimitry Andric#endif
18100b57cec5SDimitry Andric
18110b57cec5SDimitry Andrictemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1812cb14a3feSDimitry Andric_LIBCPP_HIDE_FROM_ABI bool operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1813cb14a3feSDimitry Andric                                      const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) {
18140b57cec5SDimitry Andric  if (__x.size() != __y.size())
18150b57cec5SDimitry Andric    return false;
1816cb14a3feSDimitry Andric  typedef typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator const_iterator;
1817cb14a3feSDimitry Andric  for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end(); __i != __ex; ++__i) {
18180b57cec5SDimitry Andric    const_iterator __j = __y.find(__i->first);
18190b57cec5SDimitry Andric    if (__j == __ey || !(*__i == *__j))
18200b57cec5SDimitry Andric      return false;
18210b57cec5SDimitry Andric  }
18220b57cec5SDimitry Andric  return true;
18230b57cec5SDimitry Andric}
18240b57cec5SDimitry Andric
182506c3fb27SDimitry Andric#if _LIBCPP_STD_VER <= 17
182606c3fb27SDimitry Andric
18270b57cec5SDimitry Andrictemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
1828cb14a3feSDimitry Andricinline _LIBCPP_HIDE_FROM_ABI bool operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1829cb14a3feSDimitry Andric                                             const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) {
18300b57cec5SDimitry Andric  return !(__x == __y);
18310b57cec5SDimitry Andric}
18320b57cec5SDimitry Andric
183306c3fb27SDimitry Andric#endif
183406c3fb27SDimitry Andric
1835cb14a3feSDimitry Andrictemplate <class _Key,
1836cb14a3feSDimitry Andric          class _Tp,
1837cb14a3feSDimitry Andric          class _Hash  = hash<_Key>,
1838cb14a3feSDimitry Andric          class _Pred  = equal_to<_Key>,
18390b57cec5SDimitry Andric          class _Alloc = allocator<pair<const _Key, _Tp> > >
1840cb14a3feSDimitry Andricclass _LIBCPP_TEMPLATE_VIS unordered_multimap {
18410b57cec5SDimitry Andricpublic:
18420b57cec5SDimitry Andric  // types
18430b57cec5SDimitry Andric  typedef _Key key_type;
18440b57cec5SDimitry Andric  typedef _Tp mapped_type;
184581ad6265SDimitry Andric  typedef __type_identity_t<_Hash> hasher;
184681ad6265SDimitry Andric  typedef __type_identity_t<_Pred> key_equal;
184781ad6265SDimitry Andric  typedef __type_identity_t<_Alloc> allocator_type;
18480b57cec5SDimitry Andric  typedef pair<const key_type, mapped_type> value_type;
18490b57cec5SDimitry Andric  typedef value_type& reference;
18500b57cec5SDimitry Andric  typedef const value_type& const_reference;
18510b57cec5SDimitry Andric  static_assert((is_same<value_type, typename allocator_type::value_type>::value),
185206c3fb27SDimitry Andric                "Allocator::value_type must be same type as value_type");
18530b57cec5SDimitry Andric
18540b57cec5SDimitry Andricprivate:
18550b57cec5SDimitry Andric  typedef __hash_value_type<key_type, mapped_type> __value_type;
1856e8d8bef9SDimitry Andric  typedef __unordered_map_hasher<key_type, __value_type, hasher, key_equal> __hasher;
1857e8d8bef9SDimitry Andric  typedef __unordered_map_equal<key_type, __value_type, key_equal, hasher> __key_equal;
1858bdd1243dSDimitry Andric  typedef __rebind_alloc<allocator_traits<allocator_type>, __value_type> __allocator_type;
18590b57cec5SDimitry Andric
1860cb14a3feSDimitry Andric  typedef __hash_table<__value_type, __hasher, __key_equal, __allocator_type> __table;
18610b57cec5SDimitry Andric
18620b57cec5SDimitry Andric  __table __table_;
18630b57cec5SDimitry Andric
18640b57cec5SDimitry Andric  typedef typename __table::_NodeTypes _NodeTypes;
18650b57cec5SDimitry Andric  typedef typename __table::__node_traits __node_traits;
18660b57cec5SDimitry Andric  typedef typename __table::__node_allocator __node_allocator;
18670b57cec5SDimitry Andric  typedef typename __table::__node __node;
18680b57cec5SDimitry Andric  typedef __hash_map_node_destructor<__node_allocator> _Dp;
18690b57cec5SDimitry Andric  typedef unique_ptr<__node, _Dp> __node_holder;
18700b57cec5SDimitry Andric  typedef allocator_traits<allocator_type> __alloc_traits;
1871cb14a3feSDimitry Andric  static_assert((is_same<typename __node_traits::size_type, typename __alloc_traits::size_type>::value),
18720b57cec5SDimitry Andric                "Allocator uses different size_type for different types");
1873bdd1243dSDimitry Andric
1874bdd1243dSDimitry Andric  static_assert(is_same<allocator_type, __rebind_alloc<__alloc_traits, value_type> >::value,
1875bdd1243dSDimitry Andric                "[allocator.requirements] states that rebinding an allocator to the same type should result in the "
1876bdd1243dSDimitry Andric                "original allocator");
1877bdd1243dSDimitry Andric
18780b57cec5SDimitry Andricpublic:
18790b57cec5SDimitry Andric  typedef typename __alloc_traits::pointer pointer;
18800b57cec5SDimitry Andric  typedef typename __alloc_traits::const_pointer const_pointer;
18810b57cec5SDimitry Andric  typedef typename __table::size_type size_type;
18820b57cec5SDimitry Andric  typedef typename __table::difference_type difference_type;
18830b57cec5SDimitry Andric
18840b57cec5SDimitry Andric  typedef __hash_map_iterator<typename __table::iterator> iterator;
18850b57cec5SDimitry Andric  typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator;
18860b57cec5SDimitry Andric  typedef __hash_map_iterator<typename __table::local_iterator> local_iterator;
18870b57cec5SDimitry Andric  typedef __hash_map_const_iterator<typename __table::const_local_iterator> const_local_iterator;
18880b57cec5SDimitry Andric
188906c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 17
18900b57cec5SDimitry Andric  typedef __map_node_handle<__node, allocator_type> node_type;
18910b57cec5SDimitry Andric#endif
18920b57cec5SDimitry Andric
18930b57cec5SDimitry Andric  template <class _Key2, class _Tp2, class _Hash2, class _Pred2, class _Alloc2>
18940b57cec5SDimitry Andric  friend class _LIBCPP_TEMPLATE_VIS unordered_map;
18950b57cec5SDimitry Andric  template <class _Key2, class _Tp2, class _Hash2, class _Pred2, class _Alloc2>
18960b57cec5SDimitry Andric  friend class _LIBCPP_TEMPLATE_VIS unordered_multimap;
18970b57cec5SDimitry Andric
1898cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI unordered_multimap() _NOEXCEPT_(is_nothrow_default_constructible<__table>::value) {}
1899cb14a3feSDimitry Andric  explicit _LIBCPP_HIDE_FROM_ABI
1900cb14a3feSDimitry Andric  unordered_multimap(size_type __n, const hasher& __hf = hasher(), const key_equal& __eql = key_equal());
19015f757f3fSDimitry Andric  _LIBCPP_HIDE_FROM_ABI
1902cb14a3feSDimitry Andric  unordered_multimap(size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a);
19030b57cec5SDimitry Andric  template <class _InputIterator>
190406c3fb27SDimitry Andric  _LIBCPP_HIDE_FROM_ABI unordered_multimap(_InputIterator __first, _InputIterator __last);
19050b57cec5SDimitry Andric  template <class _InputIterator>
1906cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI unordered_multimap(
1907cb14a3feSDimitry Andric      _InputIterator __first,
1908cb14a3feSDimitry Andric      _InputIterator __last,
1909cb14a3feSDimitry Andric      size_type __n,
1910cb14a3feSDimitry Andric      const hasher& __hf     = hasher(),
19110b57cec5SDimitry Andric      const key_equal& __eql = key_equal());
19120b57cec5SDimitry Andric  template <class _InputIterator>
1913cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI unordered_multimap(
1914cb14a3feSDimitry Andric      _InputIterator __first,
1915cb14a3feSDimitry Andric      _InputIterator __last,
1916cb14a3feSDimitry Andric      size_type __n,
1917cb14a3feSDimitry Andric      const hasher& __hf,
19180b57cec5SDimitry Andric      const key_equal& __eql,
19190b57cec5SDimitry Andric      const allocator_type& __a);
192006c3fb27SDimitry Andric
192106c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 23
192206c3fb27SDimitry Andric  template <_ContainerCompatibleRange<value_type> _Range>
1923cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI unordered_multimap(
1924cb14a3feSDimitry Andric      from_range_t,
1925cb14a3feSDimitry Andric      _Range&& __range,
1926cb14a3feSDimitry Andric      size_type __n             = /*implementation-defined*/ 0,
1927cb14a3feSDimitry Andric      const hasher& __hf        = hasher(),
1928cb14a3feSDimitry Andric      const key_equal& __eql    = key_equal(),
192906c3fb27SDimitry Andric      const allocator_type& __a = allocator_type())
193006c3fb27SDimitry Andric      : __table_(__hf, __eql, typename __table::allocator_type(__a)) {
193106c3fb27SDimitry Andric    if (__n > 0) {
193206c3fb27SDimitry Andric      __table_.__rehash_multi(__n);
193306c3fb27SDimitry Andric    }
193406c3fb27SDimitry Andric    insert_range(std::forward<_Range>(__range));
193506c3fb27SDimitry Andric  }
193606c3fb27SDimitry Andric#endif
193706c3fb27SDimitry Andric
1938cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI explicit unordered_multimap(const allocator_type& __a);
193906c3fb27SDimitry Andric  _LIBCPP_HIDE_FROM_ABI unordered_multimap(const unordered_multimap& __u);
194006c3fb27SDimitry Andric  _LIBCPP_HIDE_FROM_ABI unordered_multimap(const unordered_multimap& __u, const allocator_type& __a);
19410b57cec5SDimitry Andric#ifndef _LIBCPP_CXX03_LANG
1942cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI unordered_multimap(unordered_multimap&& __u)
19430b57cec5SDimitry Andric      _NOEXCEPT_(is_nothrow_move_constructible<__table>::value);
194406c3fb27SDimitry Andric  _LIBCPP_HIDE_FROM_ABI unordered_multimap(unordered_multimap&& __u, const allocator_type& __a);
194506c3fb27SDimitry Andric  _LIBCPP_HIDE_FROM_ABI unordered_multimap(initializer_list<value_type> __il);
1946cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI unordered_multimap(
1947cb14a3feSDimitry Andric      initializer_list<value_type> __il,
1948cb14a3feSDimitry Andric      size_type __n,
19490b57cec5SDimitry Andric      const hasher& __hf     = hasher(),
19500b57cec5SDimitry Andric      const key_equal& __eql = key_equal());
1951cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI unordered_multimap(
1952cb14a3feSDimitry Andric      initializer_list<value_type> __il,
1953cb14a3feSDimitry Andric      size_type __n,
1954cb14a3feSDimitry Andric      const hasher& __hf,
1955cb14a3feSDimitry Andric      const key_equal& __eql,
19560b57cec5SDimitry Andric      const allocator_type& __a);
19570b57cec5SDimitry Andric#endif // _LIBCPP_CXX03_LANG
195806c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 14
1959cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI unordered_multimap(size_type __n, const allocator_type& __a)
19600b57cec5SDimitry Andric      : unordered_multimap(__n, hasher(), key_equal(), __a) {}
1961cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI unordered_multimap(size_type __n, const hasher& __hf, const allocator_type& __a)
19620b57cec5SDimitry Andric      : unordered_multimap(__n, __hf, key_equal(), __a) {}
19630b57cec5SDimitry Andric  template <class _InputIterator>
19645f757f3fSDimitry Andric  _LIBCPP_HIDE_FROM_ABI
19650b57cec5SDimitry Andric  unordered_multimap(_InputIterator __first, _InputIterator __last, size_type __n, const allocator_type& __a)
19660b57cec5SDimitry Andric      : unordered_multimap(__first, __last, __n, hasher(), key_equal(), __a) {}
19670b57cec5SDimitry Andric  template <class _InputIterator>
1968cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI unordered_multimap(
1969cb14a3feSDimitry Andric      _InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, const allocator_type& __a)
19700b57cec5SDimitry Andric      : unordered_multimap(__first, __last, __n, __hf, key_equal(), __a) {}
197106c3fb27SDimitry Andric
197206c3fb27SDimitry Andric#  if _LIBCPP_STD_VER >= 23
197306c3fb27SDimitry Andric  template <_ContainerCompatibleRange<value_type> _Range>
1974cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI unordered_multimap(from_range_t, _Range&& __range, size_type __n, const allocator_type& __a)
197506c3fb27SDimitry Andric      : unordered_multimap(from_range, std::forward<_Range>(__range), __n, hasher(), key_equal(), __a) {}
197606c3fb27SDimitry Andric
197706c3fb27SDimitry Andric  template <_ContainerCompatibleRange<value_type> _Range>
197806c3fb27SDimitry Andric  _LIBCPP_HIDE_FROM_ABI
197906c3fb27SDimitry Andric  unordered_multimap(from_range_t, _Range&& __range, size_type __n, const hasher& __hf, const allocator_type& __a)
198006c3fb27SDimitry Andric      : unordered_multimap(from_range, std::forward<_Range>(__range), __n, __hf, key_equal(), __a) {}
198106c3fb27SDimitry Andric#  endif
198206c3fb27SDimitry Andric
1983cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI unordered_multimap(initializer_list<value_type> __il, size_type __n, const allocator_type& __a)
19840b57cec5SDimitry Andric      : unordered_multimap(__il, __n, hasher(), key_equal(), __a) {}
19855f757f3fSDimitry Andric  _LIBCPP_HIDE_FROM_ABI
1986cb14a3feSDimitry Andric  unordered_multimap(initializer_list<value_type> __il, size_type __n, const hasher& __hf, const allocator_type& __a)
19870b57cec5SDimitry Andric      : unordered_multimap(__il, __n, __hf, key_equal(), __a) {}
19880b57cec5SDimitry Andric#endif
1989cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI ~unordered_multimap() {
1990bdd1243dSDimitry Andric    static_assert(sizeof(std::__diagnose_unordered_container_requirements<_Key, _Hash, _Pred>(0)), "");
19910b57cec5SDimitry Andric  }
19920b57cec5SDimitry Andric
1993cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI unordered_multimap& operator=(const unordered_multimap& __u) {
19940b57cec5SDimitry Andric#ifndef _LIBCPP_CXX03_LANG
19950b57cec5SDimitry Andric    __table_ = __u.__table_;
19960b57cec5SDimitry Andric#else
19975f757f3fSDimitry Andric    if (this != std::addressof(__u)) {
19980b57cec5SDimitry Andric      __table_.clear();
19990b57cec5SDimitry Andric      __table_.hash_function()   = __u.__table_.hash_function();
20000b57cec5SDimitry Andric      __table_.key_eq()          = __u.__table_.key_eq();
20010b57cec5SDimitry Andric      __table_.max_load_factor() = __u.__table_.max_load_factor();
20020b57cec5SDimitry Andric      __table_.__copy_assign_alloc(__u.__table_);
20030b57cec5SDimitry Andric      insert(__u.begin(), __u.end());
20040b57cec5SDimitry Andric    }
20050b57cec5SDimitry Andric#endif
20060b57cec5SDimitry Andric    return *this;
20070b57cec5SDimitry Andric  }
20080b57cec5SDimitry Andric#ifndef _LIBCPP_CXX03_LANG
2009cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI unordered_multimap& operator=(unordered_multimap&& __u)
20100b57cec5SDimitry Andric      _NOEXCEPT_(is_nothrow_move_assignable<__table>::value);
2011cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI unordered_multimap& operator=(initializer_list<value_type> __il);
20120b57cec5SDimitry Andric#endif // _LIBCPP_CXX03_LANG
20130b57cec5SDimitry Andric
2014cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const _NOEXCEPT {
2015cb14a3feSDimitry Andric    return allocator_type(__table_.__node_alloc());
2016cb14a3feSDimitry Andric  }
20170b57cec5SDimitry Andric
2018cb14a3feSDimitry Andric  _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_HIDE_FROM_ABI bool empty() const _NOEXCEPT { return __table_.size() == 0; }
2019cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI size_type size() const _NOEXCEPT { return __table_.size(); }
2020cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI size_type max_size() const _NOEXCEPT { return __table_.max_size(); }
20210b57cec5SDimitry Andric
2022cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI iterator begin() _NOEXCEPT { return __table_.begin(); }
2023cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI iterator end() _NOEXCEPT { return __table_.end(); }
2024cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI const_iterator begin() const _NOEXCEPT { return __table_.begin(); }
2025cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI const_iterator end() const _NOEXCEPT { return __table_.end(); }
2026cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI const_iterator cbegin() const _NOEXCEPT { return __table_.begin(); }
2027cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI const_iterator cend() const _NOEXCEPT { return __table_.end(); }
20280b57cec5SDimitry Andric
2029cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI iterator insert(const value_type& __x) { return __table_.__insert_multi(__x); }
20300b57cec5SDimitry Andric
2031cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, const value_type& __x) {
2032cb14a3feSDimitry Andric    return __table_.__insert_multi(__p.__i_, __x);
2033cb14a3feSDimitry Andric  }
20340b57cec5SDimitry Andric
20350b57cec5SDimitry Andric  template <class _InputIterator>
2036cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI void insert(_InputIterator __first, _InputIterator __last);
20370b57cec5SDimitry Andric
203806c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 23
203906c3fb27SDimitry Andric  template <_ContainerCompatibleRange<value_type> _Range>
2040cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI void insert_range(_Range&& __range) {
204106c3fb27SDimitry Andric    for (auto&& __element : __range) {
204206c3fb27SDimitry Andric      __table_.__insert_multi(std::forward<decltype(__element)>(__element));
204306c3fb27SDimitry Andric    }
204406c3fb27SDimitry Andric  }
204506c3fb27SDimitry Andric#endif
204606c3fb27SDimitry Andric
20470b57cec5SDimitry Andric#ifndef _LIBCPP_CXX03_LANG
2048cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI void insert(initializer_list<value_type> __il) { insert(__il.begin(), __il.end()); }
2049cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI iterator insert(value_type&& __x) { return __table_.__insert_multi(std::move(__x)); }
20500b57cec5SDimitry Andric
2051cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, value_type&& __x) {
2052cb14a3feSDimitry Andric    return __table_.__insert_multi(__p.__i_, std::move(__x));
2053cb14a3feSDimitry Andric  }
20540b57cec5SDimitry Andric
2055cb14a3feSDimitry Andric  template <class _Pp, class = __enable_if_t<is_constructible<value_type, _Pp>::value> >
2056cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI iterator insert(_Pp&& __x) {
2057cb14a3feSDimitry Andric    return __table_.__insert_multi(std::forward<_Pp>(__x));
2058cb14a3feSDimitry Andric  }
20590b57cec5SDimitry Andric
2060cb14a3feSDimitry Andric  template <class _Pp, class = __enable_if_t<is_constructible<value_type, _Pp>::value> >
2061cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, _Pp&& __x) {
2062cb14a3feSDimitry Andric    return __table_.__insert_multi(__p.__i_, std::forward<_Pp>(__x));
2063cb14a3feSDimitry Andric  }
20640b57cec5SDimitry Andric
20650b57cec5SDimitry Andric  template <class... _Args>
206606c3fb27SDimitry Andric  _LIBCPP_HIDE_FROM_ABI iterator emplace(_Args&&... __args) {
20675f757f3fSDimitry Andric    return __table_.__emplace_multi(std::forward<_Args>(__args)...);
20680b57cec5SDimitry Andric  }
20690b57cec5SDimitry Andric
20700b57cec5SDimitry Andric  template <class... _Args>
207106c3fb27SDimitry Andric  _LIBCPP_HIDE_FROM_ABI iterator emplace_hint(const_iterator __p, _Args&&... __args) {
20725f757f3fSDimitry Andric    return __table_.__emplace_hint_multi(__p.__i_, std::forward<_Args>(__args)...);
20730b57cec5SDimitry Andric  }
20740b57cec5SDimitry Andric#endif // _LIBCPP_CXX03_LANG
20750b57cec5SDimitry Andric
2076cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __p) { return __table_.erase(__p.__i_); }
2077cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI iterator erase(iterator __p) { return __table_.erase(__p.__i_); }
2078cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI size_type erase(const key_type& __k) { return __table_.__erase_multi(__k); }
2079cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __first, const_iterator __last) {
2080cb14a3feSDimitry Andric    return __table_.erase(__first.__i_, __last.__i_);
2081cb14a3feSDimitry Andric  }
2082cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT { __table_.clear(); }
20830b57cec5SDimitry Andric
208406c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 17
2085cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI iterator insert(node_type&& __nh) {
208606c3fb27SDimitry Andric    _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(),
20870b57cec5SDimitry Andric                                        "node_type with incompatible allocator passed to unordered_multimap::insert()");
2088cb14a3feSDimitry Andric    return __table_.template __node_handle_insert_multi<node_type>(std::move(__nh));
20890b57cec5SDimitry Andric  }
2090cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __hint, node_type&& __nh) {
209106c3fb27SDimitry Andric    _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(),
20920b57cec5SDimitry Andric                                        "node_type with incompatible allocator passed to unordered_multimap::insert()");
2093cb14a3feSDimitry Andric    return __table_.template __node_handle_insert_multi<node_type>(__hint.__i_, std::move(__nh));
20940b57cec5SDimitry Andric  }
2095cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI node_type extract(key_type const& __key) {
20960b57cec5SDimitry Andric    return __table_.template __node_handle_extract<node_type>(__key);
20970b57cec5SDimitry Andric  }
2098cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI node_type extract(const_iterator __it) {
2099cb14a3feSDimitry Andric    return __table_.template __node_handle_extract<node_type>(__it.__i_);
21000b57cec5SDimitry Andric  }
21010b57cec5SDimitry Andric
21020b57cec5SDimitry Andric  template <class _H2, class _P2>
2103cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI void merge(unordered_multimap<key_type, mapped_type, _H2, _P2, allocator_type>& __source) {
2104cb14a3feSDimitry Andric    _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
2105cb14a3feSDimitry Andric        __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
21060b57cec5SDimitry Andric    return __table_.__node_handle_merge_multi(__source.__table_);
21070b57cec5SDimitry Andric  }
21080b57cec5SDimitry Andric  template <class _H2, class _P2>
2109cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI void merge(unordered_multimap<key_type, mapped_type, _H2, _P2, allocator_type>&& __source) {
2110cb14a3feSDimitry Andric    _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
2111cb14a3feSDimitry Andric        __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
21120b57cec5SDimitry Andric    return __table_.__node_handle_merge_multi(__source.__table_);
21130b57cec5SDimitry Andric  }
21140b57cec5SDimitry Andric  template <class _H2, class _P2>
2115cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI void merge(unordered_map<key_type, mapped_type, _H2, _P2, allocator_type>& __source) {
2116cb14a3feSDimitry Andric    _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
2117cb14a3feSDimitry Andric        __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
21180b57cec5SDimitry Andric    return __table_.__node_handle_merge_multi(__source.__table_);
21190b57cec5SDimitry Andric  }
21200b57cec5SDimitry Andric  template <class _H2, class _P2>
2121cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI void merge(unordered_map<key_type, mapped_type, _H2, _P2, allocator_type>&& __source) {
2122cb14a3feSDimitry Andric    _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
2123cb14a3feSDimitry Andric        __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
21240b57cec5SDimitry Andric    return __table_.__node_handle_merge_multi(__source.__table_);
21250b57cec5SDimitry Andric  }
21260b57cec5SDimitry Andric#endif
21270b57cec5SDimitry Andric
2128cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI void swap(unordered_multimap& __u) _NOEXCEPT_(__is_nothrow_swappable<__table>::value) {
2129cb14a3feSDimitry Andric    __table_.swap(__u.__table_);
2130cb14a3feSDimitry Andric  }
21310b57cec5SDimitry Andric
2132cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI hasher hash_function() const { return __table_.hash_function().hash_function(); }
2133cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI key_equal key_eq() const { return __table_.key_eq().key_eq(); }
21340b57cec5SDimitry Andric
2135cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI iterator find(const key_type& __k) { return __table_.find(__k); }
2136cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI const_iterator find(const key_type& __k) const { return __table_.find(__k); }
213706c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 20
2138cb14a3feSDimitry Andric  template <class _K2,
2139cb14a3feSDimitry Andric            enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr>
2140cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI iterator find(const _K2& __k) {
2141cb14a3feSDimitry Andric    return __table_.find(__k);
2142cb14a3feSDimitry Andric  }
2143cb14a3feSDimitry Andric  template <class _K2,
2144cb14a3feSDimitry Andric            enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr>
2145cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI const_iterator find(const _K2& __k) const {
2146cb14a3feSDimitry Andric    return __table_.find(__k);
2147cb14a3feSDimitry Andric  }
214806c3fb27SDimitry Andric#endif // _LIBCPP_STD_VER >= 20
2149349cc55cSDimitry Andric
2150cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI size_type count(const key_type& __k) const { return __table_.__count_multi(__k); }
215106c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 20
2152cb14a3feSDimitry Andric  template <class _K2,
2153cb14a3feSDimitry Andric            enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr>
2154cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI size_type count(const _K2& __k) const {
2155cb14a3feSDimitry Andric    return __table_.__count_multi(__k);
2156cb14a3feSDimitry Andric  }
215706c3fb27SDimitry Andric#endif // _LIBCPP_STD_VER >= 20
2158349cc55cSDimitry Andric
215906c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 20
2160cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI bool contains(const key_type& __k) const { return find(__k) != end(); }
2161e8d8bef9SDimitry Andric
2162cb14a3feSDimitry Andric  template <class _K2,
2163cb14a3feSDimitry Andric            enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr>
2164cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI bool contains(const _K2& __k) const {
2165cb14a3feSDimitry Andric    return find(__k) != end();
2166cb14a3feSDimitry Andric  }
216706c3fb27SDimitry Andric#endif // _LIBCPP_STD_VER >= 20
2168349cc55cSDimitry Andric
2169cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const key_type& __k) {
2170cb14a3feSDimitry Andric    return __table_.__equal_range_multi(__k);
2171cb14a3feSDimitry Andric  }
2172cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const key_type& __k) const {
2173cb14a3feSDimitry Andric    return __table_.__equal_range_multi(__k);
2174cb14a3feSDimitry Andric  }
217506c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 20
2176cb14a3feSDimitry Andric  template <class _K2,
2177cb14a3feSDimitry Andric            enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr>
2178cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const _K2& __k) {
2179cb14a3feSDimitry Andric    return __table_.__equal_range_multi(__k);
2180cb14a3feSDimitry Andric  }
2181cb14a3feSDimitry Andric  template <class _K2,
2182cb14a3feSDimitry Andric            enable_if_t<__is_transparent<hasher, _K2>::value && __is_transparent<key_equal, _K2>::value>* = nullptr>
2183cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const _K2& __k) const {
2184cb14a3feSDimitry Andric    return __table_.__equal_range_multi(__k);
2185cb14a3feSDimitry Andric  }
218606c3fb27SDimitry Andric#endif // _LIBCPP_STD_VER >= 20
21870b57cec5SDimitry Andric
2188cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI size_type bucket_count() const _NOEXCEPT { return __table_.bucket_count(); }
2189cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI size_type max_bucket_count() const _NOEXCEPT { return __table_.max_bucket_count(); }
21900b57cec5SDimitry Andric
2191cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI size_type bucket_size(size_type __n) const { return __table_.bucket_size(__n); }
2192cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI size_type bucket(const key_type& __k) const { return __table_.bucket(__k); }
21930b57cec5SDimitry Andric
2194cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI local_iterator begin(size_type __n) { return __table_.begin(__n); }
2195cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI local_iterator end(size_type __n) { return __table_.end(__n); }
2196cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI const_local_iterator begin(size_type __n) const { return __table_.cbegin(__n); }
2197cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI const_local_iterator end(size_type __n) const { return __table_.cend(__n); }
2198cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI const_local_iterator cbegin(size_type __n) const { return __table_.cbegin(__n); }
2199cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI const_local_iterator cend(size_type __n) const { return __table_.cend(__n); }
22000b57cec5SDimitry Andric
2201cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI float load_factor() const _NOEXCEPT { return __table_.load_factor(); }
2202cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI float max_load_factor() const _NOEXCEPT { return __table_.max_load_factor(); }
2203cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI void max_load_factor(float __mlf) { __table_.max_load_factor(__mlf); }
2204cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI void rehash(size_type __n) { __table_.__rehash_multi(__n); }
2205cb14a3feSDimitry Andric  _LIBCPP_HIDE_FROM_ABI void reserve(size_type __n) { __table_.__reserve_multi(__n); }
22060b57cec5SDimitry Andric};
22070b57cec5SDimitry Andric
2208349cc55cSDimitry Andric#if _LIBCPP_STD_VER >= 17
22090b57cec5SDimitry Andrictemplate <class _InputIterator,
22100b57cec5SDimitry Andric          class _Hash      = hash<__iter_key_type<_InputIterator>>,
22110b57cec5SDimitry Andric          class _Pred      = equal_to<__iter_key_type<_InputIterator>>,
22120b57cec5SDimitry Andric          class _Allocator = allocator<__iter_to_alloc_type<_InputIterator>>,
221306c3fb27SDimitry Andric          class            = enable_if_t<__has_input_iterator_category<_InputIterator>::value>,
2214349cc55cSDimitry Andric          class            = enable_if_t<!__is_allocator<_Hash>::value>,
2215349cc55cSDimitry Andric          class            = enable_if_t<!is_integral<_Hash>::value>,
2216349cc55cSDimitry Andric          class            = enable_if_t<!__is_allocator<_Pred>::value>,
2217349cc55cSDimitry Andric          class            = enable_if_t<__is_allocator<_Allocator>::value>>
2218cb14a3feSDimitry Andricunordered_multimap(_InputIterator,
2219cb14a3feSDimitry Andric                   _InputIterator,
2220cb14a3feSDimitry Andric                   typename allocator_traits<_Allocator>::size_type = 0,
2221cb14a3feSDimitry Andric                   _Hash                                            = _Hash(),
2222cb14a3feSDimitry Andric                   _Pred                                            = _Pred(),
2223cb14a3feSDimitry Andric                   _Allocator                                       = _Allocator())
2224cb14a3feSDimitry Andric    -> unordered_multimap<__iter_key_type<_InputIterator>,
2225cb14a3feSDimitry Andric                          __iter_mapped_type<_InputIterator>,
2226cb14a3feSDimitry Andric                          _Hash,
2227cb14a3feSDimitry Andric                          _Pred,
2228cb14a3feSDimitry Andric                          _Allocator>;
22290b57cec5SDimitry Andric
223006c3fb27SDimitry Andric#  if _LIBCPP_STD_VER >= 23
223106c3fb27SDimitry Andrictemplate <ranges::input_range _Range,
223206c3fb27SDimitry Andric          class _Hash      = hash<__range_key_type<_Range>>,
223306c3fb27SDimitry Andric          class _Pred      = equal_to<__range_key_type<_Range>>,
223406c3fb27SDimitry Andric          class _Allocator = allocator<__range_to_alloc_type<_Range>>,
223506c3fb27SDimitry Andric          class            = enable_if_t<!__is_allocator<_Hash>::value>,
223606c3fb27SDimitry Andric          class            = enable_if_t<!is_integral<_Hash>::value>,
223706c3fb27SDimitry Andric          class            = enable_if_t<!__is_allocator<_Pred>::value>,
223806c3fb27SDimitry Andric          class            = enable_if_t<__is_allocator<_Allocator>::value>>
2239cb14a3feSDimitry Andricunordered_multimap(from_range_t,
2240cb14a3feSDimitry Andric                   _Range&&,
2241cb14a3feSDimitry Andric                   typename allocator_traits<_Allocator>::size_type = 0,
2242cb14a3feSDimitry Andric                   _Hash                                            = _Hash(),
2243cb14a3feSDimitry Andric                   _Pred                                            = _Pred(),
2244cb14a3feSDimitry Andric                   _Allocator                                       = _Allocator())
224506c3fb27SDimitry Andric    -> unordered_multimap<__range_key_type<_Range>, __range_mapped_type<_Range>, _Hash, _Pred, _Allocator>;
224606c3fb27SDimitry Andric#  endif
224706c3fb27SDimitry Andric
2248cb14a3feSDimitry Andrictemplate <class _Key,
2249cb14a3feSDimitry Andric          class _Tp,
2250cb14a3feSDimitry Andric          class _Hash      = hash<remove_const_t<_Key>>,
22510b57cec5SDimitry Andric          class _Pred      = equal_to<remove_const_t<_Key>>,
22520b57cec5SDimitry Andric          class _Allocator = allocator<pair<const _Key, _Tp>>,
2253349cc55cSDimitry Andric          class            = enable_if_t<!__is_allocator<_Hash>::value>,
2254349cc55cSDimitry Andric          class            = enable_if_t<!is_integral<_Hash>::value>,
2255349cc55cSDimitry Andric          class            = enable_if_t<!__is_allocator<_Pred>::value>,
2256349cc55cSDimitry Andric          class            = enable_if_t<__is_allocator<_Allocator>::value>>
2257cb14a3feSDimitry Andricunordered_multimap(initializer_list<pair<_Key, _Tp>>,
2258cb14a3feSDimitry Andric                   typename allocator_traits<_Allocator>::size_type = 0,
2259cb14a3feSDimitry Andric                   _Hash                                            = _Hash(),
2260cb14a3feSDimitry Andric                   _Pred                                            = _Pred(),
2261cb14a3feSDimitry Andric                   _Allocator                                       = _Allocator())
22620b57cec5SDimitry Andric    -> unordered_multimap<remove_const_t<_Key>, _Tp, _Hash, _Pred, _Allocator>;
22630b57cec5SDimitry Andric
2264cb14a3feSDimitry Andrictemplate <class _InputIterator,
2265cb14a3feSDimitry Andric          class _Allocator,
226606c3fb27SDimitry Andric          class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>,
2267349cc55cSDimitry Andric          class = enable_if_t<__is_allocator<_Allocator>::value>>
22680b57cec5SDimitry Andricunordered_multimap(_InputIterator, _InputIterator, typename allocator_traits<_Allocator>::size_type, _Allocator)
2269cb14a3feSDimitry Andric    -> unordered_multimap<__iter_key_type<_InputIterator>,
2270cb14a3feSDimitry Andric                          __iter_mapped_type<_InputIterator>,
2271cb14a3feSDimitry Andric                          hash<__iter_key_type<_InputIterator>>,
2272cb14a3feSDimitry Andric                          equal_to<__iter_key_type<_InputIterator>>,
2273cb14a3feSDimitry Andric                          _Allocator>;
22740b57cec5SDimitry Andric
2275cb14a3feSDimitry Andrictemplate <class _InputIterator,
2276cb14a3feSDimitry Andric          class _Allocator,
227706c3fb27SDimitry Andric          class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>,
2278349cc55cSDimitry Andric          class = enable_if_t<__is_allocator<_Allocator>::value>>
22790b57cec5SDimitry Andricunordered_multimap(_InputIterator, _InputIterator, _Allocator)
2280cb14a3feSDimitry Andric    -> unordered_multimap<__iter_key_type<_InputIterator>,
2281cb14a3feSDimitry Andric                          __iter_mapped_type<_InputIterator>,
2282cb14a3feSDimitry Andric                          hash<__iter_key_type<_InputIterator>>,
2283cb14a3feSDimitry Andric                          equal_to<__iter_key_type<_InputIterator>>,
2284cb14a3feSDimitry Andric                          _Allocator>;
22850b57cec5SDimitry Andric
2286cb14a3feSDimitry Andrictemplate <class _InputIterator,
2287cb14a3feSDimitry Andric          class _Hash,
2288cb14a3feSDimitry Andric          class _Allocator,
228906c3fb27SDimitry Andric          class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>,
2290349cc55cSDimitry Andric          class = enable_if_t<!__is_allocator<_Hash>::value>,
2291349cc55cSDimitry Andric          class = enable_if_t<!is_integral<_Hash>::value>,
2292349cc55cSDimitry Andric          class = enable_if_t<__is_allocator<_Allocator>::value>>
22930b57cec5SDimitry Andricunordered_multimap(_InputIterator, _InputIterator, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator)
2294cb14a3feSDimitry Andric    -> unordered_multimap<__iter_key_type<_InputIterator>,
2295cb14a3feSDimitry Andric                          __iter_mapped_type<_InputIterator>,
2296cb14a3feSDimitry Andric                          _Hash,
2297cb14a3feSDimitry Andric                          equal_to<__iter_key_type<_InputIterator>>,
2298cb14a3feSDimitry Andric                          _Allocator>;
22990b57cec5SDimitry Andric
230006c3fb27SDimitry Andric#  if _LIBCPP_STD_VER >= 23
230106c3fb27SDimitry Andric
2302cb14a3feSDimitry Andrictemplate <ranges::input_range _Range, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value>>
230306c3fb27SDimitry Andricunordered_multimap(from_range_t, _Range&&, typename allocator_traits<_Allocator>::size_type, _Allocator)
2304cb14a3feSDimitry Andric    -> unordered_multimap<__range_key_type<_Range>,
2305cb14a3feSDimitry Andric                          __range_mapped_type<_Range>,
2306cb14a3feSDimitry Andric                          hash<__range_key_type<_Range>>,
2307cb14a3feSDimitry Andric                          equal_to<__range_key_type<_Range>>,
2308cb14a3feSDimitry Andric                          _Allocator>;
230906c3fb27SDimitry Andric
2310cb14a3feSDimitry Andrictemplate <ranges::input_range _Range, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value>>
231106c3fb27SDimitry Andricunordered_multimap(from_range_t, _Range&&, _Allocator)
2312cb14a3feSDimitry Andric    -> unordered_multimap<__range_key_type<_Range>,
2313cb14a3feSDimitry Andric                          __range_mapped_type<_Range>,
2314cb14a3feSDimitry Andric                          hash<__range_key_type<_Range>>,
2315cb14a3feSDimitry Andric                          equal_to<__range_key_type<_Range>>,
2316cb14a3feSDimitry Andric                          _Allocator>;
231706c3fb27SDimitry Andric
2318cb14a3feSDimitry Andrictemplate <ranges::input_range _Range,
2319cb14a3feSDimitry Andric          class _Hash,
2320cb14a3feSDimitry Andric          class _Allocator,
232106c3fb27SDimitry Andric          class = enable_if_t<!__is_allocator<_Hash>::value>,
232206c3fb27SDimitry Andric          class = enable_if_t<!is_integral<_Hash>::value>,
232306c3fb27SDimitry Andric          class = enable_if_t<__is_allocator<_Allocator>::value>>
232406c3fb27SDimitry Andricunordered_multimap(from_range_t, _Range&&, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator)
2325cb14a3feSDimitry Andric    -> unordered_multimap<__range_key_type<_Range>,
2326cb14a3feSDimitry Andric                          __range_mapped_type<_Range>,
2327cb14a3feSDimitry Andric                          _Hash,
2328cb14a3feSDimitry Andric                          equal_to<__range_key_type<_Range>>,
2329cb14a3feSDimitry Andric                          _Allocator>;
233006c3fb27SDimitry Andric
233106c3fb27SDimitry Andric#  endif
233206c3fb27SDimitry Andric
2333cb14a3feSDimitry Andrictemplate <class _Key, class _Tp, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value>>
23340b57cec5SDimitry Andricunordered_multimap(initializer_list<pair<_Key, _Tp>>, typename allocator_traits<_Allocator>::size_type, _Allocator)
2335cb14a3feSDimitry Andric    -> unordered_multimap<remove_const_t<_Key>,
2336cb14a3feSDimitry Andric                          _Tp,
23370b57cec5SDimitry Andric                          hash<remove_const_t<_Key>>,
2338cb14a3feSDimitry Andric                          equal_to<remove_const_t<_Key>>,
2339cb14a3feSDimitry Andric                          _Allocator>;
23400b57cec5SDimitry Andric
2341cb14a3feSDimitry Andrictemplate <class _Key, class _Tp, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value>>
23420b57cec5SDimitry Andricunordered_multimap(initializer_list<pair<_Key, _Tp>>, _Allocator)
2343cb14a3feSDimitry Andric    -> unordered_multimap<remove_const_t<_Key>,
2344cb14a3feSDimitry Andric                          _Tp,
23450b57cec5SDimitry Andric                          hash<remove_const_t<_Key>>,
2346cb14a3feSDimitry Andric                          equal_to<remove_const_t<_Key>>,
2347cb14a3feSDimitry Andric                          _Allocator>;
23480b57cec5SDimitry Andric
2349cb14a3feSDimitry Andrictemplate <class _Key,
2350cb14a3feSDimitry Andric          class _Tp,
2351cb14a3feSDimitry Andric          class _Hash,
2352cb14a3feSDimitry Andric          class _Allocator,
2353349cc55cSDimitry Andric          class = enable_if_t<!__is_allocator<_Hash>::value>,
2354349cc55cSDimitry Andric          class = enable_if_t<!is_integral<_Hash>::value>,
2355349cc55cSDimitry Andric          class = enable_if_t<__is_allocator<_Allocator>::value>>
2356cb14a3feSDimitry Andricunordered_multimap(
2357cb14a3feSDimitry Andric    initializer_list<pair<_Key, _Tp>>, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator)
2358cb14a3feSDimitry Andric    -> unordered_multimap<remove_const_t<_Key>, _Tp, _Hash, equal_to<remove_const_t<_Key>>, _Allocator>;
23590b57cec5SDimitry Andric#endif
23600b57cec5SDimitry Andric
23610b57cec5SDimitry Andrictemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
23620b57cec5SDimitry Andricunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
23630b57cec5SDimitry Andric    size_type __n, const hasher& __hf, const key_equal& __eql)
2364cb14a3feSDimitry Andric    : __table_(__hf, __eql) {
2365753f127fSDimitry Andric  __table_.__rehash_multi(__n);
23660b57cec5SDimitry Andric}
23670b57cec5SDimitry Andric
23680b57cec5SDimitry Andrictemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
23690b57cec5SDimitry Andricunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
2370cb14a3feSDimitry Andric    size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
2371cb14a3feSDimitry Andric    : __table_(__hf, __eql, typename __table::allocator_type(__a)) {
2372cb14a3feSDimitry Andric  __table_.__rehash_multi(__n);
2373cb14a3feSDimitry Andric}
2374cb14a3feSDimitry Andric
2375cb14a3feSDimitry Andrictemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2376cb14a3feSDimitry Andrictemplate <class _InputIterator>
2377cb14a3feSDimitry Andricunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(_InputIterator __first, _InputIterator __last) {
2378cb14a3feSDimitry Andric  insert(__first, __last);
2379cb14a3feSDimitry Andric}
2380cb14a3feSDimitry Andric
2381cb14a3feSDimitry Andrictemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2382cb14a3feSDimitry Andrictemplate <class _InputIterator>
2383cb14a3feSDimitry Andricunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
2384cb14a3feSDimitry Andric    _InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, const key_equal& __eql)
2385cb14a3feSDimitry Andric    : __table_(__hf, __eql) {
2386cb14a3feSDimitry Andric  __table_.__rehash_multi(__n);
2387cb14a3feSDimitry Andric  insert(__first, __last);
2388cb14a3feSDimitry Andric}
2389cb14a3feSDimitry Andric
2390cb14a3feSDimitry Andrictemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2391cb14a3feSDimitry Andrictemplate <class _InputIterator>
2392cb14a3feSDimitry Andricunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
2393cb14a3feSDimitry Andric    _InputIterator __first,
2394cb14a3feSDimitry Andric    _InputIterator __last,
2395cb14a3feSDimitry Andric    size_type __n,
2396cb14a3feSDimitry Andric    const hasher& __hf,
2397cb14a3feSDimitry Andric    const key_equal& __eql,
23980b57cec5SDimitry Andric    const allocator_type& __a)
2399cb14a3feSDimitry Andric    : __table_(__hf, __eql, typename __table::allocator_type(__a)) {
2400753f127fSDimitry Andric  __table_.__rehash_multi(__n);
24010b57cec5SDimitry Andric  insert(__first, __last);
24020b57cec5SDimitry Andric}
24030b57cec5SDimitry Andric
24040b57cec5SDimitry Andrictemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2405cb14a3feSDimitry Andricinline unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(const allocator_type& __a)
2406cb14a3feSDimitry Andric    : __table_(typename __table::allocator_type(__a)) {}
24070b57cec5SDimitry Andric
24080b57cec5SDimitry Andrictemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2409cb14a3feSDimitry Andricunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(const unordered_multimap& __u)
2410cb14a3feSDimitry Andric    : __table_(__u.__table_) {
2411753f127fSDimitry Andric  __table_.__rehash_multi(__u.bucket_count());
24120b57cec5SDimitry Andric  insert(__u.begin(), __u.end());
24130b57cec5SDimitry Andric}
24140b57cec5SDimitry Andric
24150b57cec5SDimitry Andrictemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
24160b57cec5SDimitry Andricunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
24170b57cec5SDimitry Andric    const unordered_multimap& __u, const allocator_type& __a)
2418cb14a3feSDimitry Andric    : __table_(__u.__table_, typename __table::allocator_type(__a)) {
2419753f127fSDimitry Andric  __table_.__rehash_multi(__u.bucket_count());
24200b57cec5SDimitry Andric  insert(__u.begin(), __u.end());
24210b57cec5SDimitry Andric}
24220b57cec5SDimitry Andric
24230b57cec5SDimitry Andric#ifndef _LIBCPP_CXX03_LANG
24240b57cec5SDimitry Andric
24250b57cec5SDimitry Andrictemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2426cb14a3feSDimitry Andricinline unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(unordered_multimap&& __u)
24270b57cec5SDimitry Andric    _NOEXCEPT_(is_nothrow_move_constructible<__table>::value)
2428cb14a3feSDimitry Andric    : __table_(std::move(__u.__table_)) {}
24290b57cec5SDimitry Andric
24300b57cec5SDimitry Andrictemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
24310b57cec5SDimitry Andricunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
24320b57cec5SDimitry Andric    unordered_multimap&& __u, const allocator_type& __a)
2433cb14a3feSDimitry Andric    : __table_(std::move(__u.__table_), typename __table::allocator_type(__a)) {
2434cb14a3feSDimitry Andric  if (__a != __u.get_allocator()) {
24350b57cec5SDimitry Andric    iterator __i = __u.begin();
2436cb14a3feSDimitry Andric    while (__u.size() != 0) {
2437cb14a3feSDimitry Andric      __table_.__insert_multi(__u.__table_.remove((__i++).__i_)->__get_value().__move());
24380b57cec5SDimitry Andric    }
24390b57cec5SDimitry Andric  }
24400b57cec5SDimitry Andric}
24410b57cec5SDimitry Andric
24420b57cec5SDimitry Andrictemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2443cb14a3feSDimitry Andricunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(initializer_list<value_type> __il) {
24440b57cec5SDimitry Andric  insert(__il.begin(), __il.end());
24450b57cec5SDimitry Andric}
24460b57cec5SDimitry Andric
24470b57cec5SDimitry Andrictemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
24480b57cec5SDimitry Andricunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
2449cb14a3feSDimitry Andric    initializer_list<value_type> __il, size_type __n, const hasher& __hf, const key_equal& __eql)
2450cb14a3feSDimitry Andric    : __table_(__hf, __eql) {
2451753f127fSDimitry Andric  __table_.__rehash_multi(__n);
24520b57cec5SDimitry Andric  insert(__il.begin(), __il.end());
24530b57cec5SDimitry Andric}
24540b57cec5SDimitry Andric
24550b57cec5SDimitry Andrictemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
24560b57cec5SDimitry Andricunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(
2457cb14a3feSDimitry Andric    initializer_list<value_type> __il,
2458cb14a3feSDimitry Andric    size_type __n,
2459cb14a3feSDimitry Andric    const hasher& __hf,
2460cb14a3feSDimitry Andric    const key_equal& __eql,
2461cb14a3feSDimitry Andric    const allocator_type& __a)
2462cb14a3feSDimitry Andric    : __table_(__hf, __eql, typename __table::allocator_type(__a)) {
2463753f127fSDimitry Andric  __table_.__rehash_multi(__n);
24640b57cec5SDimitry Andric  insert(__il.begin(), __il.end());
24650b57cec5SDimitry Andric}
24660b57cec5SDimitry Andric
24670b57cec5SDimitry Andrictemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2468cb14a3feSDimitry Andricinline unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>&
24690b57cec5SDimitry Andricunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(unordered_multimap&& __u)
2470cb14a3feSDimitry Andric    _NOEXCEPT_(is_nothrow_move_assignable<__table>::value) {
24715f757f3fSDimitry Andric  __table_ = std::move(__u.__table_);
24720b57cec5SDimitry Andric  return *this;
24730b57cec5SDimitry Andric}
24740b57cec5SDimitry Andric
24750b57cec5SDimitry Andrictemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2476cb14a3feSDimitry Andricinline unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>&
2477cb14a3feSDimitry Andricunordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(initializer_list<value_type> __il) {
24780b57cec5SDimitry Andric  __table_.__assign_multi(__il.begin(), __il.end());
24790b57cec5SDimitry Andric  return *this;
24800b57cec5SDimitry Andric}
24810b57cec5SDimitry Andric
24820b57cec5SDimitry Andric#endif // _LIBCPP_CXX03_LANG
24830b57cec5SDimitry Andric
24840b57cec5SDimitry Andrictemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
24850b57cec5SDimitry Andrictemplate <class _InputIterator>
2486cb14a3feSDimitry Andricinline void unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, _InputIterator __last) {
24870b57cec5SDimitry Andric  for (; __first != __last; ++__first)
24880b57cec5SDimitry Andric    __table_.__insert_multi(*__first);
24890b57cec5SDimitry Andric}
24900b57cec5SDimitry Andric
24910b57cec5SDimitry Andrictemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2492cb14a3feSDimitry Andricinline _LIBCPP_HIDE_FROM_ABI void
2493cb14a3feSDimitry Andricswap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
2494cb14a3feSDimitry Andric    _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) {
24950b57cec5SDimitry Andric  __x.swap(__y);
24960b57cec5SDimitry Andric}
24970b57cec5SDimitry Andric
249806c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 20
2499cb14a3feSDimitry Andrictemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc, class _Predicate>
2500cb14a3feSDimitry Andricinline _LIBCPP_HIDE_FROM_ABI typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::size_type
2501cb14a3feSDimitry Andricerase_if(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __c, _Predicate __pred) {
25025f757f3fSDimitry Andric  return std::__libcpp_erase_if_container(__c, __pred);
25035ffd83dbSDimitry Andric}
25040b57cec5SDimitry Andric#endif
25050b57cec5SDimitry Andric
25060b57cec5SDimitry Andrictemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2507cb14a3feSDimitry Andric_LIBCPP_HIDE_FROM_ABI bool operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
2508cb14a3feSDimitry Andric                                      const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) {
25090b57cec5SDimitry Andric  if (__x.size() != __y.size())
25100b57cec5SDimitry Andric    return false;
2511cb14a3feSDimitry Andric  typedef typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator const_iterator;
25120b57cec5SDimitry Andric  typedef pair<const_iterator, const_iterator> _EqRng;
2513cb14a3feSDimitry Andric  for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;) {
25140b57cec5SDimitry Andric    _EqRng __xeq = __x.equal_range(__i->first);
25150b57cec5SDimitry Andric    _EqRng __yeq = __y.equal_range(__i->first);
2516cb14a3feSDimitry Andric    if (std::distance(__xeq.first, __xeq.second) != std::distance(__yeq.first, __yeq.second) ||
25175f757f3fSDimitry Andric        !std::is_permutation(__xeq.first, __xeq.second, __yeq.first))
25180b57cec5SDimitry Andric      return false;
25190b57cec5SDimitry Andric    __i = __xeq.second;
25200b57cec5SDimitry Andric  }
25210b57cec5SDimitry Andric  return true;
25220b57cec5SDimitry Andric}
25230b57cec5SDimitry Andric
252406c3fb27SDimitry Andric#if _LIBCPP_STD_VER <= 17
252506c3fb27SDimitry Andric
25260b57cec5SDimitry Andrictemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
2527cb14a3feSDimitry Andricinline _LIBCPP_HIDE_FROM_ABI bool operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
2528cb14a3feSDimitry Andric                                             const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) {
25290b57cec5SDimitry Andric  return !(__x == __y);
25300b57cec5SDimitry Andric}
25310b57cec5SDimitry Andric
253206c3fb27SDimitry Andric#endif
253306c3fb27SDimitry Andric
25340b57cec5SDimitry Andric_LIBCPP_END_NAMESPACE_STD
25350b57cec5SDimitry Andric
253606c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 17
2537bdd1243dSDimitry Andric_LIBCPP_BEGIN_NAMESPACE_STD
2538bdd1243dSDimitry Andricnamespace pmr {
2539bdd1243dSDimitry Andrictemplate <class _KeyT, class _ValueT, class _HashT = std::hash<_KeyT>, class _PredT = std::equal_to<_KeyT>>
254006c3fb27SDimitry Andricusing unordered_map _LIBCPP_AVAILABILITY_PMR =
2541bdd1243dSDimitry Andric    std::unordered_map<_KeyT, _ValueT, _HashT, _PredT, polymorphic_allocator<std::pair<const _KeyT, _ValueT>>>;
2542bdd1243dSDimitry Andric
2543bdd1243dSDimitry Andrictemplate <class _KeyT, class _ValueT, class _HashT = std::hash<_KeyT>, class _PredT = std::equal_to<_KeyT>>
254406c3fb27SDimitry Andricusing unordered_multimap _LIBCPP_AVAILABILITY_PMR =
2545bdd1243dSDimitry Andric    std::unordered_multimap<_KeyT, _ValueT, _HashT, _PredT, polymorphic_allocator<std::pair<const _KeyT, _ValueT>>>;
2546bdd1243dSDimitry Andric} // namespace pmr
2547bdd1243dSDimitry Andric_LIBCPP_END_NAMESPACE_STD
2548bdd1243dSDimitry Andric#endif
2549bdd1243dSDimitry Andric
2550*b3edf446SDimitry Andric_LIBCPP_POP_MACROS
2551*b3edf446SDimitry Andric
2552bdd1243dSDimitry Andric#if !defined(_LIBCPP_REMOVE_TRANSITIVE_INCLUDES) && _LIBCPP_STD_VER <= 20
2553bdd1243dSDimitry Andric#  include <algorithm>
2554bdd1243dSDimitry Andric#  include <bit>
2555bdd1243dSDimitry Andric#  include <concepts>
255606c3fb27SDimitry Andric#  include <cstdlib>
2557bdd1243dSDimitry Andric#  include <iterator>
255806c3fb27SDimitry Andric#  include <type_traits>
2559bdd1243dSDimitry Andric#endif
2560bdd1243dSDimitry Andric
25610b57cec5SDimitry Andric#endif // _LIBCPP_UNORDERED_MAP
2562