LCOV - code coverage report
Current view: top level - v1 - map (source / functions) Coverage Total Hit
Test: vrml_testfiles.info Lines: 82.0 % 50 41
Test Date: 2024-03-08 16:12:17 Functions: 64.7 % 85 55

            Line data    Source code
       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-exception
       7              : //
       8              : //===----------------------------------------------------------------------===//
       9              : 
      10              : #ifndef _LIBCPP_MAP
      11              : #define _LIBCPP_MAP
      12              : 
      13              : /*
      14              : 
      15              :     map synopsis
      16              : 
      17              : namespace std
      18              : {
      19              : 
      20              : template <class Key, class T, class Compare = less<Key>,
      21              :           class Allocator = allocator<pair<const Key, T>>>
      22              : class map
      23              : {
      24              : public:
      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++17
      43              :     typedef INSERT_RETURN_TYPE<iterator, node_type>  insert_return_type;     // C++17
      44              : 
      45              :     class value_compare
      46              :     {
      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++20
      54              :         typedef value_type first_argument_type;  // deprecated in C++17, removed in C++20
      55              :         typedef value_type second_argument_type;  // deprecated in C++17, removed in C++20
      56              :         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              :     map(const map& m);
      74              :     map(map&& m)
      75              :         noexcept(
      76              :             is_nothrow_move_constructible<allocator_type>::value &&
      77              :             is_nothrow_move_constructible<key_compare>::value);
      78              :     explicit map(const allocator_type& a);
      79              :     map(const map& m, const allocator_type& a);
      80              :     map(map&& m, const allocator_type& a);
      81              :     map(initializer_list<value_type> il, const key_compare& comp = key_compare());
      82              :     map(initializer_list<value_type> il, const key_compare& comp, const allocator_type& a);
      83              :     template <class InputIterator>
      84              :         map(InputIterator first, InputIterator last, const allocator_type& a)
      85              :             : map(first, last, Compare(), a) {}  // C++14
      86              :     map(initializer_list<value_type> il, const allocator_type& a)
      87              :         : map(il, Compare(), a) {}  // C++14
      88              :    ~map();
      89              : 
      90              :     map& operator=(const map& m);
      91              :     map& operator=(map&& m)
      92              :         noexcept(
      93              :             allocator_type::propagate_on_container_move_assignment::value &&
      94              :             is_nothrow_move_assignable<allocator_type>::value &&
      95              :             is_nothrow_move_assignable<key_compare>::value);
      96              :     map& operator=(initializer_list<value_type> il);
      97              : 
      98              :     // iterators:
      99              :           iterator begin() noexcept;
     100              :     const_iterator begin() const noexcept;
     101              :           iterator end() noexcept;
     102              :     const_iterator end()   const noexcept;
     103              : 
     104              :           reverse_iterator rbegin() noexcept;
     105              :     const_reverse_iterator rbegin() const noexcept;
     106              :           reverse_iterator rend() noexcept;
     107              :     const_reverse_iterator rend()   const noexcept;
     108              : 
     109              :     const_iterator         cbegin()  const noexcept;
     110              :     const_iterator         cend()    const noexcept;
     111              :     const_reverse_iterator crbegin() const noexcept;
     112              :     const_reverse_iterator crend()   const noexcept;
     113              : 
     114              :     // capacity:
     115              :     bool      empty()    const noexcept;
     116              :     size_type size()     const noexcept;
     117              :     size_type max_size() const noexcept;
     118              : 
     119              :     // element access:
     120              :     mapped_type& operator[](const key_type& k);
     121              :     mapped_type& operator[](key_type&& k);
     122              : 
     123              :           mapped_type& at(const key_type& k);
     124              :     const mapped_type& at(const key_type& k) const;
     125              : 
     126              :     // modifiers:
     127              :     template <class... Args>
     128              :         pair<iterator, bool> emplace(Args&&... args);
     129              :     template <class... Args>
     130              :         iterator emplace_hint(const_iterator position, Args&&... args);
     131              :     pair<iterator, bool> insert(const value_type& v);
     132              :     pair<iterator, bool> insert(      value_type&& v);                                // C++17
     133              :     template <class P>
     134              :         pair<iterator, bool> insert(P&& p);
     135              :     iterator insert(const_iterator position, const value_type& v);
     136              :     iterator insert(const_iterator position,       value_type&& v);                   // C++17
     137              :     template <class P>
     138              :         iterator insert(const_iterator position, P&& p);
     139              :     template <class InputIterator>
     140              :         void insert(InputIterator first, InputIterator last);
     141              :     void insert(initializer_list<value_type> il);
     142              : 
     143              :     node_type extract(const_iterator position);                                       // C++17
     144              :     node_type extract(const key_type& x);                                             // C++17
     145              :     insert_return_type insert(node_type&& nh);                                        // C++17
     146              :     iterator insert(const_iterator hint, node_type&& nh);                             // C++17
     147              : 
     148              :     template <class... Args>
     149              :         pair<iterator, bool> try_emplace(const key_type& k, Args&&... args);          // C++17
     150              :     template <class... Args>
     151              :         pair<iterator, bool> try_emplace(key_type&& k, Args&&... args);               // C++17
     152              :     template <class... Args>
     153              :         iterator try_emplace(const_iterator hint, const key_type& k, Args&&... args); // C++17
     154              :     template <class... Args>
     155              :         iterator try_emplace(const_iterator hint, key_type&& k, Args&&... args);      // C++17
     156              :     template <class M>
     157              :         pair<iterator, bool> insert_or_assign(const key_type& k, M&& obj);            // C++17
     158              :     template <class M>
     159              :         pair<iterator, bool> insert_or_assign(key_type&& k, M&& obj);                 // C++17
     160              :     template <class M>
     161              :         iterator insert_or_assign(const_iterator hint, const key_type& k, M&& obj);   // C++17
     162              :     template <class M>
     163              :         iterator insert_or_assign(const_iterator hint, key_type&& k, M&& obj);        // C++17
     164              : 
     165              :     iterator  erase(const_iterator position);
     166              :     iterator  erase(iterator position); // C++14
     167              :     size_type erase(const key_type& k);
     168              :     iterator  erase(const_iterator first, const_iterator last);
     169              :     void clear() noexcept;
     170              : 
     171              :     template<class C2>
     172              :       void merge(map<Key, T, C2, Allocator>& source);         // C++17
     173              :     template<class C2>
     174              :       void merge(map<Key, T, C2, Allocator>&& source);        // C++17
     175              :     template<class C2>
     176              :       void merge(multimap<Key, T, C2, Allocator>& source);    // C++17
     177              :     template<class C2>
     178              :       void merge(multimap<Key, T, C2, Allocator>&& source);   // C++17
     179              : 
     180              :     void swap(map& m)
     181              :         noexcept(allocator_traits<allocator_type>::is_always_equal::value &&
     182              :             is_nothrow_swappable<key_compare>::value); // C++17
     183              : 
     184              :     // observers:
     185              :     allocator_type get_allocator() const noexcept;
     186              :     key_compare    key_comp()      const;
     187              :     value_compare  value_comp()    const;
     188              : 
     189              :     // map operations:
     190              :           iterator find(const key_type& k);
     191              :     const_iterator find(const key_type& k) const;
     192              :     template<typename K>
     193              :         iterator find(const K& x);              // C++14
     194              :     template<typename K>
     195              :         const_iterator find(const K& x) const;  // C++14
     196              : 
     197              :     template<typename K>
     198              :       size_type count(const K& x) const;        // C++14
     199              :     size_type      count(const key_type& k) const;
     200              : 
     201              :     bool           contains(const key_type& x) const;  // C++20
     202              :     template<class K> bool contains(const K& x) const; // C++20
     203              : 
     204              :           iterator lower_bound(const key_type& k);
     205              :     const_iterator lower_bound(const key_type& k) const;
     206              :     template<typename K>
     207              :         iterator lower_bound(const K& x);              // C++14
     208              :     template<typename K>
     209              :         const_iterator lower_bound(const K& x) const;  // C++14
     210              : 
     211              :           iterator upper_bound(const key_type& k);
     212              :     const_iterator upper_bound(const key_type& k) const;
     213              :     template<typename K>
     214              :         iterator upper_bound(const K& x);              // C++14
     215              :     template<typename K>
     216              :         const_iterator upper_bound(const K& x) const;  // C++14
     217              : 
     218              :     pair<iterator,iterator>             equal_range(const key_type& k);
     219              :     pair<const_iterator,const_iterator> equal_range(const key_type& k) const;
     220              :     template<typename K>
     221              :         pair<iterator,iterator>             equal_range(const K& x);        // C++14
     222              :     template<typename K>
     223              :         pair<const_iterator,const_iterator> equal_range(const K& x) const;  // C++14
     224              : };
     225              : 
     226              : template <class InputIterator,
     227              :       class Compare = less<iter_key_t<InputIterator>>,
     228              :       class Allocator = allocator<iter_to_alloc_t<InputIterator>>>
     229              : map(InputIterator, InputIterator, Compare = Compare(), Allocator = Allocator())
     230              :   -> map<iter_key_t<InputIterator>, iter_val_t<InputIterator>, Compare, Allocator>; // C++17
     231              : 
     232              : template<class Key, class T, class Compare = less<Key>,
     233              :     class Allocator = allocator<pair<const Key, T>>>
     234              : map(initializer_list<pair<const Key, T>>, Compare = Compare(), Allocator = Allocator())
     235              :   -> map<Key, T, Compare, Allocator>; // C++17
     236              : 
     237              : template <class InputIterator, class Allocator>
     238              : map(InputIterator, InputIterator, Allocator)
     239              :   -> map<iter_key_t<InputIterator>, iter_val_t<InputIterator>, less<iter_key_t<InputIterator>>,
     240              :     Allocator>; // C++17
     241              : 
     242              : template<class Key, class T, class Allocator>
     243              : map(initializer_list<pair<const Key, T>>, Allocator) -> map<Key, T, less<Key>, Allocator>; // C++17
     244              : 
     245              : template <class Key, class T, class Compare, class Allocator>
     246              : bool
     247              : operator==(const map<Key, T, Compare, Allocator>& x,
     248              :            const map<Key, T, Compare, Allocator>& y);
     249              : 
     250              : template <class Key, class T, class Compare, class Allocator>
     251              : bool
     252              : operator< (const map<Key, T, Compare, Allocator>& x,
     253              :            const map<Key, T, Compare, Allocator>& y);
     254              : 
     255              : template <class Key, class T, class Compare, class Allocator>
     256              : bool
     257              : operator!=(const map<Key, T, Compare, Allocator>& x,
     258              :            const map<Key, T, Compare, Allocator>& y);
     259              : 
     260              : template <class Key, class T, class Compare, class Allocator>
     261              : bool
     262              : operator> (const map<Key, T, Compare, Allocator>& x,
     263              :            const map<Key, T, Compare, Allocator>& y);
     264              : 
     265              : template <class Key, class T, class Compare, class Allocator>
     266              : bool
     267              : operator>=(const map<Key, T, Compare, Allocator>& x,
     268              :            const map<Key, T, Compare, Allocator>& y);
     269              : 
     270              : template <class Key, class T, class Compare, class Allocator>
     271              : bool
     272              : operator<=(const map<Key, T, Compare, Allocator>& x,
     273              :            const map<Key, T, Compare, Allocator>& y);
     274              : 
     275              : // specialized algorithms:
     276              : template <class Key, class T, class Compare, class Allocator>
     277              : void
     278              : swap(map<Key, T, Compare, Allocator>& x, map<Key, T, Compare, Allocator>& y)
     279              :     noexcept(noexcept(x.swap(y)));
     280              : 
     281              : template <class Key, class T, class Compare, class Allocator, class Predicate>
     282              : typename map<Key, T, Compare, Allocator>::size_type
     283              : erase_if(map<Key, T, Compare, Allocator>& c, Predicate pred);  // C++20
     284              : 
     285              : 
     286              : template <class Key, class T, class Compare = less<Key>,
     287              :           class Allocator = allocator<pair<const Key, T>>>
     288              : class multimap
     289              : {
     290              : public:
     291              :     // types:
     292              :     typedef Key                                      key_type;
     293              :     typedef T                                        mapped_type;
     294              :     typedef pair<const key_type,mapped_type>         value_type;
     295              :     typedef Compare                                  key_compare;
     296              :     typedef Allocator                                allocator_type;
     297              :     typedef typename allocator_type::reference       reference;
     298              :     typedef typename allocator_type::const_reference const_reference;
     299              :     typedef typename allocator_type::size_type       size_type;
     300              :     typedef typename allocator_type::difference_type difference_type;
     301              :     typedef typename allocator_type::pointer         pointer;
     302              :     typedef typename allocator_type::const_pointer   const_pointer;
     303              : 
     304              :     typedef implementation-defined                   iterator;
     305              :     typedef implementation-defined                   const_iterator;
     306              :     typedef std::reverse_iterator<iterator>          reverse_iterator;
     307              :     typedef std::reverse_iterator<const_iterator>    const_reverse_iterator;
     308              :     typedef unspecified                              node_type;              // C++17
     309              : 
     310              :     class value_compare
     311              :     {
     312              :         friend class multimap;
     313              :     protected:
     314              :         key_compare comp;
     315              :         value_compare(key_compare c);
     316              :     public:
     317              :         typedef bool result_type;  // deprecated in C++17, removed in C++20
     318              :         typedef value_type first_argument_type;  // deprecated in C++17, removed in C++20
     319              :         typedef value_type second_argument_type;  // deprecated in C++17, removed in C++20
     320              :         bool operator()(const value_type& x, const value_type& y) const;
     321              :     };
     322              : 
     323              :     // construct/copy/destroy:
     324              :     multimap()
     325              :         noexcept(
     326              :             is_nothrow_default_constructible<allocator_type>::value &&
     327              :             is_nothrow_default_constructible<key_compare>::value &&
     328              :             is_nothrow_copy_constructible<key_compare>::value);
     329              :     explicit multimap(const key_compare& comp);
     330              :     multimap(const key_compare& comp, const allocator_type& a);
     331              :     template <class InputIterator>
     332              :         multimap(InputIterator first, InputIterator last, const key_compare& comp);
     333              :     template <class InputIterator>
     334              :         multimap(InputIterator first, InputIterator last, const key_compare& comp,
     335              :                  const allocator_type& a);
     336              :     multimap(const multimap& m);
     337              :     multimap(multimap&& m)
     338              :         noexcept(
     339              :             is_nothrow_move_constructible<allocator_type>::value &&
     340              :             is_nothrow_move_constructible<key_compare>::value);
     341              :     explicit multimap(const allocator_type& a);
     342              :     multimap(const multimap& m, const allocator_type& a);
     343              :     multimap(multimap&& m, const allocator_type& a);
     344              :     multimap(initializer_list<value_type> il, const key_compare& comp = key_compare());
     345              :     multimap(initializer_list<value_type> il, const key_compare& comp,
     346              :              const allocator_type& a);
     347              :     template <class InputIterator>
     348              :         multimap(InputIterator first, InputIterator last, const allocator_type& a)
     349              :             : multimap(first, last, Compare(), a) {} // C++14
     350              :     multimap(initializer_list<value_type> il, const allocator_type& a)
     351              :         : multimap(il, Compare(), a) {} // C++14
     352              :     ~multimap();
     353              : 
     354              :     multimap& operator=(const multimap& m);
     355              :     multimap& operator=(multimap&& m)
     356              :         noexcept(
     357              :             allocator_type::propagate_on_container_move_assignment::value &&
     358              :             is_nothrow_move_assignable<allocator_type>::value &&
     359              :             is_nothrow_move_assignable<key_compare>::value);
     360              :     multimap& operator=(initializer_list<value_type> il);
     361              : 
     362              :     // iterators:
     363              :           iterator begin() noexcept;
     364              :     const_iterator begin() const noexcept;
     365              :           iterator end() noexcept;
     366              :     const_iterator end()   const noexcept;
     367              : 
     368              :           reverse_iterator rbegin() noexcept;
     369              :     const_reverse_iterator rbegin() const noexcept;
     370              :           reverse_iterator rend() noexcept;
     371              :     const_reverse_iterator rend()   const noexcept;
     372              : 
     373              :     const_iterator         cbegin()  const noexcept;
     374              :     const_iterator         cend()    const noexcept;
     375              :     const_reverse_iterator crbegin() const noexcept;
     376              :     const_reverse_iterator crend()   const noexcept;
     377              : 
     378              :     // capacity:
     379              :     bool      empty()    const noexcept;
     380              :     size_type size()     const noexcept;
     381              :     size_type max_size() const noexcept;
     382              : 
     383              :     // modifiers:
     384              :     template <class... Args>
     385              :         iterator emplace(Args&&... args);
     386              :     template <class... Args>
     387              :         iterator emplace_hint(const_iterator position, Args&&... args);
     388              :     iterator insert(const value_type& v);
     389              :     iterator insert(      value_type&& v);                                            // C++17
     390              :     template <class P>
     391              :         iterator insert(P&& p);
     392              :     iterator insert(const_iterator position, const value_type& v);
     393              :     iterator insert(const_iterator position,       value_type&& v);                   // C++17
     394              :     template <class P>
     395              :         iterator insert(const_iterator position, P&& p);
     396              :     template <class InputIterator>
     397              :         void insert(InputIterator first, InputIterator last);
     398              :     void insert(initializer_list<value_type> il);
     399              : 
     400              :     node_type extract(const_iterator position);                                       // C++17
     401              :     node_type extract(const key_type& x);                                             // C++17
     402              :     iterator insert(node_type&& nh);                                                  // C++17
     403              :     iterator insert(const_iterator hint, node_type&& nh);                             // C++17
     404              : 
     405              :     iterator  erase(const_iterator position);
     406              :     iterator  erase(iterator position); // C++14
     407              :     size_type erase(const key_type& k);
     408              :     iterator  erase(const_iterator first, const_iterator last);
     409              :     void clear() noexcept;
     410              : 
     411              :     template<class C2>
     412              :       void merge(multimap<Key, T, C2, Allocator>& source);    // C++17
     413              :     template<class C2>
     414              :       void merge(multimap<Key, T, C2, Allocator>&& source);   // C++17
     415              :     template<class C2>
     416              :       void merge(map<Key, T, C2, Allocator>& source);         // C++17
     417              :     template<class C2>
     418              :       void merge(map<Key, T, C2, Allocator>&& source);        // C++17
     419              : 
     420              :     void swap(multimap& m)
     421              :         noexcept(allocator_traits<allocator_type>::is_always_equal::value &&
     422              :             is_nothrow_swappable<key_compare>::value); // C++17
     423              : 
     424              :     // observers:
     425              :     allocator_type get_allocator() const noexcept;
     426              :     key_compare    key_comp()      const;
     427              :     value_compare  value_comp()    const;
     428              : 
     429              :     // map operations:
     430              :           iterator find(const key_type& k);
     431              :     const_iterator find(const key_type& k) const;
     432              :     template<typename K>
     433              :         iterator find(const K& x);              // C++14
     434              :     template<typename K>
     435              :         const_iterator find(const K& x) const;  // C++14
     436              : 
     437              :     template<typename K>
     438              :       size_type count(const K& x) const;        // C++14
     439              :     size_type      count(const key_type& k) const;
     440              : 
     441              :     bool           contains(const key_type& x) const;  // C++20
     442              :     template<class K> bool contains(const K& x) const; // C++20
     443              : 
     444              :           iterator lower_bound(const key_type& k);
     445              :     const_iterator lower_bound(const key_type& k) const;
     446              :     template<typename K>
     447              :         iterator lower_bound(const K& x);              // C++14
     448              :     template<typename K>
     449              :         const_iterator lower_bound(const K& x) const;  // C++14
     450              : 
     451              :           iterator upper_bound(const key_type& k);
     452              :     const_iterator upper_bound(const key_type& k) const;
     453              :     template<typename K>
     454              :         iterator upper_bound(const K& x);              // C++14
     455              :     template<typename K>
     456              :         const_iterator upper_bound(const K& x) const;  // C++14
     457              : 
     458              :     pair<iterator,iterator>             equal_range(const key_type& k);
     459              :     pair<const_iterator,const_iterator> equal_range(const key_type& k) const;
     460              :     template<typename K>
     461              :         pair<iterator,iterator>             equal_range(const K& x);        // C++14
     462              :     template<typename K>
     463              :         pair<const_iterator,const_iterator> equal_range(const K& x) const;  // C++14
     464              : };
     465              : 
     466              : template <class InputIterator,
     467              :       class Compare = less<iter_key_t<InputIterator>>,
     468              :       class Allocator = allocator<iter_to_alloc_t<InputIterator>>>
     469              : multimap(InputIterator, InputIterator, Compare = Compare(), Allocator = Allocator())
     470              :   -> multimap<iter_key_t<InputIterator>, iter_val_t<InputIterator>, Compare, Allocator>; // C++17
     471              : 
     472              : template<class Key, class T, class Compare = less<Key>,
     473              :     class Allocator = allocator<pair<const Key, T>>>
     474              : multimap(initializer_list<pair<const Key, T>>, Compare = Compare(), Allocator = Allocator())
     475              :   -> multimap<Key, T, Compare, Allocator>; // C++17
     476              : 
     477              : template <class InputIterator, class Allocator>
     478              : multimap(InputIterator, InputIterator, Allocator)
     479              :   -> multimap<iter_key_t<InputIterator>, iter_val_t<InputIterator>,
     480              :     less<iter_key_t<InputIterator>>, Allocator>; // C++17
     481              : 
     482              : template<class Key, class T, class Allocator>
     483              : multimap(initializer_list<pair<const Key, T>>, Allocator)
     484              :   -> multimap<Key, T, less<Key>, Allocator>; // C++17
     485              : 
     486              : template <class Key, class T, class Compare, class Allocator>
     487              : bool
     488              : operator==(const multimap<Key, T, Compare, Allocator>& x,
     489              :            const multimap<Key, T, Compare, Allocator>& y);
     490              : 
     491              : template <class Key, class T, class Compare, class Allocator>
     492              : bool
     493              : operator< (const multimap<Key, T, Compare, Allocator>& x,
     494              :            const multimap<Key, T, Compare, Allocator>& y);
     495              : 
     496              : template <class Key, class T, class Compare, class Allocator>
     497              : bool
     498              : operator!=(const multimap<Key, T, Compare, Allocator>& x,
     499              :            const multimap<Key, T, Compare, Allocator>& y);
     500              : 
     501              : template <class Key, class T, class Compare, class Allocator>
     502              : bool
     503              : operator> (const multimap<Key, T, Compare, Allocator>& x,
     504              :            const multimap<Key, T, Compare, Allocator>& y);
     505              : 
     506              : template <class Key, class T, class Compare, class Allocator>
     507              : bool
     508              : operator>=(const multimap<Key, T, Compare, Allocator>& x,
     509              :            const multimap<Key, T, Compare, Allocator>& y);
     510              : 
     511              : template <class Key, class T, class Compare, class Allocator>
     512              : bool
     513              : operator<=(const multimap<Key, T, Compare, Allocator>& x,
     514              :            const multimap<Key, T, Compare, Allocator>& y);
     515              : 
     516              : // specialized algorithms:
     517              : template <class Key, class T, class Compare, class Allocator>
     518              : void
     519              : swap(multimap<Key, T, Compare, Allocator>& x,
     520              :      multimap<Key, T, Compare, Allocator>& y)
     521              :     noexcept(noexcept(x.swap(y)));
     522              : 
     523              : template <class Key, class T, class Compare, class Allocator, class Predicate>
     524              : typename multimap<Key, T, Compare, Allocator>::size_type
     525              : erase_if(multimap<Key, T, Compare, Allocator>& c, Predicate pred);  // C++20
     526              : 
     527              : }  // std
     528              : 
     529              : */
     530              : 
     531              : #include <__algorithm/equal.h>
     532              : #include <__algorithm/lexicographical_compare.h>
     533              : #include <__assert> // all public C++ headers provide the assertion handler
     534              : #include <__config>
     535              : #include <__functional/binary_function.h>
     536              : #include <__functional/is_transparent.h>
     537              : #include <__functional/operations.h>
     538              : #include <__iterator/erase_if_container.h>
     539              : #include <__iterator/iterator_traits.h>
     540              : #include <__iterator/reverse_iterator.h>
     541              : #include <__memory/allocator.h>
     542              : #include <__memory_resource/polymorphic_allocator.h>
     543              : #include <__node_handle>
     544              : #include <__tree>
     545              : #include <__type_traits/is_allocator.h>
     546              : #include <__utility/forward.h>
     547              : #include <__utility/piecewise_construct.h>
     548              : #include <__utility/swap.h>
     549              : #include <tuple>
     550              : #include <type_traits>
     551              : #include <version>
     552              : 
     553              : // standard-mandated includes
     554              : 
     555              : // [iterator.range]
     556              : #include <__iterator/access.h>
     557              : #include <__iterator/data.h>
     558              : #include <__iterator/empty.h>
     559              : #include <__iterator/reverse_access.h>
     560              : #include <__iterator/size.h>
     561              : 
     562              : // [associative.map.syn]
     563              : #include <compare>
     564              : #include <initializer_list>
     565              : 
     566              : #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
     567              : #  pragma GCC system_header
     568              : #endif
     569              : 
     570              : _LIBCPP_BEGIN_NAMESPACE_STD
     571              : 
     572              : template <class _Key, class _CP, class _Compare,
     573              :           bool = is_empty<_Compare>::value && !__libcpp_is_final<_Compare>::value>
     574              : class __map_value_compare
     575              :     : private _Compare
     576              : {
     577              : public:
     578              :     _LIBCPP_INLINE_VISIBILITY
     579              :     __map_value_compare()
     580              :         _NOEXCEPT_(is_nothrow_default_constructible<_Compare>::value)
     581              :         : _Compare() {}
     582              :     _LIBCPP_INLINE_VISIBILITY
     583           30 :     __map_value_compare(_Compare __c)
     584              :         _NOEXCEPT_(is_nothrow_copy_constructible<_Compare>::value)
     585           30 :         : _Compare(__c) {}
     586              :     _LIBCPP_INLINE_VISIBILITY
     587              :     const _Compare& key_comp() const _NOEXCEPT {return *this;}
     588              :     _LIBCPP_INLINE_VISIBILITY
     589              :     bool operator()(const _CP& __x, const _CP& __y) const
     590              :         {return static_cast<const _Compare&>(*this)(__x.__get_value().first, __y.__get_value().first);}
     591              :     _LIBCPP_INLINE_VISIBILITY
     592        10987 :     bool operator()(const _CP& __x, const _Key& __y) const
     593        10987 :         {return static_cast<const _Compare&>(*this)(__x.__get_value().first, __y);}
     594              :     _LIBCPP_INLINE_VISIBILITY
     595         2715 :     bool operator()(const _Key& __x, const _CP& __y) const
     596         2715 :         {return static_cast<const _Compare&>(*this)(__x, __y.__get_value().first);}
     597              :     void swap(__map_value_compare& __y)
     598              :         _NOEXCEPT_(__is_nothrow_swappable<_Compare>::value)
     599              :     {
     600              :       using _VSTD::swap;
     601              :       swap(static_cast<_Compare&>(*this), static_cast<_Compare&>(__y));
     602              :     }
     603              : 
     604              : #if _LIBCPP_STD_VER > 11
     605              :     template <typename _K2>
     606              :     _LIBCPP_INLINE_VISIBILITY
     607              :     bool operator()(const _K2& __x, const _CP& __y) const
     608              :         {return static_cast<const _Compare&>(*this)(__x, __y.__get_value().first);}
     609              : 
     610              :     template <typename _K2>
     611              :     _LIBCPP_INLINE_VISIBILITY
     612              :     bool operator()(const _CP& __x, const _K2& __y) const
     613              :         {return static_cast<const _Compare&>(*this)(__x.__get_value().first, __y);}
     614              : #endif
     615              : };
     616              : 
     617              : template <class _Key, class _CP, class _Compare>
     618              : class __map_value_compare<_Key, _CP, _Compare, false>
     619              : {
     620              :     _Compare __comp_;
     621              : 
     622              : public:
     623              :     _LIBCPP_INLINE_VISIBILITY
     624              :     __map_value_compare()
     625              :         _NOEXCEPT_(is_nothrow_default_constructible<_Compare>::value)
     626              :         : __comp_() {}
     627              :     _LIBCPP_INLINE_VISIBILITY
     628              :     __map_value_compare(_Compare __c)
     629              :         _NOEXCEPT_(is_nothrow_copy_constructible<_Compare>::value)
     630              :         : __comp_(__c) {}
     631              :     _LIBCPP_INLINE_VISIBILITY
     632              :     const _Compare& key_comp() const _NOEXCEPT {return __comp_;}
     633              : 
     634              :     _LIBCPP_INLINE_VISIBILITY
     635              :     bool operator()(const _CP& __x, const _CP& __y) const
     636              :         {return __comp_(__x.__get_value().first, __y.__get_value().first);}
     637              :     _LIBCPP_INLINE_VISIBILITY
     638              :     bool operator()(const _CP& __x, const _Key& __y) const
     639              :         {return __comp_(__x.__get_value().first, __y);}
     640              :     _LIBCPP_INLINE_VISIBILITY
     641              :     bool operator()(const _Key& __x, const _CP& __y) const
     642              :         {return __comp_(__x, __y.__get_value().first);}
     643              :     void swap(__map_value_compare& __y)
     644              :         _NOEXCEPT_(__is_nothrow_swappable<_Compare>::value)
     645              :     {
     646              :         using _VSTD::swap;
     647              :         swap(__comp_, __y.__comp_);
     648              :     }
     649              : 
     650              : #if _LIBCPP_STD_VER > 11
     651              :     template <typename _K2>
     652              :     _LIBCPP_INLINE_VISIBILITY
     653              :     bool operator()(const _K2& __x, const _CP& __y) const
     654              :         {return __comp_(__x, __y.__get_value().first);}
     655              : 
     656              :     template <typename _K2>
     657              :     _LIBCPP_INLINE_VISIBILITY
     658              :     bool operator()(const _CP& __x, const _K2& __y) const
     659              :         {return __comp_(__x.__get_value().first, __y);}
     660              : #endif
     661              : };
     662              : 
     663              : template <class _Key, class _CP, class _Compare, bool __b>
     664              : inline _LIBCPP_INLINE_VISIBILITY
     665              : void
     666              : swap(__map_value_compare<_Key, _CP, _Compare, __b>& __x,
     667              :      __map_value_compare<_Key, _CP, _Compare, __b>& __y)
     668              :     _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
     669              : {
     670              :     __x.swap(__y);
     671              : }
     672              : 
     673              : template <class _Allocator>
     674              : class __map_node_destructor
     675              : {
     676              :     typedef _Allocator                          allocator_type;
     677              :     typedef allocator_traits<allocator_type>    __alloc_traits;
     678              : 
     679              : public:
     680              :     typedef typename __alloc_traits::pointer    pointer;
     681              : 
     682              : private:
     683              :     allocator_type& __na_;
     684              : 
     685              :     __map_node_destructor& operator=(const __map_node_destructor&);
     686              : 
     687              : public:
     688              :     bool __first_constructed;
     689              :     bool __second_constructed;
     690              : 
     691              :     _LIBCPP_INLINE_VISIBILITY
     692          126 :     explicit __map_node_destructor(allocator_type& __na) _NOEXCEPT
     693           63 :         : __na_(__na),
     694           63 :           __first_constructed(false),
     695           63 :           __second_constructed(false)
     696          126 :         {}
     697              : 
     698              : #ifndef _LIBCPP_CXX03_LANG
     699              :     _LIBCPP_INLINE_VISIBILITY
     700              :     __map_node_destructor(__tree_node_destructor<allocator_type>&& __x) _NOEXCEPT
     701              :         : __na_(__x.__na_),
     702              :           __first_constructed(__x.__value_constructed),
     703              :           __second_constructed(__x.__value_constructed)
     704              :         {
     705              :             __x.__value_constructed = false;
     706              :         }
     707              : #endif // _LIBCPP_CXX03_LANG
     708              : 
     709              :     _LIBCPP_INLINE_VISIBILITY
     710            0 :     void operator()(pointer __p) _NOEXCEPT
     711              :     {
     712            0 :         if (__second_constructed)
     713            0 :             __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.__get_value().second));
     714            0 :         if (__first_constructed)
     715            0 :             __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.__get_value().first));
     716            0 :         if (__p)
     717            0 :             __alloc_traits::deallocate(__na_, __p, 1);
     718            0 :     }
     719              : };
     720              : 
     721              : template <class _Key, class _Tp, class _Compare, class _Allocator>
     722              :     class map;
     723              : template <class _Key, class _Tp, class _Compare, class _Allocator>
     724              :     class multimap;
     725              : template <class _TreeIterator> class __map_const_iterator;
     726              : 
     727              : #ifndef _LIBCPP_CXX03_LANG
     728              : 
     729              : template <class _Key, class _Tp>
     730              : struct _LIBCPP_STANDALONE_DEBUG __value_type
     731              : {
     732              :     typedef _Key                                     key_type;
     733              :     typedef _Tp                                      mapped_type;
     734              :     typedef pair<const key_type, mapped_type>        value_type;
     735              :     typedef pair<key_type&, mapped_type&>            __nc_ref_pair_type;
     736              :     typedef pair<key_type&&, mapped_type&&>          __nc_rref_pair_type;
     737              : 
     738              : private:
     739              :     value_type __cc_;
     740              : 
     741              : public:
     742              :     _LIBCPP_INLINE_VISIBILITY
     743              :     value_type& __get_value()
     744              :     {
     745              : #if _LIBCPP_STD_VER > 14
     746              :         return *_VSTD::launder(_VSTD::addressof(__cc_));
     747              : #else
     748              :         return __cc_;
     749              : #endif
     750              :     }
     751              : 
     752              :     _LIBCPP_INLINE_VISIBILITY
     753              :     const value_type& __get_value() const
     754              :     {
     755              : #if _LIBCPP_STD_VER > 14
     756              :         return *_VSTD::launder(_VSTD::addressof(__cc_));
     757              : #else
     758              :         return __cc_;
     759              : #endif
     760              :     }
     761              : 
     762              :     _LIBCPP_INLINE_VISIBILITY
     763              :     __nc_ref_pair_type __ref()
     764              :     {
     765              :         value_type& __v = __get_value();
     766              :         return __nc_ref_pair_type(const_cast<key_type&>(__v.first), __v.second);
     767              :     }
     768              : 
     769              :     _LIBCPP_INLINE_VISIBILITY
     770              :     __nc_rref_pair_type __move()
     771              :     {
     772              :         value_type& __v = __get_value();
     773              :         return __nc_rref_pair_type(
     774              :             _VSTD::move(const_cast<key_type&>(__v.first)),
     775              :             _VSTD::move(__v.second));
     776              :     }
     777              : 
     778              :     _LIBCPP_INLINE_VISIBILITY
     779              :     __value_type& operator=(const __value_type& __v)
     780              :     {
     781              :         __ref() = __v.__get_value();
     782              :         return *this;
     783              :     }
     784              : 
     785              :     _LIBCPP_INLINE_VISIBILITY
     786              :     __value_type& operator=(__value_type&& __v)
     787              :     {
     788              :         __ref() = __v.__move();
     789              :         return *this;
     790              :     }
     791              : 
     792              :     template <class _ValueTp,
     793              :               class = __enable_if_t<__is_same_uncvref<_ValueTp, value_type>::value>
     794              :              >
     795              :     _LIBCPP_INLINE_VISIBILITY
     796              :     __value_type& operator=(_ValueTp&& __v)
     797              :     {
     798              :         __ref() = _VSTD::forward<_ValueTp>(__v);
     799              :         return *this;
     800              :     }
     801              : 
     802              : private:
     803              :     __value_type() = delete;
     804              :     ~__value_type() = delete;
     805              :     __value_type(const __value_type&) = delete;
     806              :     __value_type(__value_type&&) = delete;
     807              : };
     808              : 
     809              : #else
     810              : 
     811              : template <class _Key, class _Tp>
     812              : struct __value_type
     813              : {
     814              :     typedef _Key                                     key_type;
     815              :     typedef _Tp                                      mapped_type;
     816              :     typedef pair<const key_type, mapped_type>        value_type;
     817              : 
     818              : private:
     819              :     value_type __cc_;
     820              : 
     821              : public:
     822              :     _LIBCPP_INLINE_VISIBILITY
     823          213 :     value_type& __get_value() { return __cc_; }
     824              :     _LIBCPP_INLINE_VISIBILITY
     825        13702 :     const value_type& __get_value() const { return __cc_; }
     826              : 
     827              : private:
     828              :    __value_type();
     829              :    __value_type(__value_type const&);
     830              :    __value_type& operator=(__value_type const&);
     831              :    ~__value_type();
     832              : };
     833              : 
     834              : #endif // _LIBCPP_CXX03_LANG
     835              : 
     836              : template <class _Tp>
     837              : struct __extract_key_value_types;
     838              : 
     839              : template <class _Key, class _Tp>
     840              : struct __extract_key_value_types<__value_type<_Key, _Tp> >
     841              : {
     842              :   typedef _Key const __key_type;
     843              :   typedef _Tp        __mapped_type;
     844              : };
     845              : 
     846              : template <class _TreeIterator>
     847              : class _LIBCPP_TEMPLATE_VIS __map_iterator
     848              : {
     849              :     typedef typename _TreeIterator::_NodeTypes                   _NodeTypes;
     850              :     typedef typename _TreeIterator::__pointer_traits             __pointer_traits;
     851              : 
     852              :     _TreeIterator __i_;
     853              : 
     854              : public:
     855              :     typedef bidirectional_iterator_tag                           iterator_category;
     856              :     typedef typename _NodeTypes::__map_value_type                value_type;
     857              :     typedef typename _TreeIterator::difference_type              difference_type;
     858              :     typedef value_type&                                          reference;
     859              :     typedef typename _NodeTypes::__map_value_type_pointer        pointer;
     860              : 
     861              :     _LIBCPP_INLINE_VISIBILITY
     862         6228 :     __map_iterator() _NOEXCEPT {}
     863              : 
     864              :     _LIBCPP_INLINE_VISIBILITY
     865        11096 :     __map_iterator(_TreeIterator __i) _NOEXCEPT : __i_(__i) {}
     866              : 
     867              :     _LIBCPP_INLINE_VISIBILITY
     868              :     reference operator*() const {return __i_->__get_value();}
     869              :     _LIBCPP_INLINE_VISIBILITY
     870           24 :     pointer operator->() const {return pointer_traits<pointer>::pointer_to(__i_->__get_value());}
     871              : 
     872              :     _LIBCPP_INLINE_VISIBILITY
     873            0 :     __map_iterator& operator++() {++__i_; return *this;}
     874              :     _LIBCPP_INLINE_VISIBILITY
     875              :     __map_iterator operator++(int)
     876              :     {
     877              :         __map_iterator __t(*this);
     878              :         ++(*this);
     879              :         return __t;
     880              :     }
     881              : 
     882              :     _LIBCPP_INLINE_VISIBILITY
     883              :     __map_iterator& operator--() {--__i_; return *this;}
     884              :     _LIBCPP_INLINE_VISIBILITY
     885              :     __map_iterator operator--(int)
     886              :     {
     887              :         __map_iterator __t(*this);
     888              :         --(*this);
     889              :         return __t;
     890              :     }
     891              : 
     892              :     friend _LIBCPP_INLINE_VISIBILITY
     893              :     bool operator==(const __map_iterator& __x, const __map_iterator& __y)
     894              :         {return __x.__i_ == __y.__i_;}
     895              :     friend
     896              :     _LIBCPP_INLINE_VISIBILITY
     897         2755 :     bool operator!=(const __map_iterator& __x, const __map_iterator& __y)
     898         2755 :         {return __x.__i_ != __y.__i_;}
     899              : 
     900              :     template <class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS map;
     901              :     template <class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS multimap;
     902              :     template <class> friend class _LIBCPP_TEMPLATE_VIS __map_const_iterator;
     903              : };
     904              : 
     905              : template <class _TreeIterator>
     906              : class _LIBCPP_TEMPLATE_VIS __map_const_iterator
     907              : {
     908              :     typedef typename _TreeIterator::_NodeTypes                   _NodeTypes;
     909              :     typedef typename _TreeIterator::__pointer_traits             __pointer_traits;
     910              : 
     911              :     _TreeIterator __i_;
     912              : 
     913              : public:
     914              :     typedef bidirectional_iterator_tag                           iterator_category;
     915              :     typedef typename _NodeTypes::__map_value_type                value_type;
     916              :     typedef typename _TreeIterator::difference_type              difference_type;
     917              :     typedef const value_type&                                    reference;
     918              :     typedef typename _NodeTypes::__const_map_value_type_pointer  pointer;
     919              : 
     920              :     _LIBCPP_INLINE_VISIBILITY
     921              :     __map_const_iterator() _NOEXCEPT {}
     922              : 
     923              :     _LIBCPP_INLINE_VISIBILITY
     924              :     __map_const_iterator(_TreeIterator __i) _NOEXCEPT : __i_(__i) {}
     925              :     _LIBCPP_INLINE_VISIBILITY
     926              :     __map_const_iterator(__map_iterator<
     927              :         typename _TreeIterator::__non_const_iterator> __i) _NOEXCEPT
     928              :         : __i_(__i.__i_) {}
     929              : 
     930              :     _LIBCPP_INLINE_VISIBILITY
     931              :     reference operator*() const {return __i_->__get_value();}
     932              :     _LIBCPP_INLINE_VISIBILITY
     933              :     pointer operator->() const {return pointer_traits<pointer>::pointer_to(__i_->__get_value());}
     934              : 
     935              :     _LIBCPP_INLINE_VISIBILITY
     936              :     __map_const_iterator& operator++() {++__i_; return *this;}
     937              :     _LIBCPP_INLINE_VISIBILITY
     938              :     __map_const_iterator operator++(int)
     939              :     {
     940              :         __map_const_iterator __t(*this);
     941              :         ++(*this);
     942              :         return __t;
     943              :     }
     944              : 
     945              :     _LIBCPP_INLINE_VISIBILITY
     946              :     __map_const_iterator& operator--() {--__i_; return *this;}
     947              :     _LIBCPP_INLINE_VISIBILITY
     948              :     __map_const_iterator operator--(int)
     949              :     {
     950              :         __map_const_iterator __t(*this);
     951              :         --(*this);
     952              :         return __t;
     953              :     }
     954              : 
     955              :     friend _LIBCPP_INLINE_VISIBILITY
     956              :     bool operator==(const __map_const_iterator& __x, const __map_const_iterator& __y)
     957              :         {return __x.__i_ == __y.__i_;}
     958              :     friend _LIBCPP_INLINE_VISIBILITY
     959              :     bool operator!=(const __map_const_iterator& __x, const __map_const_iterator& __y)
     960              :         {return __x.__i_ != __y.__i_;}
     961              : 
     962              :     template <class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS map;
     963              :     template <class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS multimap;
     964              :     template <class, class, class> friend class _LIBCPP_TEMPLATE_VIS __tree_const_iterator;
     965              : };
     966              : 
     967              : template <class _Key, class _Tp, class _Compare = less<_Key>,
     968              :           class _Allocator = allocator<pair<const _Key, _Tp> > >
     969              : class _LIBCPP_TEMPLATE_VIS map
     970              : {
     971              : public:
     972              :     // types:
     973              :     typedef _Key                                     key_type;
     974              :     typedef _Tp                                      mapped_type;
     975              :     typedef pair<const key_type, mapped_type>        value_type;
     976              :     typedef __type_identity_t<_Compare>              key_compare;
     977              :     typedef __type_identity_t<_Allocator>            allocator_type;
     978              :     typedef value_type&                              reference;
     979              :     typedef const value_type&                        const_reference;
     980              : 
     981              :     static_assert((is_same<typename allocator_type::value_type, value_type>::value),
     982              :                   "Allocator::value_type must be same type as value_type");
     983              : 
     984              :     class _LIBCPP_TEMPLATE_VIS value_compare
     985              :         : public __binary_function<value_type, value_type, bool>
     986              :     {
     987              :         friend class map;
     988              :     protected:
     989              :         key_compare comp;
     990              : 
     991              :         _LIBCPP_INLINE_VISIBILITY value_compare(key_compare __c) : comp(__c) {}
     992              :     public:
     993              :         _LIBCPP_INLINE_VISIBILITY
     994              :         bool operator()(const value_type& __x, const value_type& __y) const
     995              :             {return comp(__x.first, __y.first);}
     996              :     };
     997              : 
     998              : private:
     999              : 
    1000              :     typedef _VSTD::__value_type<key_type, mapped_type>             __value_type;
    1001              :     typedef __map_value_compare<key_type, __value_type, key_compare> __vc;
    1002              :     typedef __rebind_alloc<allocator_traits<allocator_type>, __value_type> __allocator_type;
    1003              :     typedef __tree<__value_type, __vc, __allocator_type>   __base;
    1004              :     typedef typename __base::__node_traits                 __node_traits;
    1005              :     typedef allocator_traits<allocator_type>               __alloc_traits;
    1006              : 
    1007              :     static_assert(is_same<allocator_type, __rebind_alloc<__alloc_traits, value_type> >::value,
    1008              :                   "[allocator.requirements] states that rebinding an allocator to the same type should result in the "
    1009              :                   "original allocator");
    1010              : 
    1011              :     __base __tree_;
    1012              : 
    1013              : public:
    1014              :     typedef typename __alloc_traits::pointer               pointer;
    1015              :     typedef typename __alloc_traits::const_pointer         const_pointer;
    1016              :     typedef typename __alloc_traits::size_type             size_type;
    1017              :     typedef typename __alloc_traits::difference_type       difference_type;
    1018              :     typedef __map_iterator<typename __base::iterator>             iterator;
    1019              :     typedef __map_const_iterator<typename __base::const_iterator> const_iterator;
    1020              :     typedef _VSTD::reverse_iterator<iterator>               reverse_iterator;
    1021              :     typedef _VSTD::reverse_iterator<const_iterator>         const_reverse_iterator;
    1022              : 
    1023              : #if _LIBCPP_STD_VER > 14
    1024              :     typedef __map_node_handle<typename __base::__node, allocator_type> node_type;
    1025              :     typedef __insert_return_type<iterator, node_type> insert_return_type;
    1026              : #endif
    1027              : 
    1028              :     template <class _Key2, class _Value2, class _Comp2, class _Alloc2>
    1029              :         friend class _LIBCPP_TEMPLATE_VIS map;
    1030              :     template <class _Key2, class _Value2, class _Comp2, class _Alloc2>
    1031              :         friend class _LIBCPP_TEMPLATE_VIS multimap;
    1032              : 
    1033              :     _LIBCPP_INLINE_VISIBILITY
    1034           30 :     map()
    1035              :         _NOEXCEPT_(
    1036              :             is_nothrow_default_constructible<allocator_type>::value &&
    1037              :             is_nothrow_default_constructible<key_compare>::value &&
    1038              :             is_nothrow_copy_constructible<key_compare>::value)
    1039           30 :         : __tree_(__vc(key_compare())) {}
    1040              : 
    1041              :     _LIBCPP_INLINE_VISIBILITY
    1042              :     explicit map(const key_compare& __comp)
    1043              :         _NOEXCEPT_(
    1044              :             is_nothrow_default_constructible<allocator_type>::value &&
    1045              :             is_nothrow_copy_constructible<key_compare>::value)
    1046              :         : __tree_(__vc(__comp)) {}
    1047              : 
    1048              :     _LIBCPP_INLINE_VISIBILITY
    1049              :     explicit map(const key_compare& __comp, const allocator_type& __a)
    1050              :         : __tree_(__vc(__comp), typename __base::allocator_type(__a)) {}
    1051              : 
    1052              :     template <class _InputIterator>
    1053              :     _LIBCPP_INLINE_VISIBILITY
    1054              :         map(_InputIterator __f, _InputIterator __l,
    1055              :             const key_compare& __comp = key_compare())
    1056              :         : __tree_(__vc(__comp))
    1057              :         {
    1058              :             insert(__f, __l);
    1059              :         }
    1060              : 
    1061              :     template <class _InputIterator>
    1062              :     _LIBCPP_INLINE_VISIBILITY
    1063              :         map(_InputIterator __f, _InputIterator __l,
    1064              :             const key_compare& __comp, const allocator_type& __a)
    1065              :         : __tree_(__vc(__comp), typename __base::allocator_type(__a))
    1066              :         {
    1067              :             insert(__f, __l);
    1068              :         }
    1069              : 
    1070              : #if _LIBCPP_STD_VER > 11
    1071              :     template <class _InputIterator>
    1072              :     _LIBCPP_INLINE_VISIBILITY
    1073              :     map(_InputIterator __f, _InputIterator __l, const allocator_type& __a)
    1074              :         : map(__f, __l, key_compare(), __a) {}
    1075              : #endif
    1076              : 
    1077              :     _LIBCPP_INLINE_VISIBILITY
    1078              :     map(const map& __m)
    1079              :         : __tree_(__m.__tree_)
    1080              :         {
    1081              :             insert(__m.begin(), __m.end());
    1082              :         }
    1083              : 
    1084              :     _LIBCPP_INLINE_VISIBILITY
    1085              :     map& operator=(const map& __m)
    1086              :         {
    1087              : #ifndef _LIBCPP_CXX03_LANG
    1088              :             __tree_ = __m.__tree_;
    1089              : #else
    1090              :             if (this != _VSTD::addressof(__m)) {
    1091              :                 __tree_.clear();
    1092              :                 __tree_.value_comp() = __m.__tree_.value_comp();
    1093              :                 __tree_.__copy_assign_alloc(__m.__tree_);
    1094              :                 insert(__m.begin(), __m.end());
    1095              :             }
    1096              : #endif
    1097              :             return *this;
    1098              :         }
    1099              : 
    1100              : #ifndef _LIBCPP_CXX03_LANG
    1101              : 
    1102              :     _LIBCPP_INLINE_VISIBILITY
    1103              :     map(map&& __m)
    1104              :         _NOEXCEPT_(is_nothrow_move_constructible<__base>::value)
    1105              :         : __tree_(_VSTD::move(__m.__tree_))
    1106              :         {
    1107              :         }
    1108              : 
    1109              :     map(map&& __m, const allocator_type& __a);
    1110              : 
    1111              :     _LIBCPP_INLINE_VISIBILITY
    1112              :     map& operator=(map&& __m)
    1113              :         _NOEXCEPT_(is_nothrow_move_assignable<__base>::value)
    1114              :         {
    1115              :             __tree_ = _VSTD::move(__m.__tree_);
    1116              :             return *this;
    1117              :         }
    1118              : 
    1119              :     _LIBCPP_INLINE_VISIBILITY
    1120              :     map(initializer_list<value_type> __il, const key_compare& __comp = key_compare())
    1121              :         : __tree_(__vc(__comp))
    1122              :         {
    1123              :             insert(__il.begin(), __il.end());
    1124              :         }
    1125              : 
    1126              :     _LIBCPP_INLINE_VISIBILITY
    1127              :     map(initializer_list<value_type> __il, const key_compare& __comp, const allocator_type& __a)
    1128              :         : __tree_(__vc(__comp), typename __base::allocator_type(__a))
    1129              :         {
    1130              :             insert(__il.begin(), __il.end());
    1131              :         }
    1132              : 
    1133              : #if _LIBCPP_STD_VER > 11
    1134              :     _LIBCPP_INLINE_VISIBILITY
    1135              :     map(initializer_list<value_type> __il, const allocator_type& __a)
    1136              :         : map(__il, key_compare(), __a) {}
    1137              : #endif
    1138              : 
    1139              :     _LIBCPP_INLINE_VISIBILITY
    1140              :     map& operator=(initializer_list<value_type> __il)
    1141              :         {
    1142              :             __tree_.__assign_unique(__il.begin(), __il.end());
    1143              :             return *this;
    1144              :         }
    1145              : 
    1146              : #endif // _LIBCPP_CXX03_LANG
    1147              : 
    1148              :     _LIBCPP_INLINE_VISIBILITY
    1149              :     explicit map(const allocator_type& __a)
    1150              :         : __tree_(typename __base::allocator_type(__a))
    1151              :         {
    1152              :         }
    1153              : 
    1154              :     _LIBCPP_INLINE_VISIBILITY
    1155              :     map(const map& __m, const allocator_type& __a)
    1156              :         : __tree_(__m.__tree_.value_comp(), typename __base::allocator_type(__a))
    1157              :         {
    1158              :             insert(__m.begin(), __m.end());
    1159              :         }
    1160              : 
    1161              :     _LIBCPP_INLINE_VISIBILITY
    1162              :     ~map() {
    1163              :         static_assert(sizeof(__diagnose_non_const_comparator<_Key, _Compare>()), "");
    1164              :     }
    1165              : 
    1166              :     _LIBCPP_INLINE_VISIBILITY
    1167            3 :           iterator begin() _NOEXCEPT {return __tree_.begin();}
    1168              :     _LIBCPP_INLINE_VISIBILITY
    1169              :     const_iterator begin() const _NOEXCEPT {return __tree_.begin();}
    1170              :     _LIBCPP_INLINE_VISIBILITY
    1171         2755 :           iterator end() _NOEXCEPT {return __tree_.end();}
    1172              :     _LIBCPP_INLINE_VISIBILITY
    1173              :     const_iterator end() const _NOEXCEPT {return __tree_.end();}
    1174              : 
    1175              :     _LIBCPP_INLINE_VISIBILITY
    1176              :           reverse_iterator rbegin() _NOEXCEPT {return reverse_iterator(end());}
    1177              :     _LIBCPP_INLINE_VISIBILITY
    1178              :     const_reverse_iterator rbegin() const _NOEXCEPT
    1179              :         {return const_reverse_iterator(end());}
    1180              :     _LIBCPP_INLINE_VISIBILITY
    1181              :           reverse_iterator rend() _NOEXCEPT
    1182              :             {return       reverse_iterator(begin());}
    1183              :     _LIBCPP_INLINE_VISIBILITY
    1184              :     const_reverse_iterator rend() const _NOEXCEPT
    1185              :         {return const_reverse_iterator(begin());}
    1186              : 
    1187              :     _LIBCPP_INLINE_VISIBILITY
    1188              :     const_iterator cbegin() const _NOEXCEPT {return begin();}
    1189              :     _LIBCPP_INLINE_VISIBILITY
    1190              :     const_iterator cend() const _NOEXCEPT {return end();}
    1191              :     _LIBCPP_INLINE_VISIBILITY
    1192              :     const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();}
    1193              :     _LIBCPP_INLINE_VISIBILITY
    1194              :     const_reverse_iterator crend() const _NOEXCEPT {return rend();}
    1195              : 
    1196              :     _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY
    1197              :     bool      empty() const _NOEXCEPT {return __tree_.size() == 0;}
    1198              :     _LIBCPP_INLINE_VISIBILITY
    1199              :     size_type size() const _NOEXCEPT {return __tree_.size();}
    1200              :     _LIBCPP_INLINE_VISIBILITY
    1201              :     size_type max_size() const _NOEXCEPT {return __tree_.max_size();}
    1202              : 
    1203              :     mapped_type& operator[](const key_type& __k);
    1204              : #ifndef _LIBCPP_CXX03_LANG
    1205              :     mapped_type& operator[](key_type&& __k);
    1206              : #endif
    1207              : 
    1208              :           mapped_type& at(const key_type& __k);
    1209              :     const mapped_type& at(const key_type& __k) const;
    1210              : 
    1211              :     _LIBCPP_INLINE_VISIBILITY
    1212              :     allocator_type get_allocator() const _NOEXCEPT {return allocator_type(__tree_.__alloc());}
    1213              :     _LIBCPP_INLINE_VISIBILITY
    1214              :     key_compare    key_comp()      const {return __tree_.value_comp().key_comp();}
    1215              :     _LIBCPP_INLINE_VISIBILITY
    1216              :     value_compare  value_comp()    const {return value_compare(__tree_.value_comp().key_comp());}
    1217              : 
    1218              : #ifndef _LIBCPP_CXX03_LANG
    1219              :     template <class ..._Args>
    1220              :     _LIBCPP_INLINE_VISIBILITY
    1221              :     pair<iterator, bool> emplace(_Args&& ...__args) {
    1222              :         return __tree_.__emplace_unique(_VSTD::forward<_Args>(__args)...);
    1223              :     }
    1224              : 
    1225              :     template <class ..._Args>
    1226              :     _LIBCPP_INLINE_VISIBILITY
    1227              :     iterator emplace_hint(const_iterator __p, _Args&& ...__args) {
    1228              :         return __tree_.__emplace_hint_unique(__p.__i_, _VSTD::forward<_Args>(__args)...);
    1229              :     }
    1230              : 
    1231              :     template <class _Pp,
    1232              :               class = __enable_if_t<is_constructible<value_type, _Pp>::value> >
    1233              :         _LIBCPP_INLINE_VISIBILITY
    1234              :         pair<iterator, bool> insert(_Pp&& __p)
    1235              :             {return __tree_.__insert_unique(_VSTD::forward<_Pp>(__p));}
    1236              : 
    1237              :     template <class _Pp,
    1238              :               class = __enable_if_t<is_constructible<value_type, _Pp>::value> >
    1239              :         _LIBCPP_INLINE_VISIBILITY
    1240              :         iterator insert(const_iterator __pos, _Pp&& __p)
    1241              :             {return __tree_.__insert_unique(__pos.__i_, _VSTD::forward<_Pp>(__p));}
    1242              : 
    1243              : #endif // _LIBCPP_CXX03_LANG
    1244              : 
    1245              :     _LIBCPP_INLINE_VISIBILITY
    1246              :     pair<iterator, bool>
    1247              :         insert(const value_type& __v) {return __tree_.__insert_unique(__v);}
    1248              : 
    1249              :     _LIBCPP_INLINE_VISIBILITY
    1250              :     iterator
    1251              :         insert(const_iterator __p, const value_type& __v)
    1252              :             {return __tree_.__insert_unique(__p.__i_, __v);}
    1253              : 
    1254              : #ifndef _LIBCPP_CXX03_LANG
    1255              :     _LIBCPP_INLINE_VISIBILITY
    1256              :     pair<iterator, bool>
    1257              :     insert(value_type&& __v) {return __tree_.__insert_unique(_VSTD::move(__v));}
    1258              : 
    1259              :     _LIBCPP_INLINE_VISIBILITY
    1260              :     iterator insert(const_iterator __p,  value_type&& __v)
    1261              :     {return __tree_.__insert_unique(__p.__i_, _VSTD::move(__v));}
    1262              : 
    1263              :     _LIBCPP_INLINE_VISIBILITY
    1264              :     void insert(initializer_list<value_type> __il)
    1265              :         {insert(__il.begin(), __il.end());}
    1266              : #endif
    1267              : 
    1268              :     template <class _InputIterator>
    1269              :         _LIBCPP_INLINE_VISIBILITY
    1270              :         void insert(_InputIterator __f, _InputIterator __l)
    1271              :         {
    1272              :             for (const_iterator __e = cend(); __f != __l; ++__f)
    1273              :                 insert(__e.__i_, *__f);
    1274              :         }
    1275              : 
    1276              : #if _LIBCPP_STD_VER > 14
    1277              : 
    1278              :     template <class... _Args>
    1279              :         _LIBCPP_INLINE_VISIBILITY
    1280              :         pair<iterator, bool> try_emplace(const key_type& __k, _Args&&... __args)
    1281              :     {
    1282              :         return __tree_.__emplace_unique_key_args(__k,
    1283              :             _VSTD::piecewise_construct,
    1284              :             _VSTD::forward_as_tuple(__k),
    1285              :             _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...));
    1286              :     }
    1287              : 
    1288              :     template <class... _Args>
    1289              :         _LIBCPP_INLINE_VISIBILITY
    1290              :         pair<iterator, bool> try_emplace(key_type&& __k, _Args&&... __args)
    1291              :     {
    1292              :         return __tree_.__emplace_unique_key_args(__k,
    1293              :             _VSTD::piecewise_construct,
    1294              :             _VSTD::forward_as_tuple(_VSTD::move(__k)),
    1295              :             _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...));
    1296              :     }
    1297              : 
    1298              :     template <class... _Args>
    1299              :         _LIBCPP_INLINE_VISIBILITY
    1300              :         iterator try_emplace(const_iterator __h, const key_type& __k, _Args&&... __args)
    1301              :     {
    1302              :         return __tree_.__emplace_hint_unique_key_args(__h.__i_, __k,
    1303              :             _VSTD::piecewise_construct,
    1304              :             _VSTD::forward_as_tuple(__k),
    1305              :             _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...)).first;
    1306              :     }
    1307              : 
    1308              :     template <class... _Args>
    1309              :         _LIBCPP_INLINE_VISIBILITY
    1310              :         iterator try_emplace(const_iterator __h, key_type&& __k, _Args&&... __args)
    1311              :     {
    1312              :         return __tree_.__emplace_hint_unique_key_args(__h.__i_, __k,
    1313              :             _VSTD::piecewise_construct,
    1314              :             _VSTD::forward_as_tuple(_VSTD::move(__k)),
    1315              :             _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...)).first;
    1316              :     }
    1317              : 
    1318              :     template <class _Vp>
    1319              :         _LIBCPP_INLINE_VISIBILITY
    1320              :         pair<iterator, bool> insert_or_assign(const key_type& __k, _Vp&& __v)
    1321              :     {
    1322              :         iterator __p = lower_bound(__k);
    1323              :         if ( __p != end() && !key_comp()(__k, __p->first))
    1324              :         {
    1325              :             __p->second = _VSTD::forward<_Vp>(__v);
    1326              :             return _VSTD::make_pair(__p, false);
    1327              :         }
    1328              :         return _VSTD::make_pair(emplace_hint(__p, __k, _VSTD::forward<_Vp>(__v)), true);
    1329              :     }
    1330              : 
    1331              :     template <class _Vp>
    1332              :         _LIBCPP_INLINE_VISIBILITY
    1333              :         pair<iterator, bool> insert_or_assign(key_type&& __k, _Vp&& __v)
    1334              :     {
    1335              :         iterator __p = lower_bound(__k);
    1336              :         if ( __p != end() && !key_comp()(__k, __p->first))
    1337              :         {
    1338              :             __p->second = _VSTD::forward<_Vp>(__v);
    1339              :             return _VSTD::make_pair(__p, false);
    1340              :         }
    1341              :         return _VSTD::make_pair(emplace_hint(__p, _VSTD::move(__k), _VSTD::forward<_Vp>(__v)), true);
    1342              :     }
    1343              : 
    1344              :     template <class _Vp>
    1345              :     _LIBCPP_INLINE_VISIBILITY iterator insert_or_assign(const_iterator __h,
    1346              :                                                         const key_type& __k,
    1347              :                                                         _Vp&& __v) {
    1348              :       auto [__r, __inserted] = __tree_.__emplace_hint_unique_key_args(
    1349              :           __h.__i_, __k, __k, _VSTD::forward<_Vp>(__v));
    1350              : 
    1351              :       if (!__inserted)
    1352              :         __r->__get_value().second = _VSTD::forward<_Vp>(__v);
    1353              : 
    1354              :       return __r;
    1355              :     }
    1356              : 
    1357              :     template <class _Vp>
    1358              :     _LIBCPP_INLINE_VISIBILITY iterator insert_or_assign(const_iterator __h,
    1359              :                                                         key_type&& __k,
    1360              :                                                         _Vp&& __v) {
    1361              :       auto [__r, __inserted] = __tree_.__emplace_hint_unique_key_args(
    1362              :           __h.__i_, __k, _VSTD::move(__k), _VSTD::forward<_Vp>(__v));
    1363              : 
    1364              :       if (!__inserted)
    1365              :         __r->__get_value().second = _VSTD::forward<_Vp>(__v);
    1366              : 
    1367              :       return __r;
    1368              :     }
    1369              : 
    1370              : #endif // _LIBCPP_STD_VER > 14
    1371              : 
    1372              :     _LIBCPP_INLINE_VISIBILITY
    1373              :     iterator erase(const_iterator __p) {return __tree_.erase(__p.__i_);}
    1374              :     _LIBCPP_INLINE_VISIBILITY
    1375              :     iterator erase(iterator __p)       {return __tree_.erase(__p.__i_);}
    1376              :     _LIBCPP_INLINE_VISIBILITY
    1377              :     size_type erase(const key_type& __k)
    1378              :         {return __tree_.__erase_unique(__k);}
    1379              :     _LIBCPP_INLINE_VISIBILITY
    1380              :     iterator  erase(const_iterator __f, const_iterator __l)
    1381              :         {return __tree_.erase(__f.__i_, __l.__i_);}
    1382              :     _LIBCPP_INLINE_VISIBILITY
    1383              :     void clear() _NOEXCEPT {__tree_.clear();}
    1384              : 
    1385              : #if _LIBCPP_STD_VER > 14
    1386              :     _LIBCPP_INLINE_VISIBILITY
    1387              :     insert_return_type insert(node_type&& __nh)
    1388              :     {
    1389              :         _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(),
    1390              :             "node_type with incompatible allocator passed to map::insert()");
    1391              :         return __tree_.template __node_handle_insert_unique<
    1392              :             node_type, insert_return_type>(_VSTD::move(__nh));
    1393              :     }
    1394              :     _LIBCPP_INLINE_VISIBILITY
    1395              :     iterator insert(const_iterator __hint, node_type&& __nh)
    1396              :     {
    1397              :         _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(),
    1398              :             "node_type with incompatible allocator passed to map::insert()");
    1399              :         return __tree_.template __node_handle_insert_unique<node_type>(
    1400              :             __hint.__i_, _VSTD::move(__nh));
    1401              :     }
    1402              :     _LIBCPP_INLINE_VISIBILITY
    1403              :     node_type extract(key_type const& __key)
    1404              :     {
    1405              :         return __tree_.template __node_handle_extract<node_type>(__key);
    1406              :     }
    1407              :     _LIBCPP_INLINE_VISIBILITY
    1408              :     node_type extract(const_iterator __it)
    1409              :     {
    1410              :         return __tree_.template __node_handle_extract<node_type>(__it.__i_);
    1411              :     }
    1412              :     template <class _Compare2>
    1413              :     _LIBCPP_INLINE_VISIBILITY
    1414              :     void merge(map<key_type, mapped_type, _Compare2, allocator_type>& __source)
    1415              :     {
    1416              :         _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
    1417              :                        "merging container with incompatible allocator");
    1418              :         __tree_.__node_handle_merge_unique(__source.__tree_);
    1419              :     }
    1420              :     template <class _Compare2>
    1421              :     _LIBCPP_INLINE_VISIBILITY
    1422              :     void merge(map<key_type, mapped_type, _Compare2, allocator_type>&& __source)
    1423              :     {
    1424              :         _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
    1425              :                        "merging container with incompatible allocator");
    1426              :         __tree_.__node_handle_merge_unique(__source.__tree_);
    1427              :     }
    1428              :     template <class _Compare2>
    1429              :     _LIBCPP_INLINE_VISIBILITY
    1430              :     void merge(multimap<key_type, mapped_type, _Compare2, allocator_type>& __source)
    1431              :     {
    1432              :         _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
    1433              :                        "merging container with incompatible allocator");
    1434              :         __tree_.__node_handle_merge_unique(__source.__tree_);
    1435              :     }
    1436              :     template <class _Compare2>
    1437              :     _LIBCPP_INLINE_VISIBILITY
    1438              :     void merge(multimap<key_type, mapped_type, _Compare2, allocator_type>&& __source)
    1439              :     {
    1440              :         _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
    1441              :                        "merging container with incompatible allocator");
    1442              :         __tree_.__node_handle_merge_unique(__source.__tree_);
    1443              :     }
    1444              : #endif
    1445              : 
    1446              :     _LIBCPP_INLINE_VISIBILITY
    1447              :     void swap(map& __m)
    1448              :         _NOEXCEPT_(__is_nothrow_swappable<__base>::value)
    1449              :         {__tree_.swap(__m.__tree_);}
    1450              : 
    1451              :     _LIBCPP_INLINE_VISIBILITY
    1452         2790 :     iterator find(const key_type& __k)             {return __tree_.find(__k);}
    1453              :     _LIBCPP_INLINE_VISIBILITY
    1454              :     const_iterator find(const key_type& __k) const {return __tree_.find(__k);}
    1455              : #if _LIBCPP_STD_VER > 11
    1456              :     template <typename _K2>
    1457              :     _LIBCPP_INLINE_VISIBILITY
    1458              :     __enable_if_t<__is_transparent<_Compare, _K2>::value, iterator>
    1459              :     find(const _K2& __k)                           {return __tree_.find(__k);}
    1460              :     template <typename _K2>
    1461              :     _LIBCPP_INLINE_VISIBILITY
    1462              :     __enable_if_t<__is_transparent<_Compare, _K2>::value, const_iterator>
    1463              :     find(const _K2& __k) const                     {return __tree_.find(__k);}
    1464              : #endif
    1465              : 
    1466              :     _LIBCPP_INLINE_VISIBILITY
    1467              :     size_type      count(const key_type& __k) const
    1468              :         {return __tree_.__count_unique(__k);}
    1469              : #if _LIBCPP_STD_VER > 11
    1470              :     template <typename _K2>
    1471              :     _LIBCPP_INLINE_VISIBILITY
    1472              :     __enable_if_t<__is_transparent<_Compare, _K2>::value, size_type>
    1473              :     count(const _K2& __k) const {return __tree_.__count_multi(__k);}
    1474              : #endif
    1475              : 
    1476              : #if _LIBCPP_STD_VER > 17
    1477              :     _LIBCPP_INLINE_VISIBILITY
    1478              :     bool contains(const key_type& __k) const {return find(__k) != end();}
    1479              :     template <typename _K2>
    1480              :     _LIBCPP_INLINE_VISIBILITY
    1481              :     __enable_if_t<__is_transparent<_Compare, _K2>::value, bool>
    1482              :     contains(const _K2& __k) const { return find(__k) != end(); }
    1483              : #endif // _LIBCPP_STD_VER > 17
    1484              : 
    1485              :     _LIBCPP_INLINE_VISIBILITY
    1486              :     iterator lower_bound(const key_type& __k)
    1487              :         {return __tree_.lower_bound(__k);}
    1488              :     _LIBCPP_INLINE_VISIBILITY
    1489              :     const_iterator lower_bound(const key_type& __k) const
    1490              :         {return __tree_.lower_bound(__k);}
    1491              : #if _LIBCPP_STD_VER > 11
    1492              :     template <typename _K2>
    1493              :     _LIBCPP_INLINE_VISIBILITY
    1494              :     __enable_if_t<__is_transparent<_Compare, _K2>::value, iterator>
    1495              :     lower_bound(const _K2& __k)       {return __tree_.lower_bound(__k);}
    1496              : 
    1497              :     template <typename _K2>
    1498              :     _LIBCPP_INLINE_VISIBILITY
    1499              :     __enable_if_t<__is_transparent<_Compare, _K2>::value, const_iterator>
    1500              :     lower_bound(const _K2& __k) const {return __tree_.lower_bound(__k);}
    1501              : #endif
    1502              : 
    1503              :     _LIBCPP_INLINE_VISIBILITY
    1504              :     iterator upper_bound(const key_type& __k)
    1505              :         {return __tree_.upper_bound(__k);}
    1506              :     _LIBCPP_INLINE_VISIBILITY
    1507              :     const_iterator upper_bound(const key_type& __k) const
    1508              :         {return __tree_.upper_bound(__k);}
    1509              : #if _LIBCPP_STD_VER > 11
    1510              :     template <typename _K2>
    1511              :     _LIBCPP_INLINE_VISIBILITY
    1512              :     __enable_if_t<__is_transparent<_Compare, _K2>::value, iterator>
    1513              :     upper_bound(const _K2& __k)       {return __tree_.upper_bound(__k);}
    1514              :     template <typename _K2>
    1515              :     _LIBCPP_INLINE_VISIBILITY
    1516              :     __enable_if_t<__is_transparent<_Compare, _K2>::value, const_iterator>
    1517              :     upper_bound(const _K2& __k) const {return __tree_.upper_bound(__k);}
    1518              : #endif
    1519              : 
    1520              :     _LIBCPP_INLINE_VISIBILITY
    1521              :     pair<iterator,iterator> equal_range(const key_type& __k)
    1522              :         {return __tree_.__equal_range_unique(__k);}
    1523              :     _LIBCPP_INLINE_VISIBILITY
    1524              :     pair<const_iterator,const_iterator> equal_range(const key_type& __k) const
    1525              :         {return __tree_.__equal_range_unique(__k);}
    1526              : #if _LIBCPP_STD_VER > 11
    1527              :     template <typename _K2>
    1528              :     _LIBCPP_INLINE_VISIBILITY
    1529              :     __enable_if_t<__is_transparent<_Compare, _K2>::value, pair<iterator,iterator>>
    1530              :     equal_range(const _K2& __k)       {return __tree_.__equal_range_multi(__k);}
    1531              :     template <typename _K2>
    1532              :     _LIBCPP_INLINE_VISIBILITY
    1533              :     __enable_if_t<__is_transparent<_Compare, _K2>::value, pair<const_iterator,const_iterator>>
    1534              :     equal_range(const _K2& __k) const {return __tree_.__equal_range_multi(__k);}
    1535              : #endif
    1536              : 
    1537              : private:
    1538              :     typedef typename __base::__node                    __node;
    1539              :     typedef typename __base::__node_allocator          __node_allocator;
    1540              :     typedef typename __base::__node_pointer            __node_pointer;
    1541              :     typedef typename __base::__node_base_pointer       __node_base_pointer;
    1542              :     typedef typename __base::__parent_pointer          __parent_pointer;
    1543              : 
    1544              :     typedef __map_node_destructor<__node_allocator> _Dp;
    1545              :     typedef unique_ptr<__node, _Dp> __node_holder;
    1546              : 
    1547              : #ifdef _LIBCPP_CXX03_LANG
    1548              :     __node_holder __construct_node_with_key(const key_type& __k);
    1549              : #endif
    1550              : };
    1551              : 
    1552              : #if _LIBCPP_STD_VER >= 17
    1553              : template<class _InputIterator, class _Compare = less<__iter_key_type<_InputIterator>>,
    1554              :          class _Allocator = allocator<__iter_to_alloc_type<_InputIterator>>,
    1555              :          class = enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value, void>,
    1556              :          class = enable_if_t<!__is_allocator<_Compare>::value, void>,
    1557              :          class = enable_if_t<__is_allocator<_Allocator>::value, void>>
    1558              : map(_InputIterator, _InputIterator, _Compare = _Compare(), _Allocator = _Allocator())
    1559              :   -> map<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>, _Compare, _Allocator>;
    1560              : 
    1561              : template<class _Key, class _Tp, class _Compare = less<remove_const_t<_Key>>,
    1562              :          class _Allocator = allocator<pair<const _Key, _Tp>>,
    1563              :          class = enable_if_t<!__is_allocator<_Compare>::value, void>,
    1564              :          class = enable_if_t<__is_allocator<_Allocator>::value, void>>
    1565              : map(initializer_list<pair<_Key, _Tp>>, _Compare = _Compare(), _Allocator = _Allocator())
    1566              :   -> map<remove_const_t<_Key>, _Tp, _Compare, _Allocator>;
    1567              : 
    1568              : template<class _InputIterator, class _Allocator,
    1569              :          class = enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value, void>,
    1570              :          class = enable_if_t<__is_allocator<_Allocator>::value, void>>
    1571              : map(_InputIterator, _InputIterator, _Allocator)
    1572              :   -> map<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>,
    1573              :          less<__iter_key_type<_InputIterator>>, _Allocator>;
    1574              : 
    1575              : template<class _Key, class _Tp, class _Allocator,
    1576              :          class = enable_if_t<__is_allocator<_Allocator>::value, void>>
    1577              : map(initializer_list<pair<_Key, _Tp>>, _Allocator)
    1578              :   -> map<remove_const_t<_Key>, _Tp, less<remove_const_t<_Key>>, _Allocator>;
    1579              : #endif
    1580              : 
    1581              : #ifndef _LIBCPP_CXX03_LANG
    1582              : template <class _Key, class _Tp, class _Compare, class _Allocator>
    1583              : map<_Key, _Tp, _Compare, _Allocator>::map(map&& __m, const allocator_type& __a)
    1584              :     : __tree_(_VSTD::move(__m.__tree_), typename __base::allocator_type(__a))
    1585              : {
    1586              :     if (__a != __m.get_allocator())
    1587              :     {
    1588              :         const_iterator __e = cend();
    1589              :         while (!__m.empty())
    1590              :             __tree_.__insert_unique(__e.__i_,
    1591              :                     __m.__tree_.remove(__m.begin().__i_)->__value_.__move());
    1592              :     }
    1593              : }
    1594              : 
    1595              : template <class _Key, class _Tp, class _Compare, class _Allocator>
    1596              : _Tp&
    1597              : map<_Key, _Tp, _Compare, _Allocator>::operator[](const key_type& __k)
    1598              : {
    1599              :     return __tree_.__emplace_unique_key_args(__k,
    1600              :         _VSTD::piecewise_construct,
    1601              :         _VSTD::forward_as_tuple(__k),
    1602              :         _VSTD::forward_as_tuple()).first->__get_value().second;
    1603              : }
    1604              : 
    1605              : template <class _Key, class _Tp, class _Compare, class _Allocator>
    1606              : _Tp&
    1607              : map<_Key, _Tp, _Compare, _Allocator>::operator[](key_type&& __k)
    1608              : {
    1609              :     return __tree_.__emplace_unique_key_args(__k,
    1610              :         _VSTD::piecewise_construct,
    1611              :         _VSTD::forward_as_tuple(_VSTD::move(__k)),
    1612              :         _VSTD::forward_as_tuple()).first->__get_value().second;
    1613              : }
    1614              : 
    1615              : #else // _LIBCPP_CXX03_LANG
    1616              : 
    1617              : template <class _Key, class _Tp, class _Compare, class _Allocator>
    1618              : typename map<_Key, _Tp, _Compare, _Allocator>::__node_holder
    1619           63 : map<_Key, _Tp, _Compare, _Allocator>::__construct_node_with_key(const key_type& __k)
    1620              : {
    1621           63 :     __node_allocator& __na = __tree_.__node_alloc();
    1622           63 :     __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
    1623           63 :     __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__get_value().first), __k);
    1624           63 :     __h.get_deleter().__first_constructed = true;
    1625           63 :     __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__get_value().second));
    1626           63 :     __h.get_deleter().__second_constructed = true;
    1627           63 :     return __h;
    1628           63 : }
    1629              : 
    1630              : template <class _Key, class _Tp, class _Compare, class _Allocator>
    1631              : _Tp&
    1632           63 : map<_Key, _Tp, _Compare, _Allocator>::operator[](const key_type& __k)
    1633              : {
    1634              :     __parent_pointer __parent;
    1635           63 :     __node_base_pointer& __child = __tree_.__find_equal(__parent, __k);
    1636           63 :     __node_pointer __r = static_cast<__node_pointer>(__child);
    1637           63 :     if (__child == nullptr)
    1638              :     {
    1639           63 :         __node_holder __h = __construct_node_with_key(__k);
    1640           63 :         __tree_.__insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
    1641           63 :         __r = __h.release();
    1642           63 :     }
    1643           63 :     return __r->__value_.__get_value().second;
    1644              : }
    1645              : 
    1646              : #endif // _LIBCPP_CXX03_LANG
    1647              : 
    1648              : template <class _Key, class _Tp, class _Compare, class _Allocator>
    1649              : _Tp&
    1650              : map<_Key, _Tp, _Compare, _Allocator>::at(const key_type& __k)
    1651              : {
    1652              :     __parent_pointer __parent;
    1653              :     __node_base_pointer& __child = __tree_.__find_equal(__parent, __k);
    1654              :     if (__child == nullptr)
    1655              :         __throw_out_of_range("map::at:  key not found");
    1656              :     return static_cast<__node_pointer>(__child)->__value_.__get_value().second;
    1657              : }
    1658              : 
    1659              : template <class _Key, class _Tp, class _Compare, class _Allocator>
    1660              : const _Tp&
    1661              : map<_Key, _Tp, _Compare, _Allocator>::at(const key_type& __k) const
    1662              : {
    1663              :     __parent_pointer __parent;
    1664              :     __node_base_pointer __child = __tree_.__find_equal(__parent, __k);
    1665              :     if (__child == nullptr)
    1666              :         __throw_out_of_range("map::at:  key not found");
    1667              :     return static_cast<__node_pointer>(__child)->__value_.__get_value().second;
    1668              : }
    1669              : 
    1670              : 
    1671              : template <class _Key, class _Tp, class _Compare, class _Allocator>
    1672              : inline _LIBCPP_INLINE_VISIBILITY
    1673              : bool
    1674              : operator==(const map<_Key, _Tp, _Compare, _Allocator>& __x,
    1675              :            const map<_Key, _Tp, _Compare, _Allocator>& __y)
    1676              : {
    1677              :     return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin());
    1678              : }
    1679              : 
    1680              : template <class _Key, class _Tp, class _Compare, class _Allocator>
    1681              : inline _LIBCPP_INLINE_VISIBILITY
    1682              : bool
    1683              : operator< (const map<_Key, _Tp, _Compare, _Allocator>& __x,
    1684              :            const map<_Key, _Tp, _Compare, _Allocator>& __y)
    1685              : {
    1686              :     return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
    1687              : }
    1688              : 
    1689              : template <class _Key, class _Tp, class _Compare, class _Allocator>
    1690              : inline _LIBCPP_INLINE_VISIBILITY
    1691              : bool
    1692              : operator!=(const map<_Key, _Tp, _Compare, _Allocator>& __x,
    1693              :            const map<_Key, _Tp, _Compare, _Allocator>& __y)
    1694              : {
    1695              :     return !(__x == __y);
    1696              : }
    1697              : 
    1698              : template <class _Key, class _Tp, class _Compare, class _Allocator>
    1699              : inline _LIBCPP_INLINE_VISIBILITY
    1700              : bool
    1701              : operator> (const map<_Key, _Tp, _Compare, _Allocator>& __x,
    1702              :            const map<_Key, _Tp, _Compare, _Allocator>& __y)
    1703              : {
    1704              :     return __y < __x;
    1705              : }
    1706              : 
    1707              : template <class _Key, class _Tp, class _Compare, class _Allocator>
    1708              : inline _LIBCPP_INLINE_VISIBILITY
    1709              : bool
    1710              : operator>=(const map<_Key, _Tp, _Compare, _Allocator>& __x,
    1711              :            const map<_Key, _Tp, _Compare, _Allocator>& __y)
    1712              : {
    1713              :     return !(__x < __y);
    1714              : }
    1715              : 
    1716              : template <class _Key, class _Tp, class _Compare, class _Allocator>
    1717              : inline _LIBCPP_INLINE_VISIBILITY
    1718              : bool
    1719              : operator<=(const map<_Key, _Tp, _Compare, _Allocator>& __x,
    1720              :            const map<_Key, _Tp, _Compare, _Allocator>& __y)
    1721              : {
    1722              :     return !(__y < __x);
    1723              : }
    1724              : 
    1725              : template <class _Key, class _Tp, class _Compare, class _Allocator>
    1726              : inline _LIBCPP_INLINE_VISIBILITY
    1727              : void
    1728              : swap(map<_Key, _Tp, _Compare, _Allocator>& __x,
    1729              :      map<_Key, _Tp, _Compare, _Allocator>& __y)
    1730              :     _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
    1731              : {
    1732              :     __x.swap(__y);
    1733              : }
    1734              : 
    1735              : #if _LIBCPP_STD_VER > 17
    1736              : template <class _Key, class _Tp, class _Compare, class _Allocator,
    1737              :           class _Predicate>
    1738              : inline _LIBCPP_INLINE_VISIBILITY
    1739              :     typename map<_Key, _Tp, _Compare, _Allocator>::size_type
    1740              :     erase_if(map<_Key, _Tp, _Compare, _Allocator>& __c, _Predicate __pred) {
    1741              :   return _VSTD::__libcpp_erase_if_container(__c, __pred);
    1742              : }
    1743              : #endif
    1744              : 
    1745              : 
    1746              : template <class _Key, class _Tp, class _Compare = less<_Key>,
    1747              :           class _Allocator = allocator<pair<const _Key, _Tp> > >
    1748              : class _LIBCPP_TEMPLATE_VIS multimap
    1749              : {
    1750              : public:
    1751              :     // types:
    1752              :     typedef _Key                                     key_type;
    1753              :     typedef _Tp                                      mapped_type;
    1754              :     typedef pair<const key_type, mapped_type>        value_type;
    1755              :     typedef __type_identity_t<_Compare>              key_compare;
    1756              :     typedef __type_identity_t<_Allocator>            allocator_type;
    1757              :     typedef value_type&                              reference;
    1758              :     typedef const value_type&                        const_reference;
    1759              : 
    1760              :     static_assert((is_same<typename allocator_type::value_type, value_type>::value),
    1761              :                   "Allocator::value_type must be same type as value_type");
    1762              : 
    1763              :     class _LIBCPP_TEMPLATE_VIS value_compare
    1764              :         : public __binary_function<value_type, value_type, bool>
    1765              :     {
    1766              :         friend class multimap;
    1767              :     protected:
    1768              :         key_compare comp;
    1769              : 
    1770              :         _LIBCPP_INLINE_VISIBILITY
    1771              :         value_compare(key_compare __c) : comp(__c) {}
    1772              :     public:
    1773              :         _LIBCPP_INLINE_VISIBILITY
    1774              :         bool operator()(const value_type& __x, const value_type& __y) const
    1775              :             {return comp(__x.first, __y.first);}
    1776              :     };
    1777              : 
    1778              : private:
    1779              : 
    1780              :     typedef _VSTD::__value_type<key_type, mapped_type>             __value_type;
    1781              :     typedef __map_value_compare<key_type, __value_type, key_compare> __vc;
    1782              :     typedef __rebind_alloc<allocator_traits<allocator_type>, __value_type> __allocator_type;
    1783              :     typedef __tree<__value_type, __vc, __allocator_type>            __base;
    1784              :     typedef typename __base::__node_traits                          __node_traits;
    1785              :     typedef allocator_traits<allocator_type>                        __alloc_traits;
    1786              : 
    1787              :     static_assert(is_same<allocator_type, __rebind_alloc<__alloc_traits, value_type> >::value,
    1788              :                   "[allocator.requirements] states that rebinding an allocator to the same type should result in the "
    1789              :                   "original allocator");
    1790              : 
    1791              :     __base __tree_;
    1792              : 
    1793              : public:
    1794              :     typedef typename __alloc_traits::pointer               pointer;
    1795              :     typedef typename __alloc_traits::const_pointer         const_pointer;
    1796              :     typedef typename __alloc_traits::size_type             size_type;
    1797              :     typedef typename __alloc_traits::difference_type       difference_type;
    1798              :     typedef __map_iterator<typename __base::iterator>      iterator;
    1799              :     typedef __map_const_iterator<typename __base::const_iterator> const_iterator;
    1800              :     typedef _VSTD::reverse_iterator<iterator>               reverse_iterator;
    1801              :     typedef _VSTD::reverse_iterator<const_iterator>         const_reverse_iterator;
    1802              : 
    1803              : #if _LIBCPP_STD_VER > 14
    1804              :     typedef __map_node_handle<typename __base::__node, allocator_type> node_type;
    1805              : #endif
    1806              : 
    1807              :     template <class _Key2, class _Value2, class _Comp2, class _Alloc2>
    1808              :         friend class _LIBCPP_TEMPLATE_VIS map;
    1809              :     template <class _Key2, class _Value2, class _Comp2, class _Alloc2>
    1810              :         friend class _LIBCPP_TEMPLATE_VIS multimap;
    1811              : 
    1812              :     _LIBCPP_INLINE_VISIBILITY
    1813              :     multimap()
    1814              :         _NOEXCEPT_(
    1815              :             is_nothrow_default_constructible<allocator_type>::value &&
    1816              :             is_nothrow_default_constructible<key_compare>::value &&
    1817              :             is_nothrow_copy_constructible<key_compare>::value)
    1818              :         : __tree_(__vc(key_compare())) {}
    1819              : 
    1820              :     _LIBCPP_INLINE_VISIBILITY
    1821              :     explicit multimap(const key_compare& __comp)
    1822              :         _NOEXCEPT_(
    1823              :             is_nothrow_default_constructible<allocator_type>::value &&
    1824              :             is_nothrow_copy_constructible<key_compare>::value)
    1825              :         : __tree_(__vc(__comp)) {}
    1826              : 
    1827              :     _LIBCPP_INLINE_VISIBILITY
    1828              :     explicit multimap(const key_compare& __comp, const allocator_type& __a)
    1829              :         : __tree_(__vc(__comp), typename __base::allocator_type(__a)) {}
    1830              : 
    1831              :     template <class _InputIterator>
    1832              :         _LIBCPP_INLINE_VISIBILITY
    1833              :         multimap(_InputIterator __f, _InputIterator __l,
    1834              :             const key_compare& __comp = key_compare())
    1835              :         : __tree_(__vc(__comp))
    1836              :         {
    1837              :             insert(__f, __l);
    1838              :         }
    1839              : 
    1840              :     template <class _InputIterator>
    1841              :         _LIBCPP_INLINE_VISIBILITY
    1842              :         multimap(_InputIterator __f, _InputIterator __l,
    1843              :             const key_compare& __comp, const allocator_type& __a)
    1844              :         : __tree_(__vc(__comp), typename __base::allocator_type(__a))
    1845              :         {
    1846              :             insert(__f, __l);
    1847              :         }
    1848              : 
    1849              : #if _LIBCPP_STD_VER > 11
    1850              :     template <class _InputIterator>
    1851              :     _LIBCPP_INLINE_VISIBILITY
    1852              :     multimap(_InputIterator __f, _InputIterator __l, const allocator_type& __a)
    1853              :         : multimap(__f, __l, key_compare(), __a) {}
    1854              : #endif
    1855              : 
    1856              :     _LIBCPP_INLINE_VISIBILITY
    1857              :     multimap(const multimap& __m)
    1858              :         : __tree_(__m.__tree_.value_comp(),
    1859              :           __alloc_traits::select_on_container_copy_construction(__m.__tree_.__alloc()))
    1860              :         {
    1861              :             insert(__m.begin(), __m.end());
    1862              :         }
    1863              : 
    1864              :     _LIBCPP_INLINE_VISIBILITY
    1865              :     multimap& operator=(const multimap& __m)
    1866              :         {
    1867              : #ifndef _LIBCPP_CXX03_LANG
    1868              :             __tree_ = __m.__tree_;
    1869              : #else
    1870              :             if (this != _VSTD::addressof(__m)) {
    1871              :                 __tree_.clear();
    1872              :                 __tree_.value_comp() = __m.__tree_.value_comp();
    1873              :                 __tree_.__copy_assign_alloc(__m.__tree_);
    1874              :                 insert(__m.begin(), __m.end());
    1875              :             }
    1876              : #endif
    1877              :             return *this;
    1878              :         }
    1879              : 
    1880              : #ifndef _LIBCPP_CXX03_LANG
    1881              : 
    1882              :     _LIBCPP_INLINE_VISIBILITY
    1883              :     multimap(multimap&& __m)
    1884              :         _NOEXCEPT_(is_nothrow_move_constructible<__base>::value)
    1885              :         : __tree_(_VSTD::move(__m.__tree_))
    1886              :         {
    1887              :         }
    1888              : 
    1889              :     multimap(multimap&& __m, const allocator_type& __a);
    1890              : 
    1891              :     _LIBCPP_INLINE_VISIBILITY
    1892              :     multimap& operator=(multimap&& __m)
    1893              :         _NOEXCEPT_(is_nothrow_move_assignable<__base>::value)
    1894              :         {
    1895              :             __tree_ = _VSTD::move(__m.__tree_);
    1896              :             return *this;
    1897              :         }
    1898              : 
    1899              :     _LIBCPP_INLINE_VISIBILITY
    1900              :     multimap(initializer_list<value_type> __il, const key_compare& __comp = key_compare())
    1901              :         : __tree_(__vc(__comp))
    1902              :         {
    1903              :             insert(__il.begin(), __il.end());
    1904              :         }
    1905              : 
    1906              :     _LIBCPP_INLINE_VISIBILITY
    1907              :     multimap(initializer_list<value_type> __il, const key_compare& __comp, const allocator_type& __a)
    1908              :         : __tree_(__vc(__comp), typename __base::allocator_type(__a))
    1909              :         {
    1910              :             insert(__il.begin(), __il.end());
    1911              :         }
    1912              : 
    1913              : #if _LIBCPP_STD_VER > 11
    1914              :     _LIBCPP_INLINE_VISIBILITY
    1915              :     multimap(initializer_list<value_type> __il, const allocator_type& __a)
    1916              :         : multimap(__il, key_compare(), __a) {}
    1917              : #endif
    1918              : 
    1919              :     _LIBCPP_INLINE_VISIBILITY
    1920              :     multimap& operator=(initializer_list<value_type> __il)
    1921              :         {
    1922              :             __tree_.__assign_multi(__il.begin(), __il.end());
    1923              :             return *this;
    1924              :         }
    1925              : 
    1926              : #endif // _LIBCPP_CXX03_LANG
    1927              : 
    1928              :     _LIBCPP_INLINE_VISIBILITY
    1929              :     explicit multimap(const allocator_type& __a)
    1930              :         : __tree_(typename __base::allocator_type(__a))
    1931              :         {
    1932              :         }
    1933              : 
    1934              :     _LIBCPP_INLINE_VISIBILITY
    1935              :     multimap(const multimap& __m, const allocator_type& __a)
    1936              :         : __tree_(__m.__tree_.value_comp(), typename __base::allocator_type(__a))
    1937              :         {
    1938              :             insert(__m.begin(), __m.end());
    1939              :         }
    1940              : 
    1941              :     _LIBCPP_INLINE_VISIBILITY
    1942              :     ~multimap() {
    1943              :         static_assert(sizeof(__diagnose_non_const_comparator<_Key, _Compare>()), "");
    1944              :     }
    1945              : 
    1946              :     _LIBCPP_INLINE_VISIBILITY
    1947              :           iterator begin() _NOEXCEPT {return __tree_.begin();}
    1948              :     _LIBCPP_INLINE_VISIBILITY
    1949              :     const_iterator begin() const _NOEXCEPT {return __tree_.begin();}
    1950              :     _LIBCPP_INLINE_VISIBILITY
    1951              :           iterator end() _NOEXCEPT {return __tree_.end();}
    1952              :     _LIBCPP_INLINE_VISIBILITY
    1953              :     const_iterator end() const _NOEXCEPT {return __tree_.end();}
    1954              : 
    1955              :     _LIBCPP_INLINE_VISIBILITY
    1956              :           reverse_iterator rbegin() _NOEXCEPT {return reverse_iterator(end());}
    1957              :     _LIBCPP_INLINE_VISIBILITY
    1958              :     const_reverse_iterator rbegin() const _NOEXCEPT
    1959              :         {return const_reverse_iterator(end());}
    1960              :     _LIBCPP_INLINE_VISIBILITY
    1961              :           reverse_iterator rend() _NOEXCEPT {return reverse_iterator(begin());}
    1962              :     _LIBCPP_INLINE_VISIBILITY
    1963              :     const_reverse_iterator rend() const _NOEXCEPT
    1964              :         {return const_reverse_iterator(begin());}
    1965              : 
    1966              :     _LIBCPP_INLINE_VISIBILITY
    1967              :     const_iterator cbegin()  const _NOEXCEPT {return begin();}
    1968              :     _LIBCPP_INLINE_VISIBILITY
    1969              :     const_iterator cend() const _NOEXCEPT {return end();}
    1970              :     _LIBCPP_INLINE_VISIBILITY
    1971              :     const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();}
    1972              :     _LIBCPP_INLINE_VISIBILITY
    1973              :     const_reverse_iterator crend() const _NOEXCEPT {return rend();}
    1974              : 
    1975              :     _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY
    1976              :     bool empty() const _NOEXCEPT {return __tree_.size() == 0;}
    1977              :     _LIBCPP_INLINE_VISIBILITY
    1978              :     size_type size() const _NOEXCEPT {return __tree_.size();}
    1979              :     _LIBCPP_INLINE_VISIBILITY
    1980              :     size_type max_size() const _NOEXCEPT {return __tree_.max_size();}
    1981              : 
    1982              :     _LIBCPP_INLINE_VISIBILITY
    1983              :     allocator_type get_allocator() const _NOEXCEPT {return allocator_type(__tree_.__alloc());}
    1984              :     _LIBCPP_INLINE_VISIBILITY
    1985              :     key_compare    key_comp() const {return __tree_.value_comp().key_comp();}
    1986              :     _LIBCPP_INLINE_VISIBILITY
    1987              :     value_compare  value_comp() const
    1988              :         {return value_compare(__tree_.value_comp().key_comp());}
    1989              : 
    1990              : #ifndef _LIBCPP_CXX03_LANG
    1991              : 
    1992              :     template <class ..._Args>
    1993              :     _LIBCPP_INLINE_VISIBILITY
    1994              :     iterator emplace(_Args&& ...__args) {
    1995              :         return __tree_.__emplace_multi(_VSTD::forward<_Args>(__args)...);
    1996              :     }
    1997              : 
    1998              :     template <class ..._Args>
    1999              :     _LIBCPP_INLINE_VISIBILITY
    2000              :     iterator emplace_hint(const_iterator __p, _Args&& ...__args) {
    2001              :         return __tree_.__emplace_hint_multi(__p.__i_, _VSTD::forward<_Args>(__args)...);
    2002              :     }
    2003              : 
    2004              :     template <class _Pp,
    2005              :               class = __enable_if_t<is_constructible<value_type, _Pp>::value>>
    2006              :         _LIBCPP_INLINE_VISIBILITY
    2007              :         iterator insert(_Pp&& __p)
    2008              :             {return __tree_.__insert_multi(_VSTD::forward<_Pp>(__p));}
    2009              : 
    2010              :     template <class _Pp,
    2011              :               class = __enable_if_t<is_constructible<value_type, _Pp>::value>>
    2012              :         _LIBCPP_INLINE_VISIBILITY
    2013              :         iterator insert(const_iterator __pos, _Pp&& __p)
    2014              :             {return __tree_.__insert_multi(__pos.__i_, _VSTD::forward<_Pp>(__p));}
    2015              : 
    2016              :     _LIBCPP_INLINE_VISIBILITY
    2017              :     iterator insert(value_type&& __v)
    2018              :         {return __tree_.__insert_multi(_VSTD::move(__v));}
    2019              : 
    2020              :     _LIBCPP_INLINE_VISIBILITY
    2021              :     iterator insert(const_iterator __p, value_type&& __v)
    2022              :         {return __tree_.__insert_multi(__p.__i_, _VSTD::move(__v));}
    2023              : 
    2024              : 
    2025              :     _LIBCPP_INLINE_VISIBILITY
    2026              :     void insert(initializer_list<value_type> __il)
    2027              :         {insert(__il.begin(), __il.end());}
    2028              : 
    2029              : #endif // _LIBCPP_CXX03_LANG
    2030              : 
    2031              :     _LIBCPP_INLINE_VISIBILITY
    2032              :     iterator insert(const value_type& __v) {return __tree_.__insert_multi(__v);}
    2033              : 
    2034              :     _LIBCPP_INLINE_VISIBILITY
    2035              :     iterator insert(const_iterator __p, const value_type& __v)
    2036              :             {return __tree_.__insert_multi(__p.__i_, __v);}
    2037              : 
    2038              :     template <class _InputIterator>
    2039              :         _LIBCPP_INLINE_VISIBILITY
    2040              :         void insert(_InputIterator __f, _InputIterator __l)
    2041              :         {
    2042              :             for (const_iterator __e = cend(); __f != __l; ++__f)
    2043              :                 __tree_.__insert_multi(__e.__i_, *__f);
    2044              :         }
    2045              : 
    2046              :     _LIBCPP_INLINE_VISIBILITY
    2047              :     iterator erase(const_iterator __p) {return __tree_.erase(__p.__i_);}
    2048              :     _LIBCPP_INLINE_VISIBILITY
    2049              :     iterator erase(iterator __p)       {return __tree_.erase(__p.__i_);}
    2050              :     _LIBCPP_INLINE_VISIBILITY
    2051              :     size_type erase(const key_type& __k) {return __tree_.__erase_multi(__k);}
    2052              :     _LIBCPP_INLINE_VISIBILITY
    2053              :     iterator  erase(const_iterator __f, const_iterator __l)
    2054              :         {return __tree_.erase(__f.__i_, __l.__i_);}
    2055              : 
    2056              : #if _LIBCPP_STD_VER > 14
    2057              :     _LIBCPP_INLINE_VISIBILITY
    2058              :     iterator insert(node_type&& __nh)
    2059              :     {
    2060              :         _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(),
    2061              :             "node_type with incompatible allocator passed to multimap::insert()");
    2062              :         return __tree_.template __node_handle_insert_multi<node_type>(
    2063              :             _VSTD::move(__nh));
    2064              :     }
    2065              :     _LIBCPP_INLINE_VISIBILITY
    2066              :     iterator insert(const_iterator __hint, node_type&& __nh)
    2067              :     {
    2068              :         _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(),
    2069              :             "node_type with incompatible allocator passed to multimap::insert()");
    2070              :         return __tree_.template __node_handle_insert_multi<node_type>(
    2071              :             __hint.__i_, _VSTD::move(__nh));
    2072              :     }
    2073              :     _LIBCPP_INLINE_VISIBILITY
    2074              :     node_type extract(key_type const& __key)
    2075              :     {
    2076              :         return __tree_.template __node_handle_extract<node_type>(__key);
    2077              :     }
    2078              :     _LIBCPP_INLINE_VISIBILITY
    2079              :     node_type extract(const_iterator __it)
    2080              :     {
    2081              :         return __tree_.template __node_handle_extract<node_type>(
    2082              :             __it.__i_);
    2083              :     }
    2084              :     template <class _Compare2>
    2085              :     _LIBCPP_INLINE_VISIBILITY
    2086              :     void merge(multimap<key_type, mapped_type, _Compare2, allocator_type>& __source)
    2087              :     {
    2088              :         _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
    2089              :                        "merging container with incompatible allocator");
    2090              :         return __tree_.__node_handle_merge_multi(__source.__tree_);
    2091              :     }
    2092              :     template <class _Compare2>
    2093              :     _LIBCPP_INLINE_VISIBILITY
    2094              :     void merge(multimap<key_type, mapped_type, _Compare2, allocator_type>&& __source)
    2095              :     {
    2096              :         _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
    2097              :                        "merging container with incompatible allocator");
    2098              :         return __tree_.__node_handle_merge_multi(__source.__tree_);
    2099              :     }
    2100              :     template <class _Compare2>
    2101              :     _LIBCPP_INLINE_VISIBILITY
    2102              :     void merge(map<key_type, mapped_type, _Compare2, allocator_type>& __source)
    2103              :     {
    2104              :         _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
    2105              :                        "merging container with incompatible allocator");
    2106              :         return __tree_.__node_handle_merge_multi(__source.__tree_);
    2107              :     }
    2108              :     template <class _Compare2>
    2109              :     _LIBCPP_INLINE_VISIBILITY
    2110              :     void merge(map<key_type, mapped_type, _Compare2, allocator_type>&& __source)
    2111              :     {
    2112              :         _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
    2113              :                        "merging container with incompatible allocator");
    2114              :         return __tree_.__node_handle_merge_multi(__source.__tree_);
    2115              :     }
    2116              : #endif
    2117              : 
    2118              :     _LIBCPP_INLINE_VISIBILITY
    2119              :     void clear() _NOEXCEPT {__tree_.clear();}
    2120              : 
    2121              :     _LIBCPP_INLINE_VISIBILITY
    2122              :     void swap(multimap& __m)
    2123              :         _NOEXCEPT_(__is_nothrow_swappable<__base>::value)
    2124              :         {__tree_.swap(__m.__tree_);}
    2125              : 
    2126              :     _LIBCPP_INLINE_VISIBILITY
    2127              :     iterator find(const key_type& __k)             {return __tree_.find(__k);}
    2128              :     _LIBCPP_INLINE_VISIBILITY
    2129              :     const_iterator find(const key_type& __k) const {return __tree_.find(__k);}
    2130              : #if _LIBCPP_STD_VER > 11
    2131              :     template <typename _K2>
    2132              :     _LIBCPP_INLINE_VISIBILITY
    2133              :     __enable_if_t<__is_transparent<_Compare, _K2>::value, iterator>
    2134              :     find(const _K2& __k)                           {return __tree_.find(__k);}
    2135              :     template <typename _K2>
    2136              :     _LIBCPP_INLINE_VISIBILITY
    2137              :     __enable_if_t<__is_transparent<_Compare, _K2>::value, const_iterator>
    2138              :     find(const _K2& __k) const                     {return __tree_.find(__k);}
    2139              : #endif
    2140              : 
    2141              :     _LIBCPP_INLINE_VISIBILITY
    2142              :     size_type      count(const key_type& __k) const
    2143              :         {return __tree_.__count_multi(__k);}
    2144              : #if _LIBCPP_STD_VER > 11
    2145              :     template <typename _K2>
    2146              :     _LIBCPP_INLINE_VISIBILITY
    2147              :     __enable_if_t<__is_transparent<_Compare, _K2>::value, size_type>
    2148              :     count(const _K2& __k) const {return __tree_.__count_multi(__k);}
    2149              : #endif
    2150              : 
    2151              : #if _LIBCPP_STD_VER > 17
    2152              :     _LIBCPP_INLINE_VISIBILITY
    2153              :     bool contains(const key_type& __k) const {return find(__k) != end();}
    2154              :     template <typename _K2>
    2155              :     _LIBCPP_INLINE_VISIBILITY
    2156              :     __enable_if_t<__is_transparent<_Compare, _K2>::value, bool>
    2157              :     contains(const _K2& __k) const { return find(__k) != end(); }
    2158              : #endif // _LIBCPP_STD_VER > 17
    2159              : 
    2160              :     _LIBCPP_INLINE_VISIBILITY
    2161              :     iterator lower_bound(const key_type& __k)
    2162              :         {return __tree_.lower_bound(__k);}
    2163              :     _LIBCPP_INLINE_VISIBILITY
    2164              :     const_iterator lower_bound(const key_type& __k) const
    2165              :             {return __tree_.lower_bound(__k);}
    2166              : #if _LIBCPP_STD_VER > 11
    2167              :     template <typename _K2>
    2168              :     _LIBCPP_INLINE_VISIBILITY
    2169              :     __enable_if_t<__is_transparent<_Compare, _K2>::value, iterator>
    2170              :     lower_bound(const _K2& __k)       {return __tree_.lower_bound(__k);}
    2171              : 
    2172              :     template <typename _K2>
    2173              :     _LIBCPP_INLINE_VISIBILITY
    2174              :     __enable_if_t<__is_transparent<_Compare, _K2>::value, const_iterator>
    2175              :     lower_bound(const _K2& __k) const {return __tree_.lower_bound(__k);}
    2176              : #endif
    2177              : 
    2178              :     _LIBCPP_INLINE_VISIBILITY
    2179              :     iterator upper_bound(const key_type& __k)
    2180              :             {return __tree_.upper_bound(__k);}
    2181              :     _LIBCPP_INLINE_VISIBILITY
    2182              :     const_iterator upper_bound(const key_type& __k) const
    2183              :             {return __tree_.upper_bound(__k);}
    2184              : #if _LIBCPP_STD_VER > 11
    2185              :     template <typename _K2>
    2186              :     _LIBCPP_INLINE_VISIBILITY
    2187              :     __enable_if_t<__is_transparent<_Compare, _K2>::value, iterator>
    2188              :     upper_bound(const _K2& __k)       {return __tree_.upper_bound(__k);}
    2189              :     template <typename _K2>
    2190              :     _LIBCPP_INLINE_VISIBILITY
    2191              :     __enable_if_t<__is_transparent<_Compare, _K2>::value, const_iterator>
    2192              :     upper_bound(const _K2& __k) const {return __tree_.upper_bound(__k);}
    2193              : #endif
    2194              : 
    2195              :     _LIBCPP_INLINE_VISIBILITY
    2196              :     pair<iterator,iterator>             equal_range(const key_type& __k)
    2197              :             {return __tree_.__equal_range_multi(__k);}
    2198              :     _LIBCPP_INLINE_VISIBILITY
    2199              :     pair<const_iterator,const_iterator> equal_range(const key_type& __k) const
    2200              :             {return __tree_.__equal_range_multi(__k);}
    2201              : #if _LIBCPP_STD_VER > 11
    2202              :     template <typename _K2>
    2203              :     _LIBCPP_INLINE_VISIBILITY
    2204              :     __enable_if_t<__is_transparent<_Compare, _K2>::value, pair<iterator,iterator>>
    2205              :     equal_range(const _K2& __k)       {return __tree_.__equal_range_multi(__k);}
    2206              :     template <typename _K2>
    2207              :     _LIBCPP_INLINE_VISIBILITY
    2208              :     __enable_if_t<__is_transparent<_Compare, _K2>::value, pair<const_iterator,const_iterator>>
    2209              :     equal_range(const _K2& __k) const {return __tree_.__equal_range_multi(__k);}
    2210              : #endif
    2211              : 
    2212              : private:
    2213              :     typedef typename __base::__node                    __node;
    2214              :     typedef typename __base::__node_allocator          __node_allocator;
    2215              :     typedef typename __base::__node_pointer            __node_pointer;
    2216              : 
    2217              :     typedef __map_node_destructor<__node_allocator> _Dp;
    2218              :     typedef unique_ptr<__node, _Dp> __node_holder;
    2219              : };
    2220              : 
    2221              : #if _LIBCPP_STD_VER >= 17
    2222              : template<class _InputIterator, class _Compare = less<__iter_key_type<_InputIterator>>,
    2223              :          class _Allocator = allocator<__iter_to_alloc_type<_InputIterator>>,
    2224              :          class = enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value, void>,
    2225              :          class = enable_if_t<!__is_allocator<_Compare>::value, void>,
    2226              :          class = enable_if_t<__is_allocator<_Allocator>::value, void>>
    2227              : multimap(_InputIterator, _InputIterator, _Compare = _Compare(), _Allocator = _Allocator())
    2228              :   -> multimap<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>, _Compare, _Allocator>;
    2229              : 
    2230              : template<class _Key, class _Tp, class _Compare = less<remove_const_t<_Key>>,
    2231              :          class _Allocator = allocator<pair<const _Key, _Tp>>,
    2232              :          class = enable_if_t<!__is_allocator<_Compare>::value, void>,
    2233              :          class = enable_if_t<__is_allocator<_Allocator>::value, void>>
    2234              : multimap(initializer_list<pair<_Key, _Tp>>, _Compare = _Compare(), _Allocator = _Allocator())
    2235              :   -> multimap<remove_const_t<_Key>, _Tp, _Compare, _Allocator>;
    2236              : 
    2237              : template<class _InputIterator, class _Allocator,
    2238              :          class = enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value, void>,
    2239              :          class = enable_if_t<__is_allocator<_Allocator>::value, void>>
    2240              : multimap(_InputIterator, _InputIterator, _Allocator)
    2241              :   -> multimap<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>,
    2242              :          less<__iter_key_type<_InputIterator>>, _Allocator>;
    2243              : 
    2244              : template<class _Key, class _Tp, class _Allocator,
    2245              :          class = enable_if_t<__is_allocator<_Allocator>::value, void>>
    2246              : multimap(initializer_list<pair<_Key, _Tp>>, _Allocator)
    2247              :   -> multimap<remove_const_t<_Key>, _Tp, less<remove_const_t<_Key>>, _Allocator>;
    2248              : #endif
    2249              : 
    2250              : #ifndef _LIBCPP_CXX03_LANG
    2251              : template <class _Key, class _Tp, class _Compare, class _Allocator>
    2252              : multimap<_Key, _Tp, _Compare, _Allocator>::multimap(multimap&& __m, const allocator_type& __a)
    2253              :     : __tree_(_VSTD::move(__m.__tree_), typename __base::allocator_type(__a))
    2254              : {
    2255              :     if (__a != __m.get_allocator())
    2256              :     {
    2257              :         const_iterator __e = cend();
    2258              :         while (!__m.empty())
    2259              :             __tree_.__insert_multi(__e.__i_,
    2260              :                     _VSTD::move(__m.__tree_.remove(__m.begin().__i_)->__value_.__move()));
    2261              :     }
    2262              : }
    2263              : #endif
    2264              : 
    2265              : template <class _Key, class _Tp, class _Compare, class _Allocator>
    2266              : inline _LIBCPP_INLINE_VISIBILITY
    2267              : bool
    2268              : operator==(const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
    2269              :            const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
    2270              : {
    2271              :     return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin());
    2272              : }
    2273              : 
    2274              : template <class _Key, class _Tp, class _Compare, class _Allocator>
    2275              : inline _LIBCPP_INLINE_VISIBILITY
    2276              : bool
    2277              : operator< (const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
    2278              :            const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
    2279              : {
    2280              :     return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
    2281              : }
    2282              : 
    2283              : template <class _Key, class _Tp, class _Compare, class _Allocator>
    2284              : inline _LIBCPP_INLINE_VISIBILITY
    2285              : bool
    2286              : operator!=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
    2287              :            const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
    2288              : {
    2289              :     return !(__x == __y);
    2290              : }
    2291              : 
    2292              : template <class _Key, class _Tp, class _Compare, class _Allocator>
    2293              : inline _LIBCPP_INLINE_VISIBILITY
    2294              : bool
    2295              : operator> (const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
    2296              :            const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
    2297              : {
    2298              :     return __y < __x;
    2299              : }
    2300              : 
    2301              : template <class _Key, class _Tp, class _Compare, class _Allocator>
    2302              : inline _LIBCPP_INLINE_VISIBILITY
    2303              : bool
    2304              : operator>=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
    2305              :            const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
    2306              : {
    2307              :     return !(__x < __y);
    2308              : }
    2309              : 
    2310              : template <class _Key, class _Tp, class _Compare, class _Allocator>
    2311              : inline _LIBCPP_INLINE_VISIBILITY
    2312              : bool
    2313              : operator<=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
    2314              :            const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
    2315              : {
    2316              :     return !(__y < __x);
    2317              : }
    2318              : 
    2319              : template <class _Key, class _Tp, class _Compare, class _Allocator>
    2320              : inline _LIBCPP_INLINE_VISIBILITY
    2321              : void
    2322              : swap(multimap<_Key, _Tp, _Compare, _Allocator>& __x,
    2323              :      multimap<_Key, _Tp, _Compare, _Allocator>& __y)
    2324              :     _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
    2325              : {
    2326              :     __x.swap(__y);
    2327              : }
    2328              : 
    2329              : #if _LIBCPP_STD_VER > 17
    2330              : template <class _Key, class _Tp, class _Compare, class _Allocator,
    2331              :           class _Predicate>
    2332              : inline _LIBCPP_INLINE_VISIBILITY
    2333              :     typename multimap<_Key, _Tp, _Compare, _Allocator>::size_type
    2334              :     erase_if(multimap<_Key, _Tp, _Compare, _Allocator>& __c,
    2335              :              _Predicate __pred) {
    2336              :   return _VSTD::__libcpp_erase_if_container(__c, __pred);
    2337              : }
    2338              : #endif
    2339              : 
    2340              : _LIBCPP_END_NAMESPACE_STD
    2341              : 
    2342              : #if _LIBCPP_STD_VER > 14
    2343              : _LIBCPP_BEGIN_NAMESPACE_STD
    2344              : namespace pmr {
    2345              : template <class _KeyT, class _ValueT, class _CompareT = std::less<_KeyT>>
    2346              : using map = std::map<_KeyT, _ValueT, _CompareT, polymorphic_allocator<std::pair<const _KeyT, _ValueT>>>;
    2347              : 
    2348              : template <class _KeyT, class _ValueT, class _CompareT = std::less<_KeyT>>
    2349              : using multimap = std::multimap<_KeyT, _ValueT, _CompareT, polymorphic_allocator<std::pair<const _KeyT, _ValueT>>>;
    2350              : } // namespace pmr
    2351              : _LIBCPP_END_NAMESPACE_STD
    2352              : #endif
    2353              : 
    2354              : #if !defined(_LIBCPP_REMOVE_TRANSITIVE_INCLUDES) && _LIBCPP_STD_VER <= 20
    2355              : #  include <concepts>
    2356              : #  include <functional>
    2357              : #  include <iterator>
    2358              : #  include <utility>
    2359              : #endif
    2360              : 
    2361              : #endif // _LIBCPP_MAP
        

Generated by: LCOV version 2.0-1