blob: 3c2b6ff5eb8d222648ebba6f4954cc983fa067ee [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>
Christopher Di Bella55d7a822021-07-01 09:25:35 -0400494#include <__functional/is_transparent.h>
Erik Pilkingtonc37a3d82018-08-01 01:33:38 +0000495#include <__node_handle>
Arthur O'Dwyer597cac42021-05-12 23:04:03 -0400496#include <__tree>
Christopher Di Bella41f26e82021-06-05 02:47:47 +0000497#include <__utility/forward.h>
Arthur O'Dwyer7deec122021-03-24 18:19:12 -0400498#include <compare>
Arthur O'Dwyeref181602021-05-19 11:57:04 -0400499#include <functional>
Arthur O'Dwyer7deec122021-03-24 18:19:12 -0400500#include <initializer_list>
Arthur O'Dwyerb6738bd2021-03-21 16:53:09 -0400501#include <iterator> // __libcpp_erase_if_container
Howard Hinnantc51e1022010-05-11 19:42:16 +0000502#include <memory>
Eric Fiselierf7394302015-06-13 07:08:02 +0000503#include <type_traits>
Arthur O'Dwyeref181602021-05-19 11:57:04 -0400504#include <utility>
Marshall Clow0a1e7502018-09-12 19:41:40 +0000505#include <version>
Howard Hinnantc51e1022010-05-11 19:42:16 +0000506
Howard Hinnantaaaa52b2011-10-17 20:05:10 +0000507#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
Howard Hinnantc51e1022010-05-11 19:42:16 +0000508#pragma GCC system_header
Howard Hinnantaaaa52b2011-10-17 20:05:10 +0000509#endif
Howard Hinnantc51e1022010-05-11 19:42:16 +0000510
511_LIBCPP_BEGIN_NAMESPACE_STD
512
Louis Dionne878a3a82018-12-06 21:46:17 +0000513template <class _Key, class _CP, class _Compare,
514 bool = is_empty<_Compare>::value && !__libcpp_is_final<_Compare>::value>
Howard Hinnantc51e1022010-05-11 19:42:16 +0000515class __map_value_compare
516 : private _Compare
517{
Howard Hinnantc51e1022010-05-11 19:42:16 +0000518public:
Howard Hinnant756c69b2010-09-22 16:48:34 +0000519 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000520 __map_value_compare()
521 _NOEXCEPT_(is_nothrow_default_constructible<_Compare>::value)
522 : _Compare() {}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000523 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000524 __map_value_compare(_Compare c)
525 _NOEXCEPT_(is_nothrow_copy_constructible<_Compare>::value)
526 : _Compare(c) {}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000527 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000528 const _Compare& key_comp() const _NOEXCEPT {return *this;}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000529 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000530 bool operator()(const _CP& __x, const _CP& __y) const
Erik Pilkingtond3fe2992018-06-04 20:38:23 +0000531 {return static_cast<const _Compare&>(*this)(__x.__get_value().first, __y.__get_value().first);}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000532 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000533 bool operator()(const _CP& __x, const _Key& __y) const
Erik Pilkingtond3fe2992018-06-04 20:38:23 +0000534 {return static_cast<const _Compare&>(*this)(__x.__get_value().first, __y);}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000535 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000536 bool operator()(const _Key& __x, const _CP& __y) const
Erik Pilkingtond3fe2992018-06-04 20:38:23 +0000537 {return static_cast<const _Compare&>(*this)(__x, __y.__get_value().first);}
Marshall Clow8982dcd2015-07-13 20:04:56 +0000538 void swap(__map_value_compare&__y)
539 _NOEXCEPT_(__is_nothrow_swappable<_Compare>::value)
540 {
Eric Fiselier68b5f0b2017-04-13 00:34:24 +0000541 using _VSTD::swap;
542 swap(static_cast<_Compare&>(*this), static_cast<_Compare&>(__y));
Marshall Clow8982dcd2015-07-13 20:04:56 +0000543 }
Marshall Clowebb57322013-08-13 22:18:47 +0000544
545#if _LIBCPP_STD_VER > 11
546 template <typename _K2>
547 _LIBCPP_INLINE_VISIBILITY
548 typename enable_if<__is_transparent<_Compare, _K2>::value, bool>::type
549 operator () ( const _K2& __x, const _CP& __y ) const
Erik Pilkingtond3fe2992018-06-04 20:38:23 +0000550 {return static_cast<const _Compare&>(*this) (__x, __y.__get_value().first);}
Marshall Clowebb57322013-08-13 22:18:47 +0000551
552 template <typename _K2>
553 _LIBCPP_INLINE_VISIBILITY
554 typename enable_if<__is_transparent<_Compare, _K2>::value, bool>::type
555 operator () (const _CP& __x, const _K2& __y) const
Erik Pilkingtond3fe2992018-06-04 20:38:23 +0000556 {return static_cast<const _Compare&>(*this) (__x.__get_value().first, __y);}
Marshall Clowebb57322013-08-13 22:18:47 +0000557#endif
Howard Hinnantc51e1022010-05-11 19:42:16 +0000558};
559
Howard Hinnant90b91592013-07-05 18:06:00 +0000560template <class _Key, class _CP, class _Compare>
561class __map_value_compare<_Key, _CP, _Compare, false>
Howard Hinnantc51e1022010-05-11 19:42:16 +0000562{
563 _Compare comp;
564
Howard Hinnantc51e1022010-05-11 19:42:16 +0000565public:
Howard Hinnant756c69b2010-09-22 16:48:34 +0000566 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000567 __map_value_compare()
568 _NOEXCEPT_(is_nothrow_default_constructible<_Compare>::value)
569 : comp() {}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000570 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000571 __map_value_compare(_Compare c)
572 _NOEXCEPT_(is_nothrow_copy_constructible<_Compare>::value)
573 : comp(c) {}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000574 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000575 const _Compare& key_comp() const _NOEXCEPT {return comp;}
Howard Hinnantc51e1022010-05-11 19:42:16 +0000576
Howard Hinnant756c69b2010-09-22 16:48:34 +0000577 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000578 bool operator()(const _CP& __x, const _CP& __y) const
Erik Pilkingtond3fe2992018-06-04 20:38:23 +0000579 {return comp(__x.__get_value().first, __y.__get_value().first);}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000580 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000581 bool operator()(const _CP& __x, const _Key& __y) const
Erik Pilkingtond3fe2992018-06-04 20:38:23 +0000582 {return comp(__x.__get_value().first, __y);}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000583 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000584 bool operator()(const _Key& __x, const _CP& __y) const
Erik Pilkingtond3fe2992018-06-04 20:38:23 +0000585 {return comp(__x, __y.__get_value().first);}
Marshall Clow8982dcd2015-07-13 20:04:56 +0000586 void swap(__map_value_compare&__y)
587 _NOEXCEPT_(__is_nothrow_swappable<_Compare>::value)
588 {
589 using _VSTD::swap;
590 swap(comp, __y.comp);
591 }
Eric Fiseliercf8c0212017-01-05 06:06:18 +0000592
Marshall Clowebb57322013-08-13 22:18:47 +0000593#if _LIBCPP_STD_VER > 11
594 template <typename _K2>
595 _LIBCPP_INLINE_VISIBILITY
596 typename enable_if<__is_transparent<_Compare, _K2>::value, bool>::type
597 operator () ( const _K2& __x, const _CP& __y ) const
Erik Pilkingtond3fe2992018-06-04 20:38:23 +0000598 {return comp (__x, __y.__get_value().first);}
Marshall Clowebb57322013-08-13 22:18:47 +0000599
600 template <typename _K2>
601 _LIBCPP_INLINE_VISIBILITY
602 typename enable_if<__is_transparent<_Compare, _K2>::value, bool>::type
603 operator () (const _CP& __x, const _K2& __y) const
Erik Pilkingtond3fe2992018-06-04 20:38:23 +0000604 {return comp (__x.__get_value().first, __y);}
Marshall Clowebb57322013-08-13 22:18:47 +0000605#endif
Howard Hinnantc51e1022010-05-11 19:42:16 +0000606};
607
Marshall Clow8982dcd2015-07-13 20:04:56 +0000608template <class _Key, class _CP, class _Compare, bool __b>
609inline _LIBCPP_INLINE_VISIBILITY
610void
611swap(__map_value_compare<_Key, _CP, _Compare, __b>& __x,
612 __map_value_compare<_Key, _CP, _Compare, __b>& __y)
613 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
614{
615 __x.swap(__y);
616}
617
Howard Hinnantc51e1022010-05-11 19:42:16 +0000618template <class _Allocator>
619class __map_node_destructor
620{
621 typedef _Allocator allocator_type;
622 typedef allocator_traits<allocator_type> __alloc_traits;
Eric Fiseliera00b4842016-02-20 05:28:30 +0000623
Howard Hinnantc51e1022010-05-11 19:42:16 +0000624public:
625 typedef typename __alloc_traits::pointer pointer;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000626
Eric Fiseliera00b4842016-02-20 05:28:30 +0000627private:
Howard Hinnantc51e1022010-05-11 19:42:16 +0000628 allocator_type& __na_;
629
630 __map_node_destructor& operator=(const __map_node_destructor&);
631
632public:
633 bool __first_constructed;
634 bool __second_constructed;
635
Howard Hinnant756c69b2010-09-22 16:48:34 +0000636 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000637 explicit __map_node_destructor(allocator_type& __na) _NOEXCEPT
Howard Hinnantc51e1022010-05-11 19:42:16 +0000638 : __na_(__na),
639 __first_constructed(false),
640 __second_constructed(false)
641 {}
642
Eric Fiseliera85b1282017-04-18 21:08:06 +0000643#ifndef _LIBCPP_CXX03_LANG
Howard Hinnant756c69b2010-09-22 16:48:34 +0000644 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000645 __map_node_destructor(__tree_node_destructor<allocator_type>&& __x) _NOEXCEPT
Howard Hinnantc51e1022010-05-11 19:42:16 +0000646 : __na_(__x.__na_),
647 __first_constructed(__x.__value_constructed),
648 __second_constructed(__x.__value_constructed)
649 {
650 __x.__value_constructed = false;
651 }
Louis Dionne2b1ceaa2021-04-20 12:03:32 -0400652#endif // _LIBCPP_CXX03_LANG
Howard Hinnantc51e1022010-05-11 19:42:16 +0000653
Howard Hinnant756c69b2010-09-22 16:48:34 +0000654 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000655 void operator()(pointer __p) _NOEXCEPT
Howard Hinnantc51e1022010-05-11 19:42:16 +0000656 {
657 if (__second_constructed)
Erik Pilkingtond3fe2992018-06-04 20:38:23 +0000658 __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.__get_value().second));
Howard Hinnantc51e1022010-05-11 19:42:16 +0000659 if (__first_constructed)
Erik Pilkingtond3fe2992018-06-04 20:38:23 +0000660 __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.__get_value().first));
Howard Hinnantc51e1022010-05-11 19:42:16 +0000661 if (__p)
662 __alloc_traits::deallocate(__na_, __p, 1);
663 }
664};
665
Howard Hinnant944510a2011-06-14 19:58:17 +0000666template <class _Key, class _Tp, class _Compare, class _Allocator>
667 class map;
668template <class _Key, class _Tp, class _Compare, class _Allocator>
669 class multimap;
670template <class _TreeIterator> class __map_const_iterator;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000671
Eric Fiseliera00b4842016-02-20 05:28:30 +0000672#ifndef _LIBCPP_CXX03_LANG
Howard Hinnant89f8b792013-09-30 19:08:22 +0000673
674template <class _Key, class _Tp>
Amy Huang63f53b52021-03-15 14:20:49 -0700675struct _LIBCPP_STANDALONE_DEBUG __value_type
Howard Hinnant89f8b792013-09-30 19:08:22 +0000676{
677 typedef _Key key_type;
678 typedef _Tp mapped_type;
679 typedef pair<const key_type, mapped_type> value_type;
Erik Pilkingtond3fe2992018-06-04 20:38:23 +0000680 typedef pair<key_type&, mapped_type&> __nc_ref_pair_type;
681 typedef pair<key_type&&, mapped_type&&> __nc_rref_pair_type;
Howard Hinnant89f8b792013-09-30 19:08:22 +0000682
Erik Pilkingtond3fe2992018-06-04 20:38:23 +0000683private:
Howard Hinnant89f8b792013-09-30 19:08:22 +0000684 value_type __cc;
Erik Pilkingtond3fe2992018-06-04 20:38:23 +0000685
686public:
687 _LIBCPP_INLINE_VISIBILITY
688 value_type& __get_value()
689 {
690#if _LIBCPP_STD_VER > 14
691 return *_VSTD::launder(_VSTD::addressof(__cc));
692#else
693 return __cc;
694#endif
695 }
696
697 _LIBCPP_INLINE_VISIBILITY
698 const value_type& __get_value() const
699 {
700#if _LIBCPP_STD_VER > 14
701 return *_VSTD::launder(_VSTD::addressof(__cc));
702#else
703 return __cc;
704#endif
705 }
706
707 _LIBCPP_INLINE_VISIBILITY
708 __nc_ref_pair_type __ref()
709 {
710 value_type& __v = __get_value();
711 return __nc_ref_pair_type(const_cast<key_type&>(__v.first), __v.second);
712 }
713
714 _LIBCPP_INLINE_VISIBILITY
715 __nc_rref_pair_type __move()
716 {
717 value_type& __v = __get_value();
718 return __nc_rref_pair_type(
719 _VSTD::move(const_cast<key_type&>(__v.first)),
720 _VSTD::move(__v.second));
721 }
Howard Hinnant89f8b792013-09-30 19:08:22 +0000722
Howard Hinnant89f8b792013-09-30 19:08:22 +0000723 _LIBCPP_INLINE_VISIBILITY
724 __value_type& operator=(const __value_type& __v)
Erik Pilkingtond3fe2992018-06-04 20:38:23 +0000725 {
726 __ref() = __v.__get_value();
727 return *this;
728 }
Howard Hinnant89f8b792013-09-30 19:08:22 +0000729
730 _LIBCPP_INLINE_VISIBILITY
731 __value_type& operator=(__value_type&& __v)
Erik Pilkingtond3fe2992018-06-04 20:38:23 +0000732 {
733 __ref() = __v.__move();
734 return *this;
735 }
Howard Hinnant89f8b792013-09-30 19:08:22 +0000736
Eric Fiselierd06276b2016-03-31 02:15:15 +0000737 template <class _ValueTp,
738 class = typename enable_if<
739 __is_same_uncvref<_ValueTp, value_type>::value
740 >::type
741 >
Howard Hinnant89f8b792013-09-30 19:08:22 +0000742 _LIBCPP_INLINE_VISIBILITY
Erik Pilkingtond3fe2992018-06-04 20:38:23 +0000743 __value_type& operator=(_ValueTp&& __v)
744 {
745 __ref() = _VSTD::forward<_ValueTp>(__v);
746 return *this;
Eric Fiselierd06276b2016-03-31 02:15:15 +0000747 }
748
749private:
750 __value_type() _LIBCPP_EQUAL_DELETE;
751 ~__value_type() _LIBCPP_EQUAL_DELETE;
752 __value_type(const __value_type& __v) _LIBCPP_EQUAL_DELETE;
753 __value_type(__value_type&& __v) _LIBCPP_EQUAL_DELETE;
Howard Hinnant89f8b792013-09-30 19:08:22 +0000754};
755
756#else
757
758template <class _Key, class _Tp>
759struct __value_type
760{
761 typedef _Key key_type;
762 typedef _Tp mapped_type;
763 typedef pair<const key_type, mapped_type> value_type;
764
Erik Pilkingtond3fe2992018-06-04 20:38:23 +0000765private:
Howard Hinnant89f8b792013-09-30 19:08:22 +0000766 value_type __cc;
767
Erik Pilkingtond3fe2992018-06-04 20:38:23 +0000768public:
769 _LIBCPP_INLINE_VISIBILITY
770 value_type& __get_value() { return __cc; }
771 _LIBCPP_INLINE_VISIBILITY
772 const value_type& __get_value() const { return __cc; }
773
Eric Fiselierd06276b2016-03-31 02:15:15 +0000774private:
775 __value_type();
776 __value_type(__value_type const&);
777 __value_type& operator=(__value_type const&);
778 ~__value_type();
Howard Hinnant89f8b792013-09-30 19:08:22 +0000779};
780
Eric Fiseliera85b1282017-04-18 21:08:06 +0000781#endif // _LIBCPP_CXX03_LANG
Howard Hinnant89f8b792013-09-30 19:08:22 +0000782
Eric Fiselier44f9fd02015-03-03 20:10:01 +0000783template <class _Tp>
784struct __extract_key_value_types;
785
786template <class _Key, class _Tp>
787struct __extract_key_value_types<__value_type<_Key, _Tp> >
788{
789 typedef _Key const __key_type;
790 typedef _Tp __mapped_type;
791};
792
Howard Hinnantc51e1022010-05-11 19:42:16 +0000793template <class _TreeIterator>
Eric Fiselierb5eb1bf2017-01-04 23:56:00 +0000794class _LIBCPP_TEMPLATE_VIS __map_iterator
Howard Hinnantc51e1022010-05-11 19:42:16 +0000795{
Eric Fiseliera00b4842016-02-20 05:28:30 +0000796 typedef typename _TreeIterator::_NodeTypes _NodeTypes;
797 typedef typename _TreeIterator::__pointer_traits __pointer_traits;
798
Howard Hinnantc51e1022010-05-11 19:42:16 +0000799 _TreeIterator __i_;
800
Howard Hinnantc51e1022010-05-11 19:42:16 +0000801public:
802 typedef bidirectional_iterator_tag iterator_category;
Eric Fiseliera00b4842016-02-20 05:28:30 +0000803 typedef typename _NodeTypes::__map_value_type value_type;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000804 typedef typename _TreeIterator::difference_type difference_type;
805 typedef value_type& reference;
Eric Fiseliera00b4842016-02-20 05:28:30 +0000806 typedef typename _NodeTypes::__map_value_type_pointer pointer;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000807
Howard Hinnant756c69b2010-09-22 16:48:34 +0000808 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000809 __map_iterator() _NOEXCEPT {}
Howard Hinnantc51e1022010-05-11 19:42:16 +0000810
Howard Hinnant756c69b2010-09-22 16:48:34 +0000811 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000812 __map_iterator(_TreeIterator __i) _NOEXCEPT : __i_(__i) {}
Howard Hinnantc51e1022010-05-11 19:42:16 +0000813
Howard Hinnant756c69b2010-09-22 16:48:34 +0000814 _LIBCPP_INLINE_VISIBILITY
Erik Pilkingtond3fe2992018-06-04 20:38:23 +0000815 reference operator*() const {return __i_->__get_value();}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000816 _LIBCPP_INLINE_VISIBILITY
Erik Pilkingtond3fe2992018-06-04 20:38:23 +0000817 pointer operator->() const {return pointer_traits<pointer>::pointer_to(__i_->__get_value());}
Howard Hinnantc51e1022010-05-11 19:42:16 +0000818
Howard Hinnant756c69b2010-09-22 16:48:34 +0000819 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000820 __map_iterator& operator++() {++__i_; return *this;}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000821 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000822 __map_iterator operator++(int)
823 {
824 __map_iterator __t(*this);
825 ++(*this);
826 return __t;
827 }
828
Howard Hinnant756c69b2010-09-22 16:48:34 +0000829 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000830 __map_iterator& operator--() {--__i_; return *this;}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000831 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000832 __map_iterator operator--(int)
833 {
834 __map_iterator __t(*this);
835 --(*this);
836 return __t;
837 }
838
Howard Hinnant756c69b2010-09-22 16:48:34 +0000839 friend _LIBCPP_INLINE_VISIBILITY
840 bool operator==(const __map_iterator& __x, const __map_iterator& __y)
Howard Hinnantc51e1022010-05-11 19:42:16 +0000841 {return __x.__i_ == __y.__i_;}
Eric Fiseliercf8c0212017-01-05 06:06:18 +0000842 friend
Howard Hinnant756c69b2010-09-22 16:48:34 +0000843 _LIBCPP_INLINE_VISIBILITY
844 bool operator!=(const __map_iterator& __x, const __map_iterator& __y)
Howard Hinnantc51e1022010-05-11 19:42:16 +0000845 {return __x.__i_ != __y.__i_;}
846
Eric Fiselierb5eb1bf2017-01-04 23:56:00 +0000847 template <class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS map;
848 template <class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS multimap;
849 template <class> friend class _LIBCPP_TEMPLATE_VIS __map_const_iterator;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000850};
851
852template <class _TreeIterator>
Eric Fiselierb5eb1bf2017-01-04 23:56:00 +0000853class _LIBCPP_TEMPLATE_VIS __map_const_iterator
Howard Hinnantc51e1022010-05-11 19:42:16 +0000854{
Eric Fiseliera00b4842016-02-20 05:28:30 +0000855 typedef typename _TreeIterator::_NodeTypes _NodeTypes;
856 typedef typename _TreeIterator::__pointer_traits __pointer_traits;
857
Howard Hinnantc51e1022010-05-11 19:42:16 +0000858 _TreeIterator __i_;
859
Howard Hinnantc51e1022010-05-11 19:42:16 +0000860public:
861 typedef bidirectional_iterator_tag iterator_category;
Eric Fiseliera00b4842016-02-20 05:28:30 +0000862 typedef typename _NodeTypes::__map_value_type value_type;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000863 typedef typename _TreeIterator::difference_type difference_type;
864 typedef const value_type& reference;
Eric Fiseliera00b4842016-02-20 05:28:30 +0000865 typedef typename _NodeTypes::__const_map_value_type_pointer pointer;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000866
Howard Hinnant756c69b2010-09-22 16:48:34 +0000867 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000868 __map_const_iterator() _NOEXCEPT {}
Howard Hinnantc51e1022010-05-11 19:42:16 +0000869
Howard Hinnant756c69b2010-09-22 16:48:34 +0000870 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000871 __map_const_iterator(_TreeIterator __i) _NOEXCEPT : __i_(__i) {}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000872 _LIBCPP_INLINE_VISIBILITY
Eric Fiselier44f9fd02015-03-03 20:10:01 +0000873 __map_const_iterator(__map_iterator<
874 typename _TreeIterator::__non_const_iterator> __i) _NOEXCEPT
875 : __i_(__i.__i_) {}
Howard Hinnantc51e1022010-05-11 19:42:16 +0000876
Howard Hinnant756c69b2010-09-22 16:48:34 +0000877 _LIBCPP_INLINE_VISIBILITY
Erik Pilkingtond3fe2992018-06-04 20:38:23 +0000878 reference operator*() const {return __i_->__get_value();}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000879 _LIBCPP_INLINE_VISIBILITY
Erik Pilkingtond3fe2992018-06-04 20:38:23 +0000880 pointer operator->() const {return pointer_traits<pointer>::pointer_to(__i_->__get_value());}
Howard Hinnantc51e1022010-05-11 19:42:16 +0000881
Howard Hinnant756c69b2010-09-22 16:48:34 +0000882 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000883 __map_const_iterator& operator++() {++__i_; return *this;}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000884 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000885 __map_const_iterator operator++(int)
886 {
887 __map_const_iterator __t(*this);
888 ++(*this);
889 return __t;
890 }
891
Howard Hinnant756c69b2010-09-22 16:48:34 +0000892 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000893 __map_const_iterator& operator--() {--__i_; return *this;}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000894 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000895 __map_const_iterator operator--(int)
896 {
897 __map_const_iterator __t(*this);
898 --(*this);
899 return __t;
900 }
901
Howard Hinnant756c69b2010-09-22 16:48:34 +0000902 friend _LIBCPP_INLINE_VISIBILITY
903 bool operator==(const __map_const_iterator& __x, const __map_const_iterator& __y)
Howard Hinnantc51e1022010-05-11 19:42:16 +0000904 {return __x.__i_ == __y.__i_;}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000905 friend _LIBCPP_INLINE_VISIBILITY
906 bool operator!=(const __map_const_iterator& __x, const __map_const_iterator& __y)
Howard Hinnantc51e1022010-05-11 19:42:16 +0000907 {return __x.__i_ != __y.__i_;}
908
Eric Fiselierb5eb1bf2017-01-04 23:56:00 +0000909 template <class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS map;
910 template <class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS multimap;
911 template <class, class, class> friend class _LIBCPP_TEMPLATE_VIS __tree_const_iterator;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000912};
913
914template <class _Key, class _Tp, class _Compare = less<_Key>,
915 class _Allocator = allocator<pair<const _Key, _Tp> > >
Eric Fiselierb5eb1bf2017-01-04 23:56:00 +0000916class _LIBCPP_TEMPLATE_VIS map
Howard Hinnantc51e1022010-05-11 19:42:16 +0000917{
918public:
919 // types:
920 typedef _Key key_type;
921 typedef _Tp mapped_type;
922 typedef pair<const key_type, mapped_type> value_type;
Arthur O'Dwyer6a752e12021-03-03 11:10:49 -0500923 typedef __identity_t<_Compare> key_compare;
924 typedef __identity_t<_Allocator> allocator_type;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000925 typedef value_type& reference;
926 typedef const value_type& const_reference;
927
Marshall Clow5128cf32015-11-26 01:24:04 +0000928 static_assert((is_same<typename allocator_type::value_type, value_type>::value),
929 "Allocator::value_type must be same type as value_type");
930
Arthur O'Dwyerf5486c82021-05-25 14:34:18 -0400931_LIBCPP_SUPPRESS_DEPRECATED_PUSH
Eric Fiselierb5eb1bf2017-01-04 23:56:00 +0000932 class _LIBCPP_TEMPLATE_VIS value_compare
Arthur O'Dwyerf5486c82021-05-25 14:34:18 -0400933#if defined(_LIBCPP_ENABLE_CXX20_REMOVED_BINDER_TYPEDEFS)
Howard Hinnantc51e1022010-05-11 19:42:16 +0000934 : public binary_function<value_type, value_type, bool>
Arthur O'Dwyerf5486c82021-05-25 14:34:18 -0400935#endif
Howard Hinnantc51e1022010-05-11 19:42:16 +0000936 {
Arthur O'Dwyerf5486c82021-05-25 14:34:18 -0400937_LIBCPP_SUPPRESS_DEPRECATED_POP
Howard Hinnantc51e1022010-05-11 19:42:16 +0000938 friend class map;
939 protected:
940 key_compare comp;
941
Howard Hinnant756c69b2010-09-22 16:48:34 +0000942 _LIBCPP_INLINE_VISIBILITY value_compare(key_compare c) : comp(c) {}
Howard Hinnantc51e1022010-05-11 19:42:16 +0000943 public:
Arthur O'Dwyerf5486c82021-05-25 14:34:18 -0400944#if _LIBCPP_STD_VER <= 17 || defined(_LIBCPP_ENABLE_CXX20_REMOVED_BINDER_TYPEDEFS)
945 _LIBCPP_DEPRECATED_IN_CXX17 typedef bool result_type;
946 _LIBCPP_DEPRECATED_IN_CXX17 typedef value_type first_argument_type;
947 _LIBCPP_DEPRECATED_IN_CXX17 typedef value_type second_argument_type;
948#endif
Howard Hinnant756c69b2010-09-22 16:48:34 +0000949 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000950 bool operator()(const value_type& __x, const value_type& __y) const
951 {return comp(__x.first, __y.first);}
952 };
953
954private:
Howard Hinnant2d0046b2013-06-19 21:29:40 +0000955
Howard Hinnant89f8b792013-09-30 19:08:22 +0000956 typedef _VSTD::__value_type<key_type, mapped_type> __value_type;
Howard Hinnant90b91592013-07-05 18:06:00 +0000957 typedef __map_value_compare<key_type, __value_type, key_compare> __vc;
Marshall Clow940e01c2015-04-07 05:21:38 +0000958 typedef typename __rebind_alloc_helper<allocator_traits<allocator_type>,
959 __value_type>::type __allocator_type;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000960 typedef __tree<__value_type, __vc, __allocator_type> __base;
961 typedef typename __base::__node_traits __node_traits;
962 typedef allocator_traits<allocator_type> __alloc_traits;
963
964 __base __tree_;
965
966public:
967 typedef typename __alloc_traits::pointer pointer;
968 typedef typename __alloc_traits::const_pointer const_pointer;
969 typedef typename __alloc_traits::size_type size_type;
970 typedef typename __alloc_traits::difference_type difference_type;
Eric Fiselier44f9fd02015-03-03 20:10:01 +0000971 typedef __map_iterator<typename __base::iterator> iterator;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000972 typedef __map_const_iterator<typename __base::const_iterator> const_iterator;
Howard Hinnantb1ad5a82011-06-30 21:18:19 +0000973 typedef _VSTD::reverse_iterator<iterator> reverse_iterator;
974 typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000975
Erik Pilkingtonc37a3d82018-08-01 01:33:38 +0000976#if _LIBCPP_STD_VER > 14
977 typedef __map_node_handle<typename __base::__node, allocator_type> node_type;
978 typedef __insert_return_type<iterator, node_type> insert_return_type;
979#endif
980
Erik Pilkington82a65ad2018-10-31 17:31:35 +0000981 template <class _Key2, class _Value2, class _Comp2, class _Alloc2>
982 friend class _LIBCPP_TEMPLATE_VIS map;
983 template <class _Key2, class _Value2, class _Comp2, class _Alloc2>
984 friend class _LIBCPP_TEMPLATE_VIS multimap;
985
Howard Hinnant756c69b2010-09-22 16:48:34 +0000986 _LIBCPP_INLINE_VISIBILITY
Marshall Clow7086a5a2014-03-10 04:50:10 +0000987 map()
988 _NOEXCEPT_(
989 is_nothrow_default_constructible<allocator_type>::value &&
990 is_nothrow_default_constructible<key_compare>::value &&
991 is_nothrow_copy_constructible<key_compare>::value)
992 : __tree_(__vc(key_compare())) {}
993
994 _LIBCPP_INLINE_VISIBILITY
995 explicit map(const key_compare& __comp)
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000996 _NOEXCEPT_(
997 is_nothrow_default_constructible<allocator_type>::value &&
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000998 is_nothrow_copy_constructible<key_compare>::value)
Howard Hinnantc51e1022010-05-11 19:42:16 +0000999 : __tree_(__vc(__comp)) {}
1000
Howard Hinnant756c69b2010-09-22 16:48:34 +00001001 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001002 explicit map(const key_compare& __comp, const allocator_type& __a)
Marshall Clow657cbc42016-08-17 05:58:40 +00001003 : __tree_(__vc(__comp), typename __base::allocator_type(__a)) {}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001004
1005 template <class _InputIterator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001006 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001007 map(_InputIterator __f, _InputIterator __l,
1008 const key_compare& __comp = key_compare())
1009 : __tree_(__vc(__comp))
1010 {
1011 insert(__f, __l);
1012 }
1013
1014 template <class _InputIterator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001015 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001016 map(_InputIterator __f, _InputIterator __l,
1017 const key_compare& __comp, const allocator_type& __a)
Marshall Clow657cbc42016-08-17 05:58:40 +00001018 : __tree_(__vc(__comp), typename __base::allocator_type(__a))
Howard Hinnantc51e1022010-05-11 19:42:16 +00001019 {
1020 insert(__f, __l);
1021 }
1022
Marshall Clow300abfb2013-09-11 01:15:47 +00001023#if _LIBCPP_STD_VER > 11
1024 template <class _InputIterator>
Eric Fiseliercf8c0212017-01-05 06:06:18 +00001025 _LIBCPP_INLINE_VISIBILITY
Marshall Clow300abfb2013-09-11 01:15:47 +00001026 map(_InputIterator __f, _InputIterator __l, const allocator_type& __a)
1027 : map(__f, __l, key_compare(), __a) {}
1028#endif
1029
Howard Hinnant756c69b2010-09-22 16:48:34 +00001030 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001031 map(const map& __m)
1032 : __tree_(__m.__tree_)
1033 {
1034 insert(__m.begin(), __m.end());
1035 }
1036
Howard Hinnantd3a657f2011-07-01 19:24:36 +00001037 _LIBCPP_INLINE_VISIBILITY
1038 map& operator=(const map& __m)
1039 {
Marshall Clow476d3f42016-07-18 13:19:00 +00001040#ifndef _LIBCPP_CXX03_LANG
Howard Hinnantd3a657f2011-07-01 19:24:36 +00001041 __tree_ = __m.__tree_;
Howard Hinnant2d0046b2013-06-19 21:29:40 +00001042#else
Marshall Clowdb3cfcb2014-02-08 04:03:14 +00001043 if (this != &__m) {
1044 __tree_.clear();
1045 __tree_.value_comp() = __m.__tree_.value_comp();
1046 __tree_.__copy_assign_alloc(__m.__tree_);
1047 insert(__m.begin(), __m.end());
1048 }
Howard Hinnant2d0046b2013-06-19 21:29:40 +00001049#endif
Howard Hinnantd3a657f2011-07-01 19:24:36 +00001050 return *this;
1051 }
1052
Eric Fiseliera85b1282017-04-18 21:08:06 +00001053#ifndef _LIBCPP_CXX03_LANG
Howard Hinnantc51e1022010-05-11 19:42:16 +00001054
Howard Hinnant756c69b2010-09-22 16:48:34 +00001055 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001056 map(map&& __m)
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001057 _NOEXCEPT_(is_nothrow_move_constructible<__base>::value)
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001058 : __tree_(_VSTD::move(__m.__tree_))
Howard Hinnantc51e1022010-05-11 19:42:16 +00001059 {
1060 }
1061
1062 map(map&& __m, const allocator_type& __a);
1063
Howard Hinnant756c69b2010-09-22 16:48:34 +00001064 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant33711792011-08-12 21:56:02 +00001065 map& operator=(map&& __m)
1066 _NOEXCEPT_(is_nothrow_move_assignable<__base>::value)
1067 {
1068 __tree_ = _VSTD::move(__m.__tree_);
1069 return *this;
1070 }
1071
Howard Hinnant33711792011-08-12 21:56:02 +00001072 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001073 map(initializer_list<value_type> __il, const key_compare& __comp = key_compare())
1074 : __tree_(__vc(__comp))
1075 {
1076 insert(__il.begin(), __il.end());
1077 }
1078
Howard Hinnant756c69b2010-09-22 16:48:34 +00001079 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001080 map(initializer_list<value_type> __il, const key_compare& __comp, const allocator_type& __a)
Marshall Clow657cbc42016-08-17 05:58:40 +00001081 : __tree_(__vc(__comp), typename __base::allocator_type(__a))
Howard Hinnantc51e1022010-05-11 19:42:16 +00001082 {
1083 insert(__il.begin(), __il.end());
1084 }
1085
Marshall Clow300abfb2013-09-11 01:15:47 +00001086#if _LIBCPP_STD_VER > 11
Eric Fiseliercf8c0212017-01-05 06:06:18 +00001087 _LIBCPP_INLINE_VISIBILITY
Marshall Clow300abfb2013-09-11 01:15:47 +00001088 map(initializer_list<value_type> __il, const allocator_type& __a)
1089 : map(__il, key_compare(), __a) {}
1090#endif
1091
Howard Hinnant756c69b2010-09-22 16:48:34 +00001092 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001093 map& operator=(initializer_list<value_type> __il)
1094 {
1095 __tree_.__assign_unique(__il.begin(), __il.end());
1096 return *this;
1097 }
1098
Louis Dionne2b1ceaa2021-04-20 12:03:32 -04001099#endif // _LIBCPP_CXX03_LANG
Howard Hinnantc51e1022010-05-11 19:42:16 +00001100
Howard Hinnant756c69b2010-09-22 16:48:34 +00001101 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001102 explicit map(const allocator_type& __a)
Marshall Clow657cbc42016-08-17 05:58:40 +00001103 : __tree_(typename __base::allocator_type(__a))
Howard Hinnantc51e1022010-05-11 19:42:16 +00001104 {
1105 }
1106
Howard Hinnant756c69b2010-09-22 16:48:34 +00001107 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001108 map(const map& __m, const allocator_type& __a)
Marshall Clow657cbc42016-08-17 05:58:40 +00001109 : __tree_(__m.__tree_.value_comp(), typename __base::allocator_type(__a))
Howard Hinnantc51e1022010-05-11 19:42:16 +00001110 {
1111 insert(__m.begin(), __m.end());
1112 }
1113
Howard Hinnant756c69b2010-09-22 16:48:34 +00001114 _LIBCPP_INLINE_VISIBILITY
Louis Dionne69c42c02019-04-11 16:14:56 +00001115 ~map() {
1116 static_assert(sizeof(__diagnose_non_const_comparator<_Key, _Compare>()), "");
1117 }
1118
1119 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001120 iterator begin() _NOEXCEPT {return __tree_.begin();}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001121 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001122 const_iterator begin() const _NOEXCEPT {return __tree_.begin();}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001123 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001124 iterator end() _NOEXCEPT {return __tree_.end();}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001125 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001126 const_iterator end() const _NOEXCEPT {return __tree_.end();}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001127
Howard Hinnant756c69b2010-09-22 16:48:34 +00001128 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001129 reverse_iterator rbegin() _NOEXCEPT {return reverse_iterator(end());}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001130 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001131 const_reverse_iterator rbegin() const _NOEXCEPT
1132 {return const_reverse_iterator(end());}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001133 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001134 reverse_iterator rend() _NOEXCEPT
1135 {return reverse_iterator(begin());}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001136 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001137 const_reverse_iterator rend() const _NOEXCEPT
1138 {return const_reverse_iterator(begin());}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001139
Howard Hinnant756c69b2010-09-22 16:48:34 +00001140 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001141 const_iterator cbegin() const _NOEXCEPT {return begin();}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001142 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001143 const_iterator cend() const _NOEXCEPT {return end();}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001144 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001145 const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001146 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001147 const_reverse_iterator crend() const _NOEXCEPT {return rend();}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001148
Marshall Clow425f5752017-11-15 05:51:26 +00001149 _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001150 bool empty() const _NOEXCEPT {return __tree_.size() == 0;}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001151 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001152 size_type size() const _NOEXCEPT {return __tree_.size();}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001153 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001154 size_type max_size() const _NOEXCEPT {return __tree_.max_size();}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001155
1156 mapped_type& operator[](const key_type& __k);
Eric Fiselierd63f38e2016-03-31 03:13:37 +00001157#ifndef _LIBCPP_CXX03_LANG
Howard Hinnantc51e1022010-05-11 19:42:16 +00001158 mapped_type& operator[](key_type&& __k);
1159#endif
1160
1161 mapped_type& at(const key_type& __k);
1162 const mapped_type& at(const key_type& __k) const;
1163
Howard Hinnant756c69b2010-09-22 16:48:34 +00001164 _LIBCPP_INLINE_VISIBILITY
Marshall Clow657cbc42016-08-17 05:58:40 +00001165 allocator_type get_allocator() const _NOEXCEPT {return allocator_type(__tree_.__alloc());}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001166 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001167 key_compare key_comp() const {return __tree_.value_comp().key_comp();}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001168 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001169 value_compare value_comp() const {return value_compare(__tree_.value_comp().key_comp());}
1170
Eric Fiselierd06276b2016-03-31 02:15:15 +00001171#ifndef _LIBCPP_CXX03_LANG
1172 template <class ..._Args>
1173 _LIBCPP_INLINE_VISIBILITY
1174 pair<iterator, bool> emplace(_Args&& ...__args) {
1175 return __tree_.__emplace_unique(_VSTD::forward<_Args>(__args)...);
1176 }
Howard Hinnant74279a52010-09-04 23:28:19 +00001177
Howard Hinnant29eb9b82012-05-25 22:04:21 +00001178 template <class ..._Args>
Eric Fiselierd06276b2016-03-31 02:15:15 +00001179 _LIBCPP_INLINE_VISIBILITY
1180 iterator emplace_hint(const_iterator __p, _Args&& ...__args) {
1181 return __tree_.__emplace_hint_unique(__p.__i_, _VSTD::forward<_Args>(__args)...);
1182 }
Howard Hinnant74279a52010-09-04 23:28:19 +00001183
Howard Hinnantc834c512011-11-29 18:15:50 +00001184 template <class _Pp,
1185 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001186 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc834c512011-11-29 18:15:50 +00001187 pair<iterator, bool> insert(_Pp&& __p)
1188 {return __tree_.__insert_unique(_VSTD::forward<_Pp>(__p));}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001189
Howard Hinnantc834c512011-11-29 18:15:50 +00001190 template <class _Pp,
1191 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001192 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc834c512011-11-29 18:15:50 +00001193 iterator insert(const_iterator __pos, _Pp&& __p)
1194 {return __tree_.__insert_unique(__pos.__i_, _VSTD::forward<_Pp>(__p));}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001195
Louis Dionne2b1ceaa2021-04-20 12:03:32 -04001196#endif // _LIBCPP_CXX03_LANG
Howard Hinnantc51e1022010-05-11 19:42:16 +00001197
Howard Hinnant756c69b2010-09-22 16:48:34 +00001198 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001199 pair<iterator, bool>
1200 insert(const value_type& __v) {return __tree_.__insert_unique(__v);}
1201
Howard Hinnant756c69b2010-09-22 16:48:34 +00001202 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001203 iterator
1204 insert(const_iterator __p, const value_type& __v)
1205 {return __tree_.__insert_unique(__p.__i_, __v);}
1206
Eric Fiselierd6143132016-04-18 01:40:45 +00001207#ifndef _LIBCPP_CXX03_LANG
Marshall Clowd430d022016-01-05 19:32:41 +00001208 _LIBCPP_INLINE_VISIBILITY
1209 pair<iterator, bool>
Eric Fiselierd06276b2016-03-31 02:15:15 +00001210 insert(value_type&& __v) {return __tree_.__insert_unique(_VSTD::move(__v));}
Marshall Clowd430d022016-01-05 19:32:41 +00001211
1212 _LIBCPP_INLINE_VISIBILITY
Eric Fiselierd06276b2016-03-31 02:15:15 +00001213 iterator insert(const_iterator __p, value_type&& __v)
1214 {return __tree_.__insert_unique(__p.__i_, _VSTD::move(__v));}
Eric Fiseliera85b1282017-04-18 21:08:06 +00001215
1216 _LIBCPP_INLINE_VISIBILITY
1217 void insert(initializer_list<value_type> __il)
1218 {insert(__il.begin(), __il.end());}
Marshall Clowd430d022016-01-05 19:32:41 +00001219#endif
1220
Howard Hinnantc51e1022010-05-11 19:42:16 +00001221 template <class _InputIterator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001222 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001223 void insert(_InputIterator __f, _InputIterator __l)
1224 {
1225 for (const_iterator __e = cend(); __f != __l; ++__f)
1226 insert(__e.__i_, *__f);
1227 }
1228
Marshall Clow3223db82015-07-07 03:37:33 +00001229#if _LIBCPP_STD_VER > 14
Eric Fiselierd63f38e2016-03-31 03:13:37 +00001230
Marshall Clow3223db82015-07-07 03:37:33 +00001231 template <class... _Args>
1232 _LIBCPP_INLINE_VISIBILITY
1233 pair<iterator, bool> try_emplace(const key_type& __k, _Args&&... __args)
1234 {
Eric Fiselierd63f38e2016-03-31 03:13:37 +00001235 return __tree_.__emplace_unique_key_args(__k,
1236 _VSTD::piecewise_construct,
1237 _VSTD::forward_as_tuple(__k),
1238 _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...));
Marshall Clow3223db82015-07-07 03:37:33 +00001239 }
1240
1241 template <class... _Args>
1242 _LIBCPP_INLINE_VISIBILITY
1243 pair<iterator, bool> try_emplace(key_type&& __k, _Args&&... __args)
1244 {
Eric Fiselierd63f38e2016-03-31 03:13:37 +00001245 return __tree_.__emplace_unique_key_args(__k,
1246 _VSTD::piecewise_construct,
1247 _VSTD::forward_as_tuple(_VSTD::move(__k)),
1248 _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...));
Marshall Clow3223db82015-07-07 03:37:33 +00001249 }
1250
1251 template <class... _Args>
1252 _LIBCPP_INLINE_VISIBILITY
1253 iterator try_emplace(const_iterator __h, const key_type& __k, _Args&&... __args)
1254 {
Eric Fiselierd63f38e2016-03-31 03:13:37 +00001255 return __tree_.__emplace_hint_unique_key_args(__h.__i_, __k,
1256 _VSTD::piecewise_construct,
1257 _VSTD::forward_as_tuple(__k),
Mark de Wever1ba476f2020-09-19 15:39:09 +02001258 _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...)).first;
Marshall Clow3223db82015-07-07 03:37:33 +00001259 }
1260
1261 template <class... _Args>
1262 _LIBCPP_INLINE_VISIBILITY
1263 iterator try_emplace(const_iterator __h, key_type&& __k, _Args&&... __args)
1264 {
Eric Fiselierd63f38e2016-03-31 03:13:37 +00001265 return __tree_.__emplace_hint_unique_key_args(__h.__i_, __k,
1266 _VSTD::piecewise_construct,
1267 _VSTD::forward_as_tuple(_VSTD::move(__k)),
Mark de Wever1ba476f2020-09-19 15:39:09 +02001268 _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...)).first;
Marshall Clow3223db82015-07-07 03:37:33 +00001269 }
1270
1271 template <class _Vp>
1272 _LIBCPP_INLINE_VISIBILITY
1273 pair<iterator, bool> insert_or_assign(const key_type& __k, _Vp&& __v)
1274 {
1275 iterator __p = lower_bound(__k);
1276 if ( __p != end() && !key_comp()(__k, __p->first))
1277 {
1278 __p->second = _VSTD::forward<_Vp>(__v);
1279 return _VSTD::make_pair(__p, false);
1280 }
1281 return _VSTD::make_pair(emplace_hint(__p, __k, _VSTD::forward<_Vp>(__v)), true);
1282 }
Eric Fiselierd63f38e2016-03-31 03:13:37 +00001283
Marshall Clow3223db82015-07-07 03:37:33 +00001284 template <class _Vp>
1285 _LIBCPP_INLINE_VISIBILITY
1286 pair<iterator, bool> insert_or_assign(key_type&& __k, _Vp&& __v)
1287 {
1288 iterator __p = lower_bound(__k);
1289 if ( __p != end() && !key_comp()(__k, __p->first))
1290 {
1291 __p->second = _VSTD::forward<_Vp>(__v);
1292 return _VSTD::make_pair(__p, false);
1293 }
1294 return _VSTD::make_pair(emplace_hint(__p, _VSTD::move(__k), _VSTD::forward<_Vp>(__v)), true);
1295 }
1296
1297 template <class _Vp>
Mark de Wever1ba476f2020-09-19 15:39:09 +02001298 _LIBCPP_INLINE_VISIBILITY iterator insert_or_assign(const_iterator __h,
1299 const key_type& __k,
1300 _Vp&& __v) {
1301 auto [__r, __inserted] = __tree_.__emplace_hint_unique_key_args(
1302 __h.__i_, __k, __k, _VSTD::forward<_Vp>(__v));
1303
1304 if (!__inserted)
1305 __r->__get_value().second = _VSTD::forward<_Vp>(__v);
1306
1307 return __r;
1308 }
Marshall Clow3223db82015-07-07 03:37:33 +00001309
1310 template <class _Vp>
Mark de Wever1ba476f2020-09-19 15:39:09 +02001311 _LIBCPP_INLINE_VISIBILITY iterator insert_or_assign(const_iterator __h,
1312 key_type&& __k,
1313 _Vp&& __v) {
1314 auto [__r, __inserted] = __tree_.__emplace_hint_unique_key_args(
1315 __h.__i_, __k, _VSTD::move(__k), _VSTD::forward<_Vp>(__v));
1316
1317 if (!__inserted)
1318 __r->__get_value().second = _VSTD::forward<_Vp>(__v);
1319
1320 return __r;
1321 }
Eric Fiselierd63f38e2016-03-31 03:13:37 +00001322
Eric Fiseliera85b1282017-04-18 21:08:06 +00001323#endif // _LIBCPP_STD_VER > 14
Marshall Clow3223db82015-07-07 03:37:33 +00001324
Howard Hinnant756c69b2010-09-22 16:48:34 +00001325 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001326 iterator erase(const_iterator __p) {return __tree_.erase(__p.__i_);}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001327 _LIBCPP_INLINE_VISIBILITY
Marshall Clow22ea5b82015-05-10 13:35:00 +00001328 iterator erase(iterator __p) {return __tree_.erase(__p.__i_);}
1329 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001330 size_type erase(const key_type& __k)
1331 {return __tree_.__erase_unique(__k);}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001332 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001333 iterator erase(const_iterator __f, const_iterator __l)
1334 {return __tree_.erase(__f.__i_, __l.__i_);}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001335 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001336 void clear() _NOEXCEPT {__tree_.clear();}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001337
Erik Pilkingtonc37a3d82018-08-01 01:33:38 +00001338#if _LIBCPP_STD_VER > 14
1339 _LIBCPP_INLINE_VISIBILITY
1340 insert_return_type insert(node_type&& __nh)
1341 {
1342 _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(),
1343 "node_type with incompatible allocator passed to map::insert()");
1344 return __tree_.template __node_handle_insert_unique<
1345 node_type, insert_return_type>(_VSTD::move(__nh));
1346 }
1347 _LIBCPP_INLINE_VISIBILITY
1348 iterator insert(const_iterator __hint, node_type&& __nh)
1349 {
1350 _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(),
1351 "node_type with incompatible allocator passed to map::insert()");
1352 return __tree_.template __node_handle_insert_unique<node_type>(
1353 __hint.__i_, _VSTD::move(__nh));
1354 }
1355 _LIBCPP_INLINE_VISIBILITY
1356 node_type extract(key_type const& __key)
1357 {
1358 return __tree_.template __node_handle_extract<node_type>(__key);
1359 }
1360 _LIBCPP_INLINE_VISIBILITY
1361 node_type extract(const_iterator __it)
1362 {
1363 return __tree_.template __node_handle_extract<node_type>(__it.__i_);
1364 }
Louis Dionned2322c82018-11-01 14:41:37 +00001365 template <class _Compare2>
Erik Pilkington82a65ad2018-10-31 17:31:35 +00001366 _LIBCPP_INLINE_VISIBILITY
Louis Dionned2322c82018-11-01 14:41:37 +00001367 void merge(map<key_type, mapped_type, _Compare2, allocator_type>& __source)
Erik Pilkington82a65ad2018-10-31 17:31:35 +00001368 {
1369 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
1370 "merging container with incompatible allocator");
1371 __tree_.__node_handle_merge_unique(__source.__tree_);
1372 }
Louis Dionned2322c82018-11-01 14:41:37 +00001373 template <class _Compare2>
Erik Pilkington82a65ad2018-10-31 17:31:35 +00001374 _LIBCPP_INLINE_VISIBILITY
Louis Dionned2322c82018-11-01 14:41:37 +00001375 void merge(map<key_type, mapped_type, _Compare2, allocator_type>&& __source)
Erik Pilkington82a65ad2018-10-31 17:31:35 +00001376 {
1377 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
1378 "merging container with incompatible allocator");
1379 __tree_.__node_handle_merge_unique(__source.__tree_);
1380 }
Louis Dionned2322c82018-11-01 14:41:37 +00001381 template <class _Compare2>
Erik Pilkington82a65ad2018-10-31 17:31:35 +00001382 _LIBCPP_INLINE_VISIBILITY
Louis Dionned2322c82018-11-01 14:41:37 +00001383 void merge(multimap<key_type, mapped_type, _Compare2, allocator_type>& __source)
Erik Pilkington82a65ad2018-10-31 17:31:35 +00001384 {
1385 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
1386 "merging container with incompatible allocator");
1387 __tree_.__node_handle_merge_unique(__source.__tree_);
1388 }
Louis Dionned2322c82018-11-01 14:41:37 +00001389 template <class _Compare2>
Erik Pilkington82a65ad2018-10-31 17:31:35 +00001390 _LIBCPP_INLINE_VISIBILITY
Louis Dionned2322c82018-11-01 14:41:37 +00001391 void merge(multimap<key_type, mapped_type, _Compare2, allocator_type>&& __source)
Erik Pilkington82a65ad2018-10-31 17:31:35 +00001392 {
1393 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
1394 "merging container with incompatible allocator");
1395 __tree_.__node_handle_merge_unique(__source.__tree_);
1396 }
Erik Pilkingtonc37a3d82018-08-01 01:33:38 +00001397#endif
1398
Howard Hinnant756c69b2010-09-22 16:48:34 +00001399 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001400 void swap(map& __m)
1401 _NOEXCEPT_(__is_nothrow_swappable<__base>::value)
1402 {__tree_.swap(__m.__tree_);}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001403
Howard Hinnant756c69b2010-09-22 16:48:34 +00001404 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001405 iterator find(const key_type& __k) {return __tree_.find(__k);}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001406 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001407 const_iterator find(const key_type& __k) const {return __tree_.find(__k);}
Marshall Clowebb57322013-08-13 22:18:47 +00001408#if _LIBCPP_STD_VER > 11
1409 template <typename _K2>
1410 _LIBCPP_INLINE_VISIBILITY
1411 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
1412 find(const _K2& __k) {return __tree_.find(__k);}
1413 template <typename _K2>
1414 _LIBCPP_INLINE_VISIBILITY
1415 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
1416 find(const _K2& __k) const {return __tree_.find(__k);}
1417#endif
1418
Howard Hinnant756c69b2010-09-22 16:48:34 +00001419 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001420 size_type count(const key_type& __k) const
1421 {return __tree_.__count_unique(__k);}
Marshall Clowe6a5f522014-08-24 23:54:16 +00001422#if _LIBCPP_STD_VER > 11
1423 template <typename _K2>
1424 _LIBCPP_INLINE_VISIBILITY
1425 typename enable_if<__is_transparent<_Compare, _K2>::value,size_type>::type
Eric Fiseliera85c9e92018-02-10 02:53:47 +00001426 count(const _K2& __k) const {return __tree_.__count_multi(__k);}
Marshall Clowe6a5f522014-08-24 23:54:16 +00001427#endif
Zoe Carver3ffbab12019-07-16 03:21:01 +00001428
1429#if _LIBCPP_STD_VER > 17
1430 _LIBCPP_INLINE_VISIBILITY
1431 bool contains(const key_type& __k) const {return find(__k) != end();}
Marek Kurdejd7e019e2021-04-13 17:10:55 +02001432 template <typename _K2>
1433 _LIBCPP_INLINE_VISIBILITY
1434 typename enable_if<__is_transparent<_Compare, _K2>::value, bool>::type
1435 contains(const _K2& __k) const { return find(__k) != end(); }
Zoe Carver3ffbab12019-07-16 03:21:01 +00001436#endif // _LIBCPP_STD_VER > 17
1437
Howard Hinnant756c69b2010-09-22 16:48:34 +00001438 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001439 iterator lower_bound(const key_type& __k)
1440 {return __tree_.lower_bound(__k);}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001441 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001442 const_iterator lower_bound(const key_type& __k) const
1443 {return __tree_.lower_bound(__k);}
Marshall Clowebb57322013-08-13 22:18:47 +00001444#if _LIBCPP_STD_VER > 11
1445 template <typename _K2>
1446 _LIBCPP_INLINE_VISIBILITY
1447 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
1448 lower_bound(const _K2& __k) {return __tree_.lower_bound(__k);}
1449
1450 template <typename _K2>
1451 _LIBCPP_INLINE_VISIBILITY
1452 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
1453 lower_bound(const _K2& __k) const {return __tree_.lower_bound(__k);}
1454#endif
1455
Howard Hinnant756c69b2010-09-22 16:48:34 +00001456 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001457 iterator upper_bound(const key_type& __k)
1458 {return __tree_.upper_bound(__k);}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001459 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001460 const_iterator upper_bound(const key_type& __k) const
1461 {return __tree_.upper_bound(__k);}
Marshall Clowebb57322013-08-13 22:18:47 +00001462#if _LIBCPP_STD_VER > 11
1463 template <typename _K2>
1464 _LIBCPP_INLINE_VISIBILITY
1465 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
1466 upper_bound(const _K2& __k) {return __tree_.upper_bound(__k);}
1467 template <typename _K2>
1468 _LIBCPP_INLINE_VISIBILITY
1469 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
1470 upper_bound(const _K2& __k) const {return __tree_.upper_bound(__k);}
1471#endif
1472
Howard Hinnant756c69b2010-09-22 16:48:34 +00001473 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001474 pair<iterator,iterator> equal_range(const key_type& __k)
1475 {return __tree_.__equal_range_unique(__k);}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001476 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001477 pair<const_iterator,const_iterator> equal_range(const key_type& __k) const
1478 {return __tree_.__equal_range_unique(__k);}
Marshall Clowebb57322013-08-13 22:18:47 +00001479#if _LIBCPP_STD_VER > 11
1480 template <typename _K2>
1481 _LIBCPP_INLINE_VISIBILITY
1482 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<iterator,iterator>>::type
Eric Fiseliera85c9e92018-02-10 02:53:47 +00001483 equal_range(const _K2& __k) {return __tree_.__equal_range_multi(__k);}
Marshall Clowebb57322013-08-13 22:18:47 +00001484 template <typename _K2>
1485 _LIBCPP_INLINE_VISIBILITY
1486 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<const_iterator,const_iterator>>::type
Eric Fiseliera85c9e92018-02-10 02:53:47 +00001487 equal_range(const _K2& __k) const {return __tree_.__equal_range_multi(__k);}
Marshall Clowebb57322013-08-13 22:18:47 +00001488#endif
Howard Hinnantc51e1022010-05-11 19:42:16 +00001489
1490private:
1491 typedef typename __base::__node __node;
1492 typedef typename __base::__node_allocator __node_allocator;
1493 typedef typename __base::__node_pointer __node_pointer;
Howard Hinnantc51e1022010-05-11 19:42:16 +00001494 typedef typename __base::__node_base_pointer __node_base_pointer;
Eric Fiseliercf8c0212017-01-05 06:06:18 +00001495 typedef typename __base::__parent_pointer __parent_pointer;
Eric Fiseliera92b0732016-02-20 07:12:17 +00001496
Howard Hinnantc834c512011-11-29 18:15:50 +00001497 typedef __map_node_destructor<__node_allocator> _Dp;
1498 typedef unique_ptr<__node, _Dp> __node_holder;
Howard Hinnantc51e1022010-05-11 19:42:16 +00001499
Eric Fiselierd63f38e2016-03-31 03:13:37 +00001500#ifdef _LIBCPP_CXX03_LANG
Howard Hinnantac7e7482013-07-04 20:59:16 +00001501 __node_holder __construct_node_with_key(const key_type& __k);
Eric Fiselierd63f38e2016-03-31 03:13:37 +00001502#endif
Howard Hinnantc51e1022010-05-11 19:42:16 +00001503};
1504
Louis Dionned59f8a52021-08-17 11:59:07 -04001505#if _LIBCPP_STD_VER >= 17
Louis Dionned23a5f22019-06-20 19:32:00 +00001506template<class _InputIterator, class _Compare = less<__iter_key_type<_InputIterator>>,
1507 class _Allocator = allocator<__iter_to_alloc_type<_InputIterator>>,
Louis Dionne6c7da9a2019-07-19 17:13:39 +00001508 class = _EnableIf<!__is_allocator<_Compare>::value, void>,
1509 class = _EnableIf<__is_allocator<_Allocator>::value, void>>
Louis Dionned23a5f22019-06-20 19:32:00 +00001510map(_InputIterator, _InputIterator, _Compare = _Compare(), _Allocator = _Allocator())
1511 -> map<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>, _Compare, _Allocator>;
1512
1513template<class _Key, class _Tp, class _Compare = less<remove_const_t<_Key>>,
1514 class _Allocator = allocator<pair<const _Key, _Tp>>,
Louis Dionne6c7da9a2019-07-19 17:13:39 +00001515 class = _EnableIf<!__is_allocator<_Compare>::value, void>,
1516 class = _EnableIf<__is_allocator<_Allocator>::value, void>>
Louis Dionned23a5f22019-06-20 19:32:00 +00001517map(initializer_list<pair<_Key, _Tp>>, _Compare = _Compare(), _Allocator = _Allocator())
1518 -> map<remove_const_t<_Key>, _Tp, _Compare, _Allocator>;
1519
1520template<class _InputIterator, class _Allocator,
Louis Dionne6c7da9a2019-07-19 17:13:39 +00001521 class = _EnableIf<__is_allocator<_Allocator>::value, void>>
Louis Dionned23a5f22019-06-20 19:32:00 +00001522map(_InputIterator, _InputIterator, _Allocator)
1523 -> map<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>,
1524 less<__iter_key_type<_InputIterator>>, _Allocator>;
1525
1526template<class _Key, class _Tp, class _Allocator,
Louis Dionne6c7da9a2019-07-19 17:13:39 +00001527 class = _EnableIf<__is_allocator<_Allocator>::value, void>>
Louis Dionned23a5f22019-06-20 19:32:00 +00001528map(initializer_list<pair<_Key, _Tp>>, _Allocator)
1529 -> map<remove_const_t<_Key>, _Tp, less<remove_const_t<_Key>>, _Allocator>;
1530#endif
Eric Fiseliera92b0732016-02-20 07:12:17 +00001531
Eric Fiselierd06276b2016-03-31 02:15:15 +00001532#ifndef _LIBCPP_CXX03_LANG
Howard Hinnantc51e1022010-05-11 19:42:16 +00001533template <class _Key, class _Tp, class _Compare, class _Allocator>
1534map<_Key, _Tp, _Compare, _Allocator>::map(map&& __m, const allocator_type& __a)
Marshall Clow657cbc42016-08-17 05:58:40 +00001535 : __tree_(_VSTD::move(__m.__tree_), typename __base::allocator_type(__a))
Howard Hinnantc51e1022010-05-11 19:42:16 +00001536{
1537 if (__a != __m.get_allocator())
1538 {
1539 const_iterator __e = cend();
1540 while (!__m.empty())
1541 __tree_.__insert_unique(__e.__i_,
Erik Pilkingtond3fe2992018-06-04 20:38:23 +00001542 __m.__tree_.remove(__m.begin().__i_)->__value_.__move());
Howard Hinnantc51e1022010-05-11 19:42:16 +00001543 }
1544}
1545
Eric Fiseliera85b1282017-04-18 21:08:06 +00001546template <class _Key, class _Tp, class _Compare, class _Allocator>
1547_Tp&
1548map<_Key, _Tp, _Compare, _Allocator>::operator[](const key_type& __k)
1549{
1550 return __tree_.__emplace_unique_key_args(__k,
1551 _VSTD::piecewise_construct,
1552 _VSTD::forward_as_tuple(__k),
Erik Pilkingtond3fe2992018-06-04 20:38:23 +00001553 _VSTD::forward_as_tuple()).first->__get_value().second;
Eric Fiseliera85b1282017-04-18 21:08:06 +00001554}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001555
Eric Fiseliera85b1282017-04-18 21:08:06 +00001556template <class _Key, class _Tp, class _Compare, class _Allocator>
1557_Tp&
1558map<_Key, _Tp, _Compare, _Allocator>::operator[](key_type&& __k)
1559{
1560 return __tree_.__emplace_unique_key_args(__k,
1561 _VSTD::piecewise_construct,
1562 _VSTD::forward_as_tuple(_VSTD::move(__k)),
Erik Pilkingtond3fe2992018-06-04 20:38:23 +00001563 _VSTD::forward_as_tuple()).first->__get_value().second;
Eric Fiseliera85b1282017-04-18 21:08:06 +00001564}
Eric Fiselierd63f38e2016-03-31 03:13:37 +00001565
Eric Fiseliera85b1282017-04-18 21:08:06 +00001566#else // _LIBCPP_CXX03_LANG
Eric Fiselierd63f38e2016-03-31 03:13:37 +00001567
Howard Hinnantc51e1022010-05-11 19:42:16 +00001568template <class _Key, class _Tp, class _Compare, class _Allocator>
1569typename map<_Key, _Tp, _Compare, _Allocator>::__node_holder
Howard Hinnantac7e7482013-07-04 20:59:16 +00001570map<_Key, _Tp, _Compare, _Allocator>::__construct_node_with_key(const key_type& __k)
Howard Hinnantc51e1022010-05-11 19:42:16 +00001571{
1572 __node_allocator& __na = __tree_.__node_alloc();
Howard Hinnantc834c512011-11-29 18:15:50 +00001573 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
Erik Pilkingtond3fe2992018-06-04 20:38:23 +00001574 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__get_value().first), __k);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001575 __h.get_deleter().__first_constructed = true;
Erik Pilkingtond3fe2992018-06-04 20:38:23 +00001576 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__get_value().second));
Howard Hinnantc51e1022010-05-11 19:42:16 +00001577 __h.get_deleter().__second_constructed = true;
Louis Dionne7b844362020-07-30 09:42:23 -04001578 return __h;
Howard Hinnantc51e1022010-05-11 19:42:16 +00001579}
1580
Howard Hinnantc51e1022010-05-11 19:42:16 +00001581template <class _Key, class _Tp, class _Compare, class _Allocator>
1582_Tp&
1583map<_Key, _Tp, _Compare, _Allocator>::operator[](const key_type& __k)
1584{
Eric Fiseliercf8c0212017-01-05 06:06:18 +00001585 __parent_pointer __parent;
1586 __node_base_pointer& __child = __tree_.__find_equal(__parent, __k);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001587 __node_pointer __r = static_cast<__node_pointer>(__child);
1588 if (__child == nullptr)
1589 {
Howard Hinnantac7e7482013-07-04 20:59:16 +00001590 __node_holder __h = __construct_node_with_key(__k);
Howard Hinnant2d0046b2013-06-19 21:29:40 +00001591 __tree_.__insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
Howard Hinnantc51e1022010-05-11 19:42:16 +00001592 __r = __h.release();
1593 }
Erik Pilkingtond3fe2992018-06-04 20:38:23 +00001594 return __r->__value_.__get_value().second;
Howard Hinnantc51e1022010-05-11 19:42:16 +00001595}
1596
Louis Dionne2b1ceaa2021-04-20 12:03:32 -04001597#endif // _LIBCPP_CXX03_LANG
Howard Hinnantc51e1022010-05-11 19:42:16 +00001598
1599template <class _Key, class _Tp, class _Compare, class _Allocator>
1600_Tp&
1601map<_Key, _Tp, _Compare, _Allocator>::at(const key_type& __k)
1602{
Eric Fiseliercf8c0212017-01-05 06:06:18 +00001603 __parent_pointer __parent;
1604 __node_base_pointer& __child = __tree_.__find_equal(__parent, __k);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001605 if (__child == nullptr)
Louis Dionne2b239162019-02-12 16:06:02 +00001606 __throw_out_of_range("map::at: key not found");
Erik Pilkingtond3fe2992018-06-04 20:38:23 +00001607 return static_cast<__node_pointer>(__child)->__value_.__get_value().second;
Howard Hinnantc51e1022010-05-11 19:42:16 +00001608}
1609
1610template <class _Key, class _Tp, class _Compare, class _Allocator>
1611const _Tp&
1612map<_Key, _Tp, _Compare, _Allocator>::at(const key_type& __k) const
1613{
Eric Fiseliercf8c0212017-01-05 06:06:18 +00001614 __parent_pointer __parent;
1615 __node_base_pointer __child = __tree_.__find_equal(__parent, __k);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001616 if (__child == nullptr)
Louis Dionne2b239162019-02-12 16:06:02 +00001617 __throw_out_of_range("map::at: key not found");
Erik Pilkingtond3fe2992018-06-04 20:38:23 +00001618 return static_cast<__node_pointer>(__child)->__value_.__get_value().second;
Howard Hinnantc51e1022010-05-11 19:42:16 +00001619}
1620
Howard Hinnantc51e1022010-05-11 19:42:16 +00001621
1622template <class _Key, class _Tp, class _Compare, class _Allocator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001623inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001624bool
1625operator==(const map<_Key, _Tp, _Compare, _Allocator>& __x,
1626 const map<_Key, _Tp, _Compare, _Allocator>& __y)
1627{
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001628 return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin());
Howard Hinnantc51e1022010-05-11 19:42:16 +00001629}
1630
1631template <class _Key, class _Tp, class _Compare, class _Allocator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001632inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001633bool
1634operator< (const map<_Key, _Tp, _Compare, _Allocator>& __x,
1635 const map<_Key, _Tp, _Compare, _Allocator>& __y)
1636{
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001637 return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
Howard Hinnantc51e1022010-05-11 19:42:16 +00001638}
1639
1640template <class _Key, class _Tp, class _Compare, class _Allocator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001641inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001642bool
1643operator!=(const map<_Key, _Tp, _Compare, _Allocator>& __x,
1644 const map<_Key, _Tp, _Compare, _Allocator>& __y)
1645{
1646 return !(__x == __y);
1647}
1648
1649template <class _Key, class _Tp, class _Compare, class _Allocator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001650inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001651bool
1652operator> (const map<_Key, _Tp, _Compare, _Allocator>& __x,
1653 const map<_Key, _Tp, _Compare, _Allocator>& __y)
1654{
1655 return __y < __x;
1656}
1657
1658template <class _Key, class _Tp, class _Compare, class _Allocator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001659inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001660bool
1661operator>=(const map<_Key, _Tp, _Compare, _Allocator>& __x,
1662 const map<_Key, _Tp, _Compare, _Allocator>& __y)
1663{
1664 return !(__x < __y);
1665}
1666
1667template <class _Key, class _Tp, class _Compare, class _Allocator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001668inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001669bool
1670operator<=(const map<_Key, _Tp, _Compare, _Allocator>& __x,
1671 const map<_Key, _Tp, _Compare, _Allocator>& __y)
1672{
1673 return !(__y < __x);
1674}
1675
1676template <class _Key, class _Tp, class _Compare, class _Allocator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001677inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001678void
1679swap(map<_Key, _Tp, _Compare, _Allocator>& __x,
1680 map<_Key, _Tp, _Compare, _Allocator>& __y)
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001681 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
Howard Hinnantc51e1022010-05-11 19:42:16 +00001682{
1683 __x.swap(__y);
1684}
1685
Marshall Clow29b53f22018-12-14 18:49:35 +00001686#if _LIBCPP_STD_VER > 17
Marek Kurdeja98b1412020-05-02 13:58:03 +02001687template <class _Key, class _Tp, class _Compare, class _Allocator,
1688 class _Predicate>
Marshall Clow29b53f22018-12-14 18:49:35 +00001689inline _LIBCPP_INLINE_VISIBILITY
Marek Kurdeja98b1412020-05-02 13:58:03 +02001690 typename map<_Key, _Tp, _Compare, _Allocator>::size_type
1691 erase_if(map<_Key, _Tp, _Compare, _Allocator>& __c, _Predicate __pred) {
Arthur O'Dwyerb6738bd2021-03-21 16:53:09 -04001692 return _VSTD::__libcpp_erase_if_container(__c, __pred);
Marek Kurdeja98b1412020-05-02 13:58:03 +02001693}
Marshall Clow29b53f22018-12-14 18:49:35 +00001694#endif
1695
1696
Howard Hinnantc51e1022010-05-11 19:42:16 +00001697template <class _Key, class _Tp, class _Compare = less<_Key>,
1698 class _Allocator = allocator<pair<const _Key, _Tp> > >
Eric Fiselierb5eb1bf2017-01-04 23:56:00 +00001699class _LIBCPP_TEMPLATE_VIS multimap
Howard Hinnantc51e1022010-05-11 19:42:16 +00001700{
1701public:
1702 // types:
1703 typedef _Key key_type;
1704 typedef _Tp mapped_type;
1705 typedef pair<const key_type, mapped_type> value_type;
Arthur O'Dwyer6a752e12021-03-03 11:10:49 -05001706 typedef __identity_t<_Compare> key_compare;
1707 typedef __identity_t<_Allocator> allocator_type;
Howard Hinnantc51e1022010-05-11 19:42:16 +00001708 typedef value_type& reference;
1709 typedef const value_type& const_reference;
1710
Marshall Clow5128cf32015-11-26 01:24:04 +00001711 static_assert((is_same<typename allocator_type::value_type, value_type>::value),
1712 "Allocator::value_type must be same type as value_type");
1713
Arthur O'Dwyerf5486c82021-05-25 14:34:18 -04001714_LIBCPP_SUPPRESS_DEPRECATED_PUSH
Eric Fiselierb5eb1bf2017-01-04 23:56:00 +00001715 class _LIBCPP_TEMPLATE_VIS value_compare
Arthur O'Dwyerf5486c82021-05-25 14:34:18 -04001716#if defined(_LIBCPP_ENABLE_CXX20_REMOVED_BINDER_TYPEDEFS)
Howard Hinnantc51e1022010-05-11 19:42:16 +00001717 : public binary_function<value_type, value_type, bool>
Arthur O'Dwyerf5486c82021-05-25 14:34:18 -04001718#endif
Howard Hinnantc51e1022010-05-11 19:42:16 +00001719 {
Arthur O'Dwyerf5486c82021-05-25 14:34:18 -04001720_LIBCPP_SUPPRESS_DEPRECATED_POP
Howard Hinnantc51e1022010-05-11 19:42:16 +00001721 friend class multimap;
1722 protected:
1723 key_compare comp;
1724
Howard Hinnant756c69b2010-09-22 16:48:34 +00001725 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001726 value_compare(key_compare c) : comp(c) {}
1727 public:
Arthur O'Dwyerf5486c82021-05-25 14:34:18 -04001728#if _LIBCPP_STD_VER <= 17 || defined(_LIBCPP_ENABLE_CXX20_REMOVED_BINDER_TYPEDEFS)
1729 _LIBCPP_DEPRECATED_IN_CXX17 typedef bool result_type;
1730 _LIBCPP_DEPRECATED_IN_CXX17 typedef value_type first_argument_type;
1731 _LIBCPP_DEPRECATED_IN_CXX17 typedef value_type second_argument_type;
1732#endif
Howard Hinnant756c69b2010-09-22 16:48:34 +00001733 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001734 bool operator()(const value_type& __x, const value_type& __y) const
1735 {return comp(__x.first, __y.first);}
1736 };
1737
1738private:
Howard Hinnant2d0046b2013-06-19 21:29:40 +00001739
Howard Hinnant89f8b792013-09-30 19:08:22 +00001740 typedef _VSTD::__value_type<key_type, mapped_type> __value_type;
Howard Hinnant90b91592013-07-05 18:06:00 +00001741 typedef __map_value_compare<key_type, __value_type, key_compare> __vc;
Marshall Clow940e01c2015-04-07 05:21:38 +00001742 typedef typename __rebind_alloc_helper<allocator_traits<allocator_type>,
1743 __value_type>::type __allocator_type;
Howard Hinnantc51e1022010-05-11 19:42:16 +00001744 typedef __tree<__value_type, __vc, __allocator_type> __base;
1745 typedef typename __base::__node_traits __node_traits;
1746 typedef allocator_traits<allocator_type> __alloc_traits;
1747
1748 __base __tree_;
1749
1750public:
1751 typedef typename __alloc_traits::pointer pointer;
1752 typedef typename __alloc_traits::const_pointer const_pointer;
1753 typedef typename __alloc_traits::size_type size_type;
1754 typedef typename __alloc_traits::difference_type difference_type;
1755 typedef __map_iterator<typename __base::iterator> iterator;
1756 typedef __map_const_iterator<typename __base::const_iterator> const_iterator;
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001757 typedef _VSTD::reverse_iterator<iterator> reverse_iterator;
1758 typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator;
Howard Hinnantc51e1022010-05-11 19:42:16 +00001759
Erik Pilkingtonc37a3d82018-08-01 01:33:38 +00001760#if _LIBCPP_STD_VER > 14
1761 typedef __map_node_handle<typename __base::__node, allocator_type> node_type;
1762#endif
1763
Erik Pilkington82a65ad2018-10-31 17:31:35 +00001764 template <class _Key2, class _Value2, class _Comp2, class _Alloc2>
1765 friend class _LIBCPP_TEMPLATE_VIS map;
1766 template <class _Key2, class _Value2, class _Comp2, class _Alloc2>
1767 friend class _LIBCPP_TEMPLATE_VIS multimap;
1768
Howard Hinnant756c69b2010-09-22 16:48:34 +00001769 _LIBCPP_INLINE_VISIBILITY
Marshall Clow7086a5a2014-03-10 04:50:10 +00001770 multimap()
1771 _NOEXCEPT_(
1772 is_nothrow_default_constructible<allocator_type>::value &&
1773 is_nothrow_default_constructible<key_compare>::value &&
1774 is_nothrow_copy_constructible<key_compare>::value)
1775 : __tree_(__vc(key_compare())) {}
1776
1777 _LIBCPP_INLINE_VISIBILITY
1778 explicit multimap(const key_compare& __comp)
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001779 _NOEXCEPT_(
1780 is_nothrow_default_constructible<allocator_type>::value &&
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001781 is_nothrow_copy_constructible<key_compare>::value)
Howard Hinnantc51e1022010-05-11 19:42:16 +00001782 : __tree_(__vc(__comp)) {}
1783
Howard Hinnant756c69b2010-09-22 16:48:34 +00001784 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001785 explicit multimap(const key_compare& __comp, const allocator_type& __a)
Marshall Clow657cbc42016-08-17 05:58:40 +00001786 : __tree_(__vc(__comp), typename __base::allocator_type(__a)) {}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001787
1788 template <class _InputIterator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001789 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001790 multimap(_InputIterator __f, _InputIterator __l,
1791 const key_compare& __comp = key_compare())
1792 : __tree_(__vc(__comp))
1793 {
1794 insert(__f, __l);
1795 }
1796
1797 template <class _InputIterator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001798 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001799 multimap(_InputIterator __f, _InputIterator __l,
1800 const key_compare& __comp, const allocator_type& __a)
Marshall Clow657cbc42016-08-17 05:58:40 +00001801 : __tree_(__vc(__comp), typename __base::allocator_type(__a))
Howard Hinnantc51e1022010-05-11 19:42:16 +00001802 {
1803 insert(__f, __l);
1804 }
1805
Marshall Clow300abfb2013-09-11 01:15:47 +00001806#if _LIBCPP_STD_VER > 11
1807 template <class _InputIterator>
Eric Fiseliercf8c0212017-01-05 06:06:18 +00001808 _LIBCPP_INLINE_VISIBILITY
Marshall Clow300abfb2013-09-11 01:15:47 +00001809 multimap(_InputIterator __f, _InputIterator __l, const allocator_type& __a)
1810 : multimap(__f, __l, key_compare(), __a) {}
1811#endif
1812
Howard Hinnant756c69b2010-09-22 16:48:34 +00001813 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001814 multimap(const multimap& __m)
1815 : __tree_(__m.__tree_.value_comp(),
1816 __alloc_traits::select_on_container_copy_construction(__m.__tree_.__alloc()))
1817 {
1818 insert(__m.begin(), __m.end());
1819 }
1820
Howard Hinnantd3a657f2011-07-01 19:24:36 +00001821 _LIBCPP_INLINE_VISIBILITY
1822 multimap& operator=(const multimap& __m)
1823 {
Marshall Clow476d3f42016-07-18 13:19:00 +00001824#ifndef _LIBCPP_CXX03_LANG
Howard Hinnantd3a657f2011-07-01 19:24:36 +00001825 __tree_ = __m.__tree_;
Howard Hinnant2d0046b2013-06-19 21:29:40 +00001826#else
Marshall Clowdb3cfcb2014-02-08 04:03:14 +00001827 if (this != &__m) {
1828 __tree_.clear();
1829 __tree_.value_comp() = __m.__tree_.value_comp();
1830 __tree_.__copy_assign_alloc(__m.__tree_);
1831 insert(__m.begin(), __m.end());
1832 }
Howard Hinnant2d0046b2013-06-19 21:29:40 +00001833#endif
Howard Hinnantd3a657f2011-07-01 19:24:36 +00001834 return *this;
1835 }
1836
Eric Fiseliera85b1282017-04-18 21:08:06 +00001837#ifndef _LIBCPP_CXX03_LANG
Howard Hinnantc51e1022010-05-11 19:42:16 +00001838
Howard Hinnant756c69b2010-09-22 16:48:34 +00001839 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001840 multimap(multimap&& __m)
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001841 _NOEXCEPT_(is_nothrow_move_constructible<__base>::value)
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001842 : __tree_(_VSTD::move(__m.__tree_))
Howard Hinnantc51e1022010-05-11 19:42:16 +00001843 {
1844 }
1845
1846 multimap(multimap&& __m, const allocator_type& __a);
1847
Howard Hinnant756c69b2010-09-22 16:48:34 +00001848 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant33711792011-08-12 21:56:02 +00001849 multimap& operator=(multimap&& __m)
1850 _NOEXCEPT_(is_nothrow_move_assignable<__base>::value)
1851 {
1852 __tree_ = _VSTD::move(__m.__tree_);
1853 return *this;
1854 }
1855
Howard Hinnant33711792011-08-12 21:56:02 +00001856 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001857 multimap(initializer_list<value_type> __il, const key_compare& __comp = key_compare())
1858 : __tree_(__vc(__comp))
1859 {
1860 insert(__il.begin(), __il.end());
1861 }
1862
Howard Hinnant756c69b2010-09-22 16:48:34 +00001863 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001864 multimap(initializer_list<value_type> __il, const key_compare& __comp, const allocator_type& __a)
Marshall Clow657cbc42016-08-17 05:58:40 +00001865 : __tree_(__vc(__comp), typename __base::allocator_type(__a))
Howard Hinnantc51e1022010-05-11 19:42:16 +00001866 {
1867 insert(__il.begin(), __il.end());
1868 }
1869
Marshall Clow300abfb2013-09-11 01:15:47 +00001870#if _LIBCPP_STD_VER > 11
Eric Fiseliercf8c0212017-01-05 06:06:18 +00001871 _LIBCPP_INLINE_VISIBILITY
Marshall Clow300abfb2013-09-11 01:15:47 +00001872 multimap(initializer_list<value_type> __il, const allocator_type& __a)
1873 : multimap(__il, key_compare(), __a) {}
1874#endif
1875
Howard Hinnant756c69b2010-09-22 16:48:34 +00001876 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001877 multimap& operator=(initializer_list<value_type> __il)
1878 {
1879 __tree_.__assign_multi(__il.begin(), __il.end());
1880 return *this;
1881 }
Howard Hinnant33711792011-08-12 21:56:02 +00001882
Louis Dionne2b1ceaa2021-04-20 12:03:32 -04001883#endif // _LIBCPP_CXX03_LANG
Howard Hinnantc51e1022010-05-11 19:42:16 +00001884
Howard Hinnant756c69b2010-09-22 16:48:34 +00001885 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001886 explicit multimap(const allocator_type& __a)
Marshall Clow657cbc42016-08-17 05:58:40 +00001887 : __tree_(typename __base::allocator_type(__a))
Howard Hinnantc51e1022010-05-11 19:42:16 +00001888 {
1889 }
1890
Howard Hinnant756c69b2010-09-22 16:48:34 +00001891 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001892 multimap(const multimap& __m, const allocator_type& __a)
Marshall Clow657cbc42016-08-17 05:58:40 +00001893 : __tree_(__m.__tree_.value_comp(), typename __base::allocator_type(__a))
Howard Hinnantc51e1022010-05-11 19:42:16 +00001894 {
1895 insert(__m.begin(), __m.end());
1896 }
1897
Howard Hinnant756c69b2010-09-22 16:48:34 +00001898 _LIBCPP_INLINE_VISIBILITY
Louis Dionne69c42c02019-04-11 16:14:56 +00001899 ~multimap() {
1900 static_assert(sizeof(__diagnose_non_const_comparator<_Key, _Compare>()), "");
1901 }
1902
1903 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001904 iterator begin() _NOEXCEPT {return __tree_.begin();}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001905 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001906 const_iterator begin() const _NOEXCEPT {return __tree_.begin();}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001907 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001908 iterator end() _NOEXCEPT {return __tree_.end();}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001909 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001910 const_iterator end() const _NOEXCEPT {return __tree_.end();}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001911
Howard Hinnant756c69b2010-09-22 16:48:34 +00001912 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001913 reverse_iterator rbegin() _NOEXCEPT {return reverse_iterator(end());}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001914 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001915 const_reverse_iterator rbegin() const _NOEXCEPT
1916 {return const_reverse_iterator(end());}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001917 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001918 reverse_iterator rend() _NOEXCEPT {return reverse_iterator(begin());}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001919 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001920 const_reverse_iterator rend() const _NOEXCEPT
1921 {return const_reverse_iterator(begin());}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001922
Howard Hinnant756c69b2010-09-22 16:48:34 +00001923 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001924 const_iterator cbegin() const _NOEXCEPT {return begin();}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001925 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001926 const_iterator cend() const _NOEXCEPT {return end();}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001927 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001928 const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001929 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001930 const_reverse_iterator crend() const _NOEXCEPT {return rend();}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001931
Marshall Clow425f5752017-11-15 05:51:26 +00001932 _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001933 bool empty() const _NOEXCEPT {return __tree_.size() == 0;}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001934 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001935 size_type size() const _NOEXCEPT {return __tree_.size();}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001936 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001937 size_type max_size() const _NOEXCEPT {return __tree_.max_size();}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001938
Howard Hinnant756c69b2010-09-22 16:48:34 +00001939 _LIBCPP_INLINE_VISIBILITY
Marshall Clow657cbc42016-08-17 05:58:40 +00001940 allocator_type get_allocator() const _NOEXCEPT {return allocator_type(__tree_.__alloc());}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001941 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001942 key_compare key_comp() const {return __tree_.value_comp().key_comp();}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001943 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001944 value_compare value_comp() const
1945 {return value_compare(__tree_.value_comp().key_comp());}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001946
Eric Fiselierd06276b2016-03-31 02:15:15 +00001947#ifndef _LIBCPP_CXX03_LANG
Howard Hinnant74279a52010-09-04 23:28:19 +00001948
Howard Hinnant29eb9b82012-05-25 22:04:21 +00001949 template <class ..._Args>
Eric Fiselierd06276b2016-03-31 02:15:15 +00001950 _LIBCPP_INLINE_VISIBILITY
1951 iterator emplace(_Args&& ...__args) {
1952 return __tree_.__emplace_multi(_VSTD::forward<_Args>(__args)...);
1953 }
Howard Hinnantc51e1022010-05-11 19:42:16 +00001954
Howard Hinnant29eb9b82012-05-25 22:04:21 +00001955 template <class ..._Args>
Eric Fiselierd06276b2016-03-31 02:15:15 +00001956 _LIBCPP_INLINE_VISIBILITY
1957 iterator emplace_hint(const_iterator __p, _Args&& ...__args) {
1958 return __tree_.__emplace_hint_multi(__p.__i_, _VSTD::forward<_Args>(__args)...);
1959 }
Howard Hinnant74279a52010-09-04 23:28:19 +00001960
Howard Hinnantc834c512011-11-29 18:15:50 +00001961 template <class _Pp,
1962 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001963 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc834c512011-11-29 18:15:50 +00001964 iterator insert(_Pp&& __p)
1965 {return __tree_.__insert_multi(_VSTD::forward<_Pp>(__p));}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001966
Howard Hinnantc834c512011-11-29 18:15:50 +00001967 template <class _Pp,
1968 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001969 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc834c512011-11-29 18:15:50 +00001970 iterator insert(const_iterator __pos, _Pp&& __p)
1971 {return __tree_.__insert_multi(__pos.__i_, _VSTD::forward<_Pp>(__p));}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001972
Eric Fiselierd6143132016-04-18 01:40:45 +00001973 _LIBCPP_INLINE_VISIBILITY
1974 iterator insert(value_type&& __v)
1975 {return __tree_.__insert_multi(_VSTD::move(__v));}
1976
1977 _LIBCPP_INLINE_VISIBILITY
1978 iterator insert(const_iterator __p, value_type&& __v)
1979 {return __tree_.__insert_multi(__p.__i_, _VSTD::move(__v));}
1980
Eric Fiseliera85b1282017-04-18 21:08:06 +00001981
1982 _LIBCPP_INLINE_VISIBILITY
1983 void insert(initializer_list<value_type> __il)
1984 {insert(__il.begin(), __il.end());}
1985
Louis Dionne2b1ceaa2021-04-20 12:03:32 -04001986#endif // _LIBCPP_CXX03_LANG
Howard Hinnantc51e1022010-05-11 19:42:16 +00001987
Howard Hinnant756c69b2010-09-22 16:48:34 +00001988 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001989 iterator insert(const value_type& __v) {return __tree_.__insert_multi(__v);}
1990
Howard Hinnant756c69b2010-09-22 16:48:34 +00001991 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001992 iterator insert(const_iterator __p, const value_type& __v)
1993 {return __tree_.__insert_multi(__p.__i_, __v);}
1994
1995 template <class _InputIterator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001996 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001997 void insert(_InputIterator __f, _InputIterator __l)
1998 {
1999 for (const_iterator __e = cend(); __f != __l; ++__f)
2000 __tree_.__insert_multi(__e.__i_, *__f);
2001 }
2002
Howard Hinnant756c69b2010-09-22 16:48:34 +00002003 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00002004 iterator erase(const_iterator __p) {return __tree_.erase(__p.__i_);}
Howard Hinnant756c69b2010-09-22 16:48:34 +00002005 _LIBCPP_INLINE_VISIBILITY
Marshall Clow22ea5b82015-05-10 13:35:00 +00002006 iterator erase(iterator __p) {return __tree_.erase(__p.__i_);}
2007 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00002008 size_type erase(const key_type& __k) {return __tree_.__erase_multi(__k);}
Howard Hinnant756c69b2010-09-22 16:48:34 +00002009 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00002010 iterator erase(const_iterator __f, const_iterator __l)
2011 {return __tree_.erase(__f.__i_, __l.__i_);}
Erik Pilkingtonc37a3d82018-08-01 01:33:38 +00002012
2013#if _LIBCPP_STD_VER > 14
2014 _LIBCPP_INLINE_VISIBILITY
2015 iterator insert(node_type&& __nh)
2016 {
2017 _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(),
2018 "node_type with incompatible allocator passed to multimap::insert()");
2019 return __tree_.template __node_handle_insert_multi<node_type>(
2020 _VSTD::move(__nh));
2021 }
2022 _LIBCPP_INLINE_VISIBILITY
2023 iterator insert(const_iterator __hint, node_type&& __nh)
2024 {
2025 _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(),
2026 "node_type with incompatible allocator passed to multimap::insert()");
2027 return __tree_.template __node_handle_insert_multi<node_type>(
2028 __hint.__i_, _VSTD::move(__nh));
2029 }
2030 _LIBCPP_INLINE_VISIBILITY
2031 node_type extract(key_type const& __key)
2032 {
2033 return __tree_.template __node_handle_extract<node_type>(__key);
2034 }
2035 _LIBCPP_INLINE_VISIBILITY
2036 node_type extract(const_iterator __it)
2037 {
2038 return __tree_.template __node_handle_extract<node_type>(
2039 __it.__i_);
2040 }
Louis Dionned2322c82018-11-01 14:41:37 +00002041 template <class _Compare2>
Erik Pilkington82a65ad2018-10-31 17:31:35 +00002042 _LIBCPP_INLINE_VISIBILITY
Louis Dionned2322c82018-11-01 14:41:37 +00002043 void merge(multimap<key_type, mapped_type, _Compare2, allocator_type>& __source)
Erik Pilkington82a65ad2018-10-31 17:31:35 +00002044 {
2045 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
2046 "merging container with incompatible allocator");
2047 return __tree_.__node_handle_merge_multi(__source.__tree_);
2048 }
Louis Dionned2322c82018-11-01 14:41:37 +00002049 template <class _Compare2>
Erik Pilkington82a65ad2018-10-31 17:31:35 +00002050 _LIBCPP_INLINE_VISIBILITY
Louis Dionned2322c82018-11-01 14:41:37 +00002051 void merge(multimap<key_type, mapped_type, _Compare2, allocator_type>&& __source)
Erik Pilkington82a65ad2018-10-31 17:31:35 +00002052 {
2053 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
2054 "merging container with incompatible allocator");
2055 return __tree_.__node_handle_merge_multi(__source.__tree_);
2056 }
Louis Dionned2322c82018-11-01 14:41:37 +00002057 template <class _Compare2>
Erik Pilkington82a65ad2018-10-31 17:31:35 +00002058 _LIBCPP_INLINE_VISIBILITY
Louis Dionned2322c82018-11-01 14:41:37 +00002059 void merge(map<key_type, mapped_type, _Compare2, allocator_type>& __source)
Erik Pilkington82a65ad2018-10-31 17:31:35 +00002060 {
2061 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
2062 "merging container with incompatible allocator");
2063 return __tree_.__node_handle_merge_multi(__source.__tree_);
2064 }
Louis Dionned2322c82018-11-01 14:41:37 +00002065 template <class _Compare2>
Erik Pilkington82a65ad2018-10-31 17:31:35 +00002066 _LIBCPP_INLINE_VISIBILITY
Louis Dionned2322c82018-11-01 14:41:37 +00002067 void merge(map<key_type, mapped_type, _Compare2, allocator_type>&& __source)
Erik Pilkington82a65ad2018-10-31 17:31:35 +00002068 {
2069 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
2070 "merging container with incompatible allocator");
2071 return __tree_.__node_handle_merge_multi(__source.__tree_);
2072 }
Erik Pilkingtonc37a3d82018-08-01 01:33:38 +00002073#endif
2074
Howard Hinnant756c69b2010-09-22 16:48:34 +00002075 _LIBCPP_INLINE_VISIBILITY
Marshall Clowde1312a2018-08-22 04:28:43 +00002076 void clear() _NOEXCEPT {__tree_.clear();}
Howard Hinnantc51e1022010-05-11 19:42:16 +00002077
Howard Hinnant756c69b2010-09-22 16:48:34 +00002078 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00002079 void swap(multimap& __m)
2080 _NOEXCEPT_(__is_nothrow_swappable<__base>::value)
2081 {__tree_.swap(__m.__tree_);}
Howard Hinnantc51e1022010-05-11 19:42:16 +00002082
Howard Hinnant756c69b2010-09-22 16:48:34 +00002083 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00002084 iterator find(const key_type& __k) {return __tree_.find(__k);}
Howard Hinnant756c69b2010-09-22 16:48:34 +00002085 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00002086 const_iterator find(const key_type& __k) const {return __tree_.find(__k);}
Marshall Clowebb57322013-08-13 22:18:47 +00002087#if _LIBCPP_STD_VER > 11
2088 template <typename _K2>
2089 _LIBCPP_INLINE_VISIBILITY
2090 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
2091 find(const _K2& __k) {return __tree_.find(__k);}
2092 template <typename _K2>
2093 _LIBCPP_INLINE_VISIBILITY
2094 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
2095 find(const _K2& __k) const {return __tree_.find(__k);}
2096#endif
2097
Howard Hinnant756c69b2010-09-22 16:48:34 +00002098 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00002099 size_type count(const key_type& __k) const
2100 {return __tree_.__count_multi(__k);}
Marshall Clowe6a5f522014-08-24 23:54:16 +00002101#if _LIBCPP_STD_VER > 11
2102 template <typename _K2>
2103 _LIBCPP_INLINE_VISIBILITY
2104 typename enable_if<__is_transparent<_Compare, _K2>::value,size_type>::type
Marshall Clow141e47b2015-06-30 18:15:41 +00002105 count(const _K2& __k) const {return __tree_.__count_multi(__k);}
Marshall Clowe6a5f522014-08-24 23:54:16 +00002106#endif
Zoe Carver3ffbab12019-07-16 03:21:01 +00002107
2108#if _LIBCPP_STD_VER > 17
2109 _LIBCPP_INLINE_VISIBILITY
2110 bool contains(const key_type& __k) const {return find(__k) != end();}
Marek Kurdejd7e019e2021-04-13 17:10:55 +02002111 template <typename _K2>
2112 _LIBCPP_INLINE_VISIBILITY
2113 typename enable_if<__is_transparent<_Compare, _K2>::value, bool>::type
2114 contains(const _K2& __k) const { return find(__k) != end(); }
Zoe Carver3ffbab12019-07-16 03:21:01 +00002115#endif // _LIBCPP_STD_VER > 17
2116
Howard Hinnant756c69b2010-09-22 16:48:34 +00002117 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00002118 iterator lower_bound(const key_type& __k)
2119 {return __tree_.lower_bound(__k);}
Howard Hinnant756c69b2010-09-22 16:48:34 +00002120 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00002121 const_iterator lower_bound(const key_type& __k) const
2122 {return __tree_.lower_bound(__k);}
Marshall Clowebb57322013-08-13 22:18:47 +00002123#if _LIBCPP_STD_VER > 11
2124 template <typename _K2>
2125 _LIBCPP_INLINE_VISIBILITY
2126 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
2127 lower_bound(const _K2& __k) {return __tree_.lower_bound(__k);}
2128
2129 template <typename _K2>
2130 _LIBCPP_INLINE_VISIBILITY
2131 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
2132 lower_bound(const _K2& __k) const {return __tree_.lower_bound(__k);}
2133#endif
2134
Howard Hinnant756c69b2010-09-22 16:48:34 +00002135 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00002136 iterator upper_bound(const key_type& __k)
2137 {return __tree_.upper_bound(__k);}
Howard Hinnant756c69b2010-09-22 16:48:34 +00002138 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00002139 const_iterator upper_bound(const key_type& __k) const
2140 {return __tree_.upper_bound(__k);}
Marshall Clowebb57322013-08-13 22:18:47 +00002141#if _LIBCPP_STD_VER > 11
2142 template <typename _K2>
2143 _LIBCPP_INLINE_VISIBILITY
2144 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
2145 upper_bound(const _K2& __k) {return __tree_.upper_bound(__k);}
2146 template <typename _K2>
2147 _LIBCPP_INLINE_VISIBILITY
2148 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
2149 upper_bound(const _K2& __k) const {return __tree_.upper_bound(__k);}
2150#endif
2151
Howard Hinnant756c69b2010-09-22 16:48:34 +00002152 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00002153 pair<iterator,iterator> equal_range(const key_type& __k)
2154 {return __tree_.__equal_range_multi(__k);}
Howard Hinnant756c69b2010-09-22 16:48:34 +00002155 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00002156 pair<const_iterator,const_iterator> equal_range(const key_type& __k) const
2157 {return __tree_.__equal_range_multi(__k);}
Marshall Clowebb57322013-08-13 22:18:47 +00002158#if _LIBCPP_STD_VER > 11
2159 template <typename _K2>
2160 _LIBCPP_INLINE_VISIBILITY
2161 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<iterator,iterator>>::type
2162 equal_range(const _K2& __k) {return __tree_.__equal_range_multi(__k);}
2163 template <typename _K2>
2164 _LIBCPP_INLINE_VISIBILITY
2165 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<const_iterator,const_iterator>>::type
2166 equal_range(const _K2& __k) const {return __tree_.__equal_range_multi(__k);}
2167#endif
Howard Hinnantc51e1022010-05-11 19:42:16 +00002168
2169private:
2170 typedef typename __base::__node __node;
2171 typedef typename __base::__node_allocator __node_allocator;
2172 typedef typename __base::__node_pointer __node_pointer;
Eric Fiseliera92b0732016-02-20 07:12:17 +00002173
Howard Hinnantc834c512011-11-29 18:15:50 +00002174 typedef __map_node_destructor<__node_allocator> _Dp;
2175 typedef unique_ptr<__node, _Dp> __node_holder;
Howard Hinnantc51e1022010-05-11 19:42:16 +00002176};
2177
Louis Dionned59f8a52021-08-17 11:59:07 -04002178#if _LIBCPP_STD_VER >= 17
Louis Dionned23a5f22019-06-20 19:32:00 +00002179template<class _InputIterator, class _Compare = less<__iter_key_type<_InputIterator>>,
2180 class _Allocator = allocator<__iter_to_alloc_type<_InputIterator>>,
Louis Dionne6c7da9a2019-07-19 17:13:39 +00002181 class = _EnableIf<!__is_allocator<_Compare>::value, void>,
2182 class = _EnableIf<__is_allocator<_Allocator>::value, void>>
Louis Dionned23a5f22019-06-20 19:32:00 +00002183multimap(_InputIterator, _InputIterator, _Compare = _Compare(), _Allocator = _Allocator())
2184 -> multimap<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>, _Compare, _Allocator>;
2185
2186template<class _Key, class _Tp, class _Compare = less<remove_const_t<_Key>>,
2187 class _Allocator = allocator<pair<const _Key, _Tp>>,
Louis Dionne6c7da9a2019-07-19 17:13:39 +00002188 class = _EnableIf<!__is_allocator<_Compare>::value, void>,
2189 class = _EnableIf<__is_allocator<_Allocator>::value, void>>
Louis Dionned23a5f22019-06-20 19:32:00 +00002190multimap(initializer_list<pair<_Key, _Tp>>, _Compare = _Compare(), _Allocator = _Allocator())
2191 -> multimap<remove_const_t<_Key>, _Tp, _Compare, _Allocator>;
2192
2193template<class _InputIterator, class _Allocator,
Louis Dionne6c7da9a2019-07-19 17:13:39 +00002194 class = _EnableIf<__is_allocator<_Allocator>::value, void>>
Louis Dionned23a5f22019-06-20 19:32:00 +00002195multimap(_InputIterator, _InputIterator, _Allocator)
2196 -> multimap<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>,
2197 less<__iter_key_type<_InputIterator>>, _Allocator>;
2198
2199template<class _Key, class _Tp, class _Allocator,
Louis Dionne6c7da9a2019-07-19 17:13:39 +00002200 class = _EnableIf<__is_allocator<_Allocator>::value, void>>
Louis Dionned23a5f22019-06-20 19:32:00 +00002201multimap(initializer_list<pair<_Key, _Tp>>, _Allocator)
2202 -> multimap<remove_const_t<_Key>, _Tp, less<remove_const_t<_Key>>, _Allocator>;
2203#endif
2204
Eric Fiselierd06276b2016-03-31 02:15:15 +00002205#ifndef _LIBCPP_CXX03_LANG
Howard Hinnantc51e1022010-05-11 19:42:16 +00002206template <class _Key, class _Tp, class _Compare, class _Allocator>
2207multimap<_Key, _Tp, _Compare, _Allocator>::multimap(multimap&& __m, const allocator_type& __a)
Marshall Clow657cbc42016-08-17 05:58:40 +00002208 : __tree_(_VSTD::move(__m.__tree_), typename __base::allocator_type(__a))
Howard Hinnantc51e1022010-05-11 19:42:16 +00002209{
2210 if (__a != __m.get_allocator())
2211 {
2212 const_iterator __e = cend();
2213 while (!__m.empty())
2214 __tree_.__insert_multi(__e.__i_,
Erik Pilkingtond3fe2992018-06-04 20:38:23 +00002215 _VSTD::move(__m.__tree_.remove(__m.begin().__i_)->__value_.__move()));
Howard Hinnantc51e1022010-05-11 19:42:16 +00002216 }
2217}
Eric Fiselierd06276b2016-03-31 02:15:15 +00002218#endif
Howard Hinnantc51e1022010-05-11 19:42:16 +00002219
2220template <class _Key, class _Tp, class _Compare, class _Allocator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00002221inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00002222bool
2223operator==(const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
2224 const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
2225{
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00002226 return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin());
Howard Hinnantc51e1022010-05-11 19:42:16 +00002227}
2228
2229template <class _Key, class _Tp, class _Compare, class _Allocator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00002230inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00002231bool
2232operator< (const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
2233 const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
2234{
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00002235 return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
Howard Hinnantc51e1022010-05-11 19:42:16 +00002236}
2237
2238template <class _Key, class _Tp, class _Compare, class _Allocator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00002239inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00002240bool
2241operator!=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
2242 const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
2243{
2244 return !(__x == __y);
2245}
2246
2247template <class _Key, class _Tp, class _Compare, class _Allocator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00002248inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00002249bool
2250operator> (const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
2251 const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
2252{
2253 return __y < __x;
2254}
2255
2256template <class _Key, class _Tp, class _Compare, class _Allocator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00002257inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00002258bool
2259operator>=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
2260 const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
2261{
2262 return !(__x < __y);
2263}
2264
2265template <class _Key, class _Tp, class _Compare, class _Allocator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00002266inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00002267bool
2268operator<=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
2269 const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
2270{
2271 return !(__y < __x);
2272}
2273
2274template <class _Key, class _Tp, class _Compare, class _Allocator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00002275inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00002276void
2277swap(multimap<_Key, _Tp, _Compare, _Allocator>& __x,
2278 multimap<_Key, _Tp, _Compare, _Allocator>& __y)
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00002279 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
Howard Hinnantc51e1022010-05-11 19:42:16 +00002280{
2281 __x.swap(__y);
2282}
2283
Marshall Clow29b53f22018-12-14 18:49:35 +00002284#if _LIBCPP_STD_VER > 17
Marek Kurdeja98b1412020-05-02 13:58:03 +02002285template <class _Key, class _Tp, class _Compare, class _Allocator,
2286 class _Predicate>
Marshall Clow29b53f22018-12-14 18:49:35 +00002287inline _LIBCPP_INLINE_VISIBILITY
Marek Kurdeja98b1412020-05-02 13:58:03 +02002288 typename multimap<_Key, _Tp, _Compare, _Allocator>::size_type
2289 erase_if(multimap<_Key, _Tp, _Compare, _Allocator>& __c,
2290 _Predicate __pred) {
Arthur O'Dwyerb6738bd2021-03-21 16:53:09 -04002291 return _VSTD::__libcpp_erase_if_container(__c, __pred);
Marek Kurdeja98b1412020-05-02 13:58:03 +02002292}
Marshall Clow29b53f22018-12-14 18:49:35 +00002293#endif
2294
Howard Hinnantc51e1022010-05-11 19:42:16 +00002295_LIBCPP_END_NAMESPACE_STD
2296
Louis Dionne2b1ceaa2021-04-20 12:03:32 -04002297#endif // _LIBCPP_MAP