llvm-project

1
// -*- C++ -*-
2
//===----------------------------------------------------------------------===//
3
//
4
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
5
// See https://llvm.org/LICENSE.txt for license information.
6
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7
//
8
//===----------------------------------------------------------------------===//
9

10
#ifndef _LIBCPP_MAP
11
#define _LIBCPP_MAP
12

13
/*
14

15
    map synopsis
16

17
namespace std
18
{
19

20
template <class Key, class T, class Compare = less<Key>,
21
          class Allocator = allocator<pair<const Key, T>>>
22
class map
23
{
24
public:
25
    // types:
26
    typedef Key                                      key_type;
27
    typedef T                                        mapped_type;
28
    typedef pair<const key_type, mapped_type>        value_type;
29
    typedef Compare                                  key_compare;
30
    typedef Allocator                                allocator_type;
31
    typedef typename allocator_type::reference       reference;
32
    typedef typename allocator_type::const_reference const_reference;
33
    typedef typename allocator_type::pointer         pointer;
34
    typedef typename allocator_type::const_pointer   const_pointer;
35
    typedef typename allocator_type::size_type       size_type;
36
    typedef typename allocator_type::difference_type difference_type;
37

38
    typedef implementation-defined                   iterator;
39
    typedef implementation-defined                   const_iterator;
40
    typedef std::reverse_iterator<iterator>          reverse_iterator;
41
    typedef std::reverse_iterator<const_iterator>    const_reverse_iterator;
42
    typedef unspecified                              node_type;              // C++17
43
    typedef INSERT_RETURN_TYPE<iterator, node_type>  insert_return_type;     // C++17
44

45
    class value_compare
46
    {
47
        friend class map;
48
    protected:
49
        key_compare comp;
50

51
        value_compare(key_compare c);
52
    public:
53
        typedef bool result_type;  // deprecated in C++17, removed in C++20
54
        typedef value_type first_argument_type;  // deprecated in C++17, removed in C++20
55
        typedef value_type second_argument_type;  // deprecated in C++17, removed in C++20
56
        bool operator()(const value_type& x, const value_type& y) const;
57
    };
58

59
    // construct/copy/destroy:
60
    map()
61
        noexcept(
62
            is_nothrow_default_constructible<allocator_type>::value &&
63
            is_nothrow_default_constructible<key_compare>::value &&
64
            is_nothrow_copy_constructible<key_compare>::value);
65
    explicit map(const key_compare& comp);
66
    map(const key_compare& comp, const allocator_type& a);
67
    template <class InputIterator>
68
        map(InputIterator first, InputIterator last,
69
            const key_compare& comp = key_compare());
70
    template <class InputIterator>
71
        map(InputIterator first, InputIterator last,
72
            const key_compare& comp, const allocator_type& a);
73
    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

233
template <class InputIterator,
234
      class Compare = less<iter_key_t<InputIterator>>,
235
      class Allocator = allocator<iter_to_alloc_t<InputIterator>>>
236
map(InputIterator, InputIterator, Compare = Compare(), Allocator = Allocator())
237
  -> map<iter_key_t<InputIterator>, iter_val_t<InputIterator>, Compare, Allocator>; // C++17
238

239
template<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

244
template<class Key, class T, class Compare = less<Key>,
245
    class Allocator = allocator<pair<const Key, T>>>
246
map(initializer_list<pair<const Key, T>>, Compare = Compare(), Allocator = Allocator())
247
  -> map<Key, T, Compare, Allocator>; // C++17
248

249
template <class InputIterator, class Allocator>
250
map(InputIterator, InputIterator, Allocator)
251
  -> map<iter_key_t<InputIterator>, iter_val_t<InputIterator>, less<iter_key_t<InputIterator>>,
252
    Allocator>; // C++17
253

254
template<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

258
template<class Key, class T, class Allocator>
259
map(initializer_list<pair<const Key, T>>, Allocator) -> map<Key, T, less<Key>, Allocator>; // C++17
260

261
template <class Key, class T, class Compare, class Allocator>
262
bool
263
operator==(const map<Key, T, Compare, Allocator>& x,
264
           const map<Key, T, Compare, Allocator>& y);
265

266
template <class Key, class T, class Compare, class Allocator>
267
bool
268
operator< (const map<Key, T, Compare, Allocator>& x,
269
           const map<Key, T, Compare, Allocator>& y);      // removed in C++20
270

271
template <class Key, class T, class Compare, class Allocator>
272
bool
273
operator!=(const map<Key, T, Compare, Allocator>& x,
274
           const map<Key, T, Compare, Allocator>& y);      // removed in C++20
275

276
template <class Key, class T, class Compare, class Allocator>
277
bool
278
operator> (const map<Key, T, Compare, Allocator>& x,
279
           const map<Key, T, Compare, Allocator>& y);      // removed in C++20
280

281
template <class Key, class T, class Compare, class Allocator>
282
bool
283
operator>=(const map<Key, T, Compare, Allocator>& x,
284
           const map<Key, T, Compare, Allocator>& y);      // removed in C++20
285

286
template <class Key, class T, class Compare, class Allocator>
287
bool
288
operator<=(const map<Key, T, Compare, Allocator>& x,
289
           const map<Key, T, Compare, Allocator>& y);      // removed in C++20
290

291
template<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:
297
template <class Key, class T, class Compare, class Allocator>
298
void
299
swap(map<Key, T, Compare, Allocator>& x, map<Key, T, Compare, Allocator>& y)
300
    noexcept(noexcept(x.swap(y)));
301

302
template <class Key, class T, class Compare, class Allocator, class Predicate>
303
typename map<Key, T, Compare, Allocator>::size_type
304
erase_if(map<Key, T, Compare, Allocator>& c, Predicate pred);  // C++20
305

306

307
template <class Key, class T, class Compare = less<Key>,
308
          class Allocator = allocator<pair<const Key, T>>>
309
class multimap
310
{
311
public:
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

495
template <class InputIterator,
496
      class Compare = less<iter_key_t<InputIterator>>,
497
      class Allocator = allocator<iter_to_alloc_t<InputIterator>>>
498
multimap(InputIterator, InputIterator, Compare = Compare(), Allocator = Allocator())
499
  -> multimap<iter_key_t<InputIterator>, iter_val_t<InputIterator>, Compare, Allocator>; // C++17
500

501
template<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

506
template<class Key, class T, class Compare = less<Key>,
507
    class Allocator = allocator<pair<const Key, T>>>
508
multimap(initializer_list<pair<const Key, T>>, Compare = Compare(), Allocator = Allocator())
509
  -> multimap<Key, T, Compare, Allocator>; // C++17
510

511
template <class InputIterator, class Allocator>
512
multimap(InputIterator, InputIterator, Allocator)
513
  -> multimap<iter_key_t<InputIterator>, iter_val_t<InputIterator>,
514
    less<iter_key_t<InputIterator>>, Allocator>; // C++17
515

516
template<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

520
template<class Key, class T, class Allocator>
521
multimap(initializer_list<pair<const Key, T>>, Allocator)
522
  -> multimap<Key, T, less<Key>, Allocator>; // C++17
523

524
template <class Key, class T, class Compare, class Allocator>
525
bool
526
operator==(const multimap<Key, T, Compare, Allocator>& x,
527
           const multimap<Key, T, Compare, Allocator>& y);
528

529
template <class Key, class T, class Compare, class Allocator>
530
bool
531
operator< (const multimap<Key, T, Compare, Allocator>& x,
532
           const multimap<Key, T, Compare, Allocator>& y);      // removed in C++20
533

534
template <class Key, class T, class Compare, class Allocator>
535
bool
536
operator!=(const multimap<Key, T, Compare, Allocator>& x,
537
           const multimap<Key, T, Compare, Allocator>& y);      // removed in C++20
538

539
template <class Key, class T, class Compare, class Allocator>
540
bool
541
operator> (const multimap<Key, T, Compare, Allocator>& x,
542
           const multimap<Key, T, Compare, Allocator>& y);      // removed in C++20
543

544
template <class Key, class T, class Compare, class Allocator>
545
bool
546
operator>=(const multimap<Key, T, Compare, Allocator>& x,
547
           const multimap<Key, T, Compare, Allocator>& y);      // removed in C++20
548

549
template <class Key, class T, class Compare, class Allocator>
550
bool
551
operator<=(const multimap<Key, T, Compare, Allocator>& x,
552
           const multimap<Key, T, Compare, Allocator>& y);      // removed in C++20
553

554
template<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:
560
template <class Key, class T, class Compare, class Allocator>
561
void
562
swap(multimap<Key, T, Compare, Allocator>& x,
563
     multimap<Key, T, Compare, Allocator>& y)
564
    noexcept(noexcept(x.swap(y)));
565

566
template <class Key, class T, class Compare, class Allocator, class Predicate>
567
typename multimap<Key, T, Compare, Allocator>::size_type
568
erase_if(multimap<Key, T, Compare, Allocator>& c, Predicate pred);  // C++20
569

570
}  // std
571

572
*/
573

574
#include <__algorithm/equal.h>
575
#include <__algorithm/lexicographical_compare.h>
576
#include <__algorithm/lexicographical_compare_three_way.h>
577
#include <__assert>
578
#include <__config>
579
#include <__functional/binary_function.h>
580
#include <__functional/is_transparent.h>
581
#include <__functional/operations.h>
582
#include <__iterator/erase_if_container.h>
583
#include <__iterator/iterator_traits.h>
584
#include <__iterator/ranges_iterator_traits.h>
585
#include <__iterator/reverse_iterator.h>
586
#include <__memory/addressof.h>
587
#include <__memory/allocator.h>
588
#include <__memory_resource/polymorphic_allocator.h>
589
#include <__node_handle>
590
#include <__ranges/concepts.h>
591
#include <__ranges/container_compatible_range.h>
592
#include <__ranges/from_range.h>
593
#include <__tree>
594
#include <__type_traits/is_allocator.h>
595
#include <__utility/forward.h>
596
#include <__utility/piecewise_construct.h>
597
#include <__utility/swap.h>
598
#include <stdexcept>
599
#include <tuple>
600
#include <version>
601

602
// standard-mandated includes
603

604
// [iterator.range]
605
#include <__iterator/access.h>
606
#include <__iterator/data.h>
607
#include <__iterator/empty.h>
608
#include <__iterator/reverse_access.h>
609
#include <__iterator/size.h>
610

611
// [associative.map.syn]
612
#include <compare>
613
#include <initializer_list>
614

615
#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
616
#  pragma GCC system_header
617
#endif
618

619
_LIBCPP_PUSH_MACROS
620
#include <__undef_macros>
621

622
_LIBCPP_BEGIN_NAMESPACE_STD
623

624
template <class _Key,
625
          class _CP,
626
          class _Compare,
627
          bool = is_empty<_Compare>::value && !__libcpp_is_final<_Compare>::value>
