blob: 3a83827711f1780b36ee46614e6d52fde90fa083 [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>
Howard Hinnantc51e1022010-05-11 19:42:16 +0000431#include <functional>
Marshall Clow0a1e7502018-09-12 19:41:40 +0000432#include <version>
Howard Hinnantc51e1022010-05-11 19:42:16 +0000433
Howard Hinnantaaaa52b2011-10-17 20:05:10 +0000434#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
Howard Hinnantc51e1022010-05-11 19:42:16 +0000435#pragma GCC system_header
Howard Hinnantaaaa52b2011-10-17 20:05:10 +0000436#endif
Howard Hinnantc51e1022010-05-11 19:42:16 +0000437
438_LIBCPP_BEGIN_NAMESPACE_STD
439
Erik Pilkington82a65ad2018-10-31 17:31:35 +0000440template <class _Key, class _Compare, class _Allocator>
441class multiset;
442
Howard Hinnantc51e1022010-05-11 19:42:16 +0000443template <class _Key, class _Compare = less<_Key>,
444 class _Allocator = allocator<_Key> >
Eric Fiselierb5eb1bf2017-01-04 23:56:00 +0000445class _LIBCPP_TEMPLATE_VIS set
Howard Hinnantc51e1022010-05-11 19:42:16 +0000446{
447public:
448 // types:
449 typedef _Key key_type;
450 typedef key_type value_type;
451 typedef _Compare key_compare;
452 typedef key_compare value_compare;
Arthur O'Dwyer6a752e12021-03-03 11:10:49 -0500453 typedef __identity_t<_Allocator> allocator_type;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000454 typedef value_type& reference;
455 typedef const value_type& const_reference;
456
Marshall Clow5128cf32015-11-26 01:24:04 +0000457 static_assert((is_same<typename allocator_type::value_type, value_type>::value),
458 "Allocator::value_type must be same type as value_type");
459
Howard Hinnantc51e1022010-05-11 19:42:16 +0000460private:
461 typedef __tree<value_type, value_compare, allocator_type> __base;
462 typedef allocator_traits<allocator_type> __alloc_traits;
463 typedef typename __base::__node_holder __node_holder;
464
465 __base __tree_;
466
467public:
468 typedef typename __base::pointer pointer;
469 typedef typename __base::const_pointer const_pointer;
470 typedef typename __base::size_type size_type;
471 typedef typename __base::difference_type difference_type;
472 typedef typename __base::const_iterator iterator;
473 typedef typename __base::const_iterator const_iterator;
Howard Hinnantb1ad5a82011-06-30 21:18:19 +0000474 typedef _VSTD::reverse_iterator<iterator> reverse_iterator;
475 typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000476
Erik Pilkingtonc37a3d82018-08-01 01:33:38 +0000477#if _LIBCPP_STD_VER > 14
478 typedef __set_node_handle<typename __base::__node, allocator_type> node_type;
479 typedef __insert_return_type<iterator, node_type> insert_return_type;
480#endif
481
Erik Pilkington82a65ad2018-10-31 17:31:35 +0000482 template <class _Key2, class _Compare2, class _Alloc2>
483 friend class _LIBCPP_TEMPLATE_VIS set;
484 template <class _Key2, class _Compare2, class _Alloc2>
485 friend class _LIBCPP_TEMPLATE_VIS multiset;
486
Howard Hinnant192cf032010-09-23 16:27:36 +0000487 _LIBCPP_INLINE_VISIBILITY
Marshall Clow7086a5a2014-03-10 04:50:10 +0000488 set()
489 _NOEXCEPT_(
490 is_nothrow_default_constructible<allocator_type>::value &&
491 is_nothrow_default_constructible<key_compare>::value &&
492 is_nothrow_copy_constructible<key_compare>::value)
493 : __tree_(value_compare()) {}
494
495 _LIBCPP_INLINE_VISIBILITY
496 explicit set(const value_compare& __comp)
Howard Hinnantf95f4f52011-06-04 15:22:34 +0000497 _NOEXCEPT_(
498 is_nothrow_default_constructible<allocator_type>::value &&
Howard Hinnantf95f4f52011-06-04 15:22:34 +0000499 is_nothrow_copy_constructible<key_compare>::value)
Howard Hinnantc51e1022010-05-11 19:42:16 +0000500 : __tree_(__comp) {}
Marshall Clow7086a5a2014-03-10 04:50:10 +0000501
Howard Hinnant192cf032010-09-23 16:27:36 +0000502 _LIBCPP_INLINE_VISIBILITY
Marshall Clow7ed23a72014-03-05 19:06:20 +0000503 explicit set(const value_compare& __comp, const allocator_type& __a)
Howard Hinnantc51e1022010-05-11 19:42:16 +0000504 : __tree_(__comp, __a) {}
505 template <class _InputIterator>
Howard Hinnant192cf032010-09-23 16:27:36 +0000506 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000507 set(_InputIterator __f, _InputIterator __l,
508 const value_compare& __comp = value_compare())
509 : __tree_(__comp)
510 {
511 insert(__f, __l);
512 }
513
514 template <class _InputIterator>
Howard Hinnant192cf032010-09-23 16:27:36 +0000515 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000516 set(_InputIterator __f, _InputIterator __l, const value_compare& __comp,
517 const allocator_type& __a)
518 : __tree_(__comp, __a)
519 {
520 insert(__f, __l);
521 }
522
Marshall Clow631788a2013-09-11 00:06:45 +0000523#if _LIBCPP_STD_VER > 11
524 template <class _InputIterator>
Louis Dionned2322c82018-11-01 14:41:37 +0000525 _LIBCPP_INLINE_VISIBILITY
Marshall Clow631788a2013-09-11 00:06:45 +0000526 set(_InputIterator __f, _InputIterator __l, const allocator_type& __a)
527 : set(__f, __l, key_compare(), __a) {}
528#endif
529
Howard Hinnant192cf032010-09-23 16:27:36 +0000530 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000531 set(const set& __s)
532 : __tree_(__s.__tree_)
533 {
534 insert(__s.begin(), __s.end());
535 }
536
Howard Hinnantd3a657f2011-07-01 19:24:36 +0000537 _LIBCPP_INLINE_VISIBILITY
538 set& operator=(const set& __s)
539 {
540 __tree_ = __s.__tree_;
541 return *this;
542 }
543
Eric Fiselier615961b2017-04-18 20:58:03 +0000544#ifndef _LIBCPP_CXX03_LANG
Howard Hinnant192cf032010-09-23 16:27:36 +0000545 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000546 set(set&& __s)
Howard Hinnantf95f4f52011-06-04 15:22:34 +0000547 _NOEXCEPT_(is_nothrow_move_constructible<__base>::value)
Howard Hinnantb1ad5a82011-06-30 21:18:19 +0000548 : __tree_(_VSTD::move(__s.__tree_)) {}
Eric Fiselier615961b2017-04-18 20:58:03 +0000549#endif // _LIBCPP_CXX03_LANG
Howard Hinnantc51e1022010-05-11 19:42:16 +0000550
Howard Hinnant192cf032010-09-23 16:27:36 +0000551 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000552 explicit set(const allocator_type& __a)
553 : __tree_(__a) {}
554
Howard Hinnant192cf032010-09-23 16:27:36 +0000555 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000556 set(const set& __s, const allocator_type& __a)
557 : __tree_(__s.__tree_.value_comp(), __a)
558 {
559 insert(__s.begin(), __s.end());
560 }
561
Eric Fiselier615961b2017-04-18 20:58:03 +0000562#ifndef _LIBCPP_CXX03_LANG
Howard Hinnantc51e1022010-05-11 19:42:16 +0000563 set(set&& __s, const allocator_type& __a);
Howard Hinnantc51e1022010-05-11 19:42:16 +0000564
Howard Hinnant192cf032010-09-23 16:27:36 +0000565 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000566 set(initializer_list<value_type> __il, const value_compare& __comp = value_compare())
567 : __tree_(__comp)
568 {
569 insert(__il.begin(), __il.end());
570 }
571
Howard Hinnant192cf032010-09-23 16:27:36 +0000572 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000573 set(initializer_list<value_type> __il, const value_compare& __comp,
574 const allocator_type& __a)
575 : __tree_(__comp, __a)
576 {
577 insert(__il.begin(), __il.end());
578 }
579
Marshall Clow631788a2013-09-11 00:06:45 +0000580#if _LIBCPP_STD_VER > 11
Louis Dionned2322c82018-11-01 14:41:37 +0000581 _LIBCPP_INLINE_VISIBILITY
Marshall Clow631788a2013-09-11 00:06:45 +0000582 set(initializer_list<value_type> __il, const allocator_type& __a)
583 : set(__il, key_compare(), __a) {}
584#endif
585
Howard Hinnant192cf032010-09-23 16:27:36 +0000586 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000587 set& operator=(initializer_list<value_type> __il)
588 {
589 __tree_.__assign_unique(__il.begin(), __il.end());
590 return *this;
591 }
592
Howard Hinnant192cf032010-09-23 16:27:36 +0000593 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000594 set& operator=(set&& __s)
Howard Hinnantf95f4f52011-06-04 15:22:34 +0000595 _NOEXCEPT_(is_nothrow_move_assignable<__base>::value)
Howard Hinnantc51e1022010-05-11 19:42:16 +0000596 {
Howard Hinnantb1ad5a82011-06-30 21:18:19 +0000597 __tree_ = _VSTD::move(__s.__tree_);
Howard Hinnantc51e1022010-05-11 19:42:16 +0000598 return *this;
599 }
Eric Fiselier615961b2017-04-18 20:58:03 +0000600#endif // _LIBCPP_CXX03_LANG
Howard Hinnantc51e1022010-05-11 19:42:16 +0000601
Howard Hinnant192cf032010-09-23 16:27:36 +0000602 _LIBCPP_INLINE_VISIBILITY
Louis Dionne69c42c02019-04-11 16:14:56 +0000603 ~set() {
604 static_assert(sizeof(__diagnose_non_const_comparator<_Key, _Compare>()), "");
605 }
606
607 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantf95f4f52011-06-04 15:22:34 +0000608 iterator begin() _NOEXCEPT {return __tree_.begin();}
Howard Hinnant192cf032010-09-23 16:27:36 +0000609 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantf95f4f52011-06-04 15:22:34 +0000610 const_iterator begin() const _NOEXCEPT {return __tree_.begin();}
Howard Hinnant192cf032010-09-23 16:27:36 +0000611 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantf95f4f52011-06-04 15:22:34 +0000612 iterator end() _NOEXCEPT {return __tree_.end();}
Howard Hinnant192cf032010-09-23 16:27:36 +0000613 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantf95f4f52011-06-04 15:22:34 +0000614 const_iterator end() const _NOEXCEPT {return __tree_.end();}
Howard Hinnantc51e1022010-05-11 19:42:16 +0000615
Howard Hinnant192cf032010-09-23 16:27:36 +0000616 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantf95f4f52011-06-04 15:22:34 +0000617 reverse_iterator rbegin() _NOEXCEPT
618 {return reverse_iterator(end());}
Howard Hinnant192cf032010-09-23 16:27:36 +0000619 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantf95f4f52011-06-04 15:22:34 +0000620 const_reverse_iterator rbegin() const _NOEXCEPT
621 {return const_reverse_iterator(end());}
Howard Hinnant192cf032010-09-23 16:27:36 +0000622 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantf95f4f52011-06-04 15:22:34 +0000623 reverse_iterator rend() _NOEXCEPT
624 {return reverse_iterator(begin());}
Howard Hinnant192cf032010-09-23 16:27:36 +0000625 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantf95f4f52011-06-04 15:22:34 +0000626 const_reverse_iterator rend() const _NOEXCEPT
627 {return const_reverse_iterator(begin());}
Howard Hinnantc51e1022010-05-11 19:42:16 +0000628
Howard Hinnant192cf032010-09-23 16:27:36 +0000629 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantf95f4f52011-06-04 15:22:34 +0000630 const_iterator cbegin() const _NOEXCEPT {return begin();}
Howard Hinnant192cf032010-09-23 16:27:36 +0000631 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantf95f4f52011-06-04 15:22:34 +0000632 const_iterator cend() const _NOEXCEPT {return end();}
Howard Hinnant192cf032010-09-23 16:27:36 +0000633 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantf95f4f52011-06-04 15:22:34 +0000634 const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();}
Howard Hinnant192cf032010-09-23 16:27:36 +0000635 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantf95f4f52011-06-04 15:22:34 +0000636 const_reverse_iterator crend() const _NOEXCEPT {return rend();}
Howard Hinnantc51e1022010-05-11 19:42:16 +0000637
Marshall Clow425f5752017-11-15 05:51:26 +0000638 _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantf95f4f52011-06-04 15:22:34 +0000639 bool empty() const _NOEXCEPT {return __tree_.size() == 0;}
Howard Hinnant192cf032010-09-23 16:27:36 +0000640 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantf95f4f52011-06-04 15:22:34 +0000641 size_type size() const _NOEXCEPT {return __tree_.size();}
Howard Hinnant192cf032010-09-23 16:27:36 +0000642 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantf95f4f52011-06-04 15:22:34 +0000643 size_type max_size() const _NOEXCEPT {return __tree_.max_size();}
Howard Hinnantc51e1022010-05-11 19:42:16 +0000644
645 // modifiers:
Eric Fiselier615961b2017-04-18 20:58:03 +0000646#ifndef _LIBCPP_CXX03_LANG
Howard Hinnantc51e1022010-05-11 19:42:16 +0000647 template <class... _Args>
Howard Hinnant192cf032010-09-23 16:27:36 +0000648 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000649 pair<iterator, bool> emplace(_Args&&... __args)
Howard Hinnantb1ad5a82011-06-30 21:18:19 +0000650 {return __tree_.__emplace_unique(_VSTD::forward<_Args>(__args)...);}
Howard Hinnantc51e1022010-05-11 19:42:16 +0000651 template <class... _Args>
Howard Hinnant192cf032010-09-23 16:27:36 +0000652 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000653 iterator emplace_hint(const_iterator __p, _Args&&... __args)
Howard Hinnantb1ad5a82011-06-30 21:18:19 +0000654 {return __tree_.__emplace_hint_unique(__p, _VSTD::forward<_Args>(__args)...);}
Eric Fiselier615961b2017-04-18 20:58:03 +0000655#endif // _LIBCPP_CXX03_LANG
656
Howard Hinnant192cf032010-09-23 16:27:36 +0000657 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000658 pair<iterator,bool> insert(const value_type& __v)
659 {return __tree_.__insert_unique(__v);}
Howard Hinnant192cf032010-09-23 16:27:36 +0000660 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000661 iterator insert(const_iterator __p, const value_type& __v)
662 {return __tree_.__insert_unique(__p, __v);}
Eric Fiselier615961b2017-04-18 20:58:03 +0000663
Howard Hinnantc51e1022010-05-11 19:42:16 +0000664 template <class _InputIterator>
Howard Hinnant192cf032010-09-23 16:27:36 +0000665 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000666 void insert(_InputIterator __f, _InputIterator __l)
667 {
668 for (const_iterator __e = cend(); __f != __l; ++__f)
669 __tree_.__insert_unique(__e, *__f);
670 }
671
Eric Fiselier615961b2017-04-18 20:58:03 +0000672#ifndef _LIBCPP_CXX03_LANG
673 _LIBCPP_INLINE_VISIBILITY
674 pair<iterator,bool> insert(value_type&& __v)
675 {return __tree_.__insert_unique(_VSTD::move(__v));}
676
677 _LIBCPP_INLINE_VISIBILITY
678 iterator insert(const_iterator __p, value_type&& __v)
679 {return __tree_.__insert_unique(__p, _VSTD::move(__v));}
680
Howard Hinnant192cf032010-09-23 16:27:36 +0000681 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000682 void insert(initializer_list<value_type> __il)
683 {insert(__il.begin(), __il.end());}
Eric Fiselier615961b2017-04-18 20:58:03 +0000684#endif // _LIBCPP_CXX03_LANG
Howard Hinnantc51e1022010-05-11 19:42:16 +0000685
Howard Hinnant192cf032010-09-23 16:27:36 +0000686 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000687 iterator erase(const_iterator __p) {return __tree_.erase(__p);}
Howard Hinnant192cf032010-09-23 16:27:36 +0000688 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000689 size_type erase(const key_type& __k)
690 {return __tree_.__erase_unique(__k);}
Howard Hinnant192cf032010-09-23 16:27:36 +0000691 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000692 iterator erase(const_iterator __f, const_iterator __l)
693 {return __tree_.erase(__f, __l);}
Howard Hinnant192cf032010-09-23 16:27:36 +0000694 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantf95f4f52011-06-04 15:22:34 +0000695 void clear() _NOEXCEPT {__tree_.clear();}
Howard Hinnantc51e1022010-05-11 19:42:16 +0000696
Erik Pilkingtonc37a3d82018-08-01 01:33:38 +0000697#if _LIBCPP_STD_VER > 14
698 _LIBCPP_INLINE_VISIBILITY
699 insert_return_type insert(node_type&& __nh)
700 {
701 _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(),
702 "node_type with incompatible allocator passed to set::insert()");
703 return __tree_.template __node_handle_insert_unique<
704 node_type, insert_return_type>(_VSTD::move(__nh));
705 }
706 _LIBCPP_INLINE_VISIBILITY
707 iterator insert(const_iterator __hint, node_type&& __nh)
708 {
709 _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(),
710 "node_type with incompatible allocator passed to set::insert()");
711 return __tree_.template __node_handle_insert_unique<node_type>(
712 __hint, _VSTD::move(__nh));
713 }
714 _LIBCPP_INLINE_VISIBILITY
715 node_type extract(key_type const& __key)
716 {
717 return __tree_.template __node_handle_extract<node_type>(__key);
718 }
719 _LIBCPP_INLINE_VISIBILITY
720 node_type extract(const_iterator __it)
721 {
722 return __tree_.template __node_handle_extract<node_type>(__it);
723 }
Louis Dionned2322c82018-11-01 14:41:37 +0000724 template <class _Compare2>
Erik Pilkington82a65ad2018-10-31 17:31:35 +0000725 _LIBCPP_INLINE_VISIBILITY
Louis Dionned2322c82018-11-01 14:41:37 +0000726 void merge(set<key_type, _Compare2, allocator_type>& __source)
Erik Pilkington82a65ad2018-10-31 17:31:35 +0000727 {
728 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
729 "merging container with incompatible allocator");
730 __tree_.__node_handle_merge_unique(__source.__tree_);
731 }
Louis Dionned2322c82018-11-01 14:41:37 +0000732 template <class _Compare2>
Erik Pilkington82a65ad2018-10-31 17:31:35 +0000733 _LIBCPP_INLINE_VISIBILITY
Louis Dionned2322c82018-11-01 14:41:37 +0000734 void merge(set<key_type, _Compare2, allocator_type>&& __source)
Erik Pilkington82a65ad2018-10-31 17:31:35 +0000735 {
736 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
737 "merging container with incompatible allocator");
738 __tree_.__node_handle_merge_unique(__source.__tree_);
739 }
Louis Dionned2322c82018-11-01 14:41:37 +0000740 template <class _Compare2>
Erik Pilkington82a65ad2018-10-31 17:31:35 +0000741 _LIBCPP_INLINE_VISIBILITY
Louis Dionned2322c82018-11-01 14:41:37 +0000742 void merge(multiset<key_type, _Compare2, allocator_type>& __source)
Erik Pilkington82a65ad2018-10-31 17:31:35 +0000743 {
744 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
745 "merging container with incompatible allocator");
746 __tree_.__node_handle_merge_unique(__source.__tree_);
747 }
Louis Dionned2322c82018-11-01 14:41:37 +0000748 template <class _Compare2>
Erik Pilkington82a65ad2018-10-31 17:31:35 +0000749 _LIBCPP_INLINE_VISIBILITY
Louis Dionned2322c82018-11-01 14:41:37 +0000750 void merge(multiset<key_type, _Compare2, allocator_type>&& __source)
Erik Pilkington82a65ad2018-10-31 17:31:35 +0000751 {
752 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
753 "merging container with incompatible allocator");
754 __tree_.__node_handle_merge_unique(__source.__tree_);
755 }
Erik Pilkingtonc37a3d82018-08-01 01:33:38 +0000756#endif
757
Howard Hinnant192cf032010-09-23 16:27:36 +0000758 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantf95f4f52011-06-04 15:22:34 +0000759 void swap(set& __s) _NOEXCEPT_(__is_nothrow_swappable<__base>::value)
760 {__tree_.swap(__s.__tree_);}
Howard Hinnantc51e1022010-05-11 19:42:16 +0000761
Howard Hinnant192cf032010-09-23 16:27:36 +0000762 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantf95f4f52011-06-04 15:22:34 +0000763 allocator_type get_allocator() const _NOEXCEPT {return __tree_.__alloc();}
Howard Hinnant192cf032010-09-23 16:27:36 +0000764 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000765 key_compare key_comp() const {return __tree_.value_comp();}
Howard Hinnant192cf032010-09-23 16:27:36 +0000766 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000767 value_compare value_comp() const {return __tree_.value_comp();}
768
769 // set operations:
Howard Hinnant192cf032010-09-23 16:27:36 +0000770 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000771 iterator find(const key_type& __k) {return __tree_.find(__k);}
Howard Hinnant192cf032010-09-23 16:27:36 +0000772 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000773 const_iterator find(const key_type& __k) const {return __tree_.find(__k);}
Marshall Clowc0152142013-08-13 01:11:06 +0000774#if _LIBCPP_STD_VER > 11
775 template <typename _K2>
776 _LIBCPP_INLINE_VISIBILITY
777 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
778 find(const _K2& __k) {return __tree_.find(__k);}
779 template <typename _K2>
780 _LIBCPP_INLINE_VISIBILITY
781 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
782 find(const _K2& __k) const {return __tree_.find(__k);}
783#endif
784
Howard Hinnant192cf032010-09-23 16:27:36 +0000785 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000786 size_type count(const key_type& __k) const
787 {return __tree_.__count_unique(__k);}
Marshall Clowe6a5f522014-08-24 23:54:16 +0000788#if _LIBCPP_STD_VER > 11
789 template <typename _K2>
790 _LIBCPP_INLINE_VISIBILITY
791 typename enable_if<__is_transparent<_Compare, _K2>::value,size_type>::type
Eric Fiseliera85c9e92018-02-10 02:53:47 +0000792 count(const _K2& __k) const {return __tree_.__count_multi(__k);}
Marshall Clowe6a5f522014-08-24 23:54:16 +0000793#endif
Zoe Carver3ffbab12019-07-16 03:21:01 +0000794
795#if _LIBCPP_STD_VER > 17
796 _LIBCPP_INLINE_VISIBILITY
797 bool contains(const key_type& __k) const {return find(__k) != end();}
798#endif // _LIBCPP_STD_VER > 17
799
Howard Hinnant192cf032010-09-23 16:27:36 +0000800 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000801 iterator lower_bound(const key_type& __k)
802 {return __tree_.lower_bound(__k);}
Howard Hinnant192cf032010-09-23 16:27:36 +0000803 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000804 const_iterator lower_bound(const key_type& __k) const
805 {return __tree_.lower_bound(__k);}
Marshall Clowc0152142013-08-13 01:11:06 +0000806#if _LIBCPP_STD_VER > 11
807 template <typename _K2>
808 _LIBCPP_INLINE_VISIBILITY
809 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
810 lower_bound(const _K2& __k) {return __tree_.lower_bound(__k);}
811
812 template <typename _K2>
813 _LIBCPP_INLINE_VISIBILITY
814 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
815 lower_bound(const _K2& __k) const {return __tree_.lower_bound(__k);}
816#endif
817
Howard Hinnant192cf032010-09-23 16:27:36 +0000818 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000819 iterator upper_bound(const key_type& __k)
820 {return __tree_.upper_bound(__k);}
Howard Hinnant192cf032010-09-23 16:27:36 +0000821 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000822 const_iterator upper_bound(const key_type& __k) const
823 {return __tree_.upper_bound(__k);}
Marshall Clowc0152142013-08-13 01:11:06 +0000824#if _LIBCPP_STD_VER > 11
825 template <typename _K2>
826 _LIBCPP_INLINE_VISIBILITY
827 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
828 upper_bound(const _K2& __k) {return __tree_.upper_bound(__k);}
829 template <typename _K2>
830 _LIBCPP_INLINE_VISIBILITY
831 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
832 upper_bound(const _K2& __k) const {return __tree_.upper_bound(__k);}
833#endif
834
Howard Hinnant192cf032010-09-23 16:27:36 +0000835 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000836 pair<iterator,iterator> equal_range(const key_type& __k)
837 {return __tree_.__equal_range_unique(__k);}
Howard Hinnant192cf032010-09-23 16:27:36 +0000838 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000839 pair<const_iterator,const_iterator> equal_range(const key_type& __k) const
840 {return __tree_.__equal_range_unique(__k);}
Marshall Clowc0152142013-08-13 01:11:06 +0000841#if _LIBCPP_STD_VER > 11
842 template <typename _K2>
843 _LIBCPP_INLINE_VISIBILITY
844 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<iterator,iterator>>::type
Eric Fiseliera85c9e92018-02-10 02:53:47 +0000845 equal_range(const _K2& __k) {return __tree_.__equal_range_multi(__k);}
Marshall Clowc0152142013-08-13 01:11:06 +0000846 template <typename _K2>
847 _LIBCPP_INLINE_VISIBILITY
848 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<const_iterator,const_iterator>>::type
Eric Fiseliera85c9e92018-02-10 02:53:47 +0000849 equal_range(const _K2& __k) const {return __tree_.__equal_range_multi(__k);}
Marshall Clowc0152142013-08-13 01:11:06 +0000850#endif
Howard Hinnantc51e1022010-05-11 19:42:16 +0000851};
852
Louis Dionne27ecc152019-06-11 18:21:08 +0000853#ifndef _LIBCPP_HAS_NO_DEDUCTION_GUIDES
854template<class _InputIterator,
855 class _Compare = less<typename iterator_traits<_InputIterator>::value_type>,
856 class _Allocator = allocator<typename iterator_traits<_InputIterator>::value_type>,
Louis Dionne6c7da9a2019-07-19 17:13:39 +0000857 class = _EnableIf<__is_allocator<_Allocator>::value, void>,
858 class = _EnableIf<!__is_allocator<_Compare>::value, void>>
Louis Dionne27ecc152019-06-11 18:21:08 +0000859set(_InputIterator, _InputIterator, _Compare = _Compare(), _Allocator = _Allocator())
860 -> set<typename iterator_traits<_InputIterator>::value_type, _Compare, _Allocator>;
861
862template<class _Key, class _Compare = less<_Key>,
863 class _Allocator = allocator<_Key>,
Louis Dionne6c7da9a2019-07-19 17:13:39 +0000864 class = _EnableIf<__is_allocator<_Allocator>::value, void>,
865 class = _EnableIf<!__is_allocator<_Compare>::value, void>>
Louis Dionne27ecc152019-06-11 18:21:08 +0000866set(initializer_list<_Key>, _Compare = _Compare(), _Allocator = _Allocator())
867 -> set<_Key, _Compare, _Allocator>;
868
869template<class _InputIterator, class _Allocator,
Louis Dionne6c7da9a2019-07-19 17:13:39 +0000870 class = _EnableIf<__is_allocator<_Allocator>::value, void>>
Louis Dionne27ecc152019-06-11 18:21:08 +0000871set(_InputIterator, _InputIterator, _Allocator)
872 -> set<typename iterator_traits<_InputIterator>::value_type,
873 less<typename iterator_traits<_InputIterator>::value_type>, _Allocator>;
874
875template<class _Key, class _Allocator,
Louis Dionne6c7da9a2019-07-19 17:13:39 +0000876 class = _EnableIf<__is_allocator<_Allocator>::value, void>>
Louis Dionne27ecc152019-06-11 18:21:08 +0000877set(initializer_list<_Key>, _Allocator)
878 -> set<_Key, less<_Key>, _Allocator>;
879#endif
880
Eric Fiselier615961b2017-04-18 20:58:03 +0000881#ifndef _LIBCPP_CXX03_LANG
Howard Hinnantc51e1022010-05-11 19:42:16 +0000882
883template <class _Key, class _Compare, class _Allocator>
884set<_Key, _Compare, _Allocator>::set(set&& __s, const allocator_type& __a)
Howard Hinnantb1ad5a82011-06-30 21:18:19 +0000885 : __tree_(_VSTD::move(__s.__tree_), __a)
Howard Hinnantc51e1022010-05-11 19:42:16 +0000886{
887 if (__a != __s.get_allocator())
888 {
889 const_iterator __e = cend();
890 while (!__s.empty())
Howard Hinnantb1ad5a82011-06-30 21:18:19 +0000891 insert(__e, _VSTD::move(__s.__tree_.remove(__s.begin())->__value_));
Howard Hinnantc51e1022010-05-11 19:42:16 +0000892 }
893}
894
Eric Fiselier615961b2017-04-18 20:58:03 +0000895#endif // _LIBCPP_CXX03_LANG
Howard Hinnantc51e1022010-05-11 19:42:16 +0000896
897template <class _Key, class _Compare, class _Allocator>
Howard Hinnant192cf032010-09-23 16:27:36 +0000898inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000899bool
900operator==(const set<_Key, _Compare, _Allocator>& __x,
901 const set<_Key, _Compare, _Allocator>& __y)
902{
Howard Hinnantb1ad5a82011-06-30 21:18:19 +0000903 return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin());
Howard Hinnantc51e1022010-05-11 19:42:16 +0000904}
905
906template <class _Key, class _Compare, class _Allocator>
Howard Hinnant192cf032010-09-23 16:27:36 +0000907inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000908bool
909operator< (const set<_Key, _Compare, _Allocator>& __x,
910 const set<_Key, _Compare, _Allocator>& __y)
911{
Howard Hinnantb1ad5a82011-06-30 21:18:19 +0000912 return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
Howard Hinnantc51e1022010-05-11 19:42:16 +0000913}
914
915template <class _Key, class _Compare, class _Allocator>
Howard Hinnant192cf032010-09-23 16:27:36 +0000916inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000917bool
918operator!=(const set<_Key, _Compare, _Allocator>& __x,
919 const set<_Key, _Compare, _Allocator>& __y)
920{
921 return !(__x == __y);
922}
923
924template <class _Key, class _Compare, class _Allocator>
Howard Hinnant192cf032010-09-23 16:27:36 +0000925inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000926bool
927operator> (const set<_Key, _Compare, _Allocator>& __x,
928 const set<_Key, _Compare, _Allocator>& __y)
929{
930 return __y < __x;
931}
932
933template <class _Key, class _Compare, class _Allocator>
Howard Hinnant192cf032010-09-23 16:27:36 +0000934inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000935bool
936operator>=(const set<_Key, _Compare, _Allocator>& __x,
937 const set<_Key, _Compare, _Allocator>& __y)
938{
939 return !(__x < __y);
940}
941
942template <class _Key, class _Compare, class _Allocator>
Howard Hinnant192cf032010-09-23 16:27:36 +0000943inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000944bool
945operator<=(const set<_Key, _Compare, _Allocator>& __x,
946 const set<_Key, _Compare, _Allocator>& __y)
947{
948 return !(__y < __x);
949}
950
951// specialized algorithms:
952template <class _Key, class _Compare, class _Allocator>
Howard Hinnant192cf032010-09-23 16:27:36 +0000953inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000954void
955swap(set<_Key, _Compare, _Allocator>& __x,
956 set<_Key, _Compare, _Allocator>& __y)
Howard Hinnantf95f4f52011-06-04 15:22:34 +0000957 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
Howard Hinnantc51e1022010-05-11 19:42:16 +0000958{
959 __x.swap(__y);
960}
961
Marshall Clow29b53f22018-12-14 18:49:35 +0000962#if _LIBCPP_STD_VER > 17
963template <class _Key, class _Compare, class _Allocator, class _Predicate>
964inline _LIBCPP_INLINE_VISIBILITY
Marek Kurdeja98b1412020-05-02 13:58:03 +0200965 typename set<_Key, _Compare, _Allocator>::size_type
966 erase_if(set<_Key, _Compare, _Allocator>& __c, _Predicate __pred) {
967 return __libcpp_erase_if_container(__c, __pred);
968}
Marshall Clow29b53f22018-12-14 18:49:35 +0000969#endif
970
Howard Hinnantc51e1022010-05-11 19:42:16 +0000971template <class _Key, class _Compare = less<_Key>,
972 class _Allocator = allocator<_Key> >
Eric Fiselierb5eb1bf2017-01-04 23:56:00 +0000973class _LIBCPP_TEMPLATE_VIS multiset
Howard Hinnantc51e1022010-05-11 19:42:16 +0000974{
975public:
976 // types:
Arthur O'Dwyer6a752e12021-03-03 11:10:49 -0500977 typedef _Key key_type;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000978 typedef key_type value_type;
Arthur O'Dwyer6a752e12021-03-03 11:10:49 -0500979 typedef _Compare key_compare;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000980 typedef key_compare value_compare;
Arthur O'Dwyer6a752e12021-03-03 11:10:49 -0500981 typedef __identity_t<_Allocator> allocator_type;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000982 typedef value_type& reference;
983 typedef const value_type& const_reference;
984
Marshall Clow5128cf32015-11-26 01:24:04 +0000985 static_assert((is_same<typename allocator_type::value_type, value_type>::value),
986 "Allocator::value_type must be same type as value_type");
987
Howard Hinnantc51e1022010-05-11 19:42:16 +0000988private:
989 typedef __tree<value_type, value_compare, allocator_type> __base;
990 typedef allocator_traits<allocator_type> __alloc_traits;
991 typedef typename __base::__node_holder __node_holder;
992
993 __base __tree_;
994
995public:
996 typedef typename __base::pointer pointer;
997 typedef typename __base::const_pointer const_pointer;
998 typedef typename __base::size_type size_type;
999 typedef typename __base::difference_type difference_type;
1000 typedef typename __base::const_iterator iterator;
1001 typedef typename __base::const_iterator const_iterator;
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001002 typedef _VSTD::reverse_iterator<iterator> reverse_iterator;
1003 typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator;
Howard Hinnantc51e1022010-05-11 19:42:16 +00001004
Erik Pilkingtonc37a3d82018-08-01 01:33:38 +00001005#if _LIBCPP_STD_VER > 14
1006 typedef __set_node_handle<typename __base::__node, allocator_type> node_type;
1007#endif
1008
Erik Pilkington82a65ad2018-10-31 17:31:35 +00001009 template <class _Key2, class _Compare2, class _Alloc2>
1010 friend class _LIBCPP_TEMPLATE_VIS set;
1011 template <class _Key2, class _Compare2, class _Alloc2>
1012 friend class _LIBCPP_TEMPLATE_VIS multiset;
1013
Howard Hinnantc51e1022010-05-11 19:42:16 +00001014 // construct/copy/destroy:
Howard Hinnant192cf032010-09-23 16:27:36 +00001015 _LIBCPP_INLINE_VISIBILITY
Marshall Clow7086a5a2014-03-10 04:50:10 +00001016 multiset()
1017 _NOEXCEPT_(
1018 is_nothrow_default_constructible<allocator_type>::value &&
1019 is_nothrow_default_constructible<key_compare>::value &&
1020 is_nothrow_copy_constructible<key_compare>::value)
1021 : __tree_(value_compare()) {}
1022
1023 _LIBCPP_INLINE_VISIBILITY
1024 explicit multiset(const value_compare& __comp)
Howard Hinnantf95f4f52011-06-04 15:22:34 +00001025 _NOEXCEPT_(
1026 is_nothrow_default_constructible<allocator_type>::value &&
Howard Hinnantf95f4f52011-06-04 15:22:34 +00001027 is_nothrow_copy_constructible<key_compare>::value)
Howard Hinnantc51e1022010-05-11 19:42:16 +00001028 : __tree_(__comp) {}
Marshall Clow7086a5a2014-03-10 04:50:10 +00001029
Howard Hinnant192cf032010-09-23 16:27:36 +00001030 _LIBCPP_INLINE_VISIBILITY
Marshall Clow7ed23a72014-03-05 19:06:20 +00001031 explicit multiset(const value_compare& __comp, const allocator_type& __a)
Howard Hinnantc51e1022010-05-11 19:42:16 +00001032 : __tree_(__comp, __a) {}
1033 template <class _InputIterator>
Howard Hinnant192cf032010-09-23 16:27:36 +00001034 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001035 multiset(_InputIterator __f, _InputIterator __l,
1036 const value_compare& __comp = value_compare())
1037 : __tree_(__comp)
1038 {
1039 insert(__f, __l);
1040 }
1041
Marshall Clow631788a2013-09-11 00:06:45 +00001042#if _LIBCPP_STD_VER > 11
1043 template <class _InputIterator>
Louis Dionned2322c82018-11-01 14:41:37 +00001044 _LIBCPP_INLINE_VISIBILITY
Marshall Clow631788a2013-09-11 00:06:45 +00001045 multiset(_InputIterator __f, _InputIterator __l, const allocator_type& __a)
1046 : multiset(__f, __l, key_compare(), __a) {}
1047#endif
1048
Howard Hinnantc51e1022010-05-11 19:42:16 +00001049 template <class _InputIterator>
Howard Hinnant192cf032010-09-23 16:27:36 +00001050 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001051 multiset(_InputIterator __f, _InputIterator __l,
1052 const value_compare& __comp, const allocator_type& __a)
1053 : __tree_(__comp, __a)
1054 {
1055 insert(__f, __l);
1056 }
1057
Howard Hinnant192cf032010-09-23 16:27:36 +00001058 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001059 multiset(const multiset& __s)
1060 : __tree_(__s.__tree_.value_comp(),
1061 __alloc_traits::select_on_container_copy_construction(__s.__tree_.__alloc()))
1062 {
1063 insert(__s.begin(), __s.end());
1064 }
1065
Howard Hinnantd3a657f2011-07-01 19:24:36 +00001066 _LIBCPP_INLINE_VISIBILITY
1067 multiset& operator=(const multiset& __s)
1068 {
1069 __tree_ = __s.__tree_;
1070 return *this;
1071 }
1072
Eric Fiselier615961b2017-04-18 20:58:03 +00001073#ifndef _LIBCPP_CXX03_LANG
Howard Hinnant192cf032010-09-23 16:27:36 +00001074 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001075 multiset(multiset&& __s)
Howard Hinnantf95f4f52011-06-04 15:22:34 +00001076 _NOEXCEPT_(is_nothrow_move_constructible<__base>::value)
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001077 : __tree_(_VSTD::move(__s.__tree_)) {}
Eric Fiselier615961b2017-04-18 20:58:03 +00001078
1079 multiset(multiset&& __s, const allocator_type& __a);
1080#endif // _LIBCPP_CXX03_LANG
Howard Hinnant192cf032010-09-23 16:27:36 +00001081 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001082 explicit multiset(const allocator_type& __a)
1083 : __tree_(__a) {}
Howard Hinnant192cf032010-09-23 16:27:36 +00001084 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001085 multiset(const multiset& __s, const allocator_type& __a)
1086 : __tree_(__s.__tree_.value_comp(), __a)
1087 {
1088 insert(__s.begin(), __s.end());
1089 }
Howard Hinnantc51e1022010-05-11 19:42:16 +00001090
Eric Fiselier615961b2017-04-18 20:58:03 +00001091#ifndef _LIBCPP_CXX03_LANG
Howard Hinnant192cf032010-09-23 16:27:36 +00001092 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001093 multiset(initializer_list<value_type> __il, const value_compare& __comp = value_compare())
1094 : __tree_(__comp)
1095 {
1096 insert(__il.begin(), __il.end());
1097 }
1098
Howard Hinnant192cf032010-09-23 16:27:36 +00001099 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001100 multiset(initializer_list<value_type> __il, const value_compare& __comp,
1101 const allocator_type& __a)
1102 : __tree_(__comp, __a)
1103 {
1104 insert(__il.begin(), __il.end());
1105 }
1106
Marshall Clow631788a2013-09-11 00:06:45 +00001107#if _LIBCPP_STD_VER > 11
Louis Dionned2322c82018-11-01 14:41:37 +00001108 _LIBCPP_INLINE_VISIBILITY
Marshall Clow631788a2013-09-11 00:06:45 +00001109 multiset(initializer_list<value_type> __il, const allocator_type& __a)
1110 : multiset(__il, key_compare(), __a) {}
1111#endif
1112
Howard Hinnant192cf032010-09-23 16:27:36 +00001113 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001114 multiset& operator=(initializer_list<value_type> __il)
1115 {
1116 __tree_.__assign_multi(__il.begin(), __il.end());
1117 return *this;
1118 }
1119
Howard Hinnant192cf032010-09-23 16:27:36 +00001120 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001121 multiset& operator=(multiset&& __s)
Howard Hinnantf95f4f52011-06-04 15:22:34 +00001122 _NOEXCEPT_(is_nothrow_move_assignable<__base>::value)
Howard Hinnantc51e1022010-05-11 19:42:16 +00001123 {
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001124 __tree_ = _VSTD::move(__s.__tree_);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001125 return *this;
1126 }
Eric Fiselier615961b2017-04-18 20:58:03 +00001127#endif // _LIBCPP_CXX03_LANG
Howard Hinnantc51e1022010-05-11 19:42:16 +00001128
Howard Hinnant192cf032010-09-23 16:27:36 +00001129 _LIBCPP_INLINE_VISIBILITY
Louis Dionne69c42c02019-04-11 16:14:56 +00001130 ~multiset() {
1131 static_assert(sizeof(__diagnose_non_const_comparator<_Key, _Compare>()), "");
1132 }
1133
1134 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantf95f4f52011-06-04 15:22:34 +00001135 iterator begin() _NOEXCEPT {return __tree_.begin();}
Howard Hinnant192cf032010-09-23 16:27:36 +00001136 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantf95f4f52011-06-04 15:22:34 +00001137 const_iterator begin() const _NOEXCEPT {return __tree_.begin();}
Howard Hinnant192cf032010-09-23 16:27:36 +00001138 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantf95f4f52011-06-04 15:22:34 +00001139 iterator end() _NOEXCEPT {return __tree_.end();}
Howard Hinnant192cf032010-09-23 16:27:36 +00001140 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantf95f4f52011-06-04 15:22:34 +00001141 const_iterator end() const _NOEXCEPT {return __tree_.end();}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001142
Howard Hinnant192cf032010-09-23 16:27:36 +00001143 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantf95f4f52011-06-04 15:22:34 +00001144 reverse_iterator rbegin() _NOEXCEPT
1145 {return reverse_iterator(end());}
Howard Hinnant192cf032010-09-23 16:27:36 +00001146 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantf95f4f52011-06-04 15:22:34 +00001147 const_reverse_iterator rbegin() const _NOEXCEPT
1148 {return const_reverse_iterator(end());}
Howard Hinnant192cf032010-09-23 16:27:36 +00001149 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantf95f4f52011-06-04 15:22:34 +00001150 reverse_iterator rend() _NOEXCEPT
1151 {return reverse_iterator(begin());}
Howard Hinnant192cf032010-09-23 16:27:36 +00001152 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantf95f4f52011-06-04 15:22:34 +00001153 const_reverse_iterator rend() const _NOEXCEPT
1154 {return const_reverse_iterator(begin());}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001155
Howard Hinnant192cf032010-09-23 16:27:36 +00001156 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantf95f4f52011-06-04 15:22:34 +00001157 const_iterator cbegin() const _NOEXCEPT {return begin();}
Howard Hinnant192cf032010-09-23 16:27:36 +00001158 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantf95f4f52011-06-04 15:22:34 +00001159 const_iterator cend() const _NOEXCEPT {return end();}
Howard Hinnant192cf032010-09-23 16:27:36 +00001160 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantf95f4f52011-06-04 15:22:34 +00001161 const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();}
Howard Hinnant192cf032010-09-23 16:27:36 +00001162 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantf95f4f52011-06-04 15:22:34 +00001163 const_reverse_iterator crend() const _NOEXCEPT {return rend();}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001164
Marshall Clow425f5752017-11-15 05:51:26 +00001165 _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantf95f4f52011-06-04 15:22:34 +00001166 bool empty() const _NOEXCEPT {return __tree_.size() == 0;}
Howard Hinnant192cf032010-09-23 16:27:36 +00001167 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantf95f4f52011-06-04 15:22:34 +00001168 size_type size() const _NOEXCEPT {return __tree_.size();}
Howard Hinnant192cf032010-09-23 16:27:36 +00001169 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantf95f4f52011-06-04 15:22:34 +00001170 size_type max_size() const _NOEXCEPT {return __tree_.max_size();}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001171
1172 // modifiers:
Eric Fiselier615961b2017-04-18 20:58:03 +00001173#ifndef _LIBCPP_CXX03_LANG
Howard Hinnantc51e1022010-05-11 19:42:16 +00001174 template <class... _Args>
Howard Hinnant192cf032010-09-23 16:27:36 +00001175 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001176 iterator emplace(_Args&&... __args)
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001177 {return __tree_.__emplace_multi(_VSTD::forward<_Args>(__args)...);}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001178 template <class... _Args>
Howard Hinnant192cf032010-09-23 16:27:36 +00001179 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001180 iterator emplace_hint(const_iterator __p, _Args&&... __args)
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001181 {return __tree_.__emplace_hint_multi(__p, _VSTD::forward<_Args>(__args)...);}
Eric Fiselier615961b2017-04-18 20:58:03 +00001182#endif // _LIBCPP_CXX03_LANG
1183
Howard Hinnant192cf032010-09-23 16:27:36 +00001184 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001185 iterator insert(const value_type& __v)
1186 {return __tree_.__insert_multi(__v);}
Howard Hinnant192cf032010-09-23 16:27:36 +00001187 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001188 iterator insert(const_iterator __p, const value_type& __v)
1189 {return __tree_.__insert_multi(__p, __v);}
Eric Fiselier615961b2017-04-18 20:58:03 +00001190
Howard Hinnantc51e1022010-05-11 19:42:16 +00001191 template <class _InputIterator>
Howard Hinnant192cf032010-09-23 16:27:36 +00001192 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001193 void insert(_InputIterator __f, _InputIterator __l)
1194 {
1195 for (const_iterator __e = cend(); __f != __l; ++__f)
1196 __tree_.__insert_multi(__e, *__f);
1197 }
1198
Eric Fiselier615961b2017-04-18 20:58:03 +00001199#ifndef _LIBCPP_CXX03_LANG
1200 _LIBCPP_INLINE_VISIBILITY
1201 iterator insert(value_type&& __v)
1202 {return __tree_.__insert_multi(_VSTD::move(__v));}
1203
1204 _LIBCPP_INLINE_VISIBILITY
1205 iterator insert(const_iterator __p, value_type&& __v)
1206 {return __tree_.__insert_multi(__p, _VSTD::move(__v));}
1207
Howard Hinnant192cf032010-09-23 16:27:36 +00001208 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001209 void insert(initializer_list<value_type> __il)
1210 {insert(__il.begin(), __il.end());}
Eric Fiselier615961b2017-04-18 20:58:03 +00001211#endif // _LIBCPP_CXX03_LANG
Howard Hinnantc51e1022010-05-11 19:42:16 +00001212
Howard Hinnant192cf032010-09-23 16:27:36 +00001213 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001214 iterator erase(const_iterator __p) {return __tree_.erase(__p);}
Howard Hinnant192cf032010-09-23 16:27:36 +00001215 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001216 size_type erase(const key_type& __k) {return __tree_.__erase_multi(__k);}
Howard Hinnant192cf032010-09-23 16:27:36 +00001217 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001218 iterator erase(const_iterator __f, const_iterator __l)
1219 {return __tree_.erase(__f, __l);}
Howard Hinnant192cf032010-09-23 16:27:36 +00001220 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantf95f4f52011-06-04 15:22:34 +00001221 void clear() _NOEXCEPT {__tree_.clear();}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001222
Erik Pilkingtonc37a3d82018-08-01 01:33:38 +00001223#if _LIBCPP_STD_VER > 14
1224 _LIBCPP_INLINE_VISIBILITY
1225 iterator insert(node_type&& __nh)
1226 {
1227 _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(),
1228 "node_type with incompatible allocator passed to multiset::insert()");
1229 return __tree_.template __node_handle_insert_multi<node_type>(
1230 _VSTD::move(__nh));
1231 }
1232 _LIBCPP_INLINE_VISIBILITY
1233 iterator insert(const_iterator __hint, node_type&& __nh)
1234 {
1235 _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(),
1236 "node_type with incompatible allocator passed to multiset::insert()");
1237 return __tree_.template __node_handle_insert_multi<node_type>(
1238 __hint, _VSTD::move(__nh));
1239 }
1240 _LIBCPP_INLINE_VISIBILITY
1241 node_type extract(key_type const& __key)
1242 {
1243 return __tree_.template __node_handle_extract<node_type>(__key);
1244 }
1245 _LIBCPP_INLINE_VISIBILITY
1246 node_type extract(const_iterator __it)
1247 {
1248 return __tree_.template __node_handle_extract<node_type>(__it);
1249 }
Louis Dionned2322c82018-11-01 14:41:37 +00001250 template <class _Compare2>
Erik Pilkington82a65ad2018-10-31 17:31:35 +00001251 _LIBCPP_INLINE_VISIBILITY
Louis Dionned2322c82018-11-01 14:41:37 +00001252 void merge(multiset<key_type, _Compare2, allocator_type>& __source)
Erik Pilkington82a65ad2018-10-31 17:31:35 +00001253 {
1254 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
1255 "merging container with incompatible allocator");
1256 __tree_.__node_handle_merge_multi(__source.__tree_);
1257 }
Louis Dionned2322c82018-11-01 14:41:37 +00001258 template <class _Compare2>
Erik Pilkington82a65ad2018-10-31 17:31:35 +00001259 _LIBCPP_INLINE_VISIBILITY
Louis Dionned2322c82018-11-01 14:41:37 +00001260 void merge(multiset<key_type, _Compare2, allocator_type>&& __source)
Erik Pilkington82a65ad2018-10-31 17:31:35 +00001261 {
1262 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
1263 "merging container with incompatible allocator");
1264 __tree_.__node_handle_merge_multi(__source.__tree_);
1265 }
Louis Dionned2322c82018-11-01 14:41:37 +00001266 template <class _Compare2>
Erik Pilkington82a65ad2018-10-31 17:31:35 +00001267 _LIBCPP_INLINE_VISIBILITY
Louis Dionned2322c82018-11-01 14:41:37 +00001268 void merge(set<key_type, _Compare2, allocator_type>& __source)
Erik Pilkington82a65ad2018-10-31 17:31:35 +00001269 {
1270 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
1271 "merging container with incompatible allocator");
1272 __tree_.__node_handle_merge_multi(__source.__tree_);
1273 }
Louis Dionned2322c82018-11-01 14:41:37 +00001274 template <class _Compare2>
Erik Pilkington82a65ad2018-10-31 17:31:35 +00001275 _LIBCPP_INLINE_VISIBILITY
Louis Dionned2322c82018-11-01 14:41:37 +00001276 void merge(set<key_type, _Compare2, allocator_type>&& __source)
Erik Pilkington82a65ad2018-10-31 17:31:35 +00001277 {
1278 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
1279 "merging container with incompatible allocator");
1280 __tree_.__node_handle_merge_multi(__source.__tree_);
1281 }
Erik Pilkingtonc37a3d82018-08-01 01:33:38 +00001282#endif
1283
Howard Hinnant192cf032010-09-23 16:27:36 +00001284 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantf95f4f52011-06-04 15:22:34 +00001285 void swap(multiset& __s)
1286 _NOEXCEPT_(__is_nothrow_swappable<__base>::value)
1287 {__tree_.swap(__s.__tree_);}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001288
Howard Hinnant192cf032010-09-23 16:27:36 +00001289 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantf95f4f52011-06-04 15:22:34 +00001290 allocator_type get_allocator() const _NOEXCEPT {return __tree_.__alloc();}
Howard Hinnant192cf032010-09-23 16:27:36 +00001291 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001292 key_compare key_comp() const {return __tree_.value_comp();}
Howard Hinnant192cf032010-09-23 16:27:36 +00001293 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001294 value_compare value_comp() const {return __tree_.value_comp();}
1295
1296 // set operations:
Howard Hinnant192cf032010-09-23 16:27:36 +00001297 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001298 iterator find(const key_type& __k) {return __tree_.find(__k);}
Howard Hinnant192cf032010-09-23 16:27:36 +00001299 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001300 const_iterator find(const key_type& __k) const {return __tree_.find(__k);}
Marshall Clowc0152142013-08-13 01:11:06 +00001301#if _LIBCPP_STD_VER > 11
1302 template <typename _K2>
1303 _LIBCPP_INLINE_VISIBILITY
1304 typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,iterator>::type
1305 find(const _K2& __k) {return __tree_.find(__k);}
1306 template <typename _K2>
1307 _LIBCPP_INLINE_VISIBILITY
1308 typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,const_iterator>::type
1309 find(const _K2& __k) const {return __tree_.find(__k);}
1310#endif
1311
Howard Hinnant192cf032010-09-23 16:27:36 +00001312 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001313 size_type count(const key_type& __k) const
1314 {return __tree_.__count_multi(__k);}
Marshall Clowe6a5f522014-08-24 23:54:16 +00001315#if _LIBCPP_STD_VER > 11
1316 template <typename _K2>
1317 _LIBCPP_INLINE_VISIBILITY
1318 typename enable_if<__is_transparent<_Compare, _K2>::value,size_type>::type
Marshall Clow5571bcd2018-01-07 17:39:57 +00001319 count(const _K2& __k) const {return __tree_.__count_multi(__k);}
Marshall Clowe6a5f522014-08-24 23:54:16 +00001320#endif
Marshall Clowc0152142013-08-13 01:11:06 +00001321
Zoe Carver3ffbab12019-07-16 03:21:01 +00001322#if _LIBCPP_STD_VER > 17
1323 _LIBCPP_INLINE_VISIBILITY
1324 bool contains(const key_type& __k) const {return find(__k) != end();}
1325#endif // _LIBCPP_STD_VER > 17
1326
Howard Hinnant192cf032010-09-23 16:27:36 +00001327 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001328 iterator lower_bound(const key_type& __k)
1329 {return __tree_.lower_bound(__k);}
Howard Hinnant192cf032010-09-23 16:27:36 +00001330 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001331 const_iterator lower_bound(const key_type& __k) const
1332 {return __tree_.lower_bound(__k);}
Marshall Clowc0152142013-08-13 01:11:06 +00001333#if _LIBCPP_STD_VER > 11
1334 template <typename _K2>
1335 _LIBCPP_INLINE_VISIBILITY
1336 typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,iterator>::type
1337 lower_bound(const _K2& __k) {return __tree_.lower_bound(__k);}
1338
1339 template <typename _K2>
1340 _LIBCPP_INLINE_VISIBILITY
1341 typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,const_iterator>::type
1342 lower_bound(const _K2& __k) const {return __tree_.lower_bound(__k);}
1343#endif
1344
Howard Hinnant192cf032010-09-23 16:27:36 +00001345 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001346 iterator upper_bound(const key_type& __k)
1347 {return __tree_.upper_bound(__k);}
Howard Hinnant192cf032010-09-23 16:27:36 +00001348 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001349 const_iterator upper_bound(const key_type& __k) const
1350 {return __tree_.upper_bound(__k);}
Marshall Clowc0152142013-08-13 01:11:06 +00001351#if _LIBCPP_STD_VER > 11
1352 template <typename _K2>
1353 _LIBCPP_INLINE_VISIBILITY
1354 typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,iterator>::type
1355 upper_bound(const _K2& __k) {return __tree_.upper_bound(__k);}
1356 template <typename _K2>
1357 _LIBCPP_INLINE_VISIBILITY
1358 typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,const_iterator>::type
1359 upper_bound(const _K2& __k) const {return __tree_.upper_bound(__k);}
1360#endif
1361
Howard Hinnant192cf032010-09-23 16:27:36 +00001362 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001363 pair<iterator,iterator> equal_range(const key_type& __k)
1364 {return __tree_.__equal_range_multi(__k);}
Howard Hinnant192cf032010-09-23 16:27:36 +00001365 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001366 pair<const_iterator,const_iterator> equal_range(const key_type& __k) const
1367 {return __tree_.__equal_range_multi(__k);}
Marshall Clowc0152142013-08-13 01:11:06 +00001368#if _LIBCPP_STD_VER > 11
1369 template <typename _K2>
1370 _LIBCPP_INLINE_VISIBILITY
1371 typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,pair<iterator,iterator>>::type
1372 equal_range(const _K2& __k) {return __tree_.__equal_range_multi(__k);}
1373 template <typename _K2>
1374 _LIBCPP_INLINE_VISIBILITY
1375 typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,pair<const_iterator,const_iterator>>::type
1376 equal_range(const _K2& __k) const {return __tree_.__equal_range_multi(__k);}
1377#endif
Howard Hinnantc51e1022010-05-11 19:42:16 +00001378};
1379
Louis Dionne27ecc152019-06-11 18:21:08 +00001380#ifndef _LIBCPP_HAS_NO_DEDUCTION_GUIDES
1381template<class _InputIterator,
1382 class _Compare = less<typename iterator_traits<_InputIterator>::value_type>,
1383 class _Allocator = allocator<typename iterator_traits<_InputIterator>::value_type>,
Louis Dionne6c7da9a2019-07-19 17:13:39 +00001384 class = _EnableIf<__is_allocator<_Allocator>::value, void>,
1385 class = _EnableIf<!__is_allocator<_Compare>::value, void>>
Louis Dionne27ecc152019-06-11 18:21:08 +00001386multiset(_InputIterator, _InputIterator, _Compare = _Compare(), _Allocator = _Allocator())
1387 -> multiset<typename iterator_traits<_InputIterator>::value_type, _Compare, _Allocator>;
1388
1389template<class _Key, class _Compare = less<_Key>,
1390 class _Allocator = allocator<_Key>,
Louis Dionne6c7da9a2019-07-19 17:13:39 +00001391 class = _EnableIf<__is_allocator<_Allocator>::value, void>,
1392 class = _EnableIf<!__is_allocator<_Compare>::value, void>>
Louis Dionne27ecc152019-06-11 18:21:08 +00001393multiset(initializer_list<_Key>, _Compare = _Compare(), _Allocator = _Allocator())
1394 -> multiset<_Key, _Compare, _Allocator>;
1395
1396template<class _InputIterator, class _Allocator,
Louis Dionne6c7da9a2019-07-19 17:13:39 +00001397 class = _EnableIf<__is_allocator<_Allocator>::value, void>>
Louis Dionne27ecc152019-06-11 18:21:08 +00001398multiset(_InputIterator, _InputIterator, _Allocator)
1399 -> multiset<typename iterator_traits<_InputIterator>::value_type,
1400 less<typename iterator_traits<_InputIterator>::value_type>, _Allocator>;
1401
1402template<class _Key, class _Allocator,
Louis Dionne6c7da9a2019-07-19 17:13:39 +00001403 class = _EnableIf<__is_allocator<_Allocator>::value, void>>
Louis Dionne27ecc152019-06-11 18:21:08 +00001404multiset(initializer_list<_Key>, _Allocator)
1405 -> multiset<_Key, less<_Key>, _Allocator>;
1406#endif
1407
Eric Fiselier615961b2017-04-18 20:58:03 +00001408#ifndef _LIBCPP_CXX03_LANG
Howard Hinnantc51e1022010-05-11 19:42:16 +00001409
1410template <class _Key, class _Compare, class _Allocator>
1411multiset<_Key, _Compare, _Allocator>::multiset(multiset&& __s, const allocator_type& __a)
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001412 : __tree_(_VSTD::move(__s.__tree_), __a)
Howard Hinnantc51e1022010-05-11 19:42:16 +00001413{
1414 if (__a != __s.get_allocator())
1415 {
1416 const_iterator __e = cend();
1417 while (!__s.empty())
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001418 insert(__e, _VSTD::move(__s.__tree_.remove(__s.begin())->__value_));
Howard Hinnantc51e1022010-05-11 19:42:16 +00001419 }
1420}
1421
Eric Fiselier615961b2017-04-18 20:58:03 +00001422#endif // _LIBCPP_CXX03_LANG
Howard Hinnantc51e1022010-05-11 19:42:16 +00001423
1424template <class _Key, class _Compare, class _Allocator>
Howard Hinnant192cf032010-09-23 16:27:36 +00001425inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001426bool
1427operator==(const multiset<_Key, _Compare, _Allocator>& __x,
1428 const multiset<_Key, _Compare, _Allocator>& __y)
1429{
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001430 return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin());
Howard Hinnantc51e1022010-05-11 19:42:16 +00001431}
1432
1433template <class _Key, class _Compare, class _Allocator>
Howard Hinnant192cf032010-09-23 16:27:36 +00001434inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001435bool
1436operator< (const multiset<_Key, _Compare, _Allocator>& __x,
1437 const multiset<_Key, _Compare, _Allocator>& __y)
1438{
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001439 return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
Howard Hinnantc51e1022010-05-11 19:42:16 +00001440}
1441
1442template <class _Key, class _Compare, class _Allocator>
Howard Hinnant192cf032010-09-23 16:27:36 +00001443inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001444bool
1445operator!=(const multiset<_Key, _Compare, _Allocator>& __x,
1446 const multiset<_Key, _Compare, _Allocator>& __y)
1447{
1448 return !(__x == __y);
1449}
1450
1451template <class _Key, class _Compare, class _Allocator>
Howard Hinnant192cf032010-09-23 16:27:36 +00001452inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001453bool
1454operator> (const multiset<_Key, _Compare, _Allocator>& __x,
1455 const multiset<_Key, _Compare, _Allocator>& __y)
1456{
1457 return __y < __x;
1458}
1459
1460template <class _Key, class _Compare, class _Allocator>
Howard Hinnant192cf032010-09-23 16:27:36 +00001461inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001462bool
1463operator>=(const multiset<_Key, _Compare, _Allocator>& __x,
1464 const multiset<_Key, _Compare, _Allocator>& __y)
1465{
1466 return !(__x < __y);
1467}
1468
1469template <class _Key, class _Compare, class _Allocator>
Howard Hinnant192cf032010-09-23 16:27:36 +00001470inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001471bool
1472operator<=(const multiset<_Key, _Compare, _Allocator>& __x,
1473 const multiset<_Key, _Compare, _Allocator>& __y)
1474{
1475 return !(__y < __x);
1476}
1477
1478template <class _Key, class _Compare, class _Allocator>
Howard Hinnant192cf032010-09-23 16:27:36 +00001479inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001480void
1481swap(multiset<_Key, _Compare, _Allocator>& __x,
1482 multiset<_Key, _Compare, _Allocator>& __y)
Howard Hinnantf95f4f52011-06-04 15:22:34 +00001483 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
Howard Hinnantc51e1022010-05-11 19:42:16 +00001484{
1485 __x.swap(__y);
1486}
1487
Marshall Clow29b53f22018-12-14 18:49:35 +00001488#if _LIBCPP_STD_VER > 17
1489template <class _Key, class _Compare, class _Allocator, class _Predicate>
1490inline _LIBCPP_INLINE_VISIBILITY
Marek Kurdeja98b1412020-05-02 13:58:03 +02001491 typename multiset<_Key, _Compare, _Allocator>::size_type
1492 erase_if(multiset<_Key, _Compare, _Allocator>& __c, _Predicate __pred) {
1493 return __libcpp_erase_if_container(__c, __pred);
1494}
Marshall Clow29b53f22018-12-14 18:49:35 +00001495#endif
1496
Howard Hinnantc51e1022010-05-11 19:42:16 +00001497_LIBCPP_END_NAMESPACE_STD
1498
1499#endif // _LIBCPP_SET