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