628
class __map_value_compare : private _Compare {
629
public:
630
  _LIBCPP_HIDE_FROM_ABI __map_value_compare() _NOEXCEPT_(is_nothrow_default_constructible<_Compare>::value)
631
      : _Compare() {}
632
  _LIBCPP_HIDE_FROM_ABI __map_value_compare(_Compare __c) _NOEXCEPT_(is_nothrow_copy_constructible<_Compare>::value)
633
      : _Compare(__c) {}
634
  _LIBCPP_HIDE_FROM_ABI const _Compare& key_comp() const _NOEXCEPT { return *this; }
635
  _LIBCPP_HIDE_FROM_ABI bool operator()(const _CP& __x, const _CP& __y) const {
636
    return static_cast<const _Compare&>(*this)(__x.__get_value().first, __y.__get_value().first);
637
  }
638
  _LIBCPP_HIDE_FROM_ABI bool operator()(const _CP& __x, const _Key& __y) const {
639
    return static_cast<const _Compare&>(*this)(__x.__get_value().first, __y);
640
  }
641
  _LIBCPP_HIDE_FROM_ABI bool operator()(const _Key& __x, const _CP& __y) const {
642
    return static_cast<const _Compare&>(*this)(__x, __y.__get_value().first);
643
  }
644
  _LIBCPP_HIDE_FROM_ABI void swap(__map_value_compare& __y) _NOEXCEPT_(__is_nothrow_swappable_v<_Compare>) {
645
    using std::swap;
646
    swap(static_cast<_Compare&>(*this), static_cast<_Compare&>(__y));
647
  }
648

649
#if _LIBCPP_STD_VER >= 14
650
  template <typename _K2>
651
  _LIBCPP_HIDE_FROM_ABI bool operator()(const _K2& __x, const _CP& __y) const {
652
    return static_cast<const _Compare&>(*this)(__x, __y.__get_value().first);
653
  }
654

655
  template <typename _K2>
656
  _LIBCPP_HIDE_FROM_ABI bool operator()(const _CP& __x, const _K2& __y) const {
657
    return static_cast<const _Compare&>(*this)(__x.__get_value().first, __y);
658
  }
659
#endif
660
};
661

662
template <class _Key, class _CP, class _Compare>
663
class __map_value_compare<_Key, _CP, _Compare, false> {
664
  _Compare __comp_;
665

666
public:
667
  _LIBCPP_HIDE_FROM_ABI __map_value_compare() _NOEXCEPT_(is_nothrow_default_constructible<_Compare>::value)
668
      : __comp_() {}
669
  _LIBCPP_HIDE_FROM_ABI __map_value_compare(_Compare __c) _NOEXCEPT_(is_nothrow_copy_constructible<_Compare>::value)
670
      : __comp_(__c) {}
671
  _LIBCPP_HIDE_FROM_ABI const _Compare& key_comp() const _NOEXCEPT { return __comp_; }
672

673
  _LIBCPP_HIDE_FROM_ABI bool operator()(const _CP& __x, const _CP& __y) const {
674
    return __comp_(__x.__get_value().first, __y.__get_value().first);
675
  }
676
  _LIBCPP_HIDE_FROM_ABI bool operator()(const _CP& __x, const _Key& __y) const {
677
    return __comp_(__x.__get_value().first, __y);
678
  }
679
  _LIBCPP_HIDE_FROM_ABI bool operator()(const _Key& __x, const _CP& __y) const {
680
    return __comp_(__x, __y.__get_value().first);
681
  }
682
  void swap(__map_value_compare& __y) _NOEXCEPT_(__is_nothrow_swappable_v<_Compare>) {
683
    using std::swap;
684
    swap(__comp_, __y.__comp_);
685
  }
686

687
#if _LIBCPP_STD_VER >= 14
688
  template <typename _K2>
689
  _LIBCPP_HIDE_FROM_ABI bool operator()(const _K2& __x, const _CP& __y) const {
690
    return __comp_(__x, __y.__get_value().first);
691
  }
692

693
  template <typename _K2>
694
  _LIBCPP_HIDE_FROM_ABI bool operator()(const _CP& __x, const _K2& __y) const {
695
    return __comp_(__x.__get_value().first, __y);
696
  }
697
#endif
698
};
699

700
template <class _Key, class _CP, class _Compare, bool __b>
701
inline _LIBCPP_HIDE_FROM_ABI void
702
swap(__map_value_compare<_Key, _CP, _Compare, __b>& __x, __map_value_compare<_Key, _CP, _Compare, __b>& __y)
703
    _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) {
704
  __x.swap(__y);
705
}
706

707
template <class _Allocator>
708
class __map_node_destructor {
709
  typedef _Allocator allocator_type;
710
  typedef allocator_traits<allocator_type> __alloc_traits;
711

712
public:
713
  typedef typename __alloc_traits::pointer pointer;
714

715
private:
716
  allocator_type& __na_;
717

718
public:
719
  bool __first_constructed;
720
  bool __second_constructed;
721

722
  _LIBCPP_HIDE_FROM_ABI explicit __map_node_destructor(allocator_type& __na) _NOEXCEPT
723
      : __na_(__na),
724
        __first_constructed(false),
725
        __second_constructed(false) {}
726

727
#ifndef _LIBCPP_CXX03_LANG
728
  _LIBCPP_HIDE_FROM_ABI __map_node_destructor(__tree_node_destructor<allocator_type>&& __x) _NOEXCEPT
729
      : __na_(__x.__na_),
730
        __first_constructed(__x.__value_constructed),
731
        __second_constructed(__x.__value_constructed) {
732
    __x.__value_constructed = false;
733
  }
734
#endif // _LIBCPP_CXX03_LANG
735

736
  __map_node_destructor& operator=(const __map_node_destructor&) = delete;
737

738
  _LIBCPP_HIDE_FROM_ABI void operator()(pointer __p) _NOEXCEPT {
739
    if (__second_constructed)
740
      __alloc_traits::destroy(__na_, std::addressof(__p->__value_.__get_value().second));
741
    if (__first_constructed)
742
      __alloc_traits::destroy(__na_, std::addressof(__p->__value_.__get_value().first));
743
    if (__p)
744
      __alloc_traits::deallocate(__na_, __p, 1);
745
  }
746
};
747

748
template <class _Key, class _Tp, class _Compare, class _Allocator>
749
class map;
750
template <class _Key, class _Tp, class _Compare, class _Allocator>
751
class multimap;
752
template <class _TreeIterator>
753
class __map_const_iterator;
754

755
#ifndef _LIBCPP_CXX03_LANG
756

757
template <class _Key, class _Tp>
758
struct _LIBCPP_STANDALONE_DEBUG __value_type {
759
  typedef _Key key_type;
760
  typedef _Tp mapped_type;
761
  typedef pair<const key_type, mapped_type> value_type;
762
  typedef pair<key_type&, mapped_type&> __nc_ref_pair_type;
763
  typedef pair<key_type&&, mapped_type&&> __nc_rref_pair_type;
764

765
private:
766
  value_type __cc_;
767

768
public:
769
  _LIBCPP_HIDE_FROM_ABI value_type& __get_value() {
770
#  if _LIBCPP_STD_VER >= 17
771
    return *std::launder(std::addressof(__cc_));
772
#  else
773
    return __cc_;
774
#  endif
775
  }
776

777
  _LIBCPP_HIDE_FROM_ABI const value_type& __get_value() const {
778
#  if _LIBCPP_STD_VER >= 17
779
    return *std::launder(std::addressof(__cc_));
780
#  else
781
    return __cc_;
782
#  endif
783
  }
784

785
  _LIBCPP_HIDE_FROM_ABI __nc_ref_pair_type __ref() {
786
    value_type& __v = __get_value();
787
    return __nc_ref_pair_type(const_cast<key_type&>(__v.first), __v.second);
788
  }
789

790
  _LIBCPP_HIDE_FROM_ABI __nc_rref_pair_type __move() {
791
    value_type& __v = __get_value();
792
    return __nc_rref_pair_type(std::move(const_cast<key_type&>(__v.first)), std::move(__v.second));
793
  }
794

795
  _LIBCPP_HIDE_FROM_ABI __value_type& operator=(const __value_type& __v) {
796
    __ref() = __v.__get_value();
797
    return *this;
798
  }
799

800
  _LIBCPP_HIDE_FROM_ABI __value_type& operator=(__value_type&& __v) {
801
    __ref() = __v.__move();
802
    return *this;
803
  }
804

805
  template <class _ValueTp, __enable_if_t<__is_same_uncvref<_ValueTp, value_type>::value, int> = 0>
806
  _LIBCPP_HIDE_FROM_ABI __value_type& operator=(_ValueTp&& __v) {
807
    __ref() = std::forward<_ValueTp>(__v);
808
    return *this;
809
  }
810

811
  __value_type()                    = delete;
812
  ~__value_type()                   = delete;
813
  __value_type(const __value_type&) = delete;
814
  __value_type(__value_type&&)      = delete;
815
};
816

817
#else
818

819
template <class _Key, class _Tp>
820
struct __value_type {
821
  typedef _Key key_type;
822
  typedef _Tp mapped_type;
823
  typedef pair<const key_type, mapped_type> value_type;
824

825
private:
826
  value_type __cc_;
827

828
public:
829
  _LIBCPP_HIDE_FROM_ABI value_type& __get_value() { return __cc_; }
830
  _LIBCPP_HIDE_FROM_ABI const value_type& __get_value() const { return __cc_; }
831

832
  __value_type()                               = delete;
833
  __value_type(__value_type const&)            = delete;
834
  __value_type& operator=(__value_type const&) = delete;
835
  ~__value_type()                              = delete;
836
};
837

838
#endif // _LIBCPP_CXX03_LANG
839

840
template <class _Tp>
841
struct __extract_key_value_types;
842

843
template <class _Key, class _Tp>
844
struct __extract_key_value_types<__value_type<_Key, _Tp> > {
845
  typedef _Key const __key_type;
846
  typedef _Tp __mapped_type;
847
};
848

