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_MAP11#define _LIBCPP_MAP12 13/*14 15    map synopsis16 17namespace std18{19 20template <class Key, class T, class Compare = less<Key>,21          class Allocator = allocator<pair<const Key, T>>>22class map23{24public:25    // types:26    typedef Key                                      key_type;27    typedef T                                        mapped_type;28    typedef pair<const key_type, mapped_type>        value_type;29    typedef Compare                                  key_compare;30    typedef Allocator                                allocator_type;31    typedef typename allocator_type::reference       reference;32    typedef typename allocator_type::const_reference const_reference;33    typedef typename allocator_type::pointer         pointer;34    typedef typename allocator_type::const_pointer   const_pointer;35    typedef typename allocator_type::size_type       size_type;36    typedef typename allocator_type::difference_type difference_type;37 38    typedef implementation-defined                   iterator;39    typedef implementation-defined                   const_iterator;40    typedef std::reverse_iterator<iterator>          reverse_iterator;41    typedef std::reverse_iterator<const_iterator>    const_reverse_iterator;42    typedef unspecified                              node_type;              // C++1743    typedef INSERT_RETURN_TYPE<iterator, node_type>  insert_return_type;     // C++1744 45    class value_compare46    {47        friend class map;48    protected:49        key_compare comp;50 51        value_compare(key_compare c);52    public:53        typedef bool result_type;  // deprecated in C++17, removed in C++2054        typedef value_type first_argument_type;  // deprecated in C++17, removed in C++2055        typedef value_type second_argument_type;  // deprecated in C++17, removed in C++2056        bool operator()(const value_type& x, const value_type& y) const;57    };58 59    // construct/copy/destroy:60    map()61        noexcept(62            is_nothrow_default_constructible<allocator_type>::value &&63            is_nothrow_default_constructible<key_compare>::value &&64            is_nothrow_copy_constructible<key_compare>::value);65    explicit map(const key_compare& comp);66    map(const key_compare& comp, const allocator_type& a);67    template <class InputIterator>68        map(InputIterator first, InputIterator last,69            const key_compare& comp = key_compare());70    template <class InputIterator>71        map(InputIterator first, InputIterator last,72            const key_compare& comp, const allocator_type& a);73    template<container-compatible-range<value_type> R>74      map(from_range_t, R&& rg, const Compare& comp = Compare(), const Allocator& = Allocator()); // C++2375    map(const map& m);76    map(map&& m)77        noexcept(78            is_nothrow_move_constructible<allocator_type>::value &&79            is_nothrow_move_constructible<key_compare>::value);80    explicit map(const allocator_type& a);81    map(const map& m, const allocator_type& a);82    map(map&& m, const allocator_type& a);83    map(initializer_list<value_type> il, const key_compare& comp = key_compare());84    map(initializer_list<value_type> il, const key_compare& comp, const allocator_type& a);85    template <class InputIterator>86        map(InputIterator first, InputIterator last, const allocator_type& a)87            : map(first, last, Compare(), a) {}  // C++1488    template<container-compatible-range<value_type> R>89      map(from_range_t, R&& rg, const Allocator& a))90        : map(from_range, std::forward<R>(rg), Compare(), a) { } // C++2391    map(initializer_list<value_type> il, const allocator_type& a)92        : map(il, Compare(), a) {}  // C++1493   ~map();94 95    map& operator=(const map& m);96    map& operator=(map&& m)97        noexcept(98            allocator_type::propagate_on_container_move_assignment::value &&99            is_nothrow_move_assignable<allocator_type>::value &&100            is_nothrow_move_assignable<key_compare>::value);101    map& operator=(initializer_list<value_type> il);102 103    // iterators:104          iterator begin() noexcept;105    const_iterator begin() const noexcept;106          iterator end() noexcept;107    const_iterator end()   const noexcept;108 109          reverse_iterator rbegin() noexcept;110    const_reverse_iterator rbegin() const noexcept;111          reverse_iterator rend() noexcept;112    const_reverse_iterator rend()   const noexcept;113 114    const_iterator         cbegin()  const noexcept;115    const_iterator         cend()    const noexcept;116    const_reverse_iterator crbegin() const noexcept;117    const_reverse_iterator crend()   const noexcept;118 119    // capacity:120    bool      empty()    const noexcept;121    size_type size()     const noexcept;122    size_type max_size() const noexcept;123 124    // element access:125    mapped_type& operator[](const key_type& k);126    mapped_type& operator[](key_type&& k);127 128          mapped_type& at(const key_type& k);129    const mapped_type& at(const key_type& k) const;130 131    // modifiers:132    template <class... Args>133        pair<iterator, bool> emplace(Args&&... args);134    template <class... Args>135        iterator emplace_hint(const_iterator position, Args&&... args);136    pair<iterator, bool> insert(const value_type& v);137    pair<iterator, bool> insert(      value_type&& v);                                // C++17138    template <class P>139        pair<iterator, bool> insert(P&& p);140    iterator insert(const_iterator position, const value_type& v);141    iterator insert(const_iterator position,       value_type&& v);                   // C++17142    template <class P>143        iterator insert(const_iterator position, P&& p);144    template <class InputIterator>145        void insert(InputIterator first, InputIterator last);146    template<container-compatible-range<value_type> R>147      void insert_range(R&& rg);                                                      // C++23148    void insert(initializer_list<value_type> il);149 150    node_type extract(const_iterator position);                                       // C++17151    node_type extract(const key_type& x);                                             // C++17152    insert_return_type insert(node_type&& nh);                                        // C++17153    iterator insert(const_iterator hint, node_type&& nh);                             // C++17154 155    template <class... Args>156        pair<iterator, bool> try_emplace(const key_type& k, Args&&... args);          // C++17157    template <class... Args>158        pair<iterator, bool> try_emplace(key_type&& k, Args&&... args);               // C++17159    template <class... Args>160        iterator try_emplace(const_iterator hint, const key_type& k, Args&&... args); // C++17161    template <class... Args>162        iterator try_emplace(const_iterator hint, key_type&& k, Args&&... args);      // C++17163    template <class M>164        pair<iterator, bool> insert_or_assign(const key_type& k, M&& obj);            // C++17165    template <class M>166        pair<iterator, bool> insert_or_assign(key_type&& k, M&& obj);                 // C++17167    template <class M>168        iterator insert_or_assign(const_iterator hint, const key_type& k, M&& obj);   // C++17169    template <class M>170        iterator insert_or_assign(const_iterator hint, key_type&& k, M&& obj);        // C++17171 172    iterator  erase(const_iterator position);173    iterator  erase(iterator position); // C++14174    size_type erase(const key_type& k);175    iterator  erase(const_iterator first, const_iterator last);176    void clear() noexcept;177 178    template<class C2>179      void merge(map<Key, T, C2, Allocator>& source);         // C++17180    template<class C2>181      void merge(map<Key, T, C2, Allocator>&& source);        // C++17182    template<class C2>183      void merge(multimap<Key, T, C2, Allocator>& source);    // C++17184    template<class C2>185      void merge(multimap<Key, T, C2, Allocator>&& source);   // C++17186 187    void swap(map& m)188        noexcept(allocator_traits<allocator_type>::is_always_equal::value &&189            is_nothrow_swappable<key_compare>::value); // C++17190 191    // observers:192    allocator_type get_allocator() const noexcept;193    key_compare    key_comp()      const;194    value_compare  value_comp()    const;195 196    // map operations:197          iterator find(const key_type& k);198    const_iterator find(const key_type& k) const;199    template<typename K>200        iterator find(const K& x);              // C++14201    template<typename K>202        const_iterator find(const K& x) const;  // C++14203 204    template<typename K>205      size_type count(const K& x) const;        // C++14206    size_type      count(const key_type& k) const;207 208    bool           contains(const key_type& x) const;  // C++20209    template<class K> bool contains(const K& x) const; // C++20210 211          iterator lower_bound(const key_type& k);212    const_iterator lower_bound(const key_type& k) const;213    template<typename K>214        iterator lower_bound(const K& x);              // C++14215    template<typename K>216        const_iterator lower_bound(const K& x) const;  // C++14217 218          iterator upper_bound(const key_type& k);219    const_iterator upper_bound(const key_type& k) const;220    template<typename K>221        iterator upper_bound(const K& x);              // C++14222    template<typename K>223        const_iterator upper_bound(const K& x) const;  // C++14224 225    pair<iterator,iterator>             equal_range(const key_type& k);226    pair<const_iterator,const_iterator> equal_range(const key_type& k) const;227    template<typename K>228        pair<iterator,iterator>             equal_range(const K& x);        // C++14229    template<typename K>230        pair<const_iterator,const_iterator> equal_range(const K& x) const;  // C++14231};232 233template <class InputIterator,234      class Compare = less<iter_key_t<InputIterator>>,235      class Allocator = allocator<iter_to_alloc_t<InputIterator>>>236map(InputIterator, InputIterator, Compare = Compare(), Allocator = Allocator())237  -> map<iter_key_t<InputIterator>, iter_val_t<InputIterator>, Compare, Allocator>; // C++17238 239template<ranges::input_range R, class Compare = less<range-key-type<R>,240         class Allocator = allocator<range-to-alloc-type<R>>>241  map(from_range_t, R&&, Compare = Compare(), Allocator = Allocator())242    -> map<range-key-type<R>, range-mapped-type<R>, Compare, Allocator>; // C++23243 244template<class Key, class T, class Compare = less<Key>,245    class Allocator = allocator<pair<const Key, T>>>246map(initializer_list<pair<const Key, T>>, Compare = Compare(), Allocator = Allocator())247  -> map<Key, T, Compare, Allocator>; // C++17248 249template <class InputIterator, class Allocator>250map(InputIterator, InputIterator, Allocator)251  -> map<iter_key_t<InputIterator>, iter_val_t<InputIterator>, less<iter_key_t<InputIterator>>,252    Allocator>; // C++17253 254template<ranges::input_range R, class Allocator>255  map(from_range_t, R&&, Allocator)256    -> map<range-key-type<R>, range-mapped-type<R>, less<range-key-type<R>>, Allocator>; // C++23257 258template<class Key, class T, class Allocator>259map(initializer_list<pair<const Key, T>>, Allocator) -> map<Key, T, less<Key>, Allocator>; // C++17260 261template <class Key, class T, class Compare, class Allocator>262bool263operator==(const map<Key, T, Compare, Allocator>& x,264           const map<Key, T, Compare, Allocator>& y);265 266template <class Key, class T, class Compare, class Allocator>267bool268operator< (const map<Key, T, Compare, Allocator>& x,269           const map<Key, T, Compare, Allocator>& y);      // removed in C++20270 271template <class Key, class T, class Compare, class Allocator>272bool273operator!=(const map<Key, T, Compare, Allocator>& x,274           const map<Key, T, Compare, Allocator>& y);      // removed in C++20275 276template <class Key, class T, class Compare, class Allocator>277bool278operator> (const map<Key, T, Compare, Allocator>& x,279           const map<Key, T, Compare, Allocator>& y);      // removed in C++20280 281template <class Key, class T, class Compare, class Allocator>282bool283operator>=(const map<Key, T, Compare, Allocator>& x,284           const map<Key, T, Compare, Allocator>& y);      // removed in C++20285 286template <class Key, class T, class Compare, class Allocator>287bool288operator<=(const map<Key, T, Compare, Allocator>& x,289           const map<Key, T, Compare, Allocator>& y);      // removed in C++20290 291template<class Key, class T, class Compare, class Allocator>292  synth-three-way-result<pair<const Key, T>>293    operator<=>(const map<Key, T, Compare, Allocator>& x,294                const map<Key, T, Compare, Allocator>& y); // since C++20295 296// specialized algorithms:297template <class Key, class T, class Compare, class Allocator>298void299swap(map<Key, T, Compare, Allocator>& x, map<Key, T, Compare, Allocator>& y)300    noexcept(noexcept(x.swap(y)));301 302template <class Key, class T, class Compare, class Allocator, class Predicate>303typename map<Key, T, Compare, Allocator>::size_type304erase_if(map<Key, T, Compare, Allocator>& c, Predicate pred);  // C++20305 306 307template <class Key, class T, class Compare = less<Key>,308          class Allocator = allocator<pair<const Key, T>>>309class multimap310{311public:312    // types:313    typedef Key                                      key_type;314    typedef T                                        mapped_type;315    typedef pair<const key_type,mapped_type>         value_type;316    typedef Compare                                  key_compare;317    typedef Allocator                                allocator_type;318    typedef typename allocator_type::reference       reference;319    typedef typename allocator_type::const_reference const_reference;320    typedef typename allocator_type::size_type       size_type;321    typedef typename allocator_type::difference_type difference_type;322    typedef typename allocator_type::pointer         pointer;323    typedef typename allocator_type::const_pointer   const_pointer;324 325    typedef implementation-defined                   iterator;326    typedef implementation-defined                   const_iterator;327    typedef std::reverse_iterator<iterator>          reverse_iterator;328    typedef std::reverse_iterator<const_iterator>    const_reverse_iterator;329    typedef unspecified                              node_type;              // C++17330 331    class value_compare332    {333        friend class multimap;334    protected:335        key_compare comp;336        value_compare(key_compare c);337    public:338        typedef bool result_type;  // deprecated in C++17, removed in C++20339        typedef value_type first_argument_type;  // deprecated in C++17, removed in C++20340        typedef value_type second_argument_type;  // deprecated in C++17, removed in C++20341        bool operator()(const value_type& x, const value_type& y) const;342    };343 344    // construct/copy/destroy:345    multimap()346        noexcept(347            is_nothrow_default_constructible<allocator_type>::value &&348            is_nothrow_default_constructible<key_compare>::value &&349            is_nothrow_copy_constructible<key_compare>::value);350    explicit multimap(const key_compare& comp);351    multimap(const key_compare& comp, const allocator_type& a);352    template <class InputIterator>353        multimap(InputIterator first, InputIterator last, const key_compare& comp);354    template <class InputIterator>355        multimap(InputIterator first, InputIterator last, const key_compare& comp,356                 const allocator_type& a);357    template<container-compatible-range<value_type> R>358      multimap(from_range_t, R&& rg,359               const Compare& comp = Compare(), const Allocator& = Allocator()); // C++23360    multimap(const multimap& m);361    multimap(multimap&& m)362        noexcept(363            is_nothrow_move_constructible<allocator_type>::value &&364            is_nothrow_move_constructible<key_compare>::value);365    explicit multimap(const allocator_type& a);366    multimap(const multimap& m, const allocator_type& a);367    multimap(multimap&& m, const allocator_type& a);368    multimap(initializer_list<value_type> il, const key_compare& comp = key_compare());369    multimap(initializer_list<value_type> il, const key_compare& comp,370             const allocator_type& a);371    template <class InputIterator>372        multimap(InputIterator first, InputIterator last, const allocator_type& a)373            : multimap(first, last, Compare(), a) {} // C++14374    template<container-compatible-range<value_type> R>375      multimap(from_range_t, R&& rg, const Allocator& a))376        : multimap(from_range, std::forward<R>(rg), Compare(), a) { } // C++23377    multimap(initializer_list<value_type> il, const allocator_type& a)378        : multimap(il, Compare(), a) {} // C++14379    ~multimap();380 381    multimap& operator=(const multimap& m);382    multimap& operator=(multimap&& m)383        noexcept(384            allocator_type::propagate_on_container_move_assignment::value &&385            is_nothrow_move_assignable<allocator_type>::value &&386            is_nothrow_move_assignable<key_compare>::value);387    multimap& operator=(initializer_list<value_type> il);388 389    // iterators:390          iterator begin() noexcept;391    const_iterator begin() const noexcept;392          iterator end() noexcept;393    const_iterator end()   const noexcept;394 395          reverse_iterator rbegin() noexcept;396    const_reverse_iterator rbegin() const noexcept;397          reverse_iterator rend() noexcept;398    const_reverse_iterator rend()   const noexcept;399 400    const_iterator         cbegin()  const noexcept;401    const_iterator         cend()    const noexcept;402    const_reverse_iterator crbegin() const noexcept;403    const_reverse_iterator crend()   const noexcept;404 405    // capacity:406    bool      empty()    const noexcept;407    size_type size()     const noexcept;408    size_type max_size() const noexcept;409 410    // modifiers:411    template <class... Args>412        iterator emplace(Args&&... args);413    template <class... Args>414        iterator emplace_hint(const_iterator position, Args&&... args);415    iterator insert(const value_type& v);416    iterator insert(      value_type&& v);                                            // C++17417    template <class P>418        iterator insert(P&& p);419    iterator insert(const_iterator position, const value_type& v);420    iterator insert(const_iterator position,       value_type&& v);                   // C++17421    template <class P>422        iterator insert(const_iterator position, P&& p);423    template <class InputIterator>424        void insert(InputIterator first, InputIterator last);425    template<container-compatible-range<value_type> R>426      void insert_range(R&& rg);                                                      // C++23427    void insert(initializer_list<value_type> il);428 429    node_type extract(const_iterator position);                                       // C++17430    node_type extract(const key_type& x);                                             // C++17431    iterator insert(node_type&& nh);                                                  // C++17432    iterator insert(const_iterator hint, node_type&& nh);                             // C++17433 434    iterator  erase(const_iterator position);435    iterator  erase(iterator position); // C++14436    size_type erase(const key_type& k);437    iterator  erase(const_iterator first, const_iterator last);438    void clear() noexcept;439 440    template<class C2>441      void merge(multimap<Key, T, C2, Allocator>& source);    // C++17442    template<class C2>443      void merge(multimap<Key, T, C2, Allocator>&& source);   // C++17444    template<class C2>445      void merge(map<Key, T, C2, Allocator>& source);         // C++17446    template<class C2>447      void merge(map<Key, T, C2, Allocator>&& source);        // C++17448 449    void swap(multimap& m)450        noexcept(allocator_traits<allocator_type>::is_always_equal::value &&451            is_nothrow_swappable<key_compare>::value); // C++17452 453    // observers:454    allocator_type get_allocator() const noexcept;455    key_compare    key_comp()      const;456    value_compare  value_comp()    const;457 458    // map operations:459          iterator find(const key_type& k);460    const_iterator find(const key_type& k) const;461    template<typename K>462        iterator find(const K& x);              // C++14463    template<typename K>464        const_iterator find(const K& x) const;  // C++14465 466    template<typename K>467      size_type count(const K& x) const;        // C++14468    size_type      count(const key_type& k) const;469 470    bool           contains(const key_type& x) const;  // C++20471    template<class K> bool contains(const K& x) const; // C++20472 473          iterator lower_bound(const key_type& k);474    const_iterator lower_bound(const key_type& k) const;475    template<typename K>476        iterator lower_bound(const K& x);              // C++14477    template<typename K>478        const_iterator lower_bound(const K& x) const;  // C++14479 480          iterator upper_bound(const key_type& k);481    const_iterator upper_bound(const key_type& k) const;482    template<typename K>483        iterator upper_bound(const K& x);              // C++14484    template<typename K>485        const_iterator upper_bound(const K& x) const;  // C++14486 487    pair<iterator,iterator>             equal_range(const key_type& k);488    pair<const_iterator,const_iterator> equal_range(const key_type& k) const;489    template<typename K>490        pair<iterator,iterator>             equal_range(const K& x);        // C++14491    template<typename K>492        pair<const_iterator,const_iterator> equal_range(const K& x) const;  // C++14493};494 495template <class InputIterator,496      class Compare = less<iter_key_t<InputIterator>>,497      class Allocator = allocator<iter_to_alloc_t<InputIterator>>>498multimap(InputIterator, InputIterator, Compare = Compare(), Allocator = Allocator())499  -> multimap<iter_key_t<InputIterator>, iter_val_t<InputIterator>, Compare, Allocator>; // C++17500 501template<ranges::input_range R, class Compare = less<range-key-type<R>>,502          class Allocator = allocator<range-to-alloc-type<R>>>503  multimap(from_range_t, R&&, Compare = Compare(), Allocator = Allocator())504    -> multimap<range-key-type<R>, range-mapped-type<R>, Compare, Allocator>; // C++23505 506template<class Key, class T, class Compare = less<Key>,507    class Allocator = allocator<pair<const Key, T>>>508multimap(initializer_list<pair<const Key, T>>, Compare = Compare(), Allocator = Allocator())509  -> multimap<Key, T, Compare, Allocator>; // C++17510 511template <class InputIterator, class Allocator>512multimap(InputIterator, InputIterator, Allocator)513  -> multimap<iter_key_t<InputIterator>, iter_val_t<InputIterator>,514    less<iter_key_t<InputIterator>>, Allocator>; // C++17515 516template<ranges::input_range R, class Allocator>517  multimap(from_range_t, R&&, Allocator)518    -> multimap<range-key-type<R>, range-mapped-type<R>, less<range-key-type<R>>, Allocator>; // C++23519 520template<class Key, class T, class Allocator>521multimap(initializer_list<pair<const Key, T>>, Allocator)522  -> multimap<Key, T, less<Key>, Allocator>; // C++17523 524template <class Key, class T, class Compare, class Allocator>525bool526operator==(const multimap<Key, T, Compare, Allocator>& x,527           const multimap<Key, T, Compare, Allocator>& y);528 529template <class Key, class T, class Compare, class Allocator>530bool531operator< (const multimap<Key, T, Compare, Allocator>& x,532           const multimap<Key, T, Compare, Allocator>& y);      // removed in C++20533 534template <class Key, class T, class Compare, class Allocator>535bool536operator!=(const multimap<Key, T, Compare, Allocator>& x,537           const multimap<Key, T, Compare, Allocator>& y);      // removed in C++20538 539template <class Key, class T, class Compare, class Allocator>540bool541operator> (const multimap<Key, T, Compare, Allocator>& x,542           const multimap<Key, T, Compare, Allocator>& y);      // removed in C++20543 544template <class Key, class T, class Compare, class Allocator>545bool546operator>=(const multimap<Key, T, Compare, Allocator>& x,547           const multimap<Key, T, Compare, Allocator>& y);      // removed in C++20548 549template <class Key, class T, class Compare, class Allocator>550bool551operator<=(const multimap<Key, T, Compare, Allocator>& x,552           const multimap<Key, T, Compare, Allocator>& y);      // removed in C++20553 554template<class Key, class T, class Compare, class Allocator>555  synth-three-way-result<pair<const Key, T>>556    operator<=>(const multimap<Key, T, Compare, Allocator>& x,557                const multimap<Key, T, Compare, Allocator>& y); // since c++20558 559// specialized algorithms:560template <class Key, class T, class Compare, class Allocator>561void562swap(multimap<Key, T, Compare, Allocator>& x,563     multimap<Key, T, Compare, Allocator>& y)564    noexcept(noexcept(x.swap(y)));565 566template <class Key, class T, class Compare, class Allocator, class Predicate>567typename multimap<Key, T, Compare, Allocator>::size_type568erase_if(multimap<Key, T, Compare, Allocator>& c, Predicate pred);  // C++20569 570}  // std571 572*/573 574#if __cplusplus < 201103L && defined(_LIBCPP_USE_FROZEN_CXX03_HEADERS)575#  include <__cxx03/map>576#else577#  include <__algorithm/equal.h>578#  include <__algorithm/lexicographical_compare.h>579#  include <__algorithm/lexicographical_compare_three_way.h>580#  include <__assert>581#  include <__config>582#  include <__functional/binary_function.h>583#  include <__functional/is_transparent.h>584#  include <__functional/operations.h>585#  include <__iterator/erase_if_container.h>586#  include <__iterator/iterator_traits.h>587#  include <__iterator/ranges_iterator_traits.h>588#  include <__iterator/reverse_iterator.h>589#  include <__memory/addressof.h>590#  include <__memory/allocator.h>591#  include <__memory/allocator_traits.h>592#  include <__memory/compressed_pair.h>593#  include <__memory/pointer_traits.h>594#  include <__memory/unique_ptr.h>595#  include <__memory_resource/polymorphic_allocator.h>596#  include <__node_handle>597#  include <__ranges/access.h>598#  include <__ranges/concepts.h>599#  include <__ranges/container_compatible_range.h>600#  include <__ranges/from_range.h>601#  include <__tree>602#  include <__type_traits/container_traits.h>603#  include <__type_traits/is_allocator.h>604#  include <__type_traits/make_transparent.h>605#  include <__type_traits/remove_const.h>606#  include <__type_traits/type_identity.h>607#  include <__utility/forward.h>608#  include <__utility/lazy_synth_three_way_comparator.h>609#  include <__utility/pair.h>610#  include <__utility/piecewise_construct.h>611#  include <__utility/swap.h>612#  include <stdexcept>613#  include <tuple>614#  include <version>615 616// standard-mandated includes617 618// [iterator.range]619#  include <__iterator/access.h>620#  include <__iterator/data.h>621#  include <__iterator/empty.h>622#  include <__iterator/reverse_access.h>623#  include <__iterator/size.h>624 625// [associative.map.syn]626#  include <compare>627#  include <initializer_list>628 629#  if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)630#    pragma GCC system_header631#  endif632 633_LIBCPP_PUSH_MACROS634#  include <__undef_macros>635 636_LIBCPP_BEGIN_NAMESPACE_STD637 638template <class _Key, class _CP, class _Compare>639class __map_value_compare {640  _LIBCPP_COMPRESSED_ELEMENT(_Compare, __comp_);641 642public:643  _LIBCPP_HIDE_FROM_ABI __map_value_compare() _NOEXCEPT_(is_nothrow_default_constructible<_Compare>::value)644      : __comp_() {}645  _LIBCPP_HIDE_FROM_ABI __map_value_compare(_Compare __c) _NOEXCEPT_(is_nothrow_copy_constructible<_Compare>::value)646      : __comp_(__c) {}647  _LIBCPP_HIDE_FROM_ABI const _Compare& key_comp() const _NOEXCEPT { return __comp_; }648 649  _LIBCPP_HIDE_FROM_ABI bool operator()(const _CP& __x, const _CP& __y) const { return __comp_(__x.first, __y.first); }650  _LIBCPP_HIDE_FROM_ABI bool operator()(const _CP& __x, const _Key& __y) const { return __comp_(__x.first, __y); }651  _LIBCPP_HIDE_FROM_ABI bool operator()(const _Key& __x, const _CP& __y) const { return __comp_(__x, __y.first); }652  _LIBCPP_HIDE_FROM_ABI void swap(__map_value_compare& __y) _NOEXCEPT_(__is_nothrow_swappable_v<_Compare>) {653    using std::swap;654    swap(__comp_, __y.__comp_);655  }656 657#  if _LIBCPP_STD_VER >= 14658  template <typename _K2>659  _LIBCPP_HIDE_FROM_ABI bool operator()(const _K2& __x, const _CP& __y) const {660    return __comp_(__x, __y.first);661  }662 663  template <typename _K2>664  _LIBCPP_HIDE_FROM_ABI bool operator()(const _CP& __x, const _K2& __y) const {665    return __comp_(__x.first, __y);666  }667#  endif668};669 670template <class _Key, class _MapValueT, class _Compare>671struct __make_transparent<__map_value_compare<_Key, _MapValueT, _Compare> > {672  using type _LIBCPP_NODEBUG = __map_value_compare<_Key, _MapValueT, __make_transparent_t<_Compare> >;673};674 675#  if _LIBCPP_STD_VER >= 14676template <class _MapValueT, class _Key, class _Compare>677struct __lazy_synth_three_way_comparator<__map_value_compare<_Key, _MapValueT, _Compare>, _MapValueT, _MapValueT> {678  __lazy_synth_three_way_comparator<_Compare, _Key, _Key> __comp_;679 680  __lazy_synth_three_way_comparator(681      _LIBCPP_CTOR_LIFETIMEBOUND const __map_value_compare<_Key, _MapValueT, _Compare>& __comp)682      : __comp_(__comp.key_comp()) {}683 684  _LIBCPP_HIDE_FROM_ABI auto685  operator()(_LIBCPP_LIFETIMEBOUND const _MapValueT& __lhs, _LIBCPP_LIFETIMEBOUND const _MapValueT& __rhs) const {686    return __comp_(__lhs.first, __rhs.first);687  }688};689 690template <class _MapValueT, class _Key, class _TransparentKey, class _Compare>691struct __lazy_synth_three_way_comparator<__map_value_compare<_Key, _MapValueT, _Compare>, _TransparentKey, _MapValueT> {692  __lazy_synth_three_way_comparator<_Compare, _TransparentKey, _Key> __comp_;693 694  __lazy_synth_three_way_comparator(695      _LIBCPP_CTOR_LIFETIMEBOUND const __map_value_compare<_Key, _MapValueT, _Compare>& __comp)696      : __comp_(__comp.key_comp()) {}697 698  _LIBCPP_HIDE_FROM_ABI auto699  operator()(_LIBCPP_LIFETIMEBOUND const _TransparentKey& __lhs, _LIBCPP_LIFETIMEBOUND const _MapValueT& __rhs) const {700    return __comp_(__lhs, __rhs.first);701  }702};703 704template <class _MapValueT, class _Key, class _TransparentKey, class _Compare>705struct __lazy_synth_three_way_comparator<__map_value_compare<_Key, _MapValueT, _Compare>, _MapValueT, _TransparentKey> {706  __lazy_synth_three_way_comparator<_Compare, _Key, _TransparentKey> __comp_;707 708  __lazy_synth_three_way_comparator(709      _LIBCPP_CTOR_LIFETIMEBOUND const __map_value_compare<_Key, _MapValueT, _Compare>& __comp)710      : __comp_(__comp.key_comp()) {}711 712  _LIBCPP_HIDE_FROM_ABI auto713  operator()(_LIBCPP_LIFETIMEBOUND const _MapValueT& __lhs, _LIBCPP_LIFETIMEBOUND const _TransparentKey& __rhs) const {714    return __comp_(__lhs.first, __rhs);715  }716};717#  endif // _LIBCPP_STD_VER >= 14718 719template <class _Key, class _CP, class _Compare>720inline _LIBCPP_HIDE_FROM_ABI void721swap(__map_value_compare<_Key, _CP, _Compare>& __x, __map_value_compare<_Key, _CP, _Compare>& __y)722    _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) {723  __x.swap(__y);724}725 726template <class _Allocator>727class __map_node_destructor {728  typedef _Allocator allocator_type;729  typedef allocator_traits<allocator_type> __alloc_traits;730 731public:732  typedef typename __alloc_traits::pointer pointer;733 734private:735  allocator_type& __na_;736 737public:738  bool __first_constructed;739  bool __second_constructed;740 741  _LIBCPP_HIDE_FROM_ABI explicit __map_node_destructor(allocator_type& __na) _NOEXCEPT742      : __na_(__na),743        __first_constructed(false),744        __second_constructed(false) {}745 746#  ifndef _LIBCPP_CXX03_LANG747  _LIBCPP_HIDE_FROM_ABI __map_node_destructor(__tree_node_destructor<allocator_type>&& __x) _NOEXCEPT748      : __na_(__x.__na_),749        __first_constructed(__x.__value_constructed),750        __second_constructed(__x.__value_constructed) {751    __x.__value_constructed = false;752  }753#  endif // _LIBCPP_CXX03_LANG754 755  __map_node_destructor& operator=(const __map_node_destructor&) = delete;756 757  _LIBCPP_HIDE_FROM_ABI void operator()(pointer __p) _NOEXCEPT {758    if (__second_constructed)759      __alloc_traits::destroy(__na_, std::addressof(__p->__get_value().second));760    if (__first_constructed)761      __alloc_traits::destroy(__na_, std::addressof(__p->__get_value().first));762    if (__p)763      __alloc_traits::deallocate(__na_, __p, 1);764  }765};766 767template <class _Key, class _Tp>768struct __value_type;769 770template <class _TreeIterator>771class __map_iterator {772  _TreeIterator __i_;773 774public:775  using iterator_category = bidirectional_iterator_tag;776  using value_type        = typename _TreeIterator::value_type;777  using difference_type   = typename _TreeIterator::difference_type;778  using reference         = value_type&;779  using pointer           = typename _TreeIterator::pointer;780 781  _LIBCPP_HIDE_FROM_ABI __map_iterator() _NOEXCEPT {}782 783  _LIBCPP_HIDE_FROM_ABI __map_iterator(_TreeIterator __i) _NOEXCEPT : __i_(__i) {}784 785  _LIBCPP_HIDE_FROM_ABI reference operator*() const { return *__i_; }786  _LIBCPP_HIDE_FROM_ABI pointer operator->() const { return pointer_traits<pointer>::pointer_to(*__i_); }787 788  _LIBCPP_HIDE_FROM_ABI __map_iterator& operator++() {789    ++__i_;790    return *this;791  }792  _LIBCPP_HIDE_FROM_ABI __map_iterator operator++(int) {793    __map_iterator __t(*this);794    ++(*this);795    return __t;796  }797 798  _LIBCPP_HIDE_FROM_ABI __map_iterator& operator--() {799    --__i_;800    return *this;801  }802  _LIBCPP_HIDE_FROM_ABI __map_iterator operator--(int) {803    __map_iterator __t(*this);804    --(*this);805    return __t;806  }807 808  friend _LIBCPP_HIDE_FROM_ABI bool operator==(const __map_iterator& __x, const __map_iterator& __y) {809    return __x.__i_ == __y.__i_;810  }811  friend _LIBCPP_HIDE_FROM_ABI bool operator!=(const __map_iterator& __x, const __map_iterator& __y) {812    return __x.__i_ != __y.__i_;813  }814 815  template <class, class, class, class>816  friend class map;817  template <class, class, class, class>818  friend class multimap;819  template <class>820  friend class __map_const_iterator;821};822 823template <class _TreeIterator>824class __map_const_iterator {825  _TreeIterator __i_;826 827public:828  using iterator_category = bidirectional_iterator_tag;829  using value_type        = typename _TreeIterator::value_type;830  using difference_type   = typename _TreeIterator::difference_type;831  using reference         = const value_type&;832  using pointer           = typename _TreeIterator::pointer;833 834  _LIBCPP_HIDE_FROM_ABI __map_const_iterator() _NOEXCEPT {}835 836  _LIBCPP_HIDE_FROM_ABI __map_const_iterator(_TreeIterator __i) _NOEXCEPT : __i_(__i) {}837  _LIBCPP_HIDE_FROM_ABI838  __map_const_iterator(__map_iterator< typename _TreeIterator::__non_const_iterator> __i) _NOEXCEPT : __i_(__i.__i_) {}839 840  _LIBCPP_HIDE_FROM_ABI reference operator*() const { return *__i_; }841  _LIBCPP_HIDE_FROM_ABI pointer operator->() const { return pointer_traits<pointer>::pointer_to(*__i_); }842 843  _LIBCPP_HIDE_FROM_ABI __map_const_iterator& operator++() {844    ++__i_;845    return *this;846  }847  _LIBCPP_HIDE_FROM_ABI __map_const_iterator operator++(int) {848    __map_const_iterator __t(*this);849    ++(*this);850    return __t;851  }852 853  _LIBCPP_HIDE_FROM_ABI __map_const_iterator& operator--() {854    --__i_;855    return *this;856  }857  _LIBCPP_HIDE_FROM_ABI __map_const_iterator operator--(int) {858    __map_const_iterator __t(*this);859    --(*this);860    return __t;861  }862 863  friend _LIBCPP_HIDE_FROM_ABI bool operator==(const __map_const_iterator& __x, const __map_const_iterator& __y) {864    return __x.__i_ == __y.__i_;865  }866  friend _LIBCPP_HIDE_FROM_ABI bool operator!=(const __map_const_iterator& __x, const __map_const_iterator& __y) {867    return __x.__i_ != __y.__i_;868  }869 870  template <class, class, class, class>871  friend class map;872  template <class, class, class, class>873  friend class multimap;874  template <class, class, class>875  friend class __tree_const_iterator;876};877 878template <class _Key, class _Tp, class _Compare = less<_Key>, class _Allocator = allocator<pair<const _Key, _Tp> > >879class multimap;880 881template <class _Key, class _Tp, class _Compare = less<_Key>, class _Allocator = allocator<pair<const _Key, _Tp> > >882class map {883public:884  // types:885  typedef _Key key_type;886  typedef _Tp mapped_type;887  typedef pair<const key_type, mapped_type> value_type;888  typedef __type_identity_t<_Compare> key_compare;889  typedef __type_identity_t<_Allocator> allocator_type;890  typedef value_type& reference;891  typedef const value_type& const_reference;892 893  static_assert(is_same<typename allocator_type::value_type, value_type>::value,894                "Allocator::value_type must be same type as value_type");895 896  class value_compare : public __binary_function<value_type, value_type, bool> {897    friend class map;898 899  protected:900    key_compare comp;901 902    _LIBCPP_HIDE_FROM_ABI value_compare(key_compare __c) : comp(__c) {}903 904  public:905    _LIBCPP_HIDE_FROM_ABI bool operator()(const value_type& __x, const value_type& __y) const {906      return comp(__x.first, __y.first);907    }908  };909 910private:911  typedef std::__value_type<key_type, mapped_type> __value_type;912  typedef __map_value_compare<key_type, value_type, key_compare> __vc;913  typedef __tree<__value_type, __vc, allocator_type> __base;914  typedef typename __base::__node_traits __node_traits;915  typedef allocator_traits<allocator_type> __alloc_traits;916 917  static_assert(__check_valid_allocator<allocator_type>::value, "");918 919  __base __tree_;920 921public:922  typedef typename __alloc_traits::pointer pointer;923  typedef typename __alloc_traits::const_pointer const_pointer;924  typedef typename __alloc_traits::size_type size_type;925  typedef typename __alloc_traits::difference_type difference_type;926  typedef __map_iterator<typename __base::iterator> iterator;927  typedef __map_const_iterator<typename __base::const_iterator> const_iterator;928  typedef std::reverse_iterator<iterator> reverse_iterator;929  typedef std::reverse_iterator<const_iterator> const_reverse_iterator;930 931#  if _LIBCPP_STD_VER >= 17932  typedef __map_node_handle<typename __base::__node, allocator_type> node_type;933  typedef __insert_return_type<iterator, node_type> insert_return_type;934#  endif935 936  template <class _Key2, class _Value2, class _Comp2, class _Alloc2>937  friend class map;938  template <class _Key2, class _Value2, class _Comp2, class _Alloc2>939  friend class multimap;940 941  _LIBCPP_HIDE_FROM_ABI map() _NOEXCEPT_(942      is_nothrow_default_constructible<allocator_type>::value&& is_nothrow_default_constructible<key_compare>::value&&943          is_nothrow_copy_constructible<key_compare>::value)944      : __tree_(__vc(key_compare())) {}945 946  _LIBCPP_HIDE_FROM_ABI explicit map(const key_compare& __comp) _NOEXCEPT_(947      is_nothrow_default_constructible<allocator_type>::value&& is_nothrow_copy_constructible<key_compare>::value)948      : __tree_(__vc(__comp)) {}949 950  _LIBCPP_HIDE_FROM_ABI explicit map(const key_compare& __comp, const allocator_type& __a)951      : __tree_(__vc(__comp), typename __base::allocator_type(__a)) {}952 953  template <class _InputIterator>954  _LIBCPP_HIDE_FROM_ABI map(_InputIterator __f, _InputIterator __l, const key_compare& __comp = key_compare())955      : __tree_(__vc(__comp)) {956    insert(__f, __l);957  }958 959  template <class _InputIterator>960  _LIBCPP_HIDE_FROM_ABI961  map(_InputIterator __f, _InputIterator __l, const key_compare& __comp, const allocator_type& __a)962      : __tree_(__vc(__comp), typename __base::allocator_type(__a)) {963    insert(__f, __l);964  }965 966#  if _LIBCPP_STD_VER >= 23967  template <_ContainerCompatibleRange<value_type> _Range>968  _LIBCPP_HIDE_FROM_ABI969  map(from_range_t,970      _Range&& __range,971      const key_compare& __comp = key_compare(),972      const allocator_type& __a = allocator_type())973      : __tree_(__vc(__comp), typename __base::allocator_type(__a)) {974    insert_range(std::forward<_Range>(__range));975  }976#  endif977 978#  if _LIBCPP_STD_VER >= 14979  template <class _InputIterator>980  _LIBCPP_HIDE_FROM_ABI map(_InputIterator __f, _InputIterator __l, const allocator_type& __a)981      : map(__f, __l, key_compare(), __a) {}982#  endif983 984#  if _LIBCPP_STD_VER >= 23985  template <_ContainerCompatibleRange<value_type> _Range>986  _LIBCPP_HIDE_FROM_ABI map(from_range_t, _Range&& __range, const allocator_type& __a)987      : map(from_range, std::forward<_Range>(__range), key_compare(), __a) {}988#  endif989 990  _LIBCPP_HIDE_FROM_ABI map(const map& __m) = default;991 992  _LIBCPP_HIDE_FROM_ABI map& operator=(const map& __m) = default;993 994#  ifndef _LIBCPP_CXX03_LANG995 996  _LIBCPP_HIDE_FROM_ABI map(map&& __m) = default;997 998  _LIBCPP_HIDE_FROM_ABI map(map&& __m, const allocator_type& __a) : __tree_(std::move(__m.__tree_), __a) {}999 1000  _LIBCPP_HIDE_FROM_ABI map& operator=(map&& __m) = default;1001 1002  _LIBCPP_HIDE_FROM_ABI map(initializer_list<value_type> __il, const key_compare& __comp = key_compare())1003      : __tree_(__vc(__comp)) {1004    insert(__il.begin(), __il.end());1005  }1006 1007  _LIBCPP_HIDE_FROM_ABI map(initializer_list<value_type> __il, const key_compare& __comp, const allocator_type& __a)1008      : __tree_(__vc(__comp), typename __base::allocator_type(__a)) {1009    insert(__il.begin(), __il.end());1010  }1011 1012#    if _LIBCPP_STD_VER >= 141013  _LIBCPP_HIDE_FROM_ABI map(initializer_list<value_type> __il, const allocator_type& __a)1014      : map(__il, key_compare(), __a) {}1015#    endif1016 1017  _LIBCPP_HIDE_FROM_ABI map& operator=(initializer_list<value_type> __il) {1018    __tree_.__assign_unique(__il.begin(), __il.end());1019    return *this;1020  }1021 1022#  endif // _LIBCPP_CXX03_LANG1023 1024  _LIBCPP_HIDE_FROM_ABI explicit map(const allocator_type& __a) : __tree_(typename __base::allocator_type(__a)) {}1025 1026  _LIBCPP_HIDE_FROM_ABI map(const map& __m, const allocator_type& __alloc) : __tree_(__m.__tree_, __alloc) {}1027 1028  _LIBCPP_HIDE_FROM_ABI ~map() { static_assert(sizeof(std::__diagnose_non_const_comparator<_Key, _Compare>()), ""); }1029 1030  _LIBCPP_HIDE_FROM_ABI iterator begin() _NOEXCEPT { return __tree_.begin(); }1031  _LIBCPP_HIDE_FROM_ABI const_iterator begin() const _NOEXCEPT { return __tree_.begin(); }1032  _LIBCPP_HIDE_FROM_ABI iterator end() _NOEXCEPT { return __tree_.end(); }1033  _LIBCPP_HIDE_FROM_ABI const_iterator end() const _NOEXCEPT { return __tree_.end(); }1034 1035  _LIBCPP_HIDE_FROM_ABI reverse_iterator rbegin() _NOEXCEPT { return reverse_iterator(end()); }1036  _LIBCPP_HIDE_FROM_ABI const_reverse_iterator rbegin() const _NOEXCEPT { return const_reverse_iterator(end()); }1037  _LIBCPP_HIDE_FROM_ABI reverse_iterator rend() _NOEXCEPT { return reverse_iterator(begin()); }1038  _LIBCPP_HIDE_FROM_ABI const_reverse_iterator rend() const _NOEXCEPT { return const_reverse_iterator(begin()); }1039 1040  _LIBCPP_HIDE_FROM_ABI const_iterator cbegin() const _NOEXCEPT { return begin(); }1041  _LIBCPP_HIDE_FROM_ABI const_iterator cend() const _NOEXCEPT { return end(); }1042  _LIBCPP_HIDE_FROM_ABI const_reverse_iterator crbegin() const _NOEXCEPT { return rbegin(); }1043  _LIBCPP_HIDE_FROM_ABI const_reverse_iterator crend() const _NOEXCEPT { return rend(); }1044 1045  [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI bool empty() const _NOEXCEPT { return __tree_.size() == 0; }1046  _LIBCPP_HIDE_FROM_ABI size_type size() const _NOEXCEPT { return __tree_.size(); }1047  _LIBCPP_HIDE_FROM_ABI size_type max_size() const _NOEXCEPT { return __tree_.max_size(); }1048 1049  _LIBCPP_HIDE_FROM_ABI mapped_type& operator[](const key_type& __k);1050#  ifndef _LIBCPP_CXX03_LANG1051  _LIBCPP_HIDE_FROM_ABI mapped_type& operator[](key_type&& __k);1052#  endif1053 1054  template <class _Arg,1055            __enable_if_t<__is_transparently_comparable_v<_Compare, key_type, __remove_cvref_t<_Arg> >, int> = 0>1056  _LIBCPP_HIDE_FROM_ABI mapped_type& at(_Arg&& __arg) {1057    auto [_, __child] = __tree_.__find_equal(__arg);1058    if (__child == nullptr)1059      std::__throw_out_of_range("map::at:  key not found");1060    return static_cast<__node_pointer>(__child)->__get_value().second;1061  }1062 1063  template <class _Arg,1064            __enable_if_t<__is_transparently_comparable_v<_Compare, key_type, __remove_cvref_t<_Arg> >, int> = 0>1065  _LIBCPP_HIDE_FROM_ABI const mapped_type& at(_Arg&& __arg) const {1066    auto [_, __child] = __tree_.__find_equal(__arg);1067    if (__child == nullptr)1068      std::__throw_out_of_range("map::at:  key not found");1069    return static_cast<__node_pointer>(__child)->__get_value().second;1070  }1071 1072  _LIBCPP_HIDE_FROM_ABI mapped_type& at(const key_type& __k);1073  _LIBCPP_HIDE_FROM_ABI const mapped_type& at(const key_type& __k) const;1074 1075  _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const _NOEXCEPT { return allocator_type(__tree_.__alloc()); }1076  _LIBCPP_HIDE_FROM_ABI key_compare key_comp() const { return __tree_.value_comp().key_comp(); }1077  _LIBCPP_HIDE_FROM_ABI value_compare value_comp() const { return value_compare(__tree_.value_comp().key_comp()); }1078 1079#  ifndef _LIBCPP_CXX03_LANG1080  template <class... _Args>1081  _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> emplace(_Args&&... __args) {1082    return __tree_.__emplace_unique(std::forward<_Args>(__args)...);1083  }1084 1085  template <class... _Args>1086  _LIBCPP_HIDE_FROM_ABI iterator emplace_hint(const_iterator __p, _Args&&... __args) {1087    return __tree_.__emplace_hint_unique(__p.__i_, std::forward<_Args>(__args)...).first;1088  }1089 1090  template <class _Pp, __enable_if_t<is_constructible<value_type, _Pp>::value, int> = 0>1091  _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert(_Pp&& __p) {1092    return __tree_.__emplace_unique(std::forward<_Pp>(__p));1093  }1094 1095  template <class _Pp, __enable_if_t<is_constructible<value_type, _Pp>::value, int> = 0>1096  _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __pos, _Pp&& __p) {1097    return __tree_.__emplace_hint_unique(__pos.__i_, std::forward<_Pp>(__p)).first;1098  }1099 1100#  endif // _LIBCPP_CXX03_LANG1101 1102  _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert(const value_type& __v) { return __tree_.__emplace_unique(__v); }1103 1104  _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, const value_type& __v) {1105    return __tree_.__emplace_hint_unique(__p.__i_, __v).first;1106  }1107 1108#  ifndef _LIBCPP_CXX03_LANG1109  _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert(value_type&& __v) {1110    return __tree_.__emplace_unique(std::move(__v));1111  }1112 1113  _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, value_type&& __v) {1114    return __tree_.__emplace_hint_unique(__p.__i_, std::move(__v)).first;1115  }1116 1117  _LIBCPP_HIDE_FROM_ABI void insert(initializer_list<value_type> __il) { insert(__il.begin(), __il.end()); }1118#  endif1119 1120  template <class _InputIterator>1121  _LIBCPP_HIDE_FROM_ABI void insert(_InputIterator __first, _InputIterator __last) {1122    __tree_.__insert_range_unique(__first, __last);1123  }1124 1125#  if _LIBCPP_STD_VER >= 231126  template <_ContainerCompatibleRange<value_type> _Range>1127  _LIBCPP_HIDE_FROM_ABI void insert_range(_Range&& __range) {1128    __tree_.__insert_range_unique(ranges::begin(__range), ranges::end(__range));1129  }1130#  endif1131 1132#  if _LIBCPP_STD_VER >= 171133 1134  template <class... _Args>1135  _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> try_emplace(const key_type& __k, _Args&&... __args) {1136    return __tree_.__emplace_unique(1137        std::piecewise_construct, std::forward_as_tuple(__k), std::forward_as_tuple(std::forward<_Args>(__args)...));1138  }1139 1140  template <class... _Args>1141  _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> try_emplace(key_type&& __k, _Args&&... __args) {1142    return __tree_.__emplace_unique(1143        std::piecewise_construct,1144        std::forward_as_tuple(std::move(__k)),1145        std::forward_as_tuple(std::forward<_Args>(__args)...));1146  }1147 1148  template <class... _Args>1149  _LIBCPP_HIDE_FROM_ABI iterator try_emplace(const_iterator __h, const key_type& __k, _Args&&... __args) {1150    return __tree_1151        .__emplace_hint_unique(1152            __h.__i_,1153            std::piecewise_construct,1154            std::forward_as_tuple(__k),1155            std::forward_as_tuple(std::forward<_Args>(__args)...))1156        .first;1157  }1158 1159  template <class... _Args>1160  _LIBCPP_HIDE_FROM_ABI iterator try_emplace(const_iterator __h, key_type&& __k, _Args&&... __args) {1161    return __tree_1162        .__emplace_hint_unique(1163            __h.__i_,1164            std::piecewise_construct,1165            std::forward_as_tuple(std::move(__k)),1166            std::forward_as_tuple(std::forward<_Args>(__args)...))1167        .first;1168  }1169 1170  template <class _Vp>1171  _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert_or_assign(const key_type& __k, _Vp&& __v) {1172    auto __result              = __tree_.__emplace_unique(__k, std::forward<_Vp>(__v));1173    auto& [__iter, __inserted] = __result;1174    if (!__inserted)1175      __iter->second = std::forward<_Vp>(__v);1176    return __result;1177  }1178 1179  template <class _Vp>1180  _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert_or_assign(key_type&& __k, _Vp&& __v) {1181    auto __result              = __tree_.__emplace_unique(std::move(__k), std::forward<_Vp>(__v));1182    auto& [__iter, __inserted] = __result;1183    if (!__inserted)1184      __iter->second = std::forward<_Vp>(__v);1185    return __result;1186  }1187 1188  template <class _Vp>1189  _LIBCPP_HIDE_FROM_ABI iterator insert_or_assign(const_iterator __h, const key_type& __k, _Vp&& __v) {1190    auto [__r, __inserted] = __tree_.__emplace_hint_unique(__h.__i_, __k, std::forward<_Vp>(__v));1191 1192    if (!__inserted)1193      __r->second = std::forward<_Vp>(__v);1194 1195    return __r;1196  }1197 1198  template <class _Vp>1199  _LIBCPP_HIDE_FROM_ABI iterator insert_or_assign(const_iterator __h, key_type&& __k, _Vp&& __v) {1200    auto [__r, __inserted] = __tree_.__emplace_hint_unique(__h.__i_, std::move(__k), std::forward<_Vp>(__v));1201 1202    if (!__inserted)1203      __r->second = std::forward<_Vp>(__v);1204 1205    return __r;1206  }1207 1208#  endif // _LIBCPP_STD_VER >= 171209 1210  _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __p) { return __tree_.erase(__p.__i_); }1211  _LIBCPP_HIDE_FROM_ABI iterator erase(iterator __p) { return __tree_.erase(__p.__i_); }1212  _LIBCPP_HIDE_FROM_ABI size_type erase(const key_type& __k) { return __tree_.__erase_unique(__k); }1213  _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __f, const_iterator __l) {1214    return __tree_.erase(__f.__i_, __l.__i_);1215  }1216  _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT { __tree_.clear(); }1217 1218#  if _LIBCPP_STD_VER >= 171219  _LIBCPP_HIDE_FROM_ABI insert_return_type insert(node_type&& __nh) {1220    _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(),1221                                        "node_type with incompatible allocator passed to map::insert()");1222    return __tree_.template __node_handle_insert_unique< node_type, insert_return_type>(std::move(__nh));1223  }1224  _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __hint, node_type&& __nh) {1225    _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(),1226                                        "node_type with incompatible allocator passed to map::insert()");1227    return __tree_.template __node_handle_insert_unique<node_type>(__hint.__i_, std::move(__nh));1228  }1229  _LIBCPP_HIDE_FROM_ABI node_type extract(key_type const& __key) {1230    return __tree_.template __node_handle_extract<node_type>(__key);1231  }1232  _LIBCPP_HIDE_FROM_ABI node_type extract(const_iterator __it) {1233    return __tree_.template __node_handle_extract<node_type>(__it.__i_);1234  }1235  template <class _Compare2>1236  _LIBCPP_HIDE_FROM_ABI void merge(map<key_type, mapped_type, _Compare2, allocator_type>& __source) {1237    _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(1238        __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");1239    __tree_.__node_handle_merge_unique(__source.__tree_);1240  }1241  template <class _Compare2>1242  _LIBCPP_HIDE_FROM_ABI void merge(map<key_type, mapped_type, _Compare2, allocator_type>&& __source) {1243    _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(1244        __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");1245    __tree_.__node_handle_merge_unique(__source.__tree_);1246  }1247  template <class _Compare2>1248  _LIBCPP_HIDE_FROM_ABI void merge(multimap<key_type, mapped_type, _Compare2, allocator_type>& __source) {1249    _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(1250        __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");1251    __tree_.__node_handle_merge_unique(__source.__tree_);1252  }1253  template <class _Compare2>1254  _LIBCPP_HIDE_FROM_ABI void merge(multimap<key_type, mapped_type, _Compare2, allocator_type>&& __source) {1255    _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(1256        __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");1257    __tree_.__node_handle_merge_unique(__source.__tree_);1258  }1259#  endif1260 1261  _LIBCPP_HIDE_FROM_ABI void swap(map& __m) _NOEXCEPT_(__is_nothrow_swappable_v<__base>) { __tree_.swap(__m.__tree_); }1262 1263  _LIBCPP_HIDE_FROM_ABI iterator find(const key_type& __k) { return __tree_.find(__k); }1264  _LIBCPP_HIDE_FROM_ABI const_iterator find(const key_type& __k) const { return __tree_.find(__k); }1265#  if _LIBCPP_STD_VER >= 141266  template <typename _K2,1267            enable_if_t<__is_transparent_v<_Compare, _K2> || __is_transparently_comparable_v<_Compare, key_type, _K2>,1268                        int> = 0>1269  _LIBCPP_HIDE_FROM_ABI iterator find(const _K2& __k) {1270    return __tree_.find(__k);1271  }1272  template <typename _K2,1273            enable_if_t<__is_transparent_v<_Compare, _K2> || __is_transparently_comparable_v<_Compare, key_type, _K2>,1274                        int> = 0>1275  _LIBCPP_HIDE_FROM_ABI const_iterator find(const _K2& __k) const {1276    return __tree_.find(__k);1277  }1278#  endif1279 1280  _LIBCPP_HIDE_FROM_ABI size_type count(const key_type& __k) const { return __tree_.__count_unique(__k); }1281#  if _LIBCPP_STD_VER >= 141282  template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>1283  _LIBCPP_HIDE_FROM_ABI size_type count(const _K2& __k) const {1284    return __tree_.__count_multi(__k);1285  }1286#  endif1287 1288#  if _LIBCPP_STD_VER >= 201289  _LIBCPP_HIDE_FROM_ABI bool contains(const key_type& __k) const { return find(__k) != end(); }1290  template <typename _K2,1291            enable_if_t<__is_transparent_v<_Compare, _K2> || __is_transparently_comparable_v<_Compare, key_type, _K2>,1292                        int> = 0>1293  _LIBCPP_HIDE_FROM_ABI bool contains(const _K2& __k) const {1294    return find(__k) != end();1295  }1296#  endif // _LIBCPP_STD_VER >= 201297 1298  _LIBCPP_HIDE_FROM_ABI iterator lower_bound(const key_type& __k) { return __tree_.__lower_bound_unique(__k); }1299 1300  _LIBCPP_HIDE_FROM_ABI const_iterator lower_bound(const key_type& __k) const {1301    return __tree_.__lower_bound_unique(__k);1302  }1303 1304  // The transparent versions of the lookup functions use the _multi version, since a non-element key is allowed to1305  // match multiple elements.1306#  if _LIBCPP_STD_VER >= 141307  template <typename _K2,1308            enable_if_t<__is_transparent_v<_Compare, _K2> || __is_transparently_comparable_v<_Compare, key_type, _K2>,1309                        int> = 0>1310  _LIBCPP_HIDE_FROM_ABI iterator lower_bound(const _K2& __k) {1311    return __tree_.__lower_bound_multi(__k);1312  }1313 1314  template <typename _K2,1315            enable_if_t<__is_transparent_v<_Compare, _K2> || __is_transparently_comparable_v<_Compare, key_type, _K2>,1316                        int> = 0>1317  _LIBCPP_HIDE_FROM_ABI const_iterator lower_bound(const _K2& __k) const {1318    return __tree_.__lower_bound_multi(__k);1319  }1320#  endif1321 1322  _LIBCPP_HIDE_FROM_ABI iterator upper_bound(const key_type& __k) { return __tree_.__upper_bound_unique(__k); }1323 1324  _LIBCPP_HIDE_FROM_ABI const_iterator upper_bound(const key_type& __k) const {1325    return __tree_.__upper_bound_unique(__k);1326  }1327 1328#  if _LIBCPP_STD_VER >= 141329  template <typename _K2,1330            enable_if_t<__is_transparent_v<_Compare, _K2> || __is_transparently_comparable_v<_Compare, key_type, _K2>,1331                        int> = 0>1332  _LIBCPP_HIDE_FROM_ABI iterator upper_bound(const _K2& __k) {1333    return __tree_.__upper_bound_multi(__k);1334  }1335  template <typename _K2,1336            enable_if_t<__is_transparent_v<_Compare, _K2> || __is_transparently_comparable_v<_Compare, key_type, _K2>,1337                        int> = 0>1338  _LIBCPP_HIDE_FROM_ABI const_iterator upper_bound(const _K2& __k) const {1339    return __tree_.__upper_bound_multi(__k);1340  }1341#  endif1342 1343  _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const key_type& __k) {1344    return __tree_.__equal_range_unique(__k);1345  }1346  _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const key_type& __k) const {1347    return __tree_.__equal_range_unique(__k);1348  }1349#  if _LIBCPP_STD_VER >= 141350  template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>1351  _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const _K2& __k) {1352    return __tree_.__equal_range_multi(__k);1353  }1354  template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>1355  _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const _K2& __k) const {1356    return __tree_.__equal_range_multi(__k);1357  }1358#  endif1359 1360private:1361  typedef typename __base::__node __node;1362  typedef typename __base::__node_allocator __node_allocator;1363  typedef typename __base::__node_pointer __node_pointer;1364  typedef typename __base::__node_base_pointer __node_base_pointer;1365  typedef typename __base::__parent_pointer __parent_pointer;1366 1367  typedef __map_node_destructor<__node_allocator> _Dp;1368  typedef unique_ptr<__node, _Dp> __node_holder;1369 1370#  ifdef _LIBCPP_CXX03_LANG1371  _LIBCPP_HIDE_FROM_ABI __node_holder __construct_node_with_key(const key_type& __k);1372#  endif1373};1374 1375#  if _LIBCPP_STD_VER >= 171376template <class _InputIterator,1377          class _Compare   = less<__iter_key_type<_InputIterator>>,1378          class _Allocator = allocator<__iter_to_alloc_type<_InputIterator>>,1379          class            = enable_if_t<__has_input_iterator_category<_InputIterator>::value, void>,1380          class            = enable_if_t<!__is_allocator_v<_Compare>>,1381          class            = enable_if_t<__is_allocator_v<_Allocator>>>1382map(_InputIterator, _InputIterator, _Compare = _Compare(), _Allocator = _Allocator())1383    -> map<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>, _Compare, _Allocator>;1384 1385#    if _LIBCPP_STD_VER >= 231386template <ranges::input_range _Range,1387          class _Compare   = less<__range_key_type<_Range>>,1388          class _Allocator = allocator<__range_to_alloc_type<_Range>>,1389          class            = enable_if_t<!__is_allocator_v<_Compare>>,1390          class            = enable_if_t<__is_allocator_v<_Allocator>>>1391map(from_range_t, _Range&&, _Compare = _Compare(), _Allocator = _Allocator())1392    -> map<__range_key_type<_Range>, __range_mapped_type<_Range>, _Compare, _Allocator>;1393#    endif1394 1395template <class _Key,1396          class _Tp,1397          class _Compare   = less<remove_const_t<_Key>>,1398          class _Allocator = allocator<pair<const _Key, _Tp>>,1399          class            = enable_if_t<!__is_allocator_v<_Compare>>,1400          class            = enable_if_t<__is_allocator_v<_Allocator>>>1401map(initializer_list<pair<_Key, _Tp>>, _Compare = _Compare(), _Allocator = _Allocator())1402    -> map<remove_const_t<_Key>, _Tp, _Compare, _Allocator>;1403 1404template <class _InputIterator,1405          class _Allocator,1406          class = enable_if_t<__has_input_iterator_category<_InputIterator>::value, void>,1407          class = enable_if_t<__is_allocator_v<_Allocator>>>1408map(_InputIterator, _InputIterator, _Allocator)1409    -> map<__iter_key_type<_InputIterator>,1410           __iter_mapped_type<_InputIterator>,1411           less<__iter_key_type<_InputIterator>>,1412           _Allocator>;1413 1414#    if _LIBCPP_STD_VER >= 231415template <ranges::input_range _Range, class _Allocator, class = enable_if_t<__is_allocator_v<_Allocator>>>1416map(from_range_t, _Range&&, _Allocator)1417    -> map<__range_key_type<_Range>, __range_mapped_type<_Range>, less<__range_key_type<_Range>>, _Allocator>;1418#    endif1419 1420template <class _Key, class _Tp, class _Allocator, class = enable_if_t<__is_allocator_v<_Allocator>>>1421map(initializer_list<pair<_Key, _Tp>>, _Allocator)1422    -> map<remove_const_t<_Key>, _Tp, less<remove_const_t<_Key>>, _Allocator>;1423#  endif1424 1425#  ifndef _LIBCPP_CXX03_LANG1426template <class _Key, class _Tp, class _Compare, class _Allocator>1427_Tp& map<_Key, _Tp, _Compare, _Allocator>::operator[](const key_type& __k) {1428  return __tree_.__emplace_unique(std::piecewise_construct, std::forward_as_tuple(__k), std::forward_as_tuple())1429      .first->second;1430}1431 1432template <class _Key, class _Tp, class _Compare, class _Allocator>1433_Tp& map<_Key, _Tp, _Compare, _Allocator>::operator[](key_type&& __k) {1434  return __tree_1435      .__emplace_unique(std::piecewise_construct, std::forward_as_tuple(std::move(__k)), std::forward_as_tuple())1436      .first->second;1437}1438 1439#  else // _LIBCPP_CXX03_LANG1440 1441template <class _Key, class _Tp, class _Compare, class _Allocator>1442typename map<_Key, _Tp, _Compare, _Allocator>::__node_holder1443map<_Key, _Tp, _Compare, _Allocator>::__construct_node_with_key(const key_type& __k) {1444  __node_allocator& __na = __tree_.__node_alloc();1445  __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));1446  __node_traits::construct(__na, std::addressof(__h->__get_value().first), __k);1447  __h.get_deleter().__first_constructed = true;1448  __node_traits::construct(__na, std::addressof(__h->__get_value().second));1449  __h.get_deleter().__second_constructed = true;1450  return __h;1451}1452 1453template <class _Key, class _Tp, class _Compare, class _Allocator>1454_Tp& map<_Key, _Tp, _Compare, _Allocator>::operator[](const key_type& __k) {1455  auto [__parent, __child] = __tree_.__find_equal(__k);1456  __node_pointer __r       = static_cast<__node_pointer>(__child);1457  if (__child == nullptr) {1458    __node_holder __h = __construct_node_with_key(__k);1459    __tree_.__insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));1460    __r = __h.release();1461  }1462  return __r->__get_value().second;1463}1464 1465#  endif // _LIBCPP_CXX03_LANG1466 1467template <class _Key, class _Tp, class _Compare, class _Allocator>1468_Tp& map<_Key, _Tp, _Compare, _Allocator>::at(const key_type& __k) {1469  auto [_, __child] = __tree_.__find_equal(__k);1470  if (__child == nullptr)1471    std::__throw_out_of_range("map::at:  key not found");1472  return static_cast<__node_pointer>(__child)->__get_value().second;1473}1474 1475template <class _Key, class _Tp, class _Compare, class _Allocator>1476const _Tp& map<_Key, _Tp, _Compare, _Allocator>::at(const key_type& __k) const {1477  auto [_, __child] = __tree_.__find_equal(__k);1478  if (__child == nullptr)1479    std::__throw_out_of_range("map::at:  key not found");1480  return static_cast<__node_pointer>(__child)->__get_value().second;1481}1482 1483template <class _Key, class _Tp, class _Compare, class _Allocator>1484inline _LIBCPP_HIDE_FROM_ABI bool1485operator==(const map<_Key, _Tp, _Compare, _Allocator>& __x, const map<_Key, _Tp, _Compare, _Allocator>& __y) {1486  return __x.size() == __y.size() && std::equal(__x.begin(), __x.end(), __y.begin());1487}1488 1489#  if _LIBCPP_STD_VER <= 171490 1491template <class _Key, class _Tp, class _Compare, class _Allocator>1492inline _LIBCPP_HIDE_FROM_ABI bool1493operator<(const map<_Key, _Tp, _Compare, _Allocator>& __x, const map<_Key, _Tp, _Compare, _Allocator>& __y) {1494  return std::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());1495}1496 1497template <class _Key, class _Tp, class _Compare, class _Allocator>1498inline _LIBCPP_HIDE_FROM_ABI bool1499operator!=(const map<_Key, _Tp, _Compare, _Allocator>& __x, const map<_Key, _Tp, _Compare, _Allocator>& __y) {1500  return !(__x == __y);1501}1502 1503template <class _Key, class _Tp, class _Compare, class _Allocator>1504inline _LIBCPP_HIDE_FROM_ABI bool1505operator>(const map<_Key, _Tp, _Compare, _Allocator>& __x, const map<_Key, _Tp, _Compare, _Allocator>& __y) {1506  return __y < __x;1507}1508 1509template <class _Key, class _Tp, class _Compare, class _Allocator>1510inline _LIBCPP_HIDE_FROM_ABI bool1511operator>=(const map<_Key, _Tp, _Compare, _Allocator>& __x, const map<_Key, _Tp, _Compare, _Allocator>& __y) {1512  return !(__x < __y);1513}1514 1515template <class _Key, class _Tp, class _Compare, class _Allocator>1516inline _LIBCPP_HIDE_FROM_ABI bool1517operator<=(const map<_Key, _Tp, _Compare, _Allocator>& __x, const map<_Key, _Tp, _Compare, _Allocator>& __y) {1518  return !(__y < __x);1519}1520 1521#  else // #if _LIBCPP_STD_VER <= 171522 1523template <class _Key, class _Tp, class _Compare, class _Allocator>1524_LIBCPP_HIDE_FROM_ABI __synth_three_way_result<pair<const _Key, _Tp>>1525operator<=>(const map<_Key, _Tp, _Compare, _Allocator>& __x, const map<_Key, _Tp, _Compare, _Allocator>& __y) {1526  return std::lexicographical_compare_three_way(__x.begin(), __x.end(), __y.begin(), __y.end(), std::__synth_three_way);1527}1528 1529#  endif // #if _LIBCPP_STD_VER <= 171530 1531template <class _Key, class _Tp, class _Compare, class _Allocator>1532inline _LIBCPP_HIDE_FROM_ABI void1533swap(map<_Key, _Tp, _Compare, _Allocator>& __x, map<_Key, _Tp, _Compare, _Allocator>& __y)1534    _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) {1535  __x.swap(__y);1536}1537 1538#  if _LIBCPP_STD_VER >= 201539template <class _Key, class _Tp, class _Compare, class _Allocator, class _Predicate>1540inline _LIBCPP_HIDE_FROM_ABI typename map<_Key, _Tp, _Compare, _Allocator>::size_type1541erase_if(map<_Key, _Tp, _Compare, _Allocator>& __c, _Predicate __pred) {1542  return std::__libcpp_erase_if_container(__c, __pred);1543}1544#  endif1545 1546template <class _Key, class _Tp, class _Compare, class _Allocator>1547struct __container_traits<map<_Key, _Tp, _Compare, _Allocator> > {1548  // http://eel.is/c++draft/associative.reqmts.except#21549  // For associative containers, if an exception is thrown by any operation from within1550  // an insert or emplace function inserting a single element, the insertion has no effect.1551  static _LIBCPP_CONSTEXPR const bool __emplacement_has_strong_exception_safety_guarantee = true;1552 1553  static _LIBCPP_CONSTEXPR const bool __reservable = false;1554};1555 1556template <class _Key, class _Tp, class _Compare, class _Allocator>1557class multimap {1558public:1559  // types:1560  typedef _Key key_type;1561  typedef _Tp mapped_type;1562  typedef pair<const key_type, mapped_type> value_type;1563  typedef __type_identity_t<_Compare> key_compare;1564  typedef __type_identity_t<_Allocator> allocator_type;1565  typedef value_type& reference;1566  typedef const value_type& const_reference;1567 1568  static_assert(__check_valid_allocator<allocator_type>::value, "");1569  static_assert(is_same<typename allocator_type::value_type, value_type>::value,1570                "Allocator::value_type must be same type as value_type");1571 1572  class value_compare : public __binary_function<value_type, value_type, bool> {1573    friend class multimap;1574 1575  protected:1576    key_compare comp;1577 1578    _LIBCPP_HIDE_FROM_ABI value_compare(key_compare __c) : comp(__c) {}1579 1580  public:1581    _LIBCPP_HIDE_FROM_ABI bool operator()(const value_type& __x, const value_type& __y) const {1582      return comp(__x.first, __y.first);1583    }1584  };1585 1586private:1587  typedef std::__value_type<key_type, mapped_type> __value_type;1588  typedef __map_value_compare<key_type, value_type, key_compare> __vc;1589  typedef __tree<__value_type, __vc, allocator_type> __base;1590  typedef typename __base::__node_traits __node_traits;1591  typedef allocator_traits<allocator_type> __alloc_traits;1592 1593  __base __tree_;1594 1595public:1596  typedef typename __alloc_traits::pointer pointer;1597  typedef typename __alloc_traits::const_pointer const_pointer;1598  typedef typename __alloc_traits::size_type size_type;1599  typedef typename __alloc_traits::difference_type difference_type;1600  typedef __map_iterator<typename __base::iterator> iterator;1601  typedef __map_const_iterator<typename __base::const_iterator> const_iterator;1602  typedef std::reverse_iterator<iterator> reverse_iterator;1603  typedef std::reverse_iterator<const_iterator> const_reverse_iterator;1604 1605#  if _LIBCPP_STD_VER >= 171606  typedef __map_node_handle<typename __base::__node, allocator_type> node_type;1607#  endif1608 1609  template <class _Key2, class _Value2, class _Comp2, class _Alloc2>1610  friend class map;1611  template <class _Key2, class _Value2, class _Comp2, class _Alloc2>1612  friend class multimap;1613 1614  _LIBCPP_HIDE_FROM_ABI multimap() _NOEXCEPT_(1615      is_nothrow_default_constructible<allocator_type>::value&& is_nothrow_default_constructible<key_compare>::value&&1616          is_nothrow_copy_constructible<key_compare>::value)1617      : __tree_(__vc(key_compare())) {}1618 1619  _LIBCPP_HIDE_FROM_ABI explicit multimap(const key_compare& __comp) _NOEXCEPT_(1620      is_nothrow_default_constructible<allocator_type>::value&& is_nothrow_copy_constructible<key_compare>::value)1621      : __tree_(__vc(__comp)) {}1622 1623  _LIBCPP_HIDE_FROM_ABI explicit multimap(const key_compare& __comp, const allocator_type& __a)1624      : __tree_(__vc(__comp), typename __base::allocator_type(__a)) {}1625 1626  template <class _InputIterator>1627  _LIBCPP_HIDE_FROM_ABI multimap(_InputIterator __f, _InputIterator __l, const key_compare& __comp = key_compare())1628      : __tree_(__vc(__comp)) {1629    insert(__f, __l);1630  }1631 1632  template <class _InputIterator>1633  _LIBCPP_HIDE_FROM_ABI1634  multimap(_InputIterator __f, _InputIterator __l, const key_compare& __comp, const allocator_type& __a)1635      : __tree_(__vc(__comp), typename __base::allocator_type(__a)) {1636    insert(__f, __l);1637  }1638 1639#  if _LIBCPP_STD_VER >= 231640  template <_ContainerCompatibleRange<value_type> _Range>1641  _LIBCPP_HIDE_FROM_ABI1642  multimap(from_range_t,1643           _Range&& __range,1644           const key_compare& __comp = key_compare(),1645           const allocator_type& __a = allocator_type())1646      : __tree_(__vc(__comp), typename __base::allocator_type(__a)) {1647    insert_range(std::forward<_Range>(__range));1648  }1649#  endif1650 1651#  if _LIBCPP_STD_VER >= 141652  template <class _InputIterator>1653  _LIBCPP_HIDE_FROM_ABI multimap(_InputIterator __f, _InputIterator __l, const allocator_type& __a)1654      : multimap(__f, __l, key_compare(), __a) {}1655#  endif1656 1657#  if _LIBCPP_STD_VER >= 231658  template <_ContainerCompatibleRange<value_type> _Range>1659  _LIBCPP_HIDE_FROM_ABI multimap(from_range_t, _Range&& __range, const allocator_type& __a)1660      : multimap(from_range, std::forward<_Range>(__range), key_compare(), __a) {}1661#  endif1662 1663  _LIBCPP_HIDE_FROM_ABI multimap(const multimap& __m) = default;1664 1665  _LIBCPP_HIDE_FROM_ABI multimap& operator=(const multimap& __m) = default;1666 1667#  ifndef _LIBCPP_CXX03_LANG1668 1669  _LIBCPP_HIDE_FROM_ABI multimap(multimap&& __m) = default;1670 1671  _LIBCPP_HIDE_FROM_ABI multimap(multimap&& __m, const allocator_type& __a) : __tree_(std::move(__m.__tree_), __a) {}1672 1673  _LIBCPP_HIDE_FROM_ABI multimap& operator=(multimap&& __m) = default;1674 1675  _LIBCPP_HIDE_FROM_ABI multimap(initializer_list<value_type> __il, const key_compare& __comp = key_compare())1676      : __tree_(__vc(__comp)) {1677    insert(__il.begin(), __il.end());1678  }1679 1680  _LIBCPP_HIDE_FROM_ABI1681  multimap(initializer_list<value_type> __il, const key_compare& __comp, const allocator_type& __a)1682      : __tree_(__vc(__comp), typename __base::allocator_type(__a)) {1683    insert(__il.begin(), __il.end());1684  }1685 1686#    if _LIBCPP_STD_VER >= 141687  _LIBCPP_HIDE_FROM_ABI multimap(initializer_list<value_type> __il, const allocator_type& __a)1688      : multimap(__il, key_compare(), __a) {}1689#    endif1690 1691  _LIBCPP_HIDE_FROM_ABI multimap& operator=(initializer_list<value_type> __il) {1692    __tree_.__assign_multi(__il.begin(), __il.end());1693    return *this;1694  }1695 1696#  endif // _LIBCPP_CXX03_LANG1697 1698  _LIBCPP_HIDE_FROM_ABI explicit multimap(const allocator_type& __a) : __tree_(typename __base::allocator_type(__a)) {}1699 1700  _LIBCPP_HIDE_FROM_ABI multimap(const multimap& __m, const allocator_type& __a) : __tree_(__m.__tree_, __a) {}1701 1702  _LIBCPP_HIDE_FROM_ABI ~multimap() {1703    static_assert(sizeof(std::__diagnose_non_const_comparator<_Key, _Compare>()), "");1704  }1705 1706  _LIBCPP_HIDE_FROM_ABI iterator begin() _NOEXCEPT { return __tree_.begin(); }1707  _LIBCPP_HIDE_FROM_ABI const_iterator begin() const _NOEXCEPT { return __tree_.begin(); }1708  _LIBCPP_HIDE_FROM_ABI iterator end() _NOEXCEPT { return __tree_.end(); }1709  _LIBCPP_HIDE_FROM_ABI const_iterator end() const _NOEXCEPT { return __tree_.end(); }1710 1711  _LIBCPP_HIDE_FROM_ABI reverse_iterator rbegin() _NOEXCEPT { return reverse_iterator(end()); }1712  _LIBCPP_HIDE_FROM_ABI const_reverse_iterator rbegin() const _NOEXCEPT { return const_reverse_iterator(end()); }1713  _LIBCPP_HIDE_FROM_ABI reverse_iterator rend() _NOEXCEPT { return reverse_iterator(begin()); }1714  _LIBCPP_HIDE_FROM_ABI const_reverse_iterator rend() const _NOEXCEPT { return const_reverse_iterator(begin()); }1715 1716  _LIBCPP_HIDE_FROM_ABI const_iterator cbegin() const _NOEXCEPT { return begin(); }1717  _LIBCPP_HIDE_FROM_ABI const_iterator cend() const _NOEXCEPT { return end(); }1718  _LIBCPP_HIDE_FROM_ABI const_reverse_iterator crbegin() const _NOEXCEPT { return rbegin(); }1719  _LIBCPP_HIDE_FROM_ABI const_reverse_iterator crend() const _NOEXCEPT { return rend(); }1720 1721  [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI bool empty() const _NOEXCEPT { return __tree_.size() == 0; }1722  _LIBCPP_HIDE_FROM_ABI size_type size() const _NOEXCEPT { return __tree_.size(); }1723  _LIBCPP_HIDE_FROM_ABI size_type max_size() const _NOEXCEPT { return __tree_.max_size(); }1724 1725  _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const _NOEXCEPT { return allocator_type(__tree_.__alloc()); }1726  _LIBCPP_HIDE_FROM_ABI key_compare key_comp() const { return __tree_.value_comp().key_comp(); }1727  _LIBCPP_HIDE_FROM_ABI value_compare value_comp() const { return value_compare(__tree_.value_comp().key_comp()); }1728 1729#  ifndef _LIBCPP_CXX03_LANG1730 1731  template <class... _Args>1732  _LIBCPP_HIDE_FROM_ABI iterator emplace(_Args&&... __args) {1733    return __tree_.__emplace_multi(std::forward<_Args>(__args)...);1734  }1735 1736  template <class... _Args>1737  _LIBCPP_HIDE_FROM_ABI iterator emplace_hint(const_iterator __p, _Args&&... __args) {1738    return __tree_.__emplace_hint_multi(__p.__i_, std::forward<_Args>(__args)...);1739  }1740 1741  template <class _Pp, __enable_if_t<is_constructible<value_type, _Pp>::value, int> = 0>1742  _LIBCPP_HIDE_FROM_ABI iterator insert(_Pp&& __p) {1743    return __tree_.__emplace_multi(std::forward<_Pp>(__p));1744  }1745 1746  template <class _Pp, __enable_if_t<is_constructible<value_type, _Pp>::value, int> = 0>1747  _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __pos, _Pp&& __p) {1748    return __tree_.__emplace_hint_multi(__pos.__i_, std::forward<_Pp>(__p));1749  }1750 1751  _LIBCPP_HIDE_FROM_ABI iterator insert(value_type&& __v) { return __tree_.__emplace_multi(std::move(__v)); }1752 1753  _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, value_type&& __v) {1754    return __tree_.__emplace_hint_multi(__p.__i_, std::move(__v));1755  }1756 1757  _LIBCPP_HIDE_FROM_ABI void insert(initializer_list<value_type> __il) { insert(__il.begin(), __il.end()); }1758 1759#  endif // _LIBCPP_CXX03_LANG1760 1761  _LIBCPP_HIDE_FROM_ABI iterator insert(const value_type& __v) { return __tree_.__emplace_multi(__v); }1762 1763  _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, const value_type& __v) {1764    return __tree_.__emplace_hint_multi(__p.__i_, __v);1765  }1766 1767  template <class _InputIterator>1768  _LIBCPP_HIDE_FROM_ABI void insert(_InputIterator __f, _InputIterator __l) {1769    __tree_.__insert_range_multi(__f, __l);1770  }1771 1772#  if _LIBCPP_STD_VER >= 231773  template <_ContainerCompatibleRange<value_type> _Range>1774  _LIBCPP_HIDE_FROM_ABI void insert_range(_Range&& __range) {1775    __tree_.__insert_range_multi(ranges::begin(__range), ranges::end(__range));1776  }1777#  endif1778 1779  _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __p) { return __tree_.erase(__p.__i_); }1780  _LIBCPP_HIDE_FROM_ABI iterator erase(iterator __p) { return __tree_.erase(__p.__i_); }1781  _LIBCPP_HIDE_FROM_ABI size_type erase(const key_type& __k) { return __tree_.__erase_multi(__k); }1782  _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __f, const_iterator __l) {1783    return __tree_.erase(__f.__i_, __l.__i_);1784  }1785 1786#  if _LIBCPP_STD_VER >= 171787  _LIBCPP_HIDE_FROM_ABI iterator insert(node_type&& __nh) {1788    _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(),1789                                        "node_type with incompatible allocator passed to multimap::insert()");1790    return __tree_.template __node_handle_insert_multi<node_type>(std::move(__nh));1791  }1792  _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __hint, node_type&& __nh) {1793    _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(),1794                                        "node_type with incompatible allocator passed to multimap::insert()");1795    return __tree_.template __node_handle_insert_multi<node_type>(__hint.__i_, std::move(__nh));1796  }1797  _LIBCPP_HIDE_FROM_ABI node_type extract(key_type const& __key) {1798    return __tree_.template __node_handle_extract<node_type>(__key);1799  }1800  _LIBCPP_HIDE_FROM_ABI node_type extract(const_iterator __it) {1801    return __tree_.template __node_handle_extract<node_type>(__it.__i_);1802  }1803  template <class _Compare2>1804  _LIBCPP_HIDE_FROM_ABI void merge(multimap<key_type, mapped_type, _Compare2, allocator_type>& __source) {1805    _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(1806        __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");1807    return __tree_.__node_handle_merge_multi(__source.__tree_);1808  }1809  template <class _Compare2>1810  _LIBCPP_HIDE_FROM_ABI void merge(multimap<key_type, mapped_type, _Compare2, allocator_type>&& __source) {1811    _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(1812        __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");1813    return __tree_.__node_handle_merge_multi(__source.__tree_);1814  }1815  template <class _Compare2>1816  _LIBCPP_HIDE_FROM_ABI void merge(map<key_type, mapped_type, _Compare2, allocator_type>& __source) {1817    _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(1818        __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");1819    return __tree_.__node_handle_merge_multi(__source.__tree_);1820  }1821  template <class _Compare2>1822  _LIBCPP_HIDE_FROM_ABI void merge(map<key_type, mapped_type, _Compare2, allocator_type>&& __source) {1823    _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(1824        __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");1825    return __tree_.__node_handle_merge_multi(__source.__tree_);1826  }1827#  endif1828 1829  _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT { __tree_.clear(); }1830 1831  _LIBCPP_HIDE_FROM_ABI void swap(multimap& __m) _NOEXCEPT_(__is_nothrow_swappable_v<__base>) {1832    __tree_.swap(__m.__tree_);1833  }1834 1835  _LIBCPP_HIDE_FROM_ABI iterator find(const key_type& __k) { return __tree_.find(__k); }1836  _LIBCPP_HIDE_FROM_ABI const_iterator find(const key_type& __k) const { return __tree_.find(__k); }1837#  if _LIBCPP_STD_VER >= 141838  template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>1839  _LIBCPP_HIDE_FROM_ABI iterator find(const _K2& __k) {1840    return __tree_.find(__k);1841  }1842  template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>1843  _LIBCPP_HIDE_FROM_ABI const_iterator find(const _K2& __k) const {1844    return __tree_.find(__k);1845  }1846#  endif1847 1848  _LIBCPP_HIDE_FROM_ABI size_type count(const key_type& __k) const { return __tree_.__count_multi(__k); }1849#  if _LIBCPP_STD_VER >= 141850  template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>1851  _LIBCPP_HIDE_FROM_ABI size_type count(const _K2& __k) const {1852    return __tree_.__count_multi(__k);1853  }1854#  endif1855 1856#  if _LIBCPP_STD_VER >= 201857  _LIBCPP_HIDE_FROM_ABI bool contains(const key_type& __k) const { return find(__k) != end(); }1858  template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>1859  _LIBCPP_HIDE_FROM_ABI bool contains(const _K2& __k) const {1860    return find(__k) != end();1861  }1862#  endif // _LIBCPP_STD_VER >= 201863 1864  _LIBCPP_HIDE_FROM_ABI iterator lower_bound(const key_type& __k) { return __tree_.__lower_bound_multi(__k); }1865 1866  _LIBCPP_HIDE_FROM_ABI const_iterator lower_bound(const key_type& __k) const {1867    return __tree_.__lower_bound_multi(__k);1868  }1869 1870#  if _LIBCPP_STD_VER >= 141871  template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>1872  _LIBCPP_HIDE_FROM_ABI iterator lower_bound(const _K2& __k) {1873    return __tree_.__lower_bound_multi(__k);1874  }1875 1876  template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>1877  _LIBCPP_HIDE_FROM_ABI const_iterator lower_bound(const _K2& __k) const {1878    return __tree_.__lower_bound_multi(__k);1879  }1880#  endif1881 1882  _LIBCPP_HIDE_FROM_ABI iterator upper_bound(const key_type& __k) { return __tree_.__upper_bound_multi(__k); }1883 1884  _LIBCPP_HIDE_FROM_ABI const_iterator upper_bound(const key_type& __k) const {1885    return __tree_.__upper_bound_multi(__k);1886  }1887 1888#  if _LIBCPP_STD_VER >= 141889  template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>1890  _LIBCPP_HIDE_FROM_ABI iterator upper_bound(const _K2& __k) {1891    return __tree_.__upper_bound_multi(__k);1892  }1893  template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>1894  _LIBCPP_HIDE_FROM_ABI const_iterator upper_bound(const _K2& __k) const {1895    return __tree_.__upper_bound_multi(__k);1896  }1897#  endif1898 1899  _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const key_type& __k) {1900    return __tree_.__equal_range_multi(__k);1901  }1902  _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const key_type& __k) const {1903    return __tree_.__equal_range_multi(__k);1904  }1905#  if _LIBCPP_STD_VER >= 141906  template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>1907  _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const _K2& __k) {1908    return __tree_.__equal_range_multi(__k);1909  }1910  template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>1911  _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const _K2& __k) const {1912    return __tree_.__equal_range_multi(__k);1913  }1914#  endif1915 1916private:1917  typedef typename __base::__node __node;1918  typedef typename __base::__node_allocator __node_allocator;1919  typedef typename __base::__node_pointer __node_pointer;1920 1921  typedef __map_node_destructor<__node_allocator> _Dp;1922  typedef unique_ptr<__node, _Dp> __node_holder;1923};1924 1925#  if _LIBCPP_STD_VER >= 171926template <class _InputIterator,1927          class _Compare   = less<__iter_key_type<_InputIterator>>,1928          class _Allocator = allocator<__iter_to_alloc_type<_InputIterator>>,1929          class            = enable_if_t<__has_input_iterator_category<_InputIterator>::value, void>,1930          class            = enable_if_t<!__is_allocator_v<_Compare>>,1931          class            = enable_if_t<__is_allocator_v<_Allocator>>>1932multimap(_InputIterator, _InputIterator, _Compare = _Compare(), _Allocator = _Allocator())1933    -> multimap<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>, _Compare, _Allocator>;1934 1935#    if _LIBCPP_STD_VER >= 231936template <ranges::input_range _Range,1937          class _Compare   = less<__range_key_type<_Range>>,1938          class _Allocator = allocator<__range_to_alloc_type<_Range>>,1939          class            = enable_if_t<!__is_allocator_v<_Compare>>,1940          class            = enable_if_t<__is_allocator_v<_Allocator>>>1941multimap(from_range_t, _Range&&, _Compare = _Compare(), _Allocator = _Allocator())1942    -> multimap<__range_key_type<_Range>, __range_mapped_type<_Range>, _Compare, _Allocator>;1943#    endif1944 1945template <class _Key,1946          class _Tp,1947          class _Compare   = less<remove_const_t<_Key>>,1948          class _Allocator = allocator<pair<const _Key, _Tp>>,1949          class            = enable_if_t<!__is_allocator_v<_Compare>>,1950          class            = enable_if_t<__is_allocator_v<_Allocator>>>1951multimap(initializer_list<pair<_Key, _Tp>>, _Compare = _Compare(), _Allocator = _Allocator())1952    -> multimap<remove_const_t<_Key>, _Tp, _Compare, _Allocator>;1953 1954template <class _InputIterator,1955          class _Allocator,1956          class = enable_if_t<__has_input_iterator_category<_InputIterator>::value, void>,1957          class = enable_if_t<__is_allocator_v<_Allocator>>>1958multimap(_InputIterator, _InputIterator, _Allocator)1959    -> multimap<__iter_key_type<_InputIterator>,1960                __iter_mapped_type<_InputIterator>,1961                less<__iter_key_type<_InputIterator>>,1962                _Allocator>;1963 1964#    if _LIBCPP_STD_VER >= 231965template <ranges::input_range _Range, class _Allocator, class = enable_if_t<__is_allocator_v<_Allocator>>>1966multimap(from_range_t, _Range&&, _Allocator)1967    -> multimap<__range_key_type<_Range>, __range_mapped_type<_Range>, less<__range_key_type<_Range>>, _Allocator>;1968#    endif1969 1970template <class _Key, class _Tp, class _Allocator, class = enable_if_t<__is_allocator_v<_Allocator>>>1971multimap(initializer_list<pair<_Key, _Tp>>, _Allocator)1972    -> multimap<remove_const_t<_Key>, _Tp, less<remove_const_t<_Key>>, _Allocator>;1973#  endif1974 1975template <class _Key, class _Tp, class _Compare, class _Allocator>1976inline _LIBCPP_HIDE_FROM_ABI bool1977operator==(const multimap<_Key, _Tp, _Compare, _Allocator>& __x, const multimap<_Key, _Tp, _Compare, _Allocator>& __y) {1978  return __x.size() == __y.size() && std::equal(__x.begin(), __x.end(), __y.begin());1979}1980 1981#  if _LIBCPP_STD_VER <= 171982 1983template <class _Key, class _Tp, class _Compare, class _Allocator>1984inline _LIBCPP_HIDE_FROM_ABI bool1985operator<(const multimap<_Key, _Tp, _Compare, _Allocator>& __x, const multimap<_Key, _Tp, _Compare, _Allocator>& __y) {1986  return std::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());1987}1988 1989template <class _Key, class _Tp, class _Compare, class _Allocator>1990inline _LIBCPP_HIDE_FROM_ABI bool1991operator!=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x, const multimap<_Key, _Tp, _Compare, _Allocator>& __y) {1992  return !(__x == __y);1993}1994 1995template <class _Key, class _Tp, class _Compare, class _Allocator>1996inline _LIBCPP_HIDE_FROM_ABI bool1997operator>(const multimap<_Key, _Tp, _Compare, _Allocator>& __x, const multimap<_Key, _Tp, _Compare, _Allocator>& __y) {1998  return __y < __x;1999}2000 2001template <class _Key, class _Tp, class _Compare, class _Allocator>2002inline _LIBCPP_HIDE_FROM_ABI bool2003operator>=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x, const multimap<_Key, _Tp, _Compare, _Allocator>& __y) {2004  return !(__x < __y);2005}2006 2007template <class _Key, class _Tp, class _Compare, class _Allocator>2008inline _LIBCPP_HIDE_FROM_ABI bool2009operator<=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x, const multimap<_Key, _Tp, _Compare, _Allocator>& __y) {2010  return !(__y < __x);2011}2012 2013#  else // #if _LIBCPP_STD_VER <= 172014 2015template <class _Key, class _Tp, class _Compare, class _Allocator>2016_LIBCPP_HIDE_FROM_ABI __synth_three_way_result<pair<const _Key, _Tp>>2017operator<=>(const multimap<_Key, _Tp, _Compare, _Allocator>& __x,2018            const multimap<_Key, _Tp, _Compare, _Allocator>& __y) {2019  return std::lexicographical_compare_three_way(__x.begin(), __x.end(), __y.begin(), __y.end(), __synth_three_way);2020}2021 2022#  endif // #if _LIBCPP_STD_VER <= 172023 2024template <class _Key, class _Tp, class _Compare, class _Allocator>2025inline _LIBCPP_HIDE_FROM_ABI void2026swap(multimap<_Key, _Tp, _Compare, _Allocator>& __x, multimap<_Key, _Tp, _Compare, _Allocator>& __y)2027    _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) {2028  __x.swap(__y);2029}2030 2031#  if _LIBCPP_STD_VER >= 202032template <class _Key, class _Tp, class _Compare, class _Allocator, class _Predicate>2033inline _LIBCPP_HIDE_FROM_ABI typename multimap<_Key, _Tp, _Compare, _Allocator>::size_type2034erase_if(multimap<_Key, _Tp, _Compare, _Allocator>& __c, _Predicate __pred) {2035  return std::__libcpp_erase_if_container(__c, __pred);2036}2037#  endif2038 2039template <class _Key, class _Tp, class _Compare, class _Allocator>2040struct __container_traits<multimap<_Key, _Tp, _Compare, _Allocator> > {2041  // http://eel.is/c++draft/associative.reqmts.except#22042  // For associative containers, if an exception is thrown by any operation from within2043  // an insert or emplace function inserting a single element, the insertion has no effect.2044  static _LIBCPP_CONSTEXPR const bool __emplacement_has_strong_exception_safety_guarantee = true;2045 2046  static _LIBCPP_CONSTEXPR const bool __reservable = false;2047};2048 2049_LIBCPP_END_NAMESPACE_STD2050 2051#  if _LIBCPP_STD_VER >= 172052_LIBCPP_BEGIN_NAMESPACE_STD2053namespace pmr {2054template <class _KeyT, class _ValueT, class _CompareT = std::less<_KeyT>>2055using map _LIBCPP_AVAILABILITY_PMR =2056    std::map<_KeyT, _ValueT, _CompareT, polymorphic_allocator<std::pair<const _KeyT, _ValueT>>>;2057 2058template <class _KeyT, class _ValueT, class _CompareT = std::less<_KeyT>>2059using multimap _LIBCPP_AVAILABILITY_PMR =2060    std::multimap<_KeyT, _ValueT, _CompareT, polymorphic_allocator<std::pair<const _KeyT, _ValueT>>>;2061} // namespace pmr2062_LIBCPP_END_NAMESPACE_STD2063#  endif2064 2065_LIBCPP_POP_MACROS2066 2067#  if !defined(_LIBCPP_REMOVE_TRANSITIVE_INCLUDES) && _LIBCPP_STD_VER <= 202068#    include <concepts>2069#    include <cstdlib>2070#    include <functional>2071#    include <iterator>2072#    include <type_traits>2073#    include <utility>2074#  endif2075#endif // __cplusplus < 201103L && defined(_LIBCPP_USE_FROZEN_CXX03_HEADERS)2076 2077#endif // _LIBCPP_MAP2078