blob: c7f7df2fc9b9c855f169e7fb4c2ddf7e54488865 [file] [log] [blame]
Howard Hinnantc51e1022010-05-11 19:42:16 +00001// -*- C++ -*-
2//===----------------------------- map ------------------------------------===//
3//
Chandler Carruthd2012102019-01-19 10:56:40 +00004// 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
Howard Hinnantc51e1022010-05-11 19:42:16 +00007//
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;
Erik Pilkingtonc37a3d82018-08-01 01:33:38 +000042 typedef unspecified node_type; // C++17
43 typedef INSERT_RETURN_TYPE<iterator, node_type> insert_return_type; // C++17
Howard Hinnantc51e1022010-05-11 19:42:16 +000044
45 class value_compare
Howard Hinnantc51e1022010-05-11 19:42:16 +000046 {
47 friend class map;
48 protected:
49 key_compare comp;
50
51 value_compare(key_compare c);
52 public:
Arthur O'Dwyerf5486c82021-05-25 14:34:18 -040053 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
Howard Hinnantc51e1022010-05-11 19:42:16 +000056 bool operator()(const value_type& x, const value_type& y) const;
57 };
58
59 // construct/copy/destroy:
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +000060 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);
Howard Hinnantc51e1022010-05-11 19:42:16 +000065 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 map(const map& m);
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +000074 map(map&& m)
75 noexcept(
76 is_nothrow_move_constructible<allocator_type>::value &&
77 is_nothrow_move_constructible<key_compare>::value);
Howard Hinnantc51e1022010-05-11 19:42:16 +000078 explicit map(const allocator_type& a);
79 map(const map& m, const allocator_type& a);
80 map(map&& m, const allocator_type& a);
81 map(initializer_list<value_type> il, const key_compare& comp = key_compare());
82 map(initializer_list<value_type> il, const key_compare& comp, const allocator_type& a);
Marshall Clow300abfb2013-09-11 01:15:47 +000083 template <class InputIterator>
84 map(InputIterator first, InputIterator last, const allocator_type& a)
85 : map(first, last, Compare(), a) {} // C++14
86 map(initializer_list<value_type> il, const allocator_type& a)
87 : map(il, Compare(), a) {} // C++14
88 ~map();
Howard Hinnantc51e1022010-05-11 19:42:16 +000089
90 map& operator=(const map& m);
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +000091 map& operator=(map&& m)
92 noexcept(
93 allocator_type::propagate_on_container_move_assignment::value &&
94 is_nothrow_move_assignable<allocator_type>::value &&
Howard Hinnantf95f4f52011-06-04 15:22:34 +000095 is_nothrow_move_assignable<key_compare>::value);
Howard Hinnantc51e1022010-05-11 19:42:16 +000096 map& operator=(initializer_list<value_type> il);
97
98 // iterators:
Howard Hinnantf95f4f52011-06-04 15:22:34 +000099 iterator begin() noexcept;
100 const_iterator begin() const noexcept;
101 iterator end() noexcept;
102 const_iterator end() const noexcept;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000103
Howard Hinnantf95f4f52011-06-04 15:22:34 +0000104 reverse_iterator rbegin() noexcept;
105 const_reverse_iterator rbegin() const noexcept;
106 reverse_iterator rend() noexcept;
107 const_reverse_iterator rend() const noexcept;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000108
Howard Hinnantf95f4f52011-06-04 15:22:34 +0000109 const_iterator cbegin() const noexcept;
110 const_iterator cend() const noexcept;
111 const_reverse_iterator crbegin() const noexcept;
112 const_reverse_iterator crend() const noexcept;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000113
114 // capacity:
Howard Hinnantf95f4f52011-06-04 15:22:34 +0000115 bool empty() const noexcept;
116 size_type size() const noexcept;
117 size_type max_size() const noexcept;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000118
119 // element access:
120 mapped_type& operator[](const key_type& k);
121 mapped_type& operator[](key_type&& k);
122
123 mapped_type& at(const key_type& k);
124 const mapped_type& at(const key_type& k) const;
125
126 // modifiers:
127 template <class... Args>
128 pair<iterator, bool> emplace(Args&&... args);
129 template <class... Args>
130 iterator emplace_hint(const_iterator position, Args&&... args);
131 pair<iterator, bool> insert(const value_type& v);
Marshall Clowd430d022016-01-05 19:32:41 +0000132 pair<iterator, bool> insert( value_type&& v); // C++17
Howard Hinnantc51e1022010-05-11 19:42:16 +0000133 template <class P>
134 pair<iterator, bool> insert(P&& p);
135 iterator insert(const_iterator position, const value_type& v);
Marshall Clowd430d022016-01-05 19:32:41 +0000136 iterator insert(const_iterator position, value_type&& v); // C++17
Howard Hinnantc51e1022010-05-11 19:42:16 +0000137 template <class P>
138 iterator insert(const_iterator position, P&& p);
139 template <class InputIterator>
140 void insert(InputIterator first, InputIterator last);
141 void insert(initializer_list<value_type> il);
142
Erik Pilkingtonc37a3d82018-08-01 01:33:38 +0000143 node_type extract(const_iterator position); // C++17
144 node_type extract(const key_type& x); // C++17
145 insert_return_type insert(node_type&& nh); // C++17
146 iterator insert(const_iterator hint, node_type&& nh); // C++17
147
Marshall Clow3223db82015-07-07 03:37:33 +0000148 template <class... Args>
149 pair<iterator, bool> try_emplace(const key_type& k, Args&&... args); // C++17
150 template <class... Args>
151 pair<iterator, bool> try_emplace(key_type&& k, Args&&... args); // C++17
152 template <class... Args>
153 iterator try_emplace(const_iterator hint, const key_type& k, Args&&... args); // C++17
154 template <class... Args>
155 iterator try_emplace(const_iterator hint, key_type&& k, Args&&... args); // C++17
156 template <class M>
157 pair<iterator, bool> insert_or_assign(const key_type& k, M&& obj); // C++17
158 template <class M>
159 pair<iterator, bool> insert_or_assign(key_type&& k, M&& obj); // C++17
160 template <class M>
161 iterator insert_or_assign(const_iterator hint, const key_type& k, M&& obj); // C++17
162 template <class M>
163 iterator insert_or_assign(const_iterator hint, key_type&& k, M&& obj); // C++17
164
Howard Hinnantc51e1022010-05-11 19:42:16 +0000165 iterator erase(const_iterator position);
Marshall Clow22ea5b82015-05-10 13:35:00 +0000166 iterator erase(iterator position); // C++14
Howard Hinnantc51e1022010-05-11 19:42:16 +0000167 size_type erase(const key_type& k);
168 iterator erase(const_iterator first, const_iterator last);
Howard Hinnantf95f4f52011-06-04 15:22:34 +0000169 void clear() noexcept;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000170
Erik Pilkington82a65ad2018-10-31 17:31:35 +0000171 template<class C2>
172 void merge(map<Key, T, C2, Allocator>& source); // C++17
173 template<class C2>
174 void merge(map<Key, T, C2, Allocator>&& source); // C++17
175 template<class C2>
176 void merge(multimap<Key, T, C2, Allocator>& source); // C++17
177 template<class C2>
178 void merge(multimap<Key, T, C2, Allocator>&& source); // C++17
179
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000180 void swap(map& m)
Marshall Clow8982dcd2015-07-13 20:04:56 +0000181 noexcept(allocator_traits<allocator_type>::is_always_equal::value &&
Eric Fiselier6bfed252016-04-21 23:38:59 +0000182 is_nothrow_swappable<key_compare>::value); // C++17
Howard Hinnantc51e1022010-05-11 19:42:16 +0000183
184 // observers:
Howard Hinnantf95f4f52011-06-04 15:22:34 +0000185 allocator_type get_allocator() const noexcept;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000186 key_compare key_comp() const;
187 value_compare value_comp() const;
188
189 // map operations:
190 iterator find(const key_type& k);
191 const_iterator find(const key_type& k) const;
Marshall Clowebb57322013-08-13 22:18:47 +0000192 template<typename K>
193 iterator find(const K& x); // C++14
194 template<typename K>
195 const_iterator find(const K& x) const; // C++14
Marek Kurdejd7e019e2021-04-13 17:10:55 +0200196
Marshall Clowebb57322013-08-13 22:18:47 +0000197 template<typename K>
Marshall Clowe6a5f522014-08-24 23:54:16 +0000198 size_type count(const K& x) const; // C++14
Howard Hinnantc51e1022010-05-11 19:42:16 +0000199 size_type count(const key_type& k) const;
Marek Kurdejd7e019e2021-04-13 17:10:55 +0200200
201 bool contains(const key_type& x) const; // C++20
202 template<class K> bool contains(const K& x) const; // C++20
203
Howard Hinnantc51e1022010-05-11 19:42:16 +0000204 iterator lower_bound(const key_type& k);
205 const_iterator lower_bound(const key_type& k) const;
Marshall Clowebb57322013-08-13 22:18:47 +0000206 template<typename K>
207 iterator lower_bound(const K& x); // C++14
208 template<typename K>
209 const_iterator lower_bound(const K& x) const; // C++14
210
Howard Hinnantc51e1022010-05-11 19:42:16 +0000211 iterator upper_bound(const key_type& k);
212 const_iterator upper_bound(const key_type& k) const;
Marshall Clowebb57322013-08-13 22:18:47 +0000213 template<typename K>
214 iterator upper_bound(const K& x); // C++14
215 template<typename K>
216 const_iterator upper_bound(const K& x) const; // C++14
217
Howard Hinnantc51e1022010-05-11 19:42:16 +0000218 pair<iterator,iterator> equal_range(const key_type& k);
219 pair<const_iterator,const_iterator> equal_range(const key_type& k) const;
Marshall Clowebb57322013-08-13 22:18:47 +0000220 template<typename K>
221 pair<iterator,iterator> equal_range(const K& x); // C++14
222 template<typename K>
223 pair<const_iterator,const_iterator> equal_range(const K& x) const; // C++14
Howard Hinnantc51e1022010-05-11 19:42:16 +0000224};
225
226template <class Key, class T, class Compare, class Allocator>
227bool
228operator==(const map<Key, T, Compare, Allocator>& x,
229 const map<Key, T, Compare, Allocator>& y);
230
231template <class Key, class T, class Compare, class Allocator>
232bool
233operator< (const map<Key, T, Compare, Allocator>& x,
234 const map<Key, T, Compare, Allocator>& y);
235
236template <class Key, class T, class Compare, class Allocator>
237bool
238operator!=(const map<Key, T, Compare, Allocator>& x,
239 const map<Key, T, Compare, Allocator>& y);
240
241template <class Key, class T, class Compare, class Allocator>
242bool
243operator> (const map<Key, T, Compare, Allocator>& x,
244 const map<Key, T, Compare, Allocator>& y);
245
246template <class Key, class T, class Compare, class Allocator>
247bool
248operator>=(const map<Key, T, Compare, Allocator>& x,
249 const map<Key, T, Compare, Allocator>& y);
250
251template <class Key, class T, class Compare, class Allocator>
252bool
253operator<=(const map<Key, T, Compare, Allocator>& x,
254 const map<Key, T, Compare, Allocator>& y);
255
256// specialized algorithms:
257template <class Key, class T, class Compare, class Allocator>
258void
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000259swap(map<Key, T, Compare, Allocator>& x, map<Key, T, Compare, Allocator>& y)
260 noexcept(noexcept(x.swap(y)));
Howard Hinnantc51e1022010-05-11 19:42:16 +0000261
Marshall Clow29b53f22018-12-14 18:49:35 +0000262template <class Key, class T, class Compare, class Allocator, class Predicate>
Marek Kurdeja98b1412020-05-02 13:58:03 +0200263typename map<Key, T, Compare, Allocator>::size_type
264erase_if(map<Key, T, Compare, Allocator>& c, Predicate pred); // C++20
Marshall Clow29b53f22018-12-14 18:49:35 +0000265
266
Howard Hinnantc51e1022010-05-11 19:42:16 +0000267template <class Key, class T, class Compare = less<Key>,
268 class Allocator = allocator<pair<const Key, T>>>
269class multimap
270{
271public:
272 // types:
273 typedef Key key_type;
274 typedef T mapped_type;
275 typedef pair<const key_type,mapped_type> value_type;
276 typedef Compare key_compare;
277 typedef Allocator allocator_type;
278 typedef typename allocator_type::reference reference;
279 typedef typename allocator_type::const_reference const_reference;
280 typedef typename allocator_type::size_type size_type;
281 typedef typename allocator_type::difference_type difference_type;
282 typedef typename allocator_type::pointer pointer;
283 typedef typename allocator_type::const_pointer const_pointer;
284
285 typedef implementation-defined iterator;
286 typedef implementation-defined const_iterator;
287 typedef std::reverse_iterator<iterator> reverse_iterator;
288 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
Erik Pilkingtonc37a3d82018-08-01 01:33:38 +0000289 typedef unspecified node_type; // C++17
Howard Hinnantc51e1022010-05-11 19:42:16 +0000290
291 class value_compare
Howard Hinnantc51e1022010-05-11 19:42:16 +0000292 {
293 friend class multimap;
294 protected:
295 key_compare comp;
296 value_compare(key_compare c);
297 public:
Arthur O'Dwyerf5486c82021-05-25 14:34:18 -0400298 typedef bool result_type; // deprecated in C++17, removed in C++20
299 typedef value_type first_argument_type; // deprecated in C++17, removed in C++20
300 typedef value_type second_argument_type; // deprecated in C++17, removed in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000301 bool operator()(const value_type& x, const value_type& y) const;
302 };
303
304 // construct/copy/destroy:
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000305 multimap()
306 noexcept(
307 is_nothrow_default_constructible<allocator_type>::value &&
308 is_nothrow_default_constructible<key_compare>::value &&
309 is_nothrow_copy_constructible<key_compare>::value);
310 explicit multimap(const key_compare& comp);
Howard Hinnantc51e1022010-05-11 19:42:16 +0000311 multimap(const key_compare& comp, const allocator_type& a);
312 template <class InputIterator>
313 multimap(InputIterator first, InputIterator last, const key_compare& comp);
314 template <class InputIterator>
315 multimap(InputIterator first, InputIterator last, const key_compare& comp,
316 const allocator_type& a);
317 multimap(const multimap& m);
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000318 multimap(multimap&& m)
319 noexcept(
320 is_nothrow_move_constructible<allocator_type>::value &&
321 is_nothrow_move_constructible<key_compare>::value);
Howard Hinnantc51e1022010-05-11 19:42:16 +0000322 explicit multimap(const allocator_type& a);
323 multimap(const multimap& m, const allocator_type& a);
324 multimap(multimap&& m, const allocator_type& a);
325 multimap(initializer_list<value_type> il, const key_compare& comp = key_compare());
326 multimap(initializer_list<value_type> il, const key_compare& comp,
327 const allocator_type& a);
Marshall Clow300abfb2013-09-11 01:15:47 +0000328 template <class InputIterator>
329 multimap(InputIterator first, InputIterator last, const allocator_type& a)
330 : multimap(first, last, Compare(), a) {} // C++14
331 multimap(initializer_list<value_type> il, const allocator_type& a)
332 : multimap(il, Compare(), a) {} // C++14
Howard Hinnantc51e1022010-05-11 19:42:16 +0000333 ~multimap();
334
335 multimap& operator=(const multimap& m);
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000336 multimap& operator=(multimap&& m)
337 noexcept(
338 allocator_type::propagate_on_container_move_assignment::value &&
339 is_nothrow_move_assignable<allocator_type>::value &&
Howard Hinnantf95f4f52011-06-04 15:22:34 +0000340 is_nothrow_move_assignable<key_compare>::value);
Howard Hinnantc51e1022010-05-11 19:42:16 +0000341 multimap& operator=(initializer_list<value_type> il);
342
343 // iterators:
Howard Hinnantf95f4f52011-06-04 15:22:34 +0000344 iterator begin() noexcept;
345 const_iterator begin() const noexcept;
346 iterator end() noexcept;
347 const_iterator end() const noexcept;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000348
Howard Hinnantf95f4f52011-06-04 15:22:34 +0000349 reverse_iterator rbegin() noexcept;
350 const_reverse_iterator rbegin() const noexcept;
351 reverse_iterator rend() noexcept;
352 const_reverse_iterator rend() const noexcept;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000353
Howard Hinnantf95f4f52011-06-04 15:22:34 +0000354 const_iterator cbegin() const noexcept;
355 const_iterator cend() const noexcept;
356 const_reverse_iterator crbegin() const noexcept;
357 const_reverse_iterator crend() const noexcept;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000358
359 // capacity:
Howard Hinnantf95f4f52011-06-04 15:22:34 +0000360 bool empty() const noexcept;
361 size_type size() const noexcept;
362 size_type max_size() const noexcept;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000363
364 // modifiers:
365 template <class... Args>
366 iterator emplace(Args&&... args);
367 template <class... Args>
368 iterator emplace_hint(const_iterator position, Args&&... args);
369 iterator insert(const value_type& v);
Marshall Clowd430d022016-01-05 19:32:41 +0000370 iterator insert( value_type&& v); // C++17
Howard Hinnantc51e1022010-05-11 19:42:16 +0000371 template <class P>
372 iterator insert(P&& p);
373 iterator insert(const_iterator position, const value_type& v);
Marshall Clowd430d022016-01-05 19:32:41 +0000374 iterator insert(const_iterator position, value_type&& v); // C++17
Howard Hinnantc51e1022010-05-11 19:42:16 +0000375 template <class P>
376 iterator insert(const_iterator position, P&& p);
377 template <class InputIterator>
378 void insert(InputIterator first, InputIterator last);
379 void insert(initializer_list<value_type> il);
380
Erik Pilkingtonc37a3d82018-08-01 01:33:38 +0000381 node_type extract(const_iterator position); // C++17
382 node_type extract(const key_type& x); // C++17
383 iterator insert(node_type&& nh); // C++17
384 iterator insert(const_iterator hint, node_type&& nh); // C++17
385
Howard Hinnantc51e1022010-05-11 19:42:16 +0000386 iterator erase(const_iterator position);
Marshall Clow22ea5b82015-05-10 13:35:00 +0000387 iterator erase(iterator position); // C++14
Howard Hinnantc51e1022010-05-11 19:42:16 +0000388 size_type erase(const key_type& k);
389 iterator erase(const_iterator first, const_iterator last);
Howard Hinnantf95f4f52011-06-04 15:22:34 +0000390 void clear() noexcept;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000391
Erik Pilkington82a65ad2018-10-31 17:31:35 +0000392 template<class C2>
393 void merge(multimap<Key, T, C2, Allocator>& source); // C++17
394 template<class C2>
395 void merge(multimap<Key, T, C2, Allocator>&& source); // C++17
396 template<class C2>
397 void merge(map<Key, T, C2, Allocator>& source); // C++17
398 template<class C2>
399 void merge(map<Key, T, C2, Allocator>&& source); // C++17
400
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000401 void swap(multimap& m)
Marshall Clow8982dcd2015-07-13 20:04:56 +0000402 noexcept(allocator_traits<allocator_type>::is_always_equal::value &&
Eric Fiselier6bfed252016-04-21 23:38:59 +0000403 is_nothrow_swappable<key_compare>::value); // C++17
Howard Hinnantc51e1022010-05-11 19:42:16 +0000404
405 // observers:
Howard Hinnantf95f4f52011-06-04 15:22:34 +0000406 allocator_type get_allocator() const noexcept;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000407 key_compare key_comp() const;
408 value_compare value_comp() const;
409
410 // map operations:
411 iterator find(const key_type& k);
412 const_iterator find(const key_type& k) const;
Marshall Clowebb57322013-08-13 22:18:47 +0000413 template<typename K>
414 iterator find(const K& x); // C++14
415 template<typename K>
416 const_iterator find(const K& x) const; // C++14
Marek Kurdejd7e019e2021-04-13 17:10:55 +0200417
Marshall Clowebb57322013-08-13 22:18:47 +0000418 template<typename K>
Marshall Clowe6a5f522014-08-24 23:54:16 +0000419 size_type count(const K& x) const; // C++14
Howard Hinnantc51e1022010-05-11 19:42:16 +0000420 size_type count(const key_type& k) const;
Marek Kurdejd7e019e2021-04-13 17:10:55 +0200421
422 bool contains(const key_type& x) const; // C++20
423 template<class K> bool contains(const K& x) const; // C++20
424
Howard Hinnantc51e1022010-05-11 19:42:16 +0000425 iterator lower_bound(const key_type& k);
426 const_iterator lower_bound(const key_type& k) const;
Marshall Clowebb57322013-08-13 22:18:47 +0000427 template<typename K>
428 iterator lower_bound(const K& x); // C++14
429 template<typename K>
430 const_iterator lower_bound(const K& x) const; // C++14
431
Howard Hinnantc51e1022010-05-11 19:42:16 +0000432 iterator upper_bound(const key_type& k);
433 const_iterator upper_bound(const key_type& k) const;
Marshall Clowebb57322013-08-13 22:18:47 +0000434 template<typename K>
435 iterator upper_bound(const K& x); // C++14
436 template<typename K>
437 const_iterator upper_bound(const K& x) const; // C++14
438
Howard Hinnantc51e1022010-05-11 19:42:16 +0000439 pair<iterator,iterator> equal_range(const key_type& k);
440 pair<const_iterator,const_iterator> equal_range(const key_type& k) const;
Marshall Clowebb57322013-08-13 22:18:47 +0000441 template<typename K>
442 pair<iterator,iterator> equal_range(const K& x); // C++14
443 template<typename K>
444 pair<const_iterator,const_iterator> equal_range(const K& x) const; // C++14
Howard Hinnantc51e1022010-05-11 19:42:16 +0000445};
446
447template <class Key, class T, class Compare, class Allocator>
448bool
449operator==(const multimap<Key, T, Compare, Allocator>& x,
450 const multimap<Key, T, Compare, Allocator>& y);
451
452template <class Key, class T, class Compare, class Allocator>
453bool
454operator< (const multimap<Key, T, Compare, Allocator>& x,
455 const multimap<Key, T, Compare, Allocator>& y);
456
457template <class Key, class T, class Compare, class Allocator>
458bool
459operator!=(const multimap<Key, T, Compare, Allocator>& x,
460 const multimap<Key, T, Compare, Allocator>& y);
461
462template <class Key, class T, class Compare, class Allocator>
463bool
464operator> (const multimap<Key, T, Compare, Allocator>& x,
465 const multimap<Key, T, Compare, Allocator>& y);
466
467template <class Key, class T, class Compare, class Allocator>
468bool
469operator>=(const multimap<Key, T, Compare, Allocator>& x,
470 const multimap<Key, T, Compare, Allocator>& y);
471
472template <class Key, class T, class Compare, class Allocator>
473bool
474operator<=(const multimap<Key, T, Compare, Allocator>& x,
475 const multimap<Key, T, Compare, Allocator>& y);
476
477// specialized algorithms:
478template <class Key, class T, class Compare, class Allocator>
479void
480swap(multimap<Key, T, Compare, Allocator>& x,
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000481 multimap<Key, T, Compare, Allocator>& y)
482 noexcept(noexcept(x.swap(y)));
Howard Hinnantc51e1022010-05-11 19:42:16 +0000483
Marshall Clow29b53f22018-12-14 18:49:35 +0000484template <class Key, class T, class Compare, class Allocator, class Predicate>
Marek Kurdeja98b1412020-05-02 13:58:03 +0200485typename multimap<Key, T, Compare, Allocator>::size_type
486erase_if(multimap<Key, T, Compare, Allocator>& c, Predicate pred); // C++20
Marshall Clow29b53f22018-12-14 18:49:35 +0000487
Howard Hinnantc51e1022010-05-11 19:42:16 +0000488} // std
489
490*/
491
492#include <__config>
Arthur O'Dwyer597cac42021-05-12 23:04:03 -0400493#include <__debug>
Erik Pilkingtonc37a3d82018-08-01 01:33:38 +0000494#include <__node_handle>
Arthur O'Dwyer597cac42021-05-12 23:04:03 -0400495#include <__tree>
Arthur O'Dwyer7deec122021-03-24 18:19:12 -0400496#include <compare>
Arthur O'Dwyeref181602021-05-19 11:57:04 -0400497#include <functional>
Arthur O'Dwyer7deec122021-03-24 18:19:12 -0400498#include <initializer_list>
Arthur O'Dwyerb6738bd2021-03-21 16:53:09 -0400499#include <iterator> // __libcpp_erase_if_container
Howard Hinnantc51e1022010-05-11 19:42:16 +0000500#include <memory>
Eric Fiselierf7394302015-06-13 07:08:02 +0000501#include <type_traits>
Arthur O'Dwyeref181602021-05-19 11:57:04 -0400502#include <utility>
Marshall Clow0a1e7502018-09-12 19:41:40 +0000503#include <version>
Howard Hinnantc51e1022010-05-11 19:42:16 +0000504
Howard Hinnantaaaa52b2011-10-17 20:05:10 +0000505#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
Howard Hinnantc51e1022010-05-11 19:42:16 +0000506#pragma GCC system_header
Howard Hinnantaaaa52b2011-10-17 20:05:10 +0000507#endif
Howard Hinnantc51e1022010-05-11 19:42:16 +0000508
509_LIBCPP_BEGIN_NAMESPACE_STD
510
Louis Dionne878a3a82018-12-06 21:46:17 +0000511template <class _Key, class _CP, class _Compare,
512 bool = is_empty<_Compare>::value && !__libcpp_is_final<_Compare>::value>
Howard Hinnantc51e1022010-05-11 19:42:16 +0000513class __map_value_compare
514 : private _Compare
515{
Howard Hinnantc51e1022010-05-11 19:42:16 +0000516public:
Howard Hinnant756c69b2010-09-22 16:48:34 +0000517 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000518 __map_value_compare()
519 _NOEXCEPT_(is_nothrow_default_constructible<_Compare>::value)
520 : _Compare() {}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000521 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000522 __map_value_compare(_Compare c)
523 _NOEXCEPT_(is_nothrow_copy_constructible<_Compare>::value)
524 : _Compare(c) {}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000525 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000526 const _Compare& key_comp() const _NOEXCEPT {return *this;}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000527 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000528 bool operator()(const _CP& __x, const _CP& __y) const
Erik Pilkingtond3fe2992018-06-04 20:38:23 +0000529 {return static_cast<const _Compare&>(*this)(__x.__get_value().first, __y.__get_value().first);}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000530 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000531 bool operator()(const _CP& __x, const _Key& __y) const
Erik Pilkingtond3fe2992018-06-04 20:38:23 +0000532 {return static_cast<const _Compare&>(*this)(__x.__get_value().first, __y);}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000533 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000534 bool operator()(const _Key& __x, const _CP& __y) const
Erik Pilkingtond3fe2992018-06-04 20:38:23 +0000535 {return static_cast<const _Compare&>(*this)(__x, __y.__get_value().first);}
Marshall Clow8982dcd2015-07-13 20:04:56 +0000536 void swap(__map_value_compare&__y)
537 _NOEXCEPT_(__is_nothrow_swappable<_Compare>::value)
538 {
Eric Fiselier68b5f0b2017-04-13 00:34:24 +0000539 using _VSTD::swap;
540 swap(static_cast<_Compare&>(*this), static_cast<_Compare&>(__y));
Marshall Clow8982dcd2015-07-13 20:04:56 +0000541 }
Marshall Clowebb57322013-08-13 22:18:47 +0000542
543#if _LIBCPP_STD_VER > 11
544 template <typename _K2>
545 _LIBCPP_INLINE_VISIBILITY
546 typename enable_if<__is_transparent<_Compare, _K2>::value, bool>::type
547 operator () ( const _K2& __x, const _CP& __y ) const
Erik Pilkingtond3fe2992018-06-04 20:38:23 +0000548 {return static_cast<const _Compare&>(*this) (__x, __y.__get_value().first);}
Marshall Clowebb57322013-08-13 22:18:47 +0000549
550 template <typename _K2>
551 _LIBCPP_INLINE_VISIBILITY
552 typename enable_if<__is_transparent<_Compare, _K2>::value, bool>::type
553 operator () (const _CP& __x, const _K2& __y) const
Erik Pilkingtond3fe2992018-06-04 20:38:23 +0000554 {return static_cast<const _Compare&>(*this) (__x.__get_value().first, __y);}
Marshall Clowebb57322013-08-13 22:18:47 +0000555#endif
Howard Hinnantc51e1022010-05-11 19:42:16 +0000556};
557
Howard Hinnant90b91592013-07-05 18:06:00 +0000558template <class _Key, class _CP, class _Compare>
559class __map_value_compare<_Key, _CP, _Compare, false>
Howard Hinnantc51e1022010-05-11 19:42:16 +0000560{
561 _Compare comp;
562
Howard Hinnantc51e1022010-05-11 19:42:16 +0000563public:
Howard Hinnant756c69b2010-09-22 16:48:34 +0000564 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000565 __map_value_compare()
566 _NOEXCEPT_(is_nothrow_default_constructible<_Compare>::value)
567 : comp() {}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000568 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000569 __map_value_compare(_Compare c)
570 _NOEXCEPT_(is_nothrow_copy_constructible<_Compare>::value)
571 : comp(c) {}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000572 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000573 const _Compare& key_comp() const _NOEXCEPT {return comp;}
Howard Hinnantc51e1022010-05-11 19:42:16 +0000574
Howard Hinnant756c69b2010-09-22 16:48:34 +0000575 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000576 bool operator()(const _CP& __x, const _CP& __y) const
Erik Pilkingtond3fe2992018-06-04 20:38:23 +0000577 {return comp(__x.__get_value().first, __y.__get_value().first);}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000578 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000579 bool operator()(const _CP& __x, const _Key& __y) const
Erik Pilkingtond3fe2992018-06-04 20:38:23 +0000580 {return comp(__x.__get_value().first, __y);}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000581 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000582 bool operator()(const _Key& __x, const _CP& __y) const
Erik Pilkingtond3fe2992018-06-04 20:38:23 +0000583 {return comp(__x, __y.__get_value().first);}
Marshall Clow8982dcd2015-07-13 20:04:56 +0000584 void swap(__map_value_compare&__y)
585 _NOEXCEPT_(__is_nothrow_swappable<_Compare>::value)
586 {
587 using _VSTD::swap;
588 swap(comp, __y.comp);
589 }
Eric Fiseliercf8c0212017-01-05 06:06:18 +0000590
Marshall Clowebb57322013-08-13 22:18:47 +0000591#if _LIBCPP_STD_VER > 11
592 template <typename _K2>
593 _LIBCPP_INLINE_VISIBILITY
594 typename enable_if<__is_transparent<_Compare, _K2>::value, bool>::type
595 operator () ( const _K2& __x, const _CP& __y ) const
Erik Pilkingtond3fe2992018-06-04 20:38:23 +0000596 {return comp (__x, __y.__get_value().first);}
Marshall Clowebb57322013-08-13 22:18:47 +0000597
598 template <typename _K2>
599 _LIBCPP_INLINE_VISIBILITY
600 typename enable_if<__is_transparent<_Compare, _K2>::value, bool>::type
601 operator () (const _CP& __x, const _K2& __y) const
Erik Pilkingtond3fe2992018-06-04 20:38:23 +0000602 {return comp (__x.__get_value().first, __y);}
Marshall Clowebb57322013-08-13 22:18:47 +0000603#endif
Howard Hinnantc51e1022010-05-11 19:42:16 +0000604};
605
Marshall Clow8982dcd2015-07-13 20:04:56 +0000606template <class _Key, class _CP, class _Compare, bool __b>
607inline _LIBCPP_INLINE_VISIBILITY
608void
609swap(__map_value_compare<_Key, _CP, _Compare, __b>& __x,
610 __map_value_compare<_Key, _CP, _Compare, __b>& __y)
611 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
612{
613 __x.swap(__y);
614}
615
Howard Hinnantc51e1022010-05-11 19:42:16 +0000616template <class _Allocator>
617class __map_node_destructor
618{
619 typedef _Allocator allocator_type;
620 typedef allocator_traits<allocator_type> __alloc_traits;
Eric Fiseliera00b4842016-02-20 05:28:30 +0000621
Howard Hinnantc51e1022010-05-11 19:42:16 +0000622public:
623 typedef typename __alloc_traits::pointer pointer;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000624
Eric Fiseliera00b4842016-02-20 05:28:30 +0000625private:
Howard Hinnantc51e1022010-05-11 19:42:16 +0000626 allocator_type& __na_;
627
628 __map_node_destructor& operator=(const __map_node_destructor&);
629
630public:
631 bool __first_constructed;
632 bool __second_constructed;
633
Howard Hinnant756c69b2010-09-22 16:48:34 +0000634 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000635 explicit __map_node_destructor(allocator_type& __na) _NOEXCEPT
Howard Hinnantc51e1022010-05-11 19:42:16 +0000636 : __na_(__na),
637 __first_constructed(false),
638 __second_constructed(false)
639 {}
640
Eric Fiseliera85b1282017-04-18 21:08:06 +0000641#ifndef _LIBCPP_CXX03_LANG
Howard Hinnant756c69b2010-09-22 16:48:34 +0000642 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000643 __map_node_destructor(__tree_node_destructor<allocator_type>&& __x) _NOEXCEPT
Howard Hinnantc51e1022010-05-11 19:42:16 +0000644 : __na_(__x.__na_),
645 __first_constructed(__x.__value_constructed),
646 __second_constructed(__x.__value_constructed)
647 {
648 __x.__value_constructed = false;
649 }
Louis Dionne2b1ceaa2021-04-20 12:03:32 -0400650#endif // _LIBCPP_CXX03_LANG
Howard Hinnantc51e1022010-05-11 19:42:16 +0000651
Howard Hinnant756c69b2010-09-22 16:48:34 +0000652 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000653 void operator()(pointer __p) _NOEXCEPT
Howard Hinnantc51e1022010-05-11 19:42:16 +0000654 {
655 if (__second_constructed)
Erik Pilkingtond3fe2992018-06-04 20:38:23 +0000656 __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.__get_value().second));
Howard Hinnantc51e1022010-05-11 19:42:16 +0000657 if (__first_constructed)
Erik Pilkingtond3fe2992018-06-04 20:38:23 +0000658 __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.__get_value().first));
Howard Hinnantc51e1022010-05-11 19:42:16 +0000659 if (__p)
660 __alloc_traits::deallocate(__na_, __p, 1);
661 }
662};
663
Howard Hinnant944510a2011-06-14 19:58:17 +0000664template <class _Key, class _Tp, class _Compare, class _Allocator>
665 class map;
666template <class _Key, class _Tp, class _Compare, class _Allocator>
667 class multimap;
668template <class _TreeIterator> class __map_const_iterator;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000669
Eric Fiseliera00b4842016-02-20 05:28:30 +0000670#ifndef _LIBCPP_CXX03_LANG
Howard Hinnant89f8b792013-09-30 19:08:22 +0000671
672template <class _Key, class _Tp>
Amy Huang63f53b52021-03-15 14:20:49 -0700673struct _LIBCPP_STANDALONE_DEBUG __value_type
Howard Hinnant89f8b792013-09-30 19:08:22 +0000674{
675 typedef _Key key_type;
676 typedef _Tp mapped_type;
677 typedef pair<const key_type, mapped_type> value_type;
Erik Pilkingtond3fe2992018-06-04 20:38:23 +0000678 typedef pair<key_type&, mapped_type&> __nc_ref_pair_type;
679 typedef pair<key_type&&, mapped_type&&> __nc_rref_pair_type;
Howard Hinnant89f8b792013-09-30 19:08:22 +0000680
Erik Pilkingtond3fe2992018-06-04 20:38:23 +0000681private:
Howard Hinnant89f8b792013-09-30 19:08:22 +0000682 value_type __cc;
Erik Pilkingtond3fe2992018-06-04 20:38:23 +0000683
684public:
685 _LIBCPP_INLINE_VISIBILITY
686 value_type& __get_value()
687 {
688#if _LIBCPP_STD_VER > 14
689 return *_VSTD::launder(_VSTD::addressof(__cc));
690#else
691 return __cc;
692#endif
693 }
694
695 _LIBCPP_INLINE_VISIBILITY
696 const value_type& __get_value() const
697 {
698#if _LIBCPP_STD_VER > 14
699 return *_VSTD::launder(_VSTD::addressof(__cc));
700#else
701 return __cc;
702#endif
703 }
704
705 _LIBCPP_INLINE_VISIBILITY
706 __nc_ref_pair_type __ref()
707 {
708 value_type& __v = __get_value();
709 return __nc_ref_pair_type(const_cast<key_type&>(__v.first), __v.second);
710 }
711
712 _LIBCPP_INLINE_VISIBILITY
713 __nc_rref_pair_type __move()
714 {
715 value_type& __v = __get_value();
716 return __nc_rref_pair_type(
717 _VSTD::move(const_cast<key_type&>(__v.first)),
718 _VSTD::move(__v.second));
719 }
Howard Hinnant89f8b792013-09-30 19:08:22 +0000720
Howard Hinnant89f8b792013-09-30 19:08:22 +0000721 _LIBCPP_INLINE_VISIBILITY
722 __value_type& operator=(const __value_type& __v)
Erik Pilkingtond3fe2992018-06-04 20:38:23 +0000723 {
724 __ref() = __v.__get_value();
725 return *this;
726 }
Howard Hinnant89f8b792013-09-30 19:08:22 +0000727
728 _LIBCPP_INLINE_VISIBILITY
729 __value_type& operator=(__value_type&& __v)
Erik Pilkingtond3fe2992018-06-04 20:38:23 +0000730 {
731 __ref() = __v.__move();
732 return *this;
733 }
Howard Hinnant89f8b792013-09-30 19:08:22 +0000734
Eric Fiselierd06276b2016-03-31 02:15:15 +0000735 template <class _ValueTp,
736 class = typename enable_if<
737 __is_same_uncvref<_ValueTp, value_type>::value
738 >::type
739 >
Howard Hinnant89f8b792013-09-30 19:08:22 +0000740 _LIBCPP_INLINE_VISIBILITY
Erik Pilkingtond3fe2992018-06-04 20:38:23 +0000741 __value_type& operator=(_ValueTp&& __v)
742 {
743 __ref() = _VSTD::forward<_ValueTp>(__v);
744 return *this;
Eric Fiselierd06276b2016-03-31 02:15:15 +0000745 }
746
747private:
748 __value_type() _LIBCPP_EQUAL_DELETE;
749 ~__value_type() _LIBCPP_EQUAL_DELETE;
750 __value_type(const __value_type& __v) _LIBCPP_EQUAL_DELETE;
751 __value_type(__value_type&& __v) _LIBCPP_EQUAL_DELETE;
Howard Hinnant89f8b792013-09-30 19:08:22 +0000752};
753
754#else
755
756template <class _Key, class _Tp>
757struct __value_type
758{
759 typedef _Key key_type;
760 typedef _Tp mapped_type;
761 typedef pair<const key_type, mapped_type> value_type;
762
Erik Pilkingtond3fe2992018-06-04 20:38:23 +0000763private:
Howard Hinnant89f8b792013-09-30 19:08:22 +0000764 value_type __cc;
765
Erik Pilkingtond3fe2992018-06-04 20:38:23 +0000766public:
767 _LIBCPP_INLINE_VISIBILITY
768 value_type& __get_value() { return __cc; }
769 _LIBCPP_INLINE_VISIBILITY
770 const value_type& __get_value() const { return __cc; }
771
Eric Fiselierd06276b2016-03-31 02:15:15 +0000772private:
773 __value_type();
774 __value_type(__value_type const&);
775 __value_type& operator=(__value_type const&);
776 ~__value_type();
Howard Hinnant89f8b792013-09-30 19:08:22 +0000777};
778
Eric Fiseliera85b1282017-04-18 21:08:06 +0000779#endif // _LIBCPP_CXX03_LANG
Howard Hinnant89f8b792013-09-30 19:08:22 +0000780
Eric Fiselier44f9fd02015-03-03 20:10:01 +0000781template <class _Tp>
782struct __extract_key_value_types;
783
784template <class _Key, class _Tp>
785struct __extract_key_value_types<__value_type<_Key, _Tp> >
786{
787 typedef _Key const __key_type;
788 typedef _Tp __mapped_type;
789};
790
Howard Hinnantc51e1022010-05-11 19:42:16 +0000791template <class _TreeIterator>
Eric Fiselierb5eb1bf2017-01-04 23:56:00 +0000792class _LIBCPP_TEMPLATE_VIS __map_iterator
Howard Hinnantc51e1022010-05-11 19:42:16 +0000793{
Eric Fiseliera00b4842016-02-20 05:28:30 +0000794 typedef typename _TreeIterator::_NodeTypes _NodeTypes;
795 typedef typename _TreeIterator::__pointer_traits __pointer_traits;
796
Howard Hinnantc51e1022010-05-11 19:42:16 +0000797 _TreeIterator __i_;
798
Howard Hinnantc51e1022010-05-11 19:42:16 +0000799public:
800 typedef bidirectional_iterator_tag iterator_category;
Eric Fiseliera00b4842016-02-20 05:28:30 +0000801 typedef typename _NodeTypes::__map_value_type value_type;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000802 typedef typename _TreeIterator::difference_type difference_type;
803 typedef value_type& reference;
Eric Fiseliera00b4842016-02-20 05:28:30 +0000804 typedef typename _NodeTypes::__map_value_type_pointer pointer;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000805
Howard Hinnant756c69b2010-09-22 16:48:34 +0000806 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000807 __map_iterator() _NOEXCEPT {}
Howard Hinnantc51e1022010-05-11 19:42:16 +0000808
Howard Hinnant756c69b2010-09-22 16:48:34 +0000809 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000810 __map_iterator(_TreeIterator __i) _NOEXCEPT : __i_(__i) {}
Howard Hinnantc51e1022010-05-11 19:42:16 +0000811
Howard Hinnant756c69b2010-09-22 16:48:34 +0000812 _LIBCPP_INLINE_VISIBILITY
Erik Pilkingtond3fe2992018-06-04 20:38:23 +0000813 reference operator*() const {return __i_->__get_value();}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000814 _LIBCPP_INLINE_VISIBILITY
Erik Pilkingtond3fe2992018-06-04 20:38:23 +0000815 pointer operator->() const {return pointer_traits<pointer>::pointer_to(__i_->__get_value());}
Howard Hinnantc51e1022010-05-11 19:42:16 +0000816
Howard Hinnant756c69b2010-09-22 16:48:34 +0000817 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000818 __map_iterator& operator++() {++__i_; return *this;}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000819 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000820 __map_iterator operator++(int)
821 {
822 __map_iterator __t(*this);
823 ++(*this);
824 return __t;
825 }
826
Howard Hinnant756c69b2010-09-22 16:48:34 +0000827 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000828 __map_iterator& operator--() {--__i_; return *this;}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000829 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000830 __map_iterator operator--(int)
831 {
832 __map_iterator __t(*this);
833 --(*this);
834 return __t;
835 }
836
Howard Hinnant756c69b2010-09-22 16:48:34 +0000837 friend _LIBCPP_INLINE_VISIBILITY
838 bool operator==(const __map_iterator& __x, const __map_iterator& __y)
Howard Hinnantc51e1022010-05-11 19:42:16 +0000839 {return __x.__i_ == __y.__i_;}
Eric Fiseliercf8c0212017-01-05 06:06:18 +0000840 friend
Howard Hinnant756c69b2010-09-22 16:48:34 +0000841 _LIBCPP_INLINE_VISIBILITY
842 bool operator!=(const __map_iterator& __x, const __map_iterator& __y)
Howard Hinnantc51e1022010-05-11 19:42:16 +0000843 {return __x.__i_ != __y.__i_;}
844
Eric Fiselierb5eb1bf2017-01-04 23:56:00 +0000845 template <class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS map;
846 template <class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS multimap;
847 template <class> friend class _LIBCPP_TEMPLATE_VIS __map_const_iterator;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000848};
849
850template <class _TreeIterator>
Eric Fiselierb5eb1bf2017-01-04 23:56:00 +0000851class _LIBCPP_TEMPLATE_VIS __map_const_iterator
Howard Hinnantc51e1022010-05-11 19:42:16 +0000852{
Eric Fiseliera00b4842016-02-20 05:28:30 +0000853 typedef typename _TreeIterator::_NodeTypes _NodeTypes;
854 typedef typename _TreeIterator::__pointer_traits __pointer_traits;
855
Howard Hinnantc51e1022010-05-11 19:42:16 +0000856 _TreeIterator __i_;
857
Howard Hinnantc51e1022010-05-11 19:42:16 +0000858public:
859 typedef bidirectional_iterator_tag iterator_category;
Eric Fiseliera00b4842016-02-20 05:28:30 +0000860 typedef typename _NodeTypes::__map_value_type value_type;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000861 typedef typename _TreeIterator::difference_type difference_type;
862 typedef const value_type& reference;
Eric Fiseliera00b4842016-02-20 05:28:30 +0000863 typedef typename _NodeTypes::__const_map_value_type_pointer pointer;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000864
Howard Hinnant756c69b2010-09-22 16:48:34 +0000865 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000866 __map_const_iterator() _NOEXCEPT {}
Howard Hinnantc51e1022010-05-11 19:42:16 +0000867
Howard Hinnant756c69b2010-09-22 16:48:34 +0000868 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000869 __map_const_iterator(_TreeIterator __i) _NOEXCEPT : __i_(__i) {}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000870 _LIBCPP_INLINE_VISIBILITY
Eric Fiselier44f9fd02015-03-03 20:10:01 +0000871 __map_const_iterator(__map_iterator<
872 typename _TreeIterator::__non_const_iterator> __i) _NOEXCEPT
873 : __i_(__i.__i_) {}
Howard Hinnantc51e1022010-05-11 19:42:16 +0000874
Howard Hinnant756c69b2010-09-22 16:48:34 +0000875 _LIBCPP_INLINE_VISIBILITY
Erik Pilkingtond3fe2992018-06-04 20:38:23 +0000876 reference operator*() const {return __i_->__get_value();}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000877 _LIBCPP_INLINE_VISIBILITY
Erik Pilkingtond3fe2992018-06-04 20:38:23 +0000878 pointer operator->() const {return pointer_traits<pointer>::pointer_to(__i_->__get_value());}
Howard Hinnantc51e1022010-05-11 19:42:16 +0000879
Howard Hinnant756c69b2010-09-22 16:48:34 +0000880 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000881 __map_const_iterator& operator++() {++__i_; return *this;}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000882 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000883 __map_const_iterator operator++(int)
884 {
885 __map_const_iterator __t(*this);
886 ++(*this);
887 return __t;
888 }
889
Howard Hinnant756c69b2010-09-22 16:48:34 +0000890 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000891 __map_const_iterator& operator--() {--__i_; return *this;}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000892 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000893 __map_const_iterator operator--(int)
894 {
895 __map_const_iterator __t(*this);
896 --(*this);
897 return __t;
898 }
899
Howard Hinnant756c69b2010-09-22 16:48:34 +0000900 friend _LIBCPP_INLINE_VISIBILITY
901 bool operator==(const __map_const_iterator& __x, const __map_const_iterator& __y)
Howard Hinnantc51e1022010-05-11 19:42:16 +0000902 {return __x.__i_ == __y.__i_;}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000903 friend _LIBCPP_INLINE_VISIBILITY
904 bool operator!=(const __map_const_iterator& __x, const __map_const_iterator& __y)
Howard Hinnantc51e1022010-05-11 19:42:16 +0000905 {return __x.__i_ != __y.__i_;}
906
Eric Fiselierb5eb1bf2017-01-04 23:56:00 +0000907 template <class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS map;
908 template <class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS multimap;
909 template <class, class, class> friend class _LIBCPP_TEMPLATE_VIS __tree_const_iterator;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000910};
911
912template <class _Key, class _Tp, class _Compare = less<_Key>,
913 class _Allocator = allocator<pair<const _Key, _Tp> > >
Eric Fiselierb5eb1bf2017-01-04 23:56:00 +0000914class _LIBCPP_TEMPLATE_VIS map
Howard Hinnantc51e1022010-05-11 19:42:16 +0000915{
916public:
917 // types:
918 typedef _Key key_type;
919 typedef _Tp mapped_type;
920 typedef pair<const key_type, mapped_type> value_type;
Arthur O'Dwyer6a752e12021-03-03 11:10:49 -0500921 typedef __identity_t<_Compare> key_compare;
922 typedef __identity_t<_Allocator> allocator_type;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000923 typedef value_type& reference;
924 typedef const value_type& const_reference;
925
Marshall Clow5128cf32015-11-26 01:24:04 +0000926 static_assert((is_same<typename allocator_type::value_type, value_type>::value),
927 "Allocator::value_type must be same type as value_type");
928
Arthur O'Dwyerf5486c82021-05-25 14:34:18 -0400929_LIBCPP_SUPPRESS_DEPRECATED_PUSH
Eric Fiselierb5eb1bf2017-01-04 23:56:00 +0000930 class _LIBCPP_TEMPLATE_VIS value_compare
Arthur O'Dwyerf5486c82021-05-25 14:34:18 -0400931#if defined(_LIBCPP_ENABLE_CXX20_REMOVED_BINDER_TYPEDEFS)
Howard Hinnantc51e1022010-05-11 19:42:16 +0000932 : public binary_function<value_type, value_type, bool>
Arthur O'Dwyerf5486c82021-05-25 14:34:18 -0400933#endif
Howard Hinnantc51e1022010-05-11 19:42:16 +0000934 {
Arthur O'Dwyerf5486c82021-05-25 14:34:18 -0400935_LIBCPP_SUPPRESS_DEPRECATED_POP
Howard Hinnantc51e1022010-05-11 19:42:16 +0000936 friend class map;
937 protected:
938 key_compare comp;
939
Howard Hinnant756c69b2010-09-22 16:48:34 +0000940 _LIBCPP_INLINE_VISIBILITY value_compare(key_compare c) : comp(c) {}
Howard Hinnantc51e1022010-05-11 19:42:16 +0000941 public:
Arthur O'Dwyerf5486c82021-05-25 14:34:18 -0400942#if _LIBCPP_STD_VER <= 17 || defined(_LIBCPP_ENABLE_CXX20_REMOVED_BINDER_TYPEDEFS)
943 _LIBCPP_DEPRECATED_IN_CXX17 typedef bool result_type;
944 _LIBCPP_DEPRECATED_IN_CXX17 typedef value_type first_argument_type;
945 _LIBCPP_DEPRECATED_IN_CXX17 typedef value_type second_argument_type;
946#endif
Howard Hinnant756c69b2010-09-22 16:48:34 +0000947 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000948 bool operator()(const value_type& __x, const value_type& __y) const
949 {return comp(__x.first, __y.first);}
950 };
951
952private:
Howard Hinnant2d0046b2013-06-19 21:29:40 +0000953
Howard Hinnant89f8b792013-09-30 19:08:22 +0000954 typedef _VSTD::__value_type<key_type, mapped_type> __value_type;
Howard Hinnant90b91592013-07-05 18:06:00 +0000955 typedef __map_value_compare<key_type, __value_type, key_compare> __vc;
Marshall Clow940e01c2015-04-07 05:21:38 +0000956 typedef typename __rebind_alloc_helper<allocator_traits<allocator_type>,
957 __value_type>::type __allocator_type;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000958 typedef __tree<__value_type, __vc, __allocator_type> __base;
959 typedef typename __base::__node_traits __node_traits;
960 typedef allocator_traits<allocator_type> __alloc_traits;
961
962 __base __tree_;
963
964public:
965 typedef typename __alloc_traits::pointer pointer;
966 typedef typename __alloc_traits::const_pointer const_pointer;
967 typedef typename __alloc_traits::size_type size_type;
968 typedef typename __alloc_traits::difference_type difference_type;
Eric Fiselier44f9fd02015-03-03 20:10:01 +0000969 typedef __map_iterator<typename __base::iterator> iterator;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000970 typedef __map_const_iterator<typename __base::const_iterator> const_iterator;
Howard Hinnantb1ad5a82011-06-30 21:18:19 +0000971 typedef _VSTD::reverse_iterator<iterator> reverse_iterator;
972 typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000973
Erik Pilkingtonc37a3d82018-08-01 01:33:38 +0000974#if _LIBCPP_STD_VER > 14
975 typedef __map_node_handle<typename __base::__node, allocator_type> node_type;
976 typedef __insert_return_type<iterator, node_type> insert_return_type;
977#endif
978
Erik Pilkington82a65ad2018-10-31 17:31:35 +0000979 template <class _Key2, class _Value2, class _Comp2, class _Alloc2>
980 friend class _LIBCPP_TEMPLATE_VIS map;
981 template <class _Key2, class _Value2, class _Comp2, class _Alloc2>
982 friend class _LIBCPP_TEMPLATE_VIS multimap;
983
Howard Hinnant756c69b2010-09-22 16:48:34 +0000984 _LIBCPP_INLINE_VISIBILITY
Marshall Clow7086a5a2014-03-10 04:50:10 +0000985 map()
986 _NOEXCEPT_(
987 is_nothrow_default_constructible<allocator_type>::value &&
988 is_nothrow_default_constructible<key_compare>::value &&
989 is_nothrow_copy_constructible<key_compare>::value)
990 : __tree_(__vc(key_compare())) {}
991
992 _LIBCPP_INLINE_VISIBILITY
993 explicit map(const key_compare& __comp)
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000994 _NOEXCEPT_(
995 is_nothrow_default_constructible<allocator_type>::value &&
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000996 is_nothrow_copy_constructible<key_compare>::value)
Howard Hinnantc51e1022010-05-11 19:42:16 +0000997 : __tree_(__vc(__comp)) {}
998
Howard Hinnant756c69b2010-09-22 16:48:34 +0000999 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001000 explicit map(const key_compare& __comp, const allocator_type& __a)
Marshall Clow657cbc42016-08-17 05:58:40 +00001001 : __tree_(__vc(__comp), typename __base::allocator_type(__a)) {}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001002
1003 template <class _InputIterator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001004 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001005 map(_InputIterator __f, _InputIterator __l,
1006 const key_compare& __comp = key_compare())
1007 : __tree_(__vc(__comp))
1008 {
1009 insert(__f, __l);
1010 }
1011
1012 template <class _InputIterator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001013 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001014 map(_InputIterator __f, _InputIterator __l,
1015 const key_compare& __comp, const allocator_type& __a)
Marshall Clow657cbc42016-08-17 05:58:40 +00001016 : __tree_(__vc(__comp), typename __base::allocator_type(__a))
Howard Hinnantc51e1022010-05-11 19:42:16 +00001017 {
1018 insert(__f, __l);
1019 }
1020
Marshall Clow300abfb2013-09-11 01:15:47 +00001021#if _LIBCPP_STD_VER > 11
1022 template <class _InputIterator>
Eric Fiseliercf8c0212017-01-05 06:06:18 +00001023 _LIBCPP_INLINE_VISIBILITY
Marshall Clow300abfb2013-09-11 01:15:47 +00001024 map(_InputIterator __f, _InputIterator __l, const allocator_type& __a)
1025 : map(__f, __l, key_compare(), __a) {}
1026#endif
1027
Howard Hinnant756c69b2010-09-22 16:48:34 +00001028 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001029 map(const map& __m)
1030 : __tree_(__m.__tree_)
1031 {
1032 insert(__m.begin(), __m.end());
1033 }
1034
Howard Hinnantd3a657f2011-07-01 19:24:36 +00001035 _LIBCPP_INLINE_VISIBILITY
1036 map& operator=(const map& __m)
1037 {
Marshall Clow476d3f42016-07-18 13:19:00 +00001038#ifndef _LIBCPP_CXX03_LANG
Howard Hinnantd3a657f2011-07-01 19:24:36 +00001039 __tree_ = __m.__tree_;
Howard Hinnant2d0046b2013-06-19 21:29:40 +00001040#else
Marshall Clowdb3cfcb2014-02-08 04:03:14 +00001041 if (this != &__m) {
1042 __tree_.clear();
1043 __tree_.value_comp() = __m.__tree_.value_comp();
1044 __tree_.__copy_assign_alloc(__m.__tree_);
1045 insert(__m.begin(), __m.end());
1046 }
Howard Hinnant2d0046b2013-06-19 21:29:40 +00001047#endif
Howard Hinnantd3a657f2011-07-01 19:24:36 +00001048 return *this;
1049 }
1050
Eric Fiseliera85b1282017-04-18 21:08:06 +00001051#ifndef _LIBCPP_CXX03_LANG
Howard Hinnantc51e1022010-05-11 19:42:16 +00001052
Howard Hinnant756c69b2010-09-22 16:48:34 +00001053 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001054 map(map&& __m)
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001055 _NOEXCEPT_(is_nothrow_move_constructible<__base>::value)
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001056 : __tree_(_VSTD::move(__m.__tree_))
Howard Hinnantc51e1022010-05-11 19:42:16 +00001057 {
1058 }
1059
1060 map(map&& __m, const allocator_type& __a);
1061
Howard Hinnant756c69b2010-09-22 16:48:34 +00001062 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant33711792011-08-12 21:56:02 +00001063 map& operator=(map&& __m)
1064 _NOEXCEPT_(is_nothrow_move_assignable<__base>::value)
1065 {
1066 __tree_ = _VSTD::move(__m.__tree_);
1067 return *this;
1068 }
1069
Howard Hinnant33711792011-08-12 21:56:02 +00001070 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001071 map(initializer_list<value_type> __il, const key_compare& __comp = key_compare())
1072 : __tree_(__vc(__comp))
1073 {
1074 insert(__il.begin(), __il.end());
1075 }
1076
Howard Hinnant756c69b2010-09-22 16:48:34 +00001077 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001078 map(initializer_list<value_type> __il, const key_compare& __comp, const allocator_type& __a)
Marshall Clow657cbc42016-08-17 05:58:40 +00001079 : __tree_(__vc(__comp), typename __base::allocator_type(__a))
Howard Hinnantc51e1022010-05-11 19:42:16 +00001080 {
1081 insert(__il.begin(), __il.end());
1082 }
1083
Marshall Clow300abfb2013-09-11 01:15:47 +00001084#if _LIBCPP_STD_VER > 11
Eric Fiseliercf8c0212017-01-05 06:06:18 +00001085 _LIBCPP_INLINE_VISIBILITY
Marshall Clow300abfb2013-09-11 01:15:47 +00001086 map(initializer_list<value_type> __il, const allocator_type& __a)
1087 : map(__il, key_compare(), __a) {}
1088#endif
1089
Howard Hinnant756c69b2010-09-22 16:48:34 +00001090 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001091 map& operator=(initializer_list<value_type> __il)
1092 {
1093 __tree_.__assign_unique(__il.begin(), __il.end());
1094 return *this;
1095 }
1096
Louis Dionne2b1ceaa2021-04-20 12:03:32 -04001097#endif // _LIBCPP_CXX03_LANG
Howard Hinnantc51e1022010-05-11 19:42:16 +00001098
Howard Hinnant756c69b2010-09-22 16:48:34 +00001099 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001100 explicit map(const allocator_type& __a)
Marshall Clow657cbc42016-08-17 05:58:40 +00001101 : __tree_(typename __base::allocator_type(__a))
Howard Hinnantc51e1022010-05-11 19:42:16 +00001102 {
1103 }
1104
Howard Hinnant756c69b2010-09-22 16:48:34 +00001105 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001106 map(const map& __m, const allocator_type& __a)
Marshall Clow657cbc42016-08-17 05:58:40 +00001107 : __tree_(__m.__tree_.value_comp(), typename __base::allocator_type(__a))
Howard Hinnantc51e1022010-05-11 19:42:16 +00001108 {
1109 insert(__m.begin(), __m.end());
1110 }
1111
Howard Hinnant756c69b2010-09-22 16:48:34 +00001112 _LIBCPP_INLINE_VISIBILITY
Louis Dionne69c42c02019-04-11 16:14:56 +00001113 ~map() {
1114 static_assert(sizeof(__diagnose_non_const_comparator<_Key, _Compare>()), "");
1115 }
1116
1117 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001118 iterator begin() _NOEXCEPT {return __tree_.begin();}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001119 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001120 const_iterator begin() const _NOEXCEPT {return __tree_.begin();}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001121 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001122 iterator end() _NOEXCEPT {return __tree_.end();}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001123 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001124 const_iterator end() const _NOEXCEPT {return __tree_.end();}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001125
Howard Hinnant756c69b2010-09-22 16:48:34 +00001126 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001127 reverse_iterator rbegin() _NOEXCEPT {return reverse_iterator(end());}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001128 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001129 const_reverse_iterator rbegin() const _NOEXCEPT
1130 {return const_reverse_iterator(end());}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001131 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001132 reverse_iterator rend() _NOEXCEPT
1133 {return reverse_iterator(begin());}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001134 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001135 const_reverse_iterator rend() const _NOEXCEPT
1136 {return const_reverse_iterator(begin());}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001137
Howard Hinnant756c69b2010-09-22 16:48:34 +00001138 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001139 const_iterator cbegin() const _NOEXCEPT {return begin();}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001140 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001141 const_iterator cend() const _NOEXCEPT {return end();}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001142 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001143 const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001144 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001145 const_reverse_iterator crend() const _NOEXCEPT {return rend();}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001146
Marshall Clow425f5752017-11-15 05:51:26 +00001147 _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001148 bool empty() const _NOEXCEPT {return __tree_.size() == 0;}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001149 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001150 size_type size() const _NOEXCEPT {return __tree_.size();}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001151 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001152 size_type max_size() const _NOEXCEPT {return __tree_.max_size();}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001153
1154 mapped_type& operator[](const key_type& __k);
Eric Fiselierd63f38e2016-03-31 03:13:37 +00001155#ifndef _LIBCPP_CXX03_LANG
Howard Hinnantc51e1022010-05-11 19:42:16 +00001156 mapped_type& operator[](key_type&& __k);
1157#endif
1158
1159 mapped_type& at(const key_type& __k);
1160 const mapped_type& at(const key_type& __k) const;
1161
Howard Hinnant756c69b2010-09-22 16:48:34 +00001162 _LIBCPP_INLINE_VISIBILITY
Marshall Clow657cbc42016-08-17 05:58:40 +00001163 allocator_type get_allocator() const _NOEXCEPT {return allocator_type(__tree_.__alloc());}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001164 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001165 key_compare key_comp() const {return __tree_.value_comp().key_comp();}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001166 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001167 value_compare value_comp() const {return value_compare(__tree_.value_comp().key_comp());}
1168
Eric Fiselierd06276b2016-03-31 02:15:15 +00001169#ifndef _LIBCPP_CXX03_LANG
1170 template <class ..._Args>
1171 _LIBCPP_INLINE_VISIBILITY
1172 pair<iterator, bool> emplace(_Args&& ...__args) {
1173 return __tree_.__emplace_unique(_VSTD::forward<_Args>(__args)...);
1174 }
Howard Hinnant74279a52010-09-04 23:28:19 +00001175
Howard Hinnant29eb9b82012-05-25 22:04:21 +00001176 template <class ..._Args>
Eric Fiselierd06276b2016-03-31 02:15:15 +00001177 _LIBCPP_INLINE_VISIBILITY
1178 iterator emplace_hint(const_iterator __p, _Args&& ...__args) {
1179 return __tree_.__emplace_hint_unique(__p.__i_, _VSTD::forward<_Args>(__args)...);
1180 }
Howard Hinnant74279a52010-09-04 23:28:19 +00001181
Howard Hinnantc834c512011-11-29 18:15:50 +00001182 template <class _Pp,
1183 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001184 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc834c512011-11-29 18:15:50 +00001185 pair<iterator, bool> insert(_Pp&& __p)
1186 {return __tree_.__insert_unique(_VSTD::forward<_Pp>(__p));}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001187
Howard Hinnantc834c512011-11-29 18:15:50 +00001188 template <class _Pp,
1189 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001190 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc834c512011-11-29 18:15:50 +00001191 iterator insert(const_iterator __pos, _Pp&& __p)
1192 {return __tree_.__insert_unique(__pos.__i_, _VSTD::forward<_Pp>(__p));}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001193
Louis Dionne2b1ceaa2021-04-20 12:03:32 -04001194#endif // _LIBCPP_CXX03_LANG
Howard Hinnantc51e1022010-05-11 19:42:16 +00001195
Howard Hinnant756c69b2010-09-22 16:48:34 +00001196 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001197 pair<iterator, bool>
1198 insert(const value_type& __v) {return __tree_.__insert_unique(__v);}
1199
Howard Hinnant756c69b2010-09-22 16:48:34 +00001200 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001201 iterator
1202 insert(const_iterator __p, const value_type& __v)
1203 {return __tree_.__insert_unique(__p.__i_, __v);}
1204
Eric Fiselierd6143132016-04-18 01:40:45 +00001205#ifndef _LIBCPP_CXX03_LANG
Marshall Clowd430d022016-01-05 19:32:41 +00001206 _LIBCPP_INLINE_VISIBILITY
1207 pair<iterator, bool>
Eric Fiselierd06276b2016-03-31 02:15:15 +00001208 insert(value_type&& __v) {return __tree_.__insert_unique(_VSTD::move(__v));}
Marshall Clowd430d022016-01-05 19:32:41 +00001209
1210 _LIBCPP_INLINE_VISIBILITY
Eric Fiselierd06276b2016-03-31 02:15:15 +00001211 iterator insert(const_iterator __p, value_type&& __v)
1212 {return __tree_.__insert_unique(__p.__i_, _VSTD::move(__v));}
Eric Fiseliera85b1282017-04-18 21:08:06 +00001213
1214 _LIBCPP_INLINE_VISIBILITY
1215 void insert(initializer_list<value_type> __il)
1216 {insert(__il.begin(), __il.end());}
Marshall Clowd430d022016-01-05 19:32:41 +00001217#endif
1218
Howard Hinnantc51e1022010-05-11 19:42:16 +00001219 template <class _InputIterator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001220 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001221 void insert(_InputIterator __f, _InputIterator __l)
1222 {
1223 for (const_iterator __e = cend(); __f != __l; ++__f)
1224 insert(__e.__i_, *__f);
1225 }
1226
Marshall Clow3223db82015-07-07 03:37:33 +00001227#if _LIBCPP_STD_VER > 14
Eric Fiselierd63f38e2016-03-31 03:13:37 +00001228
Marshall Clow3223db82015-07-07 03:37:33 +00001229 template <class... _Args>
1230 _LIBCPP_INLINE_VISIBILITY
1231 pair<iterator, bool> try_emplace(const key_type& __k, _Args&&... __args)
1232 {
Eric Fiselierd63f38e2016-03-31 03:13:37 +00001233 return __tree_.__emplace_unique_key_args(__k,
1234 _VSTD::piecewise_construct,
1235 _VSTD::forward_as_tuple(__k),
1236 _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...));
Marshall Clow3223db82015-07-07 03:37:33 +00001237 }
1238
1239 template <class... _Args>
1240 _LIBCPP_INLINE_VISIBILITY
1241 pair<iterator, bool> try_emplace(key_type&& __k, _Args&&... __args)
1242 {
Eric Fiselierd63f38e2016-03-31 03:13:37 +00001243 return __tree_.__emplace_unique_key_args(__k,
1244 _VSTD::piecewise_construct,
1245 _VSTD::forward_as_tuple(_VSTD::move(__k)),
1246 _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...));
Marshall Clow3223db82015-07-07 03:37:33 +00001247 }
1248
1249 template <class... _Args>
1250 _LIBCPP_INLINE_VISIBILITY
1251 iterator try_emplace(const_iterator __h, const key_type& __k, _Args&&... __args)
1252 {
Eric Fiselierd63f38e2016-03-31 03:13:37 +00001253 return __tree_.__emplace_hint_unique_key_args(__h.__i_, __k,
1254 _VSTD::piecewise_construct,
1255 _VSTD::forward_as_tuple(__k),
Mark de Wever1ba476f2020-09-19 15:39:09 +02001256 _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...)).first;
Marshall Clow3223db82015-07-07 03:37:33 +00001257 }
1258
1259 template <class... _Args>
1260 _LIBCPP_INLINE_VISIBILITY
1261 iterator try_emplace(const_iterator __h, key_type&& __k, _Args&&... __args)
1262 {
Eric Fiselierd63f38e2016-03-31 03:13:37 +00001263 return __tree_.__emplace_hint_unique_key_args(__h.__i_, __k,
1264 _VSTD::piecewise_construct,
1265 _VSTD::forward_as_tuple(_VSTD::move(__k)),
Mark de Wever1ba476f2020-09-19 15:39:09 +02001266 _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...)).first;
Marshall Clow3223db82015-07-07 03:37:33 +00001267 }
1268
1269 template <class _Vp>
1270 _LIBCPP_INLINE_VISIBILITY
1271 pair<iterator, bool> insert_or_assign(const key_type& __k, _Vp&& __v)
1272 {
1273 iterator __p = lower_bound(__k);
1274 if ( __p != end() && !key_comp()(__k, __p->first))
1275 {
1276 __p->second = _VSTD::forward<_Vp>(__v);
1277 return _VSTD::make_pair(__p, false);
1278 }
1279 return _VSTD::make_pair(emplace_hint(__p, __k, _VSTD::forward<_Vp>(__v)), true);
1280 }
Eric Fiselierd63f38e2016-03-31 03:13:37 +00001281
Marshall Clow3223db82015-07-07 03:37:33 +00001282 template <class _Vp>
1283 _LIBCPP_INLINE_VISIBILITY
1284 pair<iterator, bool> insert_or_assign(key_type&& __k, _Vp&& __v)
1285 {
1286 iterator __p = lower_bound(__k);
1287 if ( __p != end() && !key_comp()(__k, __p->first))
1288 {
1289 __p->second = _VSTD::forward<_Vp>(__v);
1290 return _VSTD::make_pair(__p, false);
1291 }
1292 return _VSTD::make_pair(emplace_hint(__p, _VSTD::move(__k), _VSTD::forward<_Vp>(__v)), true);
1293 }
1294
1295 template <class _Vp>
Mark de Wever1ba476f2020-09-19 15:39:09 +02001296 _LIBCPP_INLINE_VISIBILITY iterator insert_or_assign(const_iterator __h,
1297 const key_type& __k,
1298 _Vp&& __v) {
1299 auto [__r, __inserted] = __tree_.__emplace_hint_unique_key_args(
1300 __h.__i_, __k, __k, _VSTD::forward<_Vp>(__v));
1301
1302 if (!__inserted)
1303 __r->__get_value().second = _VSTD::forward<_Vp>(__v);
1304
1305 return __r;
1306 }
Marshall Clow3223db82015-07-07 03:37:33 +00001307
1308 template <class _Vp>
Mark de Wever1ba476f2020-09-19 15:39:09 +02001309 _LIBCPP_INLINE_VISIBILITY iterator insert_or_assign(const_iterator __h,
1310 key_type&& __k,
1311 _Vp&& __v) {
1312 auto [__r, __inserted] = __tree_.__emplace_hint_unique_key_args(
1313 __h.__i_, __k, _VSTD::move(__k), _VSTD::forward<_Vp>(__v));
1314
1315 if (!__inserted)
1316 __r->__get_value().second = _VSTD::forward<_Vp>(__v);
1317
1318 return __r;
1319 }
Eric Fiselierd63f38e2016-03-31 03:13:37 +00001320
Eric Fiseliera85b1282017-04-18 21:08:06 +00001321#endif // _LIBCPP_STD_VER > 14
Marshall Clow3223db82015-07-07 03:37:33 +00001322
Howard Hinnant756c69b2010-09-22 16:48:34 +00001323 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001324 iterator erase(const_iterator __p) {return __tree_.erase(__p.__i_);}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001325 _LIBCPP_INLINE_VISIBILITY
Marshall Clow22ea5b82015-05-10 13:35:00 +00001326 iterator erase(iterator __p) {return __tree_.erase(__p.__i_);}
1327 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001328 size_type erase(const key_type& __k)
1329 {return __tree_.__erase_unique(__k);}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001330 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001331 iterator erase(const_iterator __f, const_iterator __l)
1332 {return __tree_.erase(__f.__i_, __l.__i_);}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001333 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001334 void clear() _NOEXCEPT {__tree_.clear();}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001335
Erik Pilkingtonc37a3d82018-08-01 01:33:38 +00001336#if _LIBCPP_STD_VER > 14
1337 _LIBCPP_INLINE_VISIBILITY
1338 insert_return_type insert(node_type&& __nh)
1339 {
1340 _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(),
1341 "node_type with incompatible allocator passed to map::insert()");
1342 return __tree_.template __node_handle_insert_unique<
1343 node_type, insert_return_type>(_VSTD::move(__nh));
1344 }
1345 _LIBCPP_INLINE_VISIBILITY
1346 iterator insert(const_iterator __hint, node_type&& __nh)
1347 {
1348 _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(),
1349 "node_type with incompatible allocator passed to map::insert()");
1350 return __tree_.template __node_handle_insert_unique<node_type>(
1351 __hint.__i_, _VSTD::move(__nh));
1352 }
1353 _LIBCPP_INLINE_VISIBILITY
1354 node_type extract(key_type const& __key)
1355 {
1356 return __tree_.template __node_handle_extract<node_type>(__key);
1357 }
1358 _LIBCPP_INLINE_VISIBILITY
1359 node_type extract(const_iterator __it)
1360 {
1361 return __tree_.template __node_handle_extract<node_type>(__it.__i_);
1362 }
Louis Dionned2322c82018-11-01 14:41:37 +00001363 template <class _Compare2>
Erik Pilkington82a65ad2018-10-31 17:31:35 +00001364 _LIBCPP_INLINE_VISIBILITY
Louis Dionned2322c82018-11-01 14:41:37 +00001365 void merge(map<key_type, mapped_type, _Compare2, allocator_type>& __source)
Erik Pilkington82a65ad2018-10-31 17:31:35 +00001366 {
1367 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
1368 "merging container with incompatible allocator");
1369 __tree_.__node_handle_merge_unique(__source.__tree_);
1370 }
Louis Dionned2322c82018-11-01 14:41:37 +00001371 template <class _Compare2>
Erik Pilkington82a65ad2018-10-31 17:31:35 +00001372 _LIBCPP_INLINE_VISIBILITY
Louis Dionned2322c82018-11-01 14:41:37 +00001373 void merge(map<key_type, mapped_type, _Compare2, allocator_type>&& __source)
Erik Pilkington82a65ad2018-10-31 17:31:35 +00001374 {
1375 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
1376 "merging container with incompatible allocator");
1377 __tree_.__node_handle_merge_unique(__source.__tree_);
1378 }
Louis Dionned2322c82018-11-01 14:41:37 +00001379 template <class _Compare2>
Erik Pilkington82a65ad2018-10-31 17:31:35 +00001380 _LIBCPP_INLINE_VISIBILITY
Louis Dionned2322c82018-11-01 14:41:37 +00001381 void merge(multimap<key_type, mapped_type, _Compare2, allocator_type>& __source)
Erik Pilkington82a65ad2018-10-31 17:31:35 +00001382 {
1383 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
1384 "merging container with incompatible allocator");
1385 __tree_.__node_handle_merge_unique(__source.__tree_);
1386 }
Louis Dionned2322c82018-11-01 14:41:37 +00001387 template <class _Compare2>
Erik Pilkington82a65ad2018-10-31 17:31:35 +00001388 _LIBCPP_INLINE_VISIBILITY
Louis Dionned2322c82018-11-01 14:41:37 +00001389 void merge(multimap<key_type, mapped_type, _Compare2, allocator_type>&& __source)
Erik Pilkington82a65ad2018-10-31 17:31:35 +00001390 {
1391 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
1392 "merging container with incompatible allocator");
1393 __tree_.__node_handle_merge_unique(__source.__tree_);
1394 }
Erik Pilkingtonc37a3d82018-08-01 01:33:38 +00001395#endif
1396
Howard Hinnant756c69b2010-09-22 16:48:34 +00001397 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001398 void swap(map& __m)
1399 _NOEXCEPT_(__is_nothrow_swappable<__base>::value)
1400 {__tree_.swap(__m.__tree_);}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001401
Howard Hinnant756c69b2010-09-22 16:48:34 +00001402 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001403 iterator find(const key_type& __k) {return __tree_.find(__k);}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001404 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001405 const_iterator find(const key_type& __k) const {return __tree_.find(__k);}
Marshall Clowebb57322013-08-13 22:18:47 +00001406#if _LIBCPP_STD_VER > 11
1407 template <typename _K2>
1408 _LIBCPP_INLINE_VISIBILITY
1409 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
1410 find(const _K2& __k) {return __tree_.find(__k);}
1411 template <typename _K2>
1412 _LIBCPP_INLINE_VISIBILITY
1413 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
1414 find(const _K2& __k) const {return __tree_.find(__k);}
1415#endif
1416
Howard Hinnant756c69b2010-09-22 16:48:34 +00001417 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001418 size_type count(const key_type& __k) const
1419 {return __tree_.__count_unique(__k);}
Marshall Clowe6a5f522014-08-24 23:54:16 +00001420#if _LIBCPP_STD_VER > 11
1421 template <typename _K2>
1422 _LIBCPP_INLINE_VISIBILITY
1423 typename enable_if<__is_transparent<_Compare, _K2>::value,size_type>::type
Eric Fiseliera85c9e92018-02-10 02:53:47 +00001424 count(const _K2& __k) const {return __tree_.__count_multi(__k);}
Marshall Clowe6a5f522014-08-24 23:54:16 +00001425#endif
Zoe Carver3ffbab12019-07-16 03:21:01 +00001426
1427#if _LIBCPP_STD_VER > 17
1428 _LIBCPP_INLINE_VISIBILITY
1429 bool contains(const key_type& __k) const {return find(__k) != end();}
Marek Kurdejd7e019e2021-04-13 17:10:55 +02001430 template <typename _K2>
1431 _LIBCPP_INLINE_VISIBILITY
1432 typename enable_if<__is_transparent<_Compare, _K2>::value, bool>::type
1433 contains(const _K2& __k) const { return find(__k) != end(); }
Zoe Carver3ffbab12019-07-16 03:21:01 +00001434#endif // _LIBCPP_STD_VER > 17
1435
Howard Hinnant756c69b2010-09-22 16:48:34 +00001436 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001437 iterator lower_bound(const key_type& __k)
1438 {return __tree_.lower_bound(__k);}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001439 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001440 const_iterator lower_bound(const key_type& __k) const
1441 {return __tree_.lower_bound(__k);}
Marshall Clowebb57322013-08-13 22:18:47 +00001442#if _LIBCPP_STD_VER > 11
1443 template <typename _K2>
1444 _LIBCPP_INLINE_VISIBILITY
1445 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
1446 lower_bound(const _K2& __k) {return __tree_.lower_bound(__k);}
1447
1448 template <typename _K2>
1449 _LIBCPP_INLINE_VISIBILITY
1450 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
1451 lower_bound(const _K2& __k) const {return __tree_.lower_bound(__k);}
1452#endif
1453
Howard Hinnant756c69b2010-09-22 16:48:34 +00001454 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001455 iterator upper_bound(const key_type& __k)
1456 {return __tree_.upper_bound(__k);}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001457 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001458 const_iterator upper_bound(const key_type& __k) const
1459 {return __tree_.upper_bound(__k);}
Marshall Clowebb57322013-08-13 22:18:47 +00001460#if _LIBCPP_STD_VER > 11
1461 template <typename _K2>
1462 _LIBCPP_INLINE_VISIBILITY
1463 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
1464 upper_bound(const _K2& __k) {return __tree_.upper_bound(__k);}
1465 template <typename _K2>
1466 _LIBCPP_INLINE_VISIBILITY
1467 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
1468 upper_bound(const _K2& __k) const {return __tree_.upper_bound(__k);}
1469#endif
1470
Howard Hinnant756c69b2010-09-22 16:48:34 +00001471 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001472 pair<iterator,iterator> equal_range(const key_type& __k)
1473 {return __tree_.__equal_range_unique(__k);}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001474 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001475 pair<const_iterator,const_iterator> equal_range(const key_type& __k) const
1476 {return __tree_.__equal_range_unique(__k);}
Marshall Clowebb57322013-08-13 22:18:47 +00001477#if _LIBCPP_STD_VER > 11
1478 template <typename _K2>
1479 _LIBCPP_INLINE_VISIBILITY
1480 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<iterator,iterator>>::type
Eric Fiseliera85c9e92018-02-10 02:53:47 +00001481 equal_range(const _K2& __k) {return __tree_.__equal_range_multi(__k);}
Marshall Clowebb57322013-08-13 22:18:47 +00001482 template <typename _K2>
1483 _LIBCPP_INLINE_VISIBILITY
1484 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<const_iterator,const_iterator>>::type
Eric Fiseliera85c9e92018-02-10 02:53:47 +00001485 equal_range(const _K2& __k) const {return __tree_.__equal_range_multi(__k);}
Marshall Clowebb57322013-08-13 22:18:47 +00001486#endif
Howard Hinnantc51e1022010-05-11 19:42:16 +00001487
1488private:
1489 typedef typename __base::__node __node;
1490 typedef typename __base::__node_allocator __node_allocator;
1491 typedef typename __base::__node_pointer __node_pointer;
Howard Hinnantc51e1022010-05-11 19:42:16 +00001492 typedef typename __base::__node_base_pointer __node_base_pointer;
Eric Fiseliercf8c0212017-01-05 06:06:18 +00001493 typedef typename __base::__parent_pointer __parent_pointer;
Eric Fiseliera92b0732016-02-20 07:12:17 +00001494
Howard Hinnantc834c512011-11-29 18:15:50 +00001495 typedef __map_node_destructor<__node_allocator> _Dp;
1496 typedef unique_ptr<__node, _Dp> __node_holder;
Howard Hinnantc51e1022010-05-11 19:42:16 +00001497
Eric Fiselierd63f38e2016-03-31 03:13:37 +00001498#ifdef _LIBCPP_CXX03_LANG
Howard Hinnantac7e7482013-07-04 20:59:16 +00001499 __node_holder __construct_node_with_key(const key_type& __k);
Eric Fiselierd63f38e2016-03-31 03:13:37 +00001500#endif
Howard Hinnantc51e1022010-05-11 19:42:16 +00001501};
1502
Louis Dionned23a5f22019-06-20 19:32:00 +00001503#ifndef _LIBCPP_HAS_NO_DEDUCTION_GUIDES
1504template<class _InputIterator, class _Compare = less<__iter_key_type<_InputIterator>>,
1505 class _Allocator = allocator<__iter_to_alloc_type<_InputIterator>>,
Louis Dionne6c7da9a2019-07-19 17:13:39 +00001506 class = _EnableIf<!__is_allocator<_Compare>::value, void>,
1507 class = _EnableIf<__is_allocator<_Allocator>::value, void>>
Louis Dionned23a5f22019-06-20 19:32:00 +00001508map(_InputIterator, _InputIterator, _Compare = _Compare(), _Allocator = _Allocator())
1509 -> map<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>, _Compare, _Allocator>;
1510
1511template<class _Key, class _Tp, class _Compare = less<remove_const_t<_Key>>,
1512 class _Allocator = allocator<pair<const _Key, _Tp>>,
Louis Dionne6c7da9a2019-07-19 17:13:39 +00001513 class = _EnableIf<!__is_allocator<_Compare>::value, void>,
1514 class = _EnableIf<__is_allocator<_Allocator>::value, void>>
Louis Dionned23a5f22019-06-20 19:32:00 +00001515map(initializer_list<pair<_Key, _Tp>>, _Compare = _Compare(), _Allocator = _Allocator())
1516 -> map<remove_const_t<_Key>, _Tp, _Compare, _Allocator>;
1517
1518template<class _InputIterator, class _Allocator,
Louis Dionne6c7da9a2019-07-19 17:13:39 +00001519 class = _EnableIf<__is_allocator<_Allocator>::value, void>>
Louis Dionned23a5f22019-06-20 19:32:00 +00001520map(_InputIterator, _InputIterator, _Allocator)
1521 -> map<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>,
1522 less<__iter_key_type<_InputIterator>>, _Allocator>;
1523
1524template<class _Key, class _Tp, class _Allocator,
Louis Dionne6c7da9a2019-07-19 17:13:39 +00001525 class = _EnableIf<__is_allocator<_Allocator>::value, void>>
Louis Dionned23a5f22019-06-20 19:32:00 +00001526map(initializer_list<pair<_Key, _Tp>>, _Allocator)
1527 -> map<remove_const_t<_Key>, _Tp, less<remove_const_t<_Key>>, _Allocator>;
1528#endif
Eric Fiseliera92b0732016-02-20 07:12:17 +00001529
Eric Fiselierd06276b2016-03-31 02:15:15 +00001530#ifndef _LIBCPP_CXX03_LANG
Howard Hinnantc51e1022010-05-11 19:42:16 +00001531template <class _Key, class _Tp, class _Compare, class _Allocator>
1532map<_Key, _Tp, _Compare, _Allocator>::map(map&& __m, const allocator_type& __a)
Marshall Clow657cbc42016-08-17 05:58:40 +00001533 : __tree_(_VSTD::move(__m.__tree_), typename __base::allocator_type(__a))
Howard Hinnantc51e1022010-05-11 19:42:16 +00001534{
1535 if (__a != __m.get_allocator())
1536 {
1537 const_iterator __e = cend();
1538 while (!__m.empty())
1539 __tree_.__insert_unique(__e.__i_,
Erik Pilkingtond3fe2992018-06-04 20:38:23 +00001540 __m.__tree_.remove(__m.begin().__i_)->__value_.__move());
Howard Hinnantc51e1022010-05-11 19:42:16 +00001541 }
1542}
1543
Eric Fiseliera85b1282017-04-18 21:08:06 +00001544template <class _Key, class _Tp, class _Compare, class _Allocator>
1545_Tp&
1546map<_Key, _Tp, _Compare, _Allocator>::operator[](const key_type& __k)
1547{
1548 return __tree_.__emplace_unique_key_args(__k,
1549 _VSTD::piecewise_construct,
1550 _VSTD::forward_as_tuple(__k),
Erik Pilkingtond3fe2992018-06-04 20:38:23 +00001551 _VSTD::forward_as_tuple()).first->__get_value().second;
Eric Fiseliera85b1282017-04-18 21:08:06 +00001552}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001553
Eric Fiseliera85b1282017-04-18 21:08:06 +00001554template <class _Key, class _Tp, class _Compare, class _Allocator>
1555_Tp&
1556map<_Key, _Tp, _Compare, _Allocator>::operator[](key_type&& __k)
1557{
1558 return __tree_.__emplace_unique_key_args(__k,
1559 _VSTD::piecewise_construct,
1560 _VSTD::forward_as_tuple(_VSTD::move(__k)),
Erik Pilkingtond3fe2992018-06-04 20:38:23 +00001561 _VSTD::forward_as_tuple()).first->__get_value().second;
Eric Fiseliera85b1282017-04-18 21:08:06 +00001562}
Eric Fiselierd63f38e2016-03-31 03:13:37 +00001563
Eric Fiseliera85b1282017-04-18 21:08:06 +00001564#else // _LIBCPP_CXX03_LANG
Eric Fiselierd63f38e2016-03-31 03:13:37 +00001565
Howard Hinnantc51e1022010-05-11 19:42:16 +00001566template <class _Key, class _Tp, class _Compare, class _Allocator>
1567typename map<_Key, _Tp, _Compare, _Allocator>::__node_holder
Howard Hinnantac7e7482013-07-04 20:59:16 +00001568map<_Key, _Tp, _Compare, _Allocator>::__construct_node_with_key(const key_type& __k)
Howard Hinnantc51e1022010-05-11 19:42:16 +00001569{
1570 __node_allocator& __na = __tree_.__node_alloc();
Howard Hinnantc834c512011-11-29 18:15:50 +00001571 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
Erik Pilkingtond3fe2992018-06-04 20:38:23 +00001572 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__get_value().first), __k);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001573 __h.get_deleter().__first_constructed = true;
Erik Pilkingtond3fe2992018-06-04 20:38:23 +00001574 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__get_value().second));
Howard Hinnantc51e1022010-05-11 19:42:16 +00001575 __h.get_deleter().__second_constructed = true;
Louis Dionne7b844362020-07-30 09:42:23 -04001576 return __h;
Howard Hinnantc51e1022010-05-11 19:42:16 +00001577}
1578
Howard Hinnantc51e1022010-05-11 19:42:16 +00001579template <class _Key, class _Tp, class _Compare, class _Allocator>
1580_Tp&
1581map<_Key, _Tp, _Compare, _Allocator>::operator[](const key_type& __k)
1582{
Eric Fiseliercf8c0212017-01-05 06:06:18 +00001583 __parent_pointer __parent;
1584 __node_base_pointer& __child = __tree_.__find_equal(__parent, __k);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001585 __node_pointer __r = static_cast<__node_pointer>(__child);
1586 if (__child == nullptr)
1587 {
Howard Hinnantac7e7482013-07-04 20:59:16 +00001588 __node_holder __h = __construct_node_with_key(__k);
Howard Hinnant2d0046b2013-06-19 21:29:40 +00001589 __tree_.__insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
Howard Hinnantc51e1022010-05-11 19:42:16 +00001590 __r = __h.release();
1591 }
Erik Pilkingtond3fe2992018-06-04 20:38:23 +00001592 return __r->__value_.__get_value().second;
Howard Hinnantc51e1022010-05-11 19:42:16 +00001593}
1594
Louis Dionne2b1ceaa2021-04-20 12:03:32 -04001595#endif // _LIBCPP_CXX03_LANG
Howard Hinnantc51e1022010-05-11 19:42:16 +00001596
1597template <class _Key, class _Tp, class _Compare, class _Allocator>
1598_Tp&
1599map<_Key, _Tp, _Compare, _Allocator>::at(const key_type& __k)
1600{
Eric Fiseliercf8c0212017-01-05 06:06:18 +00001601 __parent_pointer __parent;
1602 __node_base_pointer& __child = __tree_.__find_equal(__parent, __k);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001603 if (__child == nullptr)
Louis Dionne2b239162019-02-12 16:06:02 +00001604 __throw_out_of_range("map::at: key not found");
Erik Pilkingtond3fe2992018-06-04 20:38:23 +00001605 return static_cast<__node_pointer>(__child)->__value_.__get_value().second;
Howard Hinnantc51e1022010-05-11 19:42:16 +00001606}
1607
1608template <class _Key, class _Tp, class _Compare, class _Allocator>
1609const _Tp&
1610map<_Key, _Tp, _Compare, _Allocator>::at(const key_type& __k) const
1611{
Eric Fiseliercf8c0212017-01-05 06:06:18 +00001612 __parent_pointer __parent;
1613 __node_base_pointer __child = __tree_.__find_equal(__parent, __k);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001614 if (__child == nullptr)
Louis Dionne2b239162019-02-12 16:06:02 +00001615 __throw_out_of_range("map::at: key not found");
Erik Pilkingtond3fe2992018-06-04 20:38:23 +00001616 return static_cast<__node_pointer>(__child)->__value_.__get_value().second;
Howard Hinnantc51e1022010-05-11 19:42:16 +00001617}
1618
Howard Hinnantc51e1022010-05-11 19:42:16 +00001619
1620template <class _Key, class _Tp, class _Compare, class _Allocator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001621inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001622bool
1623operator==(const map<_Key, _Tp, _Compare, _Allocator>& __x,
1624 const map<_Key, _Tp, _Compare, _Allocator>& __y)
1625{
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001626 return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin());
Howard Hinnantc51e1022010-05-11 19:42:16 +00001627}
1628
1629template <class _Key, class _Tp, class _Compare, class _Allocator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001630inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001631bool
1632operator< (const map<_Key, _Tp, _Compare, _Allocator>& __x,
1633 const map<_Key, _Tp, _Compare, _Allocator>& __y)
1634{
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001635 return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
Howard Hinnantc51e1022010-05-11 19:42:16 +00001636}
1637
1638template <class _Key, class _Tp, class _Compare, class _Allocator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001639inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001640bool
1641operator!=(const map<_Key, _Tp, _Compare, _Allocator>& __x,
1642 const map<_Key, _Tp, _Compare, _Allocator>& __y)
1643{
1644 return !(__x == __y);
1645}
1646
1647template <class _Key, class _Tp, class _Compare, class _Allocator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001648inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001649bool
1650operator> (const map<_Key, _Tp, _Compare, _Allocator>& __x,
1651 const map<_Key, _Tp, _Compare, _Allocator>& __y)
1652{
1653 return __y < __x;
1654}
1655
1656template <class _Key, class _Tp, class _Compare, class _Allocator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001657inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001658bool
1659operator>=(const map<_Key, _Tp, _Compare, _Allocator>& __x,
1660 const map<_Key, _Tp, _Compare, _Allocator>& __y)
1661{
1662 return !(__x < __y);
1663}
1664
1665template <class _Key, class _Tp, class _Compare, class _Allocator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001666inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001667bool
1668operator<=(const map<_Key, _Tp, _Compare, _Allocator>& __x,
1669 const map<_Key, _Tp, _Compare, _Allocator>& __y)
1670{
1671 return !(__y < __x);
1672}
1673
1674template <class _Key, class _Tp, class _Compare, class _Allocator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001675inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001676void
1677swap(map<_Key, _Tp, _Compare, _Allocator>& __x,
1678 map<_Key, _Tp, _Compare, _Allocator>& __y)
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001679 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
Howard Hinnantc51e1022010-05-11 19:42:16 +00001680{
1681 __x.swap(__y);
1682}
1683
Marshall Clow29b53f22018-12-14 18:49:35 +00001684#if _LIBCPP_STD_VER > 17
Marek Kurdeja98b1412020-05-02 13:58:03 +02001685template <class _Key, class _Tp, class _Compare, class _Allocator,
1686 class _Predicate>
Marshall Clow29b53f22018-12-14 18:49:35 +00001687inline _LIBCPP_INLINE_VISIBILITY
Marek Kurdeja98b1412020-05-02 13:58:03 +02001688 typename map<_Key, _Tp, _Compare, _Allocator>::size_type
1689 erase_if(map<_Key, _Tp, _Compare, _Allocator>& __c, _Predicate __pred) {
Arthur O'Dwyerb6738bd2021-03-21 16:53:09 -04001690 return _VSTD::__libcpp_erase_if_container(__c, __pred);
Marek Kurdeja98b1412020-05-02 13:58:03 +02001691}
Marshall Clow29b53f22018-12-14 18:49:35 +00001692#endif
1693
1694
Howard Hinnantc51e1022010-05-11 19:42:16 +00001695template <class _Key, class _Tp, class _Compare = less<_Key>,
1696 class _Allocator = allocator<pair<const _Key, _Tp> > >
Eric Fiselierb5eb1bf2017-01-04 23:56:00 +00001697class _LIBCPP_TEMPLATE_VIS multimap
Howard Hinnantc51e1022010-05-11 19:42:16 +00001698{
1699public:
1700 // types:
1701 typedef _Key key_type;
1702 typedef _Tp mapped_type;
1703 typedef pair<const key_type, mapped_type> value_type;
Arthur O'Dwyer6a752e12021-03-03 11:10:49 -05001704 typedef __identity_t<_Compare> key_compare;
1705 typedef __identity_t<_Allocator> allocator_type;
Howard Hinnantc51e1022010-05-11 19:42:16 +00001706 typedef value_type& reference;
1707 typedef const value_type& const_reference;
1708
Marshall Clow5128cf32015-11-26 01:24:04 +00001709 static_assert((is_same<typename allocator_type::value_type, value_type>::value),
1710 "Allocator::value_type must be same type as value_type");
1711
Arthur O'Dwyerf5486c82021-05-25 14:34:18 -04001712_LIBCPP_SUPPRESS_DEPRECATED_PUSH
Eric Fiselierb5eb1bf2017-01-04 23:56:00 +00001713 class _LIBCPP_TEMPLATE_VIS value_compare
Arthur O'Dwyerf5486c82021-05-25 14:34:18 -04001714#if defined(_LIBCPP_ENABLE_CXX20_REMOVED_BINDER_TYPEDEFS)
Howard Hinnantc51e1022010-05-11 19:42:16 +00001715 : public binary_function<value_type, value_type, bool>
Arthur O'Dwyerf5486c82021-05-25 14:34:18 -04001716#endif
Howard Hinnantc51e1022010-05-11 19:42:16 +00001717 {
Arthur O'Dwyerf5486c82021-05-25 14:34:18 -04001718_LIBCPP_SUPPRESS_DEPRECATED_POP
Howard Hinnantc51e1022010-05-11 19:42:16 +00001719 friend class multimap;
1720 protected:
1721 key_compare comp;
1722
Howard Hinnant756c69b2010-09-22 16:48:34 +00001723 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001724 value_compare(key_compare c) : comp(c) {}
1725 public:
Arthur O'Dwyerf5486c82021-05-25 14:34:18 -04001726#if _LIBCPP_STD_VER <= 17 || defined(_LIBCPP_ENABLE_CXX20_REMOVED_BINDER_TYPEDEFS)
1727 _LIBCPP_DEPRECATED_IN_CXX17 typedef bool result_type;
1728 _LIBCPP_DEPRECATED_IN_CXX17 typedef value_type first_argument_type;
1729 _LIBCPP_DEPRECATED_IN_CXX17 typedef value_type second_argument_type;
1730#endif
Howard Hinnant756c69b2010-09-22 16:48:34 +00001731 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001732 bool operator()(const value_type& __x, const value_type& __y) const
1733 {return comp(__x.first, __y.first);}
1734 };
1735
1736private:
Howard Hinnant2d0046b2013-06-19 21:29:40 +00001737
Howard Hinnant89f8b792013-09-30 19:08:22 +00001738 typedef _VSTD::__value_type<key_type, mapped_type> __value_type;
Howard Hinnant90b91592013-07-05 18:06:00 +00001739 typedef __map_value_compare<key_type, __value_type, key_compare> __vc;
Marshall Clow940e01c2015-04-07 05:21:38 +00001740 typedef typename __rebind_alloc_helper<allocator_traits<allocator_type>,
1741 __value_type>::type __allocator_type;
Howard Hinnantc51e1022010-05-11 19:42:16 +00001742 typedef __tree<__value_type, __vc, __allocator_type> __base;
1743 typedef typename __base::__node_traits __node_traits;
1744 typedef allocator_traits<allocator_type> __alloc_traits;
1745
1746 __base __tree_;
1747
1748public:
1749 typedef typename __alloc_traits::pointer pointer;
1750 typedef typename __alloc_traits::const_pointer const_pointer;
1751 typedef typename __alloc_traits::size_type size_type;
1752 typedef typename __alloc_traits::difference_type difference_type;
1753 typedef __map_iterator<typename __base::iterator> iterator;
1754 typedef __map_const_iterator<typename __base::const_iterator> const_iterator;
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001755 typedef _VSTD::reverse_iterator<iterator> reverse_iterator;
1756 typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator;
Howard Hinnantc51e1022010-05-11 19:42:16 +00001757
Erik Pilkingtonc37a3d82018-08-01 01:33:38 +00001758#if _LIBCPP_STD_VER > 14
1759 typedef __map_node_handle<typename __base::__node, allocator_type> node_type;
1760#endif
1761
Erik Pilkington82a65ad2018-10-31 17:31:35 +00001762 template <class _Key2, class _Value2, class _Comp2, class _Alloc2>
1763 friend class _LIBCPP_TEMPLATE_VIS map;
1764 template <class _Key2, class _Value2, class _Comp2, class _Alloc2>
1765 friend class _LIBCPP_TEMPLATE_VIS multimap;
1766
Howard Hinnant756c69b2010-09-22 16:48:34 +00001767 _LIBCPP_INLINE_VISIBILITY
Marshall Clow7086a5a2014-03-10 04:50:10 +00001768 multimap()
1769 _NOEXCEPT_(
1770 is_nothrow_default_constructible<allocator_type>::value &&
1771 is_nothrow_default_constructible<key_compare>::value &&
1772 is_nothrow_copy_constructible<key_compare>::value)
1773 : __tree_(__vc(key_compare())) {}
1774
1775 _LIBCPP_INLINE_VISIBILITY
1776 explicit multimap(const key_compare& __comp)
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001777 _NOEXCEPT_(
1778 is_nothrow_default_constructible<allocator_type>::value &&
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001779 is_nothrow_copy_constructible<key_compare>::value)
Howard Hinnantc51e1022010-05-11 19:42:16 +00001780 : __tree_(__vc(__comp)) {}
1781
Howard Hinnant756c69b2010-09-22 16:48:34 +00001782 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001783 explicit multimap(const key_compare& __comp, const allocator_type& __a)
Marshall Clow657cbc42016-08-17 05:58:40 +00001784 : __tree_(__vc(__comp), typename __base::allocator_type(__a)) {}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001785
1786 template <class _InputIterator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001787 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001788 multimap(_InputIterator __f, _InputIterator __l,
1789 const key_compare& __comp = key_compare())
1790 : __tree_(__vc(__comp))
1791 {
1792 insert(__f, __l);
1793 }
1794
1795 template <class _InputIterator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001796 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001797 multimap(_InputIterator __f, _InputIterator __l,
1798 const key_compare& __comp, const allocator_type& __a)
Marshall Clow657cbc42016-08-17 05:58:40 +00001799 : __tree_(__vc(__comp), typename __base::allocator_type(__a))
Howard Hinnantc51e1022010-05-11 19:42:16 +00001800 {
1801 insert(__f, __l);
1802 }
1803
Marshall Clow300abfb2013-09-11 01:15:47 +00001804#if _LIBCPP_STD_VER > 11
1805 template <class _InputIterator>
Eric Fiseliercf8c0212017-01-05 06:06:18 +00001806 _LIBCPP_INLINE_VISIBILITY
Marshall Clow300abfb2013-09-11 01:15:47 +00001807 multimap(_InputIterator __f, _InputIterator __l, const allocator_type& __a)
1808 : multimap(__f, __l, key_compare(), __a) {}
1809#endif
1810
Howard Hinnant756c69b2010-09-22 16:48:34 +00001811 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001812 multimap(const multimap& __m)
1813 : __tree_(__m.__tree_.value_comp(),
1814 __alloc_traits::select_on_container_copy_construction(__m.__tree_.__alloc()))
1815 {
1816 insert(__m.begin(), __m.end());
1817 }
1818
Howard Hinnantd3a657f2011-07-01 19:24:36 +00001819 _LIBCPP_INLINE_VISIBILITY
1820 multimap& operator=(const multimap& __m)
1821 {
Marshall Clow476d3f42016-07-18 13:19:00 +00001822#ifndef _LIBCPP_CXX03_LANG
Howard Hinnantd3a657f2011-07-01 19:24:36 +00001823 __tree_ = __m.__tree_;
Howard Hinnant2d0046b2013-06-19 21:29:40 +00001824#else
Marshall Clowdb3cfcb2014-02-08 04:03:14 +00001825 if (this != &__m) {
1826 __tree_.clear();
1827 __tree_.value_comp() = __m.__tree_.value_comp();
1828 __tree_.__copy_assign_alloc(__m.__tree_);
1829 insert(__m.begin(), __m.end());
1830 }
Howard Hinnant2d0046b2013-06-19 21:29:40 +00001831#endif
Howard Hinnantd3a657f2011-07-01 19:24:36 +00001832 return *this;
1833 }
1834
Eric Fiseliera85b1282017-04-18 21:08:06 +00001835#ifndef _LIBCPP_CXX03_LANG
Howard Hinnantc51e1022010-05-11 19:42:16 +00001836
Howard Hinnant756c69b2010-09-22 16:48:34 +00001837 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001838 multimap(multimap&& __m)
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001839 _NOEXCEPT_(is_nothrow_move_constructible<__base>::value)
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001840 : __tree_(_VSTD::move(__m.__tree_))
Howard Hinnantc51e1022010-05-11 19:42:16 +00001841 {
1842 }
1843
1844 multimap(multimap&& __m, const allocator_type& __a);
1845
Howard Hinnant756c69b2010-09-22 16:48:34 +00001846 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant33711792011-08-12 21:56:02 +00001847 multimap& operator=(multimap&& __m)
1848 _NOEXCEPT_(is_nothrow_move_assignable<__base>::value)
1849 {
1850 __tree_ = _VSTD::move(__m.__tree_);
1851 return *this;
1852 }
1853
Howard Hinnant33711792011-08-12 21:56:02 +00001854 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001855 multimap(initializer_list<value_type> __il, const key_compare& __comp = key_compare())
1856 : __tree_(__vc(__comp))
1857 {
1858 insert(__il.begin(), __il.end());
1859 }
1860
Howard Hinnant756c69b2010-09-22 16:48:34 +00001861 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001862 multimap(initializer_list<value_type> __il, const key_compare& __comp, const allocator_type& __a)
Marshall Clow657cbc42016-08-17 05:58:40 +00001863 : __tree_(__vc(__comp), typename __base::allocator_type(__a))
Howard Hinnantc51e1022010-05-11 19:42:16 +00001864 {
1865 insert(__il.begin(), __il.end());
1866 }
1867
Marshall Clow300abfb2013-09-11 01:15:47 +00001868#if _LIBCPP_STD_VER > 11
Eric Fiseliercf8c0212017-01-05 06:06:18 +00001869 _LIBCPP_INLINE_VISIBILITY
Marshall Clow300abfb2013-09-11 01:15:47 +00001870 multimap(initializer_list<value_type> __il, const allocator_type& __a)
1871 : multimap(__il, key_compare(), __a) {}
1872#endif
1873
Howard Hinnant756c69b2010-09-22 16:48:34 +00001874 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001875 multimap& operator=(initializer_list<value_type> __il)
1876 {
1877 __tree_.__assign_multi(__il.begin(), __il.end());
1878 return *this;
1879 }
Howard Hinnant33711792011-08-12 21:56:02 +00001880
Louis Dionne2b1ceaa2021-04-20 12:03:32 -04001881#endif // _LIBCPP_CXX03_LANG
Howard Hinnantc51e1022010-05-11 19:42:16 +00001882
Howard Hinnant756c69b2010-09-22 16:48:34 +00001883 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001884 explicit multimap(const allocator_type& __a)
Marshall Clow657cbc42016-08-17 05:58:40 +00001885 : __tree_(typename __base::allocator_type(__a))
Howard Hinnantc51e1022010-05-11 19:42:16 +00001886 {
1887 }
1888
Howard Hinnant756c69b2010-09-22 16:48:34 +00001889 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001890 multimap(const multimap& __m, const allocator_type& __a)
Marshall Clow657cbc42016-08-17 05:58:40 +00001891 : __tree_(__m.__tree_.value_comp(), typename __base::allocator_type(__a))
Howard Hinnantc51e1022010-05-11 19:42:16 +00001892 {
1893 insert(__m.begin(), __m.end());
1894 }
1895
Howard Hinnant756c69b2010-09-22 16:48:34 +00001896 _LIBCPP_INLINE_VISIBILITY
Louis Dionne69c42c02019-04-11 16:14:56 +00001897 ~multimap() {
1898 static_assert(sizeof(__diagnose_non_const_comparator<_Key, _Compare>()), "");
1899 }
1900
1901 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001902 iterator begin() _NOEXCEPT {return __tree_.begin();}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001903 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001904 const_iterator begin() const _NOEXCEPT {return __tree_.begin();}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001905 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001906 iterator end() _NOEXCEPT {return __tree_.end();}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001907 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001908 const_iterator end() const _NOEXCEPT {return __tree_.end();}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001909
Howard Hinnant756c69b2010-09-22 16:48:34 +00001910 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001911 reverse_iterator rbegin() _NOEXCEPT {return reverse_iterator(end());}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001912 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001913 const_reverse_iterator rbegin() const _NOEXCEPT
1914 {return const_reverse_iterator(end());}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001915 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001916 reverse_iterator rend() _NOEXCEPT {return reverse_iterator(begin());}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001917 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001918 const_reverse_iterator rend() const _NOEXCEPT
1919 {return const_reverse_iterator(begin());}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001920
Howard Hinnant756c69b2010-09-22 16:48:34 +00001921 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001922 const_iterator cbegin() const _NOEXCEPT {return begin();}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001923 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001924 const_iterator cend() const _NOEXCEPT {return end();}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001925 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001926 const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001927 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001928 const_reverse_iterator crend() const _NOEXCEPT {return rend();}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001929
Marshall Clow425f5752017-11-15 05:51:26 +00001930 _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001931 bool empty() const _NOEXCEPT {return __tree_.size() == 0;}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001932 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001933 size_type size() const _NOEXCEPT {return __tree_.size();}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001934 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001935 size_type max_size() const _NOEXCEPT {return __tree_.max_size();}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001936
Howard Hinnant756c69b2010-09-22 16:48:34 +00001937 _LIBCPP_INLINE_VISIBILITY
Marshall Clow657cbc42016-08-17 05:58:40 +00001938 allocator_type get_allocator() const _NOEXCEPT {return allocator_type(__tree_.__alloc());}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001939 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001940 key_compare key_comp() const {return __tree_.value_comp().key_comp();}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001941 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001942 value_compare value_comp() const
1943 {return value_compare(__tree_.value_comp().key_comp());}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001944
Eric Fiselierd06276b2016-03-31 02:15:15 +00001945#ifndef _LIBCPP_CXX03_LANG
Howard Hinnant74279a52010-09-04 23:28:19 +00001946
Howard Hinnant29eb9b82012-05-25 22:04:21 +00001947 template <class ..._Args>
Eric Fiselierd06276b2016-03-31 02:15:15 +00001948 _LIBCPP_INLINE_VISIBILITY
1949 iterator emplace(_Args&& ...__args) {
1950 return __tree_.__emplace_multi(_VSTD::forward<_Args>(__args)...);
1951 }
Howard Hinnantc51e1022010-05-11 19:42:16 +00001952
Howard Hinnant29eb9b82012-05-25 22:04:21 +00001953 template <class ..._Args>
Eric Fiselierd06276b2016-03-31 02:15:15 +00001954 _LIBCPP_INLINE_VISIBILITY
1955 iterator emplace_hint(const_iterator __p, _Args&& ...__args) {
1956 return __tree_.__emplace_hint_multi(__p.__i_, _VSTD::forward<_Args>(__args)...);
1957 }
Howard Hinnant74279a52010-09-04 23:28:19 +00001958
Howard Hinnantc834c512011-11-29 18:15:50 +00001959 template <class _Pp,
1960 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001961 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc834c512011-11-29 18:15:50 +00001962 iterator insert(_Pp&& __p)
1963 {return __tree_.__insert_multi(_VSTD::forward<_Pp>(__p));}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001964
Howard Hinnantc834c512011-11-29 18:15:50 +00001965 template <class _Pp,
1966 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001967 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc834c512011-11-29 18:15:50 +00001968 iterator insert(const_iterator __pos, _Pp&& __p)
1969 {return __tree_.__insert_multi(__pos.__i_, _VSTD::forward<_Pp>(__p));}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001970
Eric Fiselierd6143132016-04-18 01:40:45 +00001971 _LIBCPP_INLINE_VISIBILITY
1972 iterator insert(value_type&& __v)
1973 {return __tree_.__insert_multi(_VSTD::move(__v));}
1974
1975 _LIBCPP_INLINE_VISIBILITY
1976 iterator insert(const_iterator __p, value_type&& __v)
1977 {return __tree_.__insert_multi(__p.__i_, _VSTD::move(__v));}
1978
Eric Fiseliera85b1282017-04-18 21:08:06 +00001979
1980 _LIBCPP_INLINE_VISIBILITY
1981 void insert(initializer_list<value_type> __il)
1982 {insert(__il.begin(), __il.end());}
1983
Louis Dionne2b1ceaa2021-04-20 12:03:32 -04001984#endif // _LIBCPP_CXX03_LANG
Howard Hinnantc51e1022010-05-11 19:42:16 +00001985
Howard Hinnant756c69b2010-09-22 16:48:34 +00001986 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001987 iterator insert(const value_type& __v) {return __tree_.__insert_multi(__v);}
1988
Howard Hinnant756c69b2010-09-22 16:48:34 +00001989 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001990 iterator insert(const_iterator __p, const value_type& __v)
1991 {return __tree_.__insert_multi(__p.__i_, __v);}
1992
1993 template <class _InputIterator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001994 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001995 void insert(_InputIterator __f, _InputIterator __l)
1996 {
1997 for (const_iterator __e = cend(); __f != __l; ++__f)
1998 __tree_.__insert_multi(__e.__i_, *__f);
1999 }
2000
Howard Hinnant756c69b2010-09-22 16:48:34 +00002001 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00002002 iterator erase(const_iterator __p) {return __tree_.erase(__p.__i_);}
Howard Hinnant756c69b2010-09-22 16:48:34 +00002003 _LIBCPP_INLINE_VISIBILITY
Marshall Clow22ea5b82015-05-10 13:35:00 +00002004 iterator erase(iterator __p) {return __tree_.erase(__p.__i_);}
2005 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00002006 size_type erase(const key_type& __k) {return __tree_.__erase_multi(__k);}
Howard Hinnant756c69b2010-09-22 16:48:34 +00002007 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00002008 iterator erase(const_iterator __f, const_iterator __l)
2009 {return __tree_.erase(__f.__i_, __l.__i_);}
Erik Pilkingtonc37a3d82018-08-01 01:33:38 +00002010
2011#if _LIBCPP_STD_VER > 14
2012 _LIBCPP_INLINE_VISIBILITY
2013 iterator insert(node_type&& __nh)
2014 {
2015 _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(),
2016 "node_type with incompatible allocator passed to multimap::insert()");
2017 return __tree_.template __node_handle_insert_multi<node_type>(
2018 _VSTD::move(__nh));
2019 }
2020 _LIBCPP_INLINE_VISIBILITY
2021 iterator insert(const_iterator __hint, node_type&& __nh)
2022 {
2023 _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(),
2024 "node_type with incompatible allocator passed to multimap::insert()");
2025 return __tree_.template __node_handle_insert_multi<node_type>(
2026 __hint.__i_, _VSTD::move(__nh));
2027 }
2028 _LIBCPP_INLINE_VISIBILITY
2029 node_type extract(key_type const& __key)
2030 {
2031 return __tree_.template __node_handle_extract<node_type>(__key);
2032 }
2033 _LIBCPP_INLINE_VISIBILITY
2034 node_type extract(const_iterator __it)
2035 {
2036 return __tree_.template __node_handle_extract<node_type>(
2037 __it.__i_);
2038 }
Louis Dionned2322c82018-11-01 14:41:37 +00002039 template <class _Compare2>
Erik Pilkington82a65ad2018-10-31 17:31:35 +00002040 _LIBCPP_INLINE_VISIBILITY
Louis Dionned2322c82018-11-01 14:41:37 +00002041 void merge(multimap<key_type, mapped_type, _Compare2, allocator_type>& __source)
Erik Pilkington82a65ad2018-10-31 17:31:35 +00002042 {
2043 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
2044 "merging container with incompatible allocator");
2045 return __tree_.__node_handle_merge_multi(__source.__tree_);
2046 }
Louis Dionned2322c82018-11-01 14:41:37 +00002047 template <class _Compare2>
Erik Pilkington82a65ad2018-10-31 17:31:35 +00002048 _LIBCPP_INLINE_VISIBILITY
Louis Dionned2322c82018-11-01 14:41:37 +00002049 void merge(multimap<key_type, mapped_type, _Compare2, allocator_type>&& __source)
Erik Pilkington82a65ad2018-10-31 17:31:35 +00002050 {
2051 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
2052 "merging container with incompatible allocator");
2053 return __tree_.__node_handle_merge_multi(__source.__tree_);
2054 }
Louis Dionned2322c82018-11-01 14:41:37 +00002055 template <class _Compare2>
Erik Pilkington82a65ad2018-10-31 17:31:35 +00002056 _LIBCPP_INLINE_VISIBILITY
Louis Dionned2322c82018-11-01 14:41:37 +00002057 void merge(map<key_type, mapped_type, _Compare2, allocator_type>& __source)
Erik Pilkington82a65ad2018-10-31 17:31:35 +00002058 {
2059 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
2060 "merging container with incompatible allocator");
2061 return __tree_.__node_handle_merge_multi(__source.__tree_);
2062 }
Louis Dionned2322c82018-11-01 14:41:37 +00002063 template <class _Compare2>
Erik Pilkington82a65ad2018-10-31 17:31:35 +00002064 _LIBCPP_INLINE_VISIBILITY
Louis Dionned2322c82018-11-01 14:41:37 +00002065 void merge(map<key_type, mapped_type, _Compare2, allocator_type>&& __source)
Erik Pilkington82a65ad2018-10-31 17:31:35 +00002066 {
2067 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
2068 "merging container with incompatible allocator");
2069 return __tree_.__node_handle_merge_multi(__source.__tree_);
2070 }
Erik Pilkingtonc37a3d82018-08-01 01:33:38 +00002071#endif
2072
Howard Hinnant756c69b2010-09-22 16:48:34 +00002073 _LIBCPP_INLINE_VISIBILITY
Marshall Clowde1312a2018-08-22 04:28:43 +00002074 void clear() _NOEXCEPT {__tree_.clear();}
Howard Hinnantc51e1022010-05-11 19:42:16 +00002075
Howard Hinnant756c69b2010-09-22 16:48:34 +00002076 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00002077 void swap(multimap& __m)
2078 _NOEXCEPT_(__is_nothrow_swappable<__base>::value)
2079 {__tree_.swap(__m.__tree_);}
Howard Hinnantc51e1022010-05-11 19:42:16 +00002080
Howard Hinnant756c69b2010-09-22 16:48:34 +00002081 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00002082 iterator find(const key_type& __k) {return __tree_.find(__k);}
Howard Hinnant756c69b2010-09-22 16:48:34 +00002083 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00002084 const_iterator find(const key_type& __k) const {return __tree_.find(__k);}
Marshall Clowebb57322013-08-13 22:18:47 +00002085#if _LIBCPP_STD_VER > 11
2086 template <typename _K2>
2087 _LIBCPP_INLINE_VISIBILITY
2088 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
2089 find(const _K2& __k) {return __tree_.find(__k);}
2090 template <typename _K2>
2091 _LIBCPP_INLINE_VISIBILITY
2092 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
2093 find(const _K2& __k) const {return __tree_.find(__k);}
2094#endif
2095
Howard Hinnant756c69b2010-09-22 16:48:34 +00002096 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00002097 size_type count(const key_type& __k) const
2098 {return __tree_.__count_multi(__k);}
Marshall Clowe6a5f522014-08-24 23:54:16 +00002099#if _LIBCPP_STD_VER > 11
2100 template <typename _K2>
2101 _LIBCPP_INLINE_VISIBILITY
2102 typename enable_if<__is_transparent<_Compare, _K2>::value,size_type>::type
Marshall Clow141e47b2015-06-30 18:15:41 +00002103 count(const _K2& __k) const {return __tree_.__count_multi(__k);}
Marshall Clowe6a5f522014-08-24 23:54:16 +00002104#endif
Zoe Carver3ffbab12019-07-16 03:21:01 +00002105
2106#if _LIBCPP_STD_VER > 17
2107 _LIBCPP_INLINE_VISIBILITY
2108 bool contains(const key_type& __k) const {return find(__k) != end();}
Marek Kurdejd7e019e2021-04-13 17:10:55 +02002109 template <typename _K2>
2110 _LIBCPP_INLINE_VISIBILITY
2111 typename enable_if<__is_transparent<_Compare, _K2>::value, bool>::type
2112 contains(const _K2& __k) const { return find(__k) != end(); }
Zoe Carver3ffbab12019-07-16 03:21:01 +00002113#endif // _LIBCPP_STD_VER > 17
2114
Howard Hinnant756c69b2010-09-22 16:48:34 +00002115 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00002116 iterator lower_bound(const key_type& __k)
2117 {return __tree_.lower_bound(__k);}
Howard Hinnant756c69b2010-09-22 16:48:34 +00002118 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00002119 const_iterator lower_bound(const key_type& __k) const
2120 {return __tree_.lower_bound(__k);}
Marshall Clowebb57322013-08-13 22:18:47 +00002121#if _LIBCPP_STD_VER > 11
2122 template <typename _K2>
2123 _LIBCPP_INLINE_VISIBILITY
2124 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
2125 lower_bound(const _K2& __k) {return __tree_.lower_bound(__k);}
2126
2127 template <typename _K2>
2128 _LIBCPP_INLINE_VISIBILITY
2129 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
2130 lower_bound(const _K2& __k) const {return __tree_.lower_bound(__k);}
2131#endif
2132
Howard Hinnant756c69b2010-09-22 16:48:34 +00002133 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00002134 iterator upper_bound(const key_type& __k)
2135 {return __tree_.upper_bound(__k);}
Howard Hinnant756c69b2010-09-22 16:48:34 +00002136 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00002137 const_iterator upper_bound(const key_type& __k) const
2138 {return __tree_.upper_bound(__k);}
Marshall Clowebb57322013-08-13 22:18:47 +00002139#if _LIBCPP_STD_VER > 11
2140 template <typename _K2>
2141 _LIBCPP_INLINE_VISIBILITY
2142 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
2143 upper_bound(const _K2& __k) {return __tree_.upper_bound(__k);}
2144 template <typename _K2>
2145 _LIBCPP_INLINE_VISIBILITY
2146 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
2147 upper_bound(const _K2& __k) const {return __tree_.upper_bound(__k);}
2148#endif
2149
Howard Hinnant756c69b2010-09-22 16:48:34 +00002150 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00002151 pair<iterator,iterator> equal_range(const key_type& __k)
2152 {return __tree_.__equal_range_multi(__k);}
Howard Hinnant756c69b2010-09-22 16:48:34 +00002153 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00002154 pair<const_iterator,const_iterator> equal_range(const key_type& __k) const
2155 {return __tree_.__equal_range_multi(__k);}
Marshall Clowebb57322013-08-13 22:18:47 +00002156#if _LIBCPP_STD_VER > 11
2157 template <typename _K2>
2158 _LIBCPP_INLINE_VISIBILITY
2159 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<iterator,iterator>>::type
2160 equal_range(const _K2& __k) {return __tree_.__equal_range_multi(__k);}
2161 template <typename _K2>
2162 _LIBCPP_INLINE_VISIBILITY
2163 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<const_iterator,const_iterator>>::type
2164 equal_range(const _K2& __k) const {return __tree_.__equal_range_multi(__k);}
2165#endif
Howard Hinnantc51e1022010-05-11 19:42:16 +00002166
2167private:
2168 typedef typename __base::__node __node;
2169 typedef typename __base::__node_allocator __node_allocator;
2170 typedef typename __base::__node_pointer __node_pointer;
Eric Fiseliera92b0732016-02-20 07:12:17 +00002171
Howard Hinnantc834c512011-11-29 18:15:50 +00002172 typedef __map_node_destructor<__node_allocator> _Dp;
2173 typedef unique_ptr<__node, _Dp> __node_holder;
Howard Hinnantc51e1022010-05-11 19:42:16 +00002174};
2175
Louis Dionned23a5f22019-06-20 19:32:00 +00002176#ifndef _LIBCPP_HAS_NO_DEDUCTION_GUIDES
2177template<class _InputIterator, class _Compare = less<__iter_key_type<_InputIterator>>,
2178 class _Allocator = allocator<__iter_to_alloc_type<_InputIterator>>,
Louis Dionne6c7da9a2019-07-19 17:13:39 +00002179 class = _EnableIf<!__is_allocator<_Compare>::value, void>,
2180 class = _EnableIf<__is_allocator<_Allocator>::value, void>>
Louis Dionned23a5f22019-06-20 19:32:00 +00002181multimap(_InputIterator, _InputIterator, _Compare = _Compare(), _Allocator = _Allocator())
2182 -> multimap<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>, _Compare, _Allocator>;
2183
2184template<class _Key, class _Tp, class _Compare = less<remove_const_t<_Key>>,
2185 class _Allocator = allocator<pair<const _Key, _Tp>>,
Louis Dionne6c7da9a2019-07-19 17:13:39 +00002186 class = _EnableIf<!__is_allocator<_Compare>::value, void>,
2187 class = _EnableIf<__is_allocator<_Allocator>::value, void>>
Louis Dionned23a5f22019-06-20 19:32:00 +00002188multimap(initializer_list<pair<_Key, _Tp>>, _Compare = _Compare(), _Allocator = _Allocator())
2189 -> multimap<remove_const_t<_Key>, _Tp, _Compare, _Allocator>;
2190
2191template<class _InputIterator, class _Allocator,
Louis Dionne6c7da9a2019-07-19 17:13:39 +00002192 class = _EnableIf<__is_allocator<_Allocator>::value, void>>
Louis Dionned23a5f22019-06-20 19:32:00 +00002193multimap(_InputIterator, _InputIterator, _Allocator)
2194 -> multimap<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>,
2195 less<__iter_key_type<_InputIterator>>, _Allocator>;
2196
2197template<class _Key, class _Tp, class _Allocator,
Louis Dionne6c7da9a2019-07-19 17:13:39 +00002198 class = _EnableIf<__is_allocator<_Allocator>::value, void>>
Louis Dionned23a5f22019-06-20 19:32:00 +00002199multimap(initializer_list<pair<_Key, _Tp>>, _Allocator)
2200 -> multimap<remove_const_t<_Key>, _Tp, less<remove_const_t<_Key>>, _Allocator>;
2201#endif
2202
Eric Fiselierd06276b2016-03-31 02:15:15 +00002203#ifndef _LIBCPP_CXX03_LANG
Howard Hinnantc51e1022010-05-11 19:42:16 +00002204template <class _Key, class _Tp, class _Compare, class _Allocator>
2205multimap<_Key, _Tp, _Compare, _Allocator>::multimap(multimap&& __m, const allocator_type& __a)
Marshall Clow657cbc42016-08-17 05:58:40 +00002206 : __tree_(_VSTD::move(__m.__tree_), typename __base::allocator_type(__a))
Howard Hinnantc51e1022010-05-11 19:42:16 +00002207{
2208 if (__a != __m.get_allocator())
2209 {
2210 const_iterator __e = cend();
2211 while (!__m.empty())
2212 __tree_.__insert_multi(__e.__i_,
Erik Pilkingtond3fe2992018-06-04 20:38:23 +00002213 _VSTD::move(__m.__tree_.remove(__m.begin().__i_)->__value_.__move()));
Howard Hinnantc51e1022010-05-11 19:42:16 +00002214 }
2215}
Eric Fiselierd06276b2016-03-31 02:15:15 +00002216#endif
Howard Hinnantc51e1022010-05-11 19:42:16 +00002217
2218template <class _Key, class _Tp, class _Compare, class _Allocator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00002219inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00002220bool
2221operator==(const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
2222 const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
2223{
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00002224 return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin());
Howard Hinnantc51e1022010-05-11 19:42:16 +00002225}
2226
2227template <class _Key, class _Tp, class _Compare, class _Allocator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00002228inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00002229bool
2230operator< (const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
2231 const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
2232{
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00002233 return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
Howard Hinnantc51e1022010-05-11 19:42:16 +00002234}
2235
2236template <class _Key, class _Tp, class _Compare, class _Allocator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00002237inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00002238bool
2239operator!=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
2240 const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
2241{
2242 return !(__x == __y);
2243}
2244
2245template <class _Key, class _Tp, class _Compare, class _Allocator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00002246inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00002247bool
2248operator> (const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
2249 const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
2250{
2251 return __y < __x;
2252}
2253
2254template <class _Key, class _Tp, class _Compare, class _Allocator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00002255inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00002256bool
2257operator>=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
2258 const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
2259{
2260 return !(__x < __y);
2261}
2262
2263template <class _Key, class _Tp, class _Compare, class _Allocator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00002264inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00002265bool
2266operator<=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
2267 const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
2268{
2269 return !(__y < __x);
2270}
2271
2272template <class _Key, class _Tp, class _Compare, class _Allocator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00002273inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00002274void
2275swap(multimap<_Key, _Tp, _Compare, _Allocator>& __x,
2276 multimap<_Key, _Tp, _Compare, _Allocator>& __y)
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00002277 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
Howard Hinnantc51e1022010-05-11 19:42:16 +00002278{
2279 __x.swap(__y);
2280}
2281
Marshall Clow29b53f22018-12-14 18:49:35 +00002282#if _LIBCPP_STD_VER > 17
Marek Kurdeja98b1412020-05-02 13:58:03 +02002283template <class _Key, class _Tp, class _Compare, class _Allocator,
2284 class _Predicate>
Marshall Clow29b53f22018-12-14 18:49:35 +00002285inline _LIBCPP_INLINE_VISIBILITY
Marek Kurdeja98b1412020-05-02 13:58:03 +02002286 typename multimap<_Key, _Tp, _Compare, _Allocator>::size_type
2287 erase_if(multimap<_Key, _Tp, _Compare, _Allocator>& __c,
2288 _Predicate __pred) {
Arthur O'Dwyerb6738bd2021-03-21 16:53:09 -04002289 return _VSTD::__libcpp_erase_if_container(__c, __pred);
Marek Kurdeja98b1412020-05-02 13:58:03 +02002290}
Marshall Clow29b53f22018-12-14 18:49:35 +00002291#endif
2292
Howard Hinnantc51e1022010-05-11 19:42:16 +00002293_LIBCPP_END_NAMESPACE_STD
2294
Louis Dionne2b1ceaa2021-04-20 12:03:32 -04002295#endif // _LIBCPP_MAP