849
template <class _TreeIterator>
850
class _LIBCPP_TEMPLATE_VIS __map_iterator {
851
  typedef typename _TreeIterator::_NodeTypes _NodeTypes;
852
  typedef typename _TreeIterator::__pointer_traits __pointer_traits;
853

854
  _TreeIterator __i_;
855

856
public:
857
  typedef bidirectional_iterator_tag iterator_category;
858
  typedef typename _NodeTypes::__map_value_type value_type;
859
  typedef typename _TreeIterator::difference_type difference_type;
860
  typedef value_type& reference;
861
  typedef typename _NodeTypes::__map_value_type_pointer pointer;
862

863
  _LIBCPP_HIDE_FROM_ABI __map_iterator() _NOEXCEPT {}
864

865
  _LIBCPP_HIDE_FROM_ABI __map_iterator(_TreeIterator __i) _NOEXCEPT : __i_(__i) {}
866

867
  _LIBCPP_HIDE_FROM_ABI reference operator*() const { return __i_->__get_value(); }
868
  _LIBCPP_HIDE_FROM_ABI pointer operator->() const { return pointer_traits<pointer>::pointer_to(__i_->__get_value()); }
869

870
  _LIBCPP_HIDE_FROM_ABI __map_iterator& operator++() {
871
    ++__i_;
872
    return *this;
873
  }
874
  _LIBCPP_HIDE_FROM_ABI __map_iterator operator++(int) {
875
    __map_iterator __t(*this);
876
    ++(*this);
877
    return __t;
878
  }
879

880
  _LIBCPP_HIDE_FROM_ABI __map_iterator& operator--() {
881
    --__i_;
882
    return *this;
883
  }
884
  _LIBCPP_HIDE_FROM_ABI __map_iterator operator--(int) {
885
    __map_iterator __t(*this);
886
    --(*this);
887
    return __t;
888
  }
889

890
  friend _LIBCPP_HIDE_FROM_ABI bool operator==(const __map_iterator& __x, const __map_iterator& __y) {
891
    return __x.__i_ == __y.__i_;
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

897
  template <class, class, class, class>
898
  friend class _LIBCPP_TEMPLATE_VIS map;
899
  template <class, class, class, class>
900
  friend class _LIBCPP_TEMPLATE_VIS multimap;
901
  template <class>
902
  friend class _LIBCPP_TEMPLATE_VIS __map_const_iterator;
903
};
904

905
template <class _TreeIterator>
906
class _LIBCPP_TEMPLATE_VIS __map_const_iterator {
907
  typedef typename _TreeIterator::_NodeTypes _NodeTypes;
908
  typedef typename _TreeIterator::__pointer_traits __pointer_traits;
909

910
  _TreeIterator __i_;
911

912
public:
913
  typedef bidirectional_iterator_tag iterator_category;
914
  typedef typename _NodeTypes::__map_value_type value_type;
915
  typedef typename _TreeIterator::difference_type difference_type;
916
  typedef const value_type& reference;
917
  typedef typename _NodeTypes::__const_map_value_type_pointer pointer;
918

919
  _LIBCPP_HIDE_FROM_ABI __map_const_iterator() _NOEXCEPT {}
920

921
  _LIBCPP_HIDE_FROM_ABI __map_const_iterator(_TreeIterator __i) _NOEXCEPT : __i_(__i) {}
922
  _LIBCPP_HIDE_FROM_ABI
923
  __map_const_iterator(__map_iterator< typename _TreeIterator::__non_const_iterator> __i) _NOEXCEPT : __i_(__i.__i_) {}
924

925
  _LIBCPP_HIDE_FROM_ABI reference operator*() const { return __i_->__get_value(); }
926
  _LIBCPP_HIDE_FROM_ABI pointer operator->() const { return pointer_traits<pointer>::pointer_to(__i_->__get_value()); }
927

928
  _LIBCPP_HIDE_FROM_ABI __map_const_iterator& operator++() {
929
    ++__i_;
930
    return *this;
931
  }
932
  _LIBCPP_HIDE_FROM_ABI __map_const_iterator operator++(int) {
933
    __map_const_iterator __t(*this);
934
    ++(*this);
935
    return __t;
936
  }
937

938
  _LIBCPP_HIDE_FROM_ABI __map_const_iterator& operator--() {
939
    --__i_;
940
    return *this;
941
  }
942
  _LIBCPP_HIDE_FROM_ABI __map_const_iterator operator--(int) {
943
    __map_const_iterator __t(*this);
944
    --(*this);
945
    return __t;
946
  }
947

948
  friend _LIBCPP_HIDE_FROM_ABI bool operator==(const __map_const_iterator& __x, const __map_const_iterator& __y) {
949
    return __x.__i_ == __y.__i_;
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

955
  template <class, class, class, class>
956
  friend class _LIBCPP_TEMPLATE_VIS map;
957
  template <class, class, class, class>
958
  friend class _LIBCPP_TEMPLATE_VIS multimap;
959
  template <class, class, class>
960
  friend class _LIBCPP_TEMPLATE_VIS __tree_const_iterator;
961
};
962

963
template <class _Key, class _Tp, class _Compare = less<_Key>, class _Allocator = allocator<pair<const _Key, _Tp> > >
964
class _LIBCPP_TEMPLATE_VIS map {
965
public:
966
  // types:
967
  typedef _Key key_type;
968
  typedef _Tp mapped_type;
969
  typedef pair<const key_type, mapped_type> value_type;
970
  typedef __type_identity_t<_Compare> key_compare;
971
  typedef __type_identity_t<_Allocator> allocator_type;
972
  typedef value_type& reference;
973
  typedef const value_type& const_reference;
974

975
  static_assert(is_same<typename allocator_type::value_type, value_type>::value,
976
                "Allocator::value_type must be same type as value_type");
977

978
  class _LIBCPP_TEMPLATE_VIS value_compare : public __binary_function<value_type, value_type, bool> {
979
    friend class map;
980

981
  protected:
982
    key_compare comp;
983

984
    _LIBCPP_HIDE_FROM_ABI value_compare(key_compare __c) : comp(__c) {}
985

986
  public:
987
    _LIBCPP_HIDE_FROM_ABI bool operator()(const value_type& __x, const value_type& __y) const {
988
      return comp(__x.first, __y.first);
989
    }
990
  };
991

992
private:
993
  typedef std::__value_type<key_type, mapped_type> __value_type;
994
  typedef __map_value_compare<key_type, __value_type, key_compare> __vc;
995
  typedef __rebind_alloc<allocator_traits<allocator_type>, __value_type> __allocator_type;
996
  typedef __tree<__value_type, __vc, __allocator_type> __base;
997
  typedef typename __base::__node_traits __node_traits;
998
  typedef allocator_traits<allocator_type> __alloc_traits;
999

1000
  static_assert(__check_valid_allocator<allocator_type>::value, "");
1001

1002
  __base __tree_;
1003

1004
public:
1005
  typedef typename __alloc_traits::pointer pointer;
1006
  typedef typename __alloc_traits::const_pointer const_pointer;
1007
  typedef typename __alloc_traits::size_type size_type;
1008
  typedef typename __alloc_traits::difference_type difference_type;
1009
  typedef __map_iterator<typename __base::iterator> iterator;
1010
  typedef __map_const_iterator<typename __base::const_iterator> const_iterator;
1011
  typedef std::reverse_iterator<iterator> reverse_iterator;
1012
  typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
1013

1014
#if _LIBCPP_STD_VER >= 17
1015
  typedef __map_node_handle<typename __base::__node, allocator_type> node_type;
1016
  typedef __insert_return_type<iterator, node_type> insert_return_type;
1017
#endif
1018

1019
  template <class _Key2, class _Value2, class _Comp2, class _Alloc2>
1020
  friend class _LIBCPP_TEMPLATE_VIS map;
1021
  template <class _Key2, class _Value2, class _Comp2, class _Alloc2>
1022
  friend class _LIBCPP_TEMPLATE_VIS multimap;
1023

1024
  _LIBCPP_HIDE_FROM_ABI map() _NOEXCEPT_(
1025
      is_nothrow_default_constructible<allocator_type>::value&& is_nothrow_default_constructible<key_compare>::value&&
1026
          is_nothrow_copy_constructible<key_compare>::value)
1027
      : __tree_(__vc(key_compare())) {}
1028

1029
  _LIBCPP_HIDE_FROM_ABI explicit map(const key_compare& __comp) _NOEXCEPT_(
1030
      is_nothrow_default_constructible<allocator_type>::value&& is_nothrow_copy_constructible<key_compare>::value)
1031
      : __tree_(__vc(__comp)) {}
1032

1033
  _LIBCPP_HIDE_FROM_ABI explicit map(const key_compare& __comp, const allocator_type& __a)
1034
      : __tree_(__vc(__comp), typename __base::allocator_type(__a)) {}
1035

1036
  template <class _InputIterator>
1037
  _LIBCPP_HIDE_FROM_ABI map(_InputIterator __f, _InputIterator __l, const key_compare& __comp = key_compare())
1038
      : __tree_(__vc(__comp)) {
1039
    insert(__f, __l);
1040
  }
1041

1042
  template <class _InputIterator>
1043
  _LIBCPP_HIDE_FROM_ABI
1044
  map(_InputIterator __f, _InputIterator __l, const key_compare& __comp, const allocator_type& __a)
1045
      : __tree_(__vc(__comp), typename __base::allocator_type(__a)) {
1046
    insert(__f, __l);
1047
  }
1048

1049
#if _LIBCPP_STD_VER >= 23
1050
  template <_ContainerCompatibleRange<value_type> _Range>
1051
  _LIBCPP_HIDE_FROM_ABI
1052
  map(from_range_t,
1053
      _Range&& __range,
1054
      const key_compare& __comp = key_compare(),
1055
      const allocator_type& __a = allocator_type())
1056
      : __tree_(__vc(__comp), typename __base::allocator_type(__a)) {
1057
    insert_range(std::forward<_Range>(__range));
1058
  }
1059
#endif
1060

1061
#if _LIBCPP_STD_VER >= 14
1062
  template <class _InputIterator>
1063
  _LIBCPP_HIDE_FROM_ABI map(_InputIterator __f, _InputIterator __l, const allocator_type& __a)
1064
      : map(__f, __l, key_compare(), __a) {}
1065
#endif
1066

1067
#if _LIBCPP_STD_VER >= 23
1068
  template <_ContainerCompatibleRange<value_type> _Range>
1069
  _LIBCPP_HIDE_FROM_ABI map(from_range_t, _Range&& __range, const allocator_type& __a)
1070
      : map(from_range, std::forward<_Range>(__range), key_compare(), __a) {}
1071
#endif
1072

1073
  _LIBCPP_HIDE_FROM_ABI map(const map& __m) : __tree_(__m.__tree_) { insert(__m.begin(), __m.end()); }
1074

1075
  _LIBCPP_HIDE_FROM_ABI map& operator=(const map& __m) {
1076
#ifndef _LIBCPP_CXX03_LANG
1077
    __tree_ = __m.__tree_;
1078
#else
1079
    if (this != std::addressof(__m)) {
1080
      __tree_.clear();
1081
      __tree_.value_comp() = __m.__tree_.value_comp();
1082
      __tree_.__copy_assign_alloc(__m.__tree_);
1083
      insert(__m.begin(), __m.end());
1084
    }
1085
#endif
1086
    return *this;
1087
  }
1088

1089
#ifndef _LIBCPP_CXX03_LANG
1090

1091
  _LIBCPP_HIDE_FROM_ABI map(map&& __m) noexcept(is_nothrow_move_constructible<__base>::value)
1092
      : __tree_(std::move(__m.__tree_)) {}
1093

1094
  _LIBCPP_HIDE_FROM_ABI map(map&& __m, const allocator_type& __a);
1095

1096
  _LIBCPP_HIDE_FROM_ABI map& operator=(map&& __m) noexcept(is_nothrow_move_assignable<__base>::value) {
1097
    __tree_ = std::move(__m.__tree_);
1098
    return *this;
1099
  }
1100

1101
  _LIBCPP_HIDE_FROM_ABI map(initializer_list<value_type> __il, const key_compare& __comp = key_compare())
1102
      : __tree_(__vc(__comp)) {
1103
    insert(__il.begin(), __il.end());
1104
  }
1105

1106
  _LIBCPP_HIDE_FROM_ABI map(initializer_list<value_type> __il, const key_compare& __comp, const allocator_type& __a)
1107
      : __tree_(__vc(__comp), typename __base::allocator_type(__a)) {
1108
    insert(__il.begin(), __il.end());
1109
  }
1110

1111
#  if _LIBCPP_STD_VER >= 14
1112
  _LIBCPP_HIDE_FROM_ABI map(initializer_list<value_type> __il, const allocator_type& __a)
1113
      : map(__il, key_compare(), __a) {}
1114
#  endif
1115

1116
  _LIBCPP_HIDE_FROM_ABI map& operator=(initializer_list<value_type> __il) {
1117
    __tree_.__assign_unique(__il.begin(), __il.end());
1118
    return *this;
1119
  }
1120

1121
#endif // _LIBCPP_CXX03_LANG
1122

1123
  _LIBCPP_HIDE_FROM_ABI explicit map(const allocator_type& __a) : __tree_(typename __base::allocator_type(__a)) {}
1124

1125
  _LIBCPP_HIDE_FROM_ABI map(const map& __m, const allocator_type& __a)
1126
      : __tree_(__m.__tree_.value_comp(), typename __base::allocator_type(__a)) {
1127
    insert(__m.begin(), __m.end());
1128
  }
1129

1130
  _LIBCPP_HIDE_FROM_ABI ~map() { static_assert(sizeof(__diagnose_non_const_comparator<_Key, _Compare>()), ""); }
1131

1132
  _LIBCPP_HIDE_FROM_ABI iterator begin() _NOEXCEPT { return __tree_.begin(); }
1133
  _LIBCPP_HIDE_FROM_ABI const_iterator begin() const _NOEXCEPT { return __tree_.begin(); }
1134
  _LIBCPP_HIDE_FROM_ABI iterator end() _NOEXCEPT { return __tree_.end(); }
1135
  _LIBCPP_HIDE_FROM_ABI const_iterator end() const _NOEXCEPT { return __tree_.end(); }
1136

1137
  _LIBCPP_HIDE_FROM_ABI reverse_iterator rbegin() _NOEXCEPT { return reverse_iterator(end()); }
1138
  _LIBCPP_HIDE_FROM_ABI const_reverse_iterator rbegin() const _NOEXCEPT { return const_reverse_iterator(end()); }
1139
  _LIBCPP_HIDE_FROM_ABI reverse_iterator rend() _NOEXCEPT { return reverse_iterator(begin()); }
1140
  _LIBCPP_HIDE_FROM_ABI const_reverse_iterator rend() const _NOEXCEPT { return const_reverse_iterator(begin()); }
1141

1142
  _LIBCPP_HIDE_FROM_ABI const_iterator cbegin() const _NOEXCEPT { return begin(); }
1143
  _LIBCPP_HIDE_FROM_ABI const_iterator cend() const _NOEXCEPT { return end(); }
1144
  _LIBCPP_HIDE_FROM_ABI const_reverse_iterator crbegin() const _NOEXCEPT { return rbegin(); }
1145
  _LIBCPP_HIDE_FROM_ABI const_reverse_iterator crend() const _NOEXCEPT { return rend(); }
1146

1147
  _LIBCPP_NODISCARD _LIBCPP_HIDE_FROM_ABI bool empty() const _NOEXCEPT { return __tree_.size() == 0; }
1148
  _LIBCPP_HIDE_FROM_ABI size_type size() const _NOEXCEPT { return __tree_.size(); }
1149
  _LIBCPP_HIDE_FROM_ABI size_type max_size() const _NOEXCEPT { return __tree_.max_size(); }
1150

1151
  _LIBCPP_HIDE_FROM_ABI mapped_type& operator[](const key_type& __k);
1152
#ifndef _LIBCPP_CXX03_LANG
1153
  _LIBCPP_HIDE_FROM_ABI mapped_type& operator[](key_type&& __k);
1154
#endif
1155

1156
  _LIBCPP_HIDE_FROM_ABI mapped_type& at(const key_type& __k);
1157
  _LIBCPP_HIDE_FROM_ABI const mapped_type& at(const key_type& __k) const;
1158

1159
  _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const _NOEXCEPT { return allocator_type(__tree_.__alloc()); }
1160
  _LIBCPP_HIDE_FROM_ABI key_compare key_comp() const { return __tree_.value_comp().key_comp(); }
1161
  _LIBCPP_HIDE_FROM_ABI value_compare value_comp() const { return value_compare(__tree_.value_comp().key_comp()); }
1162

1163
#ifndef _LIBCPP_CXX03_LANG
1164
  template <class... _Args>
1165
  _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> emplace(_Args&&... __args) {
1166
    return __tree_.__emplace_unique(std::forward<_Args>(__args)...);
1167
  }
1168

1169
  template <class... _Args>
1170
  _LIBCPP_HIDE_FROM_ABI iterator emplace_hint(const_iterator __p, _Args&&... __args) {
1171
    return __tree_.__emplace_hint_unique(__p.__i_, std::forward<_Args>(__args)...);
1172
  }
1173

1174
  template <class _Pp, __enable_if_t<is_constructible<value_type, _Pp>::value, int> = 0>
1175
  _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert(_Pp&& __p) {
1176
    return __tree_.__insert_unique(std::forward<_Pp>(__p));
1177
  }
1178

1179
  template <class _Pp, __enable_if_t<is_constructible<value_type, _Pp>::value, int> = 0>
1180
  _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __pos, _Pp&& __p) {
1181
    return __tree_.__insert_unique(__pos.__i_, std::forward<_Pp>(__p));
1182
  }
1183

1184
#endif // _LIBCPP_CXX03_LANG
1185

1186
  _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert(const value_type& __v) { return __tree_.__insert_unique(__v); }
1187

1188
  _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, const value_type& __v) {
1189
    return __tree_.__insert_unique(__p.__i_, __v);
1190
  }
1191

1192
#ifndef _LIBCPP_CXX03_LANG
1193
  _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert(value_type&& __v) {
1194
    return __tree_.__insert_unique(std::move(__v));
1195
  }
1196

1197
  _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, value_type&& __v) {
1198
    return __tree_.__insert_unique(__p.__i_, std::move(__v));
1199
  }
