xref: /freebsd/contrib/llvm-project/libcxx/include/map (revision 6580f5c38dd5b01aeeaed16b370f1a12423437f0)
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> // all public C++ headers provide the assertion handler
578#include <__availability>
579#include <__config>
580#include <__functional/binary_function.h>
581#include <__functional/is_transparent.h>
582#include <__functional/operations.h>
583#include <__iterator/erase_if_container.h>
584#include <__iterator/iterator_traits.h>
585#include <__iterator/ranges_iterator_traits.h>
586#include <__iterator/reverse_iterator.h>
587#include <__memory/addressof.h>
588#include <__memory/allocator.h>
589#include <__memory_resource/polymorphic_allocator.h>
590#include <__node_handle>
591#include <__ranges/concepts.h>
592#include <__ranges/container_compatible_range.h>
593#include <__ranges/from_range.h>
594#include <__tree>
595#include <__type_traits/is_allocator.h>
596#include <__utility/forward.h>
597#include <__utility/piecewise_construct.h>
598#include <__utility/swap.h>
599#include <stdexcept>
600#include <tuple>
601#include <version>
602
603// standard-mandated includes
604
605// [iterator.range]
606#include <__iterator/access.h>
607#include <__iterator/data.h>
608#include <__iterator/empty.h>
609#include <__iterator/reverse_access.h>
610#include <__iterator/size.h>
611
612// [associative.map.syn]
613#include <compare>
614#include <initializer_list>
615
616#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
617#  pragma GCC system_header
618#endif
619
620_LIBCPP_PUSH_MACROS
621#include <__undef_macros>
622
623_LIBCPP_BEGIN_NAMESPACE_STD
624
625template <class _Key,
626          class _CP,
627          class _Compare,
628          bool = is_empty<_Compare>::value && !__libcpp_is_final<_Compare>::value>
629class __map_value_compare : private _Compare {
630public:
631  _LIBCPP_HIDE_FROM_ABI __map_value_compare() _NOEXCEPT_(is_nothrow_default_constructible<_Compare>::value)
632      : _Compare() {}
633  _LIBCPP_HIDE_FROM_ABI __map_value_compare(_Compare __c) _NOEXCEPT_(is_nothrow_copy_constructible<_Compare>::value)
634      : _Compare(__c) {}
635  _LIBCPP_HIDE_FROM_ABI const _Compare& key_comp() const _NOEXCEPT { return *this; }
636  _LIBCPP_HIDE_FROM_ABI bool operator()(const _CP& __x, const _CP& __y) const {
637    return static_cast<const _Compare&>(*this)(__x.__get_value().first, __y.__get_value().first);
638  }
639  _LIBCPP_HIDE_FROM_ABI bool operator()(const _CP& __x, const _Key& __y) const {
640    return static_cast<const _Compare&>(*this)(__x.__get_value().first, __y);
641  }
642  _LIBCPP_HIDE_FROM_ABI bool operator()(const _Key& __x, const _CP& __y) const {
643    return static_cast<const _Compare&>(*this)(__x, __y.__get_value().first);
644  }
645  _LIBCPP_HIDE_FROM_ABI void swap(__map_value_compare& __y) _NOEXCEPT_(__is_nothrow_swappable<_Compare>::value) {
646    using std::swap;
647    swap(static_cast<_Compare&>(*this), static_cast<_Compare&>(__y));
648  }
649
650#if _LIBCPP_STD_VER >= 14
651  template <typename _K2>
652  _LIBCPP_HIDE_FROM_ABI bool operator()(const _K2& __x, const _CP& __y) const {
653    return static_cast<const _Compare&>(*this)(__x, __y.__get_value().first);
654  }
655
656  template <typename _K2>
657  _LIBCPP_HIDE_FROM_ABI bool operator()(const _CP& __x, const _K2& __y) const {
658    return static_cast<const _Compare&>(*this)(__x.__get_value().first, __y);
659  }
660#endif
661};
662
663template <class _Key, class _CP, class _Compare>
664class __map_value_compare<_Key, _CP, _Compare, false> {
665  _Compare __comp_;
666
667public:
668  _LIBCPP_HIDE_FROM_ABI __map_value_compare() _NOEXCEPT_(is_nothrow_default_constructible<_Compare>::value)
669      : __comp_() {}
670  _LIBCPP_HIDE_FROM_ABI __map_value_compare(_Compare __c) _NOEXCEPT_(is_nothrow_copy_constructible<_Compare>::value)
671      : __comp_(__c) {}
672  _LIBCPP_HIDE_FROM_ABI const _Compare& key_comp() const _NOEXCEPT { return __comp_; }
673
674  _LIBCPP_HIDE_FROM_ABI bool operator()(const _CP& __x, const _CP& __y) const {
675    return __comp_(__x.__get_value().first, __y.__get_value().first);
676  }
677  _LIBCPP_HIDE_FROM_ABI bool operator()(const _CP& __x, const _Key& __y) const {
678    return __comp_(__x.__get_value().first, __y);
679  }
680  _LIBCPP_HIDE_FROM_ABI bool operator()(const _Key& __x, const _CP& __y) const {
681    return __comp_(__x, __y.__get_value().first);
682  }
683  void swap(__map_value_compare& __y) _NOEXCEPT_(__is_nothrow_swappable<_Compare>::value) {
684    using std::swap;
685    swap(__comp_, __y.__comp_);
686  }
687
688#if _LIBCPP_STD_VER >= 14
689  template <typename _K2>
690  _LIBCPP_HIDE_FROM_ABI bool operator()(const _K2& __x, const _CP& __y) const {
691    return __comp_(__x, __y.__get_value().first);
692  }
693
694  template <typename _K2>
695  _LIBCPP_HIDE_FROM_ABI bool operator()(const _CP& __x, const _K2& __y) const {
696    return __comp_(__x.__get_value().first, __y);
697  }
698#endif
699};
700
701template <class _Key, class _CP, class _Compare, bool __b>
702inline _LIBCPP_HIDE_FROM_ABI void
703swap(__map_value_compare<_Key, _CP, _Compare, __b>& __x, __map_value_compare<_Key, _CP, _Compare, __b>& __y)
704    _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) {
705  __x.swap(__y);
706}
707
708template <class _Allocator>
709class __map_node_destructor {
710  typedef _Allocator allocator_type;
711  typedef allocator_traits<allocator_type> __alloc_traits;
712
713public:
714  typedef typename __alloc_traits::pointer pointer;
715
716private:
717  allocator_type& __na_;
718
719  __map_node_destructor& operator=(const __map_node_destructor&);
720
721public:
722  bool __first_constructed;
723  bool __second_constructed;
724
725  _LIBCPP_HIDE_FROM_ABI explicit __map_node_destructor(allocator_type& __na) _NOEXCEPT
726      : __na_(__na),
727        __first_constructed(false),
728        __second_constructed(false) {}
729
730#ifndef _LIBCPP_CXX03_LANG
731  _LIBCPP_HIDE_FROM_ABI __map_node_destructor(__tree_node_destructor<allocator_type>&& __x) _NOEXCEPT
732      : __na_(__x.__na_),
733        __first_constructed(__x.__value_constructed),
734        __second_constructed(__x.__value_constructed) {
735    __x.__value_constructed = false;
736  }
737#endif // _LIBCPP_CXX03_LANG
738
739  _LIBCPP_HIDE_FROM_ABI void operator()(pointer __p) _NOEXCEPT {
740    if (__second_constructed)
741      __alloc_traits::destroy(__na_, std::addressof(__p->__value_.__get_value().second));
742    if (__first_constructed)
743      __alloc_traits::destroy(__na_, std::addressof(__p->__value_.__get_value().first));
744    if (__p)
745      __alloc_traits::deallocate(__na_, __p, 1);
746  }
747};
748
749template <class _Key, class _Tp, class _Compare, class _Allocator>
750class map;
751template <class _Key, class _Tp, class _Compare, class _Allocator>
752class multimap;
753template <class _TreeIterator>
754class __map_const_iterator;
755
756#ifndef _LIBCPP_CXX03_LANG
757
758template <class _Key, class _Tp>
759struct _LIBCPP_STANDALONE_DEBUG __value_type {
760  typedef _Key key_type;
761  typedef _Tp mapped_type;
762  typedef pair<const key_type, mapped_type> value_type;
763  typedef pair<key_type&, mapped_type&> __nc_ref_pair_type;
764  typedef pair<key_type&&, mapped_type&&> __nc_rref_pair_type;
765
766private:
767  value_type __cc_;
768
769public:
770  _LIBCPP_HIDE_FROM_ABI value_type& __get_value() {
771#  if _LIBCPP_STD_VER >= 17
772    return *std::launder(std::addressof(__cc_));
773#  else
774    return __cc_;
775#  endif
776  }
777
778  _LIBCPP_HIDE_FROM_ABI const value_type& __get_value() const {
779#  if _LIBCPP_STD_VER >= 17
780    return *std::launder(std::addressof(__cc_));
781#  else
782    return __cc_;
783#  endif
784  }
785
786  _LIBCPP_HIDE_FROM_ABI __nc_ref_pair_type __ref() {
787    value_type& __v = __get_value();
788    return __nc_ref_pair_type(const_cast<key_type&>(__v.first), __v.second);
789  }
790
791  _LIBCPP_HIDE_FROM_ABI __nc_rref_pair_type __move() {
792    value_type& __v = __get_value();
793    return __nc_rref_pair_type(std::move(const_cast<key_type&>(__v.first)), std::move(__v.second));
794  }
795
796  _LIBCPP_HIDE_FROM_ABI __value_type& operator=(const __value_type& __v) {
797    __ref() = __v.__get_value();
798    return *this;
799  }
800
801  _LIBCPP_HIDE_FROM_ABI __value_type& operator=(__value_type&& __v) {
802    __ref() = __v.__move();
803    return *this;
804  }
805
806  template <class _ValueTp, class = __enable_if_t<__is_same_uncvref<_ValueTp, value_type>::value> >
807  _LIBCPP_HIDE_FROM_ABI __value_type& operator=(_ValueTp&& __v) {
808    __ref() = std::forward<_ValueTp>(__v);
809    return *this;
810  }
811
812private:
813  __value_type()                    = delete;
814  ~__value_type()                   = delete;
815  __value_type(const __value_type&) = delete;
816  __value_type(__value_type&&)      = delete;
817};
818
819#else
820
821template <class _Key, class _Tp>
822struct __value_type {
823  typedef _Key key_type;
824  typedef _Tp mapped_type;
825  typedef pair<const key_type, mapped_type> value_type;
826
827private:
828  value_type __cc_;
829
830public:
831  _LIBCPP_HIDE_FROM_ABI value_type& __get_value() { return __cc_; }
832  _LIBCPP_HIDE_FROM_ABI const value_type& __get_value() const { return __cc_; }
833
834private:
835  __value_type();
836  __value_type(__value_type const&);
837  __value_type& operator=(__value_type const&);
838  ~__value_type();
839};
840
841#endif // _LIBCPP_CXX03_LANG
842
843template <class _Tp>
844struct __extract_key_value_types;
845
846template <class _Key, class _Tp>
847struct __extract_key_value_types<__value_type<_Key, _Tp> > {
848  typedef _Key const __key_type;
849  typedef _Tp __mapped_type;
850};
851
852template <class _TreeIterator>
853class _LIBCPP_TEMPLATE_VIS __map_iterator {
854  typedef typename _TreeIterator::_NodeTypes _NodeTypes;
855  typedef typename _TreeIterator::__pointer_traits __pointer_traits;
856
857  _TreeIterator __i_;
858
859public:
860  typedef bidirectional_iterator_tag iterator_category;
861  typedef typename _NodeTypes::__map_value_type value_type;
862  typedef typename _TreeIterator::difference_type difference_type;
863  typedef value_type& reference;
864  typedef typename _NodeTypes::__map_value_type_pointer pointer;
865
866  _LIBCPP_HIDE_FROM_ABI __map_iterator() _NOEXCEPT {}
867
868  _LIBCPP_HIDE_FROM_ABI __map_iterator(_TreeIterator __i) _NOEXCEPT : __i_(__i) {}
869
870  _LIBCPP_HIDE_FROM_ABI reference operator*() const { return __i_->__get_value(); }
871  _LIBCPP_HIDE_FROM_ABI pointer operator->() const { return pointer_traits<pointer>::pointer_to(__i_->__get_value()); }
872
873  _LIBCPP_HIDE_FROM_ABI __map_iterator& operator++() {
874    ++__i_;
875    return *this;
876  }
877  _LIBCPP_HIDE_FROM_ABI __map_iterator operator++(int) {
878    __map_iterator __t(*this);
879    ++(*this);
880    return __t;
881  }
882
883  _LIBCPP_HIDE_FROM_ABI __map_iterator& operator--() {
884    --__i_;
885    return *this;
886  }
887  _LIBCPP_HIDE_FROM_ABI __map_iterator operator--(int) {
888    __map_iterator __t(*this);
889    --(*this);
890    return __t;
891  }
892
893  friend _LIBCPP_HIDE_FROM_ABI bool operator==(const __map_iterator& __x, const __map_iterator& __y) {
894    return __x.__i_ == __y.__i_;
895  }
896  friend _LIBCPP_HIDE_FROM_ABI bool operator!=(const __map_iterator& __x, const __map_iterator& __y) {
897    return __x.__i_ != __y.__i_;
898  }
899
900  template <class, class, class, class>
901  friend class _LIBCPP_TEMPLATE_VIS map;
902  template <class, class, class, class>
903  friend class _LIBCPP_TEMPLATE_VIS multimap;
904  template <class>
905  friend class _LIBCPP_TEMPLATE_VIS __map_const_iterator;
906};
907
908template <class _TreeIterator>
909class _LIBCPP_TEMPLATE_VIS __map_const_iterator {
910  typedef typename _TreeIterator::_NodeTypes _NodeTypes;
911  typedef typename _TreeIterator::__pointer_traits __pointer_traits;
912
913  _TreeIterator __i_;
914
915public:
916  typedef bidirectional_iterator_tag iterator_category;
917  typedef typename _NodeTypes::__map_value_type value_type;
918  typedef typename _TreeIterator::difference_type difference_type;
919  typedef const value_type& reference;
920  typedef typename _NodeTypes::__const_map_value_type_pointer pointer;
921
922  _LIBCPP_HIDE_FROM_ABI __map_const_iterator() _NOEXCEPT {}
923
924  _LIBCPP_HIDE_FROM_ABI __map_const_iterator(_TreeIterator __i) _NOEXCEPT : __i_(__i) {}
925  _LIBCPP_HIDE_FROM_ABI
926  __map_const_iterator(__map_iterator< typename _TreeIterator::__non_const_iterator> __i) _NOEXCEPT : __i_(__i.__i_) {}
927
928  _LIBCPP_HIDE_FROM_ABI reference operator*() const { return __i_->__get_value(); }
929  _LIBCPP_HIDE_FROM_ABI pointer operator->() const { return pointer_traits<pointer>::pointer_to(__i_->__get_value()); }
930
931  _LIBCPP_HIDE_FROM_ABI __map_const_iterator& operator++() {
932    ++__i_;
933    return *this;
934  }
935  _LIBCPP_HIDE_FROM_ABI __map_const_iterator operator++(int) {
936    __map_const_iterator __t(*this);
937    ++(*this);
938    return __t;
939  }
940
941  _LIBCPP_HIDE_FROM_ABI __map_const_iterator& operator--() {
942    --__i_;
943    return *this;
944  }
945  _LIBCPP_HIDE_FROM_ABI __map_const_iterator operator--(int) {
946    __map_const_iterator __t(*this);
947    --(*this);
948    return __t;
949  }
950
951  friend _LIBCPP_HIDE_FROM_ABI bool operator==(const __map_const_iterator& __x, const __map_const_iterator& __y) {
952    return __x.__i_ == __y.__i_;
953  }
954  friend _LIBCPP_HIDE_FROM_ABI bool operator!=(const __map_const_iterator& __x, const __map_const_iterator& __y) {
955    return __x.__i_ != __y.__i_;
956  }
957
958  template <class, class, class, class>
959  friend class _LIBCPP_TEMPLATE_VIS map;
960  template <class, class, class, class>
961  friend class _LIBCPP_TEMPLATE_VIS multimap;
962  template <class, class, class>
963  friend class _LIBCPP_TEMPLATE_VIS __tree_const_iterator;
964};
965
966template <class _Key, class _Tp, class _Compare = less<_Key>, class _Allocator = allocator<pair<const _Key, _Tp> > >
967class _LIBCPP_TEMPLATE_VIS map {
968public:
969  // types:
970  typedef _Key key_type;
971  typedef _Tp mapped_type;
972  typedef pair<const key_type, mapped_type> value_type;
973  typedef __type_identity_t<_Compare> key_compare;
974  typedef __type_identity_t<_Allocator> allocator_type;
975  typedef value_type& reference;
976  typedef const value_type& const_reference;
977
978  static_assert((is_same<typename allocator_type::value_type, value_type>::value),
979                "Allocator::value_type must be same type as value_type");
980
981  class _LIBCPP_TEMPLATE_VIS value_compare : public __binary_function<value_type, value_type, bool> {
982    friend class map;
983
984  protected:
985    key_compare comp;
986
987    _LIBCPP_HIDE_FROM_ABI value_compare(key_compare __c) : comp(__c) {}
988
989  public:
990    _LIBCPP_HIDE_FROM_ABI bool operator()(const value_type& __x, const value_type& __y) const {
991      return comp(__x.first, __y.first);
992    }
993  };
994
995private:
996  typedef std::__value_type<key_type, mapped_type> __value_type;
997  typedef __map_value_compare<key_type, __value_type, key_compare> __vc;
998  typedef __rebind_alloc<allocator_traits<allocator_type>, __value_type> __allocator_type;
999  typedef __tree<__value_type, __vc, __allocator_type> __base;
1000  typedef typename __base::__node_traits __node_traits;
1001  typedef allocator_traits<allocator_type> __alloc_traits;
1002
1003  static_assert(is_same<allocator_type, __rebind_alloc<__alloc_traits, value_type> >::value,
1004                "[allocator.requirements] states that rebinding an allocator to the same type should result in the "
1005                "original allocator");
1006
1007  __base __tree_;
1008
1009public:
1010  typedef typename __alloc_traits::pointer pointer;
1011  typedef typename __alloc_traits::const_pointer const_pointer;
1012  typedef typename __alloc_traits::size_type size_type;
1013  typedef typename __alloc_traits::difference_type difference_type;
1014  typedef __map_iterator<typename __base::iterator> iterator;
1015  typedef __map_const_iterator<typename __base::const_iterator> const_iterator;
1016  typedef std::reverse_iterator<iterator> reverse_iterator;
1017  typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
1018
1019#if _LIBCPP_STD_VER >= 17
1020  typedef __map_node_handle<typename __base::__node, allocator_type> node_type;
1021  typedef __insert_return_type<iterator, node_type> insert_return_type;
1022#endif
1023
1024  template <class _Key2, class _Value2, class _Comp2, class _Alloc2>
1025  friend class _LIBCPP_TEMPLATE_VIS map;
1026  template <class _Key2, class _Value2, class _Comp2, class _Alloc2>
1027  friend class _LIBCPP_TEMPLATE_VIS multimap;
1028
1029  _LIBCPP_HIDE_FROM_ABI map() _NOEXCEPT_(
1030      is_nothrow_default_constructible<allocator_type>::value&& is_nothrow_default_constructible<key_compare>::value&&
1031          is_nothrow_copy_constructible<key_compare>::value)
1032      : __tree_(__vc(key_compare())) {}
1033
1034  _LIBCPP_HIDE_FROM_ABI explicit map(const key_compare& __comp) _NOEXCEPT_(
1035      is_nothrow_default_constructible<allocator_type>::value&& is_nothrow_copy_constructible<key_compare>::value)
1036      : __tree_(__vc(__comp)) {}
1037
1038  _LIBCPP_HIDE_FROM_ABI explicit map(const key_compare& __comp, const allocator_type& __a)
1039      : __tree_(__vc(__comp), typename __base::allocator_type(__a)) {}
1040
1041  template <class _InputIterator>
1042  _LIBCPP_HIDE_FROM_ABI map(_InputIterator __f, _InputIterator __l, const key_compare& __comp = key_compare())
1043      : __tree_(__vc(__comp)) {
1044    insert(__f, __l);
1045  }
1046
1047  template <class _InputIterator>
1048  _LIBCPP_HIDE_FROM_ABI
1049  map(_InputIterator __f, _InputIterator __l, const key_compare& __comp, const allocator_type& __a)
1050      : __tree_(__vc(__comp), typename __base::allocator_type(__a)) {
1051    insert(__f, __l);
1052  }
1053
1054#if _LIBCPP_STD_VER >= 23
1055  template <_ContainerCompatibleRange<value_type> _Range>
1056  _LIBCPP_HIDE_FROM_ABI
1057  map(from_range_t,
1058      _Range&& __range,
1059      const key_compare& __comp = key_compare(),
1060      const allocator_type& __a = allocator_type())
1061      : __tree_(__vc(__comp), typename __base::allocator_type(__a)) {
1062    insert_range(std::forward<_Range>(__range));
1063  }
1064#endif
1065
1066#if _LIBCPP_STD_VER >= 14
1067  template <class _InputIterator>
1068  _LIBCPP_HIDE_FROM_ABI map(_InputIterator __f, _InputIterator __l, const allocator_type& __a)
1069      : map(__f, __l, key_compare(), __a) {}
1070#endif
1071
1072#if _LIBCPP_STD_VER >= 23
1073  template <_ContainerCompatibleRange<value_type> _Range>
1074  _LIBCPP_HIDE_FROM_ABI map(from_range_t, _Range&& __range, const allocator_type& __a)
1075      : map(from_range, std::forward<_Range>(__range), key_compare(), __a) {}
1076#endif
1077
1078  _LIBCPP_HIDE_FROM_ABI map(const map& __m) : __tree_(__m.__tree_) { insert(__m.begin(), __m.end()); }
1079
1080  _LIBCPP_HIDE_FROM_ABI map& operator=(const map& __m) {
1081#ifndef _LIBCPP_CXX03_LANG
1082    __tree_ = __m.__tree_;
1083#else
1084    if (this != std::addressof(__m)) {
1085      __tree_.clear();
1086      __tree_.value_comp() = __m.__tree_.value_comp();
1087      __tree_.__copy_assign_alloc(__m.__tree_);
1088      insert(__m.begin(), __m.end());
1089    }
1090#endif
1091    return *this;
1092  }
1093
1094#ifndef _LIBCPP_CXX03_LANG
1095
1096  _LIBCPP_HIDE_FROM_ABI map(map&& __m) _NOEXCEPT_(is_nothrow_move_constructible<__base>::value)
1097      : __tree_(std::move(__m.__tree_)) {}
1098
1099  _LIBCPP_HIDE_FROM_ABI map(map&& __m, const allocator_type& __a);
1100
1101  _LIBCPP_HIDE_FROM_ABI map& operator=(map&& __m) _NOEXCEPT_(is_nothrow_move_assignable<__base>::value) {
1102    __tree_ = std::move(__m.__tree_);
1103    return *this;
1104  }
1105
1106  _LIBCPP_HIDE_FROM_ABI map(initializer_list<value_type> __il, const key_compare& __comp = key_compare())
1107      : __tree_(__vc(__comp)) {
1108    insert(__il.begin(), __il.end());
1109  }
1110
1111  _LIBCPP_HIDE_FROM_ABI map(initializer_list<value_type> __il, const key_compare& __comp, const allocator_type& __a)
1112      : __tree_(__vc(__comp), typename __base::allocator_type(__a)) {
1113    insert(__il.begin(), __il.end());
1114  }
1115
1116#  if _LIBCPP_STD_VER >= 14
1117  _LIBCPP_HIDE_FROM_ABI map(initializer_list<value_type> __il, const allocator_type& __a)
1118      : map(__il, key_compare(), __a) {}
1119#  endif
1120
1121  _LIBCPP_HIDE_FROM_ABI map& operator=(initializer_list<value_type> __il) {
1122    __tree_.__assign_unique(__il.begin(), __il.end());
1123    return *this;
1124  }
1125
1126#endif // _LIBCPP_CXX03_LANG
1127
1128  _LIBCPP_HIDE_FROM_ABI explicit map(const allocator_type& __a) : __tree_(typename __base::allocator_type(__a)) {}
1129
1130  _LIBCPP_HIDE_FROM_ABI map(const map& __m, const allocator_type& __a)
1131      : __tree_(__m.__tree_.value_comp(), typename __base::allocator_type(__a)) {
1132    insert(__m.begin(), __m.end());
1133  }
1134
1135  _LIBCPP_HIDE_FROM_ABI ~map() { static_assert(sizeof(__diagnose_non_const_comparator<_Key, _Compare>()), ""); }
1136
1137  _LIBCPP_HIDE_FROM_ABI iterator begin() _NOEXCEPT { return __tree_.begin(); }
1138  _LIBCPP_HIDE_FROM_ABI const_iterator begin() const _NOEXCEPT { return __tree_.begin(); }
1139  _LIBCPP_HIDE_FROM_ABI iterator end() _NOEXCEPT { return __tree_.end(); }
1140  _LIBCPP_HIDE_FROM_ABI const_iterator end() const _NOEXCEPT { return __tree_.end(); }
1141
1142  _LIBCPP_HIDE_FROM_ABI reverse_iterator rbegin() _NOEXCEPT { return reverse_iterator(end()); }
1143  _LIBCPP_HIDE_FROM_ABI const_reverse_iterator rbegin() const _NOEXCEPT { return const_reverse_iterator(end()); }
1144  _LIBCPP_HIDE_FROM_ABI reverse_iterator rend() _NOEXCEPT { return reverse_iterator(begin()); }
1145  _LIBCPP_HIDE_FROM_ABI const_reverse_iterator rend() const _NOEXCEPT { return const_reverse_iterator(begin()); }
1146
1147  _LIBCPP_HIDE_FROM_ABI const_iterator cbegin() const _NOEXCEPT { return begin(); }
1148  _LIBCPP_HIDE_FROM_ABI const_iterator cend() const _NOEXCEPT { return end(); }
1149  _LIBCPP_HIDE_FROM_ABI const_reverse_iterator crbegin() const _NOEXCEPT { return rbegin(); }
1150  _LIBCPP_HIDE_FROM_ABI const_reverse_iterator crend() const _NOEXCEPT { return rend(); }
1151
1152  _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_HIDE_FROM_ABI bool empty() const _NOEXCEPT { return __tree_.size() == 0; }
1153  _LIBCPP_HIDE_FROM_ABI size_type size() const _NOEXCEPT { return __tree_.size(); }
1154  _LIBCPP_HIDE_FROM_ABI size_type max_size() const _NOEXCEPT { return __tree_.max_size(); }
1155
1156  _LIBCPP_HIDE_FROM_ABI mapped_type& operator[](const key_type& __k);
1157#ifndef _LIBCPP_CXX03_LANG
1158  _LIBCPP_HIDE_FROM_ABI mapped_type& operator[](key_type&& __k);
1159#endif
1160
1161  _LIBCPP_HIDE_FROM_ABI mapped_type& at(const key_type& __k);
1162  _LIBCPP_HIDE_FROM_ABI const mapped_type& at(const key_type& __k) const;
1163
1164  _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const _NOEXCEPT { return allocator_type(__tree_.__alloc()); }
1165  _LIBCPP_HIDE_FROM_ABI key_compare key_comp() const { return __tree_.value_comp().key_comp(); }
1166  _LIBCPP_HIDE_FROM_ABI value_compare value_comp() const { return value_compare(__tree_.value_comp().key_comp()); }
1167
1168#ifndef _LIBCPP_CXX03_LANG
1169  template <class... _Args>
1170  _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> emplace(_Args&&... __args) {
1171    return __tree_.__emplace_unique(std::forward<_Args>(__args)...);
1172  }
1173
1174  template <class... _Args>
1175  _LIBCPP_HIDE_FROM_ABI iterator emplace_hint(const_iterator __p, _Args&&... __args) {
1176    return __tree_.__emplace_hint_unique(__p.__i_, std::forward<_Args>(__args)...);
1177  }
1178
1179  template <class _Pp, class = __enable_if_t<is_constructible<value_type, _Pp>::value> >
1180  _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert(_Pp&& __p) {
1181    return __tree_.__insert_unique(std::forward<_Pp>(__p));
1182  }
1183
1184  template <class _Pp, class = __enable_if_t<is_constructible<value_type, _Pp>::value> >
1185  _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __pos, _Pp&& __p) {
1186    return __tree_.__insert_unique(__pos.__i_, std::forward<_Pp>(__p));
1187  }
1188
1189#endif // _LIBCPP_CXX03_LANG
1190
1191  _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert(const value_type& __v) { return __tree_.__insert_unique(__v); }
1192
1193  _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, const value_type& __v) {
1194    return __tree_.__insert_unique(__p.__i_, __v);
1195  }
1196
1197#ifndef _LIBCPP_CXX03_LANG
1198  _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert(value_type&& __v) {
1199    return __tree_.__insert_unique(std::move(__v));
1200  }
1201
1202  _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, value_type&& __v) {
1203    return __tree_.__insert_unique(__p.__i_, std::move(__v));
1204  }
1205
1206  _LIBCPP_HIDE_FROM_ABI void insert(initializer_list<value_type> __il) { insert(__il.begin(), __il.end()); }
1207#endif
1208
1209  template <class _InputIterator>
1210  _LIBCPP_HIDE_FROM_ABI void insert(_InputIterator __f, _InputIterator __l) {
1211    for (const_iterator __e = cend(); __f != __l; ++__f)
1212      insert(__e.__i_, *__f);
1213  }
1214
1215#if _LIBCPP_STD_VER >= 23
1216  template <_ContainerCompatibleRange<value_type> _Range>
1217  _LIBCPP_HIDE_FROM_ABI void insert_range(_Range&& __range) {
1218    const_iterator __end = cend();
1219    for (auto&& __element : __range) {
1220      insert(__end.__i_, std::forward<decltype(__element)>(__element));
1221    }
1222  }
1223#endif
1224
1225#if _LIBCPP_STD_VER >= 17
1226
1227  template <class... _Args>
1228  _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> try_emplace(const key_type& __k, _Args&&... __args) {
1229    return __tree_.__emplace_unique_key_args(
1230        __k,
1231        std::piecewise_construct,
1232        std::forward_as_tuple(__k),
1233        std::forward_as_tuple(std::forward<_Args>(__args)...));
1234  }
1235
1236  template <class... _Args>
1237  _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> try_emplace(key_type&& __k, _Args&&... __args) {
1238    return __tree_.__emplace_unique_key_args(
1239        __k,
1240        std::piecewise_construct,
1241        std::forward_as_tuple(std::move(__k)),
1242        std::forward_as_tuple(std::forward<_Args>(__args)...));
1243  }
1244
1245  template <class... _Args>
1246  _LIBCPP_HIDE_FROM_ABI iterator try_emplace(const_iterator __h, const key_type& __k, _Args&&... __args) {
1247    return __tree_
1248        .__emplace_hint_unique_key_args(
1249            __h.__i_,
1250            __k,
1251            std::piecewise_construct,
1252            std::forward_as_tuple(__k),
1253            std::forward_as_tuple(std::forward<_Args>(__args)...))
1254        .first;
1255  }
1256
1257  template <class... _Args>
1258  _LIBCPP_HIDE_FROM_ABI iterator try_emplace(const_iterator __h, key_type&& __k, _Args&&... __args) {
1259    return __tree_
1260        .__emplace_hint_unique_key_args(
1261            __h.__i_,
1262            __k,
1263            std::piecewise_construct,
1264            std::forward_as_tuple(std::move(__k)),
1265            std::forward_as_tuple(std::forward<_Args>(__args)...))
1266        .first;
1267  }
1268
1269  template <class _Vp>
1270  _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert_or_assign(const key_type& __k, _Vp&& __v) {
1271    iterator __p = lower_bound(__k);
1272    if (__p != end() && !key_comp()(__k, __p->first)) {
1273      __p->second = std::forward<_Vp>(__v);
1274      return std::make_pair(__p, false);
1275    }
1276    return std::make_pair(emplace_hint(__p, __k, std::forward<_Vp>(__v)), true);
1277  }
1278
1279  template <class _Vp>
1280  _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert_or_assign(key_type&& __k, _Vp&& __v) {
1281    iterator __p = lower_bound(__k);
1282    if (__p != end() && !key_comp()(__k, __p->first)) {
1283      __p->second = std::forward<_Vp>(__v);
1284      return std::make_pair(__p, false);
1285    }
1286    return std::make_pair(emplace_hint(__p, std::move(__k), std::forward<_Vp>(__v)), true);
1287  }
1288
1289  template <class _Vp>
1290  _LIBCPP_HIDE_FROM_ABI iterator insert_or_assign(const_iterator __h, const key_type& __k, _Vp&& __v) {
1291    auto [__r, __inserted] = __tree_.__emplace_hint_unique_key_args(__h.__i_, __k, __k, std::forward<_Vp>(__v));
1292
1293    if (!__inserted)
1294      __r->__get_value().second = std::forward<_Vp>(__v);
1295
1296    return __r;
1297  }
1298
1299  template <class _Vp>
1300  _LIBCPP_HIDE_FROM_ABI iterator insert_or_assign(const_iterator __h, key_type&& __k, _Vp&& __v) {
1301    auto [__r, __inserted] =
1302        __tree_.__emplace_hint_unique_key_args(__h.__i_, __k, std::move(__k), std::forward<_Vp>(__v));
1303
1304    if (!__inserted)
1305      __r->__get_value().second = std::forward<_Vp>(__v);
1306
1307    return __r;
1308  }
1309
1310#endif // _LIBCPP_STD_VER >= 17
1311
1312  _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __p) { return __tree_.erase(__p.__i_); }
1313  _LIBCPP_HIDE_FROM_ABI iterator erase(iterator __p) { return __tree_.erase(__p.__i_); }
1314  _LIBCPP_HIDE_FROM_ABI size_type erase(const key_type& __k) { return __tree_.__erase_unique(__k); }
1315  _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __f, const_iterator __l) {
1316    return __tree_.erase(__f.__i_, __l.__i_);
1317  }
1318  _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT { __tree_.clear(); }
1319
1320#if _LIBCPP_STD_VER >= 17
1321  _LIBCPP_HIDE_FROM_ABI insert_return_type insert(node_type&& __nh) {
1322    _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(),
1323                                        "node_type with incompatible allocator passed to map::insert()");
1324    return __tree_.template __node_handle_insert_unique< node_type, insert_return_type>(std::move(__nh));
1325  }
1326  _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __hint, node_type&& __nh) {
1327    _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(),
1328                                        "node_type with incompatible allocator passed to map::insert()");
1329    return __tree_.template __node_handle_insert_unique<node_type>(__hint.__i_, std::move(__nh));
1330  }
1331  _LIBCPP_HIDE_FROM_ABI node_type extract(key_type const& __key) {
1332    return __tree_.template __node_handle_extract<node_type>(__key);
1333  }
1334  _LIBCPP_HIDE_FROM_ABI node_type extract(const_iterator __it) {
1335    return __tree_.template __node_handle_extract<node_type>(__it.__i_);
1336  }
1337  template <class _Compare2>
1338  _LIBCPP_HIDE_FROM_ABI void merge(map<key_type, mapped_type, _Compare2, allocator_type>& __source) {
1339    _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
1340        __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
1341    __tree_.__node_handle_merge_unique(__source.__tree_);
1342  }
1343  template <class _Compare2>
1344  _LIBCPP_HIDE_FROM_ABI void merge(map<key_type, mapped_type, _Compare2, allocator_type>&& __source) {
1345    _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
1346        __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
1347    __tree_.__node_handle_merge_unique(__source.__tree_);
1348  }
1349  template <class _Compare2>
1350  _LIBCPP_HIDE_FROM_ABI void merge(multimap<key_type, mapped_type, _Compare2, allocator_type>& __source) {
1351    _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
1352        __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
1353    __tree_.__node_handle_merge_unique(__source.__tree_);
1354  }
1355  template <class _Compare2>
1356  _LIBCPP_HIDE_FROM_ABI void merge(multimap<key_type, mapped_type, _Compare2, allocator_type>&& __source) {
1357    _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
1358        __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
1359    __tree_.__node_handle_merge_unique(__source.__tree_);
1360  }
1361#endif
1362
1363  _LIBCPP_HIDE_FROM_ABI void swap(map& __m) _NOEXCEPT_(__is_nothrow_swappable<__base>::value) {
1364    __tree_.swap(__m.__tree_);
1365  }
1366
1367  _LIBCPP_HIDE_FROM_ABI iterator find(const key_type& __k) { return __tree_.find(__k); }
1368  _LIBCPP_HIDE_FROM_ABI const_iterator find(const key_type& __k) const { return __tree_.find(__k); }
1369#if _LIBCPP_STD_VER >= 14
1370  template <typename _K2, enable_if_t<__is_transparent<_Compare, _K2>::value, int> = 0>
1371  _LIBCPP_HIDE_FROM_ABI iterator find(const _K2& __k) {
1372    return __tree_.find(__k);
1373  }
1374  template <typename _K2, enable_if_t<__is_transparent<_Compare, _K2>::value, int> = 0>
1375  _LIBCPP_HIDE_FROM_ABI const_iterator find(const _K2& __k) const {
1376    return __tree_.find(__k);
1377  }
1378#endif
1379
1380  _LIBCPP_HIDE_FROM_ABI size_type count(const key_type& __k) const { return __tree_.__count_unique(__k); }
1381#if _LIBCPP_STD_VER >= 14
1382  template <typename _K2, enable_if_t<__is_transparent<_Compare, _K2>::value, int> = 0>
1383  _LIBCPP_HIDE_FROM_ABI size_type count(const _K2& __k) const {
1384    return __tree_.__count_multi(__k);
1385  }
1386#endif
1387
1388#if _LIBCPP_STD_VER >= 20
1389  _LIBCPP_HIDE_FROM_ABI bool contains(const key_type& __k) const { return find(__k) != end(); }
1390  template <typename _K2, enable_if_t<__is_transparent<_Compare, _K2>::value, int> = 0>
1391  _LIBCPP_HIDE_FROM_ABI bool contains(const _K2& __k) const {
1392    return find(__k) != end();
1393  }
1394#endif // _LIBCPP_STD_VER >= 20
1395
1396  _LIBCPP_HIDE_FROM_ABI iterator lower_bound(const key_type& __k) { return __tree_.lower_bound(__k); }
1397  _LIBCPP_HIDE_FROM_ABI const_iterator lower_bound(const key_type& __k) const { return __tree_.lower_bound(__k); }
1398#if _LIBCPP_STD_VER >= 14
1399  template <typename _K2, enable_if_t<__is_transparent<_Compare, _K2>::value, int> = 0>
1400  _LIBCPP_HIDE_FROM_ABI iterator lower_bound(const _K2& __k) {
1401    return __tree_.lower_bound(__k);
1402  }
1403
1404  template <typename _K2, enable_if_t<__is_transparent<_Compare, _K2>::value, int> = 0>
1405  _LIBCPP_HIDE_FROM_ABI const_iterator lower_bound(const _K2& __k) const {
1406    return __tree_.lower_bound(__k);
1407  }
1408#endif
1409
1410  _LIBCPP_HIDE_FROM_ABI iterator upper_bound(const key_type& __k) { return __tree_.upper_bound(__k); }
1411  _LIBCPP_HIDE_FROM_ABI const_iterator upper_bound(const key_type& __k) const { return __tree_.upper_bound(__k); }
1412#if _LIBCPP_STD_VER >= 14
1413  template <typename _K2, enable_if_t<__is_transparent<_Compare, _K2>::value, int> = 0>
1414  _LIBCPP_HIDE_FROM_ABI iterator upper_bound(const _K2& __k) {
1415    return __tree_.upper_bound(__k);
1416  }
1417  template <typename _K2, enable_if_t<__is_transparent<_Compare, _K2>::value, int> = 0>
1418  _LIBCPP_HIDE_FROM_ABI const_iterator upper_bound(const _K2& __k) const {
1419    return __tree_.upper_bound(__k);
1420  }
1421#endif
1422
1423  _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const key_type& __k) {
1424    return __tree_.__equal_range_unique(__k);
1425  }
1426  _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const key_type& __k) const {
1427    return __tree_.__equal_range_unique(__k);
1428  }
1429#if _LIBCPP_STD_VER >= 14
1430  template <typename _K2, enable_if_t<__is_transparent<_Compare, _K2>::value, int> = 0>
1431  _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const _K2& __k) {
1432    return __tree_.__equal_range_multi(__k);
1433  }
1434  template <typename _K2, enable_if_t<__is_transparent<_Compare, _K2>::value, int> = 0>
1435  _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const _K2& __k) const {
1436    return __tree_.__equal_range_multi(__k);
1437  }
1438#endif
1439
1440private:
1441  typedef typename __base::__node __node;
1442  typedef typename __base::__node_allocator __node_allocator;
1443  typedef typename __base::__node_pointer __node_pointer;
1444  typedef typename __base::__node_base_pointer __node_base_pointer;
1445  typedef typename __base::__parent_pointer __parent_pointer;
1446
1447  typedef __map_node_destructor<__node_allocator> _Dp;
1448  typedef unique_ptr<__node, _Dp> __node_holder;
1449
1450#ifdef _LIBCPP_CXX03_LANG
1451  _LIBCPP_HIDE_FROM_ABI __node_holder __construct_node_with_key(const key_type& __k);
1452#endif
1453};
1454
1455#if _LIBCPP_STD_VER >= 17
1456template <class _InputIterator,
1457          class _Compare   = less<__iter_key_type<_InputIterator>>,
1458          class _Allocator = allocator<__iter_to_alloc_type<_InputIterator>>,
1459          class            = enable_if_t<__has_input_iterator_category<_InputIterator>::value, void>,
1460          class            = enable_if_t<!__is_allocator<_Compare>::value, void>,
1461          class            = enable_if_t<__is_allocator<_Allocator>::value, void>>
1462map(_InputIterator, _InputIterator, _Compare = _Compare(), _Allocator = _Allocator())
1463    -> map<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>, _Compare, _Allocator>;
1464
1465#  if _LIBCPP_STD_VER >= 23
1466template <ranges::input_range _Range,
1467          class _Compare   = less<__range_key_type<_Range>>,
1468          class _Allocator = allocator<__range_to_alloc_type<_Range>>,
1469          class            = enable_if_t<!__is_allocator<_Compare>::value, void>,
1470          class            = enable_if_t<__is_allocator<_Allocator>::value, void>>
1471map(from_range_t, _Range&&, _Compare = _Compare(), _Allocator = _Allocator())
1472    -> map<__range_key_type<_Range>, __range_mapped_type<_Range>, _Compare, _Allocator>;
1473#  endif
1474
1475template <class _Key,
1476          class _Tp,
1477          class _Compare   = less<remove_const_t<_Key>>,
1478          class _Allocator = allocator<pair<const _Key, _Tp>>,
1479          class            = enable_if_t<!__is_allocator<_Compare>::value, void>,
1480          class            = enable_if_t<__is_allocator<_Allocator>::value, void>>
1481map(initializer_list<pair<_Key, _Tp>>, _Compare = _Compare(), _Allocator = _Allocator())
1482    -> map<remove_const_t<_Key>, _Tp, _Compare, _Allocator>;
1483
1484template <class _InputIterator,
1485          class _Allocator,
1486          class = enable_if_t<__has_input_iterator_category<_InputIterator>::value, void>,
1487          class = enable_if_t<__is_allocator<_Allocator>::value, void>>
1488map(_InputIterator, _InputIterator, _Allocator)
1489    -> map<__iter_key_type<_InputIterator>,
1490           __iter_mapped_type<_InputIterator>,
1491           less<__iter_key_type<_InputIterator>>,
1492           _Allocator>;
1493
1494#  if _LIBCPP_STD_VER >= 23
1495template <ranges::input_range _Range, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value, void>>
1496map(from_range_t, _Range&&, _Allocator)
1497    -> map<__range_key_type<_Range>, __range_mapped_type<_Range>, less<__range_key_type<_Range>>, _Allocator>;
1498#  endif
1499
1500template <class _Key, class _Tp, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value, void>>
1501map(initializer_list<pair<_Key, _Tp>>, _Allocator)
1502    -> map<remove_const_t<_Key>, _Tp, less<remove_const_t<_Key>>, _Allocator>;
1503#endif
1504
1505#ifndef _LIBCPP_CXX03_LANG
1506template <class _Key, class _Tp, class _Compare, class _Allocator>
1507map<_Key, _Tp, _Compare, _Allocator>::map(map&& __m, const allocator_type& __a)
1508    : __tree_(std::move(__m.__tree_), typename __base::allocator_type(__a)) {
1509  if (__a != __m.get_allocator()) {
1510    const_iterator __e = cend();
1511    while (!__m.empty())
1512      __tree_.__insert_unique(__e.__i_, __m.__tree_.remove(__m.begin().__i_)->__value_.__move());
1513  }
1514}
1515
1516template <class _Key, class _Tp, class _Compare, class _Allocator>
1517_Tp& map<_Key, _Tp, _Compare, _Allocator>::operator[](const key_type& __k) {
1518  return __tree_
1519      .__emplace_unique_key_args(__k, std::piecewise_construct, std::forward_as_tuple(__k), std::forward_as_tuple())
1520      .first->__get_value()
1521      .second;
1522}
1523
1524template <class _Key, class _Tp, class _Compare, class _Allocator>
1525_Tp& map<_Key, _Tp, _Compare, _Allocator>::operator[](key_type&& __k) {
1526  // TODO investigate this clang-tidy warning.
1527  // NOLINTBEGIN(bugprone-use-after-move)
1528  return __tree_
1529      .__emplace_unique_key_args(
1530          __k, std::piecewise_construct, std::forward_as_tuple(std::move(__k)), std::forward_as_tuple())
1531      .first->__get_value()
1532      .second;
1533  // NOLINTEND(bugprone-use-after-move)
1534}
1535
1536#else // _LIBCPP_CXX03_LANG
1537
1538template <class _Key, class _Tp, class _Compare, class _Allocator>
1539typename map<_Key, _Tp, _Compare, _Allocator>::__node_holder
1540map<_Key, _Tp, _Compare, _Allocator>::__construct_node_with_key(const key_type& __k) {
1541  __node_allocator& __na = __tree_.__node_alloc();
1542  __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1543  __node_traits::construct(__na, std::addressof(__h->__value_.__get_value().first), __k);
1544  __h.get_deleter().__first_constructed = true;
1545  __node_traits::construct(__na, std::addressof(__h->__value_.__get_value().second));
1546  __h.get_deleter().__second_constructed = true;
1547  return __h;
1548}
1549
1550template <class _Key, class _Tp, class _Compare, class _Allocator>
1551_Tp& map<_Key, _Tp, _Compare, _Allocator>::operator[](const key_type& __k) {
1552  __parent_pointer __parent;
1553  __node_base_pointer& __child = __tree_.__find_equal(__parent, __k);
1554  __node_pointer __r           = static_cast<__node_pointer>(__child);
1555  if (__child == nullptr) {
1556    __node_holder __h = __construct_node_with_key(__k);
1557    __tree_.__insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
1558    __r = __h.release();
1559  }
1560  return __r->__value_.__get_value().second;
1561}
1562
1563#endif // _LIBCPP_CXX03_LANG
1564
1565template <class _Key, class _Tp, class _Compare, class _Allocator>
1566_Tp& map<_Key, _Tp, _Compare, _Allocator>::at(const key_type& __k) {
1567  __parent_pointer __parent;
1568  __node_base_pointer& __child = __tree_.__find_equal(__parent, __k);
1569  if (__child == nullptr)
1570    __throw_out_of_range("map::at:  key not found");
1571  return static_cast<__node_pointer>(__child)->__value_.__get_value().second;
1572}
1573
1574template <class _Key, class _Tp, class _Compare, class _Allocator>
1575const _Tp& map<_Key, _Tp, _Compare, _Allocator>::at(const key_type& __k) const {
1576  __parent_pointer __parent;
1577  __node_base_pointer __child = __tree_.__find_equal(__parent, __k);
1578  if (__child == nullptr)
1579    __throw_out_of_range("map::at:  key not found");
1580  return static_cast<__node_pointer>(__child)->__value_.__get_value().second;
1581}
1582
1583template <class _Key, class _Tp, class _Compare, class _Allocator>
1584inline _LIBCPP_HIDE_FROM_ABI bool
1585operator==(const map<_Key, _Tp, _Compare, _Allocator>& __x, const map<_Key, _Tp, _Compare, _Allocator>& __y) {
1586  return __x.size() == __y.size() && std::equal(__x.begin(), __x.end(), __y.begin());
1587}
1588
1589#if _LIBCPP_STD_VER <= 17
1590
1591template <class _Key, class _Tp, class _Compare, class _Allocator>
1592inline _LIBCPP_HIDE_FROM_ABI bool
1593operator<(const map<_Key, _Tp, _Compare, _Allocator>& __x, const map<_Key, _Tp, _Compare, _Allocator>& __y) {
1594  return std::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
1595}
1596
1597template <class _Key, class _Tp, class _Compare, class _Allocator>
1598inline _LIBCPP_HIDE_FROM_ABI bool
1599operator!=(const map<_Key, _Tp, _Compare, _Allocator>& __x, const map<_Key, _Tp, _Compare, _Allocator>& __y) {
1600  return !(__x == __y);
1601}
1602
1603template <class _Key, class _Tp, class _Compare, class _Allocator>
1604inline _LIBCPP_HIDE_FROM_ABI bool
1605operator>(const map<_Key, _Tp, _Compare, _Allocator>& __x, const map<_Key, _Tp, _Compare, _Allocator>& __y) {
1606  return __y < __x;
1607}
1608
1609template <class _Key, class _Tp, class _Compare, class _Allocator>
1610inline _LIBCPP_HIDE_FROM_ABI bool
1611operator>=(const map<_Key, _Tp, _Compare, _Allocator>& __x, const map<_Key, _Tp, _Compare, _Allocator>& __y) {
1612  return !(__x < __y);
1613}
1614
1615template <class _Key, class _Tp, class _Compare, class _Allocator>
1616inline _LIBCPP_HIDE_FROM_ABI bool
1617operator<=(const map<_Key, _Tp, _Compare, _Allocator>& __x, const map<_Key, _Tp, _Compare, _Allocator>& __y) {
1618  return !(__y < __x);
1619}
1620
1621#else // #if _LIBCPP_STD_VER <= 17
1622
1623template <class _Key, class _Tp, class _Compare, class _Allocator>
1624_LIBCPP_HIDE_FROM_ABI __synth_three_way_result<pair<const _Key, _Tp>>
1625operator<=>(const map<_Key, _Tp, _Compare, _Allocator>& __x, const map<_Key, _Tp, _Compare, _Allocator>& __y) {
1626  return std::lexicographical_compare_three_way(
1627      __x.begin(),
1628      __x.end(),
1629      __y.begin(),
1630      __y.end(),
1631      std::__synth_three_way<pair<const _Key, _Tp>, pair<const _Key, _Tp>>);
1632}
1633
1634#endif // #if _LIBCPP_STD_VER <= 17
1635
1636template <class _Key, class _Tp, class _Compare, class _Allocator>
1637inline _LIBCPP_HIDE_FROM_ABI void
1638swap(map<_Key, _Tp, _Compare, _Allocator>& __x, map<_Key, _Tp, _Compare, _Allocator>& __y)
1639    _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) {
1640  __x.swap(__y);
1641}
1642
1643#if _LIBCPP_STD_VER >= 20
1644template <class _Key, class _Tp, class _Compare, class _Allocator, class _Predicate>
1645inline _LIBCPP_HIDE_FROM_ABI typename map<_Key, _Tp, _Compare, _Allocator>::size_type
1646erase_if(map<_Key, _Tp, _Compare, _Allocator>& __c, _Predicate __pred) {
1647  return std::__libcpp_erase_if_container(__c, __pred);
1648}
1649#endif
1650
1651template <class _Key, class _Tp, class _Compare = less<_Key>, class _Allocator = allocator<pair<const _Key, _Tp> > >
1652class _LIBCPP_TEMPLATE_VIS multimap {
1653public:
1654  // types:
1655  typedef _Key key_type;
1656  typedef _Tp mapped_type;
1657  typedef pair<const key_type, mapped_type> value_type;
1658  typedef __type_identity_t<_Compare> key_compare;
1659  typedef __type_identity_t<_Allocator> allocator_type;
1660  typedef value_type& reference;
1661  typedef const value_type& const_reference;
1662
1663  static_assert((is_same<typename allocator_type::value_type, value_type>::value),
1664                "Allocator::value_type must be same type as value_type");
1665
1666  class _LIBCPP_TEMPLATE_VIS value_compare : public __binary_function<value_type, value_type, bool> {
1667    friend class multimap;
1668
1669  protected:
1670    key_compare comp;
1671
1672    _LIBCPP_HIDE_FROM_ABI value_compare(key_compare __c) : comp(__c) {}
1673
1674  public:
1675    _LIBCPP_HIDE_FROM_ABI bool operator()(const value_type& __x, const value_type& __y) const {
1676      return comp(__x.first, __y.first);
1677    }
1678  };
1679
1680private:
1681  typedef std::__value_type<key_type, mapped_type> __value_type;
1682  typedef __map_value_compare<key_type, __value_type, key_compare> __vc;
1683  typedef __rebind_alloc<allocator_traits<allocator_type>, __value_type> __allocator_type;
1684  typedef __tree<__value_type, __vc, __allocator_type> __base;
1685  typedef typename __base::__node_traits __node_traits;
1686  typedef allocator_traits<allocator_type> __alloc_traits;
1687
1688  static_assert(is_same<allocator_type, __rebind_alloc<__alloc_traits, value_type> >::value,
1689                "[allocator.requirements] states that rebinding an allocator to the same type should result in the "
1690                "original allocator");
1691
1692  __base __tree_;
1693
1694public:
1695  typedef typename __alloc_traits::pointer pointer;
1696  typedef typename __alloc_traits::const_pointer const_pointer;
1697  typedef typename __alloc_traits::size_type size_type;
1698  typedef typename __alloc_traits::difference_type difference_type;
1699  typedef __map_iterator<typename __base::iterator> iterator;
1700  typedef __map_const_iterator<typename __base::const_iterator> const_iterator;
1701  typedef std::reverse_iterator<iterator> reverse_iterator;
1702  typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
1703
1704#if _LIBCPP_STD_VER >= 17
1705  typedef __map_node_handle<typename __base::__node, allocator_type> node_type;
1706#endif
1707
1708  template <class _Key2, class _Value2, class _Comp2, class _Alloc2>
1709  friend class _LIBCPP_TEMPLATE_VIS map;
1710  template <class _Key2, class _Value2, class _Comp2, class _Alloc2>
1711  friend class _LIBCPP_TEMPLATE_VIS multimap;
1712
1713  _LIBCPP_HIDE_FROM_ABI multimap() _NOEXCEPT_(
1714      is_nothrow_default_constructible<allocator_type>::value&& is_nothrow_default_constructible<key_compare>::value&&
1715          is_nothrow_copy_constructible<key_compare>::value)
1716      : __tree_(__vc(key_compare())) {}
1717
1718  _LIBCPP_HIDE_FROM_ABI explicit multimap(const key_compare& __comp) _NOEXCEPT_(
1719      is_nothrow_default_constructible<allocator_type>::value&& is_nothrow_copy_constructible<key_compare>::value)
1720      : __tree_(__vc(__comp)) {}
1721
1722  _LIBCPP_HIDE_FROM_ABI explicit multimap(const key_compare& __comp, const allocator_type& __a)
1723      : __tree_(__vc(__comp), typename __base::allocator_type(__a)) {}
1724
1725  template <class _InputIterator>
1726  _LIBCPP_HIDE_FROM_ABI multimap(_InputIterator __f, _InputIterator __l, const key_compare& __comp = key_compare())
1727      : __tree_(__vc(__comp)) {
1728    insert(__f, __l);
1729  }
1730
1731  template <class _InputIterator>
1732  _LIBCPP_HIDE_FROM_ABI
1733  multimap(_InputIterator __f, _InputIterator __l, const key_compare& __comp, const allocator_type& __a)
1734      : __tree_(__vc(__comp), typename __base::allocator_type(__a)) {
1735    insert(__f, __l);
1736  }
1737
1738#if _LIBCPP_STD_VER >= 23
1739  template <_ContainerCompatibleRange<value_type> _Range>
1740  _LIBCPP_HIDE_FROM_ABI
1741  multimap(from_range_t,
1742           _Range&& __range,
1743           const key_compare& __comp = key_compare(),
1744           const allocator_type& __a = allocator_type())
1745      : __tree_(__vc(__comp), typename __base::allocator_type(__a)) {
1746    insert_range(std::forward<_Range>(__range));
1747  }
1748#endif
1749
1750#if _LIBCPP_STD_VER >= 14
1751  template <class _InputIterator>
1752  _LIBCPP_HIDE_FROM_ABI multimap(_InputIterator __f, _InputIterator __l, const allocator_type& __a)
1753      : multimap(__f, __l, key_compare(), __a) {}
1754#endif
1755
1756#if _LIBCPP_STD_VER >= 23
1757  template <_ContainerCompatibleRange<value_type> _Range>
1758  _LIBCPP_HIDE_FROM_ABI multimap(from_range_t, _Range&& __range, const allocator_type& __a)
1759      : multimap(from_range, std::forward<_Range>(__range), key_compare(), __a) {}
1760#endif
1761
1762  _LIBCPP_HIDE_FROM_ABI multimap(const multimap& __m)
1763      : __tree_(__m.__tree_.value_comp(),
1764                __alloc_traits::select_on_container_copy_construction(__m.__tree_.__alloc())) {
1765    insert(__m.begin(), __m.end());
1766  }
1767
1768  _LIBCPP_HIDE_FROM_ABI multimap& operator=(const multimap& __m) {
1769#ifndef _LIBCPP_CXX03_LANG
1770    __tree_ = __m.__tree_;
1771#else
1772    if (this != std::addressof(__m)) {
1773      __tree_.clear();
1774      __tree_.value_comp() = __m.__tree_.value_comp();
1775      __tree_.__copy_assign_alloc(__m.__tree_);
1776      insert(__m.begin(), __m.end());
1777    }
1778#endif
1779    return *this;
1780  }
1781
1782#ifndef _LIBCPP_CXX03_LANG
1783
1784  _LIBCPP_HIDE_FROM_ABI multimap(multimap&& __m) _NOEXCEPT_(is_nothrow_move_constructible<__base>::value)
1785      : __tree_(std::move(__m.__tree_)) {}
1786
1787  _LIBCPP_HIDE_FROM_ABI multimap(multimap&& __m, const allocator_type& __a);
1788
1789  _LIBCPP_HIDE_FROM_ABI multimap& operator=(multimap&& __m) _NOEXCEPT_(is_nothrow_move_assignable<__base>::value) {
1790    __tree_ = std::move(__m.__tree_);
1791    return *this;
1792  }
1793
1794  _LIBCPP_HIDE_FROM_ABI multimap(initializer_list<value_type> __il, const key_compare& __comp = key_compare())
1795      : __tree_(__vc(__comp)) {
1796    insert(__il.begin(), __il.end());
1797  }
1798
1799  _LIBCPP_HIDE_FROM_ABI
1800  multimap(initializer_list<value_type> __il, const key_compare& __comp, const allocator_type& __a)
1801      : __tree_(__vc(__comp), typename __base::allocator_type(__a)) {
1802    insert(__il.begin(), __il.end());
1803  }
1804
1805#  if _LIBCPP_STD_VER >= 14
1806  _LIBCPP_HIDE_FROM_ABI multimap(initializer_list<value_type> __il, const allocator_type& __a)
1807      : multimap(__il, key_compare(), __a) {}
1808#  endif
1809
1810  _LIBCPP_HIDE_FROM_ABI multimap& operator=(initializer_list<value_type> __il) {
1811    __tree_.__assign_multi(__il.begin(), __il.end());
1812    return *this;
1813  }
1814
1815#endif // _LIBCPP_CXX03_LANG
1816
1817  _LIBCPP_HIDE_FROM_ABI explicit multimap(const allocator_type& __a) : __tree_(typename __base::allocator_type(__a)) {}
1818
1819  _LIBCPP_HIDE_FROM_ABI multimap(const multimap& __m, const allocator_type& __a)
1820      : __tree_(__m.__tree_.value_comp(), typename __base::allocator_type(__a)) {
1821    insert(__m.begin(), __m.end());
1822  }
1823
1824  _LIBCPP_HIDE_FROM_ABI ~multimap() { static_assert(sizeof(__diagnose_non_const_comparator<_Key, _Compare>()), ""); }
1825
1826  _LIBCPP_HIDE_FROM_ABI iterator begin() _NOEXCEPT { return __tree_.begin(); }
1827  _LIBCPP_HIDE_FROM_ABI const_iterator begin() const _NOEXCEPT { return __tree_.begin(); }
1828  _LIBCPP_HIDE_FROM_ABI iterator end() _NOEXCEPT { return __tree_.end(); }
1829  _LIBCPP_HIDE_FROM_ABI const_iterator end() const _NOEXCEPT { return __tree_.end(); }
1830
1831  _LIBCPP_HIDE_FROM_ABI reverse_iterator rbegin() _NOEXCEPT { return reverse_iterator(end()); }
1832  _LIBCPP_HIDE_FROM_ABI const_reverse_iterator rbegin() const _NOEXCEPT { return const_reverse_iterator(end()); }
1833  _LIBCPP_HIDE_FROM_ABI reverse_iterator rend() _NOEXCEPT { return reverse_iterator(begin()); }
1834  _LIBCPP_HIDE_FROM_ABI const_reverse_iterator rend() const _NOEXCEPT { return const_reverse_iterator(begin()); }
1835
1836  _LIBCPP_HIDE_FROM_ABI const_iterator cbegin() const _NOEXCEPT { return begin(); }
1837  _LIBCPP_HIDE_FROM_ABI const_iterator cend() const _NOEXCEPT { return end(); }
1838  _LIBCPP_HIDE_FROM_ABI const_reverse_iterator crbegin() const _NOEXCEPT { return rbegin(); }
1839  _LIBCPP_HIDE_FROM_ABI const_reverse_iterator crend() const _NOEXCEPT { return rend(); }
1840
1841  _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_HIDE_FROM_ABI bool empty() const _NOEXCEPT { return __tree_.size() == 0; }
1842  _LIBCPP_HIDE_FROM_ABI size_type size() const _NOEXCEPT { return __tree_.size(); }
1843  _LIBCPP_HIDE_FROM_ABI size_type max_size() const _NOEXCEPT { return __tree_.max_size(); }
1844
1845  _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const _NOEXCEPT { return allocator_type(__tree_.__alloc()); }
1846  _LIBCPP_HIDE_FROM_ABI key_compare key_comp() const { return __tree_.value_comp().key_comp(); }
1847  _LIBCPP_HIDE_FROM_ABI value_compare value_comp() const { return value_compare(__tree_.value_comp().key_comp()); }
1848
1849#ifndef _LIBCPP_CXX03_LANG
1850
1851  template <class... _Args>
1852  _LIBCPP_HIDE_FROM_ABI iterator emplace(_Args&&... __args) {
1853    return __tree_.__emplace_multi(std::forward<_Args>(__args)...);
1854  }
1855
1856  template <class... _Args>
1857  _LIBCPP_HIDE_FROM_ABI iterator emplace_hint(const_iterator __p, _Args&&... __args) {
1858    return __tree_.__emplace_hint_multi(__p.__i_, std::forward<_Args>(__args)...);
1859  }
1860
1861  template <class _Pp, class = __enable_if_t<is_constructible<value_type, _Pp>::value>>
1862  _LIBCPP_HIDE_FROM_ABI iterator insert(_Pp&& __p) {
1863    return __tree_.__insert_multi(std::forward<_Pp>(__p));
1864  }
1865
1866  template <class _Pp, class = __enable_if_t<is_constructible<value_type, _Pp>::value>>
1867  _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __pos, _Pp&& __p) {
1868    return __tree_.__insert_multi(__pos.__i_, std::forward<_Pp>(__p));
1869  }
1870
1871  _LIBCPP_HIDE_FROM_ABI iterator insert(value_type&& __v) { return __tree_.__insert_multi(std::move(__v)); }
1872
1873  _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, value_type&& __v) {
1874    return __tree_.__insert_multi(__p.__i_, std::move(__v));
1875  }
1876
1877  _LIBCPP_HIDE_FROM_ABI void insert(initializer_list<value_type> __il) { insert(__il.begin(), __il.end()); }
1878
1879#endif // _LIBCPP_CXX03_LANG
1880
1881  _LIBCPP_HIDE_FROM_ABI iterator insert(const value_type& __v) { return __tree_.__insert_multi(__v); }
1882
1883  _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, const value_type& __v) {
1884    return __tree_.__insert_multi(__p.__i_, __v);
1885  }
1886
1887  template <class _InputIterator>
1888  _LIBCPP_HIDE_FROM_ABI void insert(_InputIterator __f, _InputIterator __l) {
1889    for (const_iterator __e = cend(); __f != __l; ++__f)
1890      __tree_.__insert_multi(__e.__i_, *__f);
1891  }
1892
1893#if _LIBCPP_STD_VER >= 23
1894  template <_ContainerCompatibleRange<value_type> _Range>
1895  _LIBCPP_HIDE_FROM_ABI void insert_range(_Range&& __range) {
1896    const_iterator __end = cend();
1897    for (auto&& __element : __range) {
1898      __tree_.__insert_multi(__end.__i_, std::forward<decltype(__element)>(__element));
1899    }
1900  }
1901#endif
1902
1903  _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __p) { return __tree_.erase(__p.__i_); }
1904  _LIBCPP_HIDE_FROM_ABI iterator erase(iterator __p) { return __tree_.erase(__p.__i_); }
1905  _LIBCPP_HIDE_FROM_ABI size_type erase(const key_type& __k) { return __tree_.__erase_multi(__k); }
1906  _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __f, const_iterator __l) {
1907    return __tree_.erase(__f.__i_, __l.__i_);
1908  }
1909
1910#if _LIBCPP_STD_VER >= 17
1911  _LIBCPP_HIDE_FROM_ABI iterator insert(node_type&& __nh) {
1912    _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(),
1913                                        "node_type with incompatible allocator passed to multimap::insert()");
1914    return __tree_.template __node_handle_insert_multi<node_type>(std::move(__nh));
1915  }
1916  _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __hint, node_type&& __nh) {
1917    _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(),
1918                                        "node_type with incompatible allocator passed to multimap::insert()");
1919    return __tree_.template __node_handle_insert_multi<node_type>(__hint.__i_, std::move(__nh));
1920  }
1921  _LIBCPP_HIDE_FROM_ABI node_type extract(key_type const& __key) {
1922    return __tree_.template __node_handle_extract<node_type>(__key);
1923  }
1924  _LIBCPP_HIDE_FROM_ABI node_type extract(const_iterator __it) {
1925    return __tree_.template __node_handle_extract<node_type>(__it.__i_);
1926  }
1927  template <class _Compare2>
1928  _LIBCPP_HIDE_FROM_ABI void merge(multimap<key_type, mapped_type, _Compare2, allocator_type>& __source) {
1929    _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
1930        __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
1931    return __tree_.__node_handle_merge_multi(__source.__tree_);
1932  }
1933  template <class _Compare2>
1934  _LIBCPP_HIDE_FROM_ABI void merge(multimap<key_type, mapped_type, _Compare2, allocator_type>&& __source) {
1935    _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
1936        __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
1937    return __tree_.__node_handle_merge_multi(__source.__tree_);
1938  }
1939  template <class _Compare2>
1940  _LIBCPP_HIDE_FROM_ABI void merge(map<key_type, mapped_type, _Compare2, allocator_type>& __source) {
1941    _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
1942        __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
1943    return __tree_.__node_handle_merge_multi(__source.__tree_);
1944  }
1945  template <class _Compare2>
1946  _LIBCPP_HIDE_FROM_ABI void merge(map<key_type, mapped_type, _Compare2, allocator_type>&& __source) {
1947    _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
1948        __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
1949    return __tree_.__node_handle_merge_multi(__source.__tree_);
1950  }
1951#endif
1952
1953  _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT { __tree_.clear(); }
1954
1955  _LIBCPP_HIDE_FROM_ABI void swap(multimap& __m) _NOEXCEPT_(__is_nothrow_swappable<__base>::value) {
1956    __tree_.swap(__m.__tree_);
1957  }
1958
1959  _LIBCPP_HIDE_FROM_ABI iterator find(const key_type& __k) { return __tree_.find(__k); }
1960  _LIBCPP_HIDE_FROM_ABI const_iterator find(const key_type& __k) const { return __tree_.find(__k); }
1961#if _LIBCPP_STD_VER >= 14
1962  template <typename _K2, enable_if_t<__is_transparent<_Compare, _K2>::value, int> = 0>
1963  _LIBCPP_HIDE_FROM_ABI iterator find(const _K2& __k) {
1964    return __tree_.find(__k);
1965  }
1966  template <typename _K2, enable_if_t<__is_transparent<_Compare, _K2>::value, int> = 0>
1967  _LIBCPP_HIDE_FROM_ABI const_iterator find(const _K2& __k) const {
1968    return __tree_.find(__k);
1969  }
1970#endif
1971
1972  _LIBCPP_HIDE_FROM_ABI size_type count(const key_type& __k) const { return __tree_.__count_multi(__k); }
1973#if _LIBCPP_STD_VER >= 14
1974  template <typename _K2, enable_if_t<__is_transparent<_Compare, _K2>::value, int> = 0>
1975  _LIBCPP_HIDE_FROM_ABI size_type count(const _K2& __k) const {
1976    return __tree_.__count_multi(__k);
1977  }
1978#endif
1979
1980#if _LIBCPP_STD_VER >= 20
1981  _LIBCPP_HIDE_FROM_ABI bool contains(const key_type& __k) const { return find(__k) != end(); }
1982  template <typename _K2, enable_if_t<__is_transparent<_Compare, _K2>::value, int> = 0>
1983  _LIBCPP_HIDE_FROM_ABI bool contains(const _K2& __k) const {
1984    return find(__k) != end();
1985  }
1986#endif // _LIBCPP_STD_VER >= 20
1987
1988  _LIBCPP_HIDE_FROM_ABI iterator lower_bound(const key_type& __k) { return __tree_.lower_bound(__k); }
1989  _LIBCPP_HIDE_FROM_ABI const_iterator lower_bound(const key_type& __k) const { return __tree_.lower_bound(__k); }
1990#if _LIBCPP_STD_VER >= 14
1991  template <typename _K2, enable_if_t<__is_transparent<_Compare, _K2>::value, int> = 0>
1992  _LIBCPP_HIDE_FROM_ABI iterator lower_bound(const _K2& __k) {
1993    return __tree_.lower_bound(__k);
1994  }
1995
1996  template <typename _K2, enable_if_t<__is_transparent<_Compare, _K2>::value, int> = 0>
1997  _LIBCPP_HIDE_FROM_ABI const_iterator lower_bound(const _K2& __k) const {
1998    return __tree_.lower_bound(__k);
1999  }
2000#endif
2001
2002  _LIBCPP_HIDE_FROM_ABI iterator upper_bound(const key_type& __k) { return __tree_.upper_bound(__k); }
2003  _LIBCPP_HIDE_FROM_ABI const_iterator upper_bound(const key_type& __k) const { return __tree_.upper_bound(__k); }
2004#if _LIBCPP_STD_VER >= 14
2005  template <typename _K2, enable_if_t<__is_transparent<_Compare, _K2>::value, int> = 0>
2006  _LIBCPP_HIDE_FROM_ABI iterator upper_bound(const _K2& __k) {
2007    return __tree_.upper_bound(__k);
2008  }
2009  template <typename _K2, enable_if_t<__is_transparent<_Compare, _K2>::value, int> = 0>
2010  _LIBCPP_HIDE_FROM_ABI const_iterator upper_bound(const _K2& __k) const {
2011    return __tree_.upper_bound(__k);
2012  }
2013#endif
2014
2015  _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const key_type& __k) {
2016    return __tree_.__equal_range_multi(__k);
2017  }
2018  _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const key_type& __k) const {
2019    return __tree_.__equal_range_multi(__k);
2020  }
2021#if _LIBCPP_STD_VER >= 14
2022  template <typename _K2, enable_if_t<__is_transparent<_Compare, _K2>::value, int> = 0>
2023  _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const _K2& __k) {
2024    return __tree_.__equal_range_multi(__k);
2025  }
2026  template <typename _K2, enable_if_t<__is_transparent<_Compare, _K2>::value, int> = 0>
2027  _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const _K2& __k) const {
2028    return __tree_.__equal_range_multi(__k);
2029  }
2030#endif
2031
2032private:
2033  typedef typename __base::__node __node;
2034  typedef typename __base::__node_allocator __node_allocator;
2035  typedef typename __base::__node_pointer __node_pointer;
2036
2037  typedef __map_node_destructor<__node_allocator> _Dp;
2038  typedef unique_ptr<__node, _Dp> __node_holder;
2039};
2040
2041#if _LIBCPP_STD_VER >= 17
2042template <class _InputIterator,
2043          class _Compare   = less<__iter_key_type<_InputIterator>>,
2044          class _Allocator = allocator<__iter_to_alloc_type<_InputIterator>>,
2045          class            = enable_if_t<__has_input_iterator_category<_InputIterator>::value, void>,
2046          class            = enable_if_t<!__is_allocator<_Compare>::value, void>,
2047          class            = enable_if_t<__is_allocator<_Allocator>::value, void>>
2048multimap(_InputIterator, _InputIterator, _Compare = _Compare(), _Allocator = _Allocator())
2049    -> multimap<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>, _Compare, _Allocator>;
2050
2051#  if _LIBCPP_STD_VER >= 23
2052template <ranges::input_range _Range,
2053          class _Compare   = less<__range_key_type<_Range>>,
2054          class _Allocator = allocator<__range_to_alloc_type<_Range>>,
2055          class            = enable_if_t<!__is_allocator<_Compare>::value, void>,
2056          class            = enable_if_t<__is_allocator<_Allocator>::value, void>>
2057multimap(from_range_t, _Range&&, _Compare = _Compare(), _Allocator = _Allocator())
2058    -> multimap<__range_key_type<_Range>, __range_mapped_type<_Range>, _Compare, _Allocator>;
2059#  endif
2060
2061template <class _Key,
2062          class _Tp,
2063          class _Compare   = less<remove_const_t<_Key>>,
2064          class _Allocator = allocator<pair<const _Key, _Tp>>,
2065          class            = enable_if_t<!__is_allocator<_Compare>::value, void>,
2066          class            = enable_if_t<__is_allocator<_Allocator>::value, void>>
2067multimap(initializer_list<pair<_Key, _Tp>>, _Compare = _Compare(), _Allocator = _Allocator())
2068    -> multimap<remove_const_t<_Key>, _Tp, _Compare, _Allocator>;
2069
2070template <class _InputIterator,
2071          class _Allocator,
2072          class = enable_if_t<__has_input_iterator_category<_InputIterator>::value, void>,
2073          class = enable_if_t<__is_allocator<_Allocator>::value, void>>
2074multimap(_InputIterator, _InputIterator, _Allocator)
2075    -> multimap<__iter_key_type<_InputIterator>,
2076                __iter_mapped_type<_InputIterator>,
2077                less<__iter_key_type<_InputIterator>>,
2078                _Allocator>;
2079
2080#  if _LIBCPP_STD_VER >= 23
2081template <ranges::input_range _Range, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value, void>>
2082multimap(from_range_t, _Range&&, _Allocator)
2083    -> multimap<__range_key_type<_Range>, __range_mapped_type<_Range>, less<__range_key_type<_Range>>, _Allocator>;
2084#  endif
2085
2086template <class _Key, class _Tp, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value, void>>
2087multimap(initializer_list<pair<_Key, _Tp>>, _Allocator)
2088    -> multimap<remove_const_t<_Key>, _Tp, less<remove_const_t<_Key>>, _Allocator>;
2089#endif
2090
2091#ifndef _LIBCPP_CXX03_LANG
2092template <class _Key, class _Tp, class _Compare, class _Allocator>
2093multimap<_Key, _Tp, _Compare, _Allocator>::multimap(multimap&& __m, const allocator_type& __a)
2094    : __tree_(std::move(__m.__tree_), typename __base::allocator_type(__a)) {
2095  if (__a != __m.get_allocator()) {
2096    const_iterator __e = cend();
2097    while (!__m.empty())
2098      __tree_.__insert_multi(__e.__i_, std::move(__m.__tree_.remove(__m.begin().__i_)->__value_.__move()));
2099  }
2100}
2101#endif
2102
2103template <class _Key, class _Tp, class _Compare, class _Allocator>
2104inline _LIBCPP_HIDE_FROM_ABI bool
2105operator==(const multimap<_Key, _Tp, _Compare, _Allocator>& __x, const multimap<_Key, _Tp, _Compare, _Allocator>& __y) {
2106  return __x.size() == __y.size() && std::equal(__x.begin(), __x.end(), __y.begin());
2107}
2108
2109#if _LIBCPP_STD_VER <= 17
2110
2111template <class _Key, class _Tp, class _Compare, class _Allocator>
2112inline _LIBCPP_HIDE_FROM_ABI bool
2113operator<(const multimap<_Key, _Tp, _Compare, _Allocator>& __x, const multimap<_Key, _Tp, _Compare, _Allocator>& __y) {
2114  return std::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
2115}
2116
2117template <class _Key, class _Tp, class _Compare, class _Allocator>
2118inline _LIBCPP_HIDE_FROM_ABI bool
2119operator!=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x, const multimap<_Key, _Tp, _Compare, _Allocator>& __y) {
2120  return !(__x == __y);
2121}
2122
2123template <class _Key, class _Tp, class _Compare, class _Allocator>
2124inline _LIBCPP_HIDE_FROM_ABI bool
2125operator>(const multimap<_Key, _Tp, _Compare, _Allocator>& __x, const multimap<_Key, _Tp, _Compare, _Allocator>& __y) {
2126  return __y < __x;
2127}
2128
2129template <class _Key, class _Tp, class _Compare, class _Allocator>
2130inline _LIBCPP_HIDE_FROM_ABI bool
2131operator>=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x, const multimap<_Key, _Tp, _Compare, _Allocator>& __y) {
2132  return !(__x < __y);
2133}
2134
2135template <class _Key, class _Tp, class _Compare, class _Allocator>
2136inline _LIBCPP_HIDE_FROM_ABI bool
2137operator<=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x, const multimap<_Key, _Tp, _Compare, _Allocator>& __y) {
2138  return !(__y < __x);
2139}
2140
2141#else // #if _LIBCPP_STD_VER <= 17
2142
2143template <class _Key, class _Tp, class _Compare, class _Allocator>
2144_LIBCPP_HIDE_FROM_ABI __synth_three_way_result<pair<const _Key, _Tp>>
2145operator<=>(const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
2146            const multimap<_Key, _Tp, _Compare, _Allocator>& __y) {
2147  return std::lexicographical_compare_three_way(
2148      __x.begin(),
2149      __x.end(),
2150      __y.begin(),
2151      __y.end(),
2152      std::__synth_three_way<pair<const _Key, _Tp>, pair<const _Key, _Tp>>);
2153}
2154
2155#endif // #if _LIBCPP_STD_VER <= 17
2156
2157template <class _Key, class _Tp, class _Compare, class _Allocator>
2158inline _LIBCPP_HIDE_FROM_ABI void
2159swap(multimap<_Key, _Tp, _Compare, _Allocator>& __x, multimap<_Key, _Tp, _Compare, _Allocator>& __y)
2160    _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) {
2161  __x.swap(__y);
2162}
2163
2164#if _LIBCPP_STD_VER >= 20
2165template <class _Key, class _Tp, class _Compare, class _Allocator, class _Predicate>
2166inline _LIBCPP_HIDE_FROM_ABI typename multimap<_Key, _Tp, _Compare, _Allocator>::size_type
2167erase_if(multimap<_Key, _Tp, _Compare, _Allocator>& __c, _Predicate __pred) {
2168  return std::__libcpp_erase_if_container(__c, __pred);
2169}
2170#endif
2171
2172_LIBCPP_END_NAMESPACE_STD
2173
2174#if _LIBCPP_STD_VER >= 17
2175_LIBCPP_BEGIN_NAMESPACE_STD
2176namespace pmr {
2177template <class _KeyT, class _ValueT, class _CompareT = std::less<_KeyT>>
2178using map _LIBCPP_AVAILABILITY_PMR =
2179    std::map<_KeyT, _ValueT, _CompareT, polymorphic_allocator<std::pair<const _KeyT, _ValueT>>>;
2180
2181template <class _KeyT, class _ValueT, class _CompareT = std::less<_KeyT>>
2182using multimap _LIBCPP_AVAILABILITY_PMR =
2183    std::multimap<_KeyT, _ValueT, _CompareT, polymorphic_allocator<std::pair<const _KeyT, _ValueT>>>;
2184} // namespace pmr
2185_LIBCPP_END_NAMESPACE_STD
2186#endif
2187
2188_LIBCPP_POP_MACROS
2189
2190#if !defined(_LIBCPP_REMOVE_TRANSITIVE_INCLUDES) && _LIBCPP_STD_VER <= 20
2191#  include <concepts>
2192#  include <cstdlib>
2193#  include <functional>
2194#  include <iterator>
2195#  include <type_traits>
2196#  include <utility>
2197#endif
2198
2199#endif // _LIBCPP_MAP
2200