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.__get_value().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.__get_value().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) {
976# ifndef _LIBCPP_CXX03_LANG
977 __tree_ = __m.__tree_;
978# else
979 if (this != std::addressof(__m)) {
980 __tree_.clear();
981 __tree_.value_comp() = __m.__tree_.value_comp();
982 __tree_.__copy_assign_alloc(__m.__tree_);
983 insert(__m.begin(), __m.end());
984 }
985# endif
986 return *this;
987 }
988
989# ifndef _LIBCPP_CXX03_LANG
990
991 _LIBCPP_HIDE_FROM_ABI map(map&& __m) noexcept(is_nothrow_move_constructible<__base>::value)
992 : __tree_(std::move(__m.__tree_)) {}
993
994 _LIBCPP_HIDE_FROM_ABI map(map&& __m, const allocator_type& __a);
995
996 _LIBCPP_HIDE_FROM_ABI map& operator=(map&& __m) noexcept(is_nothrow_move_assignable<__base>::value) {
997 __tree_ = std::move(__m.__tree_);
998 return *this;
999 }
1000
1001 _LIBCPP_HIDE_FROM_ABI map(initializer_list<value_type> __il, const key_compare& __comp = key_compare())
1002 : __tree_(__vc(__comp)) {
1003 insert(__il.begin(), __il.end());
1004 }
1005
1006 _LIBCPP_HIDE_FROM_ABI map(initializer_list<value_type> __il, const key_compare& __comp, const allocator_type& __a)
1007 : __tree_(__vc(__comp), typename __base::allocator_type(__a)) {
1008 insert(__il.begin(), __il.end());
1009 }
1010
1011# if _LIBCPP_STD_VER >= 14
1012 _LIBCPP_HIDE_FROM_ABI map(initializer_list<value_type> __il, const allocator_type& __a)
1013 : map(__il, key_compare(), __a) {}
1014# endif
1015
1016 _LIBCPP_HIDE_FROM_ABI map& operator=(initializer_list<value_type> __il) {
1017 __tree_.__assign_unique(__il.begin(), __il.end());
1018 return *this;
1019 }
1020
1021# endif // _LIBCPP_CXX03_LANG
1022
1023 _LIBCPP_HIDE_FROM_ABI explicit map(const allocator_type& __a) : __tree_(typename __base::allocator_type(__a)) {}
1024
1025 _LIBCPP_HIDE_FROM_ABI map(const map& __m, const allocator_type& __a)
1026 : __tree_(__m.__tree_.value_comp(), typename __base::allocator_type(__a)) {
1027 insert(__m.begin(), __m.end());
1028 }
1029
1030 _LIBCPP_HIDE_FROM_ABI ~map() { static_assert(sizeof(std::__diagnose_non_const_comparator<_Key, _Compare>()), ""); }
1031
1032 _LIBCPP_HIDE_FROM_ABI iterator begin() _NOEXCEPT { return __tree_.begin(); }
1033 _LIBCPP_HIDE_FROM_ABI const_iterator begin() const _NOEXCEPT { return __tree_.begin(); }
1034 _LIBCPP_HIDE_FROM_ABI iterator end() _NOEXCEPT { return __tree_.end(); }
1035 _LIBCPP_HIDE_FROM_ABI const_iterator end() const _NOEXCEPT { return __tree_.end(); }
1036
1037 _LIBCPP_HIDE_FROM_ABI reverse_iterator rbegin() _NOEXCEPT { return reverse_iterator(end()); }
1038 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator rbegin() const _NOEXCEPT { return const_reverse_iterator(end()); }
1039 _LIBCPP_HIDE_FROM_ABI reverse_iterator rend() _NOEXCEPT { return reverse_iterator(begin()); }
1040 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator rend() const _NOEXCEPT { return const_reverse_iterator(begin()); }
1041
1042 _LIBCPP_HIDE_FROM_ABI const_iterator cbegin() const _NOEXCEPT { return begin(); }
1043 _LIBCPP_HIDE_FROM_ABI const_iterator cend() const _NOEXCEPT { return end(); }
1044 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator crbegin() const _NOEXCEPT { return rbegin(); }
1045 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator crend() const _NOEXCEPT { return rend(); }
1046
1047 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI bool empty() const _NOEXCEPT { return __tree_.size() == 0; }
1048 _LIBCPP_HIDE_FROM_ABI size_type size() const _NOEXCEPT { return __tree_.size(); }
1049 _LIBCPP_HIDE_FROM_ABI size_type max_size() const _NOEXCEPT { return __tree_.max_size(); }
1050
1051 _LIBCPP_HIDE_FROM_ABI mapped_type& operator[](const key_type& __k);
1052# ifndef _LIBCPP_CXX03_LANG
1053 _LIBCPP_HIDE_FROM_ABI mapped_type& operator[](key_type&& __k);
1054# endif
1055
1056 _LIBCPP_HIDE_FROM_ABI mapped_type& at(const key_type& __k);
1057 _LIBCPP_HIDE_FROM_ABI const mapped_type& at(const key_type& __k) const;
1058
1059 _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const _NOEXCEPT { return allocator_type(__tree_.__alloc()); }
1060 _LIBCPP_HIDE_FROM_ABI key_compare key_comp() const { return __tree_.value_comp().key_comp(); }
1061 _LIBCPP_HIDE_FROM_ABI value_compare value_comp() const { return value_compare(__tree_.value_comp().key_comp()); }
1062
1063# ifndef _LIBCPP_CXX03_LANG
1064 template <class... _Args>
1065 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> emplace(_Args&&... __args) {
1066 return __tree_.__emplace_unique(std::forward<_Args>(__args)...);
1067 }
1068
1069 template <class... _Args>
1070 _LIBCPP_HIDE_FROM_ABI iterator emplace_hint(const_iterator __p, _Args&&... __args) {
1071 return __tree_.__emplace_hint_unique(__p.__i_, std::forward<_Args>(__args)...);
1072 }
1073
1074 template <class _Pp, __enable_if_t<is_constructible<value_type, _Pp>::value, int> = 0>
1075 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert(_Pp&& __p) {
1076 return __tree_.__insert_unique(std::forward<_Pp>(__p));
1077 }
1078
1079 template <class _Pp, __enable_if_t<is_constructible<value_type, _Pp>::value, int> = 0>
1080 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __pos, _Pp&& __p) {
1081 return __tree_.__insert_unique(__pos.__i_, std::forward<_Pp>(__p));
1082 }
1083
1084# endif // _LIBCPP_CXX03_LANG
1085
1086 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert(const value_type& __v) { return __tree_.__insert_unique(__v); }
1087
1088 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, const value_type& __v) {
1089 return __tree_.__insert_unique(__p.__i_, __v);
1090 }
1091
1092# ifndef _LIBCPP_CXX03_LANG
1093 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert(value_type&& __v) {
1094 return __tree_.__insert_unique(std::move(__v));
1095 }
1096
1097 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, value_type&& __v) {
1098 return __tree_.__insert_unique(__p.__i_, std::move(__v));
1099 }
1100
1101 _LIBCPP_HIDE_FROM_ABI void insert(initializer_list<value_type> __il) { insert(__il.begin(), __il.end()); }
1102# endif
1103
1104 template <class _InputIterator>
1105 _LIBCPP_HIDE_FROM_ABI void insert(_InputIterator __f, _InputIterator __l) {
1106 for (const_iterator __e = cend(); __f != __l; ++__f)
1107 insert(__e.__i_, *__f);
1108 }
1109
1110# if _LIBCPP_STD_VER >= 23
1111 template <_ContainerCompatibleRange<value_type> _Range>
1112 _LIBCPP_HIDE_FROM_ABI void insert_range(_Range&& __range) {
1113 const_iterator __end = cend();
1114 for (auto&& __element : __range) {
1115 insert(__end.__i_, std::forward<decltype(__element)>(__element));
1116 }
1117 }
1118# endif
1119
1120# if _LIBCPP_STD_VER >= 17
1121
1122 template <class... _Args>
1123 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> try_emplace(const key_type& __k, _Args&&... __args) {
1124 return __tree_.__emplace_unique_key_args(
1125 __k,
1126 std::piecewise_construct,
1127 std::forward_as_tuple(__k),
1128 std::forward_as_tuple(std::forward<_Args>(__args)...));
1129 }
1130
1131 template <class... _Args>
1132 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> try_emplace(key_type&& __k, _Args&&... __args) {
1133 return __tree_.__emplace_unique_key_args(
1134 __k,
1135 std::piecewise_construct,
1136 std::forward_as_tuple(std::move(__k)),
1137 std::forward_as_tuple(std::forward<_Args>(__args)...));
1138 }
1139
1140 template <class... _Args>
1141 _LIBCPP_HIDE_FROM_ABI iterator try_emplace(const_iterator __h, const key_type& __k, _Args&&... __args) {
1142 return __tree_
1143 .__emplace_hint_unique_key_args(
1144 __h.__i_,
1145 __k,
1146 std::piecewise_construct,
1147 std::forward_as_tuple(__k),
1148 std::forward_as_tuple(std::forward<_Args>(__args)...))
1149 .first;
1150 }
1151
1152 template <class... _Args>
1153 _LIBCPP_HIDE_FROM_ABI iterator try_emplace(const_iterator __h, key_type&& __k, _Args&&... __args) {
1154 return __tree_
1155 .__emplace_hint_unique_key_args(
1156 __h.__i_,
1157 __k,
1158 std::piecewise_construct,
1159 std::forward_as_tuple(std::move(__k)),
1160 std::forward_as_tuple(std::forward<_Args>(__args)...))
1161 .first;
1162 }
1163
1164 template <class _Vp>
1165 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert_or_assign(const key_type& __k, _Vp&& __v) {
1166 iterator __p = lower_bound(__k);
1167 if (__p != end() && !key_comp()(__k, __p->first)) {
1168 __p->second = std::forward<_Vp>(__v);
1169 return std::make_pair(__p, false);
1170 }
1171 return std::make_pair(emplace_hint(__p, __k, std::forward<_Vp>(__v)), true);
1172 }
1173
1174 template <class _Vp>
1175 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert_or_assign(key_type&& __k, _Vp&& __v) {
1176 iterator __p = lower_bound(__k);
1177 if (__p != end() && !key_comp()(__k, __p->first)) {
1178 __p->second = std::forward<_Vp>(__v);
1179 return std::make_pair(__p, false);
1180 }
1181 return std::make_pair(emplace_hint(__p, std::move(__k), std::forward<_Vp>(__v)), true);
1182 }
1183
1184 template <class _Vp>
1185 _LIBCPP_HIDE_FROM_ABI iterator insert_or_assign(const_iterator __h, const key_type& __k, _Vp&& __v) {
1186 auto [__r, __inserted] = __tree_.__emplace_hint_unique_key_args(__h.__i_, __k, __k, std::forward<_Vp>(__v));
1187
1188 if (!__inserted)
1189 __r->second = std::forward<_Vp>(__v);
1190
1191 return __r;
1192 }
1193
1194 template <class _Vp>
1195 _LIBCPP_HIDE_FROM_ABI iterator insert_or_assign(const_iterator __h, key_type&& __k, _Vp&& __v) {
1196 auto [__r, __inserted] =
1197 __tree_.__emplace_hint_unique_key_args(__h.__i_, __k, std::move(__k), std::forward<_Vp>(__v));
1198
1199 if (!__inserted)
1200 __r->second = std::forward<_Vp>(__v);
1201
1202 return __r;
1203 }
1204
1205# endif // _LIBCPP_STD_VER >= 17
1206
1207 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __p) { return __tree_.erase(__p.__i_); }
1208 _LIBCPP_HIDE_FROM_ABI iterator erase(iterator __p) { return __tree_.erase(__p.__i_); }
1209 _LIBCPP_HIDE_FROM_ABI size_type erase(const key_type& __k) { return __tree_.__erase_unique(__k); }
1210 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __f, const_iterator __l) {
1211 return __tree_.erase(__f.__i_, __l.__i_);
1212 }
1213 _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT { __tree_.clear(); }
1214
1215# if _LIBCPP_STD_VER >= 17
1216 _LIBCPP_HIDE_FROM_ABI insert_return_type insert(node_type&& __nh) {
1217 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(),
1218 "node_type with incompatible allocator passed to map::insert()");
1219 return __tree_.template __node_handle_insert_unique< node_type, insert_return_type>(std::move(__nh));
1220 }
1221 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __hint, node_type&& __nh) {
1222 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(),
1223 "node_type with incompatible allocator passed to map::insert()");
1224 return __tree_.template __node_handle_insert_unique<node_type>(__hint.__i_, std::move(__nh));
1225 }
1226 _LIBCPP_HIDE_FROM_ABI node_type extract(key_type const& __key) {
1227 return __tree_.template __node_handle_extract<node_type>(__key);
1228 }
1229 _LIBCPP_HIDE_FROM_ABI node_type extract(const_iterator __it) {
1230 return __tree_.template __node_handle_extract<node_type>(__it.__i_);
1231 }
1232 template <class _Compare2>
1233 _LIBCPP_HIDE_FROM_ABI void merge(map<key_type, mapped_type, _Compare2, allocator_type>& __source) {
1234 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
1235 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
1236 __tree_.__node_handle_merge_unique(__source.__tree_);
1237 }
1238 template <class _Compare2>
1239 _LIBCPP_HIDE_FROM_ABI void merge(map<key_type, mapped_type, _Compare2, allocator_type>&& __source) {
1240 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
1241 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
1242 __tree_.__node_handle_merge_unique(__source.__tree_);
1243 }
1244 template <class _Compare2>
1245 _LIBCPP_HIDE_FROM_ABI void merge(multimap<key_type, mapped_type, _Compare2, allocator_type>& __source) {
1246 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
1247 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
1248 __tree_.__node_handle_merge_unique(__source.__tree_);
1249 }
1250 template <class _Compare2>
1251 _LIBCPP_HIDE_FROM_ABI void merge(multimap<key_type, mapped_type, _Compare2, allocator_type>&& __source) {
1252 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
1253 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
1254 __tree_.__node_handle_merge_unique(__source.__tree_);
1255 }
1256# endif
1257
1258 _LIBCPP_HIDE_FROM_ABI void swap(map& __m) _NOEXCEPT_(__is_nothrow_swappable_v<__base>) { __tree_.swap(__m.__tree_); }
1259
1260 _LIBCPP_HIDE_FROM_ABI iterator find(const key_type& __k) { return __tree_.find(__k); }
1261 _LIBCPP_HIDE_FROM_ABI const_iterator find(const key_type& __k) const { return __tree_.find(__k); }
1262# if _LIBCPP_STD_VER >= 14
1263 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
1264 _LIBCPP_HIDE_FROM_ABI iterator find(const _K2& __k) {
1265 return __tree_.find(__k);
1266 }
1267 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
1268 _LIBCPP_HIDE_FROM_ABI const_iterator find(const _K2& __k) const {
1269 return __tree_.find(__k);
1270 }
1271# endif
1272
1273 _LIBCPP_HIDE_FROM_ABI size_type count(const key_type& __k) const { return __tree_.__count_unique(__k); }
1274# if _LIBCPP_STD_VER >= 14
1275 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
1276 _LIBCPP_HIDE_FROM_ABI size_type count(const _K2& __k) const {
1277 return __tree_.__count_multi(__k);
1278 }
1279# endif
1280
1281# if _LIBCPP_STD_VER >= 20
1282 _LIBCPP_HIDE_FROM_ABI bool contains(const key_type& __k) const { return find(__k) != end(); }
1283 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
1284 _LIBCPP_HIDE_FROM_ABI bool contains(const _K2& __k) const {
1285 return find(__k) != end();
1286 }
1287# endif // _LIBCPP_STD_VER >= 20
1288
1289 _LIBCPP_HIDE_FROM_ABI iterator lower_bound(const key_type& __k) { return __tree_.lower_bound(__k); }
1290 _LIBCPP_HIDE_FROM_ABI const_iterator lower_bound(const key_type& __k) const { return __tree_.lower_bound(__k); }
1291# if _LIBCPP_STD_VER >= 14
1292 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
1293 _LIBCPP_HIDE_FROM_ABI iterator lower_bound(const _K2& __k) {
1294 return __tree_.lower_bound(__k);
1295 }
1296
1297 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
1298 _LIBCPP_HIDE_FROM_ABI const_iterator lower_bound(const _K2& __k) const {
1299 return __tree_.lower_bound(__k);
1300 }
1301# endif
1302
1303 _LIBCPP_HIDE_FROM_ABI iterator upper_bound(const key_type& __k) { return __tree_.upper_bound(__k); }
1304 _LIBCPP_HIDE_FROM_ABI const_iterator upper_bound(const key_type& __k) const { return __tree_.upper_bound(__k); }
1305# if _LIBCPP_STD_VER >= 14
1306 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
1307 _LIBCPP_HIDE_FROM_ABI iterator upper_bound(const _K2& __k) {
1308 return __tree_.upper_bound(__k);
1309 }
1310 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
1311 _LIBCPP_HIDE_FROM_ABI const_iterator upper_bound(const _K2& __k) const {
1312 return __tree_.upper_bound(__k);
1313 }
1314# endif
1315
1316 _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const key_type& __k) {
1317 return __tree_.__equal_range_unique(__k);
1318 }
1319 _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const key_type& __k) const {
1320 return __tree_.__equal_range_unique(__k);
1321 }
1322# if _LIBCPP_STD_VER >= 14
1323 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
1324 _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const _K2& __k) {
1325 return __tree_.__equal_range_multi(__k);
1326 }
1327 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
1328 _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const _K2& __k) const {
1329 return __tree_.__equal_range_multi(__k);
1330 }
1331# endif
1332
1333private:
1334 typedef typename __base::__node __node;
1335 typedef typename __base::__node_allocator __node_allocator;
1336 typedef typename __base::__node_pointer __node_pointer;
1337 typedef typename __base::__node_base_pointer __node_base_pointer;
1338 typedef typename __base::__parent_pointer __parent_pointer;
1339
1340 typedef __map_node_destructor<__node_allocator> _Dp;
1341 typedef unique_ptr<__node, _Dp> __node_holder;
1342
1343# ifdef _LIBCPP_CXX03_LANG
1344 _LIBCPP_HIDE_FROM_ABI __node_holder __construct_node_with_key(const key_type& __k);
1345# endif
1346};
1347
1348# if _LIBCPP_STD_VER >= 17
1349template <class _InputIterator,
1350 class _Compare = less<__iter_key_type<_InputIterator>>,
1351 class _Allocator = allocator<__iter_to_alloc_type<_InputIterator>>,
1352 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value, void>,
1353 class = enable_if_t<!__is_allocator<_Compare>::value, void>,
1354 class = enable_if_t<__is_allocator<_Allocator>::value, void>>
1355map(_InputIterator, _InputIterator, _Compare = _Compare(), _Allocator = _Allocator())
1356 -> map<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>, _Compare, _Allocator>;
1357
1358# if _LIBCPP_STD_VER >= 23
1359template <ranges::input_range _Range,
1360 class _Compare = less<__range_key_type<_Range>>,
1361 class _Allocator = allocator<__range_to_alloc_type<_Range>>,
1362 class = enable_if_t<!__is_allocator<_Compare>::value, void>,
1363 class = enable_if_t<__is_allocator<_Allocator>::value, void>>
1364map(from_range_t, _Range&&, _Compare = _Compare(), _Allocator = _Allocator())
1365 -> map<__range_key_type<_Range>, __range_mapped_type<_Range>, _Compare, _Allocator>;
1366# endif
1367
1368template <class _Key,
1369 class _Tp,
1370 class _Compare = less<remove_const_t<_Key>>,
1371 class _Allocator = allocator<pair<const _Key, _Tp>>,
1372 class = enable_if_t<!__is_allocator<_Compare>::value, void>,
1373 class = enable_if_t<__is_allocator<_Allocator>::value, void>>
1374map(initializer_list<pair<_Key, _Tp>>,
1375 _Compare = _Compare(),
1376 _Allocator = _Allocator()) -> map<remove_const_t<_Key>, _Tp, _Compare, _Allocator>;
1377
1378template <class _InputIterator,
1379 class _Allocator,
1380 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value, void>,
1381 class = enable_if_t<__is_allocator<_Allocator>::value, void>>
1382map(_InputIterator, _InputIterator, _Allocator)
1383 -> map<__iter_key_type<_InputIterator>,
1384 __iter_mapped_type<_InputIterator>,
1385 less<__iter_key_type<_InputIterator>>,
1386 _Allocator>;
1387
1388# if _LIBCPP_STD_VER >= 23
1389template <ranges::input_range _Range, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value, void>>
1390map(from_range_t, _Range&&, _Allocator)
1391 -> map<__range_key_type<_Range>, __range_mapped_type<_Range>, less<__range_key_type<_Range>>, _Allocator>;
1392# endif
1393
1394template <class _Key, class _Tp, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value, void>>
1395map(initializer_list<pair<_Key, _Tp>>,
1396 _Allocator) -> map<remove_const_t<_Key>, _Tp, less<remove_const_t<_Key>>, _Allocator>;
1397# endif
1398
1399# ifndef _LIBCPP_CXX03_LANG
1400template <class _Key, class _Tp, class _Compare, class _Allocator>
1401map<_Key, _Tp, _Compare, _Allocator>::map(map&& __m, const allocator_type& __a)
1402 : __tree_(std::move(__m.__tree_), typename __base::allocator_type(__a)) {
1403 if (__a != __m.get_allocator()) {
1404 const_iterator __e = cend();
1405 while (!__m.empty()) {
1406 __tree_.__insert_unique_from_orphaned_node(__e.__i_, std::move(__m.__tree_.remove(__m.begin().__i_)->__value_));
1407 }
1408 }
1409}
1410
1411template <class _Key, class _Tp, class _Compare, class _Allocator>
1412_Tp& map<_Key, _Tp, _Compare, _Allocator>::operator[](const key_type& __k) {
1413 return __tree_
1414 .__emplace_unique_key_args(__k, std::piecewise_construct, std::forward_as_tuple(__k), std::forward_as_tuple())
1415 .first->second;
1416}
1417
1418template <class _Key, class _Tp, class _Compare, class _Allocator>
1419_Tp& map<_Key, _Tp, _Compare, _Allocator>::operator[](key_type&& __k) {
1420 // TODO investigate this clang-tidy warning.
1421 // NOLINTBEGIN(bugprone-use-after-move)
1422 return __tree_
1423 .__emplace_unique_key_args(
1424 __k, std::piecewise_construct, std::forward_as_tuple(std::move(__k)), std::forward_as_tuple())
1425 .first->second;
1426 // NOLINTEND(bugprone-use-after-move)
1427}
1428
1429# else // _LIBCPP_CXX03_LANG
1430
1431template <class _Key, class _Tp, class _Compare, class _Allocator>
1432typename map<_Key, _Tp, _Compare, _Allocator>::__node_holder
1433map<_Key, _Tp, _Compare, _Allocator>::__construct_node_with_key(const key_type& __k) {
1434 __node_allocator& __na = __tree_.__node_alloc();
1435 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1436 __node_traits::construct(__na, std::addressof(__h->__value_.first), __k);
1437 __h.get_deleter().__first_constructed = true;
1438 __node_traits::construct(__na, std::addressof(__h->__value_.second));
1439 __h.get_deleter().__second_constructed = true;
1440 return __h;
1441}
1442
1443template <class _Key, class _Tp, class _Compare, class _Allocator>
1444_Tp& map<_Key, _Tp, _Compare, _Allocator>::operator[](const key_type& __k) {
1445 __parent_pointer __parent;
1446 __node_base_pointer& __child = __tree_.__find_equal(__parent, __k);
1447 __node_pointer __r = static_cast<__node_pointer>(__child);
1448 if (__child == nullptr) {
1449 __node_holder __h = __construct_node_with_key(__k);
1450 __tree_.__insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
1451 __r = __h.release();
1452 }
1453 return __r->__value_.second;
1454}
1455
1456# endif // _LIBCPP_CXX03_LANG
1457
1458template <class _Key, class _Tp, class _Compare, class _Allocator>
1459_Tp& map<_Key, _Tp, _Compare, _Allocator>::at(const key_type& __k) {
1460 __parent_pointer __parent;
1461 __node_base_pointer& __child = __tree_.__find_equal(__parent, __k);
1462 if (__child == nullptr)
1463 std::__throw_out_of_range(msg: "map::at: key not found");
1464 return static_cast<__node_pointer>(__child)->__value_.second;
1465}
1466
1467template <class _Key, class _Tp, class _Compare, class _Allocator>
1468const _Tp& map<_Key, _Tp, _Compare, _Allocator>::at(const key_type& __k) const {
1469 __parent_pointer __parent;
1470 __node_base_pointer __child = __tree_.__find_equal(__parent, __k);
1471 if (__child == nullptr)
1472 std::__throw_out_of_range(msg: "map::at: key not found");
1473 return static_cast<__node_pointer>(__child)->__value_.second;
1474}
1475
1476template <class _Key, class _Tp, class _Compare, class _Allocator>
1477inline _LIBCPP_HIDE_FROM_ABI bool
1478operator==(const map<_Key, _Tp, _Compare, _Allocator>& __x, const map<_Key, _Tp, _Compare, _Allocator>& __y) {
1479 return __x.size() == __y.size() && std::equal(__x.begin(), __x.end(), __y.begin());
1480}
1481
1482# if _LIBCPP_STD_VER <= 17
1483
1484template <class _Key, class _Tp, class _Compare, class _Allocator>
1485inline _LIBCPP_HIDE_FROM_ABI bool
1486operator<(const map<_Key, _Tp, _Compare, _Allocator>& __x, const map<_Key, _Tp, _Compare, _Allocator>& __y) {
1487 return std::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
1488}
1489
1490template <class _Key, class _Tp, class _Compare, class _Allocator>
1491inline _LIBCPP_HIDE_FROM_ABI bool
1492operator!=(const map<_Key, _Tp, _Compare, _Allocator>& __x, const map<_Key, _Tp, _Compare, _Allocator>& __y) {
1493 return !(__x == __y);
1494}
1495
1496template <class _Key, class _Tp, class _Compare, class _Allocator>
1497inline _LIBCPP_HIDE_FROM_ABI bool
1498operator>(const map<_Key, _Tp, _Compare, _Allocator>& __x, const map<_Key, _Tp, _Compare, _Allocator>& __y) {
1499 return __y < __x;
1500}
1501
1502template <class _Key, class _Tp, class _Compare, class _Allocator>
1503inline _LIBCPP_HIDE_FROM_ABI bool
1504operator>=(const map<_Key, _Tp, _Compare, _Allocator>& __x, const map<_Key, _Tp, _Compare, _Allocator>& __y) {
1505 return !(__x < __y);
1506}
1507
1508template <class _Key, class _Tp, class _Compare, class _Allocator>
1509inline _LIBCPP_HIDE_FROM_ABI bool
1510operator<=(const map<_Key, _Tp, _Compare, _Allocator>& __x, const map<_Key, _Tp, _Compare, _Allocator>& __y) {
1511 return !(__y < __x);
1512}
1513
1514# else // #if _LIBCPP_STD_VER <= 17
1515
1516template <class _Key, class _Tp, class _Compare, class _Allocator>
1517_LIBCPP_HIDE_FROM_ABI __synth_three_way_result<pair<const _Key, _Tp>>
1518operator<=>(const map<_Key, _Tp, _Compare, _Allocator>& __x, const map<_Key, _Tp, _Compare, _Allocator>& __y) {
1519 return std::lexicographical_compare_three_way(__x.begin(), __x.end(), __y.begin(), __y.end(), std::__synth_three_way);
1520}
1521
1522# endif // #if _LIBCPP_STD_VER <= 17
1523
1524template <class _Key, class _Tp, class _Compare, class _Allocator>
1525inline _LIBCPP_HIDE_FROM_ABI void
1526swap(map<_Key, _Tp, _Compare, _Allocator>& __x, map<_Key, _Tp, _Compare, _Allocator>& __y)
1527 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) {
1528 __x.swap(__y);
1529}
1530
1531# if _LIBCPP_STD_VER >= 20
1532template <class _Key, class _Tp, class _Compare, class _Allocator, class _Predicate>
1533inline _LIBCPP_HIDE_FROM_ABI typename map<_Key, _Tp, _Compare, _Allocator>::size_type
1534erase_if(map<_Key, _Tp, _Compare, _Allocator>& __c, _Predicate __pred) {
1535 return std::__libcpp_erase_if_container(__c, __pred);
1536}
1537# endif
1538
1539template <class _Key, class _Tp, class _Compare, class _Allocator>
1540struct __container_traits<map<_Key, _Tp, _Compare, _Allocator> > {
1541 // http://eel.is/c++draft/associative.reqmts.except#2
1542 // For associative containers, if an exception is thrown by any operation from within
1543 // an insert or emplace function inserting a single element, the insertion has no effect.
1544 static _LIBCPP_CONSTEXPR const bool __emplacement_has_strong_exception_safety_guarantee = true;
1545
1546 static _LIBCPP_CONSTEXPR const bool __reservable = false;
1547};
1548
1549template <class _Key, class _Tp, class _Compare, class _Allocator>
1550class multimap {
1551public:
1552 // types:
1553 typedef _Key key_type;
1554 typedef _Tp mapped_type;
1555 typedef pair<const key_type, mapped_type> value_type;
1556 typedef __type_identity_t<_Compare> key_compare;
1557 typedef __type_identity_t<_Allocator> allocator_type;
1558 typedef value_type& reference;
1559 typedef const value_type& const_reference;
1560
1561 static_assert(__check_valid_allocator<allocator_type>::value, "");
1562 static_assert(is_same<typename allocator_type::value_type, value_type>::value,
1563 "Allocator::value_type must be same type as value_type");
1564
1565 class value_compare : public __binary_function<value_type, value_type, bool> {
1566 friend class multimap;
1567
1568 protected:
1569 key_compare comp;
1570
1571 _LIBCPP_HIDE_FROM_ABI value_compare(key_compare __c) : comp(__c) {}
1572
1573 public:
1574 _LIBCPP_HIDE_FROM_ABI bool operator()(const value_type& __x, const value_type& __y) const {
1575 return comp(__x.first, __y.first);
1576 }
1577 };
1578
1579private:
1580 typedef std::__value_type<key_type, mapped_type> __value_type;
1581 typedef __map_value_compare<key_type, value_type, key_compare> __vc;
1582 typedef __tree<__value_type, __vc, allocator_type> __base;
1583 typedef typename __base::__node_traits __node_traits;
1584 typedef allocator_traits<allocator_type> __alloc_traits;
1585
1586 __base __tree_;
1587
1588public:
1589 typedef typename __alloc_traits::pointer pointer;
1590 typedef typename __alloc_traits::const_pointer const_pointer;
1591 typedef typename __alloc_traits::size_type size_type;
1592 typedef typename __alloc_traits::difference_type difference_type;
1593 typedef __map_iterator<typename __base::iterator> iterator;
1594 typedef __map_const_iterator<typename __base::const_iterator> const_iterator;
1595 typedef std::reverse_iterator<iterator> reverse_iterator;
1596 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
1597
1598# if _LIBCPP_STD_VER >= 17
1599 typedef __map_node_handle<typename __base::__node, allocator_type> node_type;
1600# endif
1601
1602 template <class _Key2, class _Value2, class _Comp2, class _Alloc2>
1603 friend class map;
1604 template <class _Key2, class _Value2, class _Comp2, class _Alloc2>
1605 friend class multimap;
1606
1607 _LIBCPP_HIDE_FROM_ABI multimap() _NOEXCEPT_(
1608 is_nothrow_default_constructible<allocator_type>::value&& is_nothrow_default_constructible<key_compare>::value&&
1609 is_nothrow_copy_constructible<key_compare>::value)
1610 : __tree_(__vc(key_compare())) {}
1611
1612 _LIBCPP_HIDE_FROM_ABI explicit multimap(const key_compare& __comp) _NOEXCEPT_(
1613 is_nothrow_default_constructible<allocator_type>::value&& is_nothrow_copy_constructible<key_compare>::value)
1614 : __tree_(__vc(__comp)) {}
1615
1616 _LIBCPP_HIDE_FROM_ABI explicit multimap(const key_compare& __comp, const allocator_type& __a)
1617 : __tree_(__vc(__comp), typename __base::allocator_type(__a)) {}
1618
1619 template <class _InputIterator>
1620 _LIBCPP_HIDE_FROM_ABI multimap(_InputIterator __f, _InputIterator __l, const key_compare& __comp = key_compare())
1621 : __tree_(__vc(__comp)) {
1622 insert(__f, __l);
1623 }
1624
1625 template <class _InputIterator>
1626 _LIBCPP_HIDE_FROM_ABI
1627 multimap(_InputIterator __f, _InputIterator __l, const key_compare& __comp, const allocator_type& __a)
1628 : __tree_(__vc(__comp), typename __base::allocator_type(__a)) {
1629 insert(__f, __l);
1630 }
1631
1632# if _LIBCPP_STD_VER >= 23
1633 template <_ContainerCompatibleRange<value_type> _Range>
1634 _LIBCPP_HIDE_FROM_ABI
1635 multimap(from_range_t,
1636 _Range&& __range,
1637 const key_compare& __comp = key_compare(),
1638 const allocator_type& __a = allocator_type())
1639 : __tree_(__vc(__comp), typename __base::allocator_type(__a)) {
1640 insert_range(std::forward<_Range>(__range));
1641 }
1642# endif
1643
1644# if _LIBCPP_STD_VER >= 14
1645 template <class _InputIterator>
1646 _LIBCPP_HIDE_FROM_ABI multimap(_InputIterator __f, _InputIterator __l, const allocator_type& __a)
1647 : multimap(__f, __l, key_compare(), __a) {}
1648# endif
1649
1650# if _LIBCPP_STD_VER >= 23
1651 template <_ContainerCompatibleRange<value_type> _Range>
1652 _LIBCPP_HIDE_FROM_ABI multimap(from_range_t, _Range&& __range, const allocator_type& __a)
1653 : multimap(from_range, std::forward<_Range>(__range), key_compare(), __a) {}
1654# endif
1655
1656 _LIBCPP_HIDE_FROM_ABI multimap(const multimap& __m)
1657 : __tree_(__m.__tree_.value_comp(),
1658 __alloc_traits::select_on_container_copy_construction(__m.__tree_.__alloc())) {
1659 insert(__m.begin(), __m.end());
1660 }
1661
1662 _LIBCPP_HIDE_FROM_ABI multimap& operator=(const multimap& __m) {
1663# ifndef _LIBCPP_CXX03_LANG
1664 __tree_ = __m.__tree_;
1665# else
1666 if (this != std::addressof(__m)) {
1667 __tree_.clear();
1668 __tree_.value_comp() = __m.__tree_.value_comp();
1669 __tree_.__copy_assign_alloc(__m.__tree_);
1670 insert(__m.begin(), __m.end());
1671 }
1672# endif
1673 return *this;
1674 }
1675
1676# ifndef _LIBCPP_CXX03_LANG
1677
1678 _LIBCPP_HIDE_FROM_ABI multimap(multimap&& __m) noexcept(is_nothrow_move_constructible<__base>::value)
1679 : __tree_(std::move(__m.__tree_)) {}
1680
1681 _LIBCPP_HIDE_FROM_ABI multimap(multimap&& __m, const allocator_type& __a);
1682
1683 _LIBCPP_HIDE_FROM_ABI multimap& operator=(multimap&& __m) noexcept(is_nothrow_move_assignable<__base>::value) {
1684 __tree_ = std::move(__m.__tree_);
1685 return *this;
1686 }
1687
1688 _LIBCPP_HIDE_FROM_ABI multimap(initializer_list<value_type> __il, const key_compare& __comp = key_compare())
1689 : __tree_(__vc(__comp)) {
1690 insert(__il.begin(), __il.end());
1691 }
1692
1693 _LIBCPP_HIDE_FROM_ABI
1694 multimap(initializer_list<value_type> __il, const key_compare& __comp, const allocator_type& __a)
1695 : __tree_(__vc(__comp), typename __base::allocator_type(__a)) {
1696 insert(__il.begin(), __il.end());
1697 }
1698
1699# if _LIBCPP_STD_VER >= 14
1700 _LIBCPP_HIDE_FROM_ABI multimap(initializer_list<value_type> __il, const allocator_type& __a)
1701 : multimap(__il, key_compare(), __a) {}
1702# endif
1703
1704 _LIBCPP_HIDE_FROM_ABI multimap& operator=(initializer_list<value_type> __il) {
1705 __tree_.__assign_multi(__il.begin(), __il.end());
1706 return *this;
1707 }
1708
1709# endif // _LIBCPP_CXX03_LANG
1710
1711 _LIBCPP_HIDE_FROM_ABI explicit multimap(const allocator_type& __a) : __tree_(typename __base::allocator_type(__a)) {}
1712
1713 _LIBCPP_HIDE_FROM_ABI multimap(const multimap& __m, const allocator_type& __a)
1714 : __tree_(__m.__tree_.value_comp(), typename __base::allocator_type(__a)) {
1715 insert(__m.begin(), __m.end());
1716 }
1717
1718 _LIBCPP_HIDE_FROM_ABI ~multimap() {
1719 static_assert(sizeof(std::__diagnose_non_const_comparator<_Key, _Compare>()), "");
1720 }
1721
1722 _LIBCPP_HIDE_FROM_ABI iterator begin() _NOEXCEPT { return __tree_.begin(); }
1723 _LIBCPP_HIDE_FROM_ABI const_iterator begin() const _NOEXCEPT { return __tree_.begin(); }
1724 _LIBCPP_HIDE_FROM_ABI iterator end() _NOEXCEPT { return __tree_.end(); }
1725 _LIBCPP_HIDE_FROM_ABI const_iterator end() const _NOEXCEPT { return __tree_.end(); }
1726
1727 _LIBCPP_HIDE_FROM_ABI reverse_iterator rbegin() _NOEXCEPT { return reverse_iterator(end()); }
1728 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator rbegin() const _NOEXCEPT { return const_reverse_iterator(end()); }
1729 _LIBCPP_HIDE_FROM_ABI reverse_iterator rend() _NOEXCEPT { return reverse_iterator(begin()); }
1730 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator rend() const _NOEXCEPT { return const_reverse_iterator(begin()); }
1731
1732 _LIBCPP_HIDE_FROM_ABI const_iterator cbegin() const _NOEXCEPT { return begin(); }
1733 _LIBCPP_HIDE_FROM_ABI const_iterator cend() const _NOEXCEPT { return end(); }
1734 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator crbegin() const _NOEXCEPT { return rbegin(); }
1735 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator crend() const _NOEXCEPT { return rend(); }
1736
1737 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI bool empty() const _NOEXCEPT { return __tree_.size() == 0; }
1738 _LIBCPP_HIDE_FROM_ABI size_type size() const _NOEXCEPT { return __tree_.size(); }
1739 _LIBCPP_HIDE_FROM_ABI size_type max_size() const _NOEXCEPT { return __tree_.max_size(); }
1740
1741 _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const _NOEXCEPT { return allocator_type(__tree_.__alloc()); }
1742 _LIBCPP_HIDE_FROM_ABI key_compare key_comp() const { return __tree_.value_comp().key_comp(); }
1743 _LIBCPP_HIDE_FROM_ABI value_compare value_comp() const { return value_compare(__tree_.value_comp().key_comp()); }
1744
1745# ifndef _LIBCPP_CXX03_LANG
1746
1747 template <class... _Args>
1748 _LIBCPP_HIDE_FROM_ABI iterator emplace(_Args&&... __args) {
1749 return __tree_.__emplace_multi(std::forward<_Args>(__args)...);
1750 }
1751
1752 template <class... _Args>
1753 _LIBCPP_HIDE_FROM_ABI iterator emplace_hint(const_iterator __p, _Args&&... __args) {
1754 return __tree_.__emplace_hint_multi(__p.__i_, std::forward<_Args>(__args)...);
1755 }
1756
1757 template <class _Pp, __enable_if_t<is_constructible<value_type, _Pp>::value, int> = 0>
1758 _LIBCPP_HIDE_FROM_ABI iterator insert(_Pp&& __p) {
1759 return __tree_.__insert_multi(std::forward<_Pp>(__p));
1760 }
1761
1762 template <class _Pp, __enable_if_t<is_constructible<value_type, _Pp>::value, int> = 0>
1763 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __pos, _Pp&& __p) {
1764 return __tree_.__insert_multi(__pos.__i_, std::forward<_Pp>(__p));
1765 }
1766
1767 _LIBCPP_HIDE_FROM_ABI iterator insert(value_type&& __v) { return __tree_.__insert_multi(std::move(__v)); }
1768
1769 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, value_type&& __v) {
1770 return __tree_.__insert_multi(__p.__i_, std::move(__v));
1771 }
1772
1773 _LIBCPP_HIDE_FROM_ABI void insert(initializer_list<value_type> __il) { insert(__il.begin(), __il.end()); }
1774
1775# endif // _LIBCPP_CXX03_LANG
1776
1777 _LIBCPP_HIDE_FROM_ABI iterator insert(const value_type& __v) { return __tree_.__insert_multi(__v); }
1778
1779 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, const value_type& __v) {
1780 return __tree_.__insert_multi(__p.__i_, __v);
1781 }
1782
1783 template <class _InputIterator>
1784 _LIBCPP_HIDE_FROM_ABI void insert(_InputIterator __f, _InputIterator __l) {
1785 for (const_iterator __e = cend(); __f != __l; ++__f)
1786 __tree_.__insert_multi(__e.__i_, *__f);
1787 }
1788
1789# if _LIBCPP_STD_VER >= 23
1790 template <_ContainerCompatibleRange<value_type> _Range>
1791 _LIBCPP_HIDE_FROM_ABI void insert_range(_Range&& __range) {
1792 const_iterator __end = cend();
1793 for (auto&& __element : __range) {
1794 __tree_.__insert_multi(__end.__i_, std::forward<decltype(__element)>(__element));
1795 }
1796 }
1797# endif
1798
1799 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __p) { return __tree_.erase(__p.__i_); }
1800 _LIBCPP_HIDE_FROM_ABI iterator erase(iterator __p) { return __tree_.erase(__p.__i_); }
1801 _LIBCPP_HIDE_FROM_ABI size_type erase(const key_type& __k) { return __tree_.__erase_multi(__k); }
1802 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __f, const_iterator __l) {
1803 return __tree_.erase(__f.__i_, __l.__i_);
1804 }
1805
1806# if _LIBCPP_STD_VER >= 17
1807 _LIBCPP_HIDE_FROM_ABI iterator insert(node_type&& __nh) {
1808 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(),
1809 "node_type with incompatible allocator passed to multimap::insert()");
1810 return __tree_.template __node_handle_insert_multi<node_type>(std::move(__nh));
1811 }
1812 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __hint, node_type&& __nh) {
1813 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(),
1814 "node_type with incompatible allocator passed to multimap::insert()");
1815 return __tree_.template __node_handle_insert_multi<node_type>(__hint.__i_, std::move(__nh));
1816 }
1817 _LIBCPP_HIDE_FROM_ABI node_type extract(key_type const& __key) {
1818 return __tree_.template __node_handle_extract<node_type>(__key);
1819 }
1820 _LIBCPP_HIDE_FROM_ABI node_type extract(const_iterator __it) {
1821 return __tree_.template __node_handle_extract<node_type>(__it.__i_);
1822 }
1823 template <class _Compare2>
1824 _LIBCPP_HIDE_FROM_ABI void merge(multimap<key_type, mapped_type, _Compare2, allocator_type>& __source) {
1825 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
1826 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
1827 return __tree_.__node_handle_merge_multi(__source.__tree_);
1828 }
1829 template <class _Compare2>
1830 _LIBCPP_HIDE_FROM_ABI void merge(multimap<key_type, mapped_type, _Compare2, allocator_type>&& __source) {
1831 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
1832 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
1833 return __tree_.__node_handle_merge_multi(__source.__tree_);
1834 }
1835 template <class _Compare2>
1836 _LIBCPP_HIDE_FROM_ABI void merge(map<key_type, mapped_type, _Compare2, allocator_type>& __source) {
1837 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
1838 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
1839 return __tree_.__node_handle_merge_multi(__source.__tree_);
1840 }
1841 template <class _Compare2>
1842 _LIBCPP_HIDE_FROM_ABI void merge(map<key_type, mapped_type, _Compare2, allocator_type>&& __source) {
1843 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
1844 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
1845 return __tree_.__node_handle_merge_multi(__source.__tree_);
1846 }
1847# endif
1848
1849 _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT { __tree_.clear(); }
1850
1851 _LIBCPP_HIDE_FROM_ABI void swap(multimap& __m) _NOEXCEPT_(__is_nothrow_swappable_v<__base>) {
1852 __tree_.swap(__m.__tree_);
1853 }
1854
1855 _LIBCPP_HIDE_FROM_ABI iterator find(const key_type& __k) { return __tree_.find(__k); }
1856 _LIBCPP_HIDE_FROM_ABI const_iterator find(const key_type& __k) const { return __tree_.find(__k); }
1857# if _LIBCPP_STD_VER >= 14
1858 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
1859 _LIBCPP_HIDE_FROM_ABI iterator find(const _K2& __k) {
1860 return __tree_.find(__k);
1861 }
1862 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
1863 _LIBCPP_HIDE_FROM_ABI const_iterator find(const _K2& __k) const {
1864 return __tree_.find(__k);
1865 }
1866# endif
1867
1868 _LIBCPP_HIDE_FROM_ABI size_type count(const key_type& __k) const { return __tree_.__count_multi(__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 size_type count(const _K2& __k) const {
1872 return __tree_.__count_multi(__k);
1873 }
1874# endif
1875
1876# if _LIBCPP_STD_VER >= 20
1877 _LIBCPP_HIDE_FROM_ABI bool contains(const key_type& __k) const { return find(__k) != end(); }
1878 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
1879 _LIBCPP_HIDE_FROM_ABI bool contains(const _K2& __k) const {
1880 return find(__k) != end();
1881 }
1882# endif // _LIBCPP_STD_VER >= 20
1883
1884 _LIBCPP_HIDE_FROM_ABI iterator lower_bound(const key_type& __k) { return __tree_.lower_bound(__k); }
1885 _LIBCPP_HIDE_FROM_ABI const_iterator lower_bound(const key_type& __k) const { return __tree_.lower_bound(__k); }
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 iterator lower_bound(const _K2& __k) {
1889 return __tree_.lower_bound(__k);
1890 }
1891
1892 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
1893 _LIBCPP_HIDE_FROM_ABI const_iterator lower_bound(const _K2& __k) const {
1894 return __tree_.lower_bound(__k);
1895 }
1896# endif
1897
1898 _LIBCPP_HIDE_FROM_ABI iterator upper_bound(const key_type& __k) { return __tree_.upper_bound(__k); }
1899 _LIBCPP_HIDE_FROM_ABI const_iterator upper_bound(const key_type& __k) const { return __tree_.upper_bound(__k); }
1900# if _LIBCPP_STD_VER >= 14
1901 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
1902 _LIBCPP_HIDE_FROM_ABI iterator upper_bound(const _K2& __k) {
1903 return __tree_.upper_bound(__k);
1904 }
1905 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
1906 _LIBCPP_HIDE_FROM_ABI const_iterator upper_bound(const _K2& __k) const {
1907 return __tree_.upper_bound(__k);
1908 }
1909# endif
1910
1911 _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const key_type& __k) {
1912 return __tree_.__equal_range_multi(__k);
1913 }
1914 _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const key_type& __k) const {
1915 return __tree_.__equal_range_multi(__k);
1916 }
1917# if _LIBCPP_STD_VER >= 14
1918 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
1919 _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const _K2& __k) {
1920 return __tree_.__equal_range_multi(__k);
1921 }
1922 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
1923 _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const _K2& __k) const {
1924 return __tree_.__equal_range_multi(__k);
1925 }
1926# endif
1927
1928private:
1929 typedef typename __base::__node __node;
1930 typedef typename __base::__node_allocator __node_allocator;
1931 typedef typename __base::__node_pointer __node_pointer;
1932
1933 typedef __map_node_destructor<__node_allocator> _Dp;
1934 typedef unique_ptr<__node, _Dp> __node_holder;
1935};
1936
1937# if _LIBCPP_STD_VER >= 17
1938template <class _InputIterator,
1939 class _Compare = less<__iter_key_type<_InputIterator>>,
1940 class _Allocator = allocator<__iter_to_alloc_type<_InputIterator>>,
1941 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value, void>,
1942 class = enable_if_t<!__is_allocator<_Compare>::value, void>,
1943 class = enable_if_t<__is_allocator<_Allocator>::value, void>>
1944multimap(_InputIterator, _InputIterator, _Compare = _Compare(), _Allocator = _Allocator())
1945 -> multimap<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>, _Compare, _Allocator>;
1946
1947# if _LIBCPP_STD_VER >= 23
1948template <ranges::input_range _Range,
1949 class _Compare = less<__range_key_type<_Range>>,
1950 class _Allocator = allocator<__range_to_alloc_type<_Range>>,
1951 class = enable_if_t<!__is_allocator<_Compare>::value, void>,
1952 class = enable_if_t<__is_allocator<_Allocator>::value, void>>
1953multimap(from_range_t, _Range&&, _Compare = _Compare(), _Allocator = _Allocator())
1954 -> multimap<__range_key_type<_Range>, __range_mapped_type<_Range>, _Compare, _Allocator>;
1955# endif
1956
1957template <class _Key,
1958 class _Tp,
1959 class _Compare = less<remove_const_t<_Key>>,
1960 class _Allocator = allocator<pair<const _Key, _Tp>>,
1961 class = enable_if_t<!__is_allocator<_Compare>::value, void>,
1962 class = enable_if_t<__is_allocator<_Allocator>::value, void>>
1963multimap(initializer_list<pair<_Key, _Tp>>,
1964 _Compare = _Compare(),
1965 _Allocator = _Allocator()) -> multimap<remove_const_t<_Key>, _Tp, _Compare, _Allocator>;
1966
1967template <class _InputIterator,
1968 class _Allocator,
1969 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value, void>,
1970 class = enable_if_t<__is_allocator<_Allocator>::value, void>>
1971multimap(_InputIterator, _InputIterator, _Allocator)
1972 -> multimap<__iter_key_type<_InputIterator>,
1973 __iter_mapped_type<_InputIterator>,
1974 less<__iter_key_type<_InputIterator>>,
1975 _Allocator>;
1976
1977# if _LIBCPP_STD_VER >= 23
1978template <ranges::input_range _Range, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value, void>>
1979multimap(from_range_t, _Range&&, _Allocator)
1980 -> multimap<__range_key_type<_Range>, __range_mapped_type<_Range>, less<__range_key_type<_Range>>, _Allocator>;
1981# endif
1982
1983template <class _Key, class _Tp, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value, void>>
1984multimap(initializer_list<pair<_Key, _Tp>>,
1985 _Allocator) -> multimap<remove_const_t<_Key>, _Tp, less<remove_const_t<_Key>>, _Allocator>;
1986# endif
1987
1988# ifndef _LIBCPP_CXX03_LANG
1989template <class _Key, class _Tp, class _Compare, class _Allocator>
1990multimap<_Key, _Tp, _Compare, _Allocator>::multimap(multimap&& __m, const allocator_type& __a)
1991 : __tree_(std::move(__m.__tree_), typename __base::allocator_type(__a)) {
1992 if (__a != __m.get_allocator()) {
1993 const_iterator __e = cend();
1994 while (!__m.empty())
1995 __tree_.__insert_multi_from_orphaned_node(__e.__i_, std::move(__m.__tree_.remove(__m.begin().__i_)->__value_));
1996 }
1997}
1998# endif
1999
2000template <class _Key, class _Tp, class _Compare, class _Allocator>
2001inline _LIBCPP_HIDE_FROM_ABI bool
2002operator==(const multimap<_Key, _Tp, _Compare, _Allocator>& __x, const multimap<_Key, _Tp, _Compare, _Allocator>& __y) {
2003 return __x.size() == __y.size() && std::equal(__x.begin(), __x.end(), __y.begin());
2004}
2005
2006# if _LIBCPP_STD_VER <= 17
2007
2008template <class _Key, class _Tp, class _Compare, class _Allocator>
2009inline _LIBCPP_HIDE_FROM_ABI bool
2010operator<(const multimap<_Key, _Tp, _Compare, _Allocator>& __x, const multimap<_Key, _Tp, _Compare, _Allocator>& __y) {
2011 return std::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
2012}
2013
2014template <class _Key, class _Tp, class _Compare, class _Allocator>
2015inline _LIBCPP_HIDE_FROM_ABI bool
2016operator!=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x, const multimap<_Key, _Tp, _Compare, _Allocator>& __y) {
2017 return !(__x == __y);
2018}
2019
2020template <class _Key, class _Tp, class _Compare, class _Allocator>
2021inline _LIBCPP_HIDE_FROM_ABI bool
2022operator>(const multimap<_Key, _Tp, _Compare, _Allocator>& __x, const multimap<_Key, _Tp, _Compare, _Allocator>& __y) {
2023 return __y < __x;
2024}
2025
2026template <class _Key, class _Tp, class _Compare, class _Allocator>
2027inline _LIBCPP_HIDE_FROM_ABI bool
2028operator>=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x, const multimap<_Key, _Tp, _Compare, _Allocator>& __y) {
2029 return !(__x < __y);
2030}
2031
2032template <class _Key, class _Tp, class _Compare, class _Allocator>
2033inline _LIBCPP_HIDE_FROM_ABI bool
2034operator<=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x, const multimap<_Key, _Tp, _Compare, _Allocator>& __y) {
2035 return !(__y < __x);
2036}
2037
2038# else // #if _LIBCPP_STD_VER <= 17
2039
2040template <class _Key, class _Tp, class _Compare, class _Allocator>
2041_LIBCPP_HIDE_FROM_ABI __synth_three_way_result<pair<const _Key, _Tp>>
2042operator<=>(const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
2043 const multimap<_Key, _Tp, _Compare, _Allocator>& __y) {
2044 return std::lexicographical_compare_three_way(__x.begin(), __x.end(), __y.begin(), __y.end(), __synth_three_way);
2045}
2046
2047# endif // #if _LIBCPP_STD_VER <= 17
2048
2049template <class _Key, class _Tp, class _Compare, class _Allocator>
2050inline _LIBCPP_HIDE_FROM_ABI void
2051swap(multimap<_Key, _Tp, _Compare, _Allocator>& __x, multimap<_Key, _Tp, _Compare, _Allocator>& __y)
2052 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) {
2053 __x.swap(__y);
2054}
2055
2056# if _LIBCPP_STD_VER >= 20
2057template <class _Key, class _Tp, class _Compare, class _Allocator, class _Predicate>
2058inline _LIBCPP_HIDE_FROM_ABI typename multimap<_Key, _Tp, _Compare, _Allocator>::size_type
2059erase_if(multimap<_Key, _Tp, _Compare, _Allocator>& __c, _Predicate __pred) {
2060 return std::__libcpp_erase_if_container(__c, __pred);
2061}
2062# endif
2063
2064template <class _Key, class _Tp, class _Compare, class _Allocator>
2065struct __container_traits<multimap<_Key, _Tp, _Compare, _Allocator> > {
2066 // http://eel.is/c++draft/associative.reqmts.except#2
2067 // For associative containers, if an exception is thrown by any operation from within
2068 // an insert or emplace function inserting a single element, the insertion has no effect.
2069 static _LIBCPP_CONSTEXPR const bool __emplacement_has_strong_exception_safety_guarantee = true;
2070
2071 static _LIBCPP_CONSTEXPR const bool __reservable = false;
2072};
2073
2074_LIBCPP_END_NAMESPACE_STD
2075
2076# if _LIBCPP_STD_VER >= 17
2077_LIBCPP_BEGIN_NAMESPACE_STD
2078namespace pmr {
2079template <class _KeyT, class _ValueT, class _CompareT = std::less<_KeyT>>
2080using map _LIBCPP_AVAILABILITY_PMR =
2081 std::map<_KeyT, _ValueT, _CompareT, polymorphic_allocator<std::pair<const _KeyT, _ValueT>>>;
2082
2083template <class _KeyT, class _ValueT, class _CompareT = std::less<_KeyT>>
2084using multimap _LIBCPP_AVAILABILITY_PMR =
2085 std::multimap<_KeyT, _ValueT, _CompareT, polymorphic_allocator<std::pair<const _KeyT, _ValueT>>>;
2086} // namespace pmr
2087_LIBCPP_END_NAMESPACE_STD
2088# endif
2089
2090_LIBCPP_POP_MACROS
2091
2092# if !defined(_LIBCPP_REMOVE_TRANSITIVE_INCLUDES) && _LIBCPP_STD_VER <= 20
2093# include <concepts>
2094# include <cstdlib>
2095# include <functional>
2096# include <iterator>
2097# include <type_traits>
2098# include <utility>
2099# endif
2100#endif // __cplusplus < 201103L && defined(_LIBCPP_USE_FROZEN_CXX03_HEADERS)
2101
2102#endif // _LIBCPP_MAP
2103