1200

1201
  _LIBCPP_HIDE_FROM_ABI void insert(initializer_list<value_type> __il) { insert(__il.begin(), __il.end()); }
1202
#endif
1203

1204
  template <class _InputIterator>
1205
  _LIBCPP_HIDE_FROM_ABI void insert(_InputIterator __f, _InputIterator __l) {
1206
    for (const_iterator __e = cend(); __f != __l; ++__f)
1207
      insert(__e.__i_, *__f);
1208
  }
1209

1210
#if _LIBCPP_STD_VER >= 23
1211
  template <_ContainerCompatibleRange<value_type> _Range>
1212
  _LIBCPP_HIDE_FROM_ABI void insert_range(_Range&& __range) {
1213
    const_iterator __end = cend();
1214
    for (auto&& __element : __range) {
1215
      insert(__end.__i_, std::forward<decltype(__element)>(__element));
1216
    }
1217
  }
1218
#endif
1219

1220
#if _LIBCPP_STD_VER >= 17
1221

1222
  template <class... _Args>
1223
  _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> try_emplace(const key_type& __k, _Args&&... __args) {
1224
    return __tree_.__emplace_unique_key_args(
1225
        __k,
1226
        std::piecewise_construct,
1227
        std::forward_as_tuple(__k),
1228
        std::forward_as_tuple(std::forward<_Args>(__args)...));
1229
  }
1230

1231
  template <class... _Args>
1232
  _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> try_emplace(key_type&& __k, _Args&&... __args) {
1233
    return __tree_.__emplace_unique_key_args(
1234
        __k,
1235
        std::piecewise_construct,
1236
        std::forward_as_tuple(std::move(__k)),
1237
        std::forward_as_tuple(std::forward<_Args>(__args)...));
1238
  }
1239

1240
  template <class... _Args>
1241
  _LIBCPP_HIDE_FROM_ABI iterator try_emplace(const_iterator __h, const key_type& __k, _Args&&... __args) {
1242
    return __tree_
1243
        .__emplace_hint_unique_key_args(
1244
            __h.__i_,
1245
            __k,
1246
            std::piecewise_construct,
1247
            std::forward_as_tuple(__k),
1248
            std::forward_as_tuple(std::forward<_Args>(__args)...))
1249
        .first;
1250
  }
1251

1252
  template <class... _Args>
1253
  _LIBCPP_HIDE_FROM_ABI iterator try_emplace(const_iterator __h, key_type&& __k, _Args&&... __args) {
1254
    return __tree_
1255
        .__emplace_hint_unique_key_args(
1256
            __h.__i_,
1257
            __k,
1258
            std::piecewise_construct,
1259
            std::forward_as_tuple(std::move(__k)),
1260
            std::forward_as_tuple(std::forward<_Args>(__args)...))
1261
        .first;
1262
  }
1263

1264
  template <class _Vp>
1265
  _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert_or_assign(const key_type& __k, _Vp&& __v) {
1266
    iterator __p = lower_bound(__k);
1267
    if (__p != end() && !key_comp()(__k, __p->first)) {
1268
      __p->second = std::forward<_Vp>(__v);
1269
      return std::make_pair(__p, false);
1270
    }
1271
    return std::make_pair(emplace_hint(__p, __k, std::forward<_Vp>(__v)), true);
1272
  }
1273

1274
  template <class _Vp>
1275
  _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert_or_assign(key_type&& __k, _Vp&& __v) {
1276
    iterator __p = lower_bound(__k);
1277
    if (__p != end() && !key_comp()(__k, __p->first)) {
1278
      __p->second = std::forward<_Vp>(__v);
1279
      return std::make_pair(__p, false);
1280
    }
1281
    return std::make_pair(emplace_hint(__p, std::move(__k), std::forward<_Vp>(__v)), true);
1282
  }
1283

1284
  template <class _Vp>
1285
  _LIBCPP_HIDE_FROM_ABI iterator insert_or_assign(const_iterator __h, const key_type& __k, _Vp&& __v) {
1286
    auto [__r, __inserted] = __tree_.__emplace_hint_unique_key_args(__h.__i_, __k, __k, std::forward<_Vp>(__v));
1287

1288
    if (!__inserted)
1289
      __r->__get_value().second = std::forward<_Vp>(__v);
1290

1291
    return __r;
1292
  }
1293

1294
  template <class _Vp>
1295
  _LIBCPP_HIDE_FROM_ABI iterator insert_or_assign(const_iterator __h, key_type&& __k, _Vp&& __v) {
1296
    auto [__r, __inserted] =
1297
        __tree_.__emplace_hint_unique_key_args(__h.__i_, __k, std::move(__k), std::forward<_Vp>(__v));
1298

1299
    if (!__inserted)
1300
      __r->__get_value().second = std::forward<_Vp>(__v);
1301

1302
    return __r;
1303
  }
1304

1305
#endif // _LIBCPP_STD_VER >= 17
1306

1307
  _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __p) { return __tree_.erase(__p.__i_); }
1308
  _LIBCPP_HIDE_FROM_ABI iterator erase(iterator __p) { return __tree_.erase(__p.__i_); }
1309
  _LIBCPP_HIDE_FROM_ABI size_type erase(const key_type& __k) { return __tree_.__erase_unique(__k); }
1310
  _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __f, const_iterator __l) {
1311
    return __tree_.erase(__f.__i_, __l.__i_);
1312
  }
1313
  _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT { __tree_.clear(); }
1314

1315
#if _LIBCPP_STD_VER >= 17
1316
  _LIBCPP_HIDE_FROM_ABI insert_return_type insert(node_type&& __nh) {
1317
    _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(),
1318
                                        "node_type with incompatible allocator passed to map::insert()");
1319
    return __tree_.template __node_handle_insert_unique< node_type, insert_return_type>(std::move(__nh));
1320
  }
1321
  _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __hint, 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>(__hint.__i_, std::move(__nh));
1325
  }
1326
  _LIBCPP_HIDE_FROM_ABI node_type extract(key_type const& __key) {
1327
    return __tree_.template __node_handle_extract<node_type>(__key);
1328
  }
1329
  _LIBCPP_HIDE_FROM_ABI node_type extract(const_iterator __it) {
1330
    return __tree_.template __node_handle_extract<node_type>(__it.__i_);
1331
  }
1332
  template <class _Compare2>
1333
  _LIBCPP_HIDE_FROM_ABI void merge(map<key_type, mapped_type, _Compare2, allocator_type>& __source) {
1334
    _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
1335
        __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
1336
    __tree_.__node_handle_merge_unique(__source.__tree_);
1337
  }
1338
  template <class _Compare2>
1339
  _LIBCPP_HIDE_FROM_ABI void merge(map<key_type, mapped_type, _Compare2, allocator_type>&& __source) {
1340
    _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
1341
        __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
1342
    __tree_.__node_handle_merge_unique(__source.__tree_);
1343
  }
1344
  template <class _Compare2>
