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