2 //===---------------------------- set -------------------------------------===//
4 // The LLVM Compiler Infrastructure
6 // This file is dual licensed under the MIT and the University of Illinois Open
7 // Source Licenses. See LICENSE.TXT for details.
9 //===----------------------------------------------------------------------===//
21 template <class Key, class Compare = less<Key>,
22 class Allocator = allocator<Key>>
28 typedef key_type value_type;
29 typedef Compare key_compare;
30 typedef key_compare value_compare;
31 typedef Allocator allocator_type;
32 typedef typename allocator_type::reference reference;
33 typedef typename allocator_type::const_reference const_reference;
34 typedef typename allocator_type::size_type size_type;
35 typedef typename allocator_type::difference_type difference_type;
36 typedef typename allocator_type::pointer pointer;
37 typedef typename allocator_type::const_pointer const_pointer;
39 typedef implementation-defined iterator;
40 typedef implementation-defined const_iterator;
41 typedef std::reverse_iterator<iterator> reverse_iterator;
42 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
44 // construct/copy/destroy:
47 is_nothrow_default_constructible<allocator_type>::value &&
48 is_nothrow_default_constructible<key_compare>::value &&
49 is_nothrow_copy_constructible<key_compare>::value);
50 explicit set(const value_compare& comp);
51 set(const value_compare& comp, const allocator_type& a);
52 template <class InputIterator>
53 set(InputIterator first, InputIterator last,
54 const value_compare& comp = value_compare());
55 template <class InputIterator>
56 set(InputIterator first, InputIterator last, const value_compare& comp,
57 const allocator_type& a);
61 is_nothrow_move_constructible<allocator_type>::value &&
62 is_nothrow_move_constructible<key_compare>::value);
63 explicit set(const allocator_type& a);
64 set(const set& s, const allocator_type& a);
65 set(set&& s, const allocator_type& a);
66 set(initializer_list<value_type> il, const value_compare& comp = value_compare());
67 set(initializer_list<value_type> il, const value_compare& comp,
68 const allocator_type& a);
69 template <class InputIterator>
70 set(InputIterator first, InputIterator last, const allocator_type& a)
71 : set(first, last, Compare(), a) {} // C++14
72 set(initializer_list<value_type> il, const allocator_type& a)
73 : set(il, Compare(), a) {} // C++14
76 set& operator=(const set& s);
77 set& operator=(set&& s)
79 allocator_type::propagate_on_container_move_assignment::value &&
80 is_nothrow_move_assignable<allocator_type>::value &&
81 is_nothrow_move_assignable<key_compare>::value);
82 set& operator=(initializer_list<value_type> il);
85 iterator begin() noexcept;
86 const_iterator begin() const noexcept;
87 iterator end() noexcept;
88 const_iterator end() const noexcept;
90 reverse_iterator rbegin() noexcept;
91 const_reverse_iterator rbegin() const noexcept;
92 reverse_iterator rend() noexcept;
93 const_reverse_iterator rend() const noexcept;
95 const_iterator cbegin() const noexcept;
96 const_iterator cend() const noexcept;
97 const_reverse_iterator crbegin() const noexcept;
98 const_reverse_iterator crend() const noexcept;
101 bool empty() const noexcept;
102 size_type size() const noexcept;
103 size_type max_size() const noexcept;
106 template <class... Args>
107 pair<iterator, bool> emplace(Args&&... args);
108 template <class... Args>
109 iterator emplace_hint(const_iterator position, Args&&... args);
110 pair<iterator,bool> insert(const value_type& v);
111 pair<iterator,bool> insert(value_type&& v);
112 iterator insert(const_iterator position, const value_type& v);
113 iterator insert(const_iterator position, value_type&& v);
114 template <class InputIterator>
115 void insert(InputIterator first, InputIterator last);
116 void insert(initializer_list<value_type> il);
118 iterator erase(const_iterator position);
119 iterator erase(iterator position); // C++14
120 size_type erase(const key_type& k);
121 iterator erase(const_iterator first, const_iterator last);
122 void clear() noexcept;
126 __is_nothrow_swappable<key_compare>::value &&
127 (!allocator_type::propagate_on_container_swap::value ||
128 __is_nothrow_swappable<allocator_type>::value));
131 allocator_type get_allocator() const noexcept;
132 key_compare key_comp() const;
133 value_compare value_comp() const;
136 iterator find(const key_type& k);
137 const_iterator find(const key_type& k) const;
139 iterator find(const K& x);
141 const_iterator find(const K& x) const; // C++14
143 size_type count(const K& x) const; // C++14
145 size_type count(const key_type& k) const;
146 iterator lower_bound(const key_type& k);
147 const_iterator lower_bound(const key_type& k) const;
149 iterator lower_bound(const K& x); // C++14
151 const_iterator lower_bound(const K& x) const; // C++14
153 iterator upper_bound(const key_type& k);
154 const_iterator upper_bound(const key_type& k) const;
156 iterator upper_bound(const K& x); // C++14
158 const_iterator upper_bound(const K& x) const; // C++14
159 pair<iterator,iterator> equal_range(const key_type& k);
160 pair<const_iterator,const_iterator> equal_range(const key_type& k) const;
162 pair<iterator,iterator> equal_range(const K& x); // C++14
164 pair<const_iterator,const_iterator> equal_range(const K& x) const; // C++14
167 template <class Key, class Compare, class Allocator>
169 operator==(const set<Key, Compare, Allocator>& x,
170 const set<Key, Compare, Allocator>& y);
172 template <class Key, class Compare, class Allocator>
174 operator< (const set<Key, Compare, Allocator>& x,
175 const set<Key, Compare, Allocator>& y);
177 template <class Key, class Compare, class Allocator>
179 operator!=(const set<Key, Compare, Allocator>& x,
180 const set<Key, Compare, Allocator>& y);
182 template <class Key, class Compare, class Allocator>
184 operator> (const set<Key, Compare, Allocator>& x,
185 const set<Key, Compare, Allocator>& y);
187 template <class Key, class Compare, class Allocator>
189 operator>=(const set<Key, Compare, Allocator>& x,
190 const set<Key, Compare, Allocator>& y);
192 template <class Key, class Compare, class Allocator>
194 operator<=(const set<Key, Compare, Allocator>& x,
195 const set<Key, Compare, Allocator>& y);
197 // specialized algorithms:
198 template <class Key, class Compare, class Allocator>
200 swap(set<Key, Compare, Allocator>& x, set<Key, Compare, Allocator>& y)
201 noexcept(noexcept(x.swap(y)));
203 template <class Key, class Compare = less<Key>,
204 class Allocator = allocator<Key>>
209 typedef Key key_type;
210 typedef key_type value_type;
211 typedef Compare key_compare;
212 typedef key_compare value_compare;
213 typedef Allocator allocator_type;
214 typedef typename allocator_type::reference reference;
215 typedef typename allocator_type::const_reference const_reference;
216 typedef typename allocator_type::size_type size_type;
217 typedef typename allocator_type::difference_type difference_type;
218 typedef typename allocator_type::pointer pointer;
219 typedef typename allocator_type::const_pointer const_pointer;
221 typedef implementation-defined iterator;
222 typedef implementation-defined const_iterator;
223 typedef std::reverse_iterator<iterator> reverse_iterator;
224 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
226 // construct/copy/destroy:
229 is_nothrow_default_constructible<allocator_type>::value &&
230 is_nothrow_default_constructible<key_compare>::value &&
231 is_nothrow_copy_constructible<key_compare>::value);
232 explicit multiset(const value_compare& comp);
233 multiset(const value_compare& comp, const allocator_type& a);
234 template <class InputIterator>
235 multiset(InputIterator first, InputIterator last,
236 const value_compare& comp = value_compare());
237 template <class InputIterator>
238 multiset(InputIterator first, InputIterator last,
239 const value_compare& comp, const allocator_type& a);
240 multiset(const multiset& s);
241 multiset(multiset&& s)
243 is_nothrow_move_constructible<allocator_type>::value &&
244 is_nothrow_move_constructible<key_compare>::value);
245 explicit multiset(const allocator_type& a);
246 multiset(const multiset& s, const allocator_type& a);
247 multiset(multiset&& s, const allocator_type& a);
248 multiset(initializer_list<value_type> il, const value_compare& comp = value_compare());
249 multiset(initializer_list<value_type> il, const value_compare& comp,
250 const allocator_type& a);
251 template <class InputIterator>
252 multiset(InputIterator first, InputIterator last, const allocator_type& a)
253 : set(first, last, Compare(), a) {} // C++14
254 multiset(initializer_list<value_type> il, const allocator_type& a)
255 : set(il, Compare(), a) {} // C++14
258 multiset& operator=(const multiset& s);
259 multiset& operator=(multiset&& s)
261 allocator_type::propagate_on_container_move_assignment::value &&
262 is_nothrow_move_assignable<allocator_type>::value &&
263 is_nothrow_move_assignable<key_compare>::value);
264 multiset& operator=(initializer_list<value_type> il);
267 iterator begin() noexcept;
268 const_iterator begin() const noexcept;
269 iterator end() noexcept;
270 const_iterator end() const noexcept;
272 reverse_iterator rbegin() noexcept;
273 const_reverse_iterator rbegin() const noexcept;
274 reverse_iterator rend() noexcept;
275 const_reverse_iterator rend() const noexcept;
277 const_iterator cbegin() const noexcept;
278 const_iterator cend() const noexcept;
279 const_reverse_iterator crbegin() const noexcept;
280 const_reverse_iterator crend() const noexcept;
283 bool empty() const noexcept;
284 size_type size() const noexcept;
285 size_type max_size() const noexcept;
288 template <class... Args>
289 iterator emplace(Args&&... args);
290 template <class... Args>
291 iterator emplace_hint(const_iterator position, Args&&... args);
292 iterator insert(const value_type& v);
293 iterator insert(value_type&& v);
294 iterator insert(const_iterator position, const value_type& v);
295 iterator insert(const_iterator position, value_type&& v);
296 template <class InputIterator>
297 void insert(InputIterator first, InputIterator last);
298 void insert(initializer_list<value_type> il);
300 iterator erase(const_iterator position);
301 iterator erase(iterator position); // C++14
302 size_type erase(const key_type& k);
303 iterator erase(const_iterator first, const_iterator last);
304 void clear() noexcept;
306 void swap(multiset& s)
308 __is_nothrow_swappable<key_compare>::value &&
309 (!allocator_type::propagate_on_container_swap::value ||
310 __is_nothrow_swappable<allocator_type>::value));
313 allocator_type get_allocator() const noexcept;
314 key_compare key_comp() const;
315 value_compare value_comp() const;
318 iterator find(const key_type& k);
319 const_iterator find(const key_type& k) const;
321 iterator find(const K& x);
323 const_iterator find(const K& x) const; // C++14
325 size_type count(const key_type& k) const;
326 iterator lower_bound(const key_type& k);
327 const_iterator lower_bound(const key_type& k) const;
329 iterator lower_bound(const K& x); // C++14
331 const_iterator lower_bound(const K& x) const; // C++14
333 iterator upper_bound(const key_type& k);
334 const_iterator upper_bound(const key_type& k) const;
336 iterator upper_bound(const K& x); // C++14
338 const_iterator upper_bound(const K& x) const; // C++14
340 pair<iterator,iterator> equal_range(const key_type& k);
341 pair<const_iterator,const_iterator> equal_range(const key_type& k) const;
343 pair<iterator,iterator> equal_range(const K& x); // C++14
345 pair<const_iterator,const_iterator> equal_range(const K& x) const; // C++14
348 template <class Key, class Compare, class Allocator>
350 operator==(const multiset<Key, Compare, Allocator>& x,
351 const multiset<Key, Compare, Allocator>& y);
353 template <class Key, class Compare, class Allocator>
355 operator< (const multiset<Key, Compare, Allocator>& x,
356 const multiset<Key, Compare, Allocator>& y);
358 template <class Key, class Compare, class Allocator>
360 operator!=(const multiset<Key, Compare, Allocator>& x,
361 const multiset<Key, Compare, Allocator>& y);
363 template <class Key, class Compare, class Allocator>
365 operator> (const multiset<Key, Compare, Allocator>& x,
366 const multiset<Key, Compare, Allocator>& y);
368 template <class Key, class Compare, class Allocator>
370 operator>=(const multiset<Key, Compare, Allocator>& x,
371 const multiset<Key, Compare, Allocator>& y);
373 template <class Key, class Compare, class Allocator>
375 operator<=(const multiset<Key, Compare, Allocator>& x,
376 const multiset<Key, Compare, Allocator>& y);
378 // specialized algorithms:
379 template <class Key, class Compare, class Allocator>
381 swap(multiset<Key, Compare, Allocator>& x, multiset<Key, Compare, Allocator>& y)
382 noexcept(noexcept(x.swap(y)));
390 #include <functional>
392 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
393 #pragma GCC system_header
396 _LIBCPP_BEGIN_NAMESPACE_STD
398 template <class _Key, class _Compare = less<_Key>,
399 class _Allocator = allocator<_Key> >
400 class _LIBCPP_TEMPLATE_VIS set
404 typedef _Key key_type;
405 typedef key_type value_type;
406 typedef _Compare key_compare;
407 typedef key_compare value_compare;
408 typedef _Allocator allocator_type;
409 typedef value_type& reference;
410 typedef const value_type& const_reference;
412 static_assert((is_same<typename allocator_type::value_type, value_type>::value),
413 "Allocator::value_type must be same type as value_type");
416 typedef __tree<value_type, value_compare, allocator_type> __base;
417 typedef allocator_traits<allocator_type> __alloc_traits;
418 typedef typename __base::__node_holder __node_holder;
423 typedef typename __base::pointer pointer;
424 typedef typename __base::const_pointer const_pointer;
425 typedef typename __base::size_type size_type;
426 typedef typename __base::difference_type difference_type;
427 typedef typename __base::const_iterator iterator;
428 typedef typename __base::const_iterator const_iterator;
429 typedef _VSTD::reverse_iterator<iterator> reverse_iterator;
430 typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator;
432 _LIBCPP_INLINE_VISIBILITY
435 is_nothrow_default_constructible<allocator_type>::value &&
436 is_nothrow_default_constructible<key_compare>::value &&
437 is_nothrow_copy_constructible<key_compare>::value)
438 : __tree_(value_compare()) {}
440 _LIBCPP_INLINE_VISIBILITY
441 explicit set(const value_compare& __comp)
443 is_nothrow_default_constructible<allocator_type>::value &&
444 is_nothrow_copy_constructible<key_compare>::value)
447 _LIBCPP_INLINE_VISIBILITY
448 explicit set(const value_compare& __comp, const allocator_type& __a)
449 : __tree_(__comp, __a) {}
450 template <class _InputIterator>
451 _LIBCPP_INLINE_VISIBILITY
452 set(_InputIterator __f, _InputIterator __l,
453 const value_compare& __comp = value_compare())
459 template <class _InputIterator>
460 _LIBCPP_INLINE_VISIBILITY
461 set(_InputIterator __f, _InputIterator __l, const value_compare& __comp,
462 const allocator_type& __a)
463 : __tree_(__comp, __a)
468 #if _LIBCPP_STD_VER > 11
469 template <class _InputIterator>
470 _LIBCPP_INLINE_VISIBILITY
471 set(_InputIterator __f, _InputIterator __l, const allocator_type& __a)
472 : set(__f, __l, key_compare(), __a) {}
475 _LIBCPP_INLINE_VISIBILITY
477 : __tree_(__s.__tree_)
479 insert(__s.begin(), __s.end());
482 _LIBCPP_INLINE_VISIBILITY
483 set& operator=(const set& __s)
485 __tree_ = __s.__tree_;
489 #ifndef _LIBCPP_CXX03_LANG
490 _LIBCPP_INLINE_VISIBILITY
492 _NOEXCEPT_(is_nothrow_move_constructible<__base>::value)
493 : __tree_(_VSTD::move(__s.__tree_)) {}
494 #endif // _LIBCPP_CXX03_LANG
496 _LIBCPP_INLINE_VISIBILITY
497 explicit set(const allocator_type& __a)
500 _LIBCPP_INLINE_VISIBILITY
501 set(const set& __s, const allocator_type& __a)
502 : __tree_(__s.__tree_.value_comp(), __a)
504 insert(__s.begin(), __s.end());
507 #ifndef _LIBCPP_CXX03_LANG
508 set(set&& __s, const allocator_type& __a);
510 _LIBCPP_INLINE_VISIBILITY
511 set(initializer_list<value_type> __il, const value_compare& __comp = value_compare())
514 insert(__il.begin(), __il.end());
517 _LIBCPP_INLINE_VISIBILITY
518 set(initializer_list<value_type> __il, const value_compare& __comp,
519 const allocator_type& __a)
520 : __tree_(__comp, __a)
522 insert(__il.begin(), __il.end());
525 #if _LIBCPP_STD_VER > 11
526 _LIBCPP_INLINE_VISIBILITY
527 set(initializer_list<value_type> __il, const allocator_type& __a)
528 : set(__il, key_compare(), __a) {}
531 _LIBCPP_INLINE_VISIBILITY
532 set& operator=(initializer_list<value_type> __il)
534 __tree_.__assign_unique(__il.begin(), __il.end());
538 _LIBCPP_INLINE_VISIBILITY
539 set& operator=(set&& __s)
540 _NOEXCEPT_(is_nothrow_move_assignable<__base>::value)
542 __tree_ = _VSTD::move(__s.__tree_);
545 #endif // _LIBCPP_CXX03_LANG
547 _LIBCPP_INLINE_VISIBILITY
548 iterator begin() _NOEXCEPT {return __tree_.begin();}
549 _LIBCPP_INLINE_VISIBILITY
550 const_iterator begin() const _NOEXCEPT {return __tree_.begin();}
551 _LIBCPP_INLINE_VISIBILITY
552 iterator end() _NOEXCEPT {return __tree_.end();}
553 _LIBCPP_INLINE_VISIBILITY
554 const_iterator end() const _NOEXCEPT {return __tree_.end();}
556 _LIBCPP_INLINE_VISIBILITY
557 reverse_iterator rbegin() _NOEXCEPT
558 {return reverse_iterator(end());}
559 _LIBCPP_INLINE_VISIBILITY
560 const_reverse_iterator rbegin() const _NOEXCEPT
561 {return const_reverse_iterator(end());}
562 _LIBCPP_INLINE_VISIBILITY
563 reverse_iterator rend() _NOEXCEPT
564 {return reverse_iterator(begin());}
565 _LIBCPP_INLINE_VISIBILITY
566 const_reverse_iterator rend() const _NOEXCEPT
567 {return const_reverse_iterator(begin());}
569 _LIBCPP_INLINE_VISIBILITY
570 const_iterator cbegin() const _NOEXCEPT {return begin();}
571 _LIBCPP_INLINE_VISIBILITY
572 const_iterator cend() const _NOEXCEPT {return end();}
573 _LIBCPP_INLINE_VISIBILITY
574 const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();}
575 _LIBCPP_INLINE_VISIBILITY
576 const_reverse_iterator crend() const _NOEXCEPT {return rend();}
578 _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY
579 bool empty() const _NOEXCEPT {return __tree_.size() == 0;}
580 _LIBCPP_INLINE_VISIBILITY
581 size_type size() const _NOEXCEPT {return __tree_.size();}
582 _LIBCPP_INLINE_VISIBILITY
583 size_type max_size() const _NOEXCEPT {return __tree_.max_size();}
586 #ifndef _LIBCPP_CXX03_LANG
587 template <class... _Args>
588 _LIBCPP_INLINE_VISIBILITY
589 pair<iterator, bool> emplace(_Args&&... __args)
590 {return __tree_.__emplace_unique(_VSTD::forward<_Args>(__args)...);}
591 template <class... _Args>
592 _LIBCPP_INLINE_VISIBILITY
593 iterator emplace_hint(const_iterator __p, _Args&&... __args)
594 {return __tree_.__emplace_hint_unique(__p, _VSTD::forward<_Args>(__args)...);}
595 #endif // _LIBCPP_CXX03_LANG
597 _LIBCPP_INLINE_VISIBILITY
598 pair<iterator,bool> insert(const value_type& __v)
599 {return __tree_.__insert_unique(__v);}
600 _LIBCPP_INLINE_VISIBILITY
601 iterator insert(const_iterator __p, const value_type& __v)
602 {return __tree_.__insert_unique(__p, __v);}
604 template <class _InputIterator>
605 _LIBCPP_INLINE_VISIBILITY
606 void insert(_InputIterator __f, _InputIterator __l)
608 for (const_iterator __e = cend(); __f != __l; ++__f)
609 __tree_.__insert_unique(__e, *__f);
612 #ifndef _LIBCPP_CXX03_LANG
613 _LIBCPP_INLINE_VISIBILITY
614 pair<iterator,bool> insert(value_type&& __v)
615 {return __tree_.__insert_unique(_VSTD::move(__v));}
617 _LIBCPP_INLINE_VISIBILITY
618 iterator insert(const_iterator __p, value_type&& __v)
619 {return __tree_.__insert_unique(__p, _VSTD::move(__v));}
621 _LIBCPP_INLINE_VISIBILITY
622 void insert(initializer_list<value_type> __il)
623 {insert(__il.begin(), __il.end());}
624 #endif // _LIBCPP_CXX03_LANG
626 _LIBCPP_INLINE_VISIBILITY
627 iterator erase(const_iterator __p) {return __tree_.erase(__p);}
628 _LIBCPP_INLINE_VISIBILITY
629 size_type erase(const key_type& __k)
630 {return __tree_.__erase_unique(__k);}
631 _LIBCPP_INLINE_VISIBILITY
632 iterator erase(const_iterator __f, const_iterator __l)
633 {return __tree_.erase(__f, __l);}
634 _LIBCPP_INLINE_VISIBILITY
635 void clear() _NOEXCEPT {__tree_.clear();}
637 _LIBCPP_INLINE_VISIBILITY
638 void swap(set& __s) _NOEXCEPT_(__is_nothrow_swappable<__base>::value)
639 {__tree_.swap(__s.__tree_);}
641 _LIBCPP_INLINE_VISIBILITY
642 allocator_type get_allocator() const _NOEXCEPT {return __tree_.__alloc();}
643 _LIBCPP_INLINE_VISIBILITY
644 key_compare key_comp() const {return __tree_.value_comp();}
645 _LIBCPP_INLINE_VISIBILITY
646 value_compare value_comp() const {return __tree_.value_comp();}
649 _LIBCPP_INLINE_VISIBILITY
650 iterator find(const key_type& __k) {return __tree_.find(__k);}
651 _LIBCPP_INLINE_VISIBILITY
652 const_iterator find(const key_type& __k) const {return __tree_.find(__k);}
653 #if _LIBCPP_STD_VER > 11
654 template <typename _K2>
655 _LIBCPP_INLINE_VISIBILITY
656 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
657 find(const _K2& __k) {return __tree_.find(__k);}
658 template <typename _K2>
659 _LIBCPP_INLINE_VISIBILITY
660 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
661 find(const _K2& __k) const {return __tree_.find(__k);}
664 _LIBCPP_INLINE_VISIBILITY
665 size_type count(const key_type& __k) const
666 {return __tree_.__count_unique(__k);}
667 #if _LIBCPP_STD_VER > 11
668 template <typename _K2>
669 _LIBCPP_INLINE_VISIBILITY
670 typename enable_if<__is_transparent<_Compare, _K2>::value,size_type>::type
671 count(const _K2& __k) const {return __tree_.__count_unique(__k);}
673 _LIBCPP_INLINE_VISIBILITY
674 iterator lower_bound(const key_type& __k)
675 {return __tree_.lower_bound(__k);}
676 _LIBCPP_INLINE_VISIBILITY
677 const_iterator lower_bound(const key_type& __k) const
678 {return __tree_.lower_bound(__k);}
679 #if _LIBCPP_STD_VER > 11
680 template <typename _K2>
681 _LIBCPP_INLINE_VISIBILITY
682 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
683 lower_bound(const _K2& __k) {return __tree_.lower_bound(__k);}
685 template <typename _K2>
686 _LIBCPP_INLINE_VISIBILITY
687 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
688 lower_bound(const _K2& __k) const {return __tree_.lower_bound(__k);}
691 _LIBCPP_INLINE_VISIBILITY
692 iterator upper_bound(const key_type& __k)
693 {return __tree_.upper_bound(__k);}
694 _LIBCPP_INLINE_VISIBILITY
695 const_iterator upper_bound(const key_type& __k) const
696 {return __tree_.upper_bound(__k);}
697 #if _LIBCPP_STD_VER > 11
698 template <typename _K2>
699 _LIBCPP_INLINE_VISIBILITY
700 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
701 upper_bound(const _K2& __k) {return __tree_.upper_bound(__k);}
702 template <typename _K2>
703 _LIBCPP_INLINE_VISIBILITY
704 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
705 upper_bound(const _K2& __k) const {return __tree_.upper_bound(__k);}
708 _LIBCPP_INLINE_VISIBILITY
709 pair<iterator,iterator> equal_range(const key_type& __k)
710 {return __tree_.__equal_range_unique(__k);}
711 _LIBCPP_INLINE_VISIBILITY
712 pair<const_iterator,const_iterator> equal_range(const key_type& __k) const
713 {return __tree_.__equal_range_unique(__k);}
714 #if _LIBCPP_STD_VER > 11
715 template <typename _K2>
716 _LIBCPP_INLINE_VISIBILITY
717 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<iterator,iterator>>::type
718 equal_range(const _K2& __k) {return __tree_.__equal_range_unique(__k);}
719 template <typename _K2>
720 _LIBCPP_INLINE_VISIBILITY
721 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<const_iterator,const_iterator>>::type
722 equal_range(const _K2& __k) const {return __tree_.__equal_range_unique(__k);}
726 #ifndef _LIBCPP_CXX03_LANG
728 template <class _Key, class _Compare, class _Allocator>
729 set<_Key, _Compare, _Allocator>::set(set&& __s, const allocator_type& __a)
730 : __tree_(_VSTD::move(__s.__tree_), __a)
732 if (__a != __s.get_allocator())
734 const_iterator __e = cend();
736 insert(__e, _VSTD::move(__s.__tree_.remove(__s.begin())->__value_));
740 #endif // _LIBCPP_CXX03_LANG
742 template <class _Key, class _Compare, class _Allocator>
743 inline _LIBCPP_INLINE_VISIBILITY
745 operator==(const set<_Key, _Compare, _Allocator>& __x,
746 const set<_Key, _Compare, _Allocator>& __y)
748 return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin());
751 template <class _Key, class _Compare, class _Allocator>
752 inline _LIBCPP_INLINE_VISIBILITY
754 operator< (const set<_Key, _Compare, _Allocator>& __x,
755 const set<_Key, _Compare, _Allocator>& __y)
757 return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
760 template <class _Key, class _Compare, class _Allocator>
761 inline _LIBCPP_INLINE_VISIBILITY
763 operator!=(const set<_Key, _Compare, _Allocator>& __x,
764 const set<_Key, _Compare, _Allocator>& __y)
766 return !(__x == __y);
769 template <class _Key, class _Compare, class _Allocator>
770 inline _LIBCPP_INLINE_VISIBILITY
772 operator> (const set<_Key, _Compare, _Allocator>& __x,
773 const set<_Key, _Compare, _Allocator>& __y)
778 template <class _Key, class _Compare, class _Allocator>
779 inline _LIBCPP_INLINE_VISIBILITY
781 operator>=(const set<_Key, _Compare, _Allocator>& __x,
782 const set<_Key, _Compare, _Allocator>& __y)
787 template <class _Key, class _Compare, class _Allocator>
788 inline _LIBCPP_INLINE_VISIBILITY
790 operator<=(const set<_Key, _Compare, _Allocator>& __x,
791 const set<_Key, _Compare, _Allocator>& __y)
796 // specialized algorithms:
797 template <class _Key, class _Compare, class _Allocator>
798 inline _LIBCPP_INLINE_VISIBILITY
800 swap(set<_Key, _Compare, _Allocator>& __x,
801 set<_Key, _Compare, _Allocator>& __y)
802 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
807 template <class _Key, class _Compare = less<_Key>,
808 class _Allocator = allocator<_Key> >
809 class _LIBCPP_TEMPLATE_VIS multiset
813 typedef _Key key_type;
814 typedef key_type value_type;
815 typedef _Compare key_compare;
816 typedef key_compare value_compare;
817 typedef _Allocator allocator_type;
818 typedef value_type& reference;
819 typedef const value_type& const_reference;
821 static_assert((is_same<typename allocator_type::value_type, value_type>::value),
822 "Allocator::value_type must be same type as value_type");
825 typedef __tree<value_type, value_compare, allocator_type> __base;
826 typedef allocator_traits<allocator_type> __alloc_traits;
827 typedef typename __base::__node_holder __node_holder;
832 typedef typename __base::pointer pointer;
833 typedef typename __base::const_pointer const_pointer;
834 typedef typename __base::size_type size_type;
835 typedef typename __base::difference_type difference_type;
836 typedef typename __base::const_iterator iterator;
837 typedef typename __base::const_iterator const_iterator;
838 typedef _VSTD::reverse_iterator<iterator> reverse_iterator;
839 typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator;
841 // construct/copy/destroy:
842 _LIBCPP_INLINE_VISIBILITY
845 is_nothrow_default_constructible<allocator_type>::value &&
846 is_nothrow_default_constructible<key_compare>::value &&
847 is_nothrow_copy_constructible<key_compare>::value)
848 : __tree_(value_compare()) {}
850 _LIBCPP_INLINE_VISIBILITY
851 explicit multiset(const value_compare& __comp)
853 is_nothrow_default_constructible<allocator_type>::value &&
854 is_nothrow_copy_constructible<key_compare>::value)
857 _LIBCPP_INLINE_VISIBILITY
858 explicit multiset(const value_compare& __comp, const allocator_type& __a)
859 : __tree_(__comp, __a) {}
860 template <class _InputIterator>
861 _LIBCPP_INLINE_VISIBILITY
862 multiset(_InputIterator __f, _InputIterator __l,
863 const value_compare& __comp = value_compare())
869 #if _LIBCPP_STD_VER > 11
870 template <class _InputIterator>
871 _LIBCPP_INLINE_VISIBILITY
872 multiset(_InputIterator __f, _InputIterator __l, const allocator_type& __a)
873 : multiset(__f, __l, key_compare(), __a) {}
876 template <class _InputIterator>
877 _LIBCPP_INLINE_VISIBILITY
878 multiset(_InputIterator __f, _InputIterator __l,
879 const value_compare& __comp, const allocator_type& __a)
880 : __tree_(__comp, __a)
885 _LIBCPP_INLINE_VISIBILITY
886 multiset(const multiset& __s)
887 : __tree_(__s.__tree_.value_comp(),
888 __alloc_traits::select_on_container_copy_construction(__s.__tree_.__alloc()))
890 insert(__s.begin(), __s.end());
893 _LIBCPP_INLINE_VISIBILITY
894 multiset& operator=(const multiset& __s)
896 __tree_ = __s.__tree_;
900 #ifndef _LIBCPP_CXX03_LANG
901 _LIBCPP_INLINE_VISIBILITY
902 multiset(multiset&& __s)
903 _NOEXCEPT_(is_nothrow_move_constructible<__base>::value)
904 : __tree_(_VSTD::move(__s.__tree_)) {}
906 multiset(multiset&& __s, const allocator_type& __a);
907 #endif // _LIBCPP_CXX03_LANG
908 _LIBCPP_INLINE_VISIBILITY
909 explicit multiset(const allocator_type& __a)
911 _LIBCPP_INLINE_VISIBILITY
912 multiset(const multiset& __s, const allocator_type& __a)
913 : __tree_(__s.__tree_.value_comp(), __a)
915 insert(__s.begin(), __s.end());
918 #ifndef _LIBCPP_CXX03_LANG
919 _LIBCPP_INLINE_VISIBILITY
920 multiset(initializer_list<value_type> __il, const value_compare& __comp = value_compare())
923 insert(__il.begin(), __il.end());
926 _LIBCPP_INLINE_VISIBILITY
927 multiset(initializer_list<value_type> __il, const value_compare& __comp,
928 const allocator_type& __a)
929 : __tree_(__comp, __a)
931 insert(__il.begin(), __il.end());
934 #if _LIBCPP_STD_VER > 11
935 _LIBCPP_INLINE_VISIBILITY
936 multiset(initializer_list<value_type> __il, const allocator_type& __a)
937 : multiset(__il, key_compare(), __a) {}
940 _LIBCPP_INLINE_VISIBILITY
941 multiset& operator=(initializer_list<value_type> __il)
943 __tree_.__assign_multi(__il.begin(), __il.end());
947 _LIBCPP_INLINE_VISIBILITY
948 multiset& operator=(multiset&& __s)
949 _NOEXCEPT_(is_nothrow_move_assignable<__base>::value)
951 __tree_ = _VSTD::move(__s.__tree_);
954 #endif // _LIBCPP_CXX03_LANG
956 _LIBCPP_INLINE_VISIBILITY
957 iterator begin() _NOEXCEPT {return __tree_.begin();}
958 _LIBCPP_INLINE_VISIBILITY
959 const_iterator begin() const _NOEXCEPT {return __tree_.begin();}
960 _LIBCPP_INLINE_VISIBILITY
961 iterator end() _NOEXCEPT {return __tree_.end();}
962 _LIBCPP_INLINE_VISIBILITY
963 const_iterator end() const _NOEXCEPT {return __tree_.end();}
965 _LIBCPP_INLINE_VISIBILITY
966 reverse_iterator rbegin() _NOEXCEPT
967 {return reverse_iterator(end());}
968 _LIBCPP_INLINE_VISIBILITY
969 const_reverse_iterator rbegin() const _NOEXCEPT
970 {return const_reverse_iterator(end());}
971 _LIBCPP_INLINE_VISIBILITY
972 reverse_iterator rend() _NOEXCEPT
973 {return reverse_iterator(begin());}
974 _LIBCPP_INLINE_VISIBILITY
975 const_reverse_iterator rend() const _NOEXCEPT
976 {return const_reverse_iterator(begin());}
978 _LIBCPP_INLINE_VISIBILITY
979 const_iterator cbegin() const _NOEXCEPT {return begin();}
980 _LIBCPP_INLINE_VISIBILITY
981 const_iterator cend() const _NOEXCEPT {return end();}
982 _LIBCPP_INLINE_VISIBILITY
983 const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();}
984 _LIBCPP_INLINE_VISIBILITY
985 const_reverse_iterator crend() const _NOEXCEPT {return rend();}
987 _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY
988 bool empty() const _NOEXCEPT {return __tree_.size() == 0;}
989 _LIBCPP_INLINE_VISIBILITY
990 size_type size() const _NOEXCEPT {return __tree_.size();}
991 _LIBCPP_INLINE_VISIBILITY
992 size_type max_size() const _NOEXCEPT {return __tree_.max_size();}
995 #ifndef _LIBCPP_CXX03_LANG
996 template <class... _Args>
997 _LIBCPP_INLINE_VISIBILITY
998 iterator emplace(_Args&&... __args)
999 {return __tree_.__emplace_multi(_VSTD::forward<_Args>(__args)...);}
1000 template <class... _Args>
1001 _LIBCPP_INLINE_VISIBILITY
1002 iterator emplace_hint(const_iterator __p, _Args&&... __args)
1003 {return __tree_.__emplace_hint_multi(__p, _VSTD::forward<_Args>(__args)...);}
1004 #endif // _LIBCPP_CXX03_LANG
1006 _LIBCPP_INLINE_VISIBILITY
1007 iterator insert(const value_type& __v)
1008 {return __tree_.__insert_multi(__v);}
1009 _LIBCPP_INLINE_VISIBILITY
1010 iterator insert(const_iterator __p, const value_type& __v)
1011 {return __tree_.__insert_multi(__p, __v);}
1013 template <class _InputIterator>
1014 _LIBCPP_INLINE_VISIBILITY
1015 void insert(_InputIterator __f, _InputIterator __l)
1017 for (const_iterator __e = cend(); __f != __l; ++__f)
1018 __tree_.__insert_multi(__e, *__f);
1021 #ifndef _LIBCPP_CXX03_LANG
1022 _LIBCPP_INLINE_VISIBILITY
1023 iterator insert(value_type&& __v)
1024 {return __tree_.__insert_multi(_VSTD::move(__v));}
1026 _LIBCPP_INLINE_VISIBILITY
1027 iterator insert(const_iterator __p, value_type&& __v)
1028 {return __tree_.__insert_multi(__p, _VSTD::move(__v));}
1030 _LIBCPP_INLINE_VISIBILITY
1031 void insert(initializer_list<value_type> __il)
1032 {insert(__il.begin(), __il.end());}
1033 #endif // _LIBCPP_CXX03_LANG
1035 _LIBCPP_INLINE_VISIBILITY
1036 iterator erase(const_iterator __p) {return __tree_.erase(__p);}
1037 _LIBCPP_INLINE_VISIBILITY
1038 size_type erase(const key_type& __k) {return __tree_.__erase_multi(__k);}
1039 _LIBCPP_INLINE_VISIBILITY
1040 iterator erase(const_iterator __f, const_iterator __l)
1041 {return __tree_.erase(__f, __l);}
1042 _LIBCPP_INLINE_VISIBILITY
1043 void clear() _NOEXCEPT {__tree_.clear();}
1045 _LIBCPP_INLINE_VISIBILITY
1046 void swap(multiset& __s)
1047 _NOEXCEPT_(__is_nothrow_swappable<__base>::value)
1048 {__tree_.swap(__s.__tree_);}
1050 _LIBCPP_INLINE_VISIBILITY
1051 allocator_type get_allocator() const _NOEXCEPT {return __tree_.__alloc();}
1052 _LIBCPP_INLINE_VISIBILITY
1053 key_compare key_comp() const {return __tree_.value_comp();}
1054 _LIBCPP_INLINE_VISIBILITY
1055 value_compare value_comp() const {return __tree_.value_comp();}
1058 _LIBCPP_INLINE_VISIBILITY
1059 iterator find(const key_type& __k) {return __tree_.find(__k);}
1060 _LIBCPP_INLINE_VISIBILITY
1061 const_iterator find(const key_type& __k) const {return __tree_.find(__k);}
1062 #if _LIBCPP_STD_VER > 11
1063 template <typename _K2>
1064 _LIBCPP_INLINE_VISIBILITY
1065 typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,iterator>::type
1066 find(const _K2& __k) {return __tree_.find(__k);}
1067 template <typename _K2>
1068 _LIBCPP_INLINE_VISIBILITY
1069 typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,const_iterator>::type
1070 find(const _K2& __k) const {return __tree_.find(__k);}
1073 _LIBCPP_INLINE_VISIBILITY
1074 size_type count(const key_type& __k) const
1075 {return __tree_.__count_multi(__k);}
1076 #if _LIBCPP_STD_VER > 11
1077 template <typename _K2>
1078 _LIBCPP_INLINE_VISIBILITY
1079 typename enable_if<__is_transparent<_Compare, _K2>::value,size_type>::type
1080 count(const _K2& __k) {return __tree_.__count_multi(__k);}
1083 _LIBCPP_INLINE_VISIBILITY
1084 iterator lower_bound(const key_type& __k)
1085 {return __tree_.lower_bound(__k);}
1086 _LIBCPP_INLINE_VISIBILITY
1087 const_iterator lower_bound(const key_type& __k) const
1088 {return __tree_.lower_bound(__k);}
1089 #if _LIBCPP_STD_VER > 11
1090 template <typename _K2>
1091 _LIBCPP_INLINE_VISIBILITY
1092 typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,iterator>::type
1093 lower_bound(const _K2& __k) {return __tree_.lower_bound(__k);}
1095 template <typename _K2>
1096 _LIBCPP_INLINE_VISIBILITY
1097 typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,const_iterator>::type
1098 lower_bound(const _K2& __k) const {return __tree_.lower_bound(__k);}
1101 _LIBCPP_INLINE_VISIBILITY
1102 iterator upper_bound(const key_type& __k)
1103 {return __tree_.upper_bound(__k);}
1104 _LIBCPP_INLINE_VISIBILITY
1105 const_iterator upper_bound(const key_type& __k) const
1106 {return __tree_.upper_bound(__k);}
1107 #if _LIBCPP_STD_VER > 11
1108 template <typename _K2>
1109 _LIBCPP_INLINE_VISIBILITY
1110 typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,iterator>::type
1111 upper_bound(const _K2& __k) {return __tree_.upper_bound(__k);}
1112 template <typename _K2>
1113 _LIBCPP_INLINE_VISIBILITY
1114 typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,const_iterator>::type
1115 upper_bound(const _K2& __k) const {return __tree_.upper_bound(__k);}
1118 _LIBCPP_INLINE_VISIBILITY
1119 pair<iterator,iterator> equal_range(const key_type& __k)
1120 {return __tree_.__equal_range_multi(__k);}
1121 _LIBCPP_INLINE_VISIBILITY
1122 pair<const_iterator,const_iterator> equal_range(const key_type& __k) const
1123 {return __tree_.__equal_range_multi(__k);}
1124 #if _LIBCPP_STD_VER > 11
1125 template <typename _K2>
1126 _LIBCPP_INLINE_VISIBILITY
1127 typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,pair<iterator,iterator>>::type
1128 equal_range(const _K2& __k) {return __tree_.__equal_range_multi(__k);}
1129 template <typename _K2>
1130 _LIBCPP_INLINE_VISIBILITY
1131 typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,pair<const_iterator,const_iterator>>::type
1132 equal_range(const _K2& __k) const {return __tree_.__equal_range_multi(__k);}
1136 #ifndef _LIBCPP_CXX03_LANG
1138 template <class _Key, class _Compare, class _Allocator>
1139 multiset<_Key, _Compare, _Allocator>::multiset(multiset&& __s, const allocator_type& __a)
1140 : __tree_(_VSTD::move(__s.__tree_), __a)
1142 if (__a != __s.get_allocator())
1144 const_iterator __e = cend();
1145 while (!__s.empty())
1146 insert(__e, _VSTD::move(__s.__tree_.remove(__s.begin())->__value_));
1150 #endif // _LIBCPP_CXX03_LANG
1152 template <class _Key, class _Compare, class _Allocator>
1153 inline _LIBCPP_INLINE_VISIBILITY
1155 operator==(const multiset<_Key, _Compare, _Allocator>& __x,
1156 const multiset<_Key, _Compare, _Allocator>& __y)
1158 return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin());
1161 template <class _Key, class _Compare, class _Allocator>
1162 inline _LIBCPP_INLINE_VISIBILITY
1164 operator< (const multiset<_Key, _Compare, _Allocator>& __x,
1165 const multiset<_Key, _Compare, _Allocator>& __y)
1167 return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
1170 template <class _Key, class _Compare, class _Allocator>
1171 inline _LIBCPP_INLINE_VISIBILITY
1173 operator!=(const multiset<_Key, _Compare, _Allocator>& __x,
1174 const multiset<_Key, _Compare, _Allocator>& __y)
1176 return !(__x == __y);
1179 template <class _Key, class _Compare, class _Allocator>
1180 inline _LIBCPP_INLINE_VISIBILITY
1182 operator> (const multiset<_Key, _Compare, _Allocator>& __x,
1183 const multiset<_Key, _Compare, _Allocator>& __y)
1188 template <class _Key, class _Compare, class _Allocator>
1189 inline _LIBCPP_INLINE_VISIBILITY
1191 operator>=(const multiset<_Key, _Compare, _Allocator>& __x,
1192 const multiset<_Key, _Compare, _Allocator>& __y)
1194 return !(__x < __y);
1197 template <class _Key, class _Compare, class _Allocator>
1198 inline _LIBCPP_INLINE_VISIBILITY
1200 operator<=(const multiset<_Key, _Compare, _Allocator>& __x,
1201 const multiset<_Key, _Compare, _Allocator>& __y)
1203 return !(__y < __x);
1206 template <class _Key, class _Compare, class _Allocator>
1207 inline _LIBCPP_INLINE_VISIBILITY
1209 swap(multiset<_Key, _Compare, _Allocator>& __x,
1210 multiset<_Key, _Compare, _Allocator>& __y)
1211 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
1216 _LIBCPP_END_NAMESPACE_STD
1218 #endif // _LIBCPP_SET