1345
  _LIBCPP_HIDE_FROM_ABI void merge(multimap<key_type, mapped_type, _Compare2, allocator_type>& __source) {
1346
    _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
1347
        __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
1348
    __tree_.__node_handle_merge_unique(__source.__tree_);
1349
  }
1350
  template <class _Compare2>
1351
  _LIBCPP_HIDE_FROM_ABI void merge(multimap<key_type, mapped_type, _Compare2, allocator_type>&& __source) {
1352
    _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
1353
        __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
1354
    __tree_.__node_handle_merge_unique(__source.__tree_);
1355
  }
1356
#endif
1357

1358
  _LIBCPP_HIDE_FROM_ABI void swap(map& __m) _NOEXCEPT_(__is_nothrow_swappable_v<__base>) { __tree_.swap(__m.__tree_); }
1359

1360
  _LIBCPP_HIDE_FROM_ABI iterator find(const key_type& __k) { return __tree_.find(__k); }
1361
  _LIBCPP_HIDE_FROM_ABI const_iterator find(const key_type& __k) const { return __tree_.find(__k); }
1362
#if _LIBCPP_STD_VER >= 14
1363
  template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
1364
  _LIBCPP_HIDE_FROM_ABI iterator find(const _K2& __k) {
1365
    return __tree_.find(__k);
1366
  }
1367
  template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
1368
  _LIBCPP_HIDE_FROM_ABI const_iterator find(const _K2& __k) const {
1369
    return __tree_.find(__k);
1370
  }
1371
#endif
1372

1373
  _LIBCPP_HIDE_FROM_ABI size_type count(const key_type& __k) const { return __tree_.__count_unique(__k); }
1374
#if _LIBCPP_STD_VER >= 14
1375
  template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
1376
  _LIBCPP_HIDE_FROM_ABI size_type count(const _K2& __k) const {
1377
    return __tree_.__count_multi(__k);
1378
  }
1379
#endif
1380

1381
#if _LIBCPP_STD_VER >= 20
1382
  _LIBCPP_HIDE_FROM_ABI bool contains(const key_type& __k) const { return find(__k) != end(); }
1383
  template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
1384
  _LIBCPP_HIDE_FROM_ABI bool contains(const _K2& __k) const {
1385
    return find(__k) != end();
1386
  }
1387
#endif // _LIBCPP_STD_VER >= 20
1388

1389
  _LIBCPP_HIDE_FROM_ABI iterator lower_bound(const key_type& __k) { return __tree_.lower_bound(__k); }
1390
  _LIBCPP_HIDE_FROM_ABI const_iterator lower_bound(const key_type& __k) const { return __tree_.lower_bound(__k); }
1391
#if _LIBCPP_STD_VER >= 14
1392
  template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
1393
  _LIBCPP_HIDE_FROM_ABI iterator lower_bound(const _K2& __k) {
1394
    return __tree_.lower_bound(__k);
1395
  }
1396

1397
  template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
1398
  _LIBCPP_HIDE_FROM_ABI const_iterator lower_bound(const _K2& __k) const {
1399
    return __tree_.lower_bound(__k);
1400
  }
1401
#endif
1402

1403
  _LIBCPP_HIDE_FROM_ABI iterator upper_bound(const key_type& __k) { return __tree_.upper_bound(__k); }
1404
  _LIBCPP_HIDE_FROM_ABI const_iterator upper_bound(const key_type& __k) const { return __tree_.upper_bound(__k); }
1405
#if _LIBCPP_STD_VER >= 14
1406
  template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
1407
  _LIBCPP_HIDE_FROM_ABI iterator upper_bound(const _K2& __k) {
1408
    return __tree_.upper_bound(__k);
1409
  }
1410
  template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
1411
  _LIBCPP_HIDE_FROM_ABI const_iterator upper_bound(const _K2& __k) const {
1412
    return __tree_.upper_bound(__k);
1413
  }
1414
#endif
1415

1416
  _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const key_type& __k) {
1417
    return __tree_.__equal_range_unique(__k);
1418
  }
1419
  _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const key_type& __k) const {
1420
    return __tree_.__equal_range_unique(__k);
1421
  }
1422
#if _LIBCPP_STD_VER >= 14
1423
  template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
1424
  _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const _K2& __k) {
1425
    return __tree_.__equal_range_multi(__k);
1426
  }
1427
  template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
1428
  _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const _K2& __k) const {
1429
    return __tree_.__equal_range_multi(__k);
1430
  }
1431
#endif
1432

1433
private:
1434
  typedef typename __base::__node __node;
1435
  typedef typename __base::__node_allocator __node_allocator;
1436
  typedef typename __base::__node_pointer __node_pointer;
1437
  typedef typename __base::__node_base_pointer __node_base_pointer;
1438
  typedef typename __base::__parent_pointer __parent_pointer;
1439

1440
  typedef __map_node_destructor<__node_allocator> _Dp;
1441
  typedef unique_ptr<__node, _Dp> __node_holder;
1442

1443
#ifdef _LIBCPP_CXX03_LANG
1444
  _LIBCPP_HIDE_FROM_ABI __node_holder __construct_node_with_key(const key_type& __k);
1445
#endif
1446
};
1447

1448
#if _LIBCPP_STD_VER >= 17
1449
template <class _InputIterator,
1450
          class _Compare   = less<__iter_key_type<_InputIterator>>,
1451
          class _Allocator = allocator<__iter_to_alloc_type<_InputIterator>>,
1452
          class            = enable_if_t<__has_input_iterator_category<_InputIterator>::value, void>,
1453
          class            = enable_if_t<!__is_allocator<_Compare>::value, void>,
1454
          class            = enable_if_t<__is_allocator<_Allocator>::value, void>>
1455
map(_InputIterator, _InputIterator, _Compare = _Compare(), _Allocator = _Allocator())
1456
    -> map<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>, _Compare, _Allocator>;
1457

1458
#  if _LIBCPP_STD_VER >= 23
1459
template <ranges::input_range _Range,
1460
          class _Compare   = less<__range_key_type<_Range>>,
1461
          class _Allocator = allocator<__range_to_alloc_type<_Range>>,
1462
          class            = enable_if_t<!__is_allocator<_Compare>::value, void>,
1463
          class            = enable_if_t<__is_allocator<_Allocator>::value, void>>
1464
map(from_range_t, _Range&&, _Compare = _Compare(), _Allocator = _Allocator())
1465
    -> map<__range_key_type<_Range>, __range_mapped_type<_Range>, _Compare, _Allocator>;
1466
#  endif
1467

1468
template <class _Key,
1469
          class _Tp,
1470
          class _Compare   = less<remove_const_t<_Key>>,
1471
          class _Allocator = allocator<pair<const _Key, _Tp>>,
1472
          class            = enable_if_t<!__is_allocator<_Compare>::value, void>,
1473
          class            = enable_if_t<__is_allocator<_Allocator>::value, void>>
1474
map(initializer_list<pair<_Key, _Tp>>,
1475
    _Compare   = _Compare(),
1476
    _Allocator = _Allocator()) -> map<remove_const_t<_Key>, _Tp, _Compare, _Allocator>;
1477

1478
template <class _InputIterator,
1479
          class _Allocator,
1480
          class = enable_if_t<__has_input_iterator_category<_InputIterator>::value, void>,
1481
          class = enable_if_t<__is_allocator<_Allocator>::value, void>>
1482
map(_InputIterator, _InputIterator, _Allocator)
1483
    -> map<__iter_key_type<_InputIterator>,
1484
           __iter_mapped_type<_InputIterator>,
1485
           less<__iter_key_type<_InputIterator>>,
1486
           _Allocator>;
1487

1488
#  if _LIBCPP_STD_VER >= 23
1489
template <ranges::input_range _Range, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value, void>>
1490
map(from_range_t, _Range&&, _Allocator)
1491
    -> map<__range_key_type<_Range>, __range_mapped_type<_Range>, less<__range_key_type<_Range>>, _Allocator>;
1492
#  endif
1493

1494
template <class _Key, class _Tp, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value, void>>
1495
map(initializer_list<pair<_Key, _Tp>>,
1496
    _Allocator) -> map<remove_const_t<_Key>, _Tp, less<remove_const_t<_Key>>, _Allocator>;
1497
#endif
1498

1499
#ifndef _LIBCPP_CXX03_LANG
1500
template <class _Key, class _Tp, class _Compare, class _Allocator>
1501
map<_Key, _Tp, _Compare, _Allocator>::map(map&& __m, const allocator_type& __a)
1502
    : __tree_(std::move(__m.__tree_), typename __base::allocator_type(__a)) {
1503
  if (__a != __m.get_allocator()) {
1504
    const_iterator __e = cend();
1505
    while (!__m.empty())
1506
      __tree_.__insert_unique(__e.__i_, __m.__tree_.remove(__m.begin().__i_)->__value_.__move());
1507
  }
1508
}
1509

1510
template <class _Key, class _Tp, class _Compare, class _Allocator>
1511
_Tp& map<_Key, _Tp, _Compare, _Allocator>::operator[](const key_type& __k) {
1512
  return __tree_
1513
      .__emplace_unique_key_args(__k, std::piecewise_construct, std::forward_as_tuple(__k), std::forward_as_tuple())
1514
      .first->__get_value()
1515
      .second;
1516
}
1517

1518
template <class _Key, class _Tp, class _Compare, class _Allocator>
1519
_Tp& map<_Key, _Tp, _Compare, _Allocator>::operator[](key_type&& __k) {
1520
  // TODO investigate this clang-tidy warning.
1521
  // NOLINTBEGIN(bugprone-use-after-move)
1522
  return __tree_
1523
      .__emplace_unique_key_args(
1524
          __k, std::piecewise_construct, std::forward_as_tuple(std::move(__k)), std::forward_as_tuple())
1525
      .first->__get_value()
1526
      .second;
1527
  // NOLINTEND(bugprone-use-after-move)
1528
}
1529

1530
#else // _LIBCPP_CXX03_LANG
1531

1532
template <class _Key, class _Tp, class _Compare, class _Allocator>
1533
typename map<_Key, _Tp, _Compare, _Allocator>::__node_holder
1534
map<_Key, _Tp, _Compare, _Allocator>::__construct_node_with_key(const key_type& __k) {
1535
  __node_allocator& __na = __tree_.__node_alloc();
1536
  __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1537
  __node_traits::construct(__na, std::addressof(__h->__value_.__get_value().first), __k);
1538
  __h.get_deleter().__first_constructed = true;
1539
  __node_traits::construct(__na, std::addressof(__h->__value_.__get_value().second));
1540
  __h.get_deleter().__second_constructed = true;
1541
  return __h;
1542
}
1543

1544
template <class _Key, class _Tp, class _Compare, class _Allocator>
1545
_Tp& map<_Key, _Tp, _Compare, _Allocator>::operator[](const key_type& __k) {
1546
  __parent_pointer __parent;
1547
  __node_base_pointer& __child = __tree_.__find_equal(__parent, __k);
1548
  __node_pointer __r           = static_cast<__node_pointer>(__child);
1549
  if (__child == nullptr) {
1550
    __node_holder __h = __construct_node_with_key(__k);
1551
    __tree_.__insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
1552
    __r = __h.release();
1553
  }
1554
  return __r->__value_.__get_value().second;
1555
}
1556

1557
#endif // _LIBCPP_CXX03_LANG
1558

1559
template <class _Key, class _Tp, class _Compare, class _Allocator>
1560
_Tp& map<_Key, _Tp, _Compare, _Allocator>::at(const key_type& __k) {
1561
  __parent_pointer __parent;
1562
  __node_base_pointer& __child = __tree_.__find_equal(__parent, __k);
1563
  if (__child == nullptr)
1564
    __throw_out_of_range("map::at:  key not found");
1565
  return static_cast<__node_pointer>(__child)->__value_.__get_value().second;
1566
}
1567

