blob: 4512dbd5aed647dab0c8f420020c28820baf1c2c [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
46 : public binary_function<value_type, value_type, bool>
47 {
48 friend class map;
49 protected:
50 key_compare comp;
51
52 value_compare(key_compare c);
53 public:
54 bool operator()(const value_type& x, const value_type& y) const;
55 };
56
57 // construct/copy/destroy:
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +000058 map()
59 noexcept(
60 is_nothrow_default_constructible<allocator_type>::value &&
61 is_nothrow_default_constructible<key_compare>::value &&
62 is_nothrow_copy_constructible<key_compare>::value);
Howard Hinnantc51e1022010-05-11 19:42:16 +000063 explicit map(const key_compare& comp);
64 map(const key_compare& comp, const allocator_type& a);
65 template <class InputIterator>
66 map(InputIterator first, InputIterator last,
67 const key_compare& comp = key_compare());
68 template <class InputIterator>
69 map(InputIterator first, InputIterator last,
70 const key_compare& comp, const allocator_type& a);
71 map(const map& m);
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +000072 map(map&& m)
73 noexcept(
74 is_nothrow_move_constructible<allocator_type>::value &&
75 is_nothrow_move_constructible<key_compare>::value);
Howard Hinnantc51e1022010-05-11 19:42:16 +000076 explicit map(const allocator_type& a);
77 map(const map& m, const allocator_type& a);
78 map(map&& m, const allocator_type& a);
79 map(initializer_list<value_type> il, const key_compare& comp = key_compare());
80 map(initializer_list<value_type> il, const key_compare& comp, const allocator_type& a);
Marshall Clow300abfb2013-09-11 01:15:47 +000081 template <class InputIterator>
82 map(InputIterator first, InputIterator last, const allocator_type& a)
83 : map(first, last, Compare(), a) {} // C++14
84 map(initializer_list<value_type> il, const allocator_type& a)
85 : map(il, Compare(), a) {} // C++14
86 ~map();
Howard Hinnantc51e1022010-05-11 19:42:16 +000087
88 map& operator=(const map& m);
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +000089 map& operator=(map&& m)
90 noexcept(
91 allocator_type::propagate_on_container_move_assignment::value &&
92 is_nothrow_move_assignable<allocator_type>::value &&
Howard Hinnantf95f4f52011-06-04 15:22:34 +000093 is_nothrow_move_assignable<key_compare>::value);
Howard Hinnantc51e1022010-05-11 19:42:16 +000094 map& operator=(initializer_list<value_type> il);
95
96 // iterators:
Howard Hinnantf95f4f52011-06-04 15:22:34 +000097 iterator begin() noexcept;
98 const_iterator begin() const noexcept;
99 iterator end() noexcept;
100 const_iterator end() const noexcept;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000101
Howard Hinnantf95f4f52011-06-04 15:22:34 +0000102 reverse_iterator rbegin() noexcept;
103 const_reverse_iterator rbegin() const noexcept;
104 reverse_iterator rend() noexcept;
105 const_reverse_iterator rend() const noexcept;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000106
Howard Hinnantf95f4f52011-06-04 15:22:34 +0000107 const_iterator cbegin() const noexcept;
108 const_iterator cend() const noexcept;
109 const_reverse_iterator crbegin() const noexcept;
110 const_reverse_iterator crend() const noexcept;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000111
112 // capacity:
Howard Hinnantf95f4f52011-06-04 15:22:34 +0000113 bool empty() const noexcept;
114 size_type size() const noexcept;
115 size_type max_size() const noexcept;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000116
117 // element access:
118 mapped_type& operator[](const key_type& k);
119 mapped_type& operator[](key_type&& k);
120
121 mapped_type& at(const key_type& k);
122 const mapped_type& at(const key_type& k) const;
123
124 // modifiers:
125 template <class... Args>
126 pair<iterator, bool> emplace(Args&&... args);
127 template <class... Args>
128 iterator emplace_hint(const_iterator position, Args&&... args);
129 pair<iterator, bool> insert(const value_type& v);
Marshall Clowd430d022016-01-05 19:32:41 +0000130 pair<iterator, bool> insert( value_type&& v); // C++17
Howard Hinnantc51e1022010-05-11 19:42:16 +0000131 template <class P>
132 pair<iterator, bool> insert(P&& p);
133 iterator insert(const_iterator position, const value_type& v);
Marshall Clowd430d022016-01-05 19:32:41 +0000134 iterator insert(const_iterator position, value_type&& v); // C++17
Howard Hinnantc51e1022010-05-11 19:42:16 +0000135 template <class P>
136 iterator insert(const_iterator position, P&& p);
137 template <class InputIterator>
138 void insert(InputIterator first, InputIterator last);
139 void insert(initializer_list<value_type> il);
140
Erik Pilkingtonc37a3d82018-08-01 01:33:38 +0000141 node_type extract(const_iterator position); // C++17
142 node_type extract(const key_type& x); // C++17
143 insert_return_type insert(node_type&& nh); // C++17
144 iterator insert(const_iterator hint, node_type&& nh); // C++17
145
Marshall Clow3223db82015-07-07 03:37:33 +0000146 template <class... Args>
147 pair<iterator, bool> try_emplace(const key_type& k, Args&&... args); // C++17
148 template <class... Args>
149 pair<iterator, bool> try_emplace(key_type&& k, Args&&... args); // C++17
150 template <class... Args>
151 iterator try_emplace(const_iterator hint, const key_type& k, Args&&... args); // C++17
152 template <class... Args>
153 iterator try_emplace(const_iterator hint, key_type&& k, Args&&... args); // C++17
154 template <class M>
155 pair<iterator, bool> insert_or_assign(const key_type& k, M&& obj); // C++17
156 template <class M>
157 pair<iterator, bool> insert_or_assign(key_type&& k, M&& obj); // C++17
158 template <class M>
159 iterator insert_or_assign(const_iterator hint, const key_type& k, M&& obj); // C++17
160 template <class M>
161 iterator insert_or_assign(const_iterator hint, key_type&& k, M&& obj); // C++17
162
Howard Hinnantc51e1022010-05-11 19:42:16 +0000163 iterator erase(const_iterator position);
Marshall Clow22ea5b82015-05-10 13:35:00 +0000164 iterator erase(iterator position); // C++14
Howard Hinnantc51e1022010-05-11 19:42:16 +0000165 size_type erase(const key_type& k);
166 iterator erase(const_iterator first, const_iterator last);
Howard Hinnantf95f4f52011-06-04 15:22:34 +0000167 void clear() noexcept;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000168
Erik Pilkington82a65ad2018-10-31 17:31:35 +0000169 template<class C2>
170 void merge(map<Key, T, C2, Allocator>& source); // C++17
171 template<class C2>
172 void merge(map<Key, T, C2, Allocator>&& source); // C++17
173 template<class C2>
174 void merge(multimap<Key, T, C2, Allocator>& source); // C++17
175 template<class C2>
176 void merge(multimap<Key, T, C2, Allocator>&& source); // C++17
177
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000178 void swap(map& m)
Marshall Clow8982dcd2015-07-13 20:04:56 +0000179 noexcept(allocator_traits<allocator_type>::is_always_equal::value &&
Eric Fiselier6bfed252016-04-21 23:38:59 +0000180 is_nothrow_swappable<key_compare>::value); // C++17
Howard Hinnantc51e1022010-05-11 19:42:16 +0000181
182 // observers:
Howard Hinnantf95f4f52011-06-04 15:22:34 +0000183 allocator_type get_allocator() const noexcept;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000184 key_compare key_comp() const;
185 value_compare value_comp() const;
186
187 // map operations:
188 iterator find(const key_type& k);
189 const_iterator find(const key_type& k) const;
Marshall Clowebb57322013-08-13 22:18:47 +0000190 template<typename K>
191 iterator find(const K& x); // C++14
192 template<typename K>
193 const_iterator find(const K& x) const; // C++14
Marek Kurdejd7e019e2021-04-13 17:10:55 +0200194
Marshall Clowebb57322013-08-13 22:18:47 +0000195 template<typename K>
Marshall Clowe6a5f522014-08-24 23:54:16 +0000196 size_type count(const K& x) const; // C++14
Howard Hinnantc51e1022010-05-11 19:42:16 +0000197 size_type count(const key_type& k) const;
Marek Kurdejd7e019e2021-04-13 17:10:55 +0200198
199 bool contains(const key_type& x) const; // C++20
200 template<class K> bool contains(const K& x) const; // C++20
201
Howard Hinnantc51e1022010-05-11 19:42:16 +0000202 iterator lower_bound(const key_type& k);
203 const_iterator lower_bound(const key_type& k) const;
Marshall Clowebb57322013-08-13 22:18:47 +0000204 template<typename K>
205 iterator lower_bound(const K& x); // C++14
206 template<typename K>
207 const_iterator lower_bound(const K& x) const; // C++14
208
Howard Hinnantc51e1022010-05-11 19:42:16 +0000209 iterator upper_bound(const key_type& k);
210 const_iterator upper_bound(const key_type& k) const;
Marshall Clowebb57322013-08-13 22:18:47 +0000211 template<typename K>
212 iterator upper_bound(const K& x); // C++14
213 template<typename K>
214 const_iterator upper_bound(const K& x) const; // C++14
215
Howard Hinnantc51e1022010-05-11 19:42:16 +0000216 pair<iterator,iterator> equal_range(const key_type& k);
217 pair<const_iterator,const_iterator> equal_range(const key_type& k) const;
Marshall Clowebb57322013-08-13 22:18:47 +0000218 template<typename K>
219 pair<iterator,iterator> equal_range(const K& x); // C++14
220 template<typename K>
221 pair<const_iterator,const_iterator> equal_range(const K& x) const; // C++14
Howard Hinnantc51e1022010-05-11 19:42:16 +0000222};
223
224template <class Key, class T, class Compare, class Allocator>
225bool
226operator==(const map<Key, T, Compare, Allocator>& x,
227 const map<Key, T, Compare, Allocator>& y);
228
229template <class Key, class T, class Compare, class Allocator>
230bool
231operator< (const map<Key, T, Compare, Allocator>& x,
232 const map<Key, T, Compare, Allocator>& y);
233
234template <class Key, class T, class Compare, class Allocator>
235bool
236operator!=(const map<Key, T, Compare, Allocator>& x,
237 const map<Key, T, Compare, Allocator>& y);
238
239template <class Key, class T, class Compare, class Allocator>
240bool
241operator> (const map<Key, T, Compare, Allocator>& x,
242 const map<Key, T, Compare, Allocator>& y);
243
244template <class Key, class T, class Compare, class Allocator>
245bool
246operator>=(const map<Key, T, Compare, Allocator>& x,
247 const map<Key, T, Compare, Allocator>& y);
248
249template <class Key, class T, class Compare, class Allocator>
250bool
251operator<=(const map<Key, T, Compare, Allocator>& x,
252 const map<Key, T, Compare, Allocator>& y);
253
254// specialized algorithms:
255template <class Key, class T, class Compare, class Allocator>
256void
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000257swap(map<Key, T, Compare, Allocator>& x, map<Key, T, Compare, Allocator>& y)
258 noexcept(noexcept(x.swap(y)));
Howard Hinnantc51e1022010-05-11 19:42:16 +0000259
Marshall Clow29b53f22018-12-14 18:49:35 +0000260template <class Key, class T, class Compare, class Allocator, class Predicate>
Marek Kurdeja98b1412020-05-02 13:58:03 +0200261typename map<Key, T, Compare, Allocator>::size_type
262erase_if(map<Key, T, Compare, Allocator>& c, Predicate pred); // C++20
Marshall Clow29b53f22018-12-14 18:49:35 +0000263
264
Howard Hinnantc51e1022010-05-11 19:42:16 +0000265template <class Key, class T, class Compare = less<Key>,
266 class Allocator = allocator<pair<const Key, T>>>
267class multimap
268{
269public:
270 // types:
271 typedef Key key_type;
272 typedef T mapped_type;
273 typedef pair<const key_type,mapped_type> value_type;
274 typedef Compare key_compare;
275 typedef Allocator allocator_type;
276 typedef typename allocator_type::reference reference;
277 typedef typename allocator_type::const_reference const_reference;
278 typedef typename allocator_type::size_type size_type;
279 typedef typename allocator_type::difference_type difference_type;
280 typedef typename allocator_type::pointer pointer;
281 typedef typename allocator_type::const_pointer const_pointer;
282
283 typedef implementation-defined iterator;
284 typedef implementation-defined const_iterator;
285 typedef std::reverse_iterator<iterator> reverse_iterator;
286 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
Erik Pilkingtonc37a3d82018-08-01 01:33:38 +0000287 typedef unspecified node_type; // C++17
Howard Hinnantc51e1022010-05-11 19:42:16 +0000288
289 class value_compare
290 : public binary_function<value_type,value_type,bool>
291 {
292 friend class multimap;
293 protected:
294 key_compare comp;
295 value_compare(key_compare c);
296 public:
297 bool operator()(const value_type& x, const value_type& y) const;
298 };
299
300 // construct/copy/destroy:
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000301 multimap()
302 noexcept(
303 is_nothrow_default_constructible<allocator_type>::value &&
304 is_nothrow_default_constructible<key_compare>::value &&
305 is_nothrow_copy_constructible<key_compare>::value);
306 explicit multimap(const key_compare& comp);
Howard Hinnantc51e1022010-05-11 19:42:16 +0000307 multimap(const key_compare& comp, const allocator_type& a);
308 template <class InputIterator>
309 multimap(InputIterator first, InputIterator last, const key_compare& comp);
310 template <class InputIterator>
311 multimap(InputIterator first, InputIterator last, const key_compare& comp,
312 const allocator_type& a);
313 multimap(const multimap& m);
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000314 multimap(multimap&& m)
315 noexcept(
316 is_nothrow_move_constructible<allocator_type>::value &&
317 is_nothrow_move_constructible<key_compare>::value);
Howard Hinnantc51e1022010-05-11 19:42:16 +0000318 explicit multimap(const allocator_type& a);
319 multimap(const multimap& m, const allocator_type& a);
320 multimap(multimap&& m, const allocator_type& a);
321 multimap(initializer_list<value_type> il, const key_compare& comp = key_compare());
322 multimap(initializer_list<value_type> il, const key_compare& comp,
323 const allocator_type& a);
Marshall Clow300abfb2013-09-11 01:15:47 +0000324 template <class InputIterator>
325 multimap(InputIterator first, InputIterator last, const allocator_type& a)
326 : multimap(first, last, Compare(), a) {} // C++14
327 multimap(initializer_list<value_type> il, const allocator_type& a)
328 : multimap(il, Compare(), a) {} // C++14
Howard Hinnantc51e1022010-05-11 19:42:16 +0000329 ~multimap();
330
331 multimap& operator=(const multimap& m);
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000332 multimap& operator=(multimap&& m)
333 noexcept(
334 allocator_type::propagate_on_container_move_assignment::value &&
335 is_nothrow_move_assignable<allocator_type>::value &&
Howard Hinnantf95f4f52011-06-04 15:22:34 +0000336 is_nothrow_move_assignable<key_compare>::value);
Howard Hinnantc51e1022010-05-11 19:42:16 +0000337 multimap& operator=(initializer_list<value_type> il);
338
339 // iterators:
Howard Hinnantf95f4f52011-06-04 15:22:34 +0000340 iterator begin() noexcept;
341 const_iterator begin() const noexcept;
342 iterator end() noexcept;
343 const_iterator end() const noexcept;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000344
Howard Hinnantf95f4f52011-06-04 15:22:34 +0000345 reverse_iterator rbegin() noexcept;
346 const_reverse_iterator rbegin() const noexcept;
347 reverse_iterator rend() noexcept;
348 const_reverse_iterator rend() const noexcept;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000349
Howard Hinnantf95f4f52011-06-04 15:22:34 +0000350 const_iterator cbegin() const noexcept;
351 const_iterator cend() const noexcept;
352 const_reverse_iterator crbegin() const noexcept;
353 const_reverse_iterator crend() const noexcept;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000354
355 // capacity:
Howard Hinnantf95f4f52011-06-04 15:22:34 +0000356 bool empty() const noexcept;
357 size_type size() const noexcept;
358 size_type max_size() const noexcept;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000359
360 // modifiers:
361 template <class... Args>
362 iterator emplace(Args&&... args);
363 template <class... Args>
364 iterator emplace_hint(const_iterator position, Args&&... args);
365 iterator insert(const value_type& v);
Marshall Clowd430d022016-01-05 19:32:41 +0000366 iterator insert( value_type&& v); // C++17
Howard Hinnantc51e1022010-05-11 19:42:16 +0000367 template <class P>
368 iterator insert(P&& p);
369 iterator insert(const_iterator position, const value_type& v);
Marshall Clowd430d022016-01-05 19:32:41 +0000370 iterator insert(const_iterator position, value_type&& v); // C++17
Howard Hinnantc51e1022010-05-11 19:42:16 +0000371 template <class P>
372 iterator insert(const_iterator position, P&& p);
373 template <class InputIterator>
374 void insert(InputIterator first, InputIterator last);
375 void insert(initializer_list<value_type> il);
376
Erik Pilkingtonc37a3d82018-08-01 01:33:38 +0000377 node_type extract(const_iterator position); // C++17
378 node_type extract(const key_type& x); // C++17
379 iterator insert(node_type&& nh); // C++17
380 iterator insert(const_iterator hint, node_type&& nh); // C++17
381
Howard Hinnantc51e1022010-05-11 19:42:16 +0000382 iterator erase(const_iterator position);
Marshall Clow22ea5b82015-05-10 13:35:00 +0000383 iterator erase(iterator position); // C++14
Howard Hinnantc51e1022010-05-11 19:42:16 +0000384 size_type erase(const key_type& k);
385 iterator erase(const_iterator first, const_iterator last);
Howard Hinnantf95f4f52011-06-04 15:22:34 +0000386 void clear() noexcept;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000387
Erik Pilkington82a65ad2018-10-31 17:31:35 +0000388 template<class C2>
389 void merge(multimap<Key, T, C2, Allocator>& source); // C++17
390 template<class C2>
391 void merge(multimap<Key, T, C2, Allocator>&& source); // C++17
392 template<class C2>
393 void merge(map<Key, T, C2, Allocator>& source); // C++17
394 template<class C2>
395 void merge(map<Key, T, C2, Allocator>&& source); // C++17
396
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000397 void swap(multimap& m)
Marshall Clow8982dcd2015-07-13 20:04:56 +0000398 noexcept(allocator_traits<allocator_type>::is_always_equal::value &&
Eric Fiselier6bfed252016-04-21 23:38:59 +0000399 is_nothrow_swappable<key_compare>::value); // C++17
Howard Hinnantc51e1022010-05-11 19:42:16 +0000400
401 // observers:
Howard Hinnantf95f4f52011-06-04 15:22:34 +0000402 allocator_type get_allocator() const noexcept;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000403 key_compare key_comp() const;
404 value_compare value_comp() const;
405
406 // map operations:
407 iterator find(const key_type& k);
408 const_iterator find(const key_type& k) const;
Marshall Clowebb57322013-08-13 22:18:47 +0000409 template<typename K>
410 iterator find(const K& x); // C++14
411 template<typename K>
412 const_iterator find(const K& x) const; // C++14
Marek Kurdejd7e019e2021-04-13 17:10:55 +0200413
Marshall Clowebb57322013-08-13 22:18:47 +0000414 template<typename K>
Marshall Clowe6a5f522014-08-24 23:54:16 +0000415 size_type count(const K& x) const; // C++14
Howard Hinnantc51e1022010-05-11 19:42:16 +0000416 size_type count(const key_type& k) const;
Marek Kurdejd7e019e2021-04-13 17:10:55 +0200417
418 bool contains(const key_type& x) const; // C++20
419 template<class K> bool contains(const K& x) const; // C++20
420
Howard Hinnantc51e1022010-05-11 19:42:16 +0000421 iterator lower_bound(const key_type& k);
422 const_iterator lower_bound(const key_type& k) const;
Marshall Clowebb57322013-08-13 22:18:47 +0000423 template<typename K>
424 iterator lower_bound(const K& x); // C++14
425 template<typename K>
426 const_iterator lower_bound(const K& x) const; // C++14
427
Howard Hinnantc51e1022010-05-11 19:42:16 +0000428 iterator upper_bound(const key_type& k);
429 const_iterator upper_bound(const key_type& k) const;
Marshall Clowebb57322013-08-13 22:18:47 +0000430 template<typename K>
431 iterator upper_bound(const K& x); // C++14
432 template<typename K>
433 const_iterator upper_bound(const K& x) const; // C++14
434
Howard Hinnantc51e1022010-05-11 19:42:16 +0000435 pair<iterator,iterator> equal_range(const key_type& k);
436 pair<const_iterator,const_iterator> equal_range(const key_type& k) const;
Marshall Clowebb57322013-08-13 22:18:47 +0000437 template<typename K>
438 pair<iterator,iterator> equal_range(const K& x); // C++14
439 template<typename K>
440 pair<const_iterator,const_iterator> equal_range(const K& x) const; // C++14
Howard Hinnantc51e1022010-05-11 19:42:16 +0000441};
442
443template <class Key, class T, class Compare, class Allocator>
444bool
445operator==(const multimap<Key, T, Compare, Allocator>& x,
446 const multimap<Key, T, Compare, Allocator>& y);
447
448template <class Key, class T, class Compare, class Allocator>
449bool
450operator< (const multimap<Key, T, Compare, Allocator>& x,
451 const multimap<Key, T, Compare, Allocator>& y);
452
453template <class Key, class T, class Compare, class Allocator>
454bool
455operator!=(const multimap<Key, T, Compare, Allocator>& x,
456 const multimap<Key, T, Compare, Allocator>& y);
457
458template <class Key, class T, class Compare, class Allocator>
459bool
460operator> (const multimap<Key, T, Compare, Allocator>& x,
461 const multimap<Key, T, Compare, Allocator>& y);
462
463template <class Key, class T, class Compare, class Allocator>
464bool
465operator>=(const multimap<Key, T, Compare, Allocator>& x,
466 const multimap<Key, T, Compare, Allocator>& y);
467
468template <class Key, class T, class Compare, class Allocator>
469bool
470operator<=(const multimap<Key, T, Compare, Allocator>& x,
471 const multimap<Key, T, Compare, Allocator>& y);
472
473// specialized algorithms:
474template <class Key, class T, class Compare, class Allocator>
475void
476swap(multimap<Key, T, Compare, Allocator>& x,
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000477 multimap<Key, T, Compare, Allocator>& y)
478 noexcept(noexcept(x.swap(y)));
Howard Hinnantc51e1022010-05-11 19:42:16 +0000479
Marshall Clow29b53f22018-12-14 18:49:35 +0000480template <class Key, class T, class Compare, class Allocator, class Predicate>
Marek Kurdeja98b1412020-05-02 13:58:03 +0200481typename multimap<Key, T, Compare, Allocator>::size_type
482erase_if(multimap<Key, T, Compare, Allocator>& c, Predicate pred); // C++20
Marshall Clow29b53f22018-12-14 18:49:35 +0000483
Howard Hinnantc51e1022010-05-11 19:42:16 +0000484} // std
485
486*/
487
488#include <__config>
Arthur O'Dwyer597cac42021-05-12 23:04:03 -0400489#include <__debug>
Erik Pilkingtonc37a3d82018-08-01 01:33:38 +0000490#include <__node_handle>
Arthur O'Dwyer597cac42021-05-12 23:04:03 -0400491#include <__tree>
Arthur O'Dwyer7deec122021-03-24 18:19:12 -0400492#include <compare>
493#include <initializer_list>
Arthur O'Dwyerb6738bd2021-03-21 16:53:09 -0400494#include <iterator> // __libcpp_erase_if_container
Howard Hinnantc51e1022010-05-11 19:42:16 +0000495#include <memory>
496#include <utility>
497#include <functional>
498#include <initializer_list>
Eric Fiselierf7394302015-06-13 07:08:02 +0000499#include <type_traits>
Marshall Clow0a1e7502018-09-12 19:41:40 +0000500#include <version>
Howard Hinnantc51e1022010-05-11 19:42:16 +0000501
Howard Hinnantaaaa52b2011-10-17 20:05:10 +0000502#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
Howard Hinnantc51e1022010-05-11 19:42:16 +0000503#pragma GCC system_header
Howard Hinnantaaaa52b2011-10-17 20:05:10 +0000504#endif
Howard Hinnantc51e1022010-05-11 19:42:16 +0000505
506_LIBCPP_BEGIN_NAMESPACE_STD
507
Louis Dionne878a3a82018-12-06 21:46:17 +0000508template <class _Key, class _CP, class _Compare,
509 bool = is_empty<_Compare>::value && !__libcpp_is_final<_Compare>::value>
Howard Hinnantc51e1022010-05-11 19:42:16 +0000510class __map_value_compare
511 : private _Compare
512{
Howard Hinnantc51e1022010-05-11 19:42:16 +0000513public:
Howard Hinnant756c69b2010-09-22 16:48:34 +0000514 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000515 __map_value_compare()
516 _NOEXCEPT_(is_nothrow_default_constructible<_Compare>::value)
517 : _Compare() {}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000518 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000519 __map_value_compare(_Compare c)
520 _NOEXCEPT_(is_nothrow_copy_constructible<_Compare>::value)
521 : _Compare(c) {}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000522 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000523 const _Compare& key_comp() const _NOEXCEPT {return *this;}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000524 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000525 bool operator()(const _CP& __x, const _CP& __y) const
Erik Pilkingtond3fe2992018-06-04 20:38:23 +0000526 {return static_cast<const _Compare&>(*this)(__x.__get_value().first, __y.__get_value().first);}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000527 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000528 bool operator()(const _CP& __x, const _Key& __y) const
Erik Pilkingtond3fe2992018-06-04 20:38:23 +0000529 {return static_cast<const _Compare&>(*this)(__x.__get_value().first, __y);}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000530 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000531 bool operator()(const _Key& __x, const _CP& __y) const
Erik Pilkingtond3fe2992018-06-04 20:38:23 +0000532 {return static_cast<const _Compare&>(*this)(__x, __y.__get_value().first);}
Marshall Clow8982dcd2015-07-13 20:04:56 +0000533 void swap(__map_value_compare&__y)
534 _NOEXCEPT_(__is_nothrow_swappable<_Compare>::value)
535 {
Eric Fiselier68b5f0b2017-04-13 00:34:24 +0000536 using _VSTD::swap;
537 swap(static_cast<_Compare&>(*this), static_cast<_Compare&>(__y));
Marshall Clow8982dcd2015-07-13 20:04:56 +0000538 }
Marshall Clowebb57322013-08-13 22:18:47 +0000539
540#if _LIBCPP_STD_VER > 11
541 template <typename _K2>
542 _LIBCPP_INLINE_VISIBILITY
543 typename enable_if<__is_transparent<_Compare, _K2>::value, bool>::type
544 operator () ( const _K2& __x, const _CP& __y ) const
Erik Pilkingtond3fe2992018-06-04 20:38:23 +0000545 {return static_cast<const _Compare&>(*this) (__x, __y.__get_value().first);}
Marshall Clowebb57322013-08-13 22:18:47 +0000546
547 template <typename _K2>
548 _LIBCPP_INLINE_VISIBILITY
549 typename enable_if<__is_transparent<_Compare, _K2>::value, bool>::type
550 operator () (const _CP& __x, const _K2& __y) const
Erik Pilkingtond3fe2992018-06-04 20:38:23 +0000551 {return static_cast<const _Compare&>(*this) (__x.__get_value().first, __y);}
Marshall Clowebb57322013-08-13 22:18:47 +0000552#endif
Howard Hinnantc51e1022010-05-11 19:42:16 +0000553};
554
Howard Hinnant90b91592013-07-05 18:06:00 +0000555template <class _Key, class _CP, class _Compare>
556class __map_value_compare<_Key, _CP, _Compare, false>
Howard Hinnantc51e1022010-05-11 19:42:16 +0000557{
558 _Compare comp;
559
Howard Hinnantc51e1022010-05-11 19:42:16 +0000560public:
Howard Hinnant756c69b2010-09-22 16:48:34 +0000561 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000562 __map_value_compare()
563 _NOEXCEPT_(is_nothrow_default_constructible<_Compare>::value)
564 : comp() {}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000565 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000566 __map_value_compare(_Compare c)
567 _NOEXCEPT_(is_nothrow_copy_constructible<_Compare>::value)
568 : comp(c) {}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000569 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000570 const _Compare& key_comp() const _NOEXCEPT {return comp;}
Howard Hinnantc51e1022010-05-11 19:42:16 +0000571
Howard Hinnant756c69b2010-09-22 16:48:34 +0000572 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000573 bool operator()(const _CP& __x, const _CP& __y) const
Erik Pilkingtond3fe2992018-06-04 20:38:23 +0000574 {return comp(__x.__get_value().first, __y.__get_value().first);}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000575 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000576 bool operator()(const _CP& __x, const _Key& __y) const
Erik Pilkingtond3fe2992018-06-04 20:38:23 +0000577 {return comp(__x.__get_value().first, __y);}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000578 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000579 bool operator()(const _Key& __x, const _CP& __y) const
Erik Pilkingtond3fe2992018-06-04 20:38:23 +0000580 {return comp(__x, __y.__get_value().first);}
Marshall Clow8982dcd2015-07-13 20:04:56 +0000581 void swap(__map_value_compare&__y)
582 _NOEXCEPT_(__is_nothrow_swappable<_Compare>::value)
583 {
584 using _VSTD::swap;
585 swap(comp, __y.comp);
586 }
Eric Fiseliercf8c0212017-01-05 06:06:18 +0000587
Marshall Clowebb57322013-08-13 22:18:47 +0000588#if _LIBCPP_STD_VER > 11
589 template <typename _K2>
590 _LIBCPP_INLINE_VISIBILITY
591 typename enable_if<__is_transparent<_Compare, _K2>::value, bool>::type
592 operator () ( const _K2& __x, const _CP& __y ) const
Erik Pilkingtond3fe2992018-06-04 20:38:23 +0000593 {return comp (__x, __y.__get_value().first);}
Marshall Clowebb57322013-08-13 22:18:47 +0000594
595 template <typename _K2>
596 _LIBCPP_INLINE_VISIBILITY
597 typename enable_if<__is_transparent<_Compare, _K2>::value, bool>::type
598 operator () (const _CP& __x, const _K2& __y) const
Erik Pilkingtond3fe2992018-06-04 20:38:23 +0000599 {return comp (__x.__get_value().first, __y);}
Marshall Clowebb57322013-08-13 22:18:47 +0000600#endif
Howard Hinnantc51e1022010-05-11 19:42:16 +0000601};
602
Marshall Clow8982dcd2015-07-13 20:04:56 +0000603template <class _Key, class _CP, class _Compare, bool __b>
604inline _LIBCPP_INLINE_VISIBILITY
605void
606swap(__map_value_compare<_Key, _CP, _Compare, __b>& __x,
607 __map_value_compare<_Key, _CP, _Compare, __b>& __y)
608 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
609{
610 __x.swap(__y);
611}
612
Howard Hinnantc51e1022010-05-11 19:42:16 +0000613template <class _Allocator>
614class __map_node_destructor
615{
616 typedef _Allocator allocator_type;
617 typedef allocator_traits<allocator_type> __alloc_traits;
Eric Fiseliera00b4842016-02-20 05:28:30 +0000618
Howard Hinnantc51e1022010-05-11 19:42:16 +0000619public:
620 typedef typename __alloc_traits::pointer pointer;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000621
Eric Fiseliera00b4842016-02-20 05:28:30 +0000622private:
Howard Hinnantc51e1022010-05-11 19:42:16 +0000623 allocator_type& __na_;
624
625 __map_node_destructor& operator=(const __map_node_destructor&);
626
627public:
628 bool __first_constructed;
629 bool __second_constructed;
630
Howard Hinnant756c69b2010-09-22 16:48:34 +0000631 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000632 explicit __map_node_destructor(allocator_type& __na) _NOEXCEPT
Howard Hinnantc51e1022010-05-11 19:42:16 +0000633 : __na_(__na),
634 __first_constructed(false),
635 __second_constructed(false)
636 {}
637
Eric Fiseliera85b1282017-04-18 21:08:06 +0000638#ifndef _LIBCPP_CXX03_LANG
Howard Hinnant756c69b2010-09-22 16:48:34 +0000639 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000640 __map_node_destructor(__tree_node_destructor<allocator_type>&& __x) _NOEXCEPT
Howard Hinnantc51e1022010-05-11 19:42:16 +0000641 : __na_(__x.__na_),
642 __first_constructed(__x.__value_constructed),
643 __second_constructed(__x.__value_constructed)
644 {
645 __x.__value_constructed = false;
646 }
Louis Dionne2b1ceaa2021-04-20 12:03:32 -0400647#endif // _LIBCPP_CXX03_LANG
Howard Hinnantc51e1022010-05-11 19:42:16 +0000648
Howard Hinnant756c69b2010-09-22 16:48:34 +0000649 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000650 void operator()(pointer __p) _NOEXCEPT
Howard Hinnantc51e1022010-05-11 19:42:16 +0000651 {
652 if (__second_constructed)
Erik Pilkingtond3fe2992018-06-04 20:38:23 +0000653 __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.__get_value().second));
Howard Hinnantc51e1022010-05-11 19:42:16 +0000654 if (__first_constructed)
Erik Pilkingtond3fe2992018-06-04 20:38:23 +0000655 __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.__get_value().first));
Howard Hinnantc51e1022010-05-11 19:42:16 +0000656 if (__p)
657 __alloc_traits::deallocate(__na_, __p, 1);
658 }
659};
660
Howard Hinnant944510a2011-06-14 19:58:17 +0000661template <class _Key, class _Tp, class _Compare, class _Allocator>
662 class map;
663template <class _Key, class _Tp, class _Compare, class _Allocator>
664 class multimap;
665template <class _TreeIterator> class __map_const_iterator;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000666
Eric Fiseliera00b4842016-02-20 05:28:30 +0000667#ifndef _LIBCPP_CXX03_LANG
Howard Hinnant89f8b792013-09-30 19:08:22 +0000668
669template <class _Key, class _Tp>
Amy Huang63f53b52021-03-15 14:20:49 -0700670struct _LIBCPP_STANDALONE_DEBUG __value_type
Howard Hinnant89f8b792013-09-30 19:08:22 +0000671{
672 typedef _Key key_type;
673 typedef _Tp mapped_type;
674 typedef pair<const key_type, mapped_type> value_type;
Erik Pilkingtond3fe2992018-06-04 20:38:23 +0000675 typedef pair<key_type&, mapped_type&> __nc_ref_pair_type;
676 typedef pair<key_type&&, mapped_type&&> __nc_rref_pair_type;
Howard Hinnant89f8b792013-09-30 19:08:22 +0000677
Erik Pilkingtond3fe2992018-06-04 20:38:23 +0000678private:
Howard Hinnant89f8b792013-09-30 19:08:22 +0000679 value_type __cc;
Erik Pilkingtond3fe2992018-06-04 20:38:23 +0000680
681public:
682 _LIBCPP_INLINE_VISIBILITY
683 value_type& __get_value()
684 {
685#if _LIBCPP_STD_VER > 14
686 return *_VSTD::launder(_VSTD::addressof(__cc));
687#else
688 return __cc;
689#endif
690 }
691
692 _LIBCPP_INLINE_VISIBILITY
693 const value_type& __get_value() const
694 {
695#if _LIBCPP_STD_VER > 14
696 return *_VSTD::launder(_VSTD::addressof(__cc));
697#else
698 return __cc;
699#endif
700 }
701
702 _LIBCPP_INLINE_VISIBILITY
703 __nc_ref_pair_type __ref()
704 {
705 value_type& __v = __get_value();
706 return __nc_ref_pair_type(const_cast<key_type&>(__v.first), __v.second);
707 }
708
709 _LIBCPP_INLINE_VISIBILITY
710 __nc_rref_pair_type __move()
711 {
712 value_type& __v = __get_value();
713 return __nc_rref_pair_type(
714 _VSTD::move(const_cast<key_type&>(__v.first)),
715 _VSTD::move(__v.second));
716 }
Howard Hinnant89f8b792013-09-30 19:08:22 +0000717
Howard Hinnant89f8b792013-09-30 19:08:22 +0000718 _LIBCPP_INLINE_VISIBILITY
719 __value_type& operator=(const __value_type& __v)
Erik Pilkingtond3fe2992018-06-04 20:38:23 +0000720 {
721 __ref() = __v.__get_value();
722 return *this;
723 }
Howard Hinnant89f8b792013-09-30 19:08:22 +0000724
725 _LIBCPP_INLINE_VISIBILITY
726 __value_type& operator=(__value_type&& __v)
Erik Pilkingtond3fe2992018-06-04 20:38:23 +0000727 {
728 __ref() = __v.__move();
729 return *this;
730 }
Howard Hinnant89f8b792013-09-30 19:08:22 +0000731
Eric Fiselierd06276b2016-03-31 02:15:15 +0000732 template <class _ValueTp,
733 class = typename enable_if<
734 __is_same_uncvref<_ValueTp, value_type>::value
735 >::type
736 >
Howard Hinnant89f8b792013-09-30 19:08:22 +0000737 _LIBCPP_INLINE_VISIBILITY
Erik Pilkingtond3fe2992018-06-04 20:38:23 +0000738 __value_type& operator=(_ValueTp&& __v)
739 {
740 __ref() = _VSTD::forward<_ValueTp>(__v);
741 return *this;
Eric Fiselierd06276b2016-03-31 02:15:15 +0000742 }
743
744private:
745 __value_type() _LIBCPP_EQUAL_DELETE;
746 ~__value_type() _LIBCPP_EQUAL_DELETE;
747 __value_type(const __value_type& __v) _LIBCPP_EQUAL_DELETE;
748 __value_type(__value_type&& __v) _LIBCPP_EQUAL_DELETE;
Howard Hinnant89f8b792013-09-30 19:08:22 +0000749};
750
751#else
752
753template <class _Key, class _Tp>
754struct __value_type
755{
756 typedef _Key key_type;
757 typedef _Tp mapped_type;
758 typedef pair<const key_type, mapped_type> value_type;
759
Erik Pilkingtond3fe2992018-06-04 20:38:23 +0000760private:
Howard Hinnant89f8b792013-09-30 19:08:22 +0000761 value_type __cc;
762
Erik Pilkingtond3fe2992018-06-04 20:38:23 +0000763public:
764 _LIBCPP_INLINE_VISIBILITY
765 value_type& __get_value() { return __cc; }
766 _LIBCPP_INLINE_VISIBILITY
767 const value_type& __get_value() const { return __cc; }
768
Eric Fiselierd06276b2016-03-31 02:15:15 +0000769private:
770 __value_type();
771 __value_type(__value_type const&);
772 __value_type& operator=(__value_type const&);
773 ~__value_type();
Howard Hinnant89f8b792013-09-30 19:08:22 +0000774};
775
Eric Fiseliera85b1282017-04-18 21:08:06 +0000776#endif // _LIBCPP_CXX03_LANG
Howard Hinnant89f8b792013-09-30 19:08:22 +0000777
Eric Fiselier44f9fd02015-03-03 20:10:01 +0000778template <class _Tp>
779struct __extract_key_value_types;
780
781template <class _Key, class _Tp>
782struct __extract_key_value_types<__value_type<_Key, _Tp> >
783{
784 typedef _Key const __key_type;
785 typedef _Tp __mapped_type;
786};
787
Howard Hinnantc51e1022010-05-11 19:42:16 +0000788template <class _TreeIterator>
Eric Fiselierb5eb1bf2017-01-04 23:56:00 +0000789class _LIBCPP_TEMPLATE_VIS __map_iterator
Howard Hinnantc51e1022010-05-11 19:42:16 +0000790{
Eric Fiseliera00b4842016-02-20 05:28:30 +0000791 typedef typename _TreeIterator::_NodeTypes _NodeTypes;
792 typedef typename _TreeIterator::__pointer_traits __pointer_traits;
793
Howard Hinnantc51e1022010-05-11 19:42:16 +0000794 _TreeIterator __i_;
795
Howard Hinnantc51e1022010-05-11 19:42:16 +0000796public:
797 typedef bidirectional_iterator_tag iterator_category;
Eric Fiseliera00b4842016-02-20 05:28:30 +0000798 typedef typename _NodeTypes::__map_value_type value_type;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000799 typedef typename _TreeIterator::difference_type difference_type;
800 typedef value_type& reference;
Eric Fiseliera00b4842016-02-20 05:28:30 +0000801 typedef typename _NodeTypes::__map_value_type_pointer pointer;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000802
Howard Hinnant756c69b2010-09-22 16:48:34 +0000803 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000804 __map_iterator() _NOEXCEPT {}
Howard Hinnantc51e1022010-05-11 19:42:16 +0000805
Howard Hinnant756c69b2010-09-22 16:48:34 +0000806 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000807 __map_iterator(_TreeIterator __i) _NOEXCEPT : __i_(__i) {}
Howard Hinnantc51e1022010-05-11 19:42:16 +0000808
Howard Hinnant756c69b2010-09-22 16:48:34 +0000809 _LIBCPP_INLINE_VISIBILITY
Erik Pilkingtond3fe2992018-06-04 20:38:23 +0000810 reference operator*() const {return __i_->__get_value();}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000811 _LIBCPP_INLINE_VISIBILITY
Erik Pilkingtond3fe2992018-06-04 20:38:23 +0000812 pointer operator->() const {return pointer_traits<pointer>::pointer_to(__i_->__get_value());}
Howard Hinnantc51e1022010-05-11 19:42:16 +0000813
Howard Hinnant756c69b2010-09-22 16:48:34 +0000814 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000815 __map_iterator& operator++() {++__i_; return *this;}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000816 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000817 __map_iterator operator++(int)
818 {
819 __map_iterator __t(*this);
820 ++(*this);
821 return __t;
822 }
823
Howard Hinnant756c69b2010-09-22 16:48:34 +0000824 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000825 __map_iterator& operator--() {--__i_; return *this;}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000826 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000827 __map_iterator operator--(int)
828 {
829 __map_iterator __t(*this);
830 --(*this);
831 return __t;
832 }
833
Howard Hinnant756c69b2010-09-22 16:48:34 +0000834 friend _LIBCPP_INLINE_VISIBILITY
835 bool operator==(const __map_iterator& __x, const __map_iterator& __y)
Howard Hinnantc51e1022010-05-11 19:42:16 +0000836 {return __x.__i_ == __y.__i_;}
Eric Fiseliercf8c0212017-01-05 06:06:18 +0000837 friend
Howard Hinnant756c69b2010-09-22 16:48:34 +0000838 _LIBCPP_INLINE_VISIBILITY
839 bool operator!=(const __map_iterator& __x, const __map_iterator& __y)
Howard Hinnantc51e1022010-05-11 19:42:16 +0000840 {return __x.__i_ != __y.__i_;}
841
Eric Fiselierb5eb1bf2017-01-04 23:56:00 +0000842 template <class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS map;
843 template <class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS multimap;
844 template <class> friend class _LIBCPP_TEMPLATE_VIS __map_const_iterator;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000845};
846
847template <class _TreeIterator>
Eric Fiselierb5eb1bf2017-01-04 23:56:00 +0000848class _LIBCPP_TEMPLATE_VIS __map_const_iterator
Howard Hinnantc51e1022010-05-11 19:42:16 +0000849{
Eric Fiseliera00b4842016-02-20 05:28:30 +0000850 typedef typename _TreeIterator::_NodeTypes _NodeTypes;
851 typedef typename _TreeIterator::__pointer_traits __pointer_traits;
852
Howard Hinnantc51e1022010-05-11 19:42:16 +0000853 _TreeIterator __i_;
854
Howard Hinnantc51e1022010-05-11 19:42:16 +0000855public:
856 typedef bidirectional_iterator_tag iterator_category;
Eric Fiseliera00b4842016-02-20 05:28:30 +0000857 typedef typename _NodeTypes::__map_value_type value_type;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000858 typedef typename _TreeIterator::difference_type difference_type;
859 typedef const value_type& reference;
Eric Fiseliera00b4842016-02-20 05:28:30 +0000860 typedef typename _NodeTypes::__const_map_value_type_pointer pointer;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000861
Howard Hinnant756c69b2010-09-22 16:48:34 +0000862 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000863 __map_const_iterator() _NOEXCEPT {}
Howard Hinnantc51e1022010-05-11 19:42:16 +0000864
Howard Hinnant756c69b2010-09-22 16:48:34 +0000865 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000866 __map_const_iterator(_TreeIterator __i) _NOEXCEPT : __i_(__i) {}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000867 _LIBCPP_INLINE_VISIBILITY
Eric Fiselier44f9fd02015-03-03 20:10:01 +0000868 __map_const_iterator(__map_iterator<
869 typename _TreeIterator::__non_const_iterator> __i) _NOEXCEPT
870 : __i_(__i.__i_) {}
Howard Hinnantc51e1022010-05-11 19:42:16 +0000871
Howard Hinnant756c69b2010-09-22 16:48:34 +0000872 _LIBCPP_INLINE_VISIBILITY
Erik Pilkingtond3fe2992018-06-04 20:38:23 +0000873 reference operator*() const {return __i_->__get_value();}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000874 _LIBCPP_INLINE_VISIBILITY
Erik Pilkingtond3fe2992018-06-04 20:38:23 +0000875 pointer operator->() const {return pointer_traits<pointer>::pointer_to(__i_->__get_value());}
Howard Hinnantc51e1022010-05-11 19:42:16 +0000876
Howard Hinnant756c69b2010-09-22 16:48:34 +0000877 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000878 __map_const_iterator& operator++() {++__i_; return *this;}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000879 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000880 __map_const_iterator operator++(int)
881 {
882 __map_const_iterator __t(*this);
883 ++(*this);
884 return __t;
885 }
886
Howard Hinnant756c69b2010-09-22 16:48:34 +0000887 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000888 __map_const_iterator& operator--() {--__i_; return *this;}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000889 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000890 __map_const_iterator operator--(int)
891 {
892 __map_const_iterator __t(*this);
893 --(*this);
894 return __t;
895 }
896
Howard Hinnant756c69b2010-09-22 16:48:34 +0000897 friend _LIBCPP_INLINE_VISIBILITY
898 bool operator==(const __map_const_iterator& __x, const __map_const_iterator& __y)
Howard Hinnantc51e1022010-05-11 19:42:16 +0000899 {return __x.__i_ == __y.__i_;}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000900 friend _LIBCPP_INLINE_VISIBILITY
901 bool operator!=(const __map_const_iterator& __x, const __map_const_iterator& __y)
Howard Hinnantc51e1022010-05-11 19:42:16 +0000902 {return __x.__i_ != __y.__i_;}
903
Eric Fiselierb5eb1bf2017-01-04 23:56:00 +0000904 template <class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS map;
905 template <class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS multimap;
906 template <class, class, class> friend class _LIBCPP_TEMPLATE_VIS __tree_const_iterator;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000907};
908
909template <class _Key, class _Tp, class _Compare = less<_Key>,
910 class _Allocator = allocator<pair<const _Key, _Tp> > >
Eric Fiselierb5eb1bf2017-01-04 23:56:00 +0000911class _LIBCPP_TEMPLATE_VIS map
Howard Hinnantc51e1022010-05-11 19:42:16 +0000912{
913public:
914 // types:
915 typedef _Key key_type;
916 typedef _Tp mapped_type;
917 typedef pair<const key_type, mapped_type> value_type;
Arthur O'Dwyer6a752e12021-03-03 11:10:49 -0500918 typedef __identity_t<_Compare> key_compare;
919 typedef __identity_t<_Allocator> allocator_type;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000920 typedef value_type& reference;
921 typedef const value_type& const_reference;
922
Marshall Clow5128cf32015-11-26 01:24:04 +0000923 static_assert((is_same<typename allocator_type::value_type, value_type>::value),
924 "Allocator::value_type must be same type as value_type");
925
Eric Fiselierb5eb1bf2017-01-04 23:56:00 +0000926 class _LIBCPP_TEMPLATE_VIS value_compare
Howard Hinnantc51e1022010-05-11 19:42:16 +0000927 : public binary_function<value_type, value_type, bool>
928 {
929 friend class map;
930 protected:
931 key_compare comp;
932
Howard Hinnant756c69b2010-09-22 16:48:34 +0000933 _LIBCPP_INLINE_VISIBILITY value_compare(key_compare c) : comp(c) {}
Howard Hinnantc51e1022010-05-11 19:42:16 +0000934 public:
Howard Hinnant756c69b2010-09-22 16:48:34 +0000935 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000936 bool operator()(const value_type& __x, const value_type& __y) const
937 {return comp(__x.first, __y.first);}
938 };
939
940private:
Howard Hinnant2d0046b2013-06-19 21:29:40 +0000941
Howard Hinnant89f8b792013-09-30 19:08:22 +0000942 typedef _VSTD::__value_type<key_type, mapped_type> __value_type;
Howard Hinnant90b91592013-07-05 18:06:00 +0000943 typedef __map_value_compare<key_type, __value_type, key_compare> __vc;
Marshall Clow940e01c2015-04-07 05:21:38 +0000944 typedef typename __rebind_alloc_helper<allocator_traits<allocator_type>,
945 __value_type>::type __allocator_type;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000946 typedef __tree<__value_type, __vc, __allocator_type> __base;
947 typedef typename __base::__node_traits __node_traits;
948 typedef allocator_traits<allocator_type> __alloc_traits;
949
950 __base __tree_;
951
952public:
953 typedef typename __alloc_traits::pointer pointer;
954 typedef typename __alloc_traits::const_pointer const_pointer;
955 typedef typename __alloc_traits::size_type size_type;
956 typedef typename __alloc_traits::difference_type difference_type;
Eric Fiselier44f9fd02015-03-03 20:10:01 +0000957 typedef __map_iterator<typename __base::iterator> iterator;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000958 typedef __map_const_iterator<typename __base::const_iterator> const_iterator;
Howard Hinnantb1ad5a82011-06-30 21:18:19 +0000959 typedef _VSTD::reverse_iterator<iterator> reverse_iterator;
960 typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000961
Erik Pilkingtonc37a3d82018-08-01 01:33:38 +0000962#if _LIBCPP_STD_VER > 14
963 typedef __map_node_handle<typename __base::__node, allocator_type> node_type;
964 typedef __insert_return_type<iterator, node_type> insert_return_type;
965#endif
966
Erik Pilkington82a65ad2018-10-31 17:31:35 +0000967 template <class _Key2, class _Value2, class _Comp2, class _Alloc2>
968 friend class _LIBCPP_TEMPLATE_VIS map;
969 template <class _Key2, class _Value2, class _Comp2, class _Alloc2>
970 friend class _LIBCPP_TEMPLATE_VIS multimap;
971
Howard Hinnant756c69b2010-09-22 16:48:34 +0000972 _LIBCPP_INLINE_VISIBILITY
Marshall Clow7086a5a2014-03-10 04:50:10 +0000973 map()
974 _NOEXCEPT_(
975 is_nothrow_default_constructible<allocator_type>::value &&
976 is_nothrow_default_constructible<key_compare>::value &&
977 is_nothrow_copy_constructible<key_compare>::value)
978 : __tree_(__vc(key_compare())) {}
979
980 _LIBCPP_INLINE_VISIBILITY
981 explicit map(const key_compare& __comp)
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000982 _NOEXCEPT_(
983 is_nothrow_default_constructible<allocator_type>::value &&
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000984 is_nothrow_copy_constructible<key_compare>::value)
Howard Hinnantc51e1022010-05-11 19:42:16 +0000985 : __tree_(__vc(__comp)) {}
986
Howard Hinnant756c69b2010-09-22 16:48:34 +0000987 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000988 explicit map(const key_compare& __comp, const allocator_type& __a)
Marshall Clow657cbc42016-08-17 05:58:40 +0000989 : __tree_(__vc(__comp), typename __base::allocator_type(__a)) {}
Howard Hinnantc51e1022010-05-11 19:42:16 +0000990
991 template <class _InputIterator>
Howard Hinnant756c69b2010-09-22 16:48:34 +0000992 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000993 map(_InputIterator __f, _InputIterator __l,
994 const key_compare& __comp = key_compare())
995 : __tree_(__vc(__comp))
996 {
997 insert(__f, __l);
998 }
999
1000 template <class _InputIterator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001001 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001002 map(_InputIterator __f, _InputIterator __l,
1003 const key_compare& __comp, const allocator_type& __a)
Marshall Clow657cbc42016-08-17 05:58:40 +00001004 : __tree_(__vc(__comp), typename __base::allocator_type(__a))
Howard Hinnantc51e1022010-05-11 19:42:16 +00001005 {
1006 insert(__f, __l);
1007 }
1008
Marshall Clow300abfb2013-09-11 01:15:47 +00001009#if _LIBCPP_STD_VER > 11
1010 template <class _InputIterator>
Eric Fiseliercf8c0212017-01-05 06:06:18 +00001011 _LIBCPP_INLINE_VISIBILITY
Marshall Clow300abfb2013-09-11 01:15:47 +00001012 map(_InputIterator __f, _InputIterator __l, const allocator_type& __a)
1013 : map(__f, __l, key_compare(), __a) {}
1014#endif
1015
Howard Hinnant756c69b2010-09-22 16:48:34 +00001016 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001017 map(const map& __m)
1018 : __tree_(__m.__tree_)
1019 {
1020 insert(__m.begin(), __m.end());
1021 }
1022
Howard Hinnantd3a657f2011-07-01 19:24:36 +00001023 _LIBCPP_INLINE_VISIBILITY
1024 map& operator=(const map& __m)
1025 {
Marshall Clow476d3f42016-07-18 13:19:00 +00001026#ifndef _LIBCPP_CXX03_LANG
Howard Hinnantd3a657f2011-07-01 19:24:36 +00001027 __tree_ = __m.__tree_;
Howard Hinnant2d0046b2013-06-19 21:29:40 +00001028#else
Marshall Clowdb3cfcb2014-02-08 04:03:14 +00001029 if (this != &__m) {
1030 __tree_.clear();
1031 __tree_.value_comp() = __m.__tree_.value_comp();
1032 __tree_.__copy_assign_alloc(__m.__tree_);
1033 insert(__m.begin(), __m.end());
1034 }
Howard Hinnant2d0046b2013-06-19 21:29:40 +00001035#endif
Howard Hinnantd3a657f2011-07-01 19:24:36 +00001036 return *this;
1037 }
1038
Eric Fiseliera85b1282017-04-18 21:08:06 +00001039#ifndef _LIBCPP_CXX03_LANG
Howard Hinnantc51e1022010-05-11 19:42:16 +00001040
Howard Hinnant756c69b2010-09-22 16:48:34 +00001041 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001042 map(map&& __m)
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001043 _NOEXCEPT_(is_nothrow_move_constructible<__base>::value)
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001044 : __tree_(_VSTD::move(__m.__tree_))
Howard Hinnantc51e1022010-05-11 19:42:16 +00001045 {
1046 }
1047
1048 map(map&& __m, const allocator_type& __a);
1049
Howard Hinnant756c69b2010-09-22 16:48:34 +00001050 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant33711792011-08-12 21:56:02 +00001051 map& operator=(map&& __m)
1052 _NOEXCEPT_(is_nothrow_move_assignable<__base>::value)
1053 {
1054 __tree_ = _VSTD::move(__m.__tree_);
1055 return *this;
1056 }
1057
Howard Hinnant33711792011-08-12 21:56:02 +00001058 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001059 map(initializer_list<value_type> __il, const key_compare& __comp = key_compare())
1060 : __tree_(__vc(__comp))
1061 {
1062 insert(__il.begin(), __il.end());
1063 }
1064
Howard Hinnant756c69b2010-09-22 16:48:34 +00001065 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001066 map(initializer_list<value_type> __il, const key_compare& __comp, const allocator_type& __a)
Marshall Clow657cbc42016-08-17 05:58:40 +00001067 : __tree_(__vc(__comp), typename __base::allocator_type(__a))
Howard Hinnantc51e1022010-05-11 19:42:16 +00001068 {
1069 insert(__il.begin(), __il.end());
1070 }
1071
Marshall Clow300abfb2013-09-11 01:15:47 +00001072#if _LIBCPP_STD_VER > 11
Eric Fiseliercf8c0212017-01-05 06:06:18 +00001073 _LIBCPP_INLINE_VISIBILITY
Marshall Clow300abfb2013-09-11 01:15:47 +00001074 map(initializer_list<value_type> __il, const allocator_type& __a)
1075 : map(__il, key_compare(), __a) {}
1076#endif
1077
Howard Hinnant756c69b2010-09-22 16:48:34 +00001078 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001079 map& operator=(initializer_list<value_type> __il)
1080 {
1081 __tree_.__assign_unique(__il.begin(), __il.end());
1082 return *this;
1083 }
1084
Louis Dionne2b1ceaa2021-04-20 12:03:32 -04001085#endif // _LIBCPP_CXX03_LANG
Howard Hinnantc51e1022010-05-11 19:42:16 +00001086
Howard Hinnant756c69b2010-09-22 16:48:34 +00001087 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001088 explicit map(const allocator_type& __a)
Marshall Clow657cbc42016-08-17 05:58:40 +00001089 : __tree_(typename __base::allocator_type(__a))
Howard Hinnantc51e1022010-05-11 19:42:16 +00001090 {
1091 }
1092
Howard Hinnant756c69b2010-09-22 16:48:34 +00001093 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001094 map(const map& __m, const allocator_type& __a)
Marshall Clow657cbc42016-08-17 05:58:40 +00001095 : __tree_(__m.__tree_.value_comp(), typename __base::allocator_type(__a))
Howard Hinnantc51e1022010-05-11 19:42:16 +00001096 {
1097 insert(__m.begin(), __m.end());
1098 }
1099
Howard Hinnant756c69b2010-09-22 16:48:34 +00001100 _LIBCPP_INLINE_VISIBILITY
Louis Dionne69c42c02019-04-11 16:14:56 +00001101 ~map() {
1102 static_assert(sizeof(__diagnose_non_const_comparator<_Key, _Compare>()), "");
1103 }
1104
1105 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001106 iterator begin() _NOEXCEPT {return __tree_.begin();}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001107 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001108 const_iterator begin() const _NOEXCEPT {return __tree_.begin();}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001109 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001110 iterator end() _NOEXCEPT {return __tree_.end();}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001111 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001112 const_iterator end() const _NOEXCEPT {return __tree_.end();}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001113
Howard Hinnant756c69b2010-09-22 16:48:34 +00001114 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001115 reverse_iterator rbegin() _NOEXCEPT {return reverse_iterator(end());}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001116 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001117 const_reverse_iterator rbegin() const _NOEXCEPT
1118 {return const_reverse_iterator(end());}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001119 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001120 reverse_iterator rend() _NOEXCEPT
1121 {return reverse_iterator(begin());}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001122 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001123 const_reverse_iterator rend() const _NOEXCEPT
1124 {return const_reverse_iterator(begin());}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001125
Howard Hinnant756c69b2010-09-22 16:48:34 +00001126 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001127 const_iterator cbegin() const _NOEXCEPT {return begin();}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001128 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001129 const_iterator cend() const _NOEXCEPT {return end();}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001130 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001131 const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001132 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001133 const_reverse_iterator crend() const _NOEXCEPT {return rend();}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001134
Marshall Clow425f5752017-11-15 05:51:26 +00001135 _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001136 bool empty() const _NOEXCEPT {return __tree_.size() == 0;}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001137 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001138 size_type size() const _NOEXCEPT {return __tree_.size();}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001139 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001140 size_type max_size() const _NOEXCEPT {return __tree_.max_size();}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001141
1142 mapped_type& operator[](const key_type& __k);
Eric Fiselierd63f38e2016-03-31 03:13:37 +00001143#ifndef _LIBCPP_CXX03_LANG
Howard Hinnantc51e1022010-05-11 19:42:16 +00001144 mapped_type& operator[](key_type&& __k);
1145#endif
1146
1147 mapped_type& at(const key_type& __k);
1148 const mapped_type& at(const key_type& __k) const;
1149
Howard Hinnant756c69b2010-09-22 16:48:34 +00001150 _LIBCPP_INLINE_VISIBILITY
Marshall Clow657cbc42016-08-17 05:58:40 +00001151 allocator_type get_allocator() const _NOEXCEPT {return allocator_type(__tree_.__alloc());}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001152 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001153 key_compare key_comp() const {return __tree_.value_comp().key_comp();}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001154 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001155 value_compare value_comp() const {return value_compare(__tree_.value_comp().key_comp());}
1156
Eric Fiselierd06276b2016-03-31 02:15:15 +00001157#ifndef _LIBCPP_CXX03_LANG
1158 template <class ..._Args>
1159 _LIBCPP_INLINE_VISIBILITY
1160 pair<iterator, bool> emplace(_Args&& ...__args) {
1161 return __tree_.__emplace_unique(_VSTD::forward<_Args>(__args)...);
1162 }
Howard Hinnant74279a52010-09-04 23:28:19 +00001163
Howard Hinnant29eb9b82012-05-25 22:04:21 +00001164 template <class ..._Args>
Eric Fiselierd06276b2016-03-31 02:15:15 +00001165 _LIBCPP_INLINE_VISIBILITY
1166 iterator emplace_hint(const_iterator __p, _Args&& ...__args) {
1167 return __tree_.__emplace_hint_unique(__p.__i_, _VSTD::forward<_Args>(__args)...);
1168 }
Howard Hinnant74279a52010-09-04 23:28:19 +00001169
Howard Hinnantc834c512011-11-29 18:15:50 +00001170 template <class _Pp,
1171 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001172 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc834c512011-11-29 18:15:50 +00001173 pair<iterator, bool> insert(_Pp&& __p)
1174 {return __tree_.__insert_unique(_VSTD::forward<_Pp>(__p));}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001175
Howard Hinnantc834c512011-11-29 18:15:50 +00001176 template <class _Pp,
1177 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001178 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc834c512011-11-29 18:15:50 +00001179 iterator insert(const_iterator __pos, _Pp&& __p)
1180 {return __tree_.__insert_unique(__pos.__i_, _VSTD::forward<_Pp>(__p));}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001181
Louis Dionne2b1ceaa2021-04-20 12:03:32 -04001182#endif // _LIBCPP_CXX03_LANG
Howard Hinnantc51e1022010-05-11 19:42:16 +00001183
Howard Hinnant756c69b2010-09-22 16:48:34 +00001184 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001185 pair<iterator, bool>
1186 insert(const value_type& __v) {return __tree_.__insert_unique(__v);}
1187
Howard Hinnant756c69b2010-09-22 16:48:34 +00001188 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001189 iterator
1190 insert(const_iterator __p, const value_type& __v)
1191 {return __tree_.__insert_unique(__p.__i_, __v);}
1192
Eric Fiselierd6143132016-04-18 01:40:45 +00001193#ifndef _LIBCPP_CXX03_LANG
Marshall Clowd430d022016-01-05 19:32:41 +00001194 _LIBCPP_INLINE_VISIBILITY
1195 pair<iterator, bool>
Eric Fiselierd06276b2016-03-31 02:15:15 +00001196 insert(value_type&& __v) {return __tree_.__insert_unique(_VSTD::move(__v));}
Marshall Clowd430d022016-01-05 19:32:41 +00001197
1198 _LIBCPP_INLINE_VISIBILITY
Eric Fiselierd06276b2016-03-31 02:15:15 +00001199 iterator insert(const_iterator __p, value_type&& __v)
1200 {return __tree_.__insert_unique(__p.__i_, _VSTD::move(__v));}
Eric Fiseliera85b1282017-04-18 21:08:06 +00001201
1202 _LIBCPP_INLINE_VISIBILITY
1203 void insert(initializer_list<value_type> __il)
1204 {insert(__il.begin(), __il.end());}
Marshall Clowd430d022016-01-05 19:32:41 +00001205#endif
1206
Howard Hinnantc51e1022010-05-11 19:42:16 +00001207 template <class _InputIterator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001208 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001209 void insert(_InputIterator __f, _InputIterator __l)
1210 {
1211 for (const_iterator __e = cend(); __f != __l; ++__f)
1212 insert(__e.__i_, *__f);
1213 }
1214
Marshall Clow3223db82015-07-07 03:37:33 +00001215#if _LIBCPP_STD_VER > 14
Eric Fiselierd63f38e2016-03-31 03:13:37 +00001216
Marshall Clow3223db82015-07-07 03:37:33 +00001217 template <class... _Args>
1218 _LIBCPP_INLINE_VISIBILITY
1219 pair<iterator, bool> try_emplace(const key_type& __k, _Args&&... __args)
1220 {
Eric Fiselierd63f38e2016-03-31 03:13:37 +00001221 return __tree_.__emplace_unique_key_args(__k,
1222 _VSTD::piecewise_construct,
1223 _VSTD::forward_as_tuple(__k),
1224 _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...));
Marshall Clow3223db82015-07-07 03:37:33 +00001225 }
1226
1227 template <class... _Args>
1228 _LIBCPP_INLINE_VISIBILITY
1229 pair<iterator, bool> try_emplace(key_type&& __k, _Args&&... __args)
1230 {
Eric Fiselierd63f38e2016-03-31 03:13:37 +00001231 return __tree_.__emplace_unique_key_args(__k,
1232 _VSTD::piecewise_construct,
1233 _VSTD::forward_as_tuple(_VSTD::move(__k)),
1234 _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...));
Marshall Clow3223db82015-07-07 03:37:33 +00001235 }
1236
1237 template <class... _Args>
1238 _LIBCPP_INLINE_VISIBILITY
1239 iterator try_emplace(const_iterator __h, const key_type& __k, _Args&&... __args)
1240 {
Eric Fiselierd63f38e2016-03-31 03:13:37 +00001241 return __tree_.__emplace_hint_unique_key_args(__h.__i_, __k,
1242 _VSTD::piecewise_construct,
1243 _VSTD::forward_as_tuple(__k),
Mark de Wever1ba476f2020-09-19 15:39:09 +02001244 _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...)).first;
Marshall Clow3223db82015-07-07 03:37:33 +00001245 }
1246
1247 template <class... _Args>
1248 _LIBCPP_INLINE_VISIBILITY
1249 iterator try_emplace(const_iterator __h, key_type&& __k, _Args&&... __args)
1250 {
Eric Fiselierd63f38e2016-03-31 03:13:37 +00001251 return __tree_.__emplace_hint_unique_key_args(__h.__i_, __k,
1252 _VSTD::piecewise_construct,
1253 _VSTD::forward_as_tuple(_VSTD::move(__k)),
Mark de Wever1ba476f2020-09-19 15:39:09 +02001254 _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...)).first;
Marshall Clow3223db82015-07-07 03:37:33 +00001255 }
1256
1257 template <class _Vp>
1258 _LIBCPP_INLINE_VISIBILITY
1259 pair<iterator, bool> insert_or_assign(const key_type& __k, _Vp&& __v)
1260 {
1261 iterator __p = lower_bound(__k);
1262 if ( __p != end() && !key_comp()(__k, __p->first))
1263 {
1264 __p->second = _VSTD::forward<_Vp>(__v);
1265 return _VSTD::make_pair(__p, false);
1266 }
1267 return _VSTD::make_pair(emplace_hint(__p, __k, _VSTD::forward<_Vp>(__v)), true);
1268 }
Eric Fiselierd63f38e2016-03-31 03:13:37 +00001269
Marshall Clow3223db82015-07-07 03:37:33 +00001270 template <class _Vp>
1271 _LIBCPP_INLINE_VISIBILITY
1272 pair<iterator, bool> insert_or_assign(key_type&& __k, _Vp&& __v)
1273 {
1274 iterator __p = lower_bound(__k);
1275 if ( __p != end() && !key_comp()(__k, __p->first))
1276 {
1277 __p->second = _VSTD::forward<_Vp>(__v);
1278 return _VSTD::make_pair(__p, false);
1279 }
1280 return _VSTD::make_pair(emplace_hint(__p, _VSTD::move(__k), _VSTD::forward<_Vp>(__v)), true);
1281 }
1282
1283 template <class _Vp>
Mark de Wever1ba476f2020-09-19 15:39:09 +02001284 _LIBCPP_INLINE_VISIBILITY iterator insert_or_assign(const_iterator __h,
1285 const key_type& __k,
1286 _Vp&& __v) {
1287 auto [__r, __inserted] = __tree_.__emplace_hint_unique_key_args(
1288 __h.__i_, __k, __k, _VSTD::forward<_Vp>(__v));
1289
1290 if (!__inserted)
1291 __r->__get_value().second = _VSTD::forward<_Vp>(__v);
1292
1293 return __r;
1294 }
Marshall Clow3223db82015-07-07 03:37:33 +00001295
1296 template <class _Vp>
Mark de Wever1ba476f2020-09-19 15:39:09 +02001297 _LIBCPP_INLINE_VISIBILITY iterator insert_or_assign(const_iterator __h,
1298 key_type&& __k,
1299 _Vp&& __v) {
1300 auto [__r, __inserted] = __tree_.__emplace_hint_unique_key_args(
1301 __h.__i_, __k, _VSTD::move(__k), _VSTD::forward<_Vp>(__v));
1302
1303 if (!__inserted)
1304 __r->__get_value().second = _VSTD::forward<_Vp>(__v);
1305
1306 return __r;
1307 }
Eric Fiselierd63f38e2016-03-31 03:13:37 +00001308
Eric Fiseliera85b1282017-04-18 21:08:06 +00001309#endif // _LIBCPP_STD_VER > 14
Marshall Clow3223db82015-07-07 03:37:33 +00001310
Howard Hinnant756c69b2010-09-22 16:48:34 +00001311 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001312 iterator erase(const_iterator __p) {return __tree_.erase(__p.__i_);}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001313 _LIBCPP_INLINE_VISIBILITY
Marshall Clow22ea5b82015-05-10 13:35:00 +00001314 iterator erase(iterator __p) {return __tree_.erase(__p.__i_);}
1315 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001316 size_type erase(const key_type& __k)
1317 {return __tree_.__erase_unique(__k);}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001318 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001319 iterator erase(const_iterator __f, const_iterator __l)
1320 {return __tree_.erase(__f.__i_, __l.__i_);}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001321 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001322 void clear() _NOEXCEPT {__tree_.clear();}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001323
Erik Pilkingtonc37a3d82018-08-01 01:33:38 +00001324#if _LIBCPP_STD_VER > 14
1325 _LIBCPP_INLINE_VISIBILITY
1326 insert_return_type insert(node_type&& __nh)
1327 {
1328 _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(),
1329 "node_type with incompatible allocator passed to map::insert()");
1330 return __tree_.template __node_handle_insert_unique<
1331 node_type, insert_return_type>(_VSTD::move(__nh));
1332 }
1333 _LIBCPP_INLINE_VISIBILITY
1334 iterator insert(const_iterator __hint, node_type&& __nh)
1335 {
1336 _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(),
1337 "node_type with incompatible allocator passed to map::insert()");
1338 return __tree_.template __node_handle_insert_unique<node_type>(
1339 __hint.__i_, _VSTD::move(__nh));
1340 }
1341 _LIBCPP_INLINE_VISIBILITY
1342 node_type extract(key_type const& __key)
1343 {
1344 return __tree_.template __node_handle_extract<node_type>(__key);
1345 }
1346 _LIBCPP_INLINE_VISIBILITY
1347 node_type extract(const_iterator __it)
1348 {
1349 return __tree_.template __node_handle_extract<node_type>(__it.__i_);
1350 }
Louis Dionned2322c82018-11-01 14:41:37 +00001351 template <class _Compare2>
Erik Pilkington82a65ad2018-10-31 17:31:35 +00001352 _LIBCPP_INLINE_VISIBILITY
Louis Dionned2322c82018-11-01 14:41:37 +00001353 void merge(map<key_type, mapped_type, _Compare2, allocator_type>& __source)
Erik Pilkington82a65ad2018-10-31 17:31:35 +00001354 {
1355 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
1356 "merging container with incompatible allocator");
1357 __tree_.__node_handle_merge_unique(__source.__tree_);
1358 }
Louis Dionned2322c82018-11-01 14:41:37 +00001359 template <class _Compare2>
Erik Pilkington82a65ad2018-10-31 17:31:35 +00001360 _LIBCPP_INLINE_VISIBILITY
Louis Dionned2322c82018-11-01 14:41:37 +00001361 void merge(map<key_type, mapped_type, _Compare2, allocator_type>&& __source)
Erik Pilkington82a65ad2018-10-31 17:31:35 +00001362 {
1363 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
1364 "merging container with incompatible allocator");
1365 __tree_.__node_handle_merge_unique(__source.__tree_);
1366 }
Louis Dionned2322c82018-11-01 14:41:37 +00001367 template <class _Compare2>
Erik Pilkington82a65ad2018-10-31 17:31:35 +00001368 _LIBCPP_INLINE_VISIBILITY
Louis Dionned2322c82018-11-01 14:41:37 +00001369 void merge(multimap<key_type, mapped_type, _Compare2, allocator_type>& __source)
Erik Pilkington82a65ad2018-10-31 17:31:35 +00001370 {
1371 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
1372 "merging container with incompatible allocator");
1373 __tree_.__node_handle_merge_unique(__source.__tree_);
1374 }
Louis Dionned2322c82018-11-01 14:41:37 +00001375 template <class _Compare2>
Erik Pilkington82a65ad2018-10-31 17:31:35 +00001376 _LIBCPP_INLINE_VISIBILITY
Louis Dionned2322c82018-11-01 14:41:37 +00001377 void merge(multimap<key_type, mapped_type, _Compare2, allocator_type>&& __source)
Erik Pilkington82a65ad2018-10-31 17:31:35 +00001378 {
1379 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
1380 "merging container with incompatible allocator");
1381 __tree_.__node_handle_merge_unique(__source.__tree_);
1382 }
Erik Pilkingtonc37a3d82018-08-01 01:33:38 +00001383#endif
1384
Howard Hinnant756c69b2010-09-22 16:48:34 +00001385 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001386 void swap(map& __m)
1387 _NOEXCEPT_(__is_nothrow_swappable<__base>::value)
1388 {__tree_.swap(__m.__tree_);}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001389
Howard Hinnant756c69b2010-09-22 16:48:34 +00001390 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001391 iterator find(const key_type& __k) {return __tree_.find(__k);}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001392 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001393 const_iterator find(const key_type& __k) const {return __tree_.find(__k);}
Marshall Clowebb57322013-08-13 22:18:47 +00001394#if _LIBCPP_STD_VER > 11
1395 template <typename _K2>
1396 _LIBCPP_INLINE_VISIBILITY
1397 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
1398 find(const _K2& __k) {return __tree_.find(__k);}
1399 template <typename _K2>
1400 _LIBCPP_INLINE_VISIBILITY
1401 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
1402 find(const _K2& __k) const {return __tree_.find(__k);}
1403#endif
1404
Howard Hinnant756c69b2010-09-22 16:48:34 +00001405 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001406 size_type count(const key_type& __k) const
1407 {return __tree_.__count_unique(__k);}
Marshall Clowe6a5f522014-08-24 23:54:16 +00001408#if _LIBCPP_STD_VER > 11
1409 template <typename _K2>
1410 _LIBCPP_INLINE_VISIBILITY
1411 typename enable_if<__is_transparent<_Compare, _K2>::value,size_type>::type
Eric Fiseliera85c9e92018-02-10 02:53:47 +00001412 count(const _K2& __k) const {return __tree_.__count_multi(__k);}
Marshall Clowe6a5f522014-08-24 23:54:16 +00001413#endif
Zoe Carver3ffbab12019-07-16 03:21:01 +00001414
1415#if _LIBCPP_STD_VER > 17
1416 _LIBCPP_INLINE_VISIBILITY
1417 bool contains(const key_type& __k) const {return find(__k) != end();}
Marek Kurdejd7e019e2021-04-13 17:10:55 +02001418 template <typename _K2>
1419 _LIBCPP_INLINE_VISIBILITY
1420 typename enable_if<__is_transparent<_Compare, _K2>::value, bool>::type
1421 contains(const _K2& __k) const { return find(__k) != end(); }
Zoe Carver3ffbab12019-07-16 03:21:01 +00001422#endif // _LIBCPP_STD_VER > 17
1423
Howard Hinnant756c69b2010-09-22 16:48:34 +00001424 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001425 iterator lower_bound(const key_type& __k)
1426 {return __tree_.lower_bound(__k);}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001427 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001428 const_iterator lower_bound(const key_type& __k) const
1429 {return __tree_.lower_bound(__k);}
Marshall Clowebb57322013-08-13 22:18:47 +00001430#if _LIBCPP_STD_VER > 11
1431 template <typename _K2>
1432 _LIBCPP_INLINE_VISIBILITY
1433 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
1434 lower_bound(const _K2& __k) {return __tree_.lower_bound(__k);}
1435
1436 template <typename _K2>
1437 _LIBCPP_INLINE_VISIBILITY
1438 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
1439 lower_bound(const _K2& __k) const {return __tree_.lower_bound(__k);}
1440#endif
1441
Howard Hinnant756c69b2010-09-22 16:48:34 +00001442 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001443 iterator upper_bound(const key_type& __k)
1444 {return __tree_.upper_bound(__k);}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001445 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001446 const_iterator upper_bound(const key_type& __k) const
1447 {return __tree_.upper_bound(__k);}
Marshall Clowebb57322013-08-13 22:18:47 +00001448#if _LIBCPP_STD_VER > 11
1449 template <typename _K2>
1450 _LIBCPP_INLINE_VISIBILITY
1451 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
1452 upper_bound(const _K2& __k) {return __tree_.upper_bound(__k);}
1453 template <typename _K2>
1454 _LIBCPP_INLINE_VISIBILITY
1455 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
1456 upper_bound(const _K2& __k) const {return __tree_.upper_bound(__k);}
1457#endif
1458
Howard Hinnant756c69b2010-09-22 16:48:34 +00001459 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001460 pair<iterator,iterator> equal_range(const key_type& __k)
1461 {return __tree_.__equal_range_unique(__k);}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001462 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001463 pair<const_iterator,const_iterator> equal_range(const key_type& __k) const
1464 {return __tree_.__equal_range_unique(__k);}
Marshall Clowebb57322013-08-13 22:18:47 +00001465#if _LIBCPP_STD_VER > 11
1466 template <typename _K2>
1467 _LIBCPP_INLINE_VISIBILITY
1468 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<iterator,iterator>>::type
Eric Fiseliera85c9e92018-02-10 02:53:47 +00001469 equal_range(const _K2& __k) {return __tree_.__equal_range_multi(__k);}
Marshall Clowebb57322013-08-13 22:18:47 +00001470 template <typename _K2>
1471 _LIBCPP_INLINE_VISIBILITY
1472 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<const_iterator,const_iterator>>::type
Eric Fiseliera85c9e92018-02-10 02:53:47 +00001473 equal_range(const _K2& __k) const {return __tree_.__equal_range_multi(__k);}
Marshall Clowebb57322013-08-13 22:18:47 +00001474#endif
Howard Hinnantc51e1022010-05-11 19:42:16 +00001475
1476private:
1477 typedef typename __base::__node __node;
1478 typedef typename __base::__node_allocator __node_allocator;
1479 typedef typename __base::__node_pointer __node_pointer;
Howard Hinnantc51e1022010-05-11 19:42:16 +00001480 typedef typename __base::__node_base_pointer __node_base_pointer;
Eric Fiseliercf8c0212017-01-05 06:06:18 +00001481 typedef typename __base::__parent_pointer __parent_pointer;
Eric Fiseliera92b0732016-02-20 07:12:17 +00001482
Howard Hinnantc834c512011-11-29 18:15:50 +00001483 typedef __map_node_destructor<__node_allocator> _Dp;
1484 typedef unique_ptr<__node, _Dp> __node_holder;
Howard Hinnantc51e1022010-05-11 19:42:16 +00001485
Eric Fiselierd63f38e2016-03-31 03:13:37 +00001486#ifdef _LIBCPP_CXX03_LANG
Howard Hinnantac7e7482013-07-04 20:59:16 +00001487 __node_holder __construct_node_with_key(const key_type& __k);
Eric Fiselierd63f38e2016-03-31 03:13:37 +00001488#endif
Howard Hinnantc51e1022010-05-11 19:42:16 +00001489};
1490
Louis Dionned23a5f22019-06-20 19:32:00 +00001491#ifndef _LIBCPP_HAS_NO_DEDUCTION_GUIDES
1492template<class _InputIterator, class _Compare = less<__iter_key_type<_InputIterator>>,
1493 class _Allocator = allocator<__iter_to_alloc_type<_InputIterator>>,
Louis Dionne6c7da9a2019-07-19 17:13:39 +00001494 class = _EnableIf<!__is_allocator<_Compare>::value, void>,
1495 class = _EnableIf<__is_allocator<_Allocator>::value, void>>
Louis Dionned23a5f22019-06-20 19:32:00 +00001496map(_InputIterator, _InputIterator, _Compare = _Compare(), _Allocator = _Allocator())
1497 -> map<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>, _Compare, _Allocator>;
1498
1499template<class _Key, class _Tp, class _Compare = less<remove_const_t<_Key>>,
1500 class _Allocator = allocator<pair<const _Key, _Tp>>,
Louis Dionne6c7da9a2019-07-19 17:13:39 +00001501 class = _EnableIf<!__is_allocator<_Compare>::value, void>,
1502 class = _EnableIf<__is_allocator<_Allocator>::value, void>>
Louis Dionned23a5f22019-06-20 19:32:00 +00001503map(initializer_list<pair<_Key, _Tp>>, _Compare = _Compare(), _Allocator = _Allocator())
1504 -> map<remove_const_t<_Key>, _Tp, _Compare, _Allocator>;
1505
1506template<class _InputIterator, class _Allocator,
Louis Dionne6c7da9a2019-07-19 17:13:39 +00001507 class = _EnableIf<__is_allocator<_Allocator>::value, void>>
Louis Dionned23a5f22019-06-20 19:32:00 +00001508map(_InputIterator, _InputIterator, _Allocator)
1509 -> map<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>,
1510 less<__iter_key_type<_InputIterator>>, _Allocator>;
1511
1512template<class _Key, class _Tp, class _Allocator,
Louis Dionne6c7da9a2019-07-19 17:13:39 +00001513 class = _EnableIf<__is_allocator<_Allocator>::value, void>>
Louis Dionned23a5f22019-06-20 19:32:00 +00001514map(initializer_list<pair<_Key, _Tp>>, _Allocator)
1515 -> map<remove_const_t<_Key>, _Tp, less<remove_const_t<_Key>>, _Allocator>;
1516#endif
Eric Fiseliera92b0732016-02-20 07:12:17 +00001517
Eric Fiselierd06276b2016-03-31 02:15:15 +00001518#ifndef _LIBCPP_CXX03_LANG
Howard Hinnantc51e1022010-05-11 19:42:16 +00001519template <class _Key, class _Tp, class _Compare, class _Allocator>
1520map<_Key, _Tp, _Compare, _Allocator>::map(map&& __m, const allocator_type& __a)
Marshall Clow657cbc42016-08-17 05:58:40 +00001521 : __tree_(_VSTD::move(__m.__tree_), typename __base::allocator_type(__a))
Howard Hinnantc51e1022010-05-11 19:42:16 +00001522{
1523 if (__a != __m.get_allocator())
1524 {
1525 const_iterator __e = cend();
1526 while (!__m.empty())
1527 __tree_.__insert_unique(__e.__i_,
Erik Pilkingtond3fe2992018-06-04 20:38:23 +00001528 __m.__tree_.remove(__m.begin().__i_)->__value_.__move());
Howard Hinnantc51e1022010-05-11 19:42:16 +00001529 }
1530}
1531
Eric Fiseliera85b1282017-04-18 21:08:06 +00001532template <class _Key, class _Tp, class _Compare, class _Allocator>
1533_Tp&
1534map<_Key, _Tp, _Compare, _Allocator>::operator[](const key_type& __k)
1535{
1536 return __tree_.__emplace_unique_key_args(__k,
1537 _VSTD::piecewise_construct,
1538 _VSTD::forward_as_tuple(__k),
Erik Pilkingtond3fe2992018-06-04 20:38:23 +00001539 _VSTD::forward_as_tuple()).first->__get_value().second;
Eric Fiseliera85b1282017-04-18 21:08:06 +00001540}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001541
Eric Fiseliera85b1282017-04-18 21:08:06 +00001542template <class _Key, class _Tp, class _Compare, class _Allocator>
1543_Tp&
1544map<_Key, _Tp, _Compare, _Allocator>::operator[](key_type&& __k)
1545{
1546 return __tree_.__emplace_unique_key_args(__k,
1547 _VSTD::piecewise_construct,
1548 _VSTD::forward_as_tuple(_VSTD::move(__k)),
Erik Pilkingtond3fe2992018-06-04 20:38:23 +00001549 _VSTD::forward_as_tuple()).first->__get_value().second;
Eric Fiseliera85b1282017-04-18 21:08:06 +00001550}
Eric Fiselierd63f38e2016-03-31 03:13:37 +00001551
Eric Fiseliera85b1282017-04-18 21:08:06 +00001552#else // _LIBCPP_CXX03_LANG
Eric Fiselierd63f38e2016-03-31 03:13:37 +00001553
Howard Hinnantc51e1022010-05-11 19:42:16 +00001554template <class _Key, class _Tp, class _Compare, class _Allocator>
1555typename map<_Key, _Tp, _Compare, _Allocator>::__node_holder
Howard Hinnantac7e7482013-07-04 20:59:16 +00001556map<_Key, _Tp, _Compare, _Allocator>::__construct_node_with_key(const key_type& __k)
Howard Hinnantc51e1022010-05-11 19:42:16 +00001557{
1558 __node_allocator& __na = __tree_.__node_alloc();
Howard Hinnantc834c512011-11-29 18:15:50 +00001559 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
Erik Pilkingtond3fe2992018-06-04 20:38:23 +00001560 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__get_value().first), __k);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001561 __h.get_deleter().__first_constructed = true;
Erik Pilkingtond3fe2992018-06-04 20:38:23 +00001562 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__get_value().second));
Howard Hinnantc51e1022010-05-11 19:42:16 +00001563 __h.get_deleter().__second_constructed = true;
Louis Dionne7b844362020-07-30 09:42:23 -04001564 return __h;
Howard Hinnantc51e1022010-05-11 19:42:16 +00001565}
1566
Howard Hinnantc51e1022010-05-11 19:42:16 +00001567template <class _Key, class _Tp, class _Compare, class _Allocator>
1568_Tp&
1569map<_Key, _Tp, _Compare, _Allocator>::operator[](const key_type& __k)
1570{
Eric Fiseliercf8c0212017-01-05 06:06:18 +00001571 __parent_pointer __parent;
1572 __node_base_pointer& __child = __tree_.__find_equal(__parent, __k);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001573 __node_pointer __r = static_cast<__node_pointer>(__child);
1574 if (__child == nullptr)
1575 {
Howard Hinnantac7e7482013-07-04 20:59:16 +00001576 __node_holder __h = __construct_node_with_key(__k);
Howard Hinnant2d0046b2013-06-19 21:29:40 +00001577 __tree_.__insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
Howard Hinnantc51e1022010-05-11 19:42:16 +00001578 __r = __h.release();
1579 }
Erik Pilkingtond3fe2992018-06-04 20:38:23 +00001580 return __r->__value_.__get_value().second;
Howard Hinnantc51e1022010-05-11 19:42:16 +00001581}
1582
Louis Dionne2b1ceaa2021-04-20 12:03:32 -04001583#endif // _LIBCPP_CXX03_LANG
Howard Hinnantc51e1022010-05-11 19:42:16 +00001584
1585template <class _Key, class _Tp, class _Compare, class _Allocator>
1586_Tp&
1587map<_Key, _Tp, _Compare, _Allocator>::at(const key_type& __k)
1588{
Eric Fiseliercf8c0212017-01-05 06:06:18 +00001589 __parent_pointer __parent;
1590 __node_base_pointer& __child = __tree_.__find_equal(__parent, __k);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001591 if (__child == nullptr)
Louis Dionne2b239162019-02-12 16:06:02 +00001592 __throw_out_of_range("map::at: key not found");
Erik Pilkingtond3fe2992018-06-04 20:38:23 +00001593 return static_cast<__node_pointer>(__child)->__value_.__get_value().second;
Howard Hinnantc51e1022010-05-11 19:42:16 +00001594}
1595
1596template <class _Key, class _Tp, class _Compare, class _Allocator>
1597const _Tp&
1598map<_Key, _Tp, _Compare, _Allocator>::at(const key_type& __k) const
1599{
Eric Fiseliercf8c0212017-01-05 06:06:18 +00001600 __parent_pointer __parent;
1601 __node_base_pointer __child = __tree_.__find_equal(__parent, __k);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001602 if (__child == nullptr)
Louis Dionne2b239162019-02-12 16:06:02 +00001603 __throw_out_of_range("map::at: key not found");
Erik Pilkingtond3fe2992018-06-04 20:38:23 +00001604 return static_cast<__node_pointer>(__child)->__value_.__get_value().second;
Howard Hinnantc51e1022010-05-11 19:42:16 +00001605}
1606
Howard Hinnantc51e1022010-05-11 19:42:16 +00001607
1608template <class _Key, class _Tp, class _Compare, class _Allocator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001609inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001610bool
1611operator==(const map<_Key, _Tp, _Compare, _Allocator>& __x,
1612 const map<_Key, _Tp, _Compare, _Allocator>& __y)
1613{
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001614 return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin());
Howard Hinnantc51e1022010-05-11 19:42:16 +00001615}
1616
1617template <class _Key, class _Tp, class _Compare, class _Allocator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001618inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001619bool
1620operator< (const map<_Key, _Tp, _Compare, _Allocator>& __x,
1621 const map<_Key, _Tp, _Compare, _Allocator>& __y)
1622{
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001623 return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
Howard Hinnantc51e1022010-05-11 19:42:16 +00001624}
1625
1626template <class _Key, class _Tp, class _Compare, class _Allocator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001627inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001628bool
1629operator!=(const map<_Key, _Tp, _Compare, _Allocator>& __x,
1630 const map<_Key, _Tp, _Compare, _Allocator>& __y)
1631{
1632 return !(__x == __y);
1633}
1634
1635template <class _Key, class _Tp, class _Compare, class _Allocator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001636inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001637bool
1638operator> (const map<_Key, _Tp, _Compare, _Allocator>& __x,
1639 const map<_Key, _Tp, _Compare, _Allocator>& __y)
1640{
1641 return __y < __x;
1642}
1643
1644template <class _Key, class _Tp, class _Compare, class _Allocator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001645inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001646bool
1647operator>=(const map<_Key, _Tp, _Compare, _Allocator>& __x,
1648 const map<_Key, _Tp, _Compare, _Allocator>& __y)
1649{
1650 return !(__x < __y);
1651}
1652
1653template <class _Key, class _Tp, class _Compare, class _Allocator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001654inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001655bool
1656operator<=(const map<_Key, _Tp, _Compare, _Allocator>& __x,
1657 const map<_Key, _Tp, _Compare, _Allocator>& __y)
1658{
1659 return !(__y < __x);
1660}
1661
1662template <class _Key, class _Tp, class _Compare, class _Allocator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001663inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001664void
1665swap(map<_Key, _Tp, _Compare, _Allocator>& __x,
1666 map<_Key, _Tp, _Compare, _Allocator>& __y)
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001667 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
Howard Hinnantc51e1022010-05-11 19:42:16 +00001668{
1669 __x.swap(__y);
1670}
1671
Marshall Clow29b53f22018-12-14 18:49:35 +00001672#if _LIBCPP_STD_VER > 17
Marek Kurdeja98b1412020-05-02 13:58:03 +02001673template <class _Key, class _Tp, class _Compare, class _Allocator,
1674 class _Predicate>
Marshall Clow29b53f22018-12-14 18:49:35 +00001675inline _LIBCPP_INLINE_VISIBILITY
Marek Kurdeja98b1412020-05-02 13:58:03 +02001676 typename map<_Key, _Tp, _Compare, _Allocator>::size_type
1677 erase_if(map<_Key, _Tp, _Compare, _Allocator>& __c, _Predicate __pred) {
Arthur O'Dwyerb6738bd2021-03-21 16:53:09 -04001678 return _VSTD::__libcpp_erase_if_container(__c, __pred);
Marek Kurdeja98b1412020-05-02 13:58:03 +02001679}
Marshall Clow29b53f22018-12-14 18:49:35 +00001680#endif
1681
1682
Howard Hinnantc51e1022010-05-11 19:42:16 +00001683template <class _Key, class _Tp, class _Compare = less<_Key>,
1684 class _Allocator = allocator<pair<const _Key, _Tp> > >
Eric Fiselierb5eb1bf2017-01-04 23:56:00 +00001685class _LIBCPP_TEMPLATE_VIS multimap
Howard Hinnantc51e1022010-05-11 19:42:16 +00001686{
1687public:
1688 // types:
1689 typedef _Key key_type;
1690 typedef _Tp mapped_type;
1691 typedef pair<const key_type, mapped_type> value_type;
Arthur O'Dwyer6a752e12021-03-03 11:10:49 -05001692 typedef __identity_t<_Compare> key_compare;
1693 typedef __identity_t<_Allocator> allocator_type;
Howard Hinnantc51e1022010-05-11 19:42:16 +00001694 typedef value_type& reference;
1695 typedef const value_type& const_reference;
1696
Marshall Clow5128cf32015-11-26 01:24:04 +00001697 static_assert((is_same<typename allocator_type::value_type, value_type>::value),
1698 "Allocator::value_type must be same type as value_type");
1699
Eric Fiselierb5eb1bf2017-01-04 23:56:00 +00001700 class _LIBCPP_TEMPLATE_VIS value_compare
Howard Hinnantc51e1022010-05-11 19:42:16 +00001701 : public binary_function<value_type, value_type, bool>
1702 {
1703 friend class multimap;
1704 protected:
1705 key_compare comp;
1706
Howard Hinnant756c69b2010-09-22 16:48:34 +00001707 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001708 value_compare(key_compare c) : comp(c) {}
1709 public:
Howard Hinnant756c69b2010-09-22 16:48:34 +00001710 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001711 bool operator()(const value_type& __x, const value_type& __y) const
1712 {return comp(__x.first, __y.first);}
1713 };
1714
1715private:
Howard Hinnant2d0046b2013-06-19 21:29:40 +00001716
Howard Hinnant89f8b792013-09-30 19:08:22 +00001717 typedef _VSTD::__value_type<key_type, mapped_type> __value_type;
Howard Hinnant90b91592013-07-05 18:06:00 +00001718 typedef __map_value_compare<key_type, __value_type, key_compare> __vc;
Marshall Clow940e01c2015-04-07 05:21:38 +00001719 typedef typename __rebind_alloc_helper<allocator_traits<allocator_type>,
1720 __value_type>::type __allocator_type;
Howard Hinnantc51e1022010-05-11 19:42:16 +00001721 typedef __tree<__value_type, __vc, __allocator_type> __base;
1722 typedef typename __base::__node_traits __node_traits;
1723 typedef allocator_traits<allocator_type> __alloc_traits;
1724
1725 __base __tree_;
1726
1727public:
1728 typedef typename __alloc_traits::pointer pointer;
1729 typedef typename __alloc_traits::const_pointer const_pointer;
1730 typedef typename __alloc_traits::size_type size_type;
1731 typedef typename __alloc_traits::difference_type difference_type;
1732 typedef __map_iterator<typename __base::iterator> iterator;
1733 typedef __map_const_iterator<typename __base::const_iterator> const_iterator;
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001734 typedef _VSTD::reverse_iterator<iterator> reverse_iterator;
1735 typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator;
Howard Hinnantc51e1022010-05-11 19:42:16 +00001736
Erik Pilkingtonc37a3d82018-08-01 01:33:38 +00001737#if _LIBCPP_STD_VER > 14
1738 typedef __map_node_handle<typename __base::__node, allocator_type> node_type;
1739#endif
1740
Erik Pilkington82a65ad2018-10-31 17:31:35 +00001741 template <class _Key2, class _Value2, class _Comp2, class _Alloc2>
1742 friend class _LIBCPP_TEMPLATE_VIS map;
1743 template <class _Key2, class _Value2, class _Comp2, class _Alloc2>
1744 friend class _LIBCPP_TEMPLATE_VIS multimap;
1745
Howard Hinnant756c69b2010-09-22 16:48:34 +00001746 _LIBCPP_INLINE_VISIBILITY
Marshall Clow7086a5a2014-03-10 04:50:10 +00001747 multimap()
1748 _NOEXCEPT_(
1749 is_nothrow_default_constructible<allocator_type>::value &&
1750 is_nothrow_default_constructible<key_compare>::value &&
1751 is_nothrow_copy_constructible<key_compare>::value)
1752 : __tree_(__vc(key_compare())) {}
1753
1754 _LIBCPP_INLINE_VISIBILITY
1755 explicit multimap(const key_compare& __comp)
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001756 _NOEXCEPT_(
1757 is_nothrow_default_constructible<allocator_type>::value &&
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001758 is_nothrow_copy_constructible<key_compare>::value)
Howard Hinnantc51e1022010-05-11 19:42:16 +00001759 : __tree_(__vc(__comp)) {}
1760
Howard Hinnant756c69b2010-09-22 16:48:34 +00001761 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001762 explicit multimap(const key_compare& __comp, const allocator_type& __a)
Marshall Clow657cbc42016-08-17 05:58:40 +00001763 : __tree_(__vc(__comp), typename __base::allocator_type(__a)) {}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001764
1765 template <class _InputIterator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001766 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001767 multimap(_InputIterator __f, _InputIterator __l,
1768 const key_compare& __comp = key_compare())
1769 : __tree_(__vc(__comp))
1770 {
1771 insert(__f, __l);
1772 }
1773
1774 template <class _InputIterator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001775 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001776 multimap(_InputIterator __f, _InputIterator __l,
1777 const key_compare& __comp, const allocator_type& __a)
Marshall Clow657cbc42016-08-17 05:58:40 +00001778 : __tree_(__vc(__comp), typename __base::allocator_type(__a))
Howard Hinnantc51e1022010-05-11 19:42:16 +00001779 {
1780 insert(__f, __l);
1781 }
1782
Marshall Clow300abfb2013-09-11 01:15:47 +00001783#if _LIBCPP_STD_VER > 11
1784 template <class _InputIterator>
Eric Fiseliercf8c0212017-01-05 06:06:18 +00001785 _LIBCPP_INLINE_VISIBILITY
Marshall Clow300abfb2013-09-11 01:15:47 +00001786 multimap(_InputIterator __f, _InputIterator __l, const allocator_type& __a)
1787 : multimap(__f, __l, key_compare(), __a) {}
1788#endif
1789
Howard Hinnant756c69b2010-09-22 16:48:34 +00001790 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001791 multimap(const multimap& __m)
1792 : __tree_(__m.__tree_.value_comp(),
1793 __alloc_traits::select_on_container_copy_construction(__m.__tree_.__alloc()))
1794 {
1795 insert(__m.begin(), __m.end());
1796 }
1797
Howard Hinnantd3a657f2011-07-01 19:24:36 +00001798 _LIBCPP_INLINE_VISIBILITY
1799 multimap& operator=(const multimap& __m)
1800 {
Marshall Clow476d3f42016-07-18 13:19:00 +00001801#ifndef _LIBCPP_CXX03_LANG
Howard Hinnantd3a657f2011-07-01 19:24:36 +00001802 __tree_ = __m.__tree_;
Howard Hinnant2d0046b2013-06-19 21:29:40 +00001803#else
Marshall Clowdb3cfcb2014-02-08 04:03:14 +00001804 if (this != &__m) {
1805 __tree_.clear();
1806 __tree_.value_comp() = __m.__tree_.value_comp();
1807 __tree_.__copy_assign_alloc(__m.__tree_);
1808 insert(__m.begin(), __m.end());
1809 }
Howard Hinnant2d0046b2013-06-19 21:29:40 +00001810#endif
Howard Hinnantd3a657f2011-07-01 19:24:36 +00001811 return *this;
1812 }
1813
Eric Fiseliera85b1282017-04-18 21:08:06 +00001814#ifndef _LIBCPP_CXX03_LANG
Howard Hinnantc51e1022010-05-11 19:42:16 +00001815
Howard Hinnant756c69b2010-09-22 16:48:34 +00001816 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001817 multimap(multimap&& __m)
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001818 _NOEXCEPT_(is_nothrow_move_constructible<__base>::value)
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001819 : __tree_(_VSTD::move(__m.__tree_))
Howard Hinnantc51e1022010-05-11 19:42:16 +00001820 {
1821 }
1822
1823 multimap(multimap&& __m, const allocator_type& __a);
1824
Howard Hinnant756c69b2010-09-22 16:48:34 +00001825 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant33711792011-08-12 21:56:02 +00001826 multimap& operator=(multimap&& __m)
1827 _NOEXCEPT_(is_nothrow_move_assignable<__base>::value)
1828 {
1829 __tree_ = _VSTD::move(__m.__tree_);
1830 return *this;
1831 }
1832
Howard Hinnant33711792011-08-12 21:56:02 +00001833 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001834 multimap(initializer_list<value_type> __il, const key_compare& __comp = key_compare())
1835 : __tree_(__vc(__comp))
1836 {
1837 insert(__il.begin(), __il.end());
1838 }
1839
Howard Hinnant756c69b2010-09-22 16:48:34 +00001840 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001841 multimap(initializer_list<value_type> __il, const key_compare& __comp, const allocator_type& __a)
Marshall Clow657cbc42016-08-17 05:58:40 +00001842 : __tree_(__vc(__comp), typename __base::allocator_type(__a))
Howard Hinnantc51e1022010-05-11 19:42:16 +00001843 {
1844 insert(__il.begin(), __il.end());
1845 }
1846
Marshall Clow300abfb2013-09-11 01:15:47 +00001847#if _LIBCPP_STD_VER > 11
Eric Fiseliercf8c0212017-01-05 06:06:18 +00001848 _LIBCPP_INLINE_VISIBILITY
Marshall Clow300abfb2013-09-11 01:15:47 +00001849 multimap(initializer_list<value_type> __il, const allocator_type& __a)
1850 : multimap(__il, key_compare(), __a) {}
1851#endif
1852
Howard Hinnant756c69b2010-09-22 16:48:34 +00001853 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001854 multimap& operator=(initializer_list<value_type> __il)
1855 {
1856 __tree_.__assign_multi(__il.begin(), __il.end());
1857 return *this;
1858 }
Howard Hinnant33711792011-08-12 21:56:02 +00001859
Louis Dionne2b1ceaa2021-04-20 12:03:32 -04001860#endif // _LIBCPP_CXX03_LANG
Howard Hinnantc51e1022010-05-11 19:42:16 +00001861
Howard Hinnant756c69b2010-09-22 16:48:34 +00001862 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001863 explicit multimap(const allocator_type& __a)
Marshall Clow657cbc42016-08-17 05:58:40 +00001864 : __tree_(typename __base::allocator_type(__a))
Howard Hinnantc51e1022010-05-11 19:42:16 +00001865 {
1866 }
1867
Howard Hinnant756c69b2010-09-22 16:48:34 +00001868 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001869 multimap(const multimap& __m, const allocator_type& __a)
Marshall Clow657cbc42016-08-17 05:58:40 +00001870 : __tree_(__m.__tree_.value_comp(), typename __base::allocator_type(__a))
Howard Hinnantc51e1022010-05-11 19:42:16 +00001871 {
1872 insert(__m.begin(), __m.end());
1873 }
1874
Howard Hinnant756c69b2010-09-22 16:48:34 +00001875 _LIBCPP_INLINE_VISIBILITY
Louis Dionne69c42c02019-04-11 16:14:56 +00001876 ~multimap() {
1877 static_assert(sizeof(__diagnose_non_const_comparator<_Key, _Compare>()), "");
1878 }
1879
1880 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001881 iterator begin() _NOEXCEPT {return __tree_.begin();}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001882 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001883 const_iterator begin() const _NOEXCEPT {return __tree_.begin();}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001884 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001885 iterator end() _NOEXCEPT {return __tree_.end();}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001886 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001887 const_iterator end() const _NOEXCEPT {return __tree_.end();}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001888
Howard Hinnant756c69b2010-09-22 16:48:34 +00001889 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001890 reverse_iterator rbegin() _NOEXCEPT {return reverse_iterator(end());}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001891 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001892 const_reverse_iterator rbegin() const _NOEXCEPT
1893 {return const_reverse_iterator(end());}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001894 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001895 reverse_iterator rend() _NOEXCEPT {return reverse_iterator(begin());}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001896 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001897 const_reverse_iterator rend() const _NOEXCEPT
1898 {return const_reverse_iterator(begin());}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001899
Howard Hinnant756c69b2010-09-22 16:48:34 +00001900 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001901 const_iterator cbegin() const _NOEXCEPT {return begin();}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001902 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001903 const_iterator cend() const _NOEXCEPT {return end();}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001904 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001905 const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001906 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001907 const_reverse_iterator crend() const _NOEXCEPT {return rend();}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001908
Marshall Clow425f5752017-11-15 05:51:26 +00001909 _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001910 bool empty() const _NOEXCEPT {return __tree_.size() == 0;}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001911 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001912 size_type size() const _NOEXCEPT {return __tree_.size();}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001913 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001914 size_type max_size() const _NOEXCEPT {return __tree_.max_size();}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001915
Howard Hinnant756c69b2010-09-22 16:48:34 +00001916 _LIBCPP_INLINE_VISIBILITY
Marshall Clow657cbc42016-08-17 05:58:40 +00001917 allocator_type get_allocator() const _NOEXCEPT {return allocator_type(__tree_.__alloc());}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001918 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001919 key_compare key_comp() const {return __tree_.value_comp().key_comp();}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001920 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001921 value_compare value_comp() const
1922 {return value_compare(__tree_.value_comp().key_comp());}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001923
Eric Fiselierd06276b2016-03-31 02:15:15 +00001924#ifndef _LIBCPP_CXX03_LANG
Howard Hinnant74279a52010-09-04 23:28:19 +00001925
Howard Hinnant29eb9b82012-05-25 22:04:21 +00001926 template <class ..._Args>
Eric Fiselierd06276b2016-03-31 02:15:15 +00001927 _LIBCPP_INLINE_VISIBILITY
1928 iterator emplace(_Args&& ...__args) {
1929 return __tree_.__emplace_multi(_VSTD::forward<_Args>(__args)...);
1930 }
Howard Hinnantc51e1022010-05-11 19:42:16 +00001931
Howard Hinnant29eb9b82012-05-25 22:04:21 +00001932 template <class ..._Args>
Eric Fiselierd06276b2016-03-31 02:15:15 +00001933 _LIBCPP_INLINE_VISIBILITY
1934 iterator emplace_hint(const_iterator __p, _Args&& ...__args) {
1935 return __tree_.__emplace_hint_multi(__p.__i_, _VSTD::forward<_Args>(__args)...);
1936 }
Howard Hinnant74279a52010-09-04 23:28:19 +00001937
Howard Hinnantc834c512011-11-29 18:15:50 +00001938 template <class _Pp,
1939 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001940 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc834c512011-11-29 18:15:50 +00001941 iterator insert(_Pp&& __p)
1942 {return __tree_.__insert_multi(_VSTD::forward<_Pp>(__p));}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001943
Howard Hinnantc834c512011-11-29 18:15:50 +00001944 template <class _Pp,
1945 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001946 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc834c512011-11-29 18:15:50 +00001947 iterator insert(const_iterator __pos, _Pp&& __p)
1948 {return __tree_.__insert_multi(__pos.__i_, _VSTD::forward<_Pp>(__p));}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001949
Eric Fiselierd6143132016-04-18 01:40:45 +00001950 _LIBCPP_INLINE_VISIBILITY
1951 iterator insert(value_type&& __v)
1952 {return __tree_.__insert_multi(_VSTD::move(__v));}
1953
1954 _LIBCPP_INLINE_VISIBILITY
1955 iterator insert(const_iterator __p, value_type&& __v)
1956 {return __tree_.__insert_multi(__p.__i_, _VSTD::move(__v));}
1957
Eric Fiseliera85b1282017-04-18 21:08:06 +00001958
1959 _LIBCPP_INLINE_VISIBILITY
1960 void insert(initializer_list<value_type> __il)
1961 {insert(__il.begin(), __il.end());}
1962
Louis Dionne2b1ceaa2021-04-20 12:03:32 -04001963#endif // _LIBCPP_CXX03_LANG
Howard Hinnantc51e1022010-05-11 19:42:16 +00001964
Howard Hinnant756c69b2010-09-22 16:48:34 +00001965 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001966 iterator insert(const value_type& __v) {return __tree_.__insert_multi(__v);}
1967
Howard Hinnant756c69b2010-09-22 16:48:34 +00001968 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001969 iterator insert(const_iterator __p, const value_type& __v)
1970 {return __tree_.__insert_multi(__p.__i_, __v);}
1971
1972 template <class _InputIterator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001973 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001974 void insert(_InputIterator __f, _InputIterator __l)
1975 {
1976 for (const_iterator __e = cend(); __f != __l; ++__f)
1977 __tree_.__insert_multi(__e.__i_, *__f);
1978 }
1979
Howard Hinnant756c69b2010-09-22 16:48:34 +00001980 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001981 iterator erase(const_iterator __p) {return __tree_.erase(__p.__i_);}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001982 _LIBCPP_INLINE_VISIBILITY
Marshall Clow22ea5b82015-05-10 13:35:00 +00001983 iterator erase(iterator __p) {return __tree_.erase(__p.__i_);}
1984 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001985 size_type erase(const key_type& __k) {return __tree_.__erase_multi(__k);}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001986 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001987 iterator erase(const_iterator __f, const_iterator __l)
1988 {return __tree_.erase(__f.__i_, __l.__i_);}
Erik Pilkingtonc37a3d82018-08-01 01:33:38 +00001989
1990#if _LIBCPP_STD_VER > 14
1991 _LIBCPP_INLINE_VISIBILITY
1992 iterator insert(node_type&& __nh)
1993 {
1994 _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(),
1995 "node_type with incompatible allocator passed to multimap::insert()");
1996 return __tree_.template __node_handle_insert_multi<node_type>(
1997 _VSTD::move(__nh));
1998 }
1999 _LIBCPP_INLINE_VISIBILITY
2000 iterator insert(const_iterator __hint, node_type&& __nh)
2001 {
2002 _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(),
2003 "node_type with incompatible allocator passed to multimap::insert()");
2004 return __tree_.template __node_handle_insert_multi<node_type>(
2005 __hint.__i_, _VSTD::move(__nh));
2006 }
2007 _LIBCPP_INLINE_VISIBILITY
2008 node_type extract(key_type const& __key)
2009 {
2010 return __tree_.template __node_handle_extract<node_type>(__key);
2011 }
2012 _LIBCPP_INLINE_VISIBILITY
2013 node_type extract(const_iterator __it)
2014 {
2015 return __tree_.template __node_handle_extract<node_type>(
2016 __it.__i_);
2017 }
Louis Dionned2322c82018-11-01 14:41:37 +00002018 template <class _Compare2>
Erik Pilkington82a65ad2018-10-31 17:31:35 +00002019 _LIBCPP_INLINE_VISIBILITY
Louis Dionned2322c82018-11-01 14:41:37 +00002020 void merge(multimap<key_type, mapped_type, _Compare2, allocator_type>& __source)
Erik Pilkington82a65ad2018-10-31 17:31:35 +00002021 {
2022 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
2023 "merging container with incompatible allocator");
2024 return __tree_.__node_handle_merge_multi(__source.__tree_);
2025 }
Louis Dionned2322c82018-11-01 14:41:37 +00002026 template <class _Compare2>
Erik Pilkington82a65ad2018-10-31 17:31:35 +00002027 _LIBCPP_INLINE_VISIBILITY
Louis Dionned2322c82018-11-01 14:41:37 +00002028 void merge(multimap<key_type, mapped_type, _Compare2, allocator_type>&& __source)
Erik Pilkington82a65ad2018-10-31 17:31:35 +00002029 {
2030 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
2031 "merging container with incompatible allocator");
2032 return __tree_.__node_handle_merge_multi(__source.__tree_);
2033 }
Louis Dionned2322c82018-11-01 14:41:37 +00002034 template <class _Compare2>
Erik Pilkington82a65ad2018-10-31 17:31:35 +00002035 _LIBCPP_INLINE_VISIBILITY
Louis Dionned2322c82018-11-01 14:41:37 +00002036 void merge(map<key_type, mapped_type, _Compare2, allocator_type>& __source)
Erik Pilkington82a65ad2018-10-31 17:31:35 +00002037 {
2038 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
2039 "merging container with incompatible allocator");
2040 return __tree_.__node_handle_merge_multi(__source.__tree_);
2041 }
Louis Dionned2322c82018-11-01 14:41:37 +00002042 template <class _Compare2>
Erik Pilkington82a65ad2018-10-31 17:31:35 +00002043 _LIBCPP_INLINE_VISIBILITY
Louis Dionned2322c82018-11-01 14:41:37 +00002044 void merge(map<key_type, mapped_type, _Compare2, allocator_type>&& __source)
Erik Pilkington82a65ad2018-10-31 17:31:35 +00002045 {
2046 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
2047 "merging container with incompatible allocator");
2048 return __tree_.__node_handle_merge_multi(__source.__tree_);
2049 }
Erik Pilkingtonc37a3d82018-08-01 01:33:38 +00002050#endif
2051
Howard Hinnant756c69b2010-09-22 16:48:34 +00002052 _LIBCPP_INLINE_VISIBILITY
Marshall Clowde1312a2018-08-22 04:28:43 +00002053 void clear() _NOEXCEPT {__tree_.clear();}
Howard Hinnantc51e1022010-05-11 19:42:16 +00002054
Howard Hinnant756c69b2010-09-22 16:48:34 +00002055 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00002056 void swap(multimap& __m)
2057 _NOEXCEPT_(__is_nothrow_swappable<__base>::value)
2058 {__tree_.swap(__m.__tree_);}
Howard Hinnantc51e1022010-05-11 19:42:16 +00002059
Howard Hinnant756c69b2010-09-22 16:48:34 +00002060 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00002061 iterator find(const key_type& __k) {return __tree_.find(__k);}
Howard Hinnant756c69b2010-09-22 16:48:34 +00002062 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00002063 const_iterator find(const key_type& __k) const {return __tree_.find(__k);}
Marshall Clowebb57322013-08-13 22:18:47 +00002064#if _LIBCPP_STD_VER > 11
2065 template <typename _K2>
2066 _LIBCPP_INLINE_VISIBILITY
2067 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
2068 find(const _K2& __k) {return __tree_.find(__k);}
2069 template <typename _K2>
2070 _LIBCPP_INLINE_VISIBILITY
2071 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
2072 find(const _K2& __k) const {return __tree_.find(__k);}
2073#endif
2074
Howard Hinnant756c69b2010-09-22 16:48:34 +00002075 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00002076 size_type count(const key_type& __k) const
2077 {return __tree_.__count_multi(__k);}
Marshall Clowe6a5f522014-08-24 23:54:16 +00002078#if _LIBCPP_STD_VER > 11
2079 template <typename _K2>
2080 _LIBCPP_INLINE_VISIBILITY
2081 typename enable_if<__is_transparent<_Compare, _K2>::value,size_type>::type
Marshall Clow141e47b2015-06-30 18:15:41 +00002082 count(const _K2& __k) const {return __tree_.__count_multi(__k);}
Marshall Clowe6a5f522014-08-24 23:54:16 +00002083#endif
Zoe Carver3ffbab12019-07-16 03:21:01 +00002084
2085#if _LIBCPP_STD_VER > 17
2086 _LIBCPP_INLINE_VISIBILITY
2087 bool contains(const key_type& __k) const {return find(__k) != end();}
Marek Kurdejd7e019e2021-04-13 17:10:55 +02002088 template <typename _K2>
2089 _LIBCPP_INLINE_VISIBILITY
2090 typename enable_if<__is_transparent<_Compare, _K2>::value, bool>::type
2091 contains(const _K2& __k) const { return find(__k) != end(); }
Zoe Carver3ffbab12019-07-16 03:21:01 +00002092#endif // _LIBCPP_STD_VER > 17
2093
Howard Hinnant756c69b2010-09-22 16:48:34 +00002094 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00002095 iterator lower_bound(const key_type& __k)
2096 {return __tree_.lower_bound(__k);}
Howard Hinnant756c69b2010-09-22 16:48:34 +00002097 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00002098 const_iterator lower_bound(const key_type& __k) const
2099 {return __tree_.lower_bound(__k);}
Marshall Clowebb57322013-08-13 22:18:47 +00002100#if _LIBCPP_STD_VER > 11
2101 template <typename _K2>
2102 _LIBCPP_INLINE_VISIBILITY
2103 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
2104 lower_bound(const _K2& __k) {return __tree_.lower_bound(__k);}
2105
2106 template <typename _K2>
2107 _LIBCPP_INLINE_VISIBILITY
2108 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
2109 lower_bound(const _K2& __k) const {return __tree_.lower_bound(__k);}
2110#endif
2111
Howard Hinnant756c69b2010-09-22 16:48:34 +00002112 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00002113 iterator upper_bound(const key_type& __k)
2114 {return __tree_.upper_bound(__k);}
Howard Hinnant756c69b2010-09-22 16:48:34 +00002115 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00002116 const_iterator upper_bound(const key_type& __k) const
2117 {return __tree_.upper_bound(__k);}
Marshall Clowebb57322013-08-13 22:18:47 +00002118#if _LIBCPP_STD_VER > 11
2119 template <typename _K2>
2120 _LIBCPP_INLINE_VISIBILITY
2121 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
2122 upper_bound(const _K2& __k) {return __tree_.upper_bound(__k);}
2123 template <typename _K2>
2124 _LIBCPP_INLINE_VISIBILITY
2125 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
2126 upper_bound(const _K2& __k) const {return __tree_.upper_bound(__k);}
2127#endif
2128
Howard Hinnant756c69b2010-09-22 16:48:34 +00002129 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00002130 pair<iterator,iterator> equal_range(const key_type& __k)
2131 {return __tree_.__equal_range_multi(__k);}
Howard Hinnant756c69b2010-09-22 16:48:34 +00002132 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00002133 pair<const_iterator,const_iterator> equal_range(const key_type& __k) const
2134 {return __tree_.__equal_range_multi(__k);}
Marshall Clowebb57322013-08-13 22:18:47 +00002135#if _LIBCPP_STD_VER > 11
2136 template <typename _K2>
2137 _LIBCPP_INLINE_VISIBILITY
2138 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<iterator,iterator>>::type
2139 equal_range(const _K2& __k) {return __tree_.__equal_range_multi(__k);}
2140 template <typename _K2>
2141 _LIBCPP_INLINE_VISIBILITY
2142 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<const_iterator,const_iterator>>::type
2143 equal_range(const _K2& __k) const {return __tree_.__equal_range_multi(__k);}
2144#endif
Howard Hinnantc51e1022010-05-11 19:42:16 +00002145
2146private:
2147 typedef typename __base::__node __node;
2148 typedef typename __base::__node_allocator __node_allocator;
2149 typedef typename __base::__node_pointer __node_pointer;
Eric Fiseliera92b0732016-02-20 07:12:17 +00002150
Howard Hinnantc834c512011-11-29 18:15:50 +00002151 typedef __map_node_destructor<__node_allocator> _Dp;
2152 typedef unique_ptr<__node, _Dp> __node_holder;
Howard Hinnantc51e1022010-05-11 19:42:16 +00002153};
2154
Louis Dionned23a5f22019-06-20 19:32:00 +00002155#ifndef _LIBCPP_HAS_NO_DEDUCTION_GUIDES
2156template<class _InputIterator, class _Compare = less<__iter_key_type<_InputIterator>>,
2157 class _Allocator = allocator<__iter_to_alloc_type<_InputIterator>>,
Louis Dionne6c7da9a2019-07-19 17:13:39 +00002158 class = _EnableIf<!__is_allocator<_Compare>::value, void>,
2159 class = _EnableIf<__is_allocator<_Allocator>::value, void>>
Louis Dionned23a5f22019-06-20 19:32:00 +00002160multimap(_InputIterator, _InputIterator, _Compare = _Compare(), _Allocator = _Allocator())
2161 -> multimap<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>, _Compare, _Allocator>;
2162
2163template<class _Key, class _Tp, class _Compare = less<remove_const_t<_Key>>,
2164 class _Allocator = allocator<pair<const _Key, _Tp>>,
Louis Dionne6c7da9a2019-07-19 17:13:39 +00002165 class = _EnableIf<!__is_allocator<_Compare>::value, void>,
2166 class = _EnableIf<__is_allocator<_Allocator>::value, void>>
Louis Dionned23a5f22019-06-20 19:32:00 +00002167multimap(initializer_list<pair<_Key, _Tp>>, _Compare = _Compare(), _Allocator = _Allocator())
2168 -> multimap<remove_const_t<_Key>, _Tp, _Compare, _Allocator>;
2169
2170template<class _InputIterator, class _Allocator,
Louis Dionne6c7da9a2019-07-19 17:13:39 +00002171 class = _EnableIf<__is_allocator<_Allocator>::value, void>>
Louis Dionned23a5f22019-06-20 19:32:00 +00002172multimap(_InputIterator, _InputIterator, _Allocator)
2173 -> multimap<__iter_key_type<_InputIterator>, __iter_mapped_type<_InputIterator>,
2174 less<__iter_key_type<_InputIterator>>, _Allocator>;
2175
2176template<class _Key, class _Tp, class _Allocator,
Louis Dionne6c7da9a2019-07-19 17:13:39 +00002177 class = _EnableIf<__is_allocator<_Allocator>::value, void>>
Louis Dionned23a5f22019-06-20 19:32:00 +00002178multimap(initializer_list<pair<_Key, _Tp>>, _Allocator)
2179 -> multimap<remove_const_t<_Key>, _Tp, less<remove_const_t<_Key>>, _Allocator>;
2180#endif
2181
Eric Fiselierd06276b2016-03-31 02:15:15 +00002182#ifndef _LIBCPP_CXX03_LANG
Howard Hinnantc51e1022010-05-11 19:42:16 +00002183template <class _Key, class _Tp, class _Compare, class _Allocator>
2184multimap<_Key, _Tp, _Compare, _Allocator>::multimap(multimap&& __m, const allocator_type& __a)
Marshall Clow657cbc42016-08-17 05:58:40 +00002185 : __tree_(_VSTD::move(__m.__tree_), typename __base::allocator_type(__a))
Howard Hinnantc51e1022010-05-11 19:42:16 +00002186{
2187 if (__a != __m.get_allocator())
2188 {
2189 const_iterator __e = cend();
2190 while (!__m.empty())
2191 __tree_.__insert_multi(__e.__i_,
Erik Pilkingtond3fe2992018-06-04 20:38:23 +00002192 _VSTD::move(__m.__tree_.remove(__m.begin().__i_)->__value_.__move()));
Howard Hinnantc51e1022010-05-11 19:42:16 +00002193 }
2194}
Eric Fiselierd06276b2016-03-31 02:15:15 +00002195#endif
Howard Hinnantc51e1022010-05-11 19:42:16 +00002196
2197template <class _Key, class _Tp, class _Compare, class _Allocator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00002198inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00002199bool
2200operator==(const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
2201 const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
2202{
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00002203 return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin());
Howard Hinnantc51e1022010-05-11 19:42:16 +00002204}
2205
2206template <class _Key, class _Tp, class _Compare, class _Allocator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00002207inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00002208bool
2209operator< (const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
2210 const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
2211{
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00002212 return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
Howard Hinnantc51e1022010-05-11 19:42:16 +00002213}
2214
2215template <class _Key, class _Tp, class _Compare, class _Allocator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00002216inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00002217bool
2218operator!=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
2219 const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
2220{
2221 return !(__x == __y);
2222}
2223
2224template <class _Key, class _Tp, class _Compare, class _Allocator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00002225inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00002226bool
2227operator> (const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
2228 const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
2229{
2230 return __y < __x;
2231}
2232
2233template <class _Key, class _Tp, class _Compare, class _Allocator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00002234inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00002235bool
2236operator>=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
2237 const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
2238{
2239 return !(__x < __y);
2240}
2241
2242template <class _Key, class _Tp, class _Compare, class _Allocator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00002243inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00002244bool
2245operator<=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
2246 const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
2247{
2248 return !(__y < __x);
2249}
2250
2251template <class _Key, class _Tp, class _Compare, class _Allocator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00002252inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00002253void
2254swap(multimap<_Key, _Tp, _Compare, _Allocator>& __x,
2255 multimap<_Key, _Tp, _Compare, _Allocator>& __y)
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00002256 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
Howard Hinnantc51e1022010-05-11 19:42:16 +00002257{
2258 __x.swap(__y);
2259}
2260
Marshall Clow29b53f22018-12-14 18:49:35 +00002261#if _LIBCPP_STD_VER > 17
Marek Kurdeja98b1412020-05-02 13:58:03 +02002262template <class _Key, class _Tp, class _Compare, class _Allocator,
2263 class _Predicate>
Marshall Clow29b53f22018-12-14 18:49:35 +00002264inline _LIBCPP_INLINE_VISIBILITY
Marek Kurdeja98b1412020-05-02 13:58:03 +02002265 typename multimap<_Key, _Tp, _Compare, _Allocator>::size_type
2266 erase_if(multimap<_Key, _Tp, _Compare, _Allocator>& __c,
2267 _Predicate __pred) {
Arthur O'Dwyerb6738bd2021-03-21 16:53:09 -04002268 return _VSTD::__libcpp_erase_if_container(__c, __pred);
Marek Kurdeja98b1412020-05-02 13:58:03 +02002269}
Marshall Clow29b53f22018-12-14 18:49:35 +00002270#endif
2271
Howard Hinnantc51e1022010-05-11 19:42:16 +00002272_LIBCPP_END_NAMESPACE_STD
2273
Louis Dionne2b1ceaa2021-04-20 12:03:32 -04002274#endif // _LIBCPP_MAP