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