1568
template <class _Key, class _Tp, class _Compare, class _Allocator>
1569
const _Tp& map<_Key, _Tp, _Compare, _Allocator>::at(const key_type& __k) const {
1570
  __parent_pointer __parent;
1571
  __node_base_pointer __child = __tree_.__find_equal(__parent, __k);
1572
  if (__child == nullptr)
1573
    __throw_out_of_range("map::at:  key not found");
1574
  return static_cast<__node_pointer>(__child)->__value_.__get_value().second;
1575
}
1576

1577
template <class _Key, class _Tp, class _Compare, class _Allocator>
1578
inline _LIBCPP_HIDE_FROM_ABI bool
1579
operator==(const map<_Key, _Tp, _Compare, _Allocator>& __x, const map<_Key, _Tp, _Compare, _Allocator>& __y) {
1580
  return __x.size() == __y.size() && std::equal(__x.begin(), __x.end(), __y.begin());
1581
}
1582

1583
#if _LIBCPP_STD_VER <= 17
1584

1585
template <class _Key, class _Tp, class _Compare, class _Allocator>
1586
inline _LIBCPP_HIDE_FROM_ABI bool
1587
operator<(const map<_Key, _Tp, _Compare, _Allocator>& __x, const map<_Key, _Tp, _Compare, _Allocator>& __y) {
1588
  return std::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
1589
}
1590

1591
template <class _Key, class _Tp, class _Compare, class _Allocator>
1592
inline _LIBCPP_HIDE_FROM_ABI bool
1593
operator!=(const map<_Key, _Tp, _Compare, _Allocator>& __x, const map<_Key, _Tp, _Compare, _Allocator>& __y) {
1594
  return !(__x == __y);
1595
}
1596

1597
template <class _Key, class _Tp, class _Compare, class _Allocator>
1598
inline _LIBCPP_HIDE_FROM_ABI bool
1599
operator>(const map<_Key, _Tp, _Compare, _Allocator>& __x, const map<_Key, _Tp, _Compare, _Allocator>& __y) {
1600
  return __y < __x;
1601
}
1602

1603
template <class _Key, class _Tp, class _Compare, class _Allocator>
1604
inline _LIBCPP_HIDE_FROM_ABI bool
1605
operator>=(const map<_Key, _Tp, _Compare, _Allocator>& __x, const map<_Key, _Tp, _Compare, _Allocator>& __y) {
1606
  return !(__x < __y);
1607
}
1608

1609
template <class _Key, class _Tp, class _Compare, class _Allocator>
1610
inline _LIBCPP_HIDE_FROM_ABI bool
1611
operator<=(const map<_Key, _Tp, _Compare, _Allocator>& __x, const map<_Key, _Tp, _Compare, _Allocator>& __y) {
1612
  return !(__y < __x);
1613
}
1614

1615
#else // #if _LIBCPP_STD_VER <= 17
1616

1617
template <class _Key, class _Tp, class _Compare, class _Allocator>
1618
_LIBCPP_HIDE_FROM_ABI __synth_three_way_result<pair<const _Key, _Tp>>
1619
operator<=>(const map<_Key, _Tp, _Compare, _Allocator>& __x, const map<_Key, _Tp, _Compare, _Allocator>& __y) {
1620
  return std::lexicographical_compare_three_way(__x.begin(), __x.end(), __y.begin(), __y.end(), std::__synth_three_way);
1621
}
1622

1623
#endif // #if _LIBCPP_STD_VER <= 17
1624

1625
template <class _Key, class _Tp, class _Compare, class _Allocator>
1626
inline _LIBCPP_HIDE_FROM_ABI void
1627
swap(map<_Key, _Tp, _Compare, _Allocator>& __x, map<_Key, _Tp, _Compare, _Allocator>& __y)
1628
    _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) {
1629
  __x.swap(__y);
1630
}
1631

1632
#if _LIBCPP_STD_VER >= 20
1633
template <class _Key, class _Tp, class _Compare, class _Allocator, class _Predicate>
1634
inline _LIBCPP_HIDE_FROM_ABI typename map<_Key, _Tp, _Compare, _Allocator>::size_type
1635
erase_if(map<_Key, _Tp, _Compare, _Allocator>& __c, _Predicate __pred) {
1636
  return std::__libcpp_erase_if_container(__c, __pred);
1637
}
1638
#endif
1639

1640
template <class _Key, class _Tp, class _Compare = less<_Key>, class _Allocator = allocator<pair<const _Key, _Tp> > >
1641
class _LIBCPP_TEMPLATE_VIS multimap {
1642
public:
1643
  // types:
1644
  typedef _Key key_type;
1645
  typedef _Tp mapped_type;
1646
  typedef pair<const key_type, mapped_type> value_type;
1647
  typedef __type_identity_t<_Compare> key_compare;
1648
  typedef __type_identity_t<_Allocator> allocator_type;
1649
  typedef value_type& reference;
1650
  typedef const value_type& const_reference;
1651

1652
  static_assert(__check_valid_allocator<allocator_type>::value, "");
1653
  static_assert(is_same<typename allocator_type::value_type, value_type>::value,
1654
                "Allocator::value_type must be same type as value_type");
1655

1656
  class _LIBCPP_TEMPLATE_VIS value_compare : public __binary_function<value_type, value_type, bool> {
1657
    friend class multimap;
1658

1659
  protected:
1660
    key_compare comp;
1661

1662
    _LIBCPP_HIDE_FROM_ABI value_compare(key_compare __c) : comp(__c) {}
1663

1664
  public:
1665
    _LIBCPP_HIDE_FROM_ABI bool operator()(const value_type& __x, const value_type& __y) const {
1666
      return comp(__x.first, __y.first);
1667
    }
1668
  };
1669

1670
private:
1671
  typedef std::__value_type<key_type, mapped_type> __value_type;
1672
  typedef __map_value_compare<key_type, __value_type, key_compare> __vc;
1673
  typedef __rebind_alloc<allocator_traits<allocator_type>, __value_type> __allocator_type;
1674
  typedef __tree<__value_type, __vc, __allocator_type> __base;
1675
  typedef typename __base::__node_traits __node_traits;
1676
  typedef allocator_traits<allocator_type> __alloc_traits;
1677

1678
  __base __tree_;
1679

1680
public:
1681
  typedef typename __alloc_traits::pointer pointer;
1682
  typedef typename __alloc_traits::const_pointer const_pointer;
1683
  typedef typename __alloc_traits::size_type size_type;
1684
  typedef typename __alloc_traits::difference_type difference_type;
1685
  typedef __map_iterator<typename __base::iterator> iterator;
1686
  typedef __map_const_iterator<typename __base::const_iterator> const_iterator;
1687
  typedef std::reverse_iterator<iterator> reverse_iterator;
1688
  typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
1689

1690
#if _LIBCPP_STD_VER >= 17
1691
  typedef __map_node_handle<typename __base::__node, allocator_type> node_type;
1692
#endif
1693

1694
  template <class _Key2, class _Value2, class _Comp2, class _Alloc2>
1695
  friend class _LIBCPP_TEMPLATE_VIS map;
1696
  template <class _Key2, class _Value2, class _Comp2, class _Alloc2>
1697
  friend class _LIBCPP_TEMPLATE_VIS multimap;
1698

1699
  _LIBCPP_HIDE_FROM_ABI multimap() _NOEXCEPT_(
1700
      is_nothrow_default_constructible<allocator_type>::value&& is_nothrow_default_constructible<key_compare>::value&&
1701
          is_nothrow_copy_constructible<key_compare>::value)
1702
      : __tree_(__vc(key_compare())) {}
1703

1704
  _LIBCPP_HIDE_FROM_ABI explicit multimap(const key_compare& __comp) _NOEXCEPT_(
1705
      is_nothrow_default_constructible<allocator_type>::value&& is_nothrow_copy_constructible<key_compare>::value)
1706
      : __tree_(__vc(__comp)) {}
1707

1708
  _LIBCPP_HIDE_FROM_ABI explicit multimap(const key_compare& __comp, const allocator_type& __a)
1709
      : __tree_(__vc(__comp), typename __base::allocator_type(__a)) {}
1710

1711
  template <class _InputIterator>
1712
  _LIBCPP_HIDE_FROM_ABI multimap(_InputIterator __f, _InputIterator __l, const key_compare& __comp = key_compare())
1713
      : __tree_(__vc(__comp)) {
1714
    insert(__f, __l);
1715
  }
1716

1717
  template <class _InputIterator>
1718
  _LIBCPP_HIDE_FROM_ABI
1719
  multimap(_InputIterator __f, _InputIterator __l, const key_compare& __comp, const allocator_type& __a)
1720
      : __tree_(__vc(__comp), typename __base::allocator_type(__a)) {
1721
    insert(__f, __l);
1722
  }
1723

1724
#if _LIBCPP_STD_VER >= 23
1725
  template <_ContainerCompatibleRange<value_type> _Range>
1726
  _LIBCPP_HIDE_FROM_ABI
1727
  multimap(from_range_t,
1728
           _Range&& __range,
1729
           const key_compare& __comp = key_compare(),
1730
           const allocator_type& __a = allocator_type())
1731
      : __tree_(__vc(__comp), typename __base::allocator_type(__a)) {
1732
    insert_range(std::forward<_Range>(__range));
1733
  }
1734
#endif
1735

1736
#if _LIBCPP_STD_VER >= 14
1737
  template <class _InputIterator>
1738
  _LIBCPP_HIDE_FROM_ABI multimap(_InputIterator __f, _InputIterator __l, const allocator_type& __a)
1739
      : multimap(__f, __l, key_compare(), __a) {}
1740
#endif
1741

1742
#if _LIBCPP_STD_VER >= 23
1743
  template <_ContainerCompatibleRange<value_type> _Range>
1744
  _LIBCPP_HIDE_FROM_ABI multimap(from_range_t, _Range&& __range, const allocator_type& __a)
1745
      : multimap(from_range, std::forward<_Range>(__range), key_compare(), __a) {}
1746
#endif
1747

1748
  _LIBCPP_HIDE_FROM_ABI multimap(const multimap& __m)
1749
      : __tree_(__m.__tree_.value_comp(),
1750
                __alloc_traits::select_on_container_copy_construction(__m.__tree_.__alloc())) {
1751
    insert(__m.begin(), __m.end());
1752
  }
1753

1754
  _LIBCPP_HIDE_FROM_ABI multimap& operator=(const multimap& __m) {
1755
#ifndef _LIBCPP_CXX03_LANG
1756
    __tree_ = __m.__tree_;
1757
#else
1758
    if (this != std::addressof(__m)) {
1759
      __tree_.clear();
1760
      __tree_.value_comp() = __m.__tree_.value_comp();
1761
      __tree_.__copy_assign_alloc(__m.__tree_);
1762
      insert(__m.begin(), __m.end());
1763
    }
1764
#endif
1765
    return *this;
1766
  }
1767

1768
#ifndef _LIBCPP_CXX03_LANG
1769

1770
  _LIBCPP_HIDE_FROM_ABI multimap(multimap&& __m) noexcept(is_nothrow_move_constructible<__base>::value)
1771
      : __tree_(std::move(__m.__tree_)) {}
1772

1773
  _LIBCPP_HIDE_FROM_ABI multimap(multimap&& __m, const allocator_type& __a);
1774

1775
  _LIBCPP_HIDE_FROM_ABI multimap& operator=(multimap&& __m) noexcept(is_nothrow_move_assignable<__base>::value) {
1776
    __tree_ = std::move(__m.__tree_);
1777
    return *this;
1778
  }
1779

1780
  _LIBCPP_HIDE_FROM_ABI multimap(initializer_list<value_type> __il, const key_compare& __comp = key_compare())
1781
      : __tree_(__vc(__comp)) {
1782
    insert(__il.begin(), __il.end());
1783
  }
1784

1785
  _LIBCPP_HIDE_FROM_ABI
1786
  multimap(initializer_list<value_type> __il, const key_compare& __comp, const allocator_type& __a)
1787
      : __tree_(__vc(__comp), typename __base::allocator_type(__a)) {
1788
    insert(__il.begin(), __il.end());
1789
  }
1790

1791
#  if _LIBCPP_STD_VER >= 14
1792
  _LIBCPP_HIDE_FROM_ABI multimap(initializer_list<value_type> __il, const allocator_type& __a)
1793
      : multimap(__il, key_compare(), __a) {}
1794
#  endif
1795

1796
  _LIBCPP_HIDE_FROM_ABI multimap& operator=(initializer_list<value_type> __il) {
1797
    __tree_.__assign_multi(__il.begin(), __il.end());
1798
    return *this;
1799
  }
1800

1801
#endif // _LIBCPP_CXX03_LANG
1802

1803
  _LIBCPP_HIDE_FROM_ABI explicit multimap(const allocator_type& __a) : __tree_(typename __base::allocator_type(__a)) {}
1804

1805
  _LIBCPP_HIDE_FROM_ABI multimap(const multimap& __m, const allocator_type& __a)
1806
      : __tree_(__m.__tree_.value_comp(), typename __base::allocator_type(__a)) {
1807
    insert(__m.begin(), __m.end());
1808
  }
1809

1810
  _LIBCPP_HIDE_FROM_ABI ~multimap() { static_assert(sizeof(__diagnose_non_const_comparator<_Key, _Compare>()), ""); }
1811

1812
  _LIBCPP_HIDE_FROM_ABI iterator begin() _NOEXCEPT { return __tree_.begin(); }
1813
  _LIBCPP_HIDE_FROM_ABI const_iterator begin() const _NOEXCEPT { return __tree_.begin(); }
1814
  _LIBCPP_HIDE_FROM_ABI iterator end() _NOEXCEPT { return __tree_.end(); }
1815
  _LIBCPP_HIDE_FROM_ABI const_iterator end() const _NOEXCEPT { return __tree_.end(); }
1816

1817
  _LIBCPP_HIDE_FROM_ABI reverse_iterator rbegin() _NOEXCEPT { return reverse_iterator(end()); }
1818
  _LIBCPP_HIDE_FROM_ABI const_reverse_iterator rbegin() const _NOEXCEPT { return const_reverse_iterator(end()); }
1819
  _LIBCPP_HIDE_FROM_ABI reverse_iterator rend() _NOEXCEPT { return reverse_iterator(begin()); }
1820
  _LIBCPP_HIDE_FROM_ABI const_reverse_iterator rend() const _NOEXCEPT { return const_reverse_iterator(begin()); }
1821

1822
  _LIBCPP_HIDE_FROM_ABI const_iterator cbegin() const _NOEXCEPT { return begin(); }
1823
  _LIBCPP_HIDE_FROM_ABI const_iterator cend() const _NOEXCEPT { return end(); }
1824
  _LIBCPP_HIDE_FROM_ABI const_reverse_iterator crbegin() const _NOEXCEPT { return rbegin(); }
1825
  _LIBCPP_HIDE_FROM_ABI const_reverse_iterator crend() const _NOEXCEPT { return rend(); }
1826

1827
  _LIBCPP_NODISCARD _LIBCPP_HIDE_FROM_ABI bool empty() const _NOEXCEPT { return __tree_.size() == 0; }
1828
  _LIBCPP_HIDE_FROM_ABI size_type size() const _NOEXCEPT { return __tree_.size(); }
1829
  _LIBCPP_HIDE_FROM_ABI size_type max_size() const _NOEXCEPT { return __tree_.max_size(); }
1830

1831
  _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const _NOEXCEPT { return allocator_type(__tree_.__alloc()); }
1832
  _LIBCPP_HIDE_FROM_ABI key_compare key_comp() const { return __tree_.value_comp().key_comp(); }
1833
  _LIBCPP_HIDE_FROM_ABI value_compare value_comp() const { return value_compare(__tree_.value_comp().key_comp()); }
1834

1835
#ifndef _LIBCPP_CXX03_LANG
1836

1837
  template <class... _Args>
1838
  _LIBCPP_HIDE_FROM_ABI iterator emplace(_Args&&... __args) {
1839
    return __tree_.__emplace_multi(std::forward<_Args>(__args)...);
1840
  }
1841

1842
  template <class... _Args>
1843
  _LIBCPP_HIDE_FROM_ABI iterator emplace_hint(const_iterator __p, _Args&&... __args) {
1844
    return __tree_.__emplace_hint_multi(__p.__i_, std::forward<_Args>(__args)...);
1845
  }
1846

1847
  template <class _Pp, __enable_if_t<is_constructible<value_type, _Pp>::value, int> = 0>
1848
  _LIBCPP_HIDE_FROM_ABI iterator insert(_Pp&& __p) {
1849
    return __tree_.__insert_multi(std::forward<_Pp>(__p));
1850
  }
1851

1852
  template <class _Pp, __enable_if_t<is_constructible<value_type, _Pp>::value, int> = 0>
1853
  _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __pos, _Pp&& __p) {
1854
    return __tree_.__insert_multi(__pos.__i_, std::forward<_Pp>(__p));
1855
  }
