1// -*- C++ -*-
2//===----------------------------------------------------------------------===//
3//
4// 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
7//
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;
42 typedef unspecified node_type; // C++17
43 typedef INSERT_RETURN_TYPE<iterator, node_type> insert_return_type; // C++17
44
45 // construct/copy/destroy:
46 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);
52 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);
60 set(set&& s)
61 noexcept(
62 is_nothrow_move_constructible<allocator_type>::value &&
63 is_nothrow_move_constructible<key_compare>::value);
64 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);
70 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
75 ~set();
76
77 set& operator=(const set& s);
78 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);
83 set& operator=(initializer_list<value_type> il);
84
85 // iterators:
86 iterator begin() noexcept;
87 const_iterator begin() const noexcept;
88 iterator end() noexcept;
89 const_iterator end() const noexcept;
90
91 reverse_iterator rbegin() noexcept;
92 const_reverse_iterator rbegin() const noexcept;
93 reverse_iterator rend() noexcept;
94 const_reverse_iterator rend() const noexcept;
95
96 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;
100
101 // capacity:
102 bool empty() const noexcept;
103 size_type size() const noexcept;
104 size_type max_size() const noexcept;
105
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
119 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
124 iterator erase(const_iterator position);
125 iterator erase(iterator position); // C++14
126 size_type erase(const key_type& k);
127 iterator erase(const_iterator first, const_iterator last);
128 void clear() noexcept;
129
130 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
139 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));
144
145 // observers:
146 allocator_type get_allocator() const noexcept;
147 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;
153 template<typename K>
154 iterator find(const K& x);
155 template<typename K>
156 const_iterator find(const K& x) const; // C++14
157
158 template<typename K>
159 size_type count(const K& x) const; // C++14
160 size_type count(const key_type& k) const;
161
162 bool contains(const key_type& x) const; // C++20
163 template<class K> bool contains(const K& x) const; // C++20
164
165 iterator lower_bound(const key_type& k);
166 const_iterator lower_bound(const key_type& k) const;
167 template<typename K>
168 iterator lower_bound(const K& x); // C++14
169 template<typename K>
170 const_iterator lower_bound(const K& x) const; // C++14
171
172 iterator upper_bound(const key_type& k);
173 const_iterator upper_bound(const key_type& k) const;
174 template<typename K>
175 iterator upper_bound(const K& x); // C++14
176 template<typename K>
177 const_iterator upper_bound(const K& x) const; // C++14
178 pair<iterator,iterator> equal_range(const key_type& k);
179 pair<const_iterator,const_iterator> equal_range(const key_type& k) const;
180 template<typename K>
181 pair<iterator,iterator> equal_range(const K& x); // C++14
182 template<typename K>
183 pair<const_iterator,const_iterator> equal_range(const K& x) const; // C++14
184};
185
186template <class InputIterator,
187 class Compare = less<typename iterator_traits<InputIterator>::value_type>,
188 class Allocator = allocator<typename iterator_traits<InputIterator>::value_type>>
189set(InputIterator, InputIterator,
190 Compare = Compare(), Allocator = Allocator())
191 -> set<typename iterator_traits<InputIterator>::value_type, Compare, Allocator>; // C++17
192
193template<class Key, class Compare = less<Key>, class Allocator = allocator<Key>>
194set(initializer_list<Key>, Compare = Compare(), Allocator = Allocator())
195 -> set<Key, Compare, Allocator>; // C++17
196
197template<class InputIterator, class Allocator>
198set(InputIterator, InputIterator, Allocator)
199 -> set<typename iterator_traits<InputIterator>::value_type,
200 less<typename iterator_traits<InputIterator>::value_type>, Allocator>; // C++17
201
202template<class Key, class Allocator>
203set(initializer_list<Key>, Allocator) -> set<Key, less<Key>, Allocator>; // C++17
204
205template <class Key, class Compare, class Allocator>
206bool
207operator==(const set<Key, Compare, Allocator>& x,
208 const set<Key, Compare, Allocator>& y);
209
210template <class Key, class Compare, class Allocator>
211bool
212operator< (const set<Key, Compare, Allocator>& x,
213 const set<Key, Compare, Allocator>& y);
214
215template <class Key, class Compare, class Allocator>
216bool
217operator!=(const set<Key, Compare, Allocator>& x,
218 const set<Key, Compare, Allocator>& y);
219
220template <class Key, class Compare, class Allocator>
221bool
222operator> (const set<Key, Compare, Allocator>& x,
223 const set<Key, Compare, Allocator>& y);
224
225template <class Key, class Compare, class Allocator>
226bool
227operator>=(const set<Key, Compare, Allocator>& x,
228 const set<Key, Compare, Allocator>& y);
229
230template <class Key, class Compare, class Allocator>
231bool
232operator<=(const set<Key, Compare, Allocator>& x,
233 const set<Key, Compare, Allocator>& y);
234
235// specialized algorithms:
236template <class Key, class Compare, class Allocator>
237void
238swap(set<Key, Compare, Allocator>& x, set<Key, Compare, Allocator>& y)
239 noexcept(noexcept(x.swap(y)));
240
241template <class Key, class Compare, class Allocator, class Predicate>
242typename set<Key, Compare, Allocator>::size_type
243erase_if(set<Key, Compare, Allocator>& c, Predicate pred); // C++20
244
245template <class Key, class Compare = less<Key>,
246 class Allocator = allocator<Key>>
247class multiset
248{
249public:
250 // types:
251 typedef Key key_type;
252 typedef key_type value_type;
253 typedef Compare key_compare;
254 typedef key_compare value_compare;
255 typedef Allocator allocator_type;
256 typedef typename allocator_type::reference reference;
257 typedef typename allocator_type::const_reference const_reference;
258 typedef typename allocator_type::size_type size_type;
259 typedef typename allocator_type::difference_type difference_type;
260 typedef typename allocator_type::pointer pointer;
261 typedef typename allocator_type::const_pointer const_pointer;
262
263 typedef implementation-defined iterator;
264 typedef implementation-defined const_iterator;
265 typedef std::reverse_iterator<iterator> reverse_iterator;
266 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
267 typedef unspecified node_type; // C++17
268
269 // construct/copy/destroy:
270 multiset()
271 noexcept(
272 is_nothrow_default_constructible<allocator_type>::value &&
273 is_nothrow_default_constructible<key_compare>::value &&
274 is_nothrow_copy_constructible<key_compare>::value);
275 explicit multiset(const value_compare& comp);
276 multiset(const value_compare& comp, const allocator_type& a);
277 template <class InputIterator>
278 multiset(InputIterator first, InputIterator last,
279 const value_compare& comp = value_compare());
280 template <class InputIterator>
281 multiset(InputIterator first, InputIterator last,
282 const value_compare& comp, const allocator_type& a);
283 multiset(const multiset& s);
284 multiset(multiset&& s)
285 noexcept(
286 is_nothrow_move_constructible<allocator_type>::value &&
287 is_nothrow_move_constructible<key_compare>::value);
288 explicit multiset(const allocator_type& a);
289 multiset(const multiset& s, const allocator_type& a);
290 multiset(multiset&& s, const allocator_type& a);
291 multiset(initializer_list<value_type> il, const value_compare& comp = value_compare());
292 multiset(initializer_list<value_type> il, const value_compare& comp,
293 const allocator_type& a);
294 template <class InputIterator>
295 multiset(InputIterator first, InputIterator last, const allocator_type& a)
296 : set(first, last, Compare(), a) {} // C++14
297 multiset(initializer_list<value_type> il, const allocator_type& a)
298 : set(il, Compare(), a) {} // C++14
299 ~multiset();
300
301 multiset& operator=(const multiset& s);
302 multiset& operator=(multiset&& s)
303 noexcept(
304 allocator_type::propagate_on_container_move_assignment::value &&
305 is_nothrow_move_assignable<allocator_type>::value &&
306 is_nothrow_move_assignable<key_compare>::value);
307 multiset& operator=(initializer_list<value_type> il);
308
309 // iterators:
310 iterator begin() noexcept;
311 const_iterator begin() const noexcept;
312 iterator end() noexcept;
313 const_iterator end() const noexcept;
314
315 reverse_iterator rbegin() noexcept;
316 const_reverse_iterator rbegin() const noexcept;
317 reverse_iterator rend() noexcept;
318 const_reverse_iterator rend() const noexcept;
319
320 const_iterator cbegin() const noexcept;
321 const_iterator cend() const noexcept;
322 const_reverse_iterator crbegin() const noexcept;
323 const_reverse_iterator crend() const noexcept;
324
325 // capacity:
326 bool empty() const noexcept;
327 size_type size() const noexcept;
328 size_type max_size() const noexcept;
329
330 // modifiers:
331 template <class... Args>
332 iterator emplace(Args&&... args);
333 template <class... Args>
334 iterator emplace_hint(const_iterator position, Args&&... args);
335 iterator insert(const value_type& v);
336 iterator insert(value_type&& v);
337 iterator insert(const_iterator position, const value_type& v);
338 iterator insert(const_iterator position, value_type&& v);
339 template <class InputIterator>
340 void insert(InputIterator first, InputIterator last);
341 void insert(initializer_list<value_type> il);
342
343 node_type extract(const_iterator position); // C++17
344 node_type extract(const key_type& x); // C++17
345 iterator insert(node_type&& nh); // C++17
346 iterator insert(const_iterator hint, node_type&& nh); // C++17
347
348 iterator erase(const_iterator position);
349 iterator erase(iterator position); // C++14
350 size_type erase(const key_type& k);
351 iterator erase(const_iterator first, const_iterator last);
352 void clear() noexcept;
353
354 template<class C2>
355 void merge(multiset<Key, C2, Allocator>& source); // C++17
356 template<class C2>
357 void merge(multiset<Key, C2, Allocator>&& source); // C++17
358 template<class C2>
359 void merge(set<Key, C2, Allocator>& source); // C++17
360 template<class C2>
361 void merge(set<Key, C2, Allocator>&& source); // C++17
362
363 void swap(multiset& s)
364 noexcept(
365 __is_nothrow_swappable<key_compare>::value &&
366 (!allocator_type::propagate_on_container_swap::value ||
367 __is_nothrow_swappable<allocator_type>::value));
368
369 // observers:
370 allocator_type get_allocator() const noexcept;
371 key_compare key_comp() const;
372 value_compare value_comp() const;
373
374 // set operations:
375 iterator find(const key_type& k);
376 const_iterator find(const key_type& k) const;
377 template<typename K>
378 iterator find(const K& x);
379 template<typename K>
380 const_iterator find(const K& x) const; // C++14
381
382 template<typename K>
383 size_type count(const K& x) const; // C++14
384 size_type count(const key_type& k) const;
385
386 bool contains(const key_type& x) const; // C++20
387 template<class K> bool contains(const K& x) const; // C++20
388
389 iterator lower_bound(const key_type& k);
390 const_iterator lower_bound(const key_type& k) const;
391 template<typename K>
392 iterator lower_bound(const K& x); // C++14
393 template<typename K>
394 const_iterator lower_bound(const K& x) const; // C++14
395
396 iterator upper_bound(const key_type& k);
397 const_iterator upper_bound(const key_type& k) const;
398 template<typename K>
399 iterator upper_bound(const K& x); // C++14
400 template<typename K>
401 const_iterator upper_bound(const K& x) const; // C++14
402
403 pair<iterator,iterator> equal_range(const key_type& k);
404 pair<const_iterator,const_iterator> equal_range(const key_type& k) const;
405 template<typename K>
406 pair<iterator,iterator> equal_range(const K& x); // C++14
407 template<typename K>
408 pair<const_iterator,const_iterator> equal_range(const K& x) const; // C++14
409};
410
411template <class InputIterator,
412 class Compare = less<typename iterator_traits<InputIterator>::value_type>,
413 class Allocator = allocator<typename iterator_traits<InputIterator>::value_type>>
414multiset(InputIterator, InputIterator,
415 Compare = Compare(), Allocator = Allocator())
416 -> multiset<typename iterator_traits<InputIterator>::value_type, Compare, Allocator>; // C++17
417
418template<class Key, class Compare = less<Key>, class Allocator = allocator<Key>>
419multiset(initializer_list<Key>, Compare = Compare(), Allocator = Allocator())
420 -> multiset<Key, Compare, Allocator>; // C++17
421
422template<class InputIterator, class Allocator>
423multiset(InputIterator, InputIterator, Allocator)
424 -> multiset<typename iterator_traits<InputIterator>::value_type,
425 less<typename iterator_traits<InputIterator>::value_type>, Allocator>; // C++17
426
427template<class Key, class Allocator>
428multiset(initializer_list<Key>, Allocator) -> multiset<Key, less<Key>, Allocator>; // C++17
429
430template <class Key, class Compare, class Allocator>
431bool
432operator==(const multiset<Key, Compare, Allocator>& x,
433 const multiset<Key, Compare, Allocator>& y);
434
435template <class Key, class Compare, class Allocator>
436bool
437operator< (const multiset<Key, Compare, Allocator>& x,
438 const multiset<Key, Compare, Allocator>& y);
439
440template <class Key, class Compare, class Allocator>
441bool
442operator!=(const multiset<Key, Compare, Allocator>& x,
443 const multiset<Key, Compare, Allocator>& y);
444
445template <class Key, class Compare, class Allocator>
446bool
447operator> (const multiset<Key, Compare, Allocator>& x,
448 const multiset<Key, Compare, Allocator>& y);
449
450template <class Key, class Compare, class Allocator>
451bool
452operator>=(const multiset<Key, Compare, Allocator>& x,
453 const multiset<Key, Compare, Allocator>& y);
454
455template <class Key, class Compare, class Allocator>
456bool
457operator<=(const multiset<Key, Compare, Allocator>& x,
458 const multiset<Key, Compare, Allocator>& y);
459
460// specialized algorithms:
461template <class Key, class Compare, class Allocator>
462void
463swap(multiset<Key, Compare, Allocator>& x, multiset<Key, Compare, Allocator>& y)
464 noexcept(noexcept(x.swap(y)));
465
466template <class Key, class Compare, class Allocator, class Predicate>
467typename multiset<Key, Compare, Allocator>::size_type
468erase_if(multiset<Key, Compare, Allocator>& c, Predicate pred); // C++20
469
470} // std
471
472*/
473
474#include <__algorithm/equal.h>
475#include <__algorithm/lexicographical_compare.h>
476#include <__assert> // all public C++ headers provide the assertion handler
477#include <__config>
478#include <__functional/is_transparent.h>
479#include <__functional/operations.h>
480#include <__iterator/erase_if_container.h>
481#include <__iterator/iterator_traits.h>
482#include <__iterator/reverse_iterator.h>
483#include <__node_handle>
484#include <__tree>
485#include <__utility/forward.h>
486#include <version>
487
488#ifndef _LIBCPP_REMOVE_TRANSITIVE_INCLUDES
489# include <functional>
490# include <iterator>
491#endif
492
493// standard-mandated includes
494
495// [iterator.range]
496#include <__iterator/access.h>
497#include <__iterator/data.h>
498#include <__iterator/empty.h>
499#include <__iterator/reverse_access.h>
500#include <__iterator/size.h>
501
502// [associative.set.syn]
503#include <compare>
504#include <initializer_list>
505
506#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
507# pragma GCC system_header
508#endif
509
510_LIBCPP_BEGIN_NAMESPACE_STD
511
512template <class _Key, class _Compare, class _Allocator>
513class multiset;
514
515template <class _Key, class _Compare = less<_Key>,
516 class _Allocator = allocator<_Key> >
517class _LIBCPP_TEMPLATE_VIS set
518{
519public:
520 // types:
521 typedef _Key key_type;
522 typedef key_type value_type;
523 typedef __type_identity_t<_Compare> key_compare;
524 typedef key_compare value_compare;
525 typedef __type_identity_t<_Allocator> allocator_type;
526 typedef value_type& reference;
527 typedef const value_type& const_reference;
528
529 static_assert((is_same<typename allocator_type::value_type, value_type>::value),
530 "Allocator::value_type must be same type as value_type");
531
532private:
533 typedef __tree<value_type, value_compare, allocator_type> __base;
534 typedef allocator_traits<allocator_type> __alloc_traits;
535
536 __base __tree_;
537
538public:
539 typedef typename __base::pointer pointer;
540 typedef typename __base::const_pointer const_pointer;
541 typedef typename __base::size_type size_type;
542 typedef typename __base::difference_type difference_type;
543 typedef typename __base::const_iterator iterator;
544 typedef typename __base::const_iterator const_iterator;
545 typedef _VSTD::reverse_iterator<iterator> reverse_iterator;
546 typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator;
547
548#if _LIBCPP_STD_VER > 14
549 typedef __set_node_handle<typename __base::__node, allocator_type> node_type;
550 typedef __insert_return_type<iterator, node_type> insert_return_type;
551#endif
552
553 template <class _Key2, class _Compare2, class _Alloc2>
554 friend class _LIBCPP_TEMPLATE_VIS set;
555 template <class _Key2, class _Compare2, class _Alloc2>
556 friend class _LIBCPP_TEMPLATE_VIS multiset;
557
558 _LIBCPP_INLINE_VISIBILITY
559 set()
560 _NOEXCEPT_(
561 is_nothrow_default_constructible<allocator_type>::value &&
562 is_nothrow_default_constructible<key_compare>::value &&
563 is_nothrow_copy_constructible<key_compare>::value)
564 : __tree_(value_compare()) {}
565
566 _LIBCPP_INLINE_VISIBILITY
567 explicit set(const value_compare& __comp)
568 _NOEXCEPT_(
569 is_nothrow_default_constructible<allocator_type>::value &&
570 is_nothrow_copy_constructible<key_compare>::value)
571 : __tree_(__comp) {}
572
573 _LIBCPP_INLINE_VISIBILITY
574 explicit set(const value_compare& __comp, const allocator_type& __a)
575 : __tree_(__comp, __a) {}
576 template <class _InputIterator>
577 _LIBCPP_INLINE_VISIBILITY
578 set(_InputIterator __f, _InputIterator __l,
579 const value_compare& __comp = value_compare())
580 : __tree_(__comp)
581 {
582 insert(__f, __l);
583 }
584
585 template <class _InputIterator>
586 _LIBCPP_INLINE_VISIBILITY
587 set(_InputIterator __f, _InputIterator __l, const value_compare& __comp,
588 const allocator_type& __a)
589 : __tree_(__comp, __a)
590 {
591 insert(__f, __l);
592 }
593
594#if _LIBCPP_STD_VER > 11
595 template <class _InputIterator>
596 _LIBCPP_INLINE_VISIBILITY
597 set(_InputIterator __f, _InputIterator __l, const allocator_type& __a)
598 : set(__f, __l, key_compare(), __a) {}
599#endif
600
601 _LIBCPP_INLINE_VISIBILITY
602 set(const set& __s)
603 : __tree_(__s.__tree_)
604 {
605 insert(__s.begin(), __s.end());
606 }
607
608 _LIBCPP_INLINE_VISIBILITY
609 set& operator=(const set& __s)
610 {
611 __tree_ = __s.__tree_;
612 return *this;
613 }
614
615#ifndef _LIBCPP_CXX03_LANG
616 _LIBCPP_INLINE_VISIBILITY
617 set(set&& __s)
618 _NOEXCEPT_(is_nothrow_move_constructible<__base>::value)
619 : __tree_(_VSTD::move(__s.__tree_)) {}
620#endif // _LIBCPP_CXX03_LANG
621
622 _LIBCPP_INLINE_VISIBILITY
623 explicit set(const allocator_type& __a)
624 : __tree_(__a) {}
625
626 _LIBCPP_INLINE_VISIBILITY
627 set(const set& __s, const allocator_type& __a)
628 : __tree_(__s.__tree_.value_comp(), __a)
629 {
630 insert(__s.begin(), __s.end());
631 }
632
633#ifndef _LIBCPP_CXX03_LANG
634 set(set&& __s, const allocator_type& __a);
635
636 _LIBCPP_INLINE_VISIBILITY
637 set(initializer_list<value_type> __il, const value_compare& __comp = value_compare())
638 : __tree_(__comp)
639 {
640 insert(__il.begin(), __il.end());
641 }
642
643 _LIBCPP_INLINE_VISIBILITY
644 set(initializer_list<value_type> __il, const value_compare& __comp,
645 const allocator_type& __a)
646 : __tree_(__comp, __a)
647 {
648 insert(__il.begin(), __il.end());
649 }
650
651#if _LIBCPP_STD_VER > 11
652 _LIBCPP_INLINE_VISIBILITY
653 set(initializer_list<value_type> __il, const allocator_type& __a)
654 : set(__il, key_compare(), __a) {}
655#endif
656
657 _LIBCPP_INLINE_VISIBILITY
658 set& operator=(initializer_list<value_type> __il)
659 {
660 __tree_.__assign_unique(__il.begin(), __il.end());
661 return *this;
662 }
663
664 _LIBCPP_INLINE_VISIBILITY
665 set& operator=(set&& __s)
666 _NOEXCEPT_(is_nothrow_move_assignable<__base>::value)
667 {
668 __tree_ = _VSTD::move(__s.__tree_);
669 return *this;
670 }
671#endif // _LIBCPP_CXX03_LANG
672
673 _LIBCPP_INLINE_VISIBILITY
674 ~set() {
675 static_assert(sizeof(__diagnose_non_const_comparator<_Key, _Compare>()), "");
676 }
677
678 _LIBCPP_INLINE_VISIBILITY
679 iterator begin() _NOEXCEPT {return __tree_.begin();}
680 _LIBCPP_INLINE_VISIBILITY
681 const_iterator begin() const _NOEXCEPT {return __tree_.begin();}
682 _LIBCPP_INLINE_VISIBILITY
683 iterator end() _NOEXCEPT {return __tree_.end();}
684 _LIBCPP_INLINE_VISIBILITY
685 const_iterator end() const _NOEXCEPT {return __tree_.end();}
686
687 _LIBCPP_INLINE_VISIBILITY
688 reverse_iterator rbegin() _NOEXCEPT
689 {return reverse_iterator(end());}
690 _LIBCPP_INLINE_VISIBILITY
691 const_reverse_iterator rbegin() const _NOEXCEPT
692 {return const_reverse_iterator(end());}
693 _LIBCPP_INLINE_VISIBILITY
694 reverse_iterator rend() _NOEXCEPT
695 {return reverse_iterator(begin());}
696 _LIBCPP_INLINE_VISIBILITY
697 const_reverse_iterator rend() const _NOEXCEPT
698 {return const_reverse_iterator(begin());}
699
700 _LIBCPP_INLINE_VISIBILITY
701 const_iterator cbegin() const _NOEXCEPT {return begin();}
702 _LIBCPP_INLINE_VISIBILITY
703 const_iterator cend() const _NOEXCEPT {return end();}
704 _LIBCPP_INLINE_VISIBILITY
705 const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();}
706 _LIBCPP_INLINE_VISIBILITY
707 const_reverse_iterator crend() const _NOEXCEPT {return rend();}
708
709 _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY
710 bool empty() const _NOEXCEPT {return __tree_.size() == 0;}
711 _LIBCPP_INLINE_VISIBILITY
712 size_type size() const _NOEXCEPT {return __tree_.size();}
713 _LIBCPP_INLINE_VISIBILITY
714 size_type max_size() const _NOEXCEPT {return __tree_.max_size();}
715
716 // modifiers:
717#ifndef _LIBCPP_CXX03_LANG
718 template <class... _Args>
719 _LIBCPP_INLINE_VISIBILITY
720 pair<iterator, bool> emplace(_Args&&... __args)
721 {return __tree_.__emplace_unique(_VSTD::forward<_Args>(__args)...);}
722 template <class... _Args>
723 _LIBCPP_INLINE_VISIBILITY
724 iterator emplace_hint(const_iterator __p, _Args&&... __args)
725 {return __tree_.__emplace_hint_unique(__p, _VSTD::forward<_Args>(__args)...);}
726#endif // _LIBCPP_CXX03_LANG
727
728 _LIBCPP_INLINE_VISIBILITY
729 pair<iterator,bool> insert(const value_type& __v)
730 {return __tree_.__insert_unique(__v);}
731 _LIBCPP_INLINE_VISIBILITY
732 iterator insert(const_iterator __p, const value_type& __v)
733 {return __tree_.__insert_unique(__p, __v);}
734
735 template <class _InputIterator>
736 _LIBCPP_INLINE_VISIBILITY
737 void insert(_InputIterator __f, _InputIterator __l)
738 {
739 for (const_iterator __e = cend(); __f != __l; ++__f)
740 __tree_.__insert_unique(__e, *__f);
741 }
742
743#ifndef _LIBCPP_CXX03_LANG
744 _LIBCPP_INLINE_VISIBILITY
745 pair<iterator,bool> insert(value_type&& __v)
746 {return __tree_.__insert_unique(_VSTD::move(__v));}
747
748 _LIBCPP_INLINE_VISIBILITY
749 iterator insert(const_iterator __p, value_type&& __v)
750 {return __tree_.__insert_unique(__p, _VSTD::move(__v));}
751
752 _LIBCPP_INLINE_VISIBILITY
753 void insert(initializer_list<value_type> __il)
754 {insert(__il.begin(), __il.end());}
755#endif // _LIBCPP_CXX03_LANG
756
757 _LIBCPP_INLINE_VISIBILITY
758 iterator erase(const_iterator __p) {return __tree_.erase(__p);}
759 _LIBCPP_INLINE_VISIBILITY
760 size_type erase(const key_type& __k)
761 {return __tree_.__erase_unique(__k);}
762 _LIBCPP_INLINE_VISIBILITY
763 iterator erase(const_iterator __f, const_iterator __l)
764 {return __tree_.erase(__f, __l);}
765 _LIBCPP_INLINE_VISIBILITY
766 void clear() _NOEXCEPT {__tree_.clear();}
767
768#if _LIBCPP_STD_VER > 14
769 _LIBCPP_INLINE_VISIBILITY
770 insert_return_type insert(node_type&& __nh)
771 {
772 _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(),
773 "node_type with incompatible allocator passed to set::insert()");
774 return __tree_.template __node_handle_insert_unique<
775 node_type, insert_return_type>(_VSTD::move(__nh));
776 }
777 _LIBCPP_INLINE_VISIBILITY
778 iterator insert(const_iterator __hint, node_type&& __nh)
779 {
780 _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(),
781 "node_type with incompatible allocator passed to set::insert()");
782 return __tree_.template __node_handle_insert_unique<node_type>(
783 __hint, _VSTD::move(__nh));
784 }
785 _LIBCPP_INLINE_VISIBILITY
786 node_type extract(key_type const& __key)
787 {
788 return __tree_.template __node_handle_extract<node_type>(__key);
789 }
790 _LIBCPP_INLINE_VISIBILITY
791 node_type extract(const_iterator __it)
792 {
793 return __tree_.template __node_handle_extract<node_type>(__it);
794 }
795 template <class _Compare2>
796 _LIBCPP_INLINE_VISIBILITY
797 void merge(set<key_type, _Compare2, allocator_type>& __source)
798 {
799 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
800 "merging container with incompatible allocator");
801 __tree_.__node_handle_merge_unique(__source.__tree_);
802 }
803 template <class _Compare2>
804 _LIBCPP_INLINE_VISIBILITY
805 void merge(set<key_type, _Compare2, allocator_type>&& __source)
806 {
807 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
808 "merging container with incompatible allocator");
809 __tree_.__node_handle_merge_unique(__source.__tree_);
810 }
811 template <class _Compare2>
812 _LIBCPP_INLINE_VISIBILITY
813 void merge(multiset<key_type, _Compare2, allocator_type>& __source)
814 {
815 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
816 "merging container with incompatible allocator");
817 __tree_.__node_handle_merge_unique(__source.__tree_);
818 }
819 template <class _Compare2>
820 _LIBCPP_INLINE_VISIBILITY
821 void merge(multiset<key_type, _Compare2, allocator_type>&& __source)
822 {
823 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
824 "merging container with incompatible allocator");
825 __tree_.__node_handle_merge_unique(__source.__tree_);
826 }
827#endif
828
829 _LIBCPP_INLINE_VISIBILITY
830 void swap(set& __s) _NOEXCEPT_(__is_nothrow_swappable<__base>::value)
831 {__tree_.swap(__s.__tree_);}
832
833 _LIBCPP_INLINE_VISIBILITY
834 allocator_type get_allocator() const _NOEXCEPT {return __tree_.__alloc();}
835 _LIBCPP_INLINE_VISIBILITY
836 key_compare key_comp() const {return __tree_.value_comp();}
837 _LIBCPP_INLINE_VISIBILITY
838 value_compare value_comp() const {return __tree_.value_comp();}
839
840 // set operations:
841 _LIBCPP_INLINE_VISIBILITY
842 iterator find(const key_type& __k) {return __tree_.find(__k);}
843 _LIBCPP_INLINE_VISIBILITY
844 const_iterator find(const key_type& __k) const {return __tree_.find(__k);}
845#if _LIBCPP_STD_VER > 11
846 template <typename _K2>
847 _LIBCPP_INLINE_VISIBILITY
848 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
849 find(const _K2& __k) {return __tree_.find(__k);}
850 template <typename _K2>
851 _LIBCPP_INLINE_VISIBILITY
852 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
853 find(const _K2& __k) const {return __tree_.find(__k);}
854#endif
855
856 _LIBCPP_INLINE_VISIBILITY
857 size_type count(const key_type& __k) const
858 {return __tree_.__count_unique(__k);}
859#if _LIBCPP_STD_VER > 11
860 template <typename _K2>
861 _LIBCPP_INLINE_VISIBILITY
862 typename enable_if<__is_transparent<_Compare, _K2>::value,size_type>::type
863 count(const _K2& __k) const {return __tree_.__count_multi(__k);}
864#endif
865
866#if _LIBCPP_STD_VER > 17
867 _LIBCPP_INLINE_VISIBILITY
868 bool contains(const key_type& __k) const {return find(__k) != end();}
869 template <typename _K2>
870 _LIBCPP_INLINE_VISIBILITY
871 typename enable_if<__is_transparent<_Compare, _K2>::value, bool>::type
872 contains(const _K2& __k) const { return find(__k) != end(); }
873#endif // _LIBCPP_STD_VER > 17
874
875 _LIBCPP_INLINE_VISIBILITY
876 iterator lower_bound(const key_type& __k)
877 {return __tree_.lower_bound(__k);}
878 _LIBCPP_INLINE_VISIBILITY
879 const_iterator lower_bound(const key_type& __k) const
880 {return __tree_.lower_bound(__k);}
881#if _LIBCPP_STD_VER > 11
882 template <typename _K2>
883 _LIBCPP_INLINE_VISIBILITY
884 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
885 lower_bound(const _K2& __k) {return __tree_.lower_bound(__k);}
886
887 template <typename _K2>
888 _LIBCPP_INLINE_VISIBILITY
889 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
890 lower_bound(const _K2& __k) const {return __tree_.lower_bound(__k);}
891#endif
892
893 _LIBCPP_INLINE_VISIBILITY
894 iterator upper_bound(const key_type& __k)
895 {return __tree_.upper_bound(__k);}
896 _LIBCPP_INLINE_VISIBILITY
897 const_iterator upper_bound(const key_type& __k) const
898 {return __tree_.upper_bound(__k);}
899#if _LIBCPP_STD_VER > 11
900 template <typename _K2>
901 _LIBCPP_INLINE_VISIBILITY
902 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
903 upper_bound(const _K2& __k) {return __tree_.upper_bound(__k);}
904 template <typename _K2>
905 _LIBCPP_INLINE_VISIBILITY
906 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
907 upper_bound(const _K2& __k) const {return __tree_.upper_bound(__k);}
908#endif
909
910 _LIBCPP_INLINE_VISIBILITY
911 pair<iterator,iterator> equal_range(const key_type& __k)
912 {return __tree_.__equal_range_unique(__k);}
913 _LIBCPP_INLINE_VISIBILITY
914 pair<const_iterator,const_iterator> equal_range(const key_type& __k) const
915 {return __tree_.__equal_range_unique(__k);}
916#if _LIBCPP_STD_VER > 11
917 template <typename _K2>
918 _LIBCPP_INLINE_VISIBILITY
919 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<iterator,iterator>>::type
920 equal_range(const _K2& __k) {return __tree_.__equal_range_multi(__k);}
921 template <typename _K2>
922 _LIBCPP_INLINE_VISIBILITY
923 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<const_iterator,const_iterator>>::type
924 equal_range(const _K2& __k) const {return __tree_.__equal_range_multi(__k);}
925#endif
926};
927
928#if _LIBCPP_STD_VER >= 17
929template<class _InputIterator,
930 class _Compare = less<__iter_value_type<_InputIterator>>,
931 class _Allocator = allocator<__iter_value_type<_InputIterator>>,
932 class = enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value, void>,
933 class = enable_if_t<__is_allocator<_Allocator>::value, void>,
934 class = enable_if_t<!__is_allocator<_Compare>::value, void>>
935set(_InputIterator, _InputIterator, _Compare = _Compare(), _Allocator = _Allocator())
936 -> set<__iter_value_type<_InputIterator>, _Compare, _Allocator>;
937
938template<class _Key, class _Compare = less<_Key>,
939 class _Allocator = allocator<_Key>,
940 class = enable_if_t<!__is_allocator<_Compare>::value, void>,
941 class = enable_if_t<__is_allocator<_Allocator>::value, void>>
942set(initializer_list<_Key>, _Compare = _Compare(), _Allocator = _Allocator())
943 -> set<_Key, _Compare, _Allocator>;
944
945template<class _InputIterator, class _Allocator,
946 class = enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value, void>,
947 class = enable_if_t<__is_allocator<_Allocator>::value, void>>
948set(_InputIterator, _InputIterator, _Allocator)
949 -> set<__iter_value_type<_InputIterator>,
950 less<__iter_value_type<_InputIterator>>, _Allocator>;
951
952template<class _Key, class _Allocator,
953 class = enable_if_t<__is_allocator<_Allocator>::value, void>>
954set(initializer_list<_Key>, _Allocator)
955 -> set<_Key, less<_Key>, _Allocator>;
956#endif
957
958#ifndef _LIBCPP_CXX03_LANG
959
960template <class _Key, class _Compare, class _Allocator>
961set<_Key, _Compare, _Allocator>::set(set&& __s, const allocator_type& __a)
962 : __tree_(_VSTD::move(__s.__tree_), __a)
963{
964 if (__a != __s.get_allocator())
965 {
966 const_iterator __e = cend();
967 while (!__s.empty())
968 insert(__e, _VSTD::move(__s.__tree_.remove(__s.begin())->__value_));
969 }
970}
971
972#endif // _LIBCPP_CXX03_LANG
973
974template <class _Key, class _Compare, class _Allocator>
975inline _LIBCPP_INLINE_VISIBILITY
976bool
977operator==(const set<_Key, _Compare, _Allocator>& __x,
978 const set<_Key, _Compare, _Allocator>& __y)
979{
980 return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin());
981}
982
983template <class _Key, class _Compare, class _Allocator>
984inline _LIBCPP_INLINE_VISIBILITY
985bool
986operator< (const set<_Key, _Compare, _Allocator>& __x,
987 const set<_Key, _Compare, _Allocator>& __y)
988{
989 return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
990}
991
992template <class _Key, class _Compare, class _Allocator>
993inline _LIBCPP_INLINE_VISIBILITY
994bool
995operator!=(const set<_Key, _Compare, _Allocator>& __x,
996 const set<_Key, _Compare, _Allocator>& __y)
997{
998 return !(__x == __y);
999}
1000
1001template <class _Key, class _Compare, class _Allocator>
1002inline _LIBCPP_INLINE_VISIBILITY
1003bool
1004operator> (const set<_Key, _Compare, _Allocator>& __x,
1005 const set<_Key, _Compare, _Allocator>& __y)
1006{
1007 return __y < __x;
1008}
1009
1010template <class _Key, class _Compare, class _Allocator>
1011inline _LIBCPP_INLINE_VISIBILITY
1012bool
1013operator>=(const set<_Key, _Compare, _Allocator>& __x,
1014 const set<_Key, _Compare, _Allocator>& __y)
1015{
1016 return !(__x < __y);
1017}
1018
1019template <class _Key, class _Compare, class _Allocator>
1020inline _LIBCPP_INLINE_VISIBILITY
1021bool
1022operator<=(const set<_Key, _Compare, _Allocator>& __x,
1023 const set<_Key, _Compare, _Allocator>& __y)
1024{
1025 return !(__y < __x);
1026}
1027
1028// specialized algorithms:
1029template <class _Key, class _Compare, class _Allocator>
1030inline _LIBCPP_INLINE_VISIBILITY
1031void
1032swap(set<_Key, _Compare, _Allocator>& __x,
1033 set<_Key, _Compare, _Allocator>& __y)
1034 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
1035{
1036 __x.swap(__y);
1037}
1038
1039#if _LIBCPP_STD_VER > 17
1040template <class _Key, class _Compare, class _Allocator, class _Predicate>
1041inline _LIBCPP_INLINE_VISIBILITY
1042 typename set<_Key, _Compare, _Allocator>::size_type
1043 erase_if(set<_Key, _Compare, _Allocator>& __c, _Predicate __pred) {
1044 return _VSTD::__libcpp_erase_if_container(__c, __pred);
1045}
1046#endif
1047
1048template <class _Key, class _Compare = less<_Key>,
1049 class _Allocator = allocator<_Key> >
1050class _LIBCPP_TEMPLATE_VIS multiset
1051{
1052public:
1053 // types:
1054 typedef _Key key_type;
1055 typedef key_type value_type;
1056 typedef __type_identity_t<_Compare> key_compare;
1057 typedef key_compare value_compare;
1058 typedef __type_identity_t<_Allocator> allocator_type;
1059 typedef value_type& reference;
1060 typedef const value_type& const_reference;
1061
1062 static_assert((is_same<typename allocator_type::value_type, value_type>::value),
1063 "Allocator::value_type must be same type as value_type");
1064
1065private:
1066 typedef __tree<value_type, value_compare, allocator_type> __base;
1067 typedef allocator_traits<allocator_type> __alloc_traits;
1068
1069 __base __tree_;
1070
1071public:
1072 typedef typename __base::pointer pointer;
1073 typedef typename __base::const_pointer const_pointer;
1074 typedef typename __base::size_type size_type;
1075 typedef typename __base::difference_type difference_type;
1076 typedef typename __base::const_iterator iterator;
1077 typedef typename __base::const_iterator const_iterator;
1078 typedef _VSTD::reverse_iterator<iterator> reverse_iterator;
1079 typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator;
1080
1081#if _LIBCPP_STD_VER > 14
1082 typedef __set_node_handle<typename __base::__node, allocator_type> node_type;
1083#endif
1084
1085 template <class _Key2, class _Compare2, class _Alloc2>
1086 friend class _LIBCPP_TEMPLATE_VIS set;
1087 template <class _Key2, class _Compare2, class _Alloc2>
1088 friend class _LIBCPP_TEMPLATE_VIS multiset;
1089
1090 // construct/copy/destroy:
1091 _LIBCPP_INLINE_VISIBILITY
1092 multiset()
1093 _NOEXCEPT_(
1094 is_nothrow_default_constructible<allocator_type>::value &&
1095 is_nothrow_default_constructible<key_compare>::value &&
1096 is_nothrow_copy_constructible<key_compare>::value)
1097 : __tree_(value_compare()) {}
1098
1099 _LIBCPP_INLINE_VISIBILITY
1100 explicit multiset(const value_compare& __comp)
1101 _NOEXCEPT_(
1102 is_nothrow_default_constructible<allocator_type>::value &&
1103 is_nothrow_copy_constructible<key_compare>::value)
1104 : __tree_(__comp) {}
1105
1106 _LIBCPP_INLINE_VISIBILITY
1107 explicit multiset(const value_compare& __comp, const allocator_type& __a)
1108 : __tree_(__comp, __a) {}
1109 template <class _InputIterator>
1110 _LIBCPP_INLINE_VISIBILITY
1111 multiset(_InputIterator __f, _InputIterator __l,
1112 const value_compare& __comp = value_compare())
1113 : __tree_(__comp)
1114 {
1115 insert(__f, __l);
1116 }
1117
1118#if _LIBCPP_STD_VER > 11
1119 template <class _InputIterator>
1120 _LIBCPP_INLINE_VISIBILITY
1121 multiset(_InputIterator __f, _InputIterator __l, const allocator_type& __a)
1122 : multiset(__f, __l, key_compare(), __a) {}
1123#endif
1124
1125 template <class _InputIterator>
1126 _LIBCPP_INLINE_VISIBILITY
1127 multiset(_InputIterator __f, _InputIterator __l,
1128 const value_compare& __comp, const allocator_type& __a)
1129 : __tree_(__comp, __a)
1130 {
1131 insert(__f, __l);
1132 }
1133
1134 _LIBCPP_INLINE_VISIBILITY
1135 multiset(const multiset& __s)
1136 : __tree_(__s.__tree_.value_comp(),
1137 __alloc_traits::select_on_container_copy_construction(__s.__tree_.__alloc()))
1138 {
1139 insert(__s.begin(), __s.end());
1140 }
1141
1142 _LIBCPP_INLINE_VISIBILITY
1143 multiset& operator=(const multiset& __s)
1144 {
1145 __tree_ = __s.__tree_;
1146 return *this;
1147 }
1148
1149#ifndef _LIBCPP_CXX03_LANG
1150 _LIBCPP_INLINE_VISIBILITY
1151 multiset(multiset&& __s)
1152 _NOEXCEPT_(is_nothrow_move_constructible<__base>::value)
1153 : __tree_(_VSTD::move(__s.__tree_)) {}
1154
1155 multiset(multiset&& __s, const allocator_type& __a);
1156#endif // _LIBCPP_CXX03_LANG
1157 _LIBCPP_INLINE_VISIBILITY
1158 explicit multiset(const allocator_type& __a)
1159 : __tree_(__a) {}
1160 _LIBCPP_INLINE_VISIBILITY
1161 multiset(const multiset& __s, const allocator_type& __a)
1162 : __tree_(__s.__tree_.value_comp(), __a)
1163 {
1164 insert(__s.begin(), __s.end());
1165 }
1166
1167#ifndef _LIBCPP_CXX03_LANG
1168 _LIBCPP_INLINE_VISIBILITY
1169 multiset(initializer_list<value_type> __il, const value_compare& __comp = value_compare())
1170 : __tree_(__comp)
1171 {
1172 insert(__il.begin(), __il.end());
1173 }
1174
1175 _LIBCPP_INLINE_VISIBILITY
1176 multiset(initializer_list<value_type> __il, const value_compare& __comp,
1177 const allocator_type& __a)
1178 : __tree_(__comp, __a)
1179 {
1180 insert(__il.begin(), __il.end());
1181 }
1182
1183#if _LIBCPP_STD_VER > 11
1184 _LIBCPP_INLINE_VISIBILITY
1185 multiset(initializer_list<value_type> __il, const allocator_type& __a)
1186 : multiset(__il, key_compare(), __a) {}
1187#endif
1188
1189 _LIBCPP_INLINE_VISIBILITY
1190 multiset& operator=(initializer_list<value_type> __il)
1191 {
1192 __tree_.__assign_multi(__il.begin(), __il.end());
1193 return *this;
1194 }
1195
1196 _LIBCPP_INLINE_VISIBILITY
1197 multiset& operator=(multiset&& __s)
1198 _NOEXCEPT_(is_nothrow_move_assignable<__base>::value)
1199 {
1200 __tree_ = _VSTD::move(__s.__tree_);
1201 return *this;
1202 }
1203#endif // _LIBCPP_CXX03_LANG
1204
1205 _LIBCPP_INLINE_VISIBILITY
1206 ~multiset() {
1207 static_assert(sizeof(__diagnose_non_const_comparator<_Key, _Compare>()), "");
1208 }
1209
1210 _LIBCPP_INLINE_VISIBILITY
1211 iterator begin() _NOEXCEPT {return __tree_.begin();}
1212 _LIBCPP_INLINE_VISIBILITY
1213 const_iterator begin() const _NOEXCEPT {return __tree_.begin();}
1214 _LIBCPP_INLINE_VISIBILITY
1215 iterator end() _NOEXCEPT {return __tree_.end();}
1216 _LIBCPP_INLINE_VISIBILITY
1217 const_iterator end() const _NOEXCEPT {return __tree_.end();}
1218
1219 _LIBCPP_INLINE_VISIBILITY
1220 reverse_iterator rbegin() _NOEXCEPT
1221 {return reverse_iterator(end());}
1222 _LIBCPP_INLINE_VISIBILITY
1223 const_reverse_iterator rbegin() const _NOEXCEPT
1224 {return const_reverse_iterator(end());}
1225 _LIBCPP_INLINE_VISIBILITY
1226 reverse_iterator rend() _NOEXCEPT
1227 {return reverse_iterator(begin());}
1228 _LIBCPP_INLINE_VISIBILITY
1229 const_reverse_iterator rend() const _NOEXCEPT
1230 {return const_reverse_iterator(begin());}
1231
1232 _LIBCPP_INLINE_VISIBILITY
1233 const_iterator cbegin() const _NOEXCEPT {return begin();}
1234 _LIBCPP_INLINE_VISIBILITY
1235 const_iterator cend() const _NOEXCEPT {return end();}
1236 _LIBCPP_INLINE_VISIBILITY
1237 const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();}
1238 _LIBCPP_INLINE_VISIBILITY
1239 const_reverse_iterator crend() const _NOEXCEPT {return rend();}
1240
1241 _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY
1242 bool empty() const _NOEXCEPT {return __tree_.size() == 0;}
1243 _LIBCPP_INLINE_VISIBILITY
1244 size_type size() const _NOEXCEPT {return __tree_.size();}
1245 _LIBCPP_INLINE_VISIBILITY
1246 size_type max_size() const _NOEXCEPT {return __tree_.max_size();}
1247
1248 // modifiers:
1249#ifndef _LIBCPP_CXX03_LANG
1250 template <class... _Args>
1251 _LIBCPP_INLINE_VISIBILITY
1252 iterator emplace(_Args&&... __args)
1253 {return __tree_.__emplace_multi(_VSTD::forward<_Args>(__args)...);}
1254 template <class... _Args>
1255 _LIBCPP_INLINE_VISIBILITY
1256 iterator emplace_hint(const_iterator __p, _Args&&... __args)
1257 {return __tree_.__emplace_hint_multi(__p, _VSTD::forward<_Args>(__args)...);}
1258#endif // _LIBCPP_CXX03_LANG
1259
1260 _LIBCPP_INLINE_VISIBILITY
1261 iterator insert(const value_type& __v)
1262 {return __tree_.__insert_multi(__v);}
1263 _LIBCPP_INLINE_VISIBILITY
1264 iterator insert(const_iterator __p, const value_type& __v)
1265 {return __tree_.__insert_multi(__p, __v);}
1266
1267 template <class _InputIterator>
1268 _LIBCPP_INLINE_VISIBILITY
1269 void insert(_InputIterator __f, _InputIterator __l)
1270 {
1271 for (const_iterator __e = cend(); __f != __l; ++__f)
1272 __tree_.__insert_multi(__e, *__f);
1273 }
1274
1275#ifndef _LIBCPP_CXX03_LANG
1276 _LIBCPP_INLINE_VISIBILITY
1277 iterator insert(value_type&& __v)
1278 {return __tree_.__insert_multi(_VSTD::move(__v));}
1279
1280 _LIBCPP_INLINE_VISIBILITY
1281 iterator insert(const_iterator __p, value_type&& __v)
1282 {return __tree_.__insert_multi(__p, _VSTD::move(__v));}
1283
1284 _LIBCPP_INLINE_VISIBILITY
1285 void insert(initializer_list<value_type> __il)
1286 {insert(__il.begin(), __il.end());}
1287#endif // _LIBCPP_CXX03_LANG
1288
1289 _LIBCPP_INLINE_VISIBILITY
1290 iterator erase(const_iterator __p) {return __tree_.erase(__p);}
1291 _LIBCPP_INLINE_VISIBILITY
1292 size_type erase(const key_type& __k) {return __tree_.__erase_multi(__k);}
1293 _LIBCPP_INLINE_VISIBILITY
1294 iterator erase(const_iterator __f, const_iterator __l)
1295 {return __tree_.erase(__f, __l);}
1296 _LIBCPP_INLINE_VISIBILITY
1297 void clear() _NOEXCEPT {__tree_.clear();}
1298
1299#if _LIBCPP_STD_VER > 14
1300 _LIBCPP_INLINE_VISIBILITY
1301 iterator insert(node_type&& __nh)
1302 {
1303 _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(),
1304 "node_type with incompatible allocator passed to multiset::insert()");
1305 return __tree_.template __node_handle_insert_multi<node_type>(
1306 _VSTD::move(__nh));
1307 }
1308 _LIBCPP_INLINE_VISIBILITY
1309 iterator insert(const_iterator __hint, node_type&& __nh)
1310 {
1311 _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(),
1312 "node_type with incompatible allocator passed to multiset::insert()");
1313 return __tree_.template __node_handle_insert_multi<node_type>(
1314 __hint, _VSTD::move(__nh));
1315 }
1316 _LIBCPP_INLINE_VISIBILITY
1317 node_type extract(key_type const& __key)
1318 {
1319 return __tree_.template __node_handle_extract<node_type>(__key);
1320 }
1321 _LIBCPP_INLINE_VISIBILITY
1322 node_type extract(const_iterator __it)
1323 {
1324 return __tree_.template __node_handle_extract<node_type>(__it);
1325 }
1326 template <class _Compare2>
1327 _LIBCPP_INLINE_VISIBILITY
1328 void merge(multiset<key_type, _Compare2, allocator_type>& __source)
1329 {
1330 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
1331 "merging container with incompatible allocator");
1332 __tree_.__node_handle_merge_multi(__source.__tree_);
1333 }
1334 template <class _Compare2>
1335 _LIBCPP_INLINE_VISIBILITY
1336 void merge(multiset<key_type, _Compare2, allocator_type>&& __source)
1337 {
1338 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
1339 "merging container with incompatible allocator");
1340 __tree_.__node_handle_merge_multi(__source.__tree_);
1341 }
1342 template <class _Compare2>
1343 _LIBCPP_INLINE_VISIBILITY
1344 void merge(set<key_type, _Compare2, allocator_type>& __source)
1345 {
1346 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
1347 "merging container with incompatible allocator");
1348 __tree_.__node_handle_merge_multi(__source.__tree_);
1349 }
1350 template <class _Compare2>
1351 _LIBCPP_INLINE_VISIBILITY
1352 void merge(set<key_type, _Compare2, allocator_type>&& __source)
1353 {
1354 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
1355 "merging container with incompatible allocator");
1356 __tree_.__node_handle_merge_multi(__source.__tree_);
1357 }
1358#endif
1359
1360 _LIBCPP_INLINE_VISIBILITY
1361 void swap(multiset& __s)
1362 _NOEXCEPT_(__is_nothrow_swappable<__base>::value)
1363 {__tree_.swap(__s.__tree_);}
1364
1365 _LIBCPP_INLINE_VISIBILITY
1366 allocator_type get_allocator() const _NOEXCEPT {return __tree_.__alloc();}
1367 _LIBCPP_INLINE_VISIBILITY
1368 key_compare key_comp() const {return __tree_.value_comp();}
1369 _LIBCPP_INLINE_VISIBILITY
1370 value_compare value_comp() const {return __tree_.value_comp();}
1371
1372 // set operations:
1373 _LIBCPP_INLINE_VISIBILITY
1374 iterator find(const key_type& __k) {return __tree_.find(__k);}
1375 _LIBCPP_INLINE_VISIBILITY
1376 const_iterator find(const key_type& __k) const {return __tree_.find(__k);}
1377#if _LIBCPP_STD_VER > 11
1378 template <typename _K2>
1379 _LIBCPP_INLINE_VISIBILITY
1380 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
1381 find(const _K2& __k) {return __tree_.find(__k);}
1382 template <typename _K2>
1383 _LIBCPP_INLINE_VISIBILITY
1384 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
1385 find(const _K2& __k) const {return __tree_.find(__k);}
1386#endif
1387
1388 _LIBCPP_INLINE_VISIBILITY
1389 size_type count(const key_type& __k) const
1390 {return __tree_.__count_multi(__k);}
1391#if _LIBCPP_STD_VER > 11
1392 template <typename _K2>
1393 _LIBCPP_INLINE_VISIBILITY
1394 typename enable_if<__is_transparent<_Compare, _K2>::value,size_type>::type
1395 count(const _K2& __k) const {return __tree_.__count_multi(__k);}
1396#endif
1397
1398#if _LIBCPP_STD_VER > 17
1399 _LIBCPP_INLINE_VISIBILITY
1400 bool contains(const key_type& __k) const {return find(__k) != end();}
1401 template <typename _K2>
1402 _LIBCPP_INLINE_VISIBILITY
1403 typename enable_if<__is_transparent<_Compare, _K2>::value, bool>::type
1404 contains(const _K2& __k) const { return find(__k) != end(); }
1405#endif // _LIBCPP_STD_VER > 17
1406
1407 _LIBCPP_INLINE_VISIBILITY
1408 iterator lower_bound(const key_type& __k)
1409 {return __tree_.lower_bound(__k);}
1410 _LIBCPP_INLINE_VISIBILITY
1411 const_iterator lower_bound(const key_type& __k) const
1412 {return __tree_.lower_bound(__k);}
1413#if _LIBCPP_STD_VER > 11
1414 template <typename _K2>
1415 _LIBCPP_INLINE_VISIBILITY
1416 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
1417 lower_bound(const _K2& __k) {return __tree_.lower_bound(__k);}
1418
1419 template <typename _K2>
1420 _LIBCPP_INLINE_VISIBILITY
1421 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
1422 lower_bound(const _K2& __k) const {return __tree_.lower_bound(__k);}
1423#endif
1424
1425 _LIBCPP_INLINE_VISIBILITY
1426 iterator upper_bound(const key_type& __k)
1427 {return __tree_.upper_bound(__k);}
1428 _LIBCPP_INLINE_VISIBILITY
1429 const_iterator upper_bound(const key_type& __k) const
1430 {return __tree_.upper_bound(__k);}
1431#if _LIBCPP_STD_VER > 11
1432 template <typename _K2>
1433 _LIBCPP_INLINE_VISIBILITY
1434 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
1435 upper_bound(const _K2& __k) {return __tree_.upper_bound(__k);}
1436 template <typename _K2>
1437 _LIBCPP_INLINE_VISIBILITY
1438 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
1439 upper_bound(const _K2& __k) const {return __tree_.upper_bound(__k);}
1440#endif
1441
1442 _LIBCPP_INLINE_VISIBILITY
1443 pair<iterator,iterator> equal_range(const key_type& __k)
1444 {return __tree_.__equal_range_multi(__k);}
1445 _LIBCPP_INLINE_VISIBILITY
1446 pair<const_iterator,const_iterator> equal_range(const key_type& __k) const
1447 {return __tree_.__equal_range_multi(__k);}
1448#if _LIBCPP_STD_VER > 11
1449 template <typename _K2>
1450 _LIBCPP_INLINE_VISIBILITY
1451 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<iterator,iterator>>::type
1452 equal_range(const _K2& __k) {return __tree_.__equal_range_multi(__k);}
1453 template <typename _K2>
1454 _LIBCPP_INLINE_VISIBILITY
1455 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<const_iterator,const_iterator>>::type
1456 equal_range(const _K2& __k) const {return __tree_.__equal_range_multi(__k);}
1457#endif
1458};
1459
1460#if _LIBCPP_STD_VER >= 17
1461template<class _InputIterator,
1462 class _Compare = less<__iter_value_type<_InputIterator>>,
1463 class _Allocator = allocator<__iter_value_type<_InputIterator>>,
1464 class = enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value, void>,
1465 class = enable_if_t<__is_allocator<_Allocator>::value, void>,
1466 class = enable_if_t<!__is_allocator<_Compare>::value, void>>
1467multiset(_InputIterator, _InputIterator, _Compare = _Compare(), _Allocator = _Allocator())
1468 -> multiset<__iter_value_type<_InputIterator>, _Compare, _Allocator>;
1469
1470template<class _Key, class _Compare = less<_Key>,
1471 class _Allocator = allocator<_Key>,
1472 class = enable_if_t<__is_allocator<_Allocator>::value, void>,
1473 class = enable_if_t<!__is_allocator<_Compare>::value, void>>
1474multiset(initializer_list<_Key>, _Compare = _Compare(), _Allocator = _Allocator())
1475 -> multiset<_Key, _Compare, _Allocator>;
1476
1477template<class _InputIterator, class _Allocator,
1478 class = enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value, void>,
1479 class = enable_if_t<__is_allocator<_Allocator>::value, void>>
1480multiset(_InputIterator, _InputIterator, _Allocator)
1481 -> multiset<__iter_value_type<_InputIterator>,
1482 less<__iter_value_type<_InputIterator>>, _Allocator>;
1483
1484template<class _Key, class _Allocator,
1485 class = enable_if_t<__is_allocator<_Allocator>::value, void>>
1486multiset(initializer_list<_Key>, _Allocator)
1487 -> multiset<_Key, less<_Key>, _Allocator>;
1488#endif
1489
1490#ifndef _LIBCPP_CXX03_LANG
1491
1492template <class _Key, class _Compare, class _Allocator>
1493multiset<_Key, _Compare, _Allocator>::multiset(multiset&& __s, const allocator_type& __a)
1494 : __tree_(_VSTD::move(__s.__tree_), __a)
1495{
1496 if (__a != __s.get_allocator())
1497 {
1498 const_iterator __e = cend();
1499 while (!__s.empty())
1500 insert(__e, _VSTD::move(__s.__tree_.remove(__s.begin())->__value_));
1501 }
1502}
1503
1504#endif // _LIBCPP_CXX03_LANG
1505
1506template <class _Key, class _Compare, class _Allocator>
1507inline _LIBCPP_INLINE_VISIBILITY
1508bool
1509operator==(const multiset<_Key, _Compare, _Allocator>& __x,
1510 const multiset<_Key, _Compare, _Allocator>& __y)
1511{
1512 return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin());
1513}
1514
1515template <class _Key, class _Compare, class _Allocator>
1516inline _LIBCPP_INLINE_VISIBILITY
1517bool
1518operator< (const multiset<_Key, _Compare, _Allocator>& __x,
1519 const multiset<_Key, _Compare, _Allocator>& __y)
1520{
1521 return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
1522}
1523
1524template <class _Key, class _Compare, class _Allocator>
1525inline _LIBCPP_INLINE_VISIBILITY
1526bool
1527operator!=(const multiset<_Key, _Compare, _Allocator>& __x,
1528 const multiset<_Key, _Compare, _Allocator>& __y)
1529{
1530 return !(__x == __y);
1531}
1532
1533template <class _Key, class _Compare, class _Allocator>
1534inline _LIBCPP_INLINE_VISIBILITY
1535bool
1536operator> (const multiset<_Key, _Compare, _Allocator>& __x,
1537 const multiset<_Key, _Compare, _Allocator>& __y)
1538{
1539 return __y < __x;
1540}
1541
1542template <class _Key, class _Compare, class _Allocator>
1543inline _LIBCPP_INLINE_VISIBILITY
1544bool
1545operator>=(const multiset<_Key, _Compare, _Allocator>& __x,
1546 const multiset<_Key, _Compare, _Allocator>& __y)
1547{
1548 return !(__x < __y);
1549}
1550
1551template <class _Key, class _Compare, class _Allocator>
1552inline _LIBCPP_INLINE_VISIBILITY
1553bool
1554operator<=(const multiset<_Key, _Compare, _Allocator>& __x,
1555 const multiset<_Key, _Compare, _Allocator>& __y)
1556{
1557 return !(__y < __x);
1558}
1559
1560template <class _Key, class _Compare, class _Allocator>
1561inline _LIBCPP_INLINE_VISIBILITY
1562void
1563swap(multiset<_Key, _Compare, _Allocator>& __x,
1564 multiset<_Key, _Compare, _Allocator>& __y)
1565 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
1566{
1567 __x.swap(__y);
1568}
1569
1570#if _LIBCPP_STD_VER > 17
1571template <class _Key, class _Compare, class _Allocator, class _Predicate>
1572inline _LIBCPP_INLINE_VISIBILITY
1573 typename multiset<_Key, _Compare, _Allocator>::size_type
1574 erase_if(multiset<_Key, _Compare, _Allocator>& __c, _Predicate __pred) {
1575 return _VSTD::__libcpp_erase_if_container(__c, __pred);
1576}
1577#endif
1578
1579_LIBCPP_END_NAMESPACE_STD
1580
1581#endif // _LIBCPP_SET
1582

Provided by KDAB

Privacy Policy
Learn more about Flutter for embedded and desktop on industrialflutter.com

source code of flutter_engine/third_party/libcxx/include/set