brintos / llvm-project-archived public Read only

1// -*- C++ -*-2//===----------------------------------------------------------------------===//3//4// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.5// See https://llvm.org/LICENSE.txt for license information.6// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception7//8//===----------------------------------------------------------------------===//9 10#ifndef _LIBCPP_UNORDERED_MAP11#define _LIBCPP_UNORDERED_MAP12 13/*14 15    unordered_map synopsis16 17#include <initializer_list>18 19namespace std20{21 22template <class Key, class T, class Hash = hash<Key>, class Pred = equal_to<Key>,23          class Alloc = allocator<pair<const Key, T>>>24class unordered_map25{26public:27    // types28    typedef Key                                                        key_type;29    typedef T                                                          mapped_type;30    typedef Hash                                                       hasher;31    typedef Pred                                                       key_equal;32    typedef Alloc                                                      allocator_type;33    typedef pair<const key_type, mapped_type>                          value_type;34    typedef value_type&                                                reference;35    typedef const value_type&                                          const_reference;36    typedef typename allocator_traits<allocator_type>::pointer         pointer;37    typedef typename allocator_traits<allocator_type>::const_pointer   const_pointer;38    typedef typename allocator_traits<allocator_type>::size_type       size_type;39    typedef typename allocator_traits<allocator_type>::difference_type difference_type;40 41    typedef /unspecified/ iterator;42    typedef /unspecified/ const_iterator;43    typedef /unspecified/ local_iterator;44    typedef /unspecified/ const_local_iterator;45 46    typedef unspecified                             node_type;            // C++1747    typedef INSERT_RETURN_TYPE<iterator, node_type> insert_return_type;   // C++1748 49    unordered_map()50        noexcept(51            is_nothrow_default_constructible<hasher>::value &&52            is_nothrow_default_constructible<key_equal>::value &&53            is_nothrow_default_constructible<allocator_type>::value);54    explicit unordered_map(size_type n, const hasher& hf = hasher(),55                           const key_equal& eql = key_equal(),56                           const allocator_type& a = allocator_type());57    template <class InputIterator>58        unordered_map(InputIterator f, InputIterator l,59                      size_type n = 0, const hasher& hf = hasher(),60                      const key_equal& eql = key_equal(),61                      const allocator_type& a = allocator_type());62    template<container-compatible-range<value_type> R>63      unordered_map(from_range_t, R&& rg, size_type n = see below,64        const hasher& hf = hasher(), const key_equal& eql = key_equal(),65        const allocator_type& a = allocator_type()); // C++2366 67    explicit unordered_map(const allocator_type&);68    unordered_map(const unordered_map&);69    unordered_map(const unordered_map&, const Allocator&);70    unordered_map(unordered_map&&)71        noexcept(72            is_nothrow_move_constructible<hasher>::value &&73            is_nothrow_move_constructible<key_equal>::value &&74            is_nothrow_move_constructible<allocator_type>::value);75    unordered_map(unordered_map&&, const Allocator&);76    unordered_map(initializer_list<value_type>, size_type n = 0,77                  const hasher& hf = hasher(), const key_equal& eql = key_equal(),78                  const allocator_type& a = allocator_type());79    unordered_map(size_type n, const allocator_type& a)80      : unordered_map(n, hasher(), key_equal(), a) {}  // C++1481    unordered_map(size_type n, const hasher& hf, const allocator_type& a)82      : unordered_map(n, hf, key_equal(), a) {}  // C++1483    template <class InputIterator>84      unordered_map(InputIterator f, InputIterator l, size_type n, const allocator_type& a)85      : unordered_map(f, l, n, hasher(), key_equal(), a) {}  // C++1486    template <class InputIterator>87      unordered_map(InputIterator f, InputIterator l, size_type n, const hasher& hf,88        const allocator_type& a)89      : unordered_map(f, l, n, hf, key_equal(), a) {}  // C++1490    template<container-compatible-range<value_type> R>91      unordered_map(from_range_t, R&& rg, size_type n, const allocator_type& a)92        : unordered_map(from_range, std::forward<R>(rg), n, hasher(), key_equal(), a) { } // C++2393    template<container-compatible-range<value_type> R>94      unordered_map(from_range_t, R&& rg, size_type n, const hasher& hf, const allocator_type& a)95        : unordered_map(from_range, std::forward<R>(rg), n, hf, key_equal(), a) { }       // C++2396    unordered_map(initializer_list<value_type> il, size_type n, const allocator_type& a)97      : unordered_map(il, n, hasher(), key_equal(), a) {}  // C++1498    unordered_map(initializer_list<value_type> il, size_type n, const hasher& hf,99      const allocator_type& a)100      : unordered_map(il, n, hf, key_equal(), a) {}  // C++14101    ~unordered_map();102    unordered_map& operator=(const unordered_map&);103    unordered_map& operator=(unordered_map&&)104        noexcept(105            allocator_type::propagate_on_container_move_assignment::value &&106            is_nothrow_move_assignable<allocator_type>::value &&107            is_nothrow_move_assignable<hasher>::value &&108            is_nothrow_move_assignable<key_equal>::value);109    unordered_map& operator=(initializer_list<value_type>);110 111    allocator_type get_allocator() const noexcept;112 113    bool      empty() const noexcept;114    size_type size() const noexcept;115    size_type max_size() const noexcept;116 117    iterator       begin() noexcept;118    iterator       end() noexcept;119    const_iterator begin()  const noexcept;120    const_iterator end()    const noexcept;121    const_iterator cbegin() const noexcept;122    const_iterator cend()   const noexcept;123 124    template <class... Args>125        pair<iterator, bool> emplace(Args&&... args);126    template <class... Args>127        iterator emplace_hint(const_iterator position, Args&&... args);128    pair<iterator, bool> insert(const value_type& obj);129    template <class P>130        pair<iterator, bool> insert(P&& obj);131    iterator insert(const_iterator hint, const value_type& obj);132    template <class P>133        iterator insert(const_iterator hint, P&& obj);134    template <class InputIterator>135        void insert(InputIterator first, InputIterator last);136    template<container-compatible-range<value_type> R>137      void insert_range(R&& rg);                                                      // C++23138    void insert(initializer_list<value_type>);139 140    node_type extract(const_iterator position);                                       // C++17141    node_type extract(const key_type& x);                                             // C++17142    insert_return_type insert(node_type&& nh);                                        // C++17143    iterator           insert(const_iterator hint, node_type&& nh);                   // C++17144 145    template <class... Args>146        pair<iterator, bool> try_emplace(const key_type& k, Args&&... args);          // C++17147    template <class... Args>148        pair<iterator, bool> try_emplace(key_type&& k, Args&&... args);               // C++17149    template <class... Args>150        iterator try_emplace(const_iterator hint, const key_type& k, Args&&... args); // C++17151    template <class... Args>152        iterator try_emplace(const_iterator hint, key_type&& k, Args&&... args);      // C++17153    template <class M>154        pair<iterator, bool> insert_or_assign(const key_type& k, M&& obj);            // C++17155    template <class M>156        pair<iterator, bool> insert_or_assign(key_type&& k, M&& obj);                 // C++17157    template <class M>158        iterator insert_or_assign(const_iterator hint, const key_type& k, M&& obj);   // C++17159    template <class M>160        iterator insert_or_assign(const_iterator hint, key_type&& k, M&& obj);        // C++17161 162    iterator erase(const_iterator position);163    iterator erase(iterator position);  // C++14164    size_type erase(const key_type& k);165    iterator erase(const_iterator first, const_iterator last);166    void clear() noexcept;167 168    template<class H2, class P2>169      void merge(unordered_map<Key, T, H2, P2, Allocator>& source);         // C++17170    template<class H2, class P2>171      void merge(unordered_map<Key, T, H2, P2, Allocator>&& source);        // C++17172    template<class H2, class P2>173      void merge(unordered_multimap<Key, T, H2, P2, Allocator>& source);    // C++17174    template<class H2, class P2>175      void merge(unordered_multimap<Key, T, H2, P2, Allocator>&& source);   // C++17176 177    void swap(unordered_map&)178        noexcept(179            (!allocator_type::propagate_on_container_swap::value ||180             __is_nothrow_swappable<allocator_type>::value) &&181            __is_nothrow_swappable<hasher>::value &&182            __is_nothrow_swappable<key_equal>::value);183 184    hasher hash_function() const;185    key_equal key_eq() const;186 187    iterator       find(const key_type& k);188    const_iterator find(const key_type& k) const;189    template<typename K>190        iterator find(const K& x);              // C++20191    template<typename K>192        const_iterator find(const K& x) const;  // C++20193    size_type count(const key_type& k) const;194    template<typename K>195        size_type count(const K& k) const; // C++20196    bool contains(const key_type& k) const; // C++20197    template<typename K>198        bool contains(const K& k) const; // C++20199    pair<iterator, iterator>             equal_range(const key_type& k);200    pair<const_iterator, const_iterator> equal_range(const key_type& k) const;201    template<typename K>202        pair<iterator, iterator>             equal_range(const K& k); // C++20203    template<typename K>204        pair<const_iterator, const_iterator> equal_range(const K& k) const; // C++20205 206    mapped_type& operator[](const key_type& k);207    mapped_type& operator[](key_type&& k);208 209    mapped_type&       at(const key_type& k);210    const mapped_type& at(const key_type& k) const;211 212    size_type bucket_count() const noexcept;213    size_type max_bucket_count() const noexcept;214 215    size_type bucket_size(size_type n) const;216    size_type bucket(const key_type& k) const;217 218    local_iterator       begin(size_type n);219    local_iterator       end(size_type n);220    const_local_iterator begin(size_type n) const;221    const_local_iterator end(size_type n) const;222    const_local_iterator cbegin(size_type n) const;223    const_local_iterator cend(size_type n) const;224 225    float load_factor() const noexcept;226    float max_load_factor() const noexcept;227    void max_load_factor(float z);228    void rehash(size_type n);229    void reserve(size_type n);230};231 232template<class InputIterator,233    class Hash = hash<iter_key_t<InputIterator>>, class Pred = equal_to<iter_key_t<InputIterator>>,234    class Allocator = allocator<iter_to_alloc_t<InputIterator>>>235unordered_map(InputIterator, InputIterator, typename see below::size_type = see below,236    Hash = Hash(), Pred = Pred(), Allocator = Allocator())237  -> unordered_map<iter_key_t<InputIterator>, iter_value_t<InputIterator>, Hash, Pred,238    Allocator>; // C++17239 240template<ranges::input_range R, class Hash = hash<range-key-type<R>>,241         class Pred = equal_to<range-key-type<R>>,242         class Allocator = allocator<range-to-alloc-type<R>>>243  unordered_map(from_range_t, R&&, typename see below::size_type = see below,244                Hash = Hash(), Pred = Pred(), Allocator = Allocator())245    -> unordered_map<range-key-type<R>, range-mapped-type<R>, Hash, Pred, Allocator>; // C++23246 247template<class Key, class T, class Hash = hash<Key>,248    class Pred = equal_to<Key>, class Allocator = allocator<pair<const Key, T>>>249unordered_map(initializer_list<pair<const Key, T>>, typename see below::size_type = see below,250    Hash = Hash(), Pred = Pred(), Allocator = Allocator())251  -> unordered_map<Key, T, Hash, Pred, Allocator>; // C++17252 253template<class InputIterator, class Allocator>254unordered_map(InputIterator, InputIterator, typename see below::size_type, Allocator)255  -> unordered_map<iter_key_t<InputIterator>, iter_val_t<InputIterator>,256        hash<iter_key_t<InputIterator>>, equal_to<iter_key_t<InputIterator>>, Allocator>; // C++17257 258template<class InputIterator, class Allocator>259unordered_map(InputIterator, InputIterator, Allocator)260  -> unordered_map<iter_key_t<InputIterator>, iter_val_t<InputIterator>,261        hash<iter_key_t<InputIterator>>, equal_to<iter_key_t<InputIterator>>, Allocator>; // C++17262 263template<class InputIterator, class Hash, class Allocator>264unordered_map(InputIterator, InputIterator, typename see below::size_type, Hash, Allocator)265  -> unordered_map<iter_key_t<InputIterator>, iter_val_t<InputIterator>, Hash,266          equal_to<iter_key_t<InputIterator>>, Allocator>; // C++17267 268template<ranges::input_range R, class Allocator>269  unordered_map(from_range_t, R&&, typename see below::size_type, Allocator)270    -> unordered_map<range-key-type<R>, range-mapped-type<R>, hash<range-key-type<R>>,271                      equal_to<range-key-type<R>>, Allocator>;   // C++23272 273template<ranges::input_range R, class Allocator>274  unordered_map(from_range_t, R&&, Allocator)275    -> unordered_map<range-key-type<R>, range-mapped-type<R>, hash<range-key-type<R>>,276                      equal_to<range-key-type<R>>, Allocator>;   // C++23277 278template<ranges::input_range R, class Hash, class Allocator>279  unordered_map(from_range_t, R&&, typename see below::size_type, Hash, Allocator)280    -> unordered_map<range-key-type<R>, range-mapped-type<R>, Hash,281                      equal_to<range-key-type<R>>, Allocator>;   // C++23282 283template<class Key, class T, typename Allocator>284unordered_map(initializer_list<pair<const Key, T>>, typename see below::size_type, Allocator)285  -> unordered_map<Key, T, hash<Key>, equal_to<Key>, Allocator>; // C++17286 287template<class Key, class T, typename Allocator>288unordered_map(initializer_list<pair<const Key, T>>, Allocator)289  -> unordered_map<Key, T, hash<Key>, equal_to<Key>, Allocator>; // C++17290 291template<class Key, class T, class Hash, class Allocator>292unordered_map(initializer_list<pair<const Key, T>>, typename see below::size_type, Hash, Allocator)293  -> unordered_map<Key, T, Hash, equal_to<Key>, Allocator>; // C++17294 295template <class Key, class T, class Hash, class Pred, class Alloc>296    void swap(unordered_map<Key, T, Hash, Pred, Alloc>& x,297              unordered_map<Key, T, Hash, Pred, Alloc>& y)298              noexcept(noexcept(x.swap(y)));299 300template <class Key, class T, class Hash, class Pred, class Alloc>301    bool302    operator==(const unordered_map<Key, T, Hash, Pred, Alloc>& x,303               const unordered_map<Key, T, Hash, Pred, Alloc>& y);304 305template <class Key, class T, class Hash, class Pred, class Alloc>306    bool307    operator!=(const unordered_map<Key, T, Hash, Pred, Alloc>& x,308               const unordered_map<Key, T, Hash, Pred, Alloc>& y); // Removed in C++20309 310template <class Key, class T, class Hash = hash<Key>, class Pred = equal_to<Key>,311          class Alloc = allocator<pair<const Key, T>>>312class unordered_multimap313{314public:315    // types316    typedef Key                                                        key_type;317    typedef T                                                          mapped_type;318    typedef Hash                                                       hasher;319    typedef Pred                                                       key_equal;320    typedef Alloc                                                      allocator_type;321    typedef pair<const key_type, mapped_type>                          value_type;322    typedef value_type&                                                reference;323    typedef const value_type&                                          const_reference;324    typedef typename allocator_traits<allocator_type>::pointer         pointer;325    typedef typename allocator_traits<allocator_type>::const_pointer   const_pointer;326    typedef typename allocator_traits<allocator_type>::size_type       size_type;327    typedef typename allocator_traits<allocator_type>::difference_type difference_type;328 329    typedef /unspecified/ iterator;330    typedef /unspecified/ const_iterator;331    typedef /unspecified/ local_iterator;332    typedef /unspecified/ const_local_iterator;333 334    typedef unspecified node_type;    // C++17335 336    unordered_multimap()337        noexcept(338            is_nothrow_default_constructible<hasher>::value &&339            is_nothrow_default_constructible<key_equal>::value &&340            is_nothrow_default_constructible<allocator_type>::value);341    explicit unordered_multimap(size_type n, const hasher& hf = hasher(),342                           const key_equal& eql = key_equal(),343                           const allocator_type& a = allocator_type());344    template <class InputIterator>345        unordered_multimap(InputIterator f, InputIterator l,346                      size_type n = 0, const hasher& hf = hasher(),347                      const key_equal& eql = key_equal(),348                      const allocator_type& a = allocator_type());349    template<container-compatible-range<value_type> R>350      unordered_multimap(from_range_t, R&& rg, size_type n = see below,351        const hasher& hf = hasher(), const key_equal& eql = key_equal(),352        const allocator_type& a = allocator_type()); // C++23353    explicit unordered_multimap(const allocator_type&);354    unordered_multimap(const unordered_multimap&);355    unordered_multimap(const unordered_multimap&, const Allocator&);356    unordered_multimap(unordered_multimap&&)357        noexcept(358            is_nothrow_move_constructible<hasher>::value &&359            is_nothrow_move_constructible<key_equal>::value &&360            is_nothrow_move_constructible<allocator_type>::value);361    unordered_multimap(unordered_multimap&&, const Allocator&);362    unordered_multimap(initializer_list<value_type>, size_type n = 0,363                  const hasher& hf = hasher(), const key_equal& eql = key_equal(),364                  const allocator_type& a = allocator_type());365    unordered_multimap(size_type n, const allocator_type& a)366      : unordered_multimap(n, hasher(), key_equal(), a) {}  // C++14367    unordered_multimap(size_type n, const hasher& hf, const allocator_type& a)368      : unordered_multimap(n, hf, key_equal(), a) {}  // C++14369    template <class InputIterator>370      unordered_multimap(InputIterator f, InputIterator l, size_type n, const allocator_type& a)371      : unordered_multimap(f, l, n, hasher(), key_equal(), a) {}  // C++14372    template <class InputIterator>373      unordered_multimap(InputIterator f, InputIterator l, size_type n, const hasher& hf,374        const allocator_type& a)375      : unordered_multimap(f, l, n, hf, key_equal(), a) {}  // C++14376    template<container-compatible-range<value_type> R>377      unordered_multimap(from_range_t, R&& rg, size_type n, const allocator_type& a)378        : unordered_multimap(from_range, std::forward<R>(rg), n, hasher(), key_equal(), a) { } // C++23379    template<container-compatible-range<value_type> R>380      unordered_multimap(from_range_t, R&& rg, size_type n, const hasher& hf, const allocator_type& a)381        : unordered_multimap(from_range, std::forward<R>(rg), n, hf, key_equal(), a) { }       // C++23382    unordered_multimap(initializer_list<value_type> il, size_type n, const allocator_type& a)383      : unordered_multimap(il, n, hasher(), key_equal(), a) {}  // C++14384    unordered_multimap(initializer_list<value_type> il, size_type n, const hasher& hf,385      const allocator_type& a)386      : unordered_multimap(il, n, hf, key_equal(), a) {}  // C++14387    ~unordered_multimap();388    unordered_multimap& operator=(const unordered_multimap&);389    unordered_multimap& operator=(unordered_multimap&&)390        noexcept(391            allocator_type::propagate_on_container_move_assignment::value &&392            is_nothrow_move_assignable<allocator_type>::value &&393            is_nothrow_move_assignable<hasher>::value &&394            is_nothrow_move_assignable<key_equal>::value);395    unordered_multimap& operator=(initializer_list<value_type>);396 397    allocator_type get_allocator() const noexcept;398 399    bool      empty() const noexcept;400    size_type size() const noexcept;401    size_type max_size() const noexcept;402 403    iterator       begin() noexcept;404    iterator       end() noexcept;405    const_iterator begin()  const noexcept;406    const_iterator end()    const noexcept;407    const_iterator cbegin() const noexcept;408    const_iterator cend()   const noexcept;409 410    template <class... Args>411        iterator emplace(Args&&... args);412    template <class... Args>413        iterator emplace_hint(const_iterator position, Args&&... args);414    iterator insert(const value_type& obj);415    template <class P>416        iterator insert(P&& obj);417    iterator insert(const_iterator hint, const value_type& obj);418    template <class P>419        iterator insert(const_iterator hint, P&& obj);420    template <class InputIterator>421        void insert(InputIterator first, InputIterator last);422    template<container-compatible-range<value_type> R>423      void insert_range(R&& rg);                               // C++23424    void insert(initializer_list<value_type>);425 426    node_type extract(const_iterator position);                // C++17427    node_type extract(const key_type& x);                      // C++17428    iterator insert(node_type&& nh);                           // C++17429    iterator insert(const_iterator hint, node_type&& nh);      // C++17430 431    iterator erase(const_iterator position);432    iterator erase(iterator position);  // C++14433    size_type erase(const key_type& k);434    iterator erase(const_iterator first, const_iterator last);435    void clear() noexcept;436 437    template<class H2, class P2>438      void merge(unordered_multimap<Key, T, H2, P2, Allocator>& source);    // C++17439    template<class H2, class P2>440      void merge(unordered_multimap<Key, T, H2, P2, Allocator>&& source);   // C++17441    template<class H2, class P2>442      void merge(unordered_map<Key, T, H2, P2, Allocator>& source);         // C++17443    template<class H2, class P2>444      void merge(unordered_map<Key, T, H2, P2, Allocator>&& source);        // C++17445 446    void swap(unordered_multimap&)447        noexcept(448            (!allocator_type::propagate_on_container_swap::value ||449             __is_nothrow_swappable<allocator_type>::value) &&450            __is_nothrow_swappable<hasher>::value &&451            __is_nothrow_swappable<key_equal>::value);452 453    hasher hash_function() const;454    key_equal key_eq() const;455 456    iterator       find(const key_type& k);457    const_iterator find(const key_type& k) const;458    template<typename K>459        iterator find(const K& x);              // C++20460    template<typename K>461        const_iterator find(const K& x) const;  // C++20462    size_type count(const key_type& k) const;463    template<typename K>464        size_type count(const K& k) const; // C++20465    bool contains(const key_type& k) const; // C++20466    template<typename K>467        bool contains(const K& k) const; // C++20468    pair<iterator, iterator>             equal_range(const key_type& k);469    pair<const_iterator, const_iterator> equal_range(const key_type& k) const;470    template<typename K>471        pair<iterator, iterator>             equal_range(const K& k); // C++20472    template<typename K>473        pair<const_iterator, const_iterator> equal_range(const K& k) const; // C++20474 475    size_type bucket_count() const noexcept;476    size_type max_bucket_count() const noexcept;477 478    size_type bucket_size(size_type n) const;479    size_type bucket(const key_type& k) const;480 481    local_iterator       begin(size_type n);482    local_iterator       end(size_type n);483    const_local_iterator begin(size_type n) const;484    const_local_iterator end(size_type n) const;485    const_local_iterator cbegin(size_type n) const;486    const_local_iterator cend(size_type n) const;487 488    float load_factor() const noexcept;489    float max_load_factor() const noexcept;490    void max_load_factor(float z);491    void rehash(size_type n);492    void reserve(size_type n);493};494 495template<class InputIterator,496    class Hash = hash<iter_key_t<InputIterator>>, class Pred = equal_to<iter_key_t<InputIterator>>,497    class Allocator = allocator<iter_to_alloc_t<InputIterator>>>498unordered_multimap(InputIterator, InputIterator, typename see below::size_type = see below,499    Hash = Hash(), Pred = Pred(), Allocator = Allocator())500  -> unordered_multimap<iter_key_t<InputIterator>, iter_value_t<InputIterator>, Hash, Pred,501    Allocator>; // C++17502 503template<ranges::input_range R, class Hash = hash<range-key-type<R>>,504         class Pred = equal_to<range-key-type<R>>,505         class Allocator = allocator<range-to-alloc-type<R>>>506  unordered_multimap(from_range_t, R&&, typename see below::size_type = see below,507                Hash = Hash(), Pred = Pred(), Allocator = Allocator())508    -> unordered_multimap<range-key-type<R>, range-mapped-type<R>, Hash, Pred, Allocator>; // C++23509 510template<class Key, class T, class Hash = hash<Key>,511    class Pred = equal_to<Key>, class Allocator = allocator<pair<const Key, T>>>512unordered_multimap(initializer_list<pair<const Key, T>>, typename see below::size_type = see below,513    Hash = Hash(), Pred = Pred(), Allocator = Allocator())514  -> unordered_multimap<Key, T, Hash, Pred, Allocator>; // C++17515 516template<class InputIterator, class Allocator>517unordered_multimap(InputIterator, InputIterator, typename see below::size_type, Allocator)518  -> unordered_multimap<iter_key_t<InputIterator>, iter_val_t<InputIterator>,519        hash<iter_key_t<InputIterator>>, equal_to<iter_key_t<InputIterator>>, Allocator>; // C++17520 521template<class InputIterator, class Allocator>522unordered_multimap(InputIterator, InputIterator, Allocator)523  -> unordered_multimap<iter_key_t<InputIterator>, iter_val_t<InputIterator>,524        hash<iter_key_t<InputIterator>>, equal_to<iter_key_t<InputIterator>>, Allocator>; // C++17525 526template<class InputIterator, class Hash, class Allocator>527unordered_multimap(InputIterator, InputIterator, typename see below::size_type, Hash, Allocator)528  -> unordered_multimap<iter_key_t<InputIterator>, iter_val_t<InputIterator>, Hash,529          equal_to<iter_key_t<InputIterator>>, Allocator>; // C++17530 531template<ranges::input_range R, class Allocator>532  unordered_multimap(from_range_t, R&&, typename see below::size_type, Allocator)533    -> unordered_multimap<range-key-type<R>, range-mapped-type<R>, hash<range-key-type<R>>,534                      equal_to<range-key-type<R>>, Allocator>;   // C++23535 536template<ranges::input_range R, class Allocator>537  unordered_multimap(from_range_t, R&&, Allocator)538    -> unordered_multimap<range-key-type<R>, range-mapped-type<R>, hash<range-key-type<R>>,539                      equal_to<range-key-type<R>>, Allocator>;   // C++23540 541template<ranges::input_range R, class Hash, class Allocator>542  unordered_multimap(from_range_t, R&&, typename see below::size_type, Hash, Allocator)543    -> unordered_multimap<range-key-type<R>, range-mapped-type<R>, Hash,544                      equal_to<range-key-type<R>>, Allocator>;   // C++23545 546template<class Key, class T, typename Allocator>547unordered_multimap(initializer_list<pair<const Key, T>>, typename see below::size_type, Allocator)548  -> unordered_multimap<Key, T, hash<Key>, equal_to<Key>, Allocator>; // C++17549 550template<class Key, class T, typename Allocator>551unordered_multimap(initializer_list<pair<const Key, T>>, Allocator)552  -> unordered_multimap<Key, T, hash<Key>, equal_to<Key>, Allocator>; // C++17553 554template<class Key, class T, class Hash, class Allocator>555unordered_multimap(initializer_list<pair<const Key, T>>, typename see below::size_type, Hash,556    Allocator)557  -> unordered_multimap<Key, T, Hash, equal_to<Key>, Allocator>; // C++17558 559template <class Key, class T, class Hash, class Pred, class Alloc>560    void swap(unordered_multimap<Key, T, Hash, Pred, Alloc>& x,561              unordered_multimap<Key, T, Hash, Pred, Alloc>& y)562              noexcept(noexcept(x.swap(y)));563 564template <class K, class T, class H, class P, class A, class Predicate>565    typename unordered_map<K, T, H, P, A>::size_type566    erase_if(unordered_map<K, T, H, P, A>& c, Predicate pred);       // C++20567 568template <class K, class T, class H, class P, class A, class Predicate>569    typename unordered_multimap<K, T, H, P, A>::size_type570    erase_if(unordered_multimap<K, T, H, P, A>& c, Predicate pred);  // C++20571 572template <class Key, class T, class Hash, class Pred, class Alloc>573    bool574    operator==(const unordered_multimap<Key, T, Hash, Pred, Alloc>& x,575               const unordered_multimap<Key, T, Hash, Pred, Alloc>& y);576 577template <class Key, class T, class Hash, class Pred, class Alloc>578    bool579    operator!=(const unordered_multimap<Key, T, Hash, Pred, Alloc>& x,580               const unordered_multimap<Key, T, Hash, Pred, Alloc>& y); // Removed in C++20581 582}  // std583 584*/585 586#if __cplusplus < 201103L && defined(_LIBCPP_USE_FROZEN_CXX03_HEADERS)587#  include <__cxx03/unordered_map>588#else589#  include <__algorithm/is_permutation.h>590#  include <__assert>591#  include <__config>592#  include <__functional/hash.h>593#  include <__functional/is_transparent.h>594#  include <__functional/operations.h>595#  include <__hash_table>596#  include <__iterator/distance.h>597#  include <__iterator/erase_if_container.h>598#  include <__iterator/iterator_traits.h>599#  include <__iterator/ranges_iterator_traits.h>600#  include <__memory/addressof.h>601#  include <__memory/allocator.h>602#  include <__memory/allocator_traits.h>603#  include <__memory/compressed_pair.h>604#  include <__memory/pointer_traits.h>605#  include <__memory/unique_ptr.h>606#  include <__memory_resource/polymorphic_allocator.h>607#  include <__new/launder.h>608#  include <__node_handle>609#  include <__ranges/concepts.h>610#  include <__ranges/container_compatible_range.h>611#  include <__ranges/from_range.h>612#  include <__type_traits/container_traits.h>613#  include <__type_traits/enable_if.h>614#  include <__type_traits/invoke.h>615#  include <__type_traits/is_allocator.h>616#  include <__type_traits/is_integral.h>617#  include <__type_traits/remove_const.h>618#  include <__type_traits/type_identity.h>619#  include <__utility/forward.h>620#  include <__utility/pair.h>621#  include <stdexcept>622#  include <tuple>623#  include <version>624 625// standard-mandated includes626 627// [iterator.range]628#  include <__iterator/access.h>629#  include <__iterator/data.h>630#  include <__iterator/empty.h>631#  include <__iterator/reverse_access.h>632#  include <__iterator/size.h>633 634// [unord.map.syn]635#  include <compare>636#  include <initializer_list>637 638#  if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)639#    pragma GCC system_header640#  endif641 642_LIBCPP_PUSH_MACROS643#  include <__undef_macros>644 645_LIBCPP_BEGIN_NAMESPACE_STD646 647template <class _Key, class _Cp, class _Hash, class _Pred>648class __unordered_map_hasher {649  _LIBCPP_COMPRESSED_ELEMENT(_Hash, __hash_);650 651public:652  _LIBCPP_HIDE_FROM_ABI __unordered_map_hasher() _NOEXCEPT_(is_nothrow_default_constructible<_Hash>::value)653      : __hash_() {}654  _LIBCPP_HIDE_FROM_ABI __unordered_map_hasher(const _Hash& __h) _NOEXCEPT_(is_nothrow_copy_constructible<_Hash>::value)655      : __hash_(__h) {}656  _LIBCPP_HIDE_FROM_ABI const _Hash& hash_function() const _NOEXCEPT { return __hash_; }657  _LIBCPP_HIDE_FROM_ABI size_t operator()(const _Cp& __x) const { return __hash_(__x.first); }658  _LIBCPP_HIDE_FROM_ABI size_t operator()(const _Key& __x) const { return __hash_(__x); }659#  if _LIBCPP_STD_VER >= 20660  template <typename _K2>661  _LIBCPP_HIDE_FROM_ABI size_t operator()(const _K2& __x) const {662    return __hash_(__x);663  }664#  endif665  _LIBCPP_HIDE_FROM_ABI void swap(__unordered_map_hasher& __y) _NOEXCEPT_(__is_nothrow_swappable_v<_Hash>) {666    using std::swap;667    swap(__hash_, __y.__hash_);668  }669};670 671template <class _Key, class _Cp, class _Hash, class _Pred>672inline _LIBCPP_HIDE_FROM_ABI void673swap(__unordered_map_hasher<_Key, _Cp, _Hash, _Pred>& __x, __unordered_map_hasher<_Key, _Cp, _Hash, _Pred>& __y)674    _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) {675  __x.swap(__y);676}677 678template <class _Key, class _Cp, class _Pred, class _Hash>679class __unordered_map_equal {680  _LIBCPP_COMPRESSED_ELEMENT(_Pred, __pred_);681 682public:683  _LIBCPP_HIDE_FROM_ABI __unordered_map_equal() _NOEXCEPT_(is_nothrow_default_constructible<_Pred>::value)684      : __pred_() {}685  _LIBCPP_HIDE_FROM_ABI __unordered_map_equal(const _Pred& __p) _NOEXCEPT_(is_nothrow_copy_constructible<_Pred>::value)686      : __pred_(__p) {}687  _LIBCPP_HIDE_FROM_ABI const _Pred& key_eq() const _NOEXCEPT { return __pred_; }688  _LIBCPP_HIDE_FROM_ABI bool operator()(const _Cp& __x, const _Cp& __y) const { return __pred_(__x.first, __y.first); }689  _LIBCPP_HIDE_FROM_ABI bool operator()(const _Cp& __x, const _Key& __y) const { return __pred_(__x.first, __y); }690  _LIBCPP_HIDE_FROM_ABI bool operator()(const _Key& __x, const _Cp& __y) const { return __pred_(__x, __y.first); }691#  if _LIBCPP_STD_VER >= 20692  template <typename _K2>693  _LIBCPP_HIDE_FROM_ABI bool operator()(const _Cp& __x, const _K2& __y) const {694    return __pred_(__x.first, __y);695  }696  template <typename _K2>697  _LIBCPP_HIDE_FROM_ABI bool operator()(const _K2& __x, const _Cp& __y) const {698    return __pred_(__x, __y.first);699  }700  template <typename _K2>701  _LIBCPP_HIDE_FROM_ABI bool operator()(const _Key& __x, const _K2& __y) const {702    return __pred_(__x, __y);703  }704  template <typename _K2>705  _LIBCPP_HIDE_FROM_ABI bool operator()(const _K2& __x, const _Key& __y) const {706    return __pred_(__x, __y);707  }708#  endif709  _LIBCPP_HIDE_FROM_ABI void swap(__unordered_map_equal& __y) _NOEXCEPT_(__is_nothrow_swappable_v<_Pred>) {710    using std::swap;711    swap(__pred_, __y.__pred_);712  }713};714 715template <class _Key, class _Cp, class _Pred, class _Hash>716inline _LIBCPP_HIDE_FROM_ABI void717swap(__unordered_map_equal<_Key, _Cp, _Pred, _Hash>& __x, __unordered_map_equal<_Key, _Cp, _Pred, _Hash>& __y)718    _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) {719  __x.swap(__y);720}721 722template <class _Alloc>723class __hash_map_node_destructor {724  typedef _Alloc allocator_type;725  typedef allocator_traits<allocator_type> __alloc_traits;726 727public:728  typedef typename __alloc_traits::pointer pointer;729 730private:731  allocator_type& __na_;732 733public:734  bool __first_constructed;735  bool __second_constructed;736 737  __hash_map_node_destructor& operator=(const __hash_map_node_destructor&) = delete;738 739  _LIBCPP_HIDE_FROM_ABI explicit __hash_map_node_destructor(allocator_type& __na) _NOEXCEPT740      : __na_(__na),741        __first_constructed(false),742        __second_constructed(false) {}743 744#  ifndef _LIBCPP_CXX03_LANG745  _LIBCPP_HIDE_FROM_ABI __hash_map_node_destructor(__hash_node_destructor<allocator_type>&& __x) _NOEXCEPT746      : __na_(__x.__na_),747        __first_constructed(__x.__value_constructed),748        __second_constructed(__x.__value_constructed) {749    __x.__value_constructed = false;750  }751#  else  // _LIBCPP_CXX03_LANG752  _LIBCPP_HIDE_FROM_ABI __hash_map_node_destructor(const __hash_node_destructor<allocator_type>& __x)753      : __na_(__x.__na_), __first_constructed(__x.__value_constructed), __second_constructed(__x.__value_constructed) {754    const_cast<bool&>(__x.__value_constructed) = false;755  }756#  endif // _LIBCPP_CXX03_LANG757 758  _LIBCPP_HIDE_FROM_ABI void operator()(pointer __p) _NOEXCEPT {759    if (__second_constructed)760      __alloc_traits::destroy(__na_, std::addressof(__p->__get_value().second));761    if (__first_constructed)762      __alloc_traits::destroy(__na_, std::addressof(__p->__get_value().first));763    if (__p)764      __alloc_traits::deallocate(__na_, __p, 1);765  }766};767 768template <class _Key, class _Tp>769struct __hash_value_type;770 771template <class _HashIterator>772class __hash_map_iterator {773  _HashIterator __i_;774 775  typedef __hash_node_types_from_iterator<_HashIterator> _NodeTypes;776 777public:778  typedef forward_iterator_tag iterator_category;779  using value_type      = typename _HashIterator::value_type;780  using difference_type = ptrdiff_t;781  typedef value_type& reference;782  using pointer = typename _HashIterator::pointer;783 784  _LIBCPP_HIDE_FROM_ABI __hash_map_iterator() _NOEXCEPT {}785 786  _LIBCPP_HIDE_FROM_ABI __hash_map_iterator(_HashIterator __i) _NOEXCEPT : __i_(__i) {}787 788  _LIBCPP_HIDE_FROM_ABI reference operator*() const { return *__i_; }789  _LIBCPP_HIDE_FROM_ABI pointer operator->() const { return pointer_traits<pointer>::pointer_to(*__i_); }790 791  _LIBCPP_HIDE_FROM_ABI __hash_map_iterator& operator++() {792    ++__i_;793    return *this;794  }795  _LIBCPP_HIDE_FROM_ABI __hash_map_iterator operator++(int) {796    __hash_map_iterator __t(*this);797    ++(*this);798    return __t;799  }800 801  friend _LIBCPP_HIDE_FROM_ABI bool operator==(const __hash_map_iterator& __x, const __hash_map_iterator& __y) {802    return __x.__i_ == __y.__i_;803  }804#  if _LIBCPP_STD_VER <= 17805  friend _LIBCPP_HIDE_FROM_ABI bool operator!=(const __hash_map_iterator& __x, const __hash_map_iterator& __y) {806    return __x.__i_ != __y.__i_;807  }808#  endif809 810  template <class, class, class, class, class>811  friend class unordered_map;812  template <class, class, class, class, class>813  friend class unordered_multimap;814  template <class>815  friend class __hash_const_iterator;816  template <class>817  friend class __hash_const_local_iterator;818  template <class>819  friend class __hash_map_const_iterator;820};821 822template <class _HashIterator>823class __hash_map_const_iterator {824  _HashIterator __i_;825 826  typedef __hash_node_types_from_iterator<_HashIterator> _NodeTypes;827 828public:829  typedef forward_iterator_tag iterator_category;830  using value_type      = typename _HashIterator::value_type;831  using difference_type = ptrdiff_t;832  typedef const value_type& reference;833  using pointer = typename _HashIterator::pointer;834 835  _LIBCPP_HIDE_FROM_ABI __hash_map_const_iterator() _NOEXCEPT {}836 837  _LIBCPP_HIDE_FROM_ABI __hash_map_const_iterator(_HashIterator __i) _NOEXCEPT : __i_(__i) {}838  _LIBCPP_HIDE_FROM_ABI839  __hash_map_const_iterator(__hash_map_iterator<typename _HashIterator::__non_const_iterator> __i) _NOEXCEPT840      : __i_(__i.__i_) {}841 842  _LIBCPP_HIDE_FROM_ABI reference operator*() const { return *__i_; }843  _LIBCPP_HIDE_FROM_ABI pointer operator->() const { return pointer_traits<pointer>::pointer_to(*__i_); }844 845  _LIBCPP_HIDE_FROM_ABI __hash_map_const_iterator& operator++() {846    ++__i_;847    return *this;848  }849  _LIBCPP_HIDE_FROM_ABI __hash_map_const_iterator operator++(int) {850    __hash_map_const_iterator __t(*this);851    ++(*this);852    return __t;853  }854 855  friend _LIBCPP_HIDE_FROM_ABI bool856  operator==(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y) {857    return __x.__i_ == __y.__i_;858  }859#  if _LIBCPP_STD_VER <= 17860  friend _LIBCPP_HIDE_FROM_ABI bool861  operator!=(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y) {862    return __x.__i_ != __y.__i_;863  }864#  endif865 866  template <class, class, class, class, class>867  friend class unordered_map;868  template <class, class, class, class, class>869  friend class unordered_multimap;870  template <class>871  friend class __hash_const_iterator;872  template <class>873  friend class __hash_const_local_iterator;874};875 876template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>877class unordered_multimap;878 879template <class _Key,880          class _Tp,881          class _Hash  = hash<_Key>,882          class _Pred  = equal_to<_Key>,883          class _Alloc = allocator<pair<const _Key, _Tp> > >884class unordered_map {885public:886  // types887  typedef _Key key_type;888  typedef _Tp mapped_type;889  typedef __type_identity_t<_Hash> hasher;890  typedef __type_identity_t<_Pred> key_equal;891  typedef __type_identity_t<_Alloc> allocator_type;892  typedef pair<const key_type, mapped_type> value_type;893  typedef value_type& reference;894  typedef const value_type& const_reference;895  static_assert(is_same<value_type, typename allocator_type::value_type>::value,896                "Allocator::value_type must be same type as value_type");897 898private:899  typedef __hash_value_type<key_type, mapped_type> __value_type;900  typedef __unordered_map_hasher<key_type, value_type, hasher, key_equal> __hasher;901  typedef __unordered_map_equal<key_type, value_type, key_equal, hasher> __key_equal;902 903  typedef __hash_table<__value_type, __hasher, __key_equal, allocator_type> __table;904 905  __table __table_;906 907  typedef typename __table::__node_traits __node_traits;908  typedef typename __table::__node_allocator __node_allocator;909  typedef typename __table::__node __node;910  typedef __hash_map_node_destructor<__node_allocator> _Dp;911  typedef unique_ptr<__node, _Dp> __node_holder;912  typedef allocator_traits<allocator_type> __alloc_traits;913 914  static_assert(__check_valid_allocator<allocator_type>::value, "");915 916public:917  typedef typename __alloc_traits::pointer pointer;918  typedef typename __alloc_traits::const_pointer const_pointer;919  typedef typename __table::size_type size_type;920  typedef typename __table::difference_type difference_type;921 922  typedef __hash_map_iterator<typename __table::iterator> iterator;923  typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator;924  typedef __hash_map_iterator<typename __table::local_iterator> local_iterator;925  typedef __hash_map_const_iterator<typename __table::const_local_iterator> const_local_iterator;926 927#  if _LIBCPP_STD_VER >= 17928  typedef __map_node_handle<__node, allocator_type> node_type;929  typedef __insert_return_type<iterator, node_type> insert_return_type;930#  endif931 932  template <class _Key2, class _Tp2, class _Hash2, class _Pred2, class _Alloc2>933  friend class unordered_map;934  template <class _Key2, class _Tp2, class _Hash2, class _Pred2, class _Alloc2>935  friend class unordered_multimap;936 937  _LIBCPP_HIDE_FROM_ABI unordered_map() _NOEXCEPT_(is_nothrow_default_constructible<__table>::value) {}938  explicit _LIBCPP_HIDE_FROM_ABI939  unordered_map(size_type __n, const hasher& __hf = hasher(), const key_equal& __eql = key_equal());940  _LIBCPP_HIDE_FROM_ABI941  unordered_map(size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a);942  template <class _InputIterator>943  _LIBCPP_HIDE_FROM_ABI unordered_map(_InputIterator __first, _InputIterator __last);944  template <class _InputIterator>945  _LIBCPP_HIDE_FROM_ABI946  unordered_map(_InputIterator __first,947                _InputIterator __last,948                size_type __n,949                const hasher& __hf     = hasher(),950                const key_equal& __eql = key_equal());951  template <class _InputIterator>952  _LIBCPP_HIDE_FROM_ABI unordered_map(953      _InputIterator __first,954      _InputIterator __last,955      size_type __n,956      const hasher& __hf,957      const key_equal& __eql,958      const allocator_type& __a);959 960#  if _LIBCPP_STD_VER >= 23961  template <_ContainerCompatibleRange<value_type> _Range>962  _LIBCPP_HIDE_FROM_ABI unordered_map(963      from_range_t,964      _Range&& __range,965      size_type __n             = /*implementation-defined*/ 0,966      const hasher& __hf        = hasher(),967      const key_equal& __eql    = key_equal(),968      const allocator_type& __a = allocator_type())969      : __table_(__hf, __eql, typename __table::allocator_type(__a)) {970    if (__n > 0) {971      __table_.__rehash_unique(__n);972    }973    insert_range(std::forward<_Range>(__range));974  }975#  endif976 977  _LIBCPP_HIDE_FROM_ABI explicit unordered_map(const allocator_type& __a);978  _LIBCPP_HIDE_FROM_ABI unordered_map(const unordered_map& __u) = default;979  _LIBCPP_HIDE_FROM_ABI unordered_map(const unordered_map& __u, const allocator_type& __a);980#  ifndef _LIBCPP_CXX03_LANG981  _LIBCPP_HIDE_FROM_ABI unordered_map(unordered_map&& __u) = default;982  _LIBCPP_HIDE_FROM_ABI unordered_map(unordered_map&& __u, const allocator_type& __a);983  _LIBCPP_HIDE_FROM_ABI unordered_map(initializer_list<value_type> __il);984  _LIBCPP_HIDE_FROM_ABI985  unordered_map(initializer_list<value_type> __il,986                size_type __n,987                const hasher& __hf     = hasher(),988                const key_equal& __eql = key_equal());989  _LIBCPP_HIDE_FROM_ABI unordered_map(990      initializer_list<value_type> __il,991      size_type __n,992      const hasher& __hf,993      const key_equal& __eql,994      const allocator_type& __a);995#  endif // _LIBCPP_CXX03_LANG996#  if _LIBCPP_STD_VER >= 14997  _LIBCPP_HIDE_FROM_ABI unordered_map(size_type __n, const allocator_type& __a)998      : unordered_map(__n, hasher(), key_equal(), __a) {}999  _LIBCPP_HIDE_FROM_ABI unordered_map(size_type __n, const hasher& __hf, const allocator_type& __a)1000      : unordered_map(__n, __hf, key_equal(), __a) {}1001  template <class _InputIterator>1002  _LIBCPP_HIDE_FROM_ABI1003  unordered_map(_InputIterator __first, _InputIterator __last, size_type __n, const allocator_type& __a)1004      : unordered_map(__first, __last, __n, hasher(), key_equal(), __a) {}1005  template <class _InputIterator>1006  _LIBCPP_HIDE_FROM_ABI unordered_map(1007      _InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, const allocator_type& __a)1008      : unordered_map(__first, __last, __n, __hf, key_equal(), __a) {}1009 1010#    if _LIBCPP_STD_VER >= 231011  template <_ContainerCompatibleRange<value_type> _Range>1012  _LIBCPP_HIDE_FROM_ABI unordered_map(from_range_t, _Range&& __range, size_type __n, const allocator_type& __a)1013      : unordered_map(from_range, std::forward<_Range>(__range), __n, hasher(), key_equal(), __a) {}1014 1015  template <_ContainerCompatibleRange<value_type> _Range>1016  _LIBCPP_HIDE_FROM_ABI1017  unordered_map(from_range_t, _Range&& __range, size_type __n, const hasher& __hf, const allocator_type& __a)1018      : unordered_map(from_range, std::forward<_Range>(__range), __n, __hf, key_equal(), __a) {}1019#    endif1020 1021  _LIBCPP_HIDE_FROM_ABI unordered_map(initializer_list<value_type> __il, size_type __n, const allocator_type& __a)1022      : unordered_map(__il, __n, hasher(), key_equal(), __a) {}1023  _LIBCPP_HIDE_FROM_ABI1024  unordered_map(initializer_list<value_type> __il, size_type __n, const hasher& __hf, const allocator_type& __a)1025      : unordered_map(__il, __n, __hf, key_equal(), __a) {}1026#  endif1027  _LIBCPP_HIDE_FROM_ABI ~unordered_map() {1028    static_assert(sizeof(std::__diagnose_unordered_container_requirements<_Key, _Hash, _Pred>(0)), "");1029  }1030 1031  _LIBCPP_HIDE_FROM_ABI unordered_map& operator=(const unordered_map& __u) = default;1032#  ifndef _LIBCPP_CXX03_LANG1033  _LIBCPP_HIDE_FROM_ABI unordered_map& operator=(unordered_map&& __u) = default;1034  _LIBCPP_HIDE_FROM_ABI unordered_map& operator=(initializer_list<value_type> __il);1035#  endif // _LIBCPP_CXX03_LANG1036 1037  _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const _NOEXCEPT {1038    return allocator_type(__table_.__node_alloc());1039  }1040 1041  [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI bool empty() const _NOEXCEPT { return __table_.size() == 0; }1042  _LIBCPP_HIDE_FROM_ABI size_type size() const _NOEXCEPT { return __table_.size(); }1043  _LIBCPP_HIDE_FROM_ABI size_type max_size() const _NOEXCEPT { return __table_.max_size(); }1044 1045  _LIBCPP_HIDE_FROM_ABI iterator begin() _NOEXCEPT { return __table_.begin(); }1046  _LIBCPP_HIDE_FROM_ABI iterator end() _NOEXCEPT { return __table_.end(); }1047  _LIBCPP_HIDE_FROM_ABI const_iterator begin() const _NOEXCEPT { return __table_.begin(); }1048  _LIBCPP_HIDE_FROM_ABI const_iterator end() const _NOEXCEPT { return __table_.end(); }1049  _LIBCPP_HIDE_FROM_ABI const_iterator cbegin() const _NOEXCEPT { return __table_.begin(); }1050  _LIBCPP_HIDE_FROM_ABI const_iterator cend() const _NOEXCEPT { return __table_.end(); }1051 1052  _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert(const value_type& __x) { return __table_.__emplace_unique(__x); }1053 1054  _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator, const value_type& __x) { return insert(__x).first; }1055 1056  template <class _InputIterator>1057  _LIBCPP_HIDE_FROM_ABI void insert(_InputIterator __first, _InputIterator __last);1058 1059#  if _LIBCPP_STD_VER >= 231060  template <_ContainerCompatibleRange<value_type> _Range>1061  _LIBCPP_HIDE_FROM_ABI void insert_range(_Range&& __range) {1062    for (auto&& __element : __range) {1063      __table_.__emplace_unique(std::forward<decltype(__element)>(__element));1064    }1065  }1066#  endif1067 1068#  ifndef _LIBCPP_CXX03_LANG1069  _LIBCPP_HIDE_FROM_ABI void insert(initializer_list<value_type> __il) { insert(__il.begin(), __il.end()); }1070 1071  _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert(value_type&& __x) {1072    return __table_.__emplace_unique(std::move(__x));1073  }1074 1075  _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator, value_type&& __x) {1076    return __table_.__emplace_unique(std::move(__x)).first;1077  }1078 1079  template <class _Pp, __enable_if_t<is_constructible<value_type, _Pp>::value, int> = 0>1080  _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert(_Pp&& __x) {1081    return __table_.__emplace_unique(std::forward<_Pp>(__x));1082  }1083 1084  template <class _Pp, __enable_if_t<is_constructible<value_type, _Pp>::value, int> = 0>1085  _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator, _Pp&& __x) {1086    return insert(std::forward<_Pp>(__x)).first;1087  }1088 1089  template <class... _Args>1090  _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> emplace(_Args&&... __args) {1091    return __table_.__emplace_unique(std::forward<_Args>(__args)...);1092  }1093 1094  template <class... _Args>1095  _LIBCPP_HIDE_FROM_ABI iterator emplace_hint(const_iterator, _Args&&... __args) {1096    return __table_.__emplace_unique(std::forward<_Args>(__args)...).first;1097  }1098 1099#  endif // _LIBCPP_CXX03_LANG1100 1101#  if _LIBCPP_STD_VER >= 171102  template <class... _Args>1103  _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> try_emplace(const key_type& __k, _Args&&... __args) {1104    return __table_.__emplace_unique(1105        piecewise_construct, std::forward_as_tuple(__k), std::forward_as_tuple(std::forward<_Args>(__args)...));1106  }1107 1108  template <class... _Args>1109  _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> try_emplace(key_type&& __k, _Args&&... __args) {1110    return __table_.__emplace_unique(1111        piecewise_construct,1112        std::forward_as_tuple(std::move(__k)),1113        std::forward_as_tuple(std::forward<_Args>(__args)...));1114  }1115 1116  template <class... _Args>1117  _LIBCPP_HIDE_FROM_ABI iterator try_emplace(const_iterator, const key_type& __k, _Args&&... __args) {1118    return try_emplace(__k, std::forward<_Args>(__args)...).first;1119  }1120 1121  template <class... _Args>1122  _LIBCPP_HIDE_FROM_ABI iterator try_emplace(const_iterator, key_type&& __k, _Args&&... __args) {1123    return try_emplace(std::move(__k), std::forward<_Args>(__args)...).first;1124  }1125 1126  template <class _Vp>1127  _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert_or_assign(const key_type& __k, _Vp&& __v) {1128    pair<iterator, bool> __res = __table_.__emplace_unique(__k, std::forward<_Vp>(__v));1129    if (!__res.second) {1130      __res.first->second = std::forward<_Vp>(__v);1131    }1132    return __res;1133  }1134 1135  template <class _Vp>1136  _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert_or_assign(key_type&& __k, _Vp&& __v) {1137    pair<iterator, bool> __res = __table_.__emplace_unique(std::move(__k), std::forward<_Vp>(__v));1138    if (!__res.second) {1139      __res.first->second = std::forward<_Vp>(__v);1140    }1141    return __res;1142  }1143 1144  template <class _Vp>1145  _LIBCPP_HIDE_FROM_ABI iterator insert_or_assign(const_iterator, const key_type& __k, _Vp&& __v) {1146    return insert_or_assign(__k, std::forward<_Vp>(__v)).first;1147  }1148 1149  template <class _Vp>1150  _LIBCPP_HIDE_FROM_ABI iterator insert_or_assign(const_iterator, key_type&& __k, _Vp&& __v) {1151    return insert_or_assign(std::move(__k), std::forward<_Vp>(__v)).first;1152  }1153#  endif // _LIBCPP_STD_VER >= 171154 1155  _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __p) { return __table_.erase(__p.__i_); }1156  _LIBCPP_HIDE_FROM_ABI iterator erase(iterator __p) { return __table_.erase(__p.__i_); }1157  _LIBCPP_HIDE_FROM_ABI size_type erase(const key_type& __k) { return __table_.__erase_unique(__k); }1158  _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __first, const_iterator __last) {1159    return __table_.erase(__first.__i_, __last.__i_);1160  }1161  _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT { __table_.clear(); }1162 1163#  if _LIBCPP_STD_VER >= 171164  _LIBCPP_HIDE_FROM_ABI insert_return_type insert(node_type&& __nh) {1165    _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(),1166                                        "node_type with incompatible allocator passed to unordered_map::insert()");1167    return __table_.template __node_handle_insert_unique< node_type, insert_return_type>(std::move(__nh));1168  }1169  _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __hint, node_type&& __nh) {1170    _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(),1171                                        "node_type with incompatible allocator passed to unordered_map::insert()");1172    return __table_.template __node_handle_insert_unique<node_type>(__hint.__i_, std::move(__nh));1173  }1174  _LIBCPP_HIDE_FROM_ABI node_type extract(key_type const& __key) {1175    return __table_.template __node_handle_extract<node_type>(__key);1176  }1177  _LIBCPP_HIDE_FROM_ABI node_type extract(const_iterator __it) {1178    return __table_.template __node_handle_extract<node_type>(__it.__i_);1179  }1180 1181  template <class _H2, class _P2>1182  _LIBCPP_HIDE_FROM_ABI void merge(unordered_map<key_type, mapped_type, _H2, _P2, allocator_type>& __source) {1183    _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(1184        __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");1185    return __table_.__node_handle_merge_unique(__source.__table_);1186  }1187  template <class _H2, class _P2>1188  _LIBCPP_HIDE_FROM_ABI void merge(unordered_map<key_type, mapped_type, _H2, _P2, allocator_type>&& __source) {1189    _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(1190        __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");1191    return __table_.__node_handle_merge_unique(__source.__table_);1192  }1193  template <class _H2, class _P2>1194  _LIBCPP_HIDE_FROM_ABI void merge(unordered_multimap<key_type, mapped_type, _H2, _P2, allocator_type>& __source) {1195    _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(1196        __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");1197    return __table_.__node_handle_merge_unique(__source.__table_);1198  }1199  template <class _H2, class _P2>1200  _LIBCPP_HIDE_FROM_ABI void merge(unordered_multimap<key_type, mapped_type, _H2, _P2, allocator_type>&& __source) {1201    _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(1202        __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");1203    return __table_.__node_handle_merge_unique(__source.__table_);1204  }1205#  endif1206 1207  _LIBCPP_HIDE_FROM_ABI void swap(unordered_map& __u) _NOEXCEPT_(__is_nothrow_swappable_v<__table>) {1208    __table_.swap(__u.__table_);1209  }1210 1211  _LIBCPP_HIDE_FROM_ABI hasher hash_function() const { return __table_.hash_function().hash_function(); }1212  _LIBCPP_HIDE_FROM_ABI key_equal key_eq() const { return __table_.key_eq().key_eq(); }1213 1214  _LIBCPP_HIDE_FROM_ABI iterator find(const key_type& __k) { return __table_.find(__k); }1215  _LIBCPP_HIDE_FROM_ABI const_iterator find(const key_type& __k) const { return __table_.find(__k); }1216#  if _LIBCPP_STD_VER >= 201217  template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr>1218  _LIBCPP_HIDE_FROM_ABI iterator find(const _K2& __k) {1219    return __table_.find(__k);1220  }1221  template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr>1222  _LIBCPP_HIDE_FROM_ABI const_iterator find(const _K2& __k) const {1223    return __table_.find(__k);1224  }1225#  endif // _LIBCPP_STD_VER >= 201226 1227  _LIBCPP_HIDE_FROM_ABI size_type count(const key_type& __k) const { return __table_.__count_unique(__k); }1228#  if _LIBCPP_STD_VER >= 201229  template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr>1230  _LIBCPP_HIDE_FROM_ABI size_type count(const _K2& __k) const {1231    return __table_.__count_unique(__k);1232  }1233#  endif // _LIBCPP_STD_VER >= 201234 1235#  if _LIBCPP_STD_VER >= 201236  _LIBCPP_HIDE_FROM_ABI bool contains(const key_type& __k) const { return find(__k) != end(); }1237 1238  template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr>1239  _LIBCPP_HIDE_FROM_ABI bool contains(const _K2& __k) const {1240    return find(__k) != end();1241  }1242#  endif // _LIBCPP_STD_VER >= 201243 1244  _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const key_type& __k) {1245    return __table_.__equal_range_unique(__k);1246  }1247  _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const key_type& __k) const {1248    return __table_.__equal_range_unique(__k);1249  }1250#  if _LIBCPP_STD_VER >= 201251  template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr>1252  _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const _K2& __k) {1253    return __table_.__equal_range_unique(__k);1254  }1255  template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr>1256  _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const _K2& __k) const {1257    return __table_.__equal_range_unique(__k);1258  }1259#  endif // _LIBCPP_STD_VER >= 201260 1261  _LIBCPP_HIDE_FROM_ABI mapped_type& operator[](const key_type& __k);1262#  ifndef _LIBCPP_CXX03_LANG1263  _LIBCPP_HIDE_FROM_ABI mapped_type& operator[](key_type&& __k);1264#  endif1265 1266  _LIBCPP_HIDE_FROM_ABI mapped_type& at(const key_type& __k);1267  _LIBCPP_HIDE_FROM_ABI const mapped_type& at(const key_type& __k) const;1268 1269  _LIBCPP_HIDE_FROM_ABI size_type bucket_count() const _NOEXCEPT { return __table_.bucket_count(); }1270  _LIBCPP_HIDE_FROM_ABI size_type max_bucket_count() const _NOEXCEPT { return __table_.max_bucket_count(); }1271 1272  _LIBCPP_HIDE_FROM_ABI size_type bucket_size(size_type __n) const { return __table_.bucket_size(__n); }1273  _LIBCPP_HIDE_FROM_ABI size_type bucket(const key_type& __k) const { return __table_.bucket(__k); }1274 1275  _LIBCPP_HIDE_FROM_ABI local_iterator begin(size_type __n) { return __table_.begin(__n); }1276  _LIBCPP_HIDE_FROM_ABI local_iterator end(size_type __n) { return __table_.end(__n); }1277  _LIBCPP_HIDE_FROM_ABI const_local_iterator begin(size_type __n) const { return __table_.cbegin(__n); }1278  _LIBCPP_HIDE_FROM_ABI const_local_iterator end(size_type __n) const { return __table_.cend(__n); }1279  _LIBCPP_HIDE_FROM_ABI const_local_iterator cbegin(size_type __n) const { return __table_.cbegin(__n); }1280  _LIBCPP_HIDE_FROM_ABI const_local_iterator cend(size_type __n) const { return __table_.cend(__n); }1281 1282  _LIBCPP_HIDE_FROM_ABI float load_factor() const _NOEXCEPT { return __table_.load_factor(); }1283  _LIBCPP_HIDE_FROM_ABI float max_load_factor() const _NOEXCEPT { return __table_.max_load_factor(); }1284  _LIBCPP_HIDE_FROM_ABI void max_load_factor(float __mlf) { __table_.max_load_factor(__mlf); }1285  _LIBCPP_HIDE_FROM_ABI void rehash(size_type __n) { __table_.__rehash_unique(__n); }1286  _LIBCPP_HIDE_FROM_ABI void reserve(size_type __n) { __table_.__reserve_unique(__n); }1287 1288private:1289#  ifdef _LIBCPP_CXX03_LANG1290  _LIBCPP_HIDE_FROM_ABI __node_holder __construct_node_with_key(const key_type& __k);1291#  endif1292};1293 1294#  if _LIBCPP_STD_VER >= 171295template <class _InputIterator,1296          class _Hash      = hash<__iter_key_type<_InputIterator>>,1297          class _Pred      = equal_to<__iter_key_type<_InputIterator>>,1298          class _Allocator = allocator<__iter_to_alloc_type<_InputIterator>>,1299          class            = enable_if_t<__has_input_iterator_category<_InputIterator>::value>,1300          class            = enable_if_t<!__is_allocator_v<_Hash>>,1301          class            = enable_if_t<!is_integral<_Hash>::value>,1302          class            = enable_if_t<!__is_allocator_v<_Pred>>,1303          class            = enable_if_t<__is_allocator_v<_Allocator>>>1304unordered_map(_InputIterator,1305              _InputIterator,1306              typename allocator_traits<_Allocator>::size_type = 0,1307              _Hash                                            = _Hash(),1308              _Pred                                            = _Pred(),1309              _Allocator                                       = _Allocator())1310    -> unordered_map<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>, _Hash, _Pred, _Allocator>;1311 1312#    if _LIBCPP_STD_VER >= 231313template <ranges::input_range _Range,1314          class _Hash      = hash<__range_key_type<_Range>>,1315          class _Pred      = equal_to<__range_key_type<_Range>>,1316          class _Allocator = allocator<__range_to_alloc_type<_Range>>,1317          class            = enable_if_t<!__is_allocator_v<_Hash>>,1318          class            = enable_if_t<!is_integral<_Hash>::value>,1319          class            = enable_if_t<!__is_allocator_v<_Pred>>,1320          class            = enable_if_t<__is_allocator_v<_Allocator>>>1321unordered_map(from_range_t,1322              _Range&&,1323              typename allocator_traits<_Allocator>::size_type = 0,1324              _Hash                                            = _Hash(),1325              _Pred                                            = _Pred(),1326              _Allocator                                       = _Allocator())1327    -> unordered_map<__range_key_type<_Range>, __range_mapped_type<_Range>, _Hash, _Pred, _Allocator>; // C++231328#    endif1329 1330template <class _Key,1331          class _Tp,1332          class _Hash      = hash<remove_const_t<_Key>>,1333          class _Pred      = equal_to<remove_const_t<_Key>>,1334          class _Allocator = allocator<pair<const _Key, _Tp>>,1335          class            = enable_if_t<!__is_allocator_v<_Hash>>,1336          class            = enable_if_t<!is_integral<_Hash>::value>,1337          class            = enable_if_t<!__is_allocator_v<_Pred>>,1338          class            = enable_if_t<__is_allocator_v<_Allocator>>>1339unordered_map(initializer_list<pair<_Key, _Tp>>,1340              typename allocator_traits<_Allocator>::size_type = 0,1341              _Hash                                            = _Hash(),1342              _Pred                                            = _Pred(),1343              _Allocator = _Allocator()) -> unordered_map<remove_const_t<_Key>, _Tp, _Hash, _Pred, _Allocator>;1344 1345template <class _InputIterator,1346          class _Allocator,1347          class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>,1348          class = enable_if_t<__is_allocator_v<_Allocator>>>1349unordered_map(_InputIterator, _InputIterator, typename allocator_traits<_Allocator>::size_type, _Allocator)1350    -> unordered_map<__iter_key_type<_InputIterator>,1351                     __iter_mapped_type<_InputIterator>,1352                     hash<__iter_key_type<_InputIterator>>,1353                     equal_to<__iter_key_type<_InputIterator>>,1354                     _Allocator>;1355 1356template <class _InputIterator,1357          class _Allocator,1358          class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>,1359          class = enable_if_t<__is_allocator_v<_Allocator>>>1360unordered_map(_InputIterator, _InputIterator, _Allocator)1361    -> unordered_map<__iter_key_type<_InputIterator>,1362                     __iter_mapped_type<_InputIterator>,1363                     hash<__iter_key_type<_InputIterator>>,1364                     equal_to<__iter_key_type<_InputIterator>>,1365                     _Allocator>;1366 1367template <class _InputIterator,1368          class _Hash,1369          class _Allocator,1370          class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>,1371          class = enable_if_t<!__is_allocator_v<_Hash>>,1372          class = enable_if_t<!is_integral<_Hash>::value>,1373          class = enable_if_t<__is_allocator_v<_Allocator>>>1374unordered_map(_InputIterator, _InputIterator, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator)1375    -> unordered_map<__iter_key_type<_InputIterator>,1376                     __iter_mapped_type<_InputIterator>,1377                     _Hash,1378                     equal_to<__iter_key_type<_InputIterator>>,1379                     _Allocator>;1380 1381#    if _LIBCPP_STD_VER >= 231382 1383template <ranges::input_range _Range, class _Allocator, class = enable_if_t<__is_allocator_v<_Allocator>>>1384unordered_map(from_range_t, _Range&&, typename allocator_traits<_Allocator>::size_type, _Allocator)1385    -> unordered_map<__range_key_type<_Range>,1386                     __range_mapped_type<_Range>,1387                     hash<__range_key_type<_Range>>,1388                     equal_to<__range_key_type<_Range>>,1389                     _Allocator>;1390 1391template <ranges::input_range _Range, class _Allocator, class = enable_if_t<__is_allocator_v<_Allocator>>>1392unordered_map(from_range_t, _Range&&, _Allocator)1393    -> unordered_map<__range_key_type<_Range>,1394                     __range_mapped_type<_Range>,1395                     hash<__range_key_type<_Range>>,1396                     equal_to<__range_key_type<_Range>>,1397                     _Allocator>;1398 1399template <ranges::input_range _Range,1400          class _Hash,1401          class _Allocator,1402          class = enable_if_t<!__is_allocator_v<_Hash>>,1403          class = enable_if_t<!is_integral<_Hash>::value>,1404          class = enable_if_t<__is_allocator_v<_Allocator>>>1405unordered_map(from_range_t, _Range&&, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator)1406    -> unordered_map<__range_key_type<_Range>,1407                     __range_mapped_type<_Range>,1408                     _Hash,1409                     equal_to<__range_key_type<_Range>>,1410                     _Allocator>;1411 1412#    endif1413 1414template <class _Key, class _Tp, class _Allocator, class = enable_if_t<__is_allocator_v<_Allocator>>>1415unordered_map(initializer_list<pair<_Key, _Tp>>, typename allocator_traits<_Allocator>::size_type, _Allocator)1416    -> unordered_map<remove_const_t<_Key>, _Tp, hash<remove_const_t<_Key>>, equal_to<remove_const_t<_Key>>, _Allocator>;1417 1418template <class _Key, class _Tp, class _Allocator, class = enable_if_t<__is_allocator_v<_Allocator>>>1419unordered_map(initializer_list<pair<_Key, _Tp>>, _Allocator)1420    -> unordered_map<remove_const_t<_Key>, _Tp, hash<remove_const_t<_Key>>, equal_to<remove_const_t<_Key>>, _Allocator>;1421 1422template <class _Key,1423          class _Tp,1424          class _Hash,1425          class _Allocator,1426          class = enable_if_t<!__is_allocator_v<_Hash>>,1427          class = enable_if_t<!is_integral<_Hash>::value>,1428          class = enable_if_t<__is_allocator_v<_Allocator>>>1429unordered_map(initializer_list<pair<_Key, _Tp>>, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator)1430    -> unordered_map<remove_const_t<_Key>, _Tp, _Hash, equal_to<remove_const_t<_Key>>, _Allocator>;1431#  endif1432 1433template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>1434unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(size_type __n, const hasher& __hf, const key_equal& __eql)1435    : __table_(__hf, __eql) {1436  __table_.__rehash_unique(__n);1437}1438 1439template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>1440unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(1441    size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a)1442    : __table_(__hf, __eql, typename __table::allocator_type(__a)) {1443  __table_.__rehash_unique(__n);1444}1445 1446template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>1447inline unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(const allocator_type& __a)1448    : __table_(typename __table::allocator_type(__a)) {}1449 1450template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>1451template <class _InputIterator>1452unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(_InputIterator __first, _InputIterator __last) {1453  insert(__first, __last);1454}1455 1456template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>1457template <class _InputIterator>1458unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(1459    _InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, const key_equal& __eql)1460    : __table_(__hf, __eql) {1461  __table_.__rehash_unique(__n);1462  insert(__first, __last);1463}1464 1465template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>1466template <class _InputIterator>1467unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(1468    _InputIterator __first,1469    _InputIterator __last,1470    size_type __n,1471    const hasher& __hf,1472    const key_equal& __eql,1473    const allocator_type& __a)1474    : __table_(__hf, __eql, typename __table::allocator_type(__a)) {1475  __table_.__rehash_unique(__n);1476  insert(__first, __last);1477}1478 1479template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>1480unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(const unordered_map& __u, const allocator_type& __a)1481    : __table_(__u.__table_, typename __table::allocator_type(__a)) {1482  __table_.__rehash_unique(__u.bucket_count());1483  insert(__u.begin(), __u.end());1484}1485 1486#  ifndef _LIBCPP_CXX03_LANG1487 1488template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>1489unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(unordered_map&& __u, const allocator_type& __a)1490    : __table_(std::move(__u.__table_), typename __table::allocator_type(__a)) {1491  if (__a != __u.get_allocator()) {1492    iterator __i = __u.begin();1493    while (__u.size() != 0)1494      __table_.__insert_unique_from_orphaned_node(std::move(__u.__table_.remove((__i++).__i_)->__get_value()));1495  }1496}1497 1498template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>1499unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(initializer_list<value_type> __il) {1500  insert(__il.begin(), __il.end());1501}1502 1503template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>1504unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(1505    initializer_list<value_type> __il, size_type __n, const hasher& __hf, const key_equal& __eql)1506    : __table_(__hf, __eql) {1507  __table_.__rehash_unique(__n);1508  insert(__il.begin(), __il.end());1509}1510 1511template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>1512unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map(1513    initializer_list<value_type> __il,1514    size_type __n,1515    const hasher& __hf,1516    const key_equal& __eql,1517    const allocator_type& __a)1518    : __table_(__hf, __eql, typename __table::allocator_type(__a)) {1519  __table_.__rehash_unique(__n);1520  insert(__il.begin(), __il.end());1521}1522 1523template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>1524inline unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>&1525unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(initializer_list<value_type> __il) {1526  __table_.__assign_unique(__il.begin(), __il.end());1527  return *this;1528}1529 1530#  endif // _LIBCPP_CXX03_LANG1531 1532template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>1533template <class _InputIterator>1534inline void unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, _InputIterator __last) {1535  for (; __first != __last; ++__first)1536    __table_.__emplace_unique(*__first);1537}1538 1539#  ifndef _LIBCPP_CXX03_LANG1540 1541template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>1542_Tp& unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](const key_type& __k) {1543  return __table_.__emplace_unique(piecewise_construct, std::forward_as_tuple(__k), std::forward_as_tuple())1544      .first->second;1545}1546 1547template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>1548_Tp& unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](key_type&& __k) {1549  return __table_.__emplace_unique(piecewise_construct, std::forward_as_tuple(std::move(__k)), std::forward_as_tuple())1550      .first->second;1551}1552#  else // _LIBCPP_CXX03_LANG1553 1554template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>1555typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder1556unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node_with_key(const key_type& __k) {1557  __node_allocator& __na = __table_.__node_alloc();1558  __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));1559  __node_traits::construct(__na, std::addressof(__h->__get_value().first), __k);1560  __h.get_deleter().__first_constructed = true;1561  __node_traits::construct(__na, std::addressof(__h->__get_value().second));1562  __h.get_deleter().__second_constructed = true;1563  return __h;1564}1565 1566template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>1567_Tp& unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](const key_type& __k) {1568  iterator __i = find(__k);1569  if (__i != end())1570    return __i->second;1571  __node_holder __h        = __construct_node_with_key(__k);1572  pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get());1573  __h.release();1574  return __r.first->second;1575}1576 1577#  endif // _LIBCPP_CXX03_LANG1578 1579template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>1580_Tp& unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::at(const key_type& __k) {1581  iterator __i = find(__k);1582  if (__i == end())1583    std::__throw_out_of_range("unordered_map::at: key not found");1584  return __i->second;1585}1586 1587template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>1588const _Tp& unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::at(const key_type& __k) const {1589  const_iterator __i = find(__k);1590  if (__i == end())1591    std::__throw_out_of_range("unordered_map::at: key not found");1592  return __i->second;1593}1594 1595template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>1596inline _LIBCPP_HIDE_FROM_ABI void1597swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)1598    _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) {1599  __x.swap(__y);1600}1601 1602#  if _LIBCPP_STD_VER >= 201603template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc, class _Predicate>1604inline _LIBCPP_HIDE_FROM_ABI typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::size_type1605erase_if(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __c, _Predicate __pred) {1606  return std::__libcpp_erase_if_container(__c, __pred);1607}1608#  endif1609 1610template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>1611_LIBCPP_HIDE_FROM_ABI bool operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,1612                                      const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) {1613  if (__x.size() != __y.size())1614    return false;1615  typedef typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator const_iterator;1616  for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end(); __i != __ex; ++__i) {1617    const_iterator __j = __y.find(__i->first);1618    if (__j == __ey || !(*__i == *__j))1619      return false;1620  }1621  return true;1622}1623 1624#  if _LIBCPP_STD_VER <= 171625 1626template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>1627inline _LIBCPP_HIDE_FROM_ABI bool operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,1628                                             const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) {1629  return !(__x == __y);1630}1631 1632#  endif1633 1634template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>1635struct __container_traits<unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc> > {1636  // http://eel.is/c++draft/unord.req.except#21637  //  For unordered associative containers, if an exception is thrown by any operation1638  //  other than the container's hash function from within an insert or emplace function1639  //  inserting a single element, the insertion has no effect.1640  static _LIBCPP_CONSTEXPR const bool __emplacement_has_strong_exception_safety_guarantee =1641      __is_nothrow_invocable_v<_Hash, const _Key&>;1642 1643  static _LIBCPP_CONSTEXPR const bool __reservable = true;1644};1645 1646template <class _Key,1647          class _Tp,1648          class _Hash  = hash<_Key>,1649          class _Pred  = equal_to<_Key>,1650          class _Alloc = allocator<pair<const _Key, _Tp> > >1651class unordered_multimap {1652public:1653  // types1654  typedef _Key key_type;1655  typedef _Tp mapped_type;1656  typedef __type_identity_t<_Hash> hasher;1657  typedef __type_identity_t<_Pred> key_equal;1658  typedef __type_identity_t<_Alloc> allocator_type;1659  typedef pair<const key_type, mapped_type> value_type;1660  typedef value_type& reference;1661  typedef const value_type& const_reference;1662  static_assert(__check_valid_allocator<allocator_type>::value, "");1663  static_assert(is_same<value_type, typename allocator_type::value_type>::value,1664                "Allocator::value_type must be same type as value_type");1665 1666private:1667  typedef __hash_value_type<key_type, mapped_type> __value_type;1668  typedef __unordered_map_hasher<key_type, value_type, hasher, key_equal> __hasher;1669  typedef __unordered_map_equal<key_type, value_type, key_equal, hasher> __key_equal;1670 1671  typedef __hash_table<__value_type, __hasher, __key_equal, allocator_type> __table;1672 1673  __table __table_;1674 1675  typedef typename __table::__node_traits __node_traits;1676  typedef typename __table::__node __node;1677  typedef allocator_traits<allocator_type> __alloc_traits;1678  static_assert(is_same<typename __node_traits::size_type, typename __alloc_traits::size_type>::value,1679                "Allocator uses different size_type for different types");1680 1681public:1682  typedef typename __alloc_traits::pointer pointer;1683  typedef typename __alloc_traits::const_pointer const_pointer;1684  typedef typename __table::size_type size_type;1685  typedef typename __table::difference_type difference_type;1686 1687  typedef __hash_map_iterator<typename __table::iterator> iterator;1688  typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator;1689  typedef __hash_map_iterator<typename __table::local_iterator> local_iterator;1690  typedef __hash_map_const_iterator<typename __table::const_local_iterator> const_local_iterator;1691 1692#  if _LIBCPP_STD_VER >= 171693  typedef __map_node_handle<__node, allocator_type> node_type;1694#  endif1695 1696  template <class _Key2, class _Tp2, class _Hash2, class _Pred2, class _Alloc2>1697  friend class unordered_map;1698  template <class _Key2, class _Tp2, class _Hash2, class _Pred2, class _Alloc2>1699  friend class unordered_multimap;1700 1701  _LIBCPP_HIDE_FROM_ABI unordered_multimap() _NOEXCEPT_(is_nothrow_default_constructible<__table>::value) {}1702  explicit _LIBCPP_HIDE_FROM_ABI1703  unordered_multimap(size_type __n, const hasher& __hf = hasher(), const key_equal& __eql = key_equal());1704  _LIBCPP_HIDE_FROM_ABI1705  unordered_multimap(size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a);1706  template <class _InputIterator>1707  _LIBCPP_HIDE_FROM_ABI unordered_multimap(_InputIterator __first, _InputIterator __last);1708  template <class _InputIterator>1709  _LIBCPP_HIDE_FROM_ABI unordered_multimap(1710      _InputIterator __first,1711      _InputIterator __last,1712      size_type __n,1713      const hasher& __hf     = hasher(),1714      const key_equal& __eql = key_equal());1715  template <class _InputIterator>1716  _LIBCPP_HIDE_FROM_ABI unordered_multimap(1717      _InputIterator __first,1718      _InputIterator __last,1719      size_type __n,1720      const hasher& __hf,1721      const key_equal& __eql,1722      const allocator_type& __a);1723 1724#  if _LIBCPP_STD_VER >= 231725  template <_ContainerCompatibleRange<value_type> _Range>1726  _LIBCPP_HIDE_FROM_ABI unordered_multimap(1727      from_range_t,1728      _Range&& __range,1729      size_type __n             = /*implementation-defined*/ 0,1730      const hasher& __hf        = hasher(),1731      const key_equal& __eql    = key_equal(),1732      const allocator_type& __a = allocator_type())1733      : __table_(__hf, __eql, typename __table::allocator_type(__a)) {1734    if (__n > 0) {1735      __table_.__rehash_multi(__n);1736    }1737    insert_range(std::forward<_Range>(__range));1738  }1739#  endif1740 1741  _LIBCPP_HIDE_FROM_ABI explicit unordered_multimap(const allocator_type& __a);1742  _LIBCPP_HIDE_FROM_ABI unordered_multimap(const unordered_multimap& __u) = default;1743  _LIBCPP_HIDE_FROM_ABI unordered_multimap(const unordered_multimap& __u, const allocator_type& __a);1744#  ifndef _LIBCPP_CXX03_LANG1745  _LIBCPP_HIDE_FROM_ABI unordered_multimap(unordered_multimap&& __u) = default;1746  _LIBCPP_HIDE_FROM_ABI unordered_multimap(unordered_multimap&& __u, const allocator_type& __a);1747  _LIBCPP_HIDE_FROM_ABI unordered_multimap(initializer_list<value_type> __il);1748  _LIBCPP_HIDE_FROM_ABI unordered_multimap(1749      initializer_list<value_type> __il,1750      size_type __n,1751      const hasher& __hf     = hasher(),1752      const key_equal& __eql = key_equal());1753  _LIBCPP_HIDE_FROM_ABI unordered_multimap(1754      initializer_list<value_type> __il,1755      size_type __n,1756      const hasher& __hf,1757      const key_equal& __eql,1758      const allocator_type& __a);1759#  endif // _LIBCPP_CXX03_LANG1760#  if _LIBCPP_STD_VER >= 141761  _LIBCPP_HIDE_FROM_ABI unordered_multimap(size_type __n, const allocator_type& __a)1762      : unordered_multimap(__n, hasher(), key_equal(), __a) {}1763  _LIBCPP_HIDE_FROM_ABI unordered_multimap(size_type __n, const hasher& __hf, const allocator_type& __a)1764      : unordered_multimap(__n, __hf, key_equal(), __a) {}1765  template <class _InputIterator>1766  _LIBCPP_HIDE_FROM_ABI1767  unordered_multimap(_InputIterator __first, _InputIterator __last, size_type __n, const allocator_type& __a)1768      : unordered_multimap(__first, __last, __n, hasher(), key_equal(), __a) {}1769  template <class _InputIterator>1770  _LIBCPP_HIDE_FROM_ABI unordered_multimap(1771      _InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, const allocator_type& __a)1772      : unordered_multimap(__first, __last, __n, __hf, key_equal(), __a) {}1773 1774#    if _LIBCPP_STD_VER >= 231775  template <_ContainerCompatibleRange<value_type> _Range>1776  _LIBCPP_HIDE_FROM_ABI unordered_multimap(from_range_t, _Range&& __range, size_type __n, const allocator_type& __a)1777      : unordered_multimap(from_range, std::forward<_Range>(__range), __n, hasher(), key_equal(), __a) {}1778 1779  template <_ContainerCompatibleRange<value_type> _Range>1780  _LIBCPP_HIDE_FROM_ABI1781  unordered_multimap(from_range_t, _Range&& __range, size_type __n, const hasher& __hf, const allocator_type& __a)1782      : unordered_multimap(from_range, std::forward<_Range>(__range), __n, __hf, key_equal(), __a) {}1783#    endif1784 1785  _LIBCPP_HIDE_FROM_ABI unordered_multimap(initializer_list<value_type> __il, size_type __n, const allocator_type& __a)1786      : unordered_multimap(__il, __n, hasher(), key_equal(), __a) {}1787  _LIBCPP_HIDE_FROM_ABI1788  unordered_multimap(initializer_list<value_type> __il, size_type __n, const hasher& __hf, const allocator_type& __a)1789      : unordered_multimap(__il, __n, __hf, key_equal(), __a) {}1790#  endif1791  _LIBCPP_HIDE_FROM_ABI ~unordered_multimap() {1792    static_assert(sizeof(std::__diagnose_unordered_container_requirements<_Key, _Hash, _Pred>(0)), "");1793  }1794 1795  _LIBCPP_HIDE_FROM_ABI unordered_multimap& operator=(const unordered_multimap& __u) = default;1796#  ifndef _LIBCPP_CXX03_LANG1797  _LIBCPP_HIDE_FROM_ABI unordered_multimap& operator=(unordered_multimap&& __u) = default;1798  _LIBCPP_HIDE_FROM_ABI unordered_multimap& operator=(initializer_list<value_type> __il);1799#  endif // _LIBCPP_CXX03_LANG1800 1801  _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const _NOEXCEPT {1802    return allocator_type(__table_.__node_alloc());1803  }1804 1805  [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI bool empty() const _NOEXCEPT { return __table_.size() == 0; }1806  _LIBCPP_HIDE_FROM_ABI size_type size() const _NOEXCEPT { return __table_.size(); }1807  _LIBCPP_HIDE_FROM_ABI size_type max_size() const _NOEXCEPT { return __table_.max_size(); }1808 1809  _LIBCPP_HIDE_FROM_ABI iterator begin() _NOEXCEPT { return __table_.begin(); }1810  _LIBCPP_HIDE_FROM_ABI iterator end() _NOEXCEPT { return __table_.end(); }1811  _LIBCPP_HIDE_FROM_ABI const_iterator begin() const _NOEXCEPT { return __table_.begin(); }1812  _LIBCPP_HIDE_FROM_ABI const_iterator end() const _NOEXCEPT { return __table_.end(); }1813  _LIBCPP_HIDE_FROM_ABI const_iterator cbegin() const _NOEXCEPT { return __table_.begin(); }1814  _LIBCPP_HIDE_FROM_ABI const_iterator cend() const _NOEXCEPT { return __table_.end(); }1815 1816  _LIBCPP_HIDE_FROM_ABI iterator insert(const value_type& __x) { return __table_.__emplace_multi(__x); }1817 1818  _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, const value_type& __x) {1819    return __table_.__emplace_hint_multi(__p.__i_, __x);1820  }1821 1822  template <class _InputIterator>1823  _LIBCPP_HIDE_FROM_ABI void insert(_InputIterator __first, _InputIterator __last);1824 1825#  if _LIBCPP_STD_VER >= 231826  template <_ContainerCompatibleRange<value_type> _Range>1827  _LIBCPP_HIDE_FROM_ABI void insert_range(_Range&& __range) {1828    for (auto&& __element : __range) {1829      __table_.__emplace_multi(std::forward<decltype(__element)>(__element));1830    }1831  }1832#  endif1833 1834#  ifndef _LIBCPP_CXX03_LANG1835  _LIBCPP_HIDE_FROM_ABI void insert(initializer_list<value_type> __il) { insert(__il.begin(), __il.end()); }1836  _LIBCPP_HIDE_FROM_ABI iterator insert(value_type&& __x) { return __table_.__emplace_multi(std::move(__x)); }1837 1838  _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, value_type&& __x) {1839    return __table_.__emplace_hint_multi(__p.__i_, std::move(__x));1840  }1841 1842  template <class _Pp, __enable_if_t<is_constructible<value_type, _Pp>::value, int> = 0>1843  _LIBCPP_HIDE_FROM_ABI iterator insert(_Pp&& __x) {1844    return __table_.__emplace_multi(std::forward<_Pp>(__x));1845  }1846 1847  template <class _Pp, __enable_if_t<is_constructible<value_type, _Pp>::value, int> = 0>1848  _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, _Pp&& __x) {1849    return __table_.__emplace_hint_multi(__p.__i_, std::forward<_Pp>(__x));1850  }1851 1852  template <class... _Args>1853  _LIBCPP_HIDE_FROM_ABI iterator emplace(_Args&&... __args) {1854    return __table_.__emplace_multi(std::forward<_Args>(__args)...);1855  }1856 1857  template <class... _Args>1858  _LIBCPP_HIDE_FROM_ABI iterator emplace_hint(const_iterator __p, _Args&&... __args) {1859    return __table_.__emplace_hint_multi(__p.__i_, std::forward<_Args>(__args)...);1860  }1861#  endif // _LIBCPP_CXX03_LANG1862 1863  _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __p) { return __table_.erase(__p.__i_); }1864  _LIBCPP_HIDE_FROM_ABI iterator erase(iterator __p) { return __table_.erase(__p.__i_); }1865  _LIBCPP_HIDE_FROM_ABI size_type erase(const key_type& __k) { return __table_.__erase_multi(__k); }1866  _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __first, const_iterator __last) {1867    return __table_.erase(__first.__i_, __last.__i_);1868  }1869  _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT { __table_.clear(); }1870 1871#  if _LIBCPP_STD_VER >= 171872  _LIBCPP_HIDE_FROM_ABI iterator insert(node_type&& __nh) {1873    _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(),1874                                        "node_type with incompatible allocator passed to unordered_multimap::insert()");1875    return __table_.template __node_handle_insert_multi<node_type>(std::move(__nh));1876  }1877  _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __hint, node_type&& __nh) {1878    _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(),1879                                        "node_type with incompatible allocator passed to unordered_multimap::insert()");1880    return __table_.template __node_handle_insert_multi<node_type>(__hint.__i_, std::move(__nh));1881  }1882  _LIBCPP_HIDE_FROM_ABI node_type extract(key_type const& __key) {1883    return __table_.template __node_handle_extract<node_type>(__key);1884  }1885  _LIBCPP_HIDE_FROM_ABI node_type extract(const_iterator __it) {1886    return __table_.template __node_handle_extract<node_type>(__it.__i_);1887  }1888 1889  template <class _H2, class _P2>1890  _LIBCPP_HIDE_FROM_ABI void merge(unordered_multimap<key_type, mapped_type, _H2, _P2, allocator_type>& __source) {1891    _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(1892        __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");1893    return __table_.__node_handle_merge_multi(__source.__table_);1894  }1895  template <class _H2, class _P2>1896  _LIBCPP_HIDE_FROM_ABI void merge(unordered_multimap<key_type, mapped_type, _H2, _P2, allocator_type>&& __source) {1897    _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(1898        __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");1899    return __table_.__node_handle_merge_multi(__source.__table_);1900  }1901  template <class _H2, class _P2>1902  _LIBCPP_HIDE_FROM_ABI void merge(unordered_map<key_type, mapped_type, _H2, _P2, allocator_type>& __source) {1903    _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(1904        __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");1905    return __table_.__node_handle_merge_multi(__source.__table_);1906  }1907  template <class _H2, class _P2>1908  _LIBCPP_HIDE_FROM_ABI void merge(unordered_map<key_type, mapped_type, _H2, _P2, allocator_type>&& __source) {1909    _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(1910        __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");1911    return __table_.__node_handle_merge_multi(__source.__table_);1912  }1913#  endif1914 1915  _LIBCPP_HIDE_FROM_ABI void swap(unordered_multimap& __u) _NOEXCEPT_(__is_nothrow_swappable_v<__table>) {1916    __table_.swap(__u.__table_);1917  }1918 1919  _LIBCPP_HIDE_FROM_ABI hasher hash_function() const { return __table_.hash_function().hash_function(); }1920  _LIBCPP_HIDE_FROM_ABI key_equal key_eq() const { return __table_.key_eq().key_eq(); }1921 1922  _LIBCPP_HIDE_FROM_ABI iterator find(const key_type& __k) { return __table_.find(__k); }1923  _LIBCPP_HIDE_FROM_ABI const_iterator find(const key_type& __k) const { return __table_.find(__k); }1924#  if _LIBCPP_STD_VER >= 201925  template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr>1926  _LIBCPP_HIDE_FROM_ABI iterator find(const _K2& __k) {1927    return __table_.find(__k);1928  }1929  template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr>1930  _LIBCPP_HIDE_FROM_ABI const_iterator find(const _K2& __k) const {1931    return __table_.find(__k);1932  }1933#  endif // _LIBCPP_STD_VER >= 201934 1935  _LIBCPP_HIDE_FROM_ABI size_type count(const key_type& __k) const { return __table_.__count_multi(__k); }1936#  if _LIBCPP_STD_VER >= 201937  template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr>1938  _LIBCPP_HIDE_FROM_ABI size_type count(const _K2& __k) const {1939    return __table_.__count_multi(__k);1940  }1941#  endif // _LIBCPP_STD_VER >= 201942 1943#  if _LIBCPP_STD_VER >= 201944  _LIBCPP_HIDE_FROM_ABI bool contains(const key_type& __k) const { return find(__k) != end(); }1945 1946  template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr>1947  _LIBCPP_HIDE_FROM_ABI bool contains(const _K2& __k) const {1948    return find(__k) != end();1949  }1950#  endif // _LIBCPP_STD_VER >= 201951 1952  _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const key_type& __k) {1953    return __table_.__equal_range_multi(__k);1954  }1955  _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const key_type& __k) const {1956    return __table_.__equal_range_multi(__k);1957  }1958#  if _LIBCPP_STD_VER >= 201959  template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr>1960  _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const _K2& __k) {1961    return __table_.__equal_range_multi(__k);1962  }1963  template <class _K2, enable_if_t<__is_transparent_v<hasher, _K2> && __is_transparent_v<key_equal, _K2>>* = nullptr>1964  _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const _K2& __k) const {1965    return __table_.__equal_range_multi(__k);1966  }1967#  endif // _LIBCPP_STD_VER >= 201968 1969  _LIBCPP_HIDE_FROM_ABI size_type bucket_count() const _NOEXCEPT { return __table_.bucket_count(); }1970  _LIBCPP_HIDE_FROM_ABI size_type max_bucket_count() const _NOEXCEPT { return __table_.max_bucket_count(); }1971 1972  _LIBCPP_HIDE_FROM_ABI size_type bucket_size(size_type __n) const { return __table_.bucket_size(__n); }1973  _LIBCPP_HIDE_FROM_ABI size_type bucket(const key_type& __k) const { return __table_.bucket(__k); }1974 1975  _LIBCPP_HIDE_FROM_ABI local_iterator begin(size_type __n) { return __table_.begin(__n); }1976  _LIBCPP_HIDE_FROM_ABI local_iterator end(size_type __n) { return __table_.end(__n); }1977  _LIBCPP_HIDE_FROM_ABI const_local_iterator begin(size_type __n) const { return __table_.cbegin(__n); }1978  _LIBCPP_HIDE_FROM_ABI const_local_iterator end(size_type __n) const { return __table_.cend(__n); }1979  _LIBCPP_HIDE_FROM_ABI const_local_iterator cbegin(size_type __n) const { return __table_.cbegin(__n); }1980  _LIBCPP_HIDE_FROM_ABI const_local_iterator cend(size_type __n) const { return __table_.cend(__n); }1981 1982  _LIBCPP_HIDE_FROM_ABI float load_factor() const _NOEXCEPT { return __table_.load_factor(); }1983  _LIBCPP_HIDE_FROM_ABI float max_load_factor() const _NOEXCEPT { return __table_.max_load_factor(); }1984  _LIBCPP_HIDE_FROM_ABI void max_load_factor(float __mlf) { __table_.max_load_factor(__mlf); }1985  _LIBCPP_HIDE_FROM_ABI void rehash(size_type __n) { __table_.__rehash_multi(__n); }1986  _LIBCPP_HIDE_FROM_ABI void reserve(size_type __n) { __table_.__reserve_multi(__n); }1987};1988 1989#  if _LIBCPP_STD_VER >= 171990template <class _InputIterator,1991          class _Hash      = hash<__iter_key_type<_InputIterator>>,1992          class _Pred      = equal_to<__iter_key_type<_InputIterator>>,1993          class _Allocator = allocator<__iter_to_alloc_type<_InputIterator>>,1994          class            = enable_if_t<__has_input_iterator_category<_InputIterator>::value>,1995          class            = enable_if_t<!__is_allocator_v<_Hash>>,1996          class            = enable_if_t<!is_integral<_Hash>::value>,1997          class            = enable_if_t<!__is_allocator_v<_Pred>>,1998          class            = enable_if_t<__is_allocator_v<_Allocator>>>1999unordered_multimap(_InputIterator,2000                   _InputIterator,2001                   typename allocator_traits<_Allocator>::size_type = 0,2002                   _Hash                                            = _Hash(),2003                   _Pred                                            = _Pred(),2004                   _Allocator                                       = _Allocator())2005    -> unordered_multimap<__iter_key_type<_InputIterator>,2006                          __iter_mapped_type<_InputIterator>,2007                          _Hash,2008                          _Pred,2009                          _Allocator>;2010 2011#    if _LIBCPP_STD_VER >= 232012template <ranges::input_range _Range,2013          class _Hash      = hash<__range_key_type<_Range>>,2014          class _Pred      = equal_to<__range_key_type<_Range>>,2015          class _Allocator = allocator<__range_to_alloc_type<_Range>>,2016          class            = enable_if_t<!__is_allocator_v<_Hash>>,2017          class            = enable_if_t<!is_integral<_Hash>::value>,2018          class            = enable_if_t<!__is_allocator_v<_Pred>>,2019          class            = enable_if_t<__is_allocator_v<_Allocator>>>2020unordered_multimap(from_range_t,2021                   _Range&&,2022                   typename allocator_traits<_Allocator>::size_type = 0,2023                   _Hash                                            = _Hash(),2024                   _Pred                                            = _Pred(),2025                   _Allocator                                       = _Allocator())2026    -> unordered_multimap<__range_key_type<_Range>, __range_mapped_type<_Range>, _Hash, _Pred, _Allocator>;2027#    endif2028 2029template <class _Key,2030          class _Tp,2031          class _Hash      = hash<remove_const_t<_Key>>,2032          class _Pred      = equal_to<remove_const_t<_Key>>,2033          class _Allocator = allocator<pair<const _Key, _Tp>>,2034          class            = enable_if_t<!__is_allocator_v<_Hash>>,2035          class            = enable_if_t<!is_integral<_Hash>::value>,2036          class            = enable_if_t<!__is_allocator_v<_Pred>>,2037          class            = enable_if_t<__is_allocator_v<_Allocator>>>2038unordered_multimap(initializer_list<pair<_Key, _Tp>>,2039                   typename allocator_traits<_Allocator>::size_type = 0,2040                   _Hash                                            = _Hash(),2041                   _Pred                                            = _Pred(),2042                   _Allocator                                       = _Allocator())2043    -> unordered_multimap<remove_const_t<_Key>, _Tp, _Hash, _Pred, _Allocator>;2044 2045template <class _InputIterator,2046          class _Allocator,2047          class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>,2048          class = enable_if_t<__is_allocator_v<_Allocator>>>2049unordered_multimap(_InputIterator, _InputIterator, typename allocator_traits<_Allocator>::size_type, _Allocator)2050    -> unordered_multimap<__iter_key_type<_InputIterator>,2051                          __iter_mapped_type<_InputIterator>,2052                          hash<__iter_key_type<_InputIterator>>,2053                          equal_to<__iter_key_type<_InputIterator>>,2054                          _Allocator>;2055 2056template <class _InputIterator,2057          class _Allocator,2058          class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>,2059          class = enable_if_t<__is_allocator_v<_Allocator>>>2060unordered_multimap(_InputIterator, _InputIterator, _Allocator)2061    -> unordered_multimap<__iter_key_type<_InputIterator>,2062                          __iter_mapped_type<_InputIterator>,2063                          hash<__iter_key_type<_InputIterator>>,2064                          equal_to<__iter_key_type<_InputIterator>>,2065                          _Allocator>;2066 2067template <class _InputIterator,2068          class _Hash,2069          class _Allocator,2070          class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>,2071          class = enable_if_t<!__is_allocator_v<_Hash>>,2072          class = enable_if_t<!is_integral<_Hash>::value>,2073          class = enable_if_t<__is_allocator_v<_Allocator>>>2074unordered_multimap(_InputIterator, _InputIterator, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator)2075    -> unordered_multimap<__iter_key_type<_InputIterator>,2076                          __iter_mapped_type<_InputIterator>,2077                          _Hash,2078                          equal_to<__iter_key_type<_InputIterator>>,2079                          _Allocator>;2080 2081#    if _LIBCPP_STD_VER >= 232082 2083template <ranges::input_range _Range, class _Allocator, class = enable_if_t<__is_allocator_v<_Allocator>>>2084unordered_multimap(from_range_t, _Range&&, typename allocator_traits<_Allocator>::size_type, _Allocator)2085    -> unordered_multimap<__range_key_type<_Range>,2086                          __range_mapped_type<_Range>,2087                          hash<__range_key_type<_Range>>,2088                          equal_to<__range_key_type<_Range>>,2089                          _Allocator>;2090 2091template <ranges::input_range _Range, class _Allocator, class = enable_if_t<__is_allocator_v<_Allocator>>>2092unordered_multimap(from_range_t, _Range&&, _Allocator)2093    -> unordered_multimap<__range_key_type<_Range>,2094                          __range_mapped_type<_Range>,2095                          hash<__range_key_type<_Range>>,2096                          equal_to<__range_key_type<_Range>>,2097                          _Allocator>;2098 2099template <ranges::input_range _Range,2100          class _Hash,2101          class _Allocator,2102          class = enable_if_t<!__is_allocator_v<_Hash>>,2103          class = enable_if_t<!is_integral<_Hash>::value>,2104          class = enable_if_t<__is_allocator_v<_Allocator>>>2105unordered_multimap(from_range_t, _Range&&, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator)2106    -> unordered_multimap<__range_key_type<_Range>,2107                          __range_mapped_type<_Range>,2108                          _Hash,2109                          equal_to<__range_key_type<_Range>>,2110                          _Allocator>;2111 2112#    endif2113 2114template <class _Key, class _Tp, class _Allocator, class = enable_if_t<__is_allocator_v<_Allocator>>>2115unordered_multimap(initializer_list<pair<_Key, _Tp>>, typename allocator_traits<_Allocator>::size_type, _Allocator)2116    -> unordered_multimap<remove_const_t<_Key>,2117                          _Tp,2118                          hash<remove_const_t<_Key>>,2119                          equal_to<remove_const_t<_Key>>,2120                          _Allocator>;2121 2122template <class _Key, class _Tp, class _Allocator, class = enable_if_t<__is_allocator_v<_Allocator>>>2123unordered_multimap(initializer_list<pair<_Key, _Tp>>, _Allocator)2124    -> unordered_multimap<remove_const_t<_Key>,2125                          _Tp,2126                          hash<remove_const_t<_Key>>,2127                          equal_to<remove_const_t<_Key>>,2128                          _Allocator>;2129 2130template <class _Key,2131          class _Tp,2132          class _Hash,2133          class _Allocator,2134          class = enable_if_t<!__is_allocator_v<_Hash>>,2135          class = enable_if_t<!is_integral<_Hash>::value>,2136          class = enable_if_t<__is_allocator_v<_Allocator>>>2137unordered_multimap(2138    initializer_list<pair<_Key, _Tp>>, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator)2139    -> unordered_multimap<remove_const_t<_Key>, _Tp, _Hash, equal_to<remove_const_t<_Key>>, _Allocator>;2140#  endif2141 2142template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>2143unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(2144    size_type __n, const hasher& __hf, const key_equal& __eql)2145    : __table_(__hf, __eql) {2146  __table_.__rehash_multi(__n);2147}2148 2149template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>2150unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(2151    size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a)2152    : __table_(__hf, __eql, typename __table::allocator_type(__a)) {2153  __table_.__rehash_multi(__n);2154}2155 2156template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>2157template <class _InputIterator>2158unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(_InputIterator __first, _InputIterator __last) {2159  insert(__first, __last);2160}2161 2162template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>2163template <class _InputIterator>2164unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(2165    _InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, const key_equal& __eql)2166    : __table_(__hf, __eql) {2167  __table_.__rehash_multi(__n);2168  insert(__first, __last);2169}2170 2171template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>2172template <class _InputIterator>2173unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(2174    _InputIterator __first,2175    _InputIterator __last,2176    size_type __n,2177    const hasher& __hf,2178    const key_equal& __eql,2179    const allocator_type& __a)2180    : __table_(__hf, __eql, typename __table::allocator_type(__a)) {2181  __table_.__rehash_multi(__n);2182  insert(__first, __last);2183}2184 2185template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>2186inline unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(const allocator_type& __a)2187    : __table_(typename __table::allocator_type(__a)) {}2188 2189template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>2190unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(2191    const unordered_multimap& __u, const allocator_type& __a)2192    : __table_(__u.__table_, typename __table::allocator_type(__a)) {2193  __table_.__rehash_multi(__u.bucket_count());2194  insert(__u.begin(), __u.end());2195}2196 2197#  ifndef _LIBCPP_CXX03_LANG2198 2199template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>2200unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(2201    unordered_multimap&& __u, const allocator_type& __a)2202    : __table_(std::move(__u.__table_), typename __table::allocator_type(__a)) {2203  if (__a != __u.get_allocator()) {2204    iterator __i = __u.begin();2205    while (__u.size() != 0)2206      __table_.__insert_multi_from_orphaned_node(std::move(__u.__table_.remove((__i++).__i_)->__get_value()));2207  }2208}2209 2210template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>2211unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(initializer_list<value_type> __il) {2212  insert(__il.begin(), __il.end());2213}2214 2215template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>2216unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(2217    initializer_list<value_type> __il, size_type __n, const hasher& __hf, const key_equal& __eql)2218    : __table_(__hf, __eql) {2219  __table_.__rehash_multi(__n);2220  insert(__il.begin(), __il.end());2221}2222 2223template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>2224unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap(2225    initializer_list<value_type> __il,2226    size_type __n,2227    const hasher& __hf,2228    const key_equal& __eql,2229    const allocator_type& __a)2230    : __table_(__hf, __eql, typename __table::allocator_type(__a)) {2231  __table_.__rehash_multi(__n);2232  insert(__il.begin(), __il.end());2233}2234 2235template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>2236inline unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>&2237unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::operator=(initializer_list<value_type> __il) {2238  __table_.__assign_multi(__il.begin(), __il.end());2239  return *this;2240}2241 2242#  endif // _LIBCPP_CXX03_LANG2243 2244template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>2245template <class _InputIterator>2246inline void unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, _InputIterator __last) {2247  for (; __first != __last; ++__first)2248    __table_.__emplace_multi(*__first);2249}2250 2251template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>2252inline _LIBCPP_HIDE_FROM_ABI void2253swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)2254    _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) {2255  __x.swap(__y);2256}2257 2258#  if _LIBCPP_STD_VER >= 202259template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc, class _Predicate>2260inline _LIBCPP_HIDE_FROM_ABI typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::size_type2261erase_if(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __c, _Predicate __pred) {2262  return std::__libcpp_erase_if_container(__c, __pred);2263}2264#  endif2265 2266template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>2267_LIBCPP_HIDE_FROM_ABI bool operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,2268                                      const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) {2269  if (__x.size() != __y.size())2270    return false;2271  typedef typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator const_iterator;2272  typedef pair<const_iterator, const_iterator> _EqRng;2273  for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;) {2274    _EqRng __xeq = __x.equal_range(__i->first);2275    _EqRng __yeq = __y.equal_range(__i->first);2276    if (std::distance(__xeq.first, __xeq.second) != std::distance(__yeq.first, __yeq.second) ||2277        !std::is_permutation(__xeq.first, __xeq.second, __yeq.first))2278      return false;2279    __i = __xeq.second;2280  }2281  return true;2282}2283 2284#  if _LIBCPP_STD_VER <= 172285 2286template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>2287inline _LIBCPP_HIDE_FROM_ABI bool operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,2288                                             const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) {2289  return !(__x == __y);2290}2291 2292#  endif2293 2294template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>2295struct __container_traits<unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc> > {2296  // http://eel.is/c++draft/unord.req.except#22297  //  For unordered associative containers, if an exception is thrown by any operation2298  //  other than the container's hash function from within an insert or emplace function2299  //  inserting a single element, the insertion has no effect.2300  static _LIBCPP_CONSTEXPR const bool __emplacement_has_strong_exception_safety_guarantee =2301      __is_nothrow_invocable_v<_Hash, const _Key&>;2302 2303  static _LIBCPP_CONSTEXPR const bool __reservable = true;2304};2305 2306_LIBCPP_END_NAMESPACE_STD2307 2308#  if _LIBCPP_STD_VER >= 172309_LIBCPP_BEGIN_NAMESPACE_STD2310namespace pmr {2311template <class _KeyT, class _ValueT, class _HashT = std::hash<_KeyT>, class _PredT = std::equal_to<_KeyT>>2312using unordered_map _LIBCPP_AVAILABILITY_PMR =2313    std::unordered_map<_KeyT, _ValueT, _HashT, _PredT, polymorphic_allocator<std::pair<const _KeyT, _ValueT>>>;2314 2315template <class _KeyT, class _ValueT, class _HashT = std::hash<_KeyT>, class _PredT = std::equal_to<_KeyT>>2316using unordered_multimap _LIBCPP_AVAILABILITY_PMR =2317    std::unordered_multimap<_KeyT, _ValueT, _HashT, _PredT, polymorphic_allocator<std::pair<const _KeyT, _ValueT>>>;2318} // namespace pmr2319_LIBCPP_END_NAMESPACE_STD2320#  endif2321 2322_LIBCPP_POP_MACROS2323 2324#  if !defined(_LIBCPP_REMOVE_TRANSITIVE_INCLUDES) && _LIBCPP_STD_VER <= 202325#    include <algorithm>2326#    include <bit>2327#    include <cmath>2328#    include <concepts>2329#    include <cstdlib>2330#    include <iterator>2331#    include <type_traits>2332#  endif2333#endif // __cplusplus < 201103L && defined(_LIBCPP_USE_FROZEN_CXX03_HEADERS)2334 2335#endif // _LIBCPP_UNORDERED_MAP2336