1856

1857
  _LIBCPP_HIDE_FROM_ABI iterator insert(value_type&& __v) { return __tree_.__insert_multi(std::move(__v)); }
1858

1859
  _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, value_type&& __v) {
1860
    return __tree_.__insert_multi(__p.__i_, std::move(__v));
1861
  }
1862

1863
  _LIBCPP_HIDE_FROM_ABI void insert(initializer_list<value_type> __il) { insert(__il.begin(), __il.end()); }
1864

1865
#endif // _LIBCPP_CXX03_LANG
1866

1867
  _LIBCPP_HIDE_FROM_ABI iterator insert(const value_type& __v) { return __tree_.__insert_multi(__v); }
1868

1869
  _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, const value_type& __v) {
1870
    return __tree_.__insert_multi(__p.__i_, __v);
1871
  }
1872

1873
  template <class _InputIterator>
1874
  _LIBCPP_HIDE_FROM_ABI void insert(_InputIterator __f, _InputIterator __l) {
1875
    for (const_iterator __e = cend(); __f != __l; ++__f)
1876
      __tree_.__insert_multi(__e.__i_, *__f);
1877
  }
1878

1879
#if _LIBCPP_STD_VER >= 23
1880
  template <_ContainerCompatibleRange<value_type> _Range>
1881
  _LIBCPP_HIDE_FROM_ABI void insert_range(_Range&& __range) {
1882
    const_iterator __end = cend();
1883
    for (auto&& __element : __range) {
1884
      __tree_.__insert_multi(__end.__i_, std::forward<decltype(__element)>(__element));
1885
    }
1886
  }
1887
#endif
1888

1889
  _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __p) { return __tree_.erase(__p.__i_); }
1890
  _LIBCPP_HIDE_FROM_ABI iterator erase(iterator __p) { return __tree_.erase(__p.__i_); }
1891
  _LIBCPP_HIDE_FROM_ABI size_type erase(const key_type& __k) { return __tree_.__erase_multi(__k); }
1892
  _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __f, const_iterator __l) {
1893
    return __tree_.erase(__f.__i_, __l.__i_);
1894
  }
1895

1896
#if _LIBCPP_STD_VER >= 17
1897
  _LIBCPP_HIDE_FROM_ABI iterator insert(node_type&& __nh) {
1898
    _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(),
1899
                                        "node_type with incompatible allocator passed to multimap::insert()");
1900
    return __tree_.template __node_handle_insert_multi<node_type>(std::move(__nh));
1901
  }
1902
  _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __hint, node_type&& __nh) {
1903
    _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(),
1904
                                        "node_type with incompatible allocator passed to multimap::insert()");
1905
    return __tree_.template __node_handle_insert_multi<node_type>(__hint.__i_, std::move(__nh));
1906
  }
1907
  _LIBCPP_HIDE_FROM_ABI node_type extract(key_type const& __key) {
1908
    return __tree_.template __node_handle_extract<node_type>(__key);
1909
  }
1910
  _LIBCPP_HIDE_FROM_ABI node_type extract(const_iterator __it) {
1911
    return __tree_.template __node_handle_extract<node_type>(__it.__i_);
1912
  }
1913
  template <class _Compare2>
1914
  _LIBCPP_HIDE_FROM_ABI void merge(multimap<key_type, mapped_type, _Compare2, allocator_type>& __source) {
1915
    _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
1916
        __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
1917
    return __tree_.__node_handle_merge_multi(__source.__tree_);
1918
  }
1919
  template <class _Compare2>
1920
  _LIBCPP_HIDE_FROM_ABI void merge(multimap<key_type, mapped_type, _Compare2, allocator_type>&& __source) {
1921
    _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
1922
        __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
1923
    return __tree_.__node_handle_merge_multi(__source.__tree_);
1924
  }
1925
  template <class _Compare2>
1926
  _LIBCPP_HIDE_FROM_ABI void merge(map<key_type, mapped_type, _Compare2, allocator_type>& __source) {
1927
    _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
1928
        __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
1929
    return __tree_.__node_handle_merge_multi(__source.__tree_);
1930
  }
1931
  template <class _Compare2>
1932
  _LIBCPP_HIDE_FROM_ABI void merge(map<key_type, mapped_type, _Compare2, allocator_type>&& __source) {
1933
    _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
1934
        __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
1935
    return __tree_.__node_handle_merge_multi(__source.__tree_);
1936
  }
1937
#endif
1938

1939
  _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT { __tree_.clear(); }
1940

1941
  _LIBCPP_HIDE_FROM_ABI void swap(multimap& __m) _NOEXCEPT_(__is_nothrow_swappable_v<__base>) {
1942
    __tree_.swap(__m.__tree_);
1943
  }
1944

1945
  _LIBCPP_HIDE_FROM_ABI iterator find(const key_type& __k) { return __tree_.find(__k); }
1946
  _LIBCPP_HIDE_FROM_ABI const_iterator find(const key_type& __k) const { return __tree_.find(__k); }
1947
#if _LIBCPP_STD_VER >= 14
1948
  template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
1949
  _LIBCPP_HIDE_FROM_ABI iterator find(const _K2& __k) {
1950
    return __tree_.find(__k);
1951
  }
1952
  template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
1953
  _LIBCPP_HIDE_FROM_ABI const_iterator find(const _K2& __k) const {
1954
    return __tree_.find(__k);
1955
  }
1956
#endif
1957

1958
  _LIBCPP_HIDE_FROM_ABI size_type count(const key_type& __k) const { return __tree_.__count_multi(__k); }
1959
#if _LIBCPP_STD_VER >= 14
1960
  template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
1961
  _LIBCPP_HIDE_FROM_ABI size_type count(const _K2& __k) const {
1962
    return __tree_.__count_multi(__k);
1963
  }
1964
#endif
1965

1966
#if _LIBCPP_STD_VER >= 20
1967
  _LIBCPP_HIDE_FROM_ABI bool contains(const key_type& __k) const { return find(__k) != end(); }
