1// -*- C++ -*-
2//===----------------------------------------------------------------------===//
3//
4// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
5// See https://llvm.org/LICENSE.txt for license information.
6// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7//
8//===----------------------------------------------------------------------===//
9
10#ifndef _LIBCPP_MAP
11#define _LIBCPP_MAP
12
13/*
14
15 map synopsis
16
17namespace std
18{
19
20template <class Key, class T, class Compare = less<Key>,
21 class Allocator = allocator<pair<const Key, T>>>
22class map
23{
24public:
25 // types:
26 typedef Key key_type;
27 typedef T mapped_type;
28 typedef pair<const key_type, mapped_type> value_type;
29 typedef Compare key_compare;
30 typedef Allocator allocator_type;
31 typedef typename allocator_type::reference reference;
32 typedef typename allocator_type::const_reference const_reference;
33 typedef typename allocator_type::pointer pointer;
34 typedef typename allocator_type::const_pointer const_pointer;
35 typedef typename allocator_type::size_type size_type;
36 typedef typename allocator_type::difference_type difference_type;
37
38 typedef implementation-defined iterator;
39 typedef implementation-defined const_iterator;
40 typedef std::reverse_iterator<iterator> reverse_iterator;
41 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
42 typedef unspecified node_type; // C++17
43 typedef INSERT_RETURN_TYPE<iterator, node_type> insert_return_type; // C++17
44
45 class value_compare
46 {
47 friend class map;
48 protected:
49 key_compare comp;
50
51 value_compare(key_compare c);
52 public:
53 typedef bool result_type; // deprecated in C++17, removed in C++20
54 typedef value_type first_argument_type; // deprecated in C++17, removed in C++20
55 typedef value_type second_argument_type; // deprecated in C++17, removed in C++20
56 bool operator()(const value_type& x, const value_type& y) const;
57 };
58
59 // construct/copy/destroy:
60 map()
61 noexcept(
62 is_nothrow_default_constructible<allocator_type>::value &&
63 is_nothrow_default_constructible<key_compare>::value &&
64 is_nothrow_copy_constructible<key_compare>::value);
65 explicit map(const key_compare& comp);
66 map(const key_compare& comp, const allocator_type& a);
67 template <class InputIterator>
68 map(InputIterator first, InputIterator last,
69 const key_compare& comp = key_compare());
70 template <class InputIterator>
71 map(InputIterator first, InputIterator last,
72 const key_compare& comp, const allocator_type& a);
73 template<container-compatible-range<value_type> R>
74 map(from_range_t, R&& rg, const Compare& comp = Compare(), const Allocator& = Allocator()); // C++23
75 map(const map& m);
76 map(map&& m)
77 noexcept(
78 is_nothrow_move_constructible<allocator_type>::value &&
79 is_nothrow_move_constructible<key_compare>::value);
80 explicit map(const allocator_type& a);
81 map(const map& m, const allocator_type& a);
82 map(map&& m, const allocator_type& a);
83 map(initializer_list<value_type> il, const key_compare& comp = key_compare());
84 map(initializer_list<value_type> il, const key_compare& comp, const allocator_type& a);
85 template <class InputIterator>
86 map(InputIterator first, InputIterator last, const allocator_type& a)
87 : map(first, last, Compare(), a) {} // C++14
88 template<container-compatible-range<value_type> R>
89 map(from_range_t, R&& rg, const Allocator& a))
90 : map(from_range, std::forward<R>(rg), Compare(), a) { } // C++23
91 map(initializer_list<value_type> il, const allocator_type& a)
92 : map(il, Compare(), a) {} // C++14
93 ~map();
94
95 map& operator=(const map& m);
96 map& operator=(map&& m)
97 noexcept(
98 allocator_type::propagate_on_container_move_assignment::value &&
99 is_nothrow_move_assignable<allocator_type>::value &&
100 is_nothrow_move_assignable<key_compare>::value);
101 map& operator=(initializer_list<value_type> il);
102
103 // iterators:
104 iterator begin() noexcept;
105 const_iterator begin() const noexcept;
106 iterator end() noexcept;
107 const_iterator end() const noexcept;
108
109 reverse_iterator rbegin() noexcept;
110 const_reverse_iterator rbegin() const noexcept;
111 reverse_iterator rend() noexcept;
112 const_reverse_iterator rend() const noexcept;
113
114 const_iterator cbegin() const noexcept;
115 const_iterator cend() const noexcept;
116 const_reverse_iterator crbegin() const noexcept;
117 const_reverse_iterator crend() const noexcept;
118
119 // capacity:
120 bool empty() const noexcept;
121 size_type size() const noexcept;
122 size_type max_size() const noexcept;
123
124 // element access:
125 mapped_type& operator[](const key_type& k);
126 mapped_type& operator[](key_type&& k);
127
128 mapped_type& at(const key_type& k);
129 const mapped_type& at(const key_type& k) const;
130
131 // modifiers:
132 template <class... Args>
133 pair<iterator, bool> emplace(Args&&... args);
134 template <class... Args>
135 iterator emplace_hint(const_iterator position, Args&&... args);
136 pair<iterator, bool> insert(const value_type& v);
137 pair<iterator, bool> insert( value_type&& v); // C++17
138 template <class P>
139 pair<iterator, bool> insert(P&& p);
140 iterator insert(const_iterator position, const value_type& v);
141 iterator insert(const_iterator position, value_type&& v); // C++17
142 template <class P>
143 iterator insert(const_iterator position, P&& p);
144 template <class InputIterator>
145 void insert(InputIterator first, InputIterator last);
146 template<container-compatible-range<value_type> R>
147 void insert_range(R&& rg); // C++23
148 void insert(initializer_list<value_type> il);
149
150 node_type extract(const_iterator position); // C++17
151 node_type extract(const key_type& x); // C++17
152 insert_return_type insert(node_type&& nh); // C++17
153 iterator insert(const_iterator hint, node_type&& nh); // C++17
154
155 template <class... Args>
156 pair<iterator, bool> try_emplace(const key_type& k, Args&&... args); // C++17
157 template <class... Args>
158 pair<iterator, bool> try_emplace(key_type&& k, Args&&... args); // C++17
159 template <class... Args>
160 iterator try_emplace(const_iterator hint, const key_type& k, Args&&... args); // C++17
161 template <class... Args>
162 iterator try_emplace(const_iterator hint, key_type&& k, Args&&... args); // C++17
163 template <class M>
164 pair<iterator, bool> insert_or_assign(const key_type& k, M&& obj); // C++17
165 template <class M>
166 pair<iterator, bool> insert_or_assign(key_type&& k, M&& obj); // C++17
167 template <class M>
168 iterator insert_or_assign(const_iterator hint, const key_type& k, M&& obj); // C++17
169 template <class M>
170 iterator insert_or_assign(const_iterator hint, key_type&& k, M&& obj); // C++17
171
172 iterator erase(const_iterator position);
173 iterator erase(iterator position); // C++14
174 size_type erase(const key_type& k);
175 iterator erase(const_iterator first, const_iterator last);
176 void clear() noexcept;
177
178 template<class C2>
179 void merge(map<Key, T, C2, Allocator>& source); // C++17
180 template<class C2>
181 void merge(map<Key, T, C2, Allocator>&& source); // C++17
182 template<class C2>
183 void merge(multimap<Key, T, C2, Allocator>& source); // C++17
184 template<class C2>
185 void merge(multimap<Key, T, C2, Allocator>&& source); // C++17
186
187 void swap(map& m)
188 noexcept(allocator_traits<allocator_type>::is_always_equal::value &&
189 is_nothrow_swappable<key_compare>::value); // C++17
190
191 // observers:
192 allocator_type get_allocator() const noexcept;
193 key_compare key_comp() const;
194 value_compare value_comp() const;
195
196 // map operations:
197 iterator find(const key_type& k);
198 const_iterator find(const key_type& k) const;
199 template<typename K>
200 iterator find(const K& x); // C++14
201 template<typename K>
202 const_iterator find(const K& x) const; // C++14
203
204 template<typename K>
205 size_type count(const K& x) const; // C++14
206 size_type count(const key_type& k) const;
207
208 bool contains(const key_type& x) const; // C++20
209 template<class K> bool contains(const K& x) const; // C++20
210
211 iterator lower_bound(const key_type& k);
212 const_iterator lower_bound(const key_type& k) const;
213 template<typename K>
214 iterator lower_bound(const K& x); // C++14
215 template<typename K>
216 const_iterator lower_bound(const K& x) const; // C++14
217
218 iterator upper_bound(const key_type& k);
219 const_iterator upper_bound(const key_type& k) const;
220 template<typename K>
221 iterator upper_bound(const K& x); // C++14
222 template<typename K>
223 const_iterator upper_bound(const K& x) const; // C++14
224
225 pair<iterator,iterator> equal_range(const key_type& k);
226 pair<const_iterator,const_iterator> equal_range(const key_type& k) const;
227 template<typename K>
228 pair<iterator,iterator> equal_range(const K& x); // C++14
229 template<typename K>
230 pair<const_iterator,const_iterator> equal_range(const K& x) const; // C++14
231};
232
233template <class InputIterator,
234 class Compare = less<iter_key_t<InputIterator>>,
235 class Allocator = allocator<iter_to_alloc_t<InputIterator>>>
236map(InputIterator, InputIterator, Compare = Compare(), Allocator = Allocator())
237 -> map<iter_key_t<InputIterator>, iter_val_t<InputIterator>, Compare, Allocator>; // C++17
238
239template<ranges::input_range R, class Compare = less<range-key-type<R>,
240 class Allocator = allocator<range-to-alloc-type<R>>>
241 map(from_range_t, R&&, Compare = Compare(), Allocator = Allocator())
242 -> map<range-key-type<R>, range-mapped-type<R>, Compare, Allocator>; // C++23
243
244template<class Key, class T, class Compare = less<Key>,
245 class Allocator = allocator<pair<const Key, T>>>
246map(initializer_list<pair<const Key, T>>, Compare = Compare(), Allocator = Allocator())
247 -> map<Key, T, Compare, Allocator>; // C++17
248
249template <class InputIterator, class Allocator>
250map(InputIterator, InputIterator, Allocator)
251 -> map<iter_key_t<InputIterator>, iter_val_t<InputIterator>, less<iter_key_t<InputIterator>>,
252 Allocator>; // C++17
253
254template<ranges::input_range R, class Allocator>
255 map(from_range_t, R&&, Allocator)
256 -> map<range-key-type<R>, range-mapped-type<R>, less<range-key-type<R>>, Allocator>; // C++23
257
258template<class Key, class T, class Allocator>
259map(initializer_list<pair<const Key, T>>, Allocator) -> map<Key, T, less<Key>, Allocator>; // C++17
260
261template <class Key, class T, class Compare, class Allocator>
262bool
263operator==(const map<Key, T, Compare, Allocator>& x,
264 const map<Key, T, Compare, Allocator>& y);
265
266template <class Key, class T, class Compare, class Allocator>
267bool
268operator< (const map<Key, T, Compare, Allocator>& x,
269 const map<Key, T, Compare, Allocator>& y); // removed in C++20
270
271template <class Key, class T, class Compare, class Allocator>
272bool
273operator!=(const map<Key, T, Compare, Allocator>& x,
274 const map<Key, T, Compare, Allocator>& y); // removed in C++20
275
276template <class Key, class T, class Compare, class Allocator>
277bool
278operator> (const map<Key, T, Compare, Allocator>& x,
279 const map<Key, T, Compare, Allocator>& y); // removed in C++20
280
281template <class Key, class T, class Compare, class Allocator>
282bool
283operator>=(const map<Key, T, Compare, Allocator>& x,
284 const map<Key, T, Compare, Allocator>& y); // removed in C++20
285
286template <class Key, class T, class Compare, class Allocator>
287bool
288operator<=(const map<Key, T, Compare, Allocator>& x,
289 const map<Key, T, Compare, Allocator>& y); // removed in C++20
290
291template<class Key, class T, class Compare, class Allocator>
292 synth-three-way-result<pair<const Key, T>>
293 operator<=>(const map<Key, T, Compare, Allocator>& x,
294 const map<Key, T, Compare, Allocator>& y); // since C++20
295
296// specialized algorithms:
297template <class Key, class T, class Compare, class Allocator>
298void
299swap(map<Key, T, Compare, Allocator>& x, map<Key, T, Compare, Allocator>& y)
300 noexcept(noexcept(x.swap(y)));
301
302template <class Key, class T, class Compare, class Allocator, class Predicate>
303typename map<Key, T, Compare, Allocator>::size_type
304erase_if(map<Key, T, Compare, Allocator>& c, Predicate pred); // C++20
305
306
307template <class Key, class T, class Compare = less<Key>,
308 class Allocator = allocator<pair<const Key, T>>>
309class multimap
310{
311public:
312 // types:
313 typedef Key key_type;
314 typedef T mapped_type;
315 typedef pair<const key_type,mapped_type> value_type;
316 typedef Compare key_compare;
317 typedef Allocator allocator_type;
318 typedef typename allocator_type::reference reference;
319 typedef typename allocator_type::const_reference const_reference;
320 typedef typename allocator_type::size_type size_type;
321 typedef typename allocator_type::difference_type difference_type;
322 typedef typename allocator_type::pointer pointer;
323 typedef typename allocator_type::const_pointer const_pointer;
324
325 typedef implementation-defined iterator;
326 typedef implementation-defined const_iterator;
327 typedef std::reverse_iterator<iterator> reverse_iterator;
328 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
329 typedef unspecified node_type; // C++17
330
331 class value_compare
332 {
333 friend class multimap;
334 protected:
335 key_compare comp;
336 value_compare(key_compare c);
337 public:
338 typedef bool result_type; // deprecated in C++17, removed in C++20
339 typedef value_type first_argument_type; // deprecated in C++17, removed in C++20
340 typedef value_type second_argument_type; // deprecated in C++17, removed in C++20
341 bool operator()(const value_type& x, const value_type& y) const;
342 };
343
344 // construct/copy/destroy:
345 multimap()
346 noexcept(
347 is_nothrow_default_constructible<allocator_type>::value &&
348 is_nothrow_default_constructible<key_compare>::value &&
349 is_nothrow_copy_constructible<key_compare>::value);
350 explicit multimap(const key_compare& comp);
351 multimap(const key_compare& comp, const allocator_type& a);
352 template <class InputIterator>
353 multimap(InputIterator first, InputIterator last, const key_compare& comp);
354 template <class InputIterator>
355 multimap(InputIterator first, InputIterator last, const key_compare& comp,
356 const allocator_type& a);
357 template<container-compatible-range<value_type> R>
358 multimap(from_range_t, R&& rg,
359 const Compare& comp = Compare(), const Allocator& = Allocator()); // C++23
360 multimap(const multimap& m);
361 multimap(multimap&& m)
362 noexcept(
363 is_nothrow_move_constructible<allocator_type>::value &&
364 is_nothrow_move_constructible<key_compare>::value);
365 explicit multimap(const allocator_type& a);
366 multimap(const multimap& m, const allocator_type& a);
367 multimap(multimap&& m, const allocator_type& a);
368 multimap(initializer_list<value_type> il, const key_compare& comp = key_compare());
369 multimap(initializer_list<value_type> il, const key_compare& comp,
370 const allocator_type& a);
371 template <class InputIterator>
372 multimap(InputIterator first, InputIterator last, const allocator_type& a)
373 : multimap(first, last, Compare(), a) {} // C++14
374 template<container-compatible-range<value_type> R>
375 multimap(from_range_t, R&& rg, const Allocator& a))
376 : multimap(from_range, std::forward<R>(rg), Compare(), a) { } // C++23
377 multimap(initializer_list<value_type> il, const allocator_type& a)
378 : multimap(il, Compare(), a) {} // C++14
379 ~multimap();
380
381 multimap& operator=(const multimap& m);
382 multimap& operator=(multimap&& m)
383 noexcept(
384 allocator_type::propagate_on_container_move_assignment::value &&
385 is_nothrow_move_assignable<allocator_type>::value &&
386 is_nothrow_move_assignable<key_compare>::value);
387 multimap& operator=(initializer_list<value_type> il);
388
389 // iterators:
390 iterator begin() noexcept;
391 const_iterator begin() const noexcept;
392 iterator end() noexcept;
393 const_iterator end() const noexcept;
394
395 reverse_iterator rbegin() noexcept;
396 const_reverse_iterator rbegin() const noexcept;
397 reverse_iterator rend() noexcept;
398 const_reverse_iterator rend() const noexcept;
399
400 const_iterator cbegin() const noexcept;
401 const_iterator cend() const noexcept;
402 const_reverse_iterator crbegin() const noexcept;
403 const_reverse_iterator crend() const noexcept;
404
405 // capacity:
406 bool empty() const noexcept;
407 size_type size() const noexcept;
408 size_type max_size() const noexcept;
409
410 // modifiers:
411 template <class... Args>
412 iterator emplace(Args&&... args);
413 template <class... Args>
414 iterator emplace_hint(const_iterator position, Args&&... args);
415 iterator insert(const value_type& v);
416 iterator insert( value_type&& v); // C++17
417 template <class P>
418 iterator insert(P&& p);
419 iterator insert(const_iterator position, const value_type& v);
420 iterator insert(const_iterator position, value_type&& v); // C++17
421 template <class P>
422 iterator insert(const_iterator position, P&& p);
423 template <class InputIterator>
424 void insert(InputIterator first, InputIterator last);
425 template<container-compatible-range<value_type> R>
426 void insert_range(R&& rg); // C++23
427 void insert(initializer_list<value_type> il);
428
429 node_type extract(const_iterator position); // C++17
430 node_type extract(const key_type& x); // C++17
431 iterator insert(node_type&& nh); // C++17
432 iterator insert(const_iterator hint, node_type&& nh); // C++17
433
434 iterator erase(const_iterator position);
435 iterator erase(iterator position); // C++14
436 size_type erase(const key_type& k);
437 iterator erase(const_iterator first, const_iterator last);
438 void clear() noexcept;
439
440 template<class C2>
441 void merge(multimap<Key, T, C2, Allocator>& source); // C++17
442 template<class C2>
443 void merge(multimap<Key, T, C2, Allocator>&& source); // C++17
444 template<class C2>
445 void merge(map<Key, T, C2, Allocator>& source); // C++17
446 template<class C2>
447 void merge(map<Key, T, C2, Allocator>&& source); // C++17
448
449 void swap(multimap& m)
450 noexcept(allocator_traits<allocator_type>::is_always_equal::value &&
451 is_nothrow_swappable<key_compare>::value); // C++17
452
453 // observers:
454 allocator_type get_allocator() const noexcept;
455 key_compare key_comp() const;
456 value_compare value_comp() const;
457
458 // map operations:
459 iterator find(const key_type& k);
460 const_iterator find(const key_type& k) const;
461 template<typename K>
462 iterator find(const K& x); // C++14
463 template<typename K>
464 const_iterator find(const K& x) const; // C++14
465
466 template<typename K>
467 size_type count(const K& x) const; // C++14
468 size_type count(const key_type& k) const;
469
470 bool contains(const key_type& x) const; // C++20
471 template<class K> bool contains(const K& x) const; // C++20
472
473 iterator lower_bound(const key_type& k);
474 const_iterator lower_bound(const key_type& k) const;
475 template<typename K>
476 iterator lower_bound(const K& x); // C++14
477 template<typename K>
478 const_iterator lower_bound(const K& x) const; // C++14
479
480 iterator upper_bound(const key_type& k);
481 const_iterator upper_bound(const key_type& k) const;
482 template<typename K>
483 iterator upper_bound(const K& x); // C++14
484 template<typename K>
485 const_iterator upper_bound(const K& x) const; // C++14
486
487 pair<iterator,iterator> equal_range(const key_type& k);
488 pair<const_iterator,const_iterator> equal_range(const key_type& k) const;
489 template<typename K>
490 pair<iterator,iterator> equal_range(const K& x); // C++14
491 template<typename K>
492 pair<const_iterator,const_iterator> equal_range(const K& x) const; // C++14
493};
494
495template <class InputIterator,
496 class Compare = less<iter_key_t<InputIterator>>,
497 class Allocator = allocator<iter_to_alloc_t<InputIterator>>>
498multimap(InputIterator, InputIterator, Compare = Compare(), Allocator = Allocator())
499 -> multimap<iter_key_t<InputIterator>, iter_val_t<InputIterator>, Compare, Allocator>; // C++17
500
501template<ranges::input_range R, class Compare = less<range-key-type<R>>,
502 class Allocator = allocator<range-to-alloc-type<R>>>
503 multimap(from_range_t, R&&, Compare = Compare(), Allocator = Allocator())
504 -> multimap<range-key-type<R>, range-mapped-type<R>, Compare, Allocator>; // C++23
505
506template<class Key, class T, class Compare = less<Key>,
507 class Allocator = allocator<pair<const Key, T>>>
508multimap(initializer_list<pair<const Key, T>>, Compare = Compare(), Allocator = Allocator())
509 -> multimap<Key, T, Compare, Allocator>; // C++17
510
511template <class InputIterator, class Allocator>
512multimap(InputIterator, InputIterator, Allocator)
513 -> multimap<iter_key_t<InputIterator>, iter_val_t<InputIterator>,
514 less<iter_key_t<InputIterator>>, Allocator>; // C++17
515
516template<ranges::input_range R, class Allocator>
517 multimap(from_range_t, R&&, Allocator)
518 -> multimap<range-key-type<R>, range-mapped-type<R>, less<range-key-type<R>>, Allocator>; // C++23
519
520template<class Key, class T, class Allocator>
521multimap(initializer_list<pair<const Key, T>>, Allocator)
522 -> multimap<Key, T, less<Key>, Allocator>; // C++17
523
524template <class Key, class T, class Compare, class Allocator>
525bool
526operator==(const multimap<Key, T, Compare, Allocator>& x,
527 const multimap<Key, T, Compare, Allocator>& y);
528
529template <class Key, class T, class Compare, class Allocator>
530bool
531operator< (const multimap<Key, T, Compare, Allocator>& x,
532 const multimap<Key, T, Compare, Allocator>& y); // removed in C++20
533
534template <class Key, class T, class Compare, class Allocator>
535bool
536operator!=(const multimap<Key, T, Compare, Allocator>& x,
537 const multimap<Key, T, Compare, Allocator>& y); // removed in C++20
538
539template <class Key, class T, class Compare, class Allocator>
540bool
541operator> (const multimap<Key, T, Compare, Allocator>& x,
542 const multimap<Key, T, Compare, Allocator>& y); // removed in C++20
543
544template <class Key, class T, class Compare, class Allocator>
545bool
546operator>=(const multimap<Key, T, Compare, Allocator>& x,
547 const multimap<Key, T, Compare, Allocator>& y); // removed in C++20
548
549template <class Key, class T, class Compare, class Allocator>
550bool
551operator<=(const multimap<Key, T, Compare, Allocator>& x,
552 const multimap<Key, T, Compare, Allocator>& y); // removed in C++20
553
554template<class Key, class T, class Compare, class Allocator>
555 synth-three-way-result<pair<const Key, T>>
556 operator<=>(const multimap<Key, T, Compare, Allocator>& x,
557 const multimap<Key, T, Compare, Allocator>& y); // since c++20
558
559// specialized algorithms:
560template <class Key, class T, class Compare, class Allocator>
561void
562swap(multimap<Key, T, Compare, Allocator>& x,
563 multimap<Key, T, Compare, Allocator>& y)
564 noexcept(noexcept(x.swap(y)));
565
566template <class Key, class T, class Compare, class Allocator, class Predicate>
567typename multimap<Key, T, Compare, Allocator>::size_type
568erase_if(multimap<Key, T, Compare, Allocator>& c, Predicate pred); // C++20
569
570} // std
571
572*/
573
574#include <__algorithm/equal.h>
575#include <__algorithm/lexicographical_compare.h>
576#include <__algorithm/lexicographical_compare_three_way.h>
577#include <__assert>
578#include <__config>
579#include <__functional/binary_function.h>
580#include <__functional/is_transparent.h>
581#include <__functional/operations.h>
582#include <__iterator/erase_if_container.h>
583#include <__iterator/iterator_traits.h>
584#include <__iterator/ranges_iterator_traits.h>
585#include <__iterator/reverse_iterator.h>
586#include <__memory/addressof.h>
587#include <__memory/allocator.h>
588#include <__memory_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
624template <class _Key,
625 class _CP,
626 class _Compare,
627 bool = is_empty<_Compare>::value && !__libcpp_is_final<_Compare>::value>
628class __map_value_compare : private _Compare {
629public:
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
662template <class _Key, class _CP, class _Compare>
663class __map_value_compare<_Key, _CP, _Compare, false> {
664 _Compare __comp_;
665
666public:
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
700template <class _Key, class _CP, class _Compare, bool __b>
701inline _LIBCPP_HIDE_FROM_ABI void
702swap(__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
707template <class _Allocator>
708class __map_node_destructor {
709 typedef _Allocator allocator_type;
710 typedef allocator_traits<allocator_type> __alloc_traits;
711
712public:
713 typedef typename __alloc_traits::pointer pointer;
714
715private:
716 allocator_type& __na_;
717
718public:
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
748template <class _Key, class _Tp, class _Compare, class _Allocator>
749class map;
750template <class _Key, class _Tp, class _Compare, class _Allocator>
751class multimap;
752template <class _TreeIterator>
753class __map_const_iterator;
754
755#ifndef _LIBCPP_CXX03_LANG
756
757template <class _Key, class _Tp>
758struct _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
765private:
766 value_type __cc_;
767
768public:
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
819template <class _Key, class _Tp>
820struct __value_type {
821 typedef _Key key_type;
822 typedef _Tp mapped_type;
823 typedef pair<const key_type, mapped_type> value_type;
824
825private:
826 value_type __cc_;
827
828public:
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
840template <class _Tp>
841struct __extract_key_value_types;
842
843template <class _Key, class _Tp>
844struct __extract_key_value_types<__value_type<_Key, _Tp> > {
845 typedef _Key const __key_type;
846 typedef _Tp __mapped_type;
847};
848
849template <class _TreeIterator>
850class _LIBCPP_TEMPLATE_VIS __map_iterator {
851 typedef typename _TreeIterator::_NodeTypes _NodeTypes;
852 typedef typename _TreeIterator::__pointer_traits __pointer_traits;
853
854 _TreeIterator __i_;
855
856public:
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
905template <class _TreeIterator>
906class _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
912public:
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
963template <class _Key, class _Tp, class _Compare = less<_Key>, class _Allocator = allocator<pair<const _Key, _Tp> > >
964class _LIBCPP_TEMPLATE_VIS map {
965public:
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
992private:
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
1004public:
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
1433private:
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
1449template <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>>
1455map(_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
1459template <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>>
1464map(from_range_t, _Range&&, _Compare = _Compare(), _Allocator = _Allocator())
1465 -> map<__range_key_type<_Range>, __range_mapped_type<_Range>, _Compare, _Allocator>;
1466# endif
1467
1468template <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>>
1474map(initializer_list<pair<_Key, _Tp>>,
1475 _Compare = _Compare(),
1476 _Allocator = _Allocator()) -> map<remove_const_t<_Key>, _Tp, _Compare, _Allocator>;
1477
1478template <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>>
1482map(_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
1489template <ranges::input_range _Range, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value, void>>
1490map(from_range_t, _Range&&, _Allocator)
1491 -> map<__range_key_type<_Range>, __range_mapped_type<_Range>, less<__range_key_type<_Range>>, _Allocator>;
1492# endif
1493
1494template <class _Key, class _Tp, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value, void>>
1495map(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
1500template <class _Key, class _Tp, class _Compare, class _Allocator>
1501map<_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
1510template <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
1518template <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
1532template <class _Key, class _Tp, class _Compare, class _Allocator>
1533typename map<_Key, _Tp, _Compare, _Allocator>::__node_holder
1534map<_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
1544template <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
1559template <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
1568template <class _Key, class _Tp, class _Compare, class _Allocator>
1569const _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
1577template <class _Key, class _Tp, class _Compare, class _Allocator>
1578inline _LIBCPP_HIDE_FROM_ABI bool
1579operator==(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
1585template <class _Key, class _Tp, class _Compare, class _Allocator>
1586inline _LIBCPP_HIDE_FROM_ABI bool
1587operator<(const map<_Key, _Tp, _Compare, _Allocator>& __x, const map<_Key, _Tp, _Compare, _Allocator>& __y) {
1588 return std::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
1589}
1590
1591template <class _Key, class _Tp, class _Compare, class _Allocator>
1592inline _LIBCPP_HIDE_FROM_ABI bool
1593operator!=(const map<_Key, _Tp, _Compare, _Allocator>& __x, const map<_Key, _Tp, _Compare, _Allocator>& __y) {
1594 return !(__x == __y);
1595}
1596
1597template <class _Key, class _Tp, class _Compare, class _Allocator>
1598inline _LIBCPP_HIDE_FROM_ABI bool
1599operator>(const map<_Key, _Tp, _Compare, _Allocator>& __x, const map<_Key, _Tp, _Compare, _Allocator>& __y) {
1600 return __y < __x;
1601}
1602
1603template <class _Key, class _Tp, class _Compare, class _Allocator>
1604inline _LIBCPP_HIDE_FROM_ABI bool
1605operator>=(const map<_Key, _Tp, _Compare, _Allocator>& __x, const map<_Key, _Tp, _Compare, _Allocator>& __y) {
1606 return !(__x < __y);
1607}
1608
1609template <class _Key, class _Tp, class _Compare, class _Allocator>
1610inline _LIBCPP_HIDE_FROM_ABI bool
1611operator<=(const map<_Key, _Tp, _Compare, _Allocator>& __x, const map<_Key, _Tp, _Compare, _Allocator>& __y) {
1612 return !(__y < __x);
1613}
1614
1615#else // #if _LIBCPP_STD_VER <= 17
1616
1617template <class _Key, class _Tp, class _Compare, class _Allocator>
1618_LIBCPP_HIDE_FROM_ABI __synth_three_way_result<pair<const _Key, _Tp>>
1619operator<=>(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
1625template <class _Key, class _Tp, class _Compare, class _Allocator>
1626inline _LIBCPP_HIDE_FROM_ABI void
1627swap(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
1633template <class _Key, class _Tp, class _Compare, class _Allocator, class _Predicate>
1634inline _LIBCPP_HIDE_FROM_ABI typename map<_Key, _Tp, _Compare, _Allocator>::size_type
1635erase_if(map<_Key, _Tp, _Compare, _Allocator>& __c, _Predicate __pred) {
1636 return std::__libcpp_erase_if_container(__c, __pred);
1637}
1638#endif
1639
1640template <class _Key, class _Tp, class _Compare = less<_Key>, class _Allocator = allocator<pair<const _Key, _Tp> > >
1641class _LIBCPP_TEMPLATE_VIS multimap {
1642public:
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
1670private:
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
1680public:
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
2018private:
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
2028template <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>>
2034multimap(_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
2038template <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>>
2043multimap(from_range_t, _Range&&, _Compare = _Compare(), _Allocator = _Allocator())
2044 -> multimap<__range_key_type<_Range>, __range_mapped_type<_Range>, _Compare, _Allocator>;
2045# endif
2046
2047template <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>>
2053multimap(initializer_list<pair<_Key, _Tp>>,
2054 _Compare = _Compare(),
2055 _Allocator = _Allocator()) -> multimap<remove_const_t<_Key>, _Tp, _Compare, _Allocator>;
2056
2057template <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>>
2061multimap(_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
2068template <ranges::input_range _Range, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value, void>>
2069multimap(from_range_t, _Range&&, _Allocator)
2070 -> multimap<__range_key_type<_Range>, __range_mapped_type<_Range>, less<__range_key_type<_Range>>, _Allocator>;
2071# endif
2072
2073template <class _Key, class _Tp, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value, void>>
2074multimap(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
2079template <class _Key, class _Tp, class _Compare, class _Allocator>
2080multimap<_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
2090template <class _Key, class _Tp, class _Compare, class _Allocator>
2091inline _LIBCPP_HIDE_FROM_ABI bool
2092operator==(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
2098template <class _Key, class _Tp, class _Compare, class _Allocator>
2099inline _LIBCPP_HIDE_FROM_ABI bool
2100operator<(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
2104template <class _Key, class _Tp, class _Compare, class _Allocator>
2105inline _LIBCPP_HIDE_FROM_ABI bool
2106operator!=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x, const multimap<_Key, _Tp, _Compare, _Allocator>& __y) {
2107 return !(__x == __y);
2108}
2109
2110template <class _Key, class _Tp, class _Compare, class _Allocator>
2111inline _LIBCPP_HIDE_FROM_ABI bool
2112operator>(const multimap<_Key, _Tp, _Compare, _Allocator>& __x, const multimap<_Key, _Tp, _Compare, _Allocator>& __y) {
2113 return __y < __x;
2114}
2115
2116template <class _Key, class _Tp, class _Compare, class _Allocator>
2117inline _LIBCPP_HIDE_FROM_ABI bool
2118operator>=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x, const multimap<_Key, _Tp, _Compare, _Allocator>& __y) {
2119 return !(__x < __y);
2120}
2121
2122template <class _Key, class _Tp, class _Compare, class _Allocator>
2123inline _LIBCPP_HIDE_FROM_ABI bool
2124operator<=(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
2130template <class _Key, class _Tp, class _Compare, class _Allocator>
2131_LIBCPP_HIDE_FROM_ABI __synth_three_way_result<pair<const _Key, _Tp>>
2132operator<=>(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
2139template <class _Key, class _Tp, class _Compare, class _Allocator>
2140inline _LIBCPP_HIDE_FROM_ABI void
2141swap(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
2147template <class _Key, class _Tp, class _Compare, class _Allocator, class _Predicate>
2148inline _LIBCPP_HIDE_FROM_ABI typename multimap<_Key, _Tp, _Compare, _Allocator>::size_type
2149erase_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
2158namespace pmr {
2159template <class _KeyT, class _ValueT, class _CompareT = std::less<_KeyT>>
2160using map _LIBCPP_AVAILABILITY_PMR =
2161 std::map<_KeyT, _ValueT, _CompareT, polymorphic_allocator<std::pair<const _KeyT, _ValueT>>>;
2162
2163template <class _KeyT, class _ValueT, class _CompareT = std::less<_KeyT>>
2164using 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