blob: 11991affb66e020360c6586c83e7fe04672a0441 [file] [log] [blame]
Howard Hinnantc51e1022010-05-11 19:42:16 +00001// -*- C++ -*-
2//===---------------------------- set -------------------------------------===//
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_SET
11#define _LIBCPP_SET
12
13/*
14
15 set synopsis
16
17namespace std
18{
19
20template <class Key, class Compare = less<Key>,
21 class Allocator = allocator<Key>>
22class set
23{
24public:
25 // types:
26 typedef Key key_type;
27 typedef key_type value_type;
28 typedef Compare key_compare;
29 typedef key_compare value_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::size_type size_type;
34 typedef typename allocator_type::difference_type difference_type;
35 typedef typename allocator_type::pointer pointer;
36 typedef typename allocator_type::const_pointer const_pointer;
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 // construct/copy/destroy:
Howard Hinnantf95f4f52011-06-04 15:22:34 +000046 set()
47 noexcept(
48 is_nothrow_default_constructible<allocator_type>::value &&
49 is_nothrow_default_constructible<key_compare>::value &&
50 is_nothrow_copy_constructible<key_compare>::value);
51 explicit set(const value_compare& comp);
Howard Hinnantc51e1022010-05-11 19:42:16 +000052 set(const value_compare& comp, const allocator_type& a);
53 template <class InputIterator>
54 set(InputIterator first, InputIterator last,
55 const value_compare& comp = value_compare());
56 template <class InputIterator>
57 set(InputIterator first, InputIterator last, const value_compare& comp,
58 const allocator_type& a);
59 set(const set& s);
Howard Hinnantf95f4f52011-06-04 15:22:34 +000060 set(set&& s)
61 noexcept(
62 is_nothrow_move_constructible<allocator_type>::value &&
63 is_nothrow_move_constructible<key_compare>::value);
Howard Hinnantc51e1022010-05-11 19:42:16 +000064 explicit set(const allocator_type& a);
65 set(const set& s, const allocator_type& a);
66 set(set&& s, const allocator_type& a);
67 set(initializer_list<value_type> il, const value_compare& comp = value_compare());
68 set(initializer_list<value_type> il, const value_compare& comp,
69 const allocator_type& a);
Marshall Clow631788a2013-09-11 00:06:45 +000070 template <class InputIterator>
71 set(InputIterator first, InputIterator last, const allocator_type& a)
72 : set(first, last, Compare(), a) {} // C++14
73 set(initializer_list<value_type> il, const allocator_type& a)
74 : set(il, Compare(), a) {} // C++14
Howard Hinnantc51e1022010-05-11 19:42:16 +000075 ~set();
76
77 set& operator=(const set& s);
Howard Hinnantf95f4f52011-06-04 15:22:34 +000078 set& operator=(set&& s)
79 noexcept(
80 allocator_type::propagate_on_container_move_assignment::value &&
81 is_nothrow_move_assignable<allocator_type>::value &&
82 is_nothrow_move_assignable<key_compare>::value);
Howard Hinnantc51e1022010-05-11 19:42:16 +000083 set& operator=(initializer_list<value_type> il);
84
85 // iterators:
Howard Hinnantf95f4f52011-06-04 15:22:34 +000086 iterator begin() noexcept;
87 const_iterator begin() const noexcept;
88 iterator end() noexcept;
89 const_iterator end() const noexcept;
Howard Hinnantc51e1022010-05-11 19:42:16 +000090
Howard Hinnantf95f4f52011-06-04 15:22:34 +000091 reverse_iterator rbegin() noexcept;
92 const_reverse_iterator rbegin() const noexcept;
93 reverse_iterator rend() noexcept;
94 const_reverse_iterator rend() const noexcept;
Howard Hinnantc51e1022010-05-11 19:42:16 +000095
Howard Hinnantf95f4f52011-06-04 15:22:34 +000096 const_iterator cbegin() const noexcept;
97 const_iterator cend() const noexcept;
98 const_reverse_iterator crbegin() const noexcept;
99 const_reverse_iterator crend() const noexcept;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000100
101 // capacity:
Howard Hinnantf95f4f52011-06-04 15:22:34 +0000102 bool empty() const noexcept;
103 size_type size() const noexcept;
104 size_type max_size() const noexcept;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000105
106 // modifiers:
107 template <class... Args>
108 pair<iterator, bool> emplace(Args&&... args);
109 template <class... Args>
110 iterator emplace_hint(const_iterator position, Args&&... args);
111 pair<iterator,bool> insert(const value_type& v);
112 pair<iterator,bool> insert(value_type&& v);
113 iterator insert(const_iterator position, const value_type& v);
114 iterator insert(const_iterator position, value_type&& v);
115 template <class InputIterator>
116 void insert(InputIterator first, InputIterator last);
117 void insert(initializer_list<value_type> il);
118
Erik Pilkingtonc37a3d82018-08-01 01:33:38 +0000119 node_type extract(const_iterator position); // C++17
120 node_type extract(const key_type& x); // C++17
121 insert_return_type insert(node_type&& nh); // C++17
122 iterator insert(const_iterator hint, node_type&& nh); // C++17
123
Howard Hinnantc51e1022010-05-11 19:42:16 +0000124 iterator erase(const_iterator position);
Marshall Clow22ea5b82015-05-10 13:35:00 +0000125 iterator erase(iterator position); // C++14
Howard Hinnantc51e1022010-05-11 19:42:16 +0000126 size_type erase(const key_type& k);
127 iterator erase(const_iterator first, const_iterator last);
Howard Hinnantf95f4f52011-06-04 15:22:34 +0000128 void clear() noexcept;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000129
Erik Pilkington82a65ad2018-10-31 17:31:35 +0000130 template<class C2>
131 void merge(set<Key, C2, Allocator>& source); // C++17
132 template<class C2>
133 void merge(set<Key, C2, Allocator>&& source); // C++17
134 template<class C2>
135 void merge(multiset<Key, C2, Allocator>& source); // C++17
136 template<class C2>
137 void merge(multiset<Key, C2, Allocator>&& source); // C++17
138
Howard Hinnantf95f4f52011-06-04 15:22:34 +0000139 void swap(set& s)
140 noexcept(
141 __is_nothrow_swappable<key_compare>::value &&
142 (!allocator_type::propagate_on_container_swap::value ||
143 __is_nothrow_swappable<allocator_type>::value));
Howard Hinnantc51e1022010-05-11 19:42:16 +0000144
145 // observers:
Howard Hinnantf95f4f52011-06-04 15:22:34 +0000146 allocator_type get_allocator() const noexcept;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000147 key_compare key_comp() const;
148 value_compare value_comp() const;
149
150 // set operations:
151 iterator find(const key_type& k);
152 const_iterator find(const key_type& k) const;
Marshall Clowc0152142013-08-13 01:11:06 +0000153 template<typename K>
154 iterator find(const K& x);
155 template<typename K>
156 const_iterator find(const K& x) const; // C++14
157 template<typename K>
Zoe Carver3ffbab12019-07-16 03:21:01 +0000158 size_type count(const K& x) const; // C++14
Howard Hinnantc51e1022010-05-11 19:42:16 +0000159 size_type count(const key_type& k) const;
Zoe Carver3ffbab12019-07-16 03:21:01 +0000160 bool contains(const key_type& x) const; // C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000161 iterator lower_bound(const key_type& k);
162 const_iterator lower_bound(const key_type& k) const;
Marshall Clowc0152142013-08-13 01:11:06 +0000163 template<typename K>
164 iterator lower_bound(const K& x); // C++14
165 template<typename K>
166 const_iterator lower_bound(const K& x) const; // C++14
167
Howard Hinnantc51e1022010-05-11 19:42:16 +0000168 iterator upper_bound(const key_type& k);
169 const_iterator upper_bound(const key_type& k) const;
Marshall Clowc0152142013-08-13 01:11:06 +0000170 template<typename K>
171 iterator upper_bound(const K& x); // C++14
172 template<typename K>
173 const_iterator upper_bound(const K& x) const; // C++14
Howard Hinnantc51e1022010-05-11 19:42:16 +0000174 pair<iterator,iterator> equal_range(const key_type& k);
175 pair<const_iterator,const_iterator> equal_range(const key_type& k) const;
Marshall Clowc0152142013-08-13 01:11:06 +0000176 template<typename K>
177 pair<iterator,iterator> equal_range(const K& x); // C++14
178 template<typename K>
179 pair<const_iterator,const_iterator> equal_range(const K& x) const; // C++14
Howard Hinnantc51e1022010-05-11 19:42:16 +0000180};
181
182template <class Key, class Compare, class Allocator>
183bool
184operator==(const set<Key, Compare, Allocator>& x,
185 const set<Key, Compare, Allocator>& y);
186
187template <class Key, class Compare, class Allocator>
188bool
189operator< (const set<Key, Compare, Allocator>& x,
190 const set<Key, Compare, Allocator>& y);
191
192template <class Key, class Compare, class Allocator>
193bool
194operator!=(const set<Key, Compare, Allocator>& x,
195 const set<Key, Compare, Allocator>& y);
196
197template <class Key, class Compare, class Allocator>
198bool
199operator> (const set<Key, Compare, Allocator>& x,
200 const set<Key, Compare, Allocator>& y);
201
202template <class Key, class Compare, class Allocator>
203bool
204operator>=(const set<Key, Compare, Allocator>& x,
205 const set<Key, Compare, Allocator>& y);
206
207template <class Key, class Compare, class Allocator>
208bool
209operator<=(const set<Key, Compare, Allocator>& x,
210 const set<Key, Compare, Allocator>& y);
211
212// specialized algorithms:
213template <class Key, class Compare, class Allocator>
214void
Howard Hinnantf95f4f52011-06-04 15:22:34 +0000215swap(set<Key, Compare, Allocator>& x, set<Key, Compare, Allocator>& y)
216 noexcept(noexcept(x.swap(y)));
Howard Hinnantc51e1022010-05-11 19:42:16 +0000217
Marshall Clow29b53f22018-12-14 18:49:35 +0000218template <class Key, class Compare, class Allocator, class Predicate>
Marek Kurdeja98b1412020-05-02 13:58:03 +0200219typename set<Key, Compare, Allocator>::size_type
220erase_if(set<Key, Compare, Allocator>& c, Predicate pred); // C++20
Marshall Clow29b53f22018-12-14 18:49:35 +0000221
Howard Hinnantc51e1022010-05-11 19:42:16 +0000222template <class Key, class Compare = less<Key>,
223 class Allocator = allocator<Key>>
224class multiset
225{
226public:
227 // types:
228 typedef Key key_type;
229 typedef key_type value_type;
230 typedef Compare key_compare;
231 typedef key_compare value_compare;
232 typedef Allocator allocator_type;
233 typedef typename allocator_type::reference reference;
234 typedef typename allocator_type::const_reference const_reference;
235 typedef typename allocator_type::size_type size_type;
236 typedef typename allocator_type::difference_type difference_type;
237 typedef typename allocator_type::pointer pointer;
238 typedef typename allocator_type::const_pointer const_pointer;
239
240 typedef implementation-defined iterator;
241 typedef implementation-defined const_iterator;
242 typedef std::reverse_iterator<iterator> reverse_iterator;
243 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
Erik Pilkingtonc37a3d82018-08-01 01:33:38 +0000244 typedef unspecified node_type; // C++17
Howard Hinnantc51e1022010-05-11 19:42:16 +0000245
246 // construct/copy/destroy:
Howard Hinnantf95f4f52011-06-04 15:22:34 +0000247 multiset()
248 noexcept(
249 is_nothrow_default_constructible<allocator_type>::value &&
250 is_nothrow_default_constructible<key_compare>::value &&
251 is_nothrow_copy_constructible<key_compare>::value);
252 explicit multiset(const value_compare& comp);
Howard Hinnantc51e1022010-05-11 19:42:16 +0000253 multiset(const value_compare& comp, const allocator_type& a);
254 template <class InputIterator>
255 multiset(InputIterator first, InputIterator last,
256 const value_compare& comp = value_compare());
257 template <class InputIterator>
258 multiset(InputIterator first, InputIterator last,
259 const value_compare& comp, const allocator_type& a);
260 multiset(const multiset& s);
Howard Hinnantf95f4f52011-06-04 15:22:34 +0000261 multiset(multiset&& s)
262 noexcept(
263 is_nothrow_move_constructible<allocator_type>::value &&
264 is_nothrow_move_constructible<key_compare>::value);
Howard Hinnantc51e1022010-05-11 19:42:16 +0000265 explicit multiset(const allocator_type& a);
266 multiset(const multiset& s, const allocator_type& a);
267 multiset(multiset&& s, const allocator_type& a);
268 multiset(initializer_list<value_type> il, const value_compare& comp = value_compare());
269 multiset(initializer_list<value_type> il, const value_compare& comp,
270 const allocator_type& a);
Marshall Clow631788a2013-09-11 00:06:45 +0000271 template <class InputIterator>
272 multiset(InputIterator first, InputIterator last, const allocator_type& a)
273 : set(first, last, Compare(), a) {} // C++14
274 multiset(initializer_list<value_type> il, const allocator_type& a)
275 : set(il, Compare(), a) {} // C++14
Howard Hinnantc51e1022010-05-11 19:42:16 +0000276 ~multiset();
277
278 multiset& operator=(const multiset& s);
Howard Hinnantf95f4f52011-06-04 15:22:34 +0000279 multiset& operator=(multiset&& s)
280 noexcept(
281 allocator_type::propagate_on_container_move_assignment::value &&
282 is_nothrow_move_assignable<allocator_type>::value &&
283 is_nothrow_move_assignable<key_compare>::value);
Howard Hinnantc51e1022010-05-11 19:42:16 +0000284 multiset& operator=(initializer_list<value_type> il);
285
286 // iterators:
Howard Hinnantf95f4f52011-06-04 15:22:34 +0000287 iterator begin() noexcept;
288 const_iterator begin() const noexcept;
289 iterator end() noexcept;
290 const_iterator end() const noexcept;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000291
Howard Hinnantf95f4f52011-06-04 15:22:34 +0000292 reverse_iterator rbegin() noexcept;
293 const_reverse_iterator rbegin() const noexcept;
294 reverse_iterator rend() noexcept;
295 const_reverse_iterator rend() const noexcept;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000296
Howard Hinnantf95f4f52011-06-04 15:22:34 +0000297 const_iterator cbegin() const noexcept;
298 const_iterator cend() const noexcept;
299 const_reverse_iterator crbegin() const noexcept;
300 const_reverse_iterator crend() const noexcept;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000301
302 // capacity:
Howard Hinnantf95f4f52011-06-04 15:22:34 +0000303 bool empty() const noexcept;
304 size_type size() const noexcept;
305 size_type max_size() const noexcept;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000306
307 // modifiers:
308 template <class... Args>
309 iterator emplace(Args&&... args);
310 template <class... Args>
311 iterator emplace_hint(const_iterator position, Args&&... args);
312 iterator insert(const value_type& v);
313 iterator insert(value_type&& v);
314 iterator insert(const_iterator position, const value_type& v);
315 iterator insert(const_iterator position, value_type&& v);
316 template <class InputIterator>
317 void insert(InputIterator first, InputIterator last);
318 void insert(initializer_list<value_type> il);
319
Erik Pilkingtonc37a3d82018-08-01 01:33:38 +0000320 node_type extract(const_iterator position); // C++17
321 node_type extract(const key_type& x); // C++17
322 iterator insert(node_type&& nh); // C++17
323 iterator insert(const_iterator hint, node_type&& nh); // C++17
324
Howard Hinnantc51e1022010-05-11 19:42:16 +0000325 iterator erase(const_iterator position);
Marshall Clow22ea5b82015-05-10 13:35:00 +0000326 iterator erase(iterator position); // C++14
Howard Hinnantc51e1022010-05-11 19:42:16 +0000327 size_type erase(const key_type& k);
328 iterator erase(const_iterator first, const_iterator last);
Howard Hinnantf95f4f52011-06-04 15:22:34 +0000329 void clear() noexcept;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000330
Erik Pilkington82a65ad2018-10-31 17:31:35 +0000331 template<class C2>
332 void merge(multiset<Key, C2, Allocator>& source); // C++17
333 template<class C2>
334 void merge(multiset<Key, C2, Allocator>&& source); // C++17
335 template<class C2>
336 void merge(set<Key, C2, Allocator>& source); // C++17
337 template<class C2>
338 void merge(set<Key, C2, Allocator>&& source); // C++17
339
Howard Hinnantf95f4f52011-06-04 15:22:34 +0000340 void swap(multiset& s)
341 noexcept(
342 __is_nothrow_swappable<key_compare>::value &&
343 (!allocator_type::propagate_on_container_swap::value ||
344 __is_nothrow_swappable<allocator_type>::value));
Howard Hinnantc51e1022010-05-11 19:42:16 +0000345
346 // observers:
Howard Hinnantf95f4f52011-06-04 15:22:34 +0000347 allocator_type get_allocator() const noexcept;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000348 key_compare key_comp() const;
349 value_compare value_comp() const;
350
351 // set operations:
352 iterator find(const key_type& k);
353 const_iterator find(const key_type& k) const;
Marshall Clowc0152142013-08-13 01:11:06 +0000354 template<typename K>
355 iterator find(const K& x);
356 template<typename K>
357 const_iterator find(const K& x) const; // C++14
Zoe Carver3ffbab12019-07-16 03:21:01 +0000358 template<typename K>
359 size_type count(const K& x) const; // C++14
Howard Hinnantc51e1022010-05-11 19:42:16 +0000360 size_type count(const key_type& k) const;
Zoe Carver3ffbab12019-07-16 03:21:01 +0000361 bool contains(const key_type& x) const; // C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000362 iterator lower_bound(const key_type& k);
363 const_iterator lower_bound(const key_type& k) const;
Marshall Clowc0152142013-08-13 01:11:06 +0000364 template<typename K>
365 iterator lower_bound(const K& x); // C++14
366 template<typename K>
367 const_iterator lower_bound(const K& x) const; // C++14
368
Howard Hinnantc51e1022010-05-11 19:42:16 +0000369 iterator upper_bound(const key_type& k);
370 const_iterator upper_bound(const key_type& k) const;
Marshall Clowc0152142013-08-13 01:11:06 +0000371 template<typename K>
372 iterator upper_bound(const K& x); // C++14
373 template<typename K>
374 const_iterator upper_bound(const K& x) const; // C++14
375
Howard Hinnantc51e1022010-05-11 19:42:16 +0000376 pair<iterator,iterator> equal_range(const key_type& k);
377 pair<const_iterator,const_iterator> equal_range(const key_type& k) const;
Marshall Clowc0152142013-08-13 01:11:06 +0000378 template<typename K>
379 pair<iterator,iterator> equal_range(const K& x); // C++14
380 template<typename K>
381 pair<const_iterator,const_iterator> equal_range(const K& x) const; // C++14
Howard Hinnantc51e1022010-05-11 19:42:16 +0000382};
383
384template <class Key, class Compare, class Allocator>
385bool
386operator==(const multiset<Key, Compare, Allocator>& x,
387 const multiset<Key, Compare, Allocator>& y);
388
389template <class Key, class Compare, class Allocator>
390bool
391operator< (const multiset<Key, Compare, Allocator>& x,
392 const multiset<Key, Compare, Allocator>& y);
393
394template <class Key, class Compare, class Allocator>
395bool
396operator!=(const multiset<Key, Compare, Allocator>& x,
397 const multiset<Key, Compare, Allocator>& y);
398
399template <class Key, class Compare, class Allocator>
400bool
401operator> (const multiset<Key, Compare, Allocator>& x,
402 const multiset<Key, Compare, Allocator>& y);
403
404template <class Key, class Compare, class Allocator>
405bool
406operator>=(const multiset<Key, Compare, Allocator>& x,
407 const multiset<Key, Compare, Allocator>& y);
408
409template <class Key, class Compare, class Allocator>
410bool
411operator<=(const multiset<Key, Compare, Allocator>& x,
412 const multiset<Key, Compare, Allocator>& y);
413
414// specialized algorithms:
415template <class Key, class Compare, class Allocator>
416void
Howard Hinnantf95f4f52011-06-04 15:22:34 +0000417swap(multiset<Key, Compare, Allocator>& x, multiset<Key, Compare, Allocator>& y)
418 noexcept(noexcept(x.swap(y)));
Howard Hinnantc51e1022010-05-11 19:42:16 +0000419
Marshall Clow29b53f22018-12-14 18:49:35 +0000420template <class Key, class Compare, class Allocator, class Predicate>
Marek Kurdeja98b1412020-05-02 13:58:03 +0200421typename multiset<Key, Compare, Allocator>::size_type
422erase_if(multiset<Key, Compare, Allocator>& c, Predicate pred); // C++20
Marshall Clow29b53f22018-12-14 18:49:35 +0000423
Howard Hinnantc51e1022010-05-11 19:42:16 +0000424} // std
425
426*/
427
428#include <__config>
429#include <__tree>
Erik Pilkingtonc37a3d82018-08-01 01:33:38 +0000430#include <__node_handle>
Arthur O'Dwyer7deec122021-03-24 18:19:12 -0400431#include <compare>
Howard Hinnantc51e1022010-05-11 19:42:16 +0000432#include <functional>
Arthur O'Dwyer7deec122021-03-24 18:19:12 -0400433#include <initializer_list>
Arthur O'Dwyerb6738bd2021-03-21 16:53:09 -0400434#include <iterator> // __libcpp_erase_if_container
Marshall Clow0a1e7502018-09-12 19:41:40 +0000435#include <version>
Howard Hinnantc51e1022010-05-11 19:42:16 +0000436
Howard Hinnantaaaa52b2011-10-17 20:05:10 +0000437#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
Howard Hinnantc51e1022010-05-11 19:42:16 +0000438#pragma GCC system_header
Howard Hinnantaaaa52b2011-10-17 20:05:10 +0000439#endif
Howard Hinnantc51e1022010-05-11 19:42:16 +0000440
441_LIBCPP_BEGIN_NAMESPACE_STD
442
Erik Pilkington82a65ad2018-10-31 17:31:35 +0000443template <class _Key, class _Compare, class _Allocator>
444class multiset;
445
Howard Hinnantc51e1022010-05-11 19:42:16 +0000446template <class _Key, class _Compare = less<_Key>,
447 class _Allocator = allocator<_Key> >
Eric Fiselierb5eb1bf2017-01-04 23:56:00 +0000448class _LIBCPP_TEMPLATE_VIS set
Howard Hinnantc51e1022010-05-11 19:42:16 +0000449{
450public:
451 // types:
452 typedef _Key key_type;
453 typedef key_type value_type;
454 typedef _Compare key_compare;
455 typedef key_compare value_compare;
Arthur O'Dwyer6a752e12021-03-03 11:10:49 -0500456 typedef __identity_t<_Allocator> allocator_type;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000457 typedef value_type& reference;
458 typedef const value_type& const_reference;
459
Marshall Clow5128cf32015-11-26 01:24:04 +0000460 static_assert((is_same<typename allocator_type::value_type, value_type>::value),
461 "Allocator::value_type must be same type as value_type");
462
Howard Hinnantc51e1022010-05-11 19:42:16 +0000463private:
464 typedef __tree<value_type, value_compare, allocator_type> __base;
465 typedef allocator_traits<allocator_type> __alloc_traits;
466 typedef typename __base::__node_holder __node_holder;
467
468 __base __tree_;
469
470public:
471 typedef typename __base::pointer pointer;
472 typedef typename __base::const_pointer const_pointer;
473 typedef typename __base::size_type size_type;
474 typedef typename __base::difference_type difference_type;
475 typedef typename __base::const_iterator iterator;
476 typedef typename __base::const_iterator const_iterator;
Howard Hinnantb1ad5a82011-06-30 21:18:19 +0000477 typedef _VSTD::reverse_iterator<iterator> reverse_iterator;
478 typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000479
Erik Pilkingtonc37a3d82018-08-01 01:33:38 +0000480#if _LIBCPP_STD_VER > 14
481 typedef __set_node_handle<typename __base::__node, allocator_type> node_type;
482 typedef __insert_return_type<iterator, node_type> insert_return_type;
483#endif
484
Erik Pilkington82a65ad2018-10-31 17:31:35 +0000485 template <class _Key2, class _Compare2, class _Alloc2>
486 friend class _LIBCPP_TEMPLATE_VIS set;
487 template <class _Key2, class _Compare2, class _Alloc2>
488 friend class _LIBCPP_TEMPLATE_VIS multiset;
489
Howard Hinnant192cf032010-09-23 16:27:36 +0000490 _LIBCPP_INLINE_VISIBILITY
Marshall Clow7086a5a2014-03-10 04:50:10 +0000491 set()
492 _NOEXCEPT_(
493 is_nothrow_default_constructible<allocator_type>::value &&
494 is_nothrow_default_constructible<key_compare>::value &&
495 is_nothrow_copy_constructible<key_compare>::value)
496 : __tree_(value_compare()) {}
497
498 _LIBCPP_INLINE_VISIBILITY
499 explicit set(const value_compare& __comp)
Howard Hinnantf95f4f52011-06-04 15:22:34 +0000500 _NOEXCEPT_(
501 is_nothrow_default_constructible<allocator_type>::value &&
Howard Hinnantf95f4f52011-06-04 15:22:34 +0000502 is_nothrow_copy_constructible<key_compare>::value)
Howard Hinnantc51e1022010-05-11 19:42:16 +0000503 : __tree_(__comp) {}
Marshall Clow7086a5a2014-03-10 04:50:10 +0000504
Howard Hinnant192cf032010-09-23 16:27:36 +0000505 _LIBCPP_INLINE_VISIBILITY
Marshall Clow7ed23a72014-03-05 19:06:20 +0000506 explicit set(const value_compare& __comp, const allocator_type& __a)
Howard Hinnantc51e1022010-05-11 19:42:16 +0000507 : __tree_(__comp, __a) {}
508 template <class _InputIterator>
Howard Hinnant192cf032010-09-23 16:27:36 +0000509 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000510 set(_InputIterator __f, _InputIterator __l,
511 const value_compare& __comp = value_compare())
512 : __tree_(__comp)
513 {
514 insert(__f, __l);
515 }
516
517 template <class _InputIterator>
Howard Hinnant192cf032010-09-23 16:27:36 +0000518 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000519 set(_InputIterator __f, _InputIterator __l, const value_compare& __comp,
520 const allocator_type& __a)
521 : __tree_(__comp, __a)
522 {
523 insert(__f, __l);
524 }
525
Marshall Clow631788a2013-09-11 00:06:45 +0000526#if _LIBCPP_STD_VER > 11
527 template <class _InputIterator>
Louis Dionned2322c82018-11-01 14:41:37 +0000528 _LIBCPP_INLINE_VISIBILITY
Marshall Clow631788a2013-09-11 00:06:45 +0000529 set(_InputIterator __f, _InputIterator __l, const allocator_type& __a)
530 : set(__f, __l, key_compare(), __a) {}
531#endif
532
Howard Hinnant192cf032010-09-23 16:27:36 +0000533 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000534 set(const set& __s)
535 : __tree_(__s.__tree_)
536 {
537 insert(__s.begin(), __s.end());
538 }
539
Howard Hinnantd3a657f2011-07-01 19:24:36 +0000540 _LIBCPP_INLINE_VISIBILITY
541 set& operator=(const set& __s)
542 {
543 __tree_ = __s.__tree_;
544 return *this;
545 }
546
Eric Fiselier615961b2017-04-18 20:58:03 +0000547#ifndef _LIBCPP_CXX03_LANG
Howard Hinnant192cf032010-09-23 16:27:36 +0000548 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000549 set(set&& __s)
Howard Hinnantf95f4f52011-06-04 15:22:34 +0000550 _NOEXCEPT_(is_nothrow_move_constructible<__base>::value)
Howard Hinnantb1ad5a82011-06-30 21:18:19 +0000551 : __tree_(_VSTD::move(__s.__tree_)) {}
Eric Fiselier615961b2017-04-18 20:58:03 +0000552#endif // _LIBCPP_CXX03_LANG
Howard Hinnantc51e1022010-05-11 19:42:16 +0000553
Howard Hinnant192cf032010-09-23 16:27:36 +0000554 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000555 explicit set(const allocator_type& __a)
556 : __tree_(__a) {}
557
Howard Hinnant192cf032010-09-23 16:27:36 +0000558 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000559 set(const set& __s, const allocator_type& __a)
560 : __tree_(__s.__tree_.value_comp(), __a)
561 {
562 insert(__s.begin(), __s.end());
563 }
564
Eric Fiselier615961b2017-04-18 20:58:03 +0000565#ifndef _LIBCPP_CXX03_LANG
Howard Hinnantc51e1022010-05-11 19:42:16 +0000566 set(set&& __s, const allocator_type& __a);
Howard Hinnantc51e1022010-05-11 19:42:16 +0000567
Howard Hinnant192cf032010-09-23 16:27:36 +0000568 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000569 set(initializer_list<value_type> __il, const value_compare& __comp = value_compare())
570 : __tree_(__comp)
571 {
572 insert(__il.begin(), __il.end());
573 }
574
Howard Hinnant192cf032010-09-23 16:27:36 +0000575 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000576 set(initializer_list<value_type> __il, const value_compare& __comp,
577 const allocator_type& __a)
578 : __tree_(__comp, __a)
579 {
580 insert(__il.begin(), __il.end());
581 }
582
Marshall Clow631788a2013-09-11 00:06:45 +0000583#if _LIBCPP_STD_VER > 11
Louis Dionned2322c82018-11-01 14:41:37 +0000584 _LIBCPP_INLINE_VISIBILITY
Marshall Clow631788a2013-09-11 00:06:45 +0000585 set(initializer_list<value_type> __il, const allocator_type& __a)
586 : set(__il, key_compare(), __a) {}
587#endif
588
Howard Hinnant192cf032010-09-23 16:27:36 +0000589 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000590 set& operator=(initializer_list<value_type> __il)
591 {
592 __tree_.__assign_unique(__il.begin(), __il.end());
593 return *this;
594 }
595
Howard Hinnant192cf032010-09-23 16:27:36 +0000596 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000597 set& operator=(set&& __s)
Howard Hinnantf95f4f52011-06-04 15:22:34 +0000598 _NOEXCEPT_(is_nothrow_move_assignable<__base>::value)
Howard Hinnantc51e1022010-05-11 19:42:16 +0000599 {
Howard Hinnantb1ad5a82011-06-30 21:18:19 +0000600 __tree_ = _VSTD::move(__s.__tree_);
Howard Hinnantc51e1022010-05-11 19:42:16 +0000601 return *this;
602 }
Eric Fiselier615961b2017-04-18 20:58:03 +0000603#endif // _LIBCPP_CXX03_LANG
Howard Hinnantc51e1022010-05-11 19:42:16 +0000604
Howard Hinnant192cf032010-09-23 16:27:36 +0000605 _LIBCPP_INLINE_VISIBILITY
Louis Dionne69c42c02019-04-11 16:14:56 +0000606 ~set() {
607 static_assert(sizeof(__diagnose_non_const_comparator<_Key, _Compare>()), "");
608 }
609
610 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantf95f4f52011-06-04 15:22:34 +0000611 iterator begin() _NOEXCEPT {return __tree_.begin();}
Howard Hinnant192cf032010-09-23 16:27:36 +0000612 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantf95f4f52011-06-04 15:22:34 +0000613 const_iterator begin() const _NOEXCEPT {return __tree_.begin();}
Howard Hinnant192cf032010-09-23 16:27:36 +0000614 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantf95f4f52011-06-04 15:22:34 +0000615 iterator end() _NOEXCEPT {return __tree_.end();}
Howard Hinnant192cf032010-09-23 16:27:36 +0000616 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantf95f4f52011-06-04 15:22:34 +0000617 const_iterator end() const _NOEXCEPT {return __tree_.end();}
Howard Hinnantc51e1022010-05-11 19:42:16 +0000618
Howard Hinnant192cf032010-09-23 16:27:36 +0000619 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantf95f4f52011-06-04 15:22:34 +0000620 reverse_iterator rbegin() _NOEXCEPT
621 {return reverse_iterator(end());}
Howard Hinnant192cf032010-09-23 16:27:36 +0000622 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantf95f4f52011-06-04 15:22:34 +0000623 const_reverse_iterator rbegin() const _NOEXCEPT
624 {return const_reverse_iterator(end());}
Howard Hinnant192cf032010-09-23 16:27:36 +0000625 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantf95f4f52011-06-04 15:22:34 +0000626 reverse_iterator rend() _NOEXCEPT
627 {return reverse_iterator(begin());}
Howard Hinnant192cf032010-09-23 16:27:36 +0000628 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantf95f4f52011-06-04 15:22:34 +0000629 const_reverse_iterator rend() const _NOEXCEPT
630 {return const_reverse_iterator(begin());}
Howard Hinnantc51e1022010-05-11 19:42:16 +0000631
Howard Hinnant192cf032010-09-23 16:27:36 +0000632 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantf95f4f52011-06-04 15:22:34 +0000633 const_iterator cbegin() const _NOEXCEPT {return begin();}
Howard Hinnant192cf032010-09-23 16:27:36 +0000634 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantf95f4f52011-06-04 15:22:34 +0000635 const_iterator cend() const _NOEXCEPT {return end();}
Howard Hinnant192cf032010-09-23 16:27:36 +0000636 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantf95f4f52011-06-04 15:22:34 +0000637 const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();}
Howard Hinnant192cf032010-09-23 16:27:36 +0000638 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantf95f4f52011-06-04 15:22:34 +0000639 const_reverse_iterator crend() const _NOEXCEPT {return rend();}
Howard Hinnantc51e1022010-05-11 19:42:16 +0000640
Marshall Clow425f5752017-11-15 05:51:26 +0000641 _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantf95f4f52011-06-04 15:22:34 +0000642 bool empty() const _NOEXCEPT {return __tree_.size() == 0;}
Howard Hinnant192cf032010-09-23 16:27:36 +0000643 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantf95f4f52011-06-04 15:22:34 +0000644 size_type size() const _NOEXCEPT {return __tree_.size();}
Howard Hinnant192cf032010-09-23 16:27:36 +0000645 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantf95f4f52011-06-04 15:22:34 +0000646 size_type max_size() const _NOEXCEPT {return __tree_.max_size();}
Howard Hinnantc51e1022010-05-11 19:42:16 +0000647
648 // modifiers:
Eric Fiselier615961b2017-04-18 20:58:03 +0000649#ifndef _LIBCPP_CXX03_LANG
Howard Hinnantc51e1022010-05-11 19:42:16 +0000650 template <class... _Args>
Howard Hinnant192cf032010-09-23 16:27:36 +0000651 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000652 pair<iterator, bool> emplace(_Args&&... __args)
Howard Hinnantb1ad5a82011-06-30 21:18:19 +0000653 {return __tree_.__emplace_unique(_VSTD::forward<_Args>(__args)...);}
Howard Hinnantc51e1022010-05-11 19:42:16 +0000654 template <class... _Args>
Howard Hinnant192cf032010-09-23 16:27:36 +0000655 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000656 iterator emplace_hint(const_iterator __p, _Args&&... __args)
Howard Hinnantb1ad5a82011-06-30 21:18:19 +0000657 {return __tree_.__emplace_hint_unique(__p, _VSTD::forward<_Args>(__args)...);}
Eric Fiselier615961b2017-04-18 20:58:03 +0000658#endif // _LIBCPP_CXX03_LANG
659
Howard Hinnant192cf032010-09-23 16:27:36 +0000660 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000661 pair<iterator,bool> insert(const value_type& __v)
662 {return __tree_.__insert_unique(__v);}
Howard Hinnant192cf032010-09-23 16:27:36 +0000663 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000664 iterator insert(const_iterator __p, const value_type& __v)
665 {return __tree_.__insert_unique(__p, __v);}
Eric Fiselier615961b2017-04-18 20:58:03 +0000666
Howard Hinnantc51e1022010-05-11 19:42:16 +0000667 template <class _InputIterator>
Howard Hinnant192cf032010-09-23 16:27:36 +0000668 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000669 void insert(_InputIterator __f, _InputIterator __l)
670 {
671 for (const_iterator __e = cend(); __f != __l; ++__f)
672 __tree_.__insert_unique(__e, *__f);
673 }
674
Eric Fiselier615961b2017-04-18 20:58:03 +0000675#ifndef _LIBCPP_CXX03_LANG
676 _LIBCPP_INLINE_VISIBILITY
677 pair<iterator,bool> insert(value_type&& __v)
678 {return __tree_.__insert_unique(_VSTD::move(__v));}
679
680 _LIBCPP_INLINE_VISIBILITY
681 iterator insert(const_iterator __p, value_type&& __v)
682 {return __tree_.__insert_unique(__p, _VSTD::move(__v));}
683
Howard Hinnant192cf032010-09-23 16:27:36 +0000684 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000685 void insert(initializer_list<value_type> __il)
686 {insert(__il.begin(), __il.end());}
Eric Fiselier615961b2017-04-18 20:58:03 +0000687#endif // _LIBCPP_CXX03_LANG
Howard Hinnantc51e1022010-05-11 19:42:16 +0000688
Howard Hinnant192cf032010-09-23 16:27:36 +0000689 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000690 iterator erase(const_iterator __p) {return __tree_.erase(__p);}
Howard Hinnant192cf032010-09-23 16:27:36 +0000691 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000692 size_type erase(const key_type& __k)
693 {return __tree_.__erase_unique(__k);}
Howard Hinnant192cf032010-09-23 16:27:36 +0000694 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000695 iterator erase(const_iterator __f, const_iterator __l)
696 {return __tree_.erase(__f, __l);}
Howard Hinnant192cf032010-09-23 16:27:36 +0000697 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantf95f4f52011-06-04 15:22:34 +0000698 void clear() _NOEXCEPT {__tree_.clear();}
Howard Hinnantc51e1022010-05-11 19:42:16 +0000699
Erik Pilkingtonc37a3d82018-08-01 01:33:38 +0000700#if _LIBCPP_STD_VER > 14
701 _LIBCPP_INLINE_VISIBILITY
702 insert_return_type insert(node_type&& __nh)
703 {
704 _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(),
705 "node_type with incompatible allocator passed to set::insert()");
706 return __tree_.template __node_handle_insert_unique<
707 node_type, insert_return_type>(_VSTD::move(__nh));
708 }
709 _LIBCPP_INLINE_VISIBILITY
710 iterator insert(const_iterator __hint, node_type&& __nh)
711 {
712 _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(),
713 "node_type with incompatible allocator passed to set::insert()");
714 return __tree_.template __node_handle_insert_unique<node_type>(
715 __hint, _VSTD::move(__nh));
716 }
717 _LIBCPP_INLINE_VISIBILITY
718 node_type extract(key_type const& __key)
719 {
720 return __tree_.template __node_handle_extract<node_type>(__key);
721 }
722 _LIBCPP_INLINE_VISIBILITY
723 node_type extract(const_iterator __it)
724 {
725 return __tree_.template __node_handle_extract<node_type>(__it);
726 }
Louis Dionned2322c82018-11-01 14:41:37 +0000727 template <class _Compare2>
Erik Pilkington82a65ad2018-10-31 17:31:35 +0000728 _LIBCPP_INLINE_VISIBILITY
Louis Dionned2322c82018-11-01 14:41:37 +0000729 void merge(set<key_type, _Compare2, allocator_type>& __source)
Erik Pilkington82a65ad2018-10-31 17:31:35 +0000730 {
731 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
732 "merging container with incompatible allocator");
733 __tree_.__node_handle_merge_unique(__source.__tree_);
734 }
Louis Dionned2322c82018-11-01 14:41:37 +0000735 template <class _Compare2>
Erik Pilkington82a65ad2018-10-31 17:31:35 +0000736 _LIBCPP_INLINE_VISIBILITY
Louis Dionned2322c82018-11-01 14:41:37 +0000737 void merge(set<key_type, _Compare2, allocator_type>&& __source)
Erik Pilkington82a65ad2018-10-31 17:31:35 +0000738 {
739 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
740 "merging container with incompatible allocator");
741 __tree_.__node_handle_merge_unique(__source.__tree_);
742 }
Louis Dionned2322c82018-11-01 14:41:37 +0000743 template <class _Compare2>
Erik Pilkington82a65ad2018-10-31 17:31:35 +0000744 _LIBCPP_INLINE_VISIBILITY
Louis Dionned2322c82018-11-01 14:41:37 +0000745 void merge(multiset<key_type, _Compare2, allocator_type>& __source)
Erik Pilkington82a65ad2018-10-31 17:31:35 +0000746 {
747 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
748 "merging container with incompatible allocator");
749 __tree_.__node_handle_merge_unique(__source.__tree_);
750 }
Louis Dionned2322c82018-11-01 14:41:37 +0000751 template <class _Compare2>
Erik Pilkington82a65ad2018-10-31 17:31:35 +0000752 _LIBCPP_INLINE_VISIBILITY
Louis Dionned2322c82018-11-01 14:41:37 +0000753 void merge(multiset<key_type, _Compare2, allocator_type>&& __source)
Erik Pilkington82a65ad2018-10-31 17:31:35 +0000754 {
755 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
756 "merging container with incompatible allocator");
757 __tree_.__node_handle_merge_unique(__source.__tree_);
758 }
Erik Pilkingtonc37a3d82018-08-01 01:33:38 +0000759#endif
760
Howard Hinnant192cf032010-09-23 16:27:36 +0000761 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantf95f4f52011-06-04 15:22:34 +0000762 void swap(set& __s) _NOEXCEPT_(__is_nothrow_swappable<__base>::value)
763 {__tree_.swap(__s.__tree_);}
Howard Hinnantc51e1022010-05-11 19:42:16 +0000764
Howard Hinnant192cf032010-09-23 16:27:36 +0000765 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantf95f4f52011-06-04 15:22:34 +0000766 allocator_type get_allocator() const _NOEXCEPT {return __tree_.__alloc();}
Howard Hinnant192cf032010-09-23 16:27:36 +0000767 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000768 key_compare key_comp() const {return __tree_.value_comp();}
Howard Hinnant192cf032010-09-23 16:27:36 +0000769 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000770 value_compare value_comp() const {return __tree_.value_comp();}
771
772 // set operations:
Howard Hinnant192cf032010-09-23 16:27:36 +0000773 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000774 iterator find(const key_type& __k) {return __tree_.find(__k);}
Howard Hinnant192cf032010-09-23 16:27:36 +0000775 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000776 const_iterator find(const key_type& __k) const {return __tree_.find(__k);}
Marshall Clowc0152142013-08-13 01:11:06 +0000777#if _LIBCPP_STD_VER > 11
778 template <typename _K2>
779 _LIBCPP_INLINE_VISIBILITY
780 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
781 find(const _K2& __k) {return __tree_.find(__k);}
782 template <typename _K2>
783 _LIBCPP_INLINE_VISIBILITY
784 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
785 find(const _K2& __k) const {return __tree_.find(__k);}
786#endif
787
Howard Hinnant192cf032010-09-23 16:27:36 +0000788 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000789 size_type count(const key_type& __k) const
790 {return __tree_.__count_unique(__k);}
Marshall Clowe6a5f522014-08-24 23:54:16 +0000791#if _LIBCPP_STD_VER > 11
792 template <typename _K2>
793 _LIBCPP_INLINE_VISIBILITY
794 typename enable_if<__is_transparent<_Compare, _K2>::value,size_type>::type
Eric Fiseliera85c9e92018-02-10 02:53:47 +0000795 count(const _K2& __k) const {return __tree_.__count_multi(__k);}
Marshall Clowe6a5f522014-08-24 23:54:16 +0000796#endif
Zoe Carver3ffbab12019-07-16 03:21:01 +0000797
798#if _LIBCPP_STD_VER > 17
799 _LIBCPP_INLINE_VISIBILITY
800 bool contains(const key_type& __k) const {return find(__k) != end();}
801#endif // _LIBCPP_STD_VER > 17
802
Howard Hinnant192cf032010-09-23 16:27:36 +0000803 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000804 iterator lower_bound(const key_type& __k)
805 {return __tree_.lower_bound(__k);}
Howard Hinnant192cf032010-09-23 16:27:36 +0000806 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000807 const_iterator lower_bound(const key_type& __k) const
808 {return __tree_.lower_bound(__k);}
Marshall Clowc0152142013-08-13 01:11:06 +0000809#if _LIBCPP_STD_VER > 11
810 template <typename _K2>
811 _LIBCPP_INLINE_VISIBILITY
812 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
813 lower_bound(const _K2& __k) {return __tree_.lower_bound(__k);}
814
815 template <typename _K2>
816 _LIBCPP_INLINE_VISIBILITY
817 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
818 lower_bound(const _K2& __k) const {return __tree_.lower_bound(__k);}
819#endif
820
Howard Hinnant192cf032010-09-23 16:27:36 +0000821 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000822 iterator upper_bound(const key_type& __k)
823 {return __tree_.upper_bound(__k);}
Howard Hinnant192cf032010-09-23 16:27:36 +0000824 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000825 const_iterator upper_bound(const key_type& __k) const
826 {return __tree_.upper_bound(__k);}
Marshall Clowc0152142013-08-13 01:11:06 +0000827#if _LIBCPP_STD_VER > 11
828 template <typename _K2>
829 _LIBCPP_INLINE_VISIBILITY
830 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
831 upper_bound(const _K2& __k) {return __tree_.upper_bound(__k);}
832 template <typename _K2>
833 _LIBCPP_INLINE_VISIBILITY
834 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
835 upper_bound(const _K2& __k) const {return __tree_.upper_bound(__k);}
836#endif
837
Howard Hinnant192cf032010-09-23 16:27:36 +0000838 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000839 pair<iterator,iterator> equal_range(const key_type& __k)
840 {return __tree_.__equal_range_unique(__k);}
Howard Hinnant192cf032010-09-23 16:27:36 +0000841 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000842 pair<const_iterator,const_iterator> equal_range(const key_type& __k) const
843 {return __tree_.__equal_range_unique(__k);}
Marshall Clowc0152142013-08-13 01:11:06 +0000844#if _LIBCPP_STD_VER > 11
845 template <typename _K2>
846 _LIBCPP_INLINE_VISIBILITY
847 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<iterator,iterator>>::type
Eric Fiseliera85c9e92018-02-10 02:53:47 +0000848 equal_range(const _K2& __k) {return __tree_.__equal_range_multi(__k);}
Marshall Clowc0152142013-08-13 01:11:06 +0000849 template <typename _K2>
850 _LIBCPP_INLINE_VISIBILITY
851 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<const_iterator,const_iterator>>::type
Eric Fiseliera85c9e92018-02-10 02:53:47 +0000852 equal_range(const _K2& __k) const {return __tree_.__equal_range_multi(__k);}
Marshall Clowc0152142013-08-13 01:11:06 +0000853#endif
Howard Hinnantc51e1022010-05-11 19:42:16 +0000854};
855
Louis Dionne27ecc152019-06-11 18:21:08 +0000856#ifndef _LIBCPP_HAS_NO_DEDUCTION_GUIDES
857template<class _InputIterator,
Arthur O'Dwyer56226762021-03-03 23:02:20 -0500858 class _Compare = less<__iter_value_type<_InputIterator>>,
859 class _Allocator = allocator<__iter_value_type<_InputIterator>>,
Louis Dionne6c7da9a2019-07-19 17:13:39 +0000860 class = _EnableIf<__is_allocator<_Allocator>::value, void>,
861 class = _EnableIf<!__is_allocator<_Compare>::value, void>>
Louis Dionne27ecc152019-06-11 18:21:08 +0000862set(_InputIterator, _InputIterator, _Compare = _Compare(), _Allocator = _Allocator())
Arthur O'Dwyer56226762021-03-03 23:02:20 -0500863 -> set<__iter_value_type<_InputIterator>, _Compare, _Allocator>;
Louis Dionne27ecc152019-06-11 18:21:08 +0000864
865template<class _Key, class _Compare = less<_Key>,
866 class _Allocator = allocator<_Key>,
Louis Dionne6c7da9a2019-07-19 17:13:39 +0000867 class = _EnableIf<__is_allocator<_Allocator>::value, void>,
868 class = _EnableIf<!__is_allocator<_Compare>::value, void>>
Louis Dionne27ecc152019-06-11 18:21:08 +0000869set(initializer_list<_Key>, _Compare = _Compare(), _Allocator = _Allocator())
870 -> set<_Key, _Compare, _Allocator>;
871
872template<class _InputIterator, class _Allocator,
Louis Dionne6c7da9a2019-07-19 17:13:39 +0000873 class = _EnableIf<__is_allocator<_Allocator>::value, void>>
Louis Dionne27ecc152019-06-11 18:21:08 +0000874set(_InputIterator, _InputIterator, _Allocator)
Arthur O'Dwyer56226762021-03-03 23:02:20 -0500875 -> set<__iter_value_type<_InputIterator>,
876 less<__iter_value_type<_InputIterator>>, _Allocator>;
Louis Dionne27ecc152019-06-11 18:21:08 +0000877
878template<class _Key, class _Allocator,
Louis Dionne6c7da9a2019-07-19 17:13:39 +0000879 class = _EnableIf<__is_allocator<_Allocator>::value, void>>
Louis Dionne27ecc152019-06-11 18:21:08 +0000880set(initializer_list<_Key>, _Allocator)
881 -> set<_Key, less<_Key>, _Allocator>;
882#endif
883
Eric Fiselier615961b2017-04-18 20:58:03 +0000884#ifndef _LIBCPP_CXX03_LANG
Howard Hinnantc51e1022010-05-11 19:42:16 +0000885
886template <class _Key, class _Compare, class _Allocator>
887set<_Key, _Compare, _Allocator>::set(set&& __s, const allocator_type& __a)
Howard Hinnantb1ad5a82011-06-30 21:18:19 +0000888 : __tree_(_VSTD::move(__s.__tree_), __a)
Howard Hinnantc51e1022010-05-11 19:42:16 +0000889{
890 if (__a != __s.get_allocator())
891 {
892 const_iterator __e = cend();
893 while (!__s.empty())
Howard Hinnantb1ad5a82011-06-30 21:18:19 +0000894 insert(__e, _VSTD::move(__s.__tree_.remove(__s.begin())->__value_));
Howard Hinnantc51e1022010-05-11 19:42:16 +0000895 }
896}
897
Eric Fiselier615961b2017-04-18 20:58:03 +0000898#endif // _LIBCPP_CXX03_LANG
Howard Hinnantc51e1022010-05-11 19:42:16 +0000899
900template <class _Key, class _Compare, class _Allocator>
Howard Hinnant192cf032010-09-23 16:27:36 +0000901inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000902bool
903operator==(const set<_Key, _Compare, _Allocator>& __x,
904 const set<_Key, _Compare, _Allocator>& __y)
905{
Howard Hinnantb1ad5a82011-06-30 21:18:19 +0000906 return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin());
Howard Hinnantc51e1022010-05-11 19:42:16 +0000907}
908
909template <class _Key, class _Compare, class _Allocator>
Howard Hinnant192cf032010-09-23 16:27:36 +0000910inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000911bool
912operator< (const set<_Key, _Compare, _Allocator>& __x,
913 const set<_Key, _Compare, _Allocator>& __y)
914{
Howard Hinnantb1ad5a82011-06-30 21:18:19 +0000915 return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
Howard Hinnantc51e1022010-05-11 19:42:16 +0000916}
917
918template <class _Key, class _Compare, class _Allocator>
Howard Hinnant192cf032010-09-23 16:27:36 +0000919inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000920bool
921operator!=(const set<_Key, _Compare, _Allocator>& __x,
922 const set<_Key, _Compare, _Allocator>& __y)
923{
924 return !(__x == __y);
925}
926
927template <class _Key, class _Compare, class _Allocator>
Howard Hinnant192cf032010-09-23 16:27:36 +0000928inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000929bool
930operator> (const set<_Key, _Compare, _Allocator>& __x,
931 const set<_Key, _Compare, _Allocator>& __y)
932{
933 return __y < __x;
934}
935
936template <class _Key, class _Compare, class _Allocator>
Howard Hinnant192cf032010-09-23 16:27:36 +0000937inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000938bool
939operator>=(const set<_Key, _Compare, _Allocator>& __x,
940 const set<_Key, _Compare, _Allocator>& __y)
941{
942 return !(__x < __y);
943}
944
945template <class _Key, class _Compare, class _Allocator>
Howard Hinnant192cf032010-09-23 16:27:36 +0000946inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000947bool
948operator<=(const set<_Key, _Compare, _Allocator>& __x,
949 const set<_Key, _Compare, _Allocator>& __y)
950{
951 return !(__y < __x);
952}
953
954// specialized algorithms:
955template <class _Key, class _Compare, class _Allocator>
Howard Hinnant192cf032010-09-23 16:27:36 +0000956inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000957void
958swap(set<_Key, _Compare, _Allocator>& __x,
959 set<_Key, _Compare, _Allocator>& __y)
Howard Hinnantf95f4f52011-06-04 15:22:34 +0000960 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
Howard Hinnantc51e1022010-05-11 19:42:16 +0000961{
962 __x.swap(__y);
963}
964
Marshall Clow29b53f22018-12-14 18:49:35 +0000965#if _LIBCPP_STD_VER > 17
966template <class _Key, class _Compare, class _Allocator, class _Predicate>
967inline _LIBCPP_INLINE_VISIBILITY
Marek Kurdeja98b1412020-05-02 13:58:03 +0200968 typename set<_Key, _Compare, _Allocator>::size_type
969 erase_if(set<_Key, _Compare, _Allocator>& __c, _Predicate __pred) {
Arthur O'Dwyerb6738bd2021-03-21 16:53:09 -0400970 return _VSTD::__libcpp_erase_if_container(__c, __pred);
Marek Kurdeja98b1412020-05-02 13:58:03 +0200971}
Marshall Clow29b53f22018-12-14 18:49:35 +0000972#endif
973
Howard Hinnantc51e1022010-05-11 19:42:16 +0000974template <class _Key, class _Compare = less<_Key>,
975 class _Allocator = allocator<_Key> >
Eric Fiselierb5eb1bf2017-01-04 23:56:00 +0000976class _LIBCPP_TEMPLATE_VIS multiset
Howard Hinnantc51e1022010-05-11 19:42:16 +0000977{
978public:
979 // types:
Arthur O'Dwyer6a752e12021-03-03 11:10:49 -0500980 typedef _Key key_type;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000981 typedef key_type value_type;
Arthur O'Dwyer6a752e12021-03-03 11:10:49 -0500982 typedef _Compare key_compare;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000983 typedef key_compare value_compare;
Arthur O'Dwyer6a752e12021-03-03 11:10:49 -0500984 typedef __identity_t<_Allocator> allocator_type;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000985 typedef value_type& reference;
986 typedef const value_type& const_reference;
987
Marshall Clow5128cf32015-11-26 01:24:04 +0000988 static_assert((is_same<typename allocator_type::value_type, value_type>::value),
989 "Allocator::value_type must be same type as value_type");
990
Howard Hinnantc51e1022010-05-11 19:42:16 +0000991private:
992 typedef __tree<value_type, value_compare, allocator_type> __base;
993 typedef allocator_traits<allocator_type> __alloc_traits;
994 typedef typename __base::__node_holder __node_holder;
995
996 __base __tree_;
997
998public:
999 typedef typename __base::pointer pointer;
1000 typedef typename __base::const_pointer const_pointer;
1001 typedef typename __base::size_type size_type;
1002 typedef typename __base::difference_type difference_type;
1003 typedef typename __base::const_iterator iterator;
1004 typedef typename __base::const_iterator const_iterator;
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001005 typedef _VSTD::reverse_iterator<iterator> reverse_iterator;
1006 typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator;
Howard Hinnantc51e1022010-05-11 19:42:16 +00001007
Erik Pilkingtonc37a3d82018-08-01 01:33:38 +00001008#if _LIBCPP_STD_VER > 14
1009 typedef __set_node_handle<typename __base::__node, allocator_type> node_type;
1010#endif
1011
Erik Pilkington82a65ad2018-10-31 17:31:35 +00001012 template <class _Key2, class _Compare2, class _Alloc2>
1013 friend class _LIBCPP_TEMPLATE_VIS set;
1014 template <class _Key2, class _Compare2, class _Alloc2>
1015 friend class _LIBCPP_TEMPLATE_VIS multiset;
1016
Howard Hinnantc51e1022010-05-11 19:42:16 +00001017 // construct/copy/destroy:
Howard Hinnant192cf032010-09-23 16:27:36 +00001018 _LIBCPP_INLINE_VISIBILITY
Marshall Clow7086a5a2014-03-10 04:50:10 +00001019 multiset()
1020 _NOEXCEPT_(
1021 is_nothrow_default_constructible<allocator_type>::value &&
1022 is_nothrow_default_constructible<key_compare>::value &&
1023 is_nothrow_copy_constructible<key_compare>::value)
1024 : __tree_(value_compare()) {}
1025
1026 _LIBCPP_INLINE_VISIBILITY
1027 explicit multiset(const value_compare& __comp)
Howard Hinnantf95f4f52011-06-04 15:22:34 +00001028 _NOEXCEPT_(
1029 is_nothrow_default_constructible<allocator_type>::value &&
Howard Hinnantf95f4f52011-06-04 15:22:34 +00001030 is_nothrow_copy_constructible<key_compare>::value)
Howard Hinnantc51e1022010-05-11 19:42:16 +00001031 : __tree_(__comp) {}
Marshall Clow7086a5a2014-03-10 04:50:10 +00001032
Howard Hinnant192cf032010-09-23 16:27:36 +00001033 _LIBCPP_INLINE_VISIBILITY
Marshall Clow7ed23a72014-03-05 19:06:20 +00001034 explicit multiset(const value_compare& __comp, const allocator_type& __a)
Howard Hinnantc51e1022010-05-11 19:42:16 +00001035 : __tree_(__comp, __a) {}
1036 template <class _InputIterator>
Howard Hinnant192cf032010-09-23 16:27:36 +00001037 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001038 multiset(_InputIterator __f, _InputIterator __l,
1039 const value_compare& __comp = value_compare())
1040 : __tree_(__comp)
1041 {
1042 insert(__f, __l);
1043 }
1044
Marshall Clow631788a2013-09-11 00:06:45 +00001045#if _LIBCPP_STD_VER > 11
1046 template <class _InputIterator>
Louis Dionned2322c82018-11-01 14:41:37 +00001047 _LIBCPP_INLINE_VISIBILITY
Marshall Clow631788a2013-09-11 00:06:45 +00001048 multiset(_InputIterator __f, _InputIterator __l, const allocator_type& __a)
1049 : multiset(__f, __l, key_compare(), __a) {}
1050#endif
1051
Howard Hinnantc51e1022010-05-11 19:42:16 +00001052 template <class _InputIterator>
Howard Hinnant192cf032010-09-23 16:27:36 +00001053 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001054 multiset(_InputIterator __f, _InputIterator __l,
1055 const value_compare& __comp, const allocator_type& __a)
1056 : __tree_(__comp, __a)
1057 {
1058 insert(__f, __l);
1059 }
1060
Howard Hinnant192cf032010-09-23 16:27:36 +00001061 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001062 multiset(const multiset& __s)
1063 : __tree_(__s.__tree_.value_comp(),
1064 __alloc_traits::select_on_container_copy_construction(__s.__tree_.__alloc()))
1065 {
1066 insert(__s.begin(), __s.end());
1067 }
1068
Howard Hinnantd3a657f2011-07-01 19:24:36 +00001069 _LIBCPP_INLINE_VISIBILITY
1070 multiset& operator=(const multiset& __s)
1071 {
1072 __tree_ = __s.__tree_;
1073 return *this;
1074 }
1075
Eric Fiselier615961b2017-04-18 20:58:03 +00001076#ifndef _LIBCPP_CXX03_LANG
Howard Hinnant192cf032010-09-23 16:27:36 +00001077 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001078 multiset(multiset&& __s)
Howard Hinnantf95f4f52011-06-04 15:22:34 +00001079 _NOEXCEPT_(is_nothrow_move_constructible<__base>::value)
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001080 : __tree_(_VSTD::move(__s.__tree_)) {}
Eric Fiselier615961b2017-04-18 20:58:03 +00001081
1082 multiset(multiset&& __s, const allocator_type& __a);
1083#endif // _LIBCPP_CXX03_LANG
Howard Hinnant192cf032010-09-23 16:27:36 +00001084 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001085 explicit multiset(const allocator_type& __a)
1086 : __tree_(__a) {}
Howard Hinnant192cf032010-09-23 16:27:36 +00001087 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001088 multiset(const multiset& __s, const allocator_type& __a)
1089 : __tree_(__s.__tree_.value_comp(), __a)
1090 {
1091 insert(__s.begin(), __s.end());
1092 }
Howard Hinnantc51e1022010-05-11 19:42:16 +00001093
Eric Fiselier615961b2017-04-18 20:58:03 +00001094#ifndef _LIBCPP_CXX03_LANG
Howard Hinnant192cf032010-09-23 16:27:36 +00001095 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001096 multiset(initializer_list<value_type> __il, const value_compare& __comp = value_compare())
1097 : __tree_(__comp)
1098 {
1099 insert(__il.begin(), __il.end());
1100 }
1101
Howard Hinnant192cf032010-09-23 16:27:36 +00001102 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001103 multiset(initializer_list<value_type> __il, const value_compare& __comp,
1104 const allocator_type& __a)
1105 : __tree_(__comp, __a)
1106 {
1107 insert(__il.begin(), __il.end());
1108 }
1109
Marshall Clow631788a2013-09-11 00:06:45 +00001110#if _LIBCPP_STD_VER > 11
Louis Dionned2322c82018-11-01 14:41:37 +00001111 _LIBCPP_INLINE_VISIBILITY
Marshall Clow631788a2013-09-11 00:06:45 +00001112 multiset(initializer_list<value_type> __il, const allocator_type& __a)
1113 : multiset(__il, key_compare(), __a) {}
1114#endif
1115
Howard Hinnant192cf032010-09-23 16:27:36 +00001116 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001117 multiset& operator=(initializer_list<value_type> __il)
1118 {
1119 __tree_.__assign_multi(__il.begin(), __il.end());
1120 return *this;
1121 }
1122
Howard Hinnant192cf032010-09-23 16:27:36 +00001123 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001124 multiset& operator=(multiset&& __s)
Howard Hinnantf95f4f52011-06-04 15:22:34 +00001125 _NOEXCEPT_(is_nothrow_move_assignable<__base>::value)
Howard Hinnantc51e1022010-05-11 19:42:16 +00001126 {
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001127 __tree_ = _VSTD::move(__s.__tree_);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001128 return *this;
1129 }
Eric Fiselier615961b2017-04-18 20:58:03 +00001130#endif // _LIBCPP_CXX03_LANG
Howard Hinnantc51e1022010-05-11 19:42:16 +00001131
Howard Hinnant192cf032010-09-23 16:27:36 +00001132 _LIBCPP_INLINE_VISIBILITY
Louis Dionne69c42c02019-04-11 16:14:56 +00001133 ~multiset() {
1134 static_assert(sizeof(__diagnose_non_const_comparator<_Key, _Compare>()), "");
1135 }
1136
1137 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantf95f4f52011-06-04 15:22:34 +00001138 iterator begin() _NOEXCEPT {return __tree_.begin();}
Howard Hinnant192cf032010-09-23 16:27:36 +00001139 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantf95f4f52011-06-04 15:22:34 +00001140 const_iterator begin() const _NOEXCEPT {return __tree_.begin();}
Howard Hinnant192cf032010-09-23 16:27:36 +00001141 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantf95f4f52011-06-04 15:22:34 +00001142 iterator end() _NOEXCEPT {return __tree_.end();}
Howard Hinnant192cf032010-09-23 16:27:36 +00001143 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantf95f4f52011-06-04 15:22:34 +00001144 const_iterator end() const _NOEXCEPT {return __tree_.end();}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001145
Howard Hinnant192cf032010-09-23 16:27:36 +00001146 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantf95f4f52011-06-04 15:22:34 +00001147 reverse_iterator rbegin() _NOEXCEPT
1148 {return reverse_iterator(end());}
Howard Hinnant192cf032010-09-23 16:27:36 +00001149 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantf95f4f52011-06-04 15:22:34 +00001150 const_reverse_iterator rbegin() const _NOEXCEPT
1151 {return const_reverse_iterator(end());}
Howard Hinnant192cf032010-09-23 16:27:36 +00001152 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantf95f4f52011-06-04 15:22:34 +00001153 reverse_iterator rend() _NOEXCEPT
1154 {return reverse_iterator(begin());}
Howard Hinnant192cf032010-09-23 16:27:36 +00001155 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantf95f4f52011-06-04 15:22:34 +00001156 const_reverse_iterator rend() const _NOEXCEPT
1157 {return const_reverse_iterator(begin());}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001158
Howard Hinnant192cf032010-09-23 16:27:36 +00001159 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantf95f4f52011-06-04 15:22:34 +00001160 const_iterator cbegin() const _NOEXCEPT {return begin();}
Howard Hinnant192cf032010-09-23 16:27:36 +00001161 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantf95f4f52011-06-04 15:22:34 +00001162 const_iterator cend() const _NOEXCEPT {return end();}
Howard Hinnant192cf032010-09-23 16:27:36 +00001163 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantf95f4f52011-06-04 15:22:34 +00001164 const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();}
Howard Hinnant192cf032010-09-23 16:27:36 +00001165 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantf95f4f52011-06-04 15:22:34 +00001166 const_reverse_iterator crend() const _NOEXCEPT {return rend();}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001167
Marshall Clow425f5752017-11-15 05:51:26 +00001168 _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantf95f4f52011-06-04 15:22:34 +00001169 bool empty() const _NOEXCEPT {return __tree_.size() == 0;}
Howard Hinnant192cf032010-09-23 16:27:36 +00001170 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantf95f4f52011-06-04 15:22:34 +00001171 size_type size() const _NOEXCEPT {return __tree_.size();}
Howard Hinnant192cf032010-09-23 16:27:36 +00001172 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantf95f4f52011-06-04 15:22:34 +00001173 size_type max_size() const _NOEXCEPT {return __tree_.max_size();}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001174
1175 // modifiers:
Eric Fiselier615961b2017-04-18 20:58:03 +00001176#ifndef _LIBCPP_CXX03_LANG
Howard Hinnantc51e1022010-05-11 19:42:16 +00001177 template <class... _Args>
Howard Hinnant192cf032010-09-23 16:27:36 +00001178 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001179 iterator emplace(_Args&&... __args)
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001180 {return __tree_.__emplace_multi(_VSTD::forward<_Args>(__args)...);}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001181 template <class... _Args>
Howard Hinnant192cf032010-09-23 16:27:36 +00001182 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001183 iterator emplace_hint(const_iterator __p, _Args&&... __args)
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001184 {return __tree_.__emplace_hint_multi(__p, _VSTD::forward<_Args>(__args)...);}
Eric Fiselier615961b2017-04-18 20:58:03 +00001185#endif // _LIBCPP_CXX03_LANG
1186
Howard Hinnant192cf032010-09-23 16:27:36 +00001187 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001188 iterator insert(const value_type& __v)
1189 {return __tree_.__insert_multi(__v);}
Howard Hinnant192cf032010-09-23 16:27:36 +00001190 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001191 iterator insert(const_iterator __p, const value_type& __v)
1192 {return __tree_.__insert_multi(__p, __v);}
Eric Fiselier615961b2017-04-18 20:58:03 +00001193
Howard Hinnantc51e1022010-05-11 19:42:16 +00001194 template <class _InputIterator>
Howard Hinnant192cf032010-09-23 16:27:36 +00001195 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001196 void insert(_InputIterator __f, _InputIterator __l)
1197 {
1198 for (const_iterator __e = cend(); __f != __l; ++__f)
1199 __tree_.__insert_multi(__e, *__f);
1200 }
1201
Eric Fiselier615961b2017-04-18 20:58:03 +00001202#ifndef _LIBCPP_CXX03_LANG
1203 _LIBCPP_INLINE_VISIBILITY
1204 iterator insert(value_type&& __v)
1205 {return __tree_.__insert_multi(_VSTD::move(__v));}
1206
1207 _LIBCPP_INLINE_VISIBILITY
1208 iterator insert(const_iterator __p, value_type&& __v)
1209 {return __tree_.__insert_multi(__p, _VSTD::move(__v));}
1210
Howard Hinnant192cf032010-09-23 16:27:36 +00001211 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001212 void insert(initializer_list<value_type> __il)
1213 {insert(__il.begin(), __il.end());}
Eric Fiselier615961b2017-04-18 20:58:03 +00001214#endif // _LIBCPP_CXX03_LANG
Howard Hinnantc51e1022010-05-11 19:42:16 +00001215
Howard Hinnant192cf032010-09-23 16:27:36 +00001216 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001217 iterator erase(const_iterator __p) {return __tree_.erase(__p);}
Howard Hinnant192cf032010-09-23 16:27:36 +00001218 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001219 size_type erase(const key_type& __k) {return __tree_.__erase_multi(__k);}
Howard Hinnant192cf032010-09-23 16:27:36 +00001220 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001221 iterator erase(const_iterator __f, const_iterator __l)
1222 {return __tree_.erase(__f, __l);}
Howard Hinnant192cf032010-09-23 16:27:36 +00001223 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantf95f4f52011-06-04 15:22:34 +00001224 void clear() _NOEXCEPT {__tree_.clear();}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001225
Erik Pilkingtonc37a3d82018-08-01 01:33:38 +00001226#if _LIBCPP_STD_VER > 14
1227 _LIBCPP_INLINE_VISIBILITY
1228 iterator insert(node_type&& __nh)
1229 {
1230 _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(),
1231 "node_type with incompatible allocator passed to multiset::insert()");
1232 return __tree_.template __node_handle_insert_multi<node_type>(
1233 _VSTD::move(__nh));
1234 }
1235 _LIBCPP_INLINE_VISIBILITY
1236 iterator insert(const_iterator __hint, node_type&& __nh)
1237 {
1238 _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(),
1239 "node_type with incompatible allocator passed to multiset::insert()");
1240 return __tree_.template __node_handle_insert_multi<node_type>(
1241 __hint, _VSTD::move(__nh));
1242 }
1243 _LIBCPP_INLINE_VISIBILITY
1244 node_type extract(key_type const& __key)
1245 {
1246 return __tree_.template __node_handle_extract<node_type>(__key);
1247 }
1248 _LIBCPP_INLINE_VISIBILITY
1249 node_type extract(const_iterator __it)
1250 {
1251 return __tree_.template __node_handle_extract<node_type>(__it);
1252 }
Louis Dionned2322c82018-11-01 14:41:37 +00001253 template <class _Compare2>
Erik Pilkington82a65ad2018-10-31 17:31:35 +00001254 _LIBCPP_INLINE_VISIBILITY
Louis Dionned2322c82018-11-01 14:41:37 +00001255 void merge(multiset<key_type, _Compare2, allocator_type>& __source)
Erik Pilkington82a65ad2018-10-31 17:31:35 +00001256 {
1257 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
1258 "merging container with incompatible allocator");
1259 __tree_.__node_handle_merge_multi(__source.__tree_);
1260 }
Louis Dionned2322c82018-11-01 14:41:37 +00001261 template <class _Compare2>
Erik Pilkington82a65ad2018-10-31 17:31:35 +00001262 _LIBCPP_INLINE_VISIBILITY
Louis Dionned2322c82018-11-01 14:41:37 +00001263 void merge(multiset<key_type, _Compare2, allocator_type>&& __source)
Erik Pilkington82a65ad2018-10-31 17:31:35 +00001264 {
1265 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
1266 "merging container with incompatible allocator");
1267 __tree_.__node_handle_merge_multi(__source.__tree_);
1268 }
Louis Dionned2322c82018-11-01 14:41:37 +00001269 template <class _Compare2>
Erik Pilkington82a65ad2018-10-31 17:31:35 +00001270 _LIBCPP_INLINE_VISIBILITY
Louis Dionned2322c82018-11-01 14:41:37 +00001271 void merge(set<key_type, _Compare2, allocator_type>& __source)
Erik Pilkington82a65ad2018-10-31 17:31:35 +00001272 {
1273 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
1274 "merging container with incompatible allocator");
1275 __tree_.__node_handle_merge_multi(__source.__tree_);
1276 }
Louis Dionned2322c82018-11-01 14:41:37 +00001277 template <class _Compare2>
Erik Pilkington82a65ad2018-10-31 17:31:35 +00001278 _LIBCPP_INLINE_VISIBILITY
Louis Dionned2322c82018-11-01 14:41:37 +00001279 void merge(set<key_type, _Compare2, allocator_type>&& __source)
Erik Pilkington82a65ad2018-10-31 17:31:35 +00001280 {
1281 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
1282 "merging container with incompatible allocator");
1283 __tree_.__node_handle_merge_multi(__source.__tree_);
1284 }
Erik Pilkingtonc37a3d82018-08-01 01:33:38 +00001285#endif
1286
Howard Hinnant192cf032010-09-23 16:27:36 +00001287 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantf95f4f52011-06-04 15:22:34 +00001288 void swap(multiset& __s)
1289 _NOEXCEPT_(__is_nothrow_swappable<__base>::value)
1290 {__tree_.swap(__s.__tree_);}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001291
Howard Hinnant192cf032010-09-23 16:27:36 +00001292 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantf95f4f52011-06-04 15:22:34 +00001293 allocator_type get_allocator() const _NOEXCEPT {return __tree_.__alloc();}
Howard Hinnant192cf032010-09-23 16:27:36 +00001294 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001295 key_compare key_comp() const {return __tree_.value_comp();}
Howard Hinnant192cf032010-09-23 16:27:36 +00001296 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001297 value_compare value_comp() const {return __tree_.value_comp();}
1298
1299 // set operations:
Howard Hinnant192cf032010-09-23 16:27:36 +00001300 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001301 iterator find(const key_type& __k) {return __tree_.find(__k);}
Howard Hinnant192cf032010-09-23 16:27:36 +00001302 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001303 const_iterator find(const key_type& __k) const {return __tree_.find(__k);}
Marshall Clowc0152142013-08-13 01:11:06 +00001304#if _LIBCPP_STD_VER > 11
1305 template <typename _K2>
1306 _LIBCPP_INLINE_VISIBILITY
1307 typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,iterator>::type
1308 find(const _K2& __k) {return __tree_.find(__k);}
1309 template <typename _K2>
1310 _LIBCPP_INLINE_VISIBILITY
1311 typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,const_iterator>::type
1312 find(const _K2& __k) const {return __tree_.find(__k);}
1313#endif
1314
Howard Hinnant192cf032010-09-23 16:27:36 +00001315 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001316 size_type count(const key_type& __k) const
1317 {return __tree_.__count_multi(__k);}
Marshall Clowe6a5f522014-08-24 23:54:16 +00001318#if _LIBCPP_STD_VER > 11
1319 template <typename _K2>
1320 _LIBCPP_INLINE_VISIBILITY
1321 typename enable_if<__is_transparent<_Compare, _K2>::value,size_type>::type
Marshall Clow5571bcd2018-01-07 17:39:57 +00001322 count(const _K2& __k) const {return __tree_.__count_multi(__k);}
Marshall Clowe6a5f522014-08-24 23:54:16 +00001323#endif
Marshall Clowc0152142013-08-13 01:11:06 +00001324
Zoe Carver3ffbab12019-07-16 03:21:01 +00001325#if _LIBCPP_STD_VER > 17
1326 _LIBCPP_INLINE_VISIBILITY
1327 bool contains(const key_type& __k) const {return find(__k) != end();}
1328#endif // _LIBCPP_STD_VER > 17
1329
Howard Hinnant192cf032010-09-23 16:27:36 +00001330 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001331 iterator lower_bound(const key_type& __k)
1332 {return __tree_.lower_bound(__k);}
Howard Hinnant192cf032010-09-23 16:27:36 +00001333 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001334 const_iterator lower_bound(const key_type& __k) const
1335 {return __tree_.lower_bound(__k);}
Marshall Clowc0152142013-08-13 01:11:06 +00001336#if _LIBCPP_STD_VER > 11
1337 template <typename _K2>
1338 _LIBCPP_INLINE_VISIBILITY
1339 typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,iterator>::type
1340 lower_bound(const _K2& __k) {return __tree_.lower_bound(__k);}
1341
1342 template <typename _K2>
1343 _LIBCPP_INLINE_VISIBILITY
1344 typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,const_iterator>::type
1345 lower_bound(const _K2& __k) const {return __tree_.lower_bound(__k);}
1346#endif
1347
Howard Hinnant192cf032010-09-23 16:27:36 +00001348 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001349 iterator upper_bound(const key_type& __k)
1350 {return __tree_.upper_bound(__k);}
Howard Hinnant192cf032010-09-23 16:27:36 +00001351 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001352 const_iterator upper_bound(const key_type& __k) const
1353 {return __tree_.upper_bound(__k);}
Marshall Clowc0152142013-08-13 01:11:06 +00001354#if _LIBCPP_STD_VER > 11
1355 template <typename _K2>
1356 _LIBCPP_INLINE_VISIBILITY
1357 typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,iterator>::type
1358 upper_bound(const _K2& __k) {return __tree_.upper_bound(__k);}
1359 template <typename _K2>
1360 _LIBCPP_INLINE_VISIBILITY
1361 typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,const_iterator>::type
1362 upper_bound(const _K2& __k) const {return __tree_.upper_bound(__k);}
1363#endif
1364
Howard Hinnant192cf032010-09-23 16:27:36 +00001365 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001366 pair<iterator,iterator> equal_range(const key_type& __k)
1367 {return __tree_.__equal_range_multi(__k);}
Howard Hinnant192cf032010-09-23 16:27:36 +00001368 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001369 pair<const_iterator,const_iterator> equal_range(const key_type& __k) const
1370 {return __tree_.__equal_range_multi(__k);}
Marshall Clowc0152142013-08-13 01:11:06 +00001371#if _LIBCPP_STD_VER > 11
1372 template <typename _K2>
1373 _LIBCPP_INLINE_VISIBILITY
1374 typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,pair<iterator,iterator>>::type
1375 equal_range(const _K2& __k) {return __tree_.__equal_range_multi(__k);}
1376 template <typename _K2>
1377 _LIBCPP_INLINE_VISIBILITY
1378 typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,pair<const_iterator,const_iterator>>::type
1379 equal_range(const _K2& __k) const {return __tree_.__equal_range_multi(__k);}
1380#endif
Howard Hinnantc51e1022010-05-11 19:42:16 +00001381};
1382
Louis Dionne27ecc152019-06-11 18:21:08 +00001383#ifndef _LIBCPP_HAS_NO_DEDUCTION_GUIDES
1384template<class _InputIterator,
Arthur O'Dwyer56226762021-03-03 23:02:20 -05001385 class _Compare = less<__iter_value_type<_InputIterator>>,
1386 class _Allocator = allocator<__iter_value_type<_InputIterator>>,
Louis Dionne6c7da9a2019-07-19 17:13:39 +00001387 class = _EnableIf<__is_allocator<_Allocator>::value, void>,
1388 class = _EnableIf<!__is_allocator<_Compare>::value, void>>
Louis Dionne27ecc152019-06-11 18:21:08 +00001389multiset(_InputIterator, _InputIterator, _Compare = _Compare(), _Allocator = _Allocator())
Arthur O'Dwyer56226762021-03-03 23:02:20 -05001390 -> multiset<__iter_value_type<_InputIterator>, _Compare, _Allocator>;
Louis Dionne27ecc152019-06-11 18:21:08 +00001391
1392template<class _Key, class _Compare = less<_Key>,
1393 class _Allocator = allocator<_Key>,
Louis Dionne6c7da9a2019-07-19 17:13:39 +00001394 class = _EnableIf<__is_allocator<_Allocator>::value, void>,
1395 class = _EnableIf<!__is_allocator<_Compare>::value, void>>
Louis Dionne27ecc152019-06-11 18:21:08 +00001396multiset(initializer_list<_Key>, _Compare = _Compare(), _Allocator = _Allocator())
1397 -> multiset<_Key, _Compare, _Allocator>;
1398
1399template<class _InputIterator, class _Allocator,
Louis Dionne6c7da9a2019-07-19 17:13:39 +00001400 class = _EnableIf<__is_allocator<_Allocator>::value, void>>
Louis Dionne27ecc152019-06-11 18:21:08 +00001401multiset(_InputIterator, _InputIterator, _Allocator)
Arthur O'Dwyer56226762021-03-03 23:02:20 -05001402 -> multiset<__iter_value_type<_InputIterator>,
1403 less<__iter_value_type<_InputIterator>>, _Allocator>;
Louis Dionne27ecc152019-06-11 18:21:08 +00001404
1405template<class _Key, class _Allocator,
Louis Dionne6c7da9a2019-07-19 17:13:39 +00001406 class = _EnableIf<__is_allocator<_Allocator>::value, void>>
Louis Dionne27ecc152019-06-11 18:21:08 +00001407multiset(initializer_list<_Key>, _Allocator)
1408 -> multiset<_Key, less<_Key>, _Allocator>;
1409#endif
1410
Eric Fiselier615961b2017-04-18 20:58:03 +00001411#ifndef _LIBCPP_CXX03_LANG
Howard Hinnantc51e1022010-05-11 19:42:16 +00001412
1413template <class _Key, class _Compare, class _Allocator>
1414multiset<_Key, _Compare, _Allocator>::multiset(multiset&& __s, const allocator_type& __a)
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001415 : __tree_(_VSTD::move(__s.__tree_), __a)
Howard Hinnantc51e1022010-05-11 19:42:16 +00001416{
1417 if (__a != __s.get_allocator())
1418 {
1419 const_iterator __e = cend();
1420 while (!__s.empty())
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001421 insert(__e, _VSTD::move(__s.__tree_.remove(__s.begin())->__value_));
Howard Hinnantc51e1022010-05-11 19:42:16 +00001422 }
1423}
1424
Eric Fiselier615961b2017-04-18 20:58:03 +00001425#endif // _LIBCPP_CXX03_LANG
Howard Hinnantc51e1022010-05-11 19:42:16 +00001426
1427template <class _Key, class _Compare, class _Allocator>
Howard Hinnant192cf032010-09-23 16:27:36 +00001428inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001429bool
1430operator==(const multiset<_Key, _Compare, _Allocator>& __x,
1431 const multiset<_Key, _Compare, _Allocator>& __y)
1432{
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001433 return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin());
Howard Hinnantc51e1022010-05-11 19:42:16 +00001434}
1435
1436template <class _Key, class _Compare, class _Allocator>
Howard Hinnant192cf032010-09-23 16:27:36 +00001437inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001438bool
1439operator< (const multiset<_Key, _Compare, _Allocator>& __x,
1440 const multiset<_Key, _Compare, _Allocator>& __y)
1441{
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001442 return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
Howard Hinnantc51e1022010-05-11 19:42:16 +00001443}
1444
1445template <class _Key, class _Compare, class _Allocator>
Howard Hinnant192cf032010-09-23 16:27:36 +00001446inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001447bool
1448operator!=(const multiset<_Key, _Compare, _Allocator>& __x,
1449 const multiset<_Key, _Compare, _Allocator>& __y)
1450{
1451 return !(__x == __y);
1452}
1453
1454template <class _Key, class _Compare, class _Allocator>
Howard Hinnant192cf032010-09-23 16:27:36 +00001455inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001456bool
1457operator> (const multiset<_Key, _Compare, _Allocator>& __x,
1458 const multiset<_Key, _Compare, _Allocator>& __y)
1459{
1460 return __y < __x;
1461}
1462
1463template <class _Key, class _Compare, class _Allocator>
Howard Hinnant192cf032010-09-23 16:27:36 +00001464inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001465bool
1466operator>=(const multiset<_Key, _Compare, _Allocator>& __x,
1467 const multiset<_Key, _Compare, _Allocator>& __y)
1468{
1469 return !(__x < __y);
1470}
1471
1472template <class _Key, class _Compare, class _Allocator>
Howard Hinnant192cf032010-09-23 16:27:36 +00001473inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001474bool
1475operator<=(const multiset<_Key, _Compare, _Allocator>& __x,
1476 const multiset<_Key, _Compare, _Allocator>& __y)
1477{
1478 return !(__y < __x);
1479}
1480
1481template <class _Key, class _Compare, class _Allocator>
Howard Hinnant192cf032010-09-23 16:27:36 +00001482inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001483void
1484swap(multiset<_Key, _Compare, _Allocator>& __x,
1485 multiset<_Key, _Compare, _Allocator>& __y)
Howard Hinnantf95f4f52011-06-04 15:22:34 +00001486 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
Howard Hinnantc51e1022010-05-11 19:42:16 +00001487{
1488 __x.swap(__y);
1489}
1490
Marshall Clow29b53f22018-12-14 18:49:35 +00001491#if _LIBCPP_STD_VER > 17
1492template <class _Key, class _Compare, class _Allocator, class _Predicate>
1493inline _LIBCPP_INLINE_VISIBILITY
Marek Kurdeja98b1412020-05-02 13:58:03 +02001494 typename multiset<_Key, _Compare, _Allocator>::size_type
1495 erase_if(multiset<_Key, _Compare, _Allocator>& __c, _Predicate __pred) {
Arthur O'Dwyerb6738bd2021-03-21 16:53:09 -04001496 return _VSTD::__libcpp_erase_if_container(__c, __pred);
Marek Kurdeja98b1412020-05-02 13:58:03 +02001497}
Marshall Clow29b53f22018-12-14 18:49:35 +00001498#endif
1499
Howard Hinnantc51e1022010-05-11 19:42:16 +00001500_LIBCPP_END_NAMESPACE_STD
1501
1502#endif // _LIBCPP_SET