1968
  template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
1969
  _LIBCPP_HIDE_FROM_ABI bool contains(const _K2& __k) const {
1970
    return find(__k) != end();
1971
  }
1972
#endif // _LIBCPP_STD_VER >= 20
1973

1974
  _LIBCPP_HIDE_FROM_ABI iterator lower_bound(const key_type& __k) { return __tree_.lower_bound(__k); }
1975
  _LIBCPP_HIDE_FROM_ABI const_iterator lower_bound(const key_type& __k) const { return __tree_.lower_bound(__k); }
1976
#if _LIBCPP_STD_VER >= 14
1977
  template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
1978
  _LIBCPP_HIDE_FROM_ABI iterator lower_bound(const _K2& __k) {
1979
    return __tree_.lower_bound(__k);
1980
  }
1981

1982
  template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
1983
  _LIBCPP_HIDE_FROM_ABI const_iterator lower_bound(const _K2& __k) const {
1984
    return __tree_.lower_bound(__k);
1985
  }
1986
#endif
1987

1988
  _LIBCPP_HIDE_FROM_ABI iterator upper_bound(const key_type& __k) { return __tree_.upper_bound(__k); }
1989
  _LIBCPP_HIDE_FROM_ABI const_iterator upper_bound(const key_type& __k) const { return __tree_.upper_bound(__k); }
1990
#if _LIBCPP_STD_VER >= 14
1991
  template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
1992
  _LIBCPP_HIDE_FROM_ABI iterator upper_bound(const _K2& __k) {
1993
    return __tree_.upper_bound(__k);
1994
  }
1995
  template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
1996
  _LIBCPP_HIDE_FROM_ABI const_iterator upper_bound(const _K2& __k) const {
1997
    return __tree_.upper_bound(__k);
1998
  }
1999
#endif
2000

2001
  _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const key_type& __k) {
2002
    return __tree_.__equal_range_multi(__k);
2003
  }
2004
  _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const key_type& __k) const {
2005
    return __tree_.__equal_range_multi(__k);
2006
  }
2007
#if _LIBCPP_STD_VER >= 14
2008
  template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
2009
  _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const _K2& __k) {
2010
    return __tree_.__equal_range_multi(__k);
2011
  }
2012
  template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
2013
  _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const _K2& __k) const {
2014
    return __tree_.__equal_range_multi(__k);
2015
  }
2016
#endif
2017

2018
private:
2019
  typedef typename __base::__node __node;
2020
  typedef typename __base::__node_allocator __node_allocator;
2021
  typedef typename __base::__node_pointer __node_pointer;
2022

2023
  typedef __map_node_destructor<__node_allocator> _Dp;
2024
  typedef unique_ptr<__node, _Dp> __node_holder;
2025
};
2026

2027
#if _LIBCPP_STD_VER >= 17
2028
template <class _InputIterator,
2029
          class _Compare   = less<__iter_key_type<_InputIterator>>,
2030
          class _Allocator = allocator<__iter_to_alloc_type<_InputIterator>>,
2031
          class            = enable_if_t<__has_input_iterator_category<_InputIterator>::value, void>,
2032
          class            = enable_if_t<!__is_allocator<_Compare>::value, void>,
2033
          class            = enable_if_t<__is_allocator<_Allocator>::value, void>>
2034
multimap(_InputIterator, _InputIterator, _Compare = _Compare(), _Allocator = _Allocator())
2035
    -> multimap<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>, _Compare, _Allocator>;
2036

2037
#  if _LIBCPP_STD_VER >= 23
2038
template <ranges::input_range _Range,
2039
          class _Compare   = less<__range_key_type<_Range>>,
2040
          class _Allocator = allocator<__range_to_alloc_type<_Range>>,
2041
          class            = enable_if_t<!__is_allocator<_Compare>::value, void>,
2042
          class            = enable_if_t<__is_allocator<_Allocator>::value, void>>
2043
multimap(from_range_t, _Range&&, _Compare = _Compare(), _Allocator = _Allocator())
2044
    -> multimap<__range_key_type<_Range>, __range_mapped_type<_Range>, _Compare, _Allocator>;
2045
#  endif
2046

2047
template <class _Key,
2048
          class _Tp,
2049
          class _Compare   = less<remove_const_t<_Key>>,
2050
          class _Allocator = allocator<pair<const _Key, _Tp>>,
2051
          class            = enable_if_t<!__is_allocator<_Compare>::value, void>,
2052
          class            = enable_if_t<__is_allocator<_Allocator>::value, void>>
2053
multimap(initializer_list<pair<_Key, _Tp>>,
2054
         _Compare   = _Compare(),
2055
         _Allocator = _Allocator()) -> multimap<remove_const_t<_Key>, _Tp, _Compare, _Allocator>;
2056

2057
template <class _InputIterator,
2058
          class _Allocator,
2059
          class = enable_if_t<__has_input_iterator_category<_InputIterator>::value, void>,
2060
          class = enable_if_t<__is_allocator<_Allocator>::value, void>>
2061
multimap(_InputIterator, _InputIterator, _Allocator)
2062
    -> multimap<__iter_key_type<_InputIterator>,
2063
                __iter_mapped_type<_InputIterator>,
2064
                less<__iter_key_type<_InputIterator>>,
2065
                _Allocator>;
2066

2067
#  if _LIBCPP_STD_VER >= 23
2068
template <ranges::input_range _Range, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value, void>>
2069
multimap(from_range_t, _Range&&, _Allocator)
2070
    -> multimap<__range_key_type<_Range>, __range_mapped_type<_Range>, less<__range_key_type<_Range>>, _Allocator>;
2071
#  endif
2072

2073
template <class _Key, class _Tp, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value, void>>
2074
multimap(initializer_list<pair<_Key, _Tp>>,
2075
         _Allocator) -> multimap<remove_const_t<_Key>, _Tp, less<remove_const_t<_Key>>, _Allocator>;
2076
#endif
2077

2078
#ifndef _LIBCPP_CXX03_LANG
2079
template <class _Key, class _Tp, class _Compare, class _Allocator>
2080
multimap<_Key, _Tp, _Compare, _Allocator>::multimap(multimap&& __m, const allocator_type& __a)
2081
    : __tree_(std::move(__m.__tree_), typename __base::allocator_type(__a)) {
2082
  if (__a != __m.get_allocator()) {
2083
    const_iterator __e = cend();
2084
    while (!__m.empty())
2085
      __tree_.__insert_multi(__e.__i_, std::move(__m.__tree_.remove(__m.begin().__i_)->__value_.__move()));
2086
  }
2087
}
2088
#endif
2089

2090
template <class _Key, class _Tp, class _Compare, class _Allocator>
2091
inline _LIBCPP_HIDE_FROM_ABI bool
2092
operator==(const multimap<_Key, _Tp, _Compare, _Allocator>& __x, const multimap<_Key, _Tp, _Compare, _Allocator>& __y) {
2093
  return __x.size() == __y.size() && std::equal(__x.begin(), __x.end(), __y.begin());
2094
}
2095

2096
#if _LIBCPP_STD_VER <= 17
2097

2098
template <class _Key, class _Tp, class _Compare, class _Allocator>
2099
inline _LIBCPP_HIDE_FROM_ABI bool
2100
operator<(const multimap<_Key, _Tp, _Compare, _Allocator>& __x, const multimap<_Key, _Tp, _Compare, _Allocator>& __y) {
2101
  return std::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
2102
}
2103

2104
template <class _Key, class _Tp, class _Compare, class _Allocator>
2105
inline _LIBCPP_HIDE_FROM_ABI bool
2106
operator!=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x, const multimap<_Key, _Tp, _Compare, _Allocator>& __y) {
2107
  return !(__x == __y);
2108
}
2109

2110
template <class _Key, class _Tp, class _Compare, class _Allocator>
2111
inline _LIBCPP_HIDE_FROM_ABI bool
2112
operator>(const multimap<_Key, _Tp, _Compare, _Allocator>& __x, const multimap<_Key, _Tp, _Compare, _Allocator>& __y) {
2113
  return __y < __x;
2114
}
2115

2116
template <class _Key, class _Tp, class _Compare, class _Allocator>
2117
inline _LIBCPP_HIDE_FROM_ABI bool
2118
operator>=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x, const multimap<_Key, _Tp, _Compare, _Allocator>& __y) {
2119
  return !(__x < __y);
2120
}
2121

2122
template <class _Key, class _Tp, class _Compare, class _Allocator>
2123
inline _LIBCPP_HIDE_FROM_ABI bool
2124
operator<=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x, const multimap<_Key, _Tp, _Compare, _Allocator>& __y) {
2125
  return !(__y < __x);
2126
}
2127

2128
#else // #if _LIBCPP_STD_VER <= 17
2129

2130
template <class _Key, class _Tp, class _Compare, class _Allocator>
2131
_LIBCPP_HIDE_FROM_ABI __synth_three_way_result<pair<const _Key, _Tp>>
2132
operator<=>(const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
2133
            const multimap<_Key, _Tp, _Compare, _Allocator>& __y) {
2134
  return std::lexicographical_compare_three_way(__x.begin(), __x.end(), __y.begin(), __y.end(), __synth_three_way);
2135
}
2136

2137
#endif // #if _LIBCPP_STD_VER <= 17
2138

2139
template <class _Key, class _Tp, class _Compare, class _Allocator>
2140
inline _LIBCPP_HIDE_FROM_ABI void
2141
swap(multimap<_Key, _Tp, _Compare, _Allocator>& __x, multimap<_Key, _Tp, _Compare, _Allocator>& __y)
2142
    _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) {
2143
  __x.swap(__y);
2144
}
2145

2146
#if _LIBCPP_STD_VER >= 20
2147
template <class _Key, class _Tp, class _Compare, class _Allocator, class _Predicate>
2148
inline _LIBCPP_HIDE_FROM_ABI typename multimap<_Key, _Tp, _Compare, _Allocator>::size_type
2149
erase_if(multimap<_Key, _Tp, _Compare, _Allocator>& __c, _Predicate __pred) {
2150
  return std::__libcpp_erase_if_container(__c, __pred);
2151
}
2152
#endif
2153

2154
_LIBCPP_END_NAMESPACE_STD
2155

2156
#if _LIBCPP_STD_VER >= 17
2157
_LIBCPP_BEGIN_NAMESPACE_STD
2158
namespace pmr {
2159
template <class _KeyT, class _ValueT, class _CompareT = std::less<_KeyT>>
2160
using map _LIBCPP_AVAILABILITY_PMR =
2161
    std::map<_KeyT, _ValueT, _CompareT, polymorphic_allocator<std::pair<const _KeyT, _ValueT>>>;
2162

2163
template <class _KeyT, class _ValueT, class _CompareT = std::less<_KeyT>>
2164
using multimap _LIBCPP_AVAILABILITY_PMR =
2165
    std::multimap<_KeyT, _ValueT, _CompareT, polymorphic_allocator<std::pair<const _KeyT, _ValueT>>>;
2166
} // namespace pmr
2167
_LIBCPP_END_NAMESPACE_STD
2168
#endif
2169

2170
_LIBCPP_POP_MACROS
2171

2172
#if !defined(_LIBCPP_REMOVE_TRANSITIVE_INCLUDES) && _LIBCPP_STD_VER <= 20
2173
#  include <concepts>
2174
#  include <cstdlib>
2175
#  include <functional>
2176
#  include <iterator>
2177
#  include <type_traits>
2178
#  include <utility>
2179
#endif
2180

2181
#endif // _LIBCPP_MAP
2182