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_HAS_NO_RVALUE_REFERENCES
490 _LIBCPP_INLINE_VISIBILITY
492 _NOEXCEPT_(is_nothrow_move_constructible<__base>::value)
493 : __tree_(_VSTD::move(__s.__tree_)) {}
494 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
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_HAS_NO_RVALUE_REFERENCES
508 set(set&& __s, const allocator_type& __a);
511 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
512 _LIBCPP_INLINE_VISIBILITY
513 set(initializer_list<value_type> __il, const value_compare& __comp = value_compare())
516 insert(__il.begin(), __il.end());
519 _LIBCPP_INLINE_VISIBILITY
520 set(initializer_list<value_type> __il, const value_compare& __comp,
521 const allocator_type& __a)
522 : __tree_(__comp, __a)
524 insert(__il.begin(), __il.end());
527 #if _LIBCPP_STD_VER > 11
528 _LIBCPP_INLINE_VISIBILITY
529 set(initializer_list<value_type> __il, const allocator_type& __a)
530 : set(__il, key_compare(), __a) {}
533 _LIBCPP_INLINE_VISIBILITY
534 set& operator=(initializer_list<value_type> __il)
536 __tree_.__assign_unique(__il.begin(), __il.end());
539 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
541 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
542 _LIBCPP_INLINE_VISIBILITY
543 set& operator=(set&& __s)
544 _NOEXCEPT_(is_nothrow_move_assignable<__base>::value)
546 __tree_ = _VSTD::move(__s.__tree_);
549 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
551 _LIBCPP_INLINE_VISIBILITY
552 iterator begin() _NOEXCEPT {return __tree_.begin();}
553 _LIBCPP_INLINE_VISIBILITY
554 const_iterator begin() const _NOEXCEPT {return __tree_.begin();}
555 _LIBCPP_INLINE_VISIBILITY
556 iterator end() _NOEXCEPT {return __tree_.end();}
557 _LIBCPP_INLINE_VISIBILITY
558 const_iterator end() const _NOEXCEPT {return __tree_.end();}
560 _LIBCPP_INLINE_VISIBILITY
561 reverse_iterator rbegin() _NOEXCEPT
562 {return reverse_iterator(end());}
563 _LIBCPP_INLINE_VISIBILITY
564 const_reverse_iterator rbegin() const _NOEXCEPT
565 {return const_reverse_iterator(end());}
566 _LIBCPP_INLINE_VISIBILITY
567 reverse_iterator rend() _NOEXCEPT
568 {return reverse_iterator(begin());}
569 _LIBCPP_INLINE_VISIBILITY
570 const_reverse_iterator rend() const _NOEXCEPT
571 {return const_reverse_iterator(begin());}
573 _LIBCPP_INLINE_VISIBILITY
574 const_iterator cbegin() const _NOEXCEPT {return begin();}
575 _LIBCPP_INLINE_VISIBILITY
576 const_iterator cend() const _NOEXCEPT {return end();}
577 _LIBCPP_INLINE_VISIBILITY
578 const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();}
579 _LIBCPP_INLINE_VISIBILITY
580 const_reverse_iterator crend() const _NOEXCEPT {return rend();}
582 _LIBCPP_INLINE_VISIBILITY
583 bool empty() const _NOEXCEPT {return __tree_.size() == 0;}
584 _LIBCPP_INLINE_VISIBILITY
585 size_type size() const _NOEXCEPT {return __tree_.size();}
586 _LIBCPP_INLINE_VISIBILITY
587 size_type max_size() const _NOEXCEPT {return __tree_.max_size();}
590 #if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
591 template <class... _Args>
592 _LIBCPP_INLINE_VISIBILITY
593 pair<iterator, bool> emplace(_Args&&... __args)
594 {return __tree_.__emplace_unique(_VSTD::forward<_Args>(__args)...);}
595 template <class... _Args>
596 _LIBCPP_INLINE_VISIBILITY
597 iterator emplace_hint(const_iterator __p, _Args&&... __args)
598 {return __tree_.__emplace_hint_unique(__p, _VSTD::forward<_Args>(__args)...);}
599 #endif // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
600 _LIBCPP_INLINE_VISIBILITY
601 pair<iterator,bool> insert(const value_type& __v)
602 {return __tree_.__insert_unique(__v);}
603 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
604 _LIBCPP_INLINE_VISIBILITY
605 pair<iterator,bool> insert(value_type&& __v)
606 {return __tree_.__insert_unique(_VSTD::move(__v));}
607 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
608 _LIBCPP_INLINE_VISIBILITY
609 iterator insert(const_iterator __p, const value_type& __v)
610 {return __tree_.__insert_unique(__p, __v);}
611 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
612 _LIBCPP_INLINE_VISIBILITY
613 iterator insert(const_iterator __p, value_type&& __v)
614 {return __tree_.__insert_unique(__p, _VSTD::move(__v));}
615 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
616 template <class _InputIterator>
617 _LIBCPP_INLINE_VISIBILITY
618 void insert(_InputIterator __f, _InputIterator __l)
620 for (const_iterator __e = cend(); __f != __l; ++__f)
621 __tree_.__insert_unique(__e, *__f);
624 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
625 _LIBCPP_INLINE_VISIBILITY
626 void insert(initializer_list<value_type> __il)
627 {insert(__il.begin(), __il.end());}
628 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
630 _LIBCPP_INLINE_VISIBILITY
631 iterator erase(const_iterator __p) {return __tree_.erase(__p);}
632 _LIBCPP_INLINE_VISIBILITY
633 size_type erase(const key_type& __k)
634 {return __tree_.__erase_unique(__k);}
635 _LIBCPP_INLINE_VISIBILITY
636 iterator erase(const_iterator __f, const_iterator __l)
637 {return __tree_.erase(__f, __l);}
638 _LIBCPP_INLINE_VISIBILITY
639 void clear() _NOEXCEPT {__tree_.clear();}
641 _LIBCPP_INLINE_VISIBILITY
642 void swap(set& __s) _NOEXCEPT_(__is_nothrow_swappable<__base>::value)
643 {__tree_.swap(__s.__tree_);}
645 _LIBCPP_INLINE_VISIBILITY
646 allocator_type get_allocator() const _NOEXCEPT {return __tree_.__alloc();}
647 _LIBCPP_INLINE_VISIBILITY
648 key_compare key_comp() const {return __tree_.value_comp();}
649 _LIBCPP_INLINE_VISIBILITY
650 value_compare value_comp() const {return __tree_.value_comp();}
653 _LIBCPP_INLINE_VISIBILITY
654 iterator find(const key_type& __k) {return __tree_.find(__k);}
655 _LIBCPP_INLINE_VISIBILITY
656 const_iterator find(const key_type& __k) const {return __tree_.find(__k);}
657 #if _LIBCPP_STD_VER > 11
658 template <typename _K2>
659 _LIBCPP_INLINE_VISIBILITY
660 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
661 find(const _K2& __k) {return __tree_.find(__k);}
662 template <typename _K2>
663 _LIBCPP_INLINE_VISIBILITY
664 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
665 find(const _K2& __k) const {return __tree_.find(__k);}
668 _LIBCPP_INLINE_VISIBILITY
669 size_type count(const key_type& __k) const
670 {return __tree_.__count_unique(__k);}
671 #if _LIBCPP_STD_VER > 11
672 template <typename _K2>
673 _LIBCPP_INLINE_VISIBILITY
674 typename enable_if<__is_transparent<_Compare, _K2>::value,size_type>::type
675 count(const _K2& __k) const {return __tree_.__count_unique(__k);}
677 _LIBCPP_INLINE_VISIBILITY
678 iterator lower_bound(const key_type& __k)
679 {return __tree_.lower_bound(__k);}
680 _LIBCPP_INLINE_VISIBILITY
681 const_iterator lower_bound(const key_type& __k) const
682 {return __tree_.lower_bound(__k);}
683 #if _LIBCPP_STD_VER > 11
684 template <typename _K2>
685 _LIBCPP_INLINE_VISIBILITY
686 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
687 lower_bound(const _K2& __k) {return __tree_.lower_bound(__k);}
689 template <typename _K2>
690 _LIBCPP_INLINE_VISIBILITY
691 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
692 lower_bound(const _K2& __k) const {return __tree_.lower_bound(__k);}
695 _LIBCPP_INLINE_VISIBILITY
696 iterator upper_bound(const key_type& __k)
697 {return __tree_.upper_bound(__k);}
698 _LIBCPP_INLINE_VISIBILITY
699 const_iterator upper_bound(const key_type& __k) const
700 {return __tree_.upper_bound(__k);}
701 #if _LIBCPP_STD_VER > 11
702 template <typename _K2>
703 _LIBCPP_INLINE_VISIBILITY
704 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
705 upper_bound(const _K2& __k) {return __tree_.upper_bound(__k);}
706 template <typename _K2>
707 _LIBCPP_INLINE_VISIBILITY
708 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
709 upper_bound(const _K2& __k) const {return __tree_.upper_bound(__k);}
712 _LIBCPP_INLINE_VISIBILITY
713 pair<iterator,iterator> equal_range(const key_type& __k)
714 {return __tree_.__equal_range_unique(__k);}
715 _LIBCPP_INLINE_VISIBILITY
716 pair<const_iterator,const_iterator> equal_range(const key_type& __k) const
717 {return __tree_.__equal_range_unique(__k);}
718 #if _LIBCPP_STD_VER > 11
719 template <typename _K2>
720 _LIBCPP_INLINE_VISIBILITY
721 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<iterator,iterator>>::type
722 equal_range(const _K2& __k) {return __tree_.__equal_range_unique(__k);}
723 template <typename _K2>
724 _LIBCPP_INLINE_VISIBILITY
725 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<const_iterator,const_iterator>>::type
726 equal_range(const _K2& __k) const {return __tree_.__equal_range_unique(__k);}
730 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
732 template <class _Key, class _Compare, class _Allocator>
733 set<_Key, _Compare, _Allocator>::set(set&& __s, const allocator_type& __a)
734 : __tree_(_VSTD::move(__s.__tree_), __a)
736 if (__a != __s.get_allocator())
738 const_iterator __e = cend();
740 insert(__e, _VSTD::move(__s.__tree_.remove(__s.begin())->__value_));
744 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
746 template <class _Key, class _Compare, class _Allocator>
747 inline _LIBCPP_INLINE_VISIBILITY
749 operator==(const set<_Key, _Compare, _Allocator>& __x,
750 const set<_Key, _Compare, _Allocator>& __y)
752 return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin());
755 template <class _Key, class _Compare, class _Allocator>
756 inline _LIBCPP_INLINE_VISIBILITY
758 operator< (const set<_Key, _Compare, _Allocator>& __x,
759 const set<_Key, _Compare, _Allocator>& __y)
761 return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
764 template <class _Key, class _Compare, class _Allocator>
765 inline _LIBCPP_INLINE_VISIBILITY
767 operator!=(const set<_Key, _Compare, _Allocator>& __x,
768 const set<_Key, _Compare, _Allocator>& __y)
770 return !(__x == __y);
773 template <class _Key, class _Compare, class _Allocator>
774 inline _LIBCPP_INLINE_VISIBILITY
776 operator> (const set<_Key, _Compare, _Allocator>& __x,
777 const set<_Key, _Compare, _Allocator>& __y)
782 template <class _Key, class _Compare, class _Allocator>
783 inline _LIBCPP_INLINE_VISIBILITY
785 operator>=(const set<_Key, _Compare, _Allocator>& __x,
786 const set<_Key, _Compare, _Allocator>& __y)
791 template <class _Key, class _Compare, class _Allocator>
792 inline _LIBCPP_INLINE_VISIBILITY
794 operator<=(const set<_Key, _Compare, _Allocator>& __x,
795 const set<_Key, _Compare, _Allocator>& __y)
800 // specialized algorithms:
801 template <class _Key, class _Compare, class _Allocator>
802 inline _LIBCPP_INLINE_VISIBILITY
804 swap(set<_Key, _Compare, _Allocator>& __x,
805 set<_Key, _Compare, _Allocator>& __y)
806 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
811 template <class _Key, class _Compare = less<_Key>,
812 class _Allocator = allocator<_Key> >
813 class _LIBCPP_TEMPLATE_VIS multiset
817 typedef _Key key_type;
818 typedef key_type value_type;
819 typedef _Compare key_compare;
820 typedef key_compare value_compare;
821 typedef _Allocator allocator_type;
822 typedef value_type& reference;
823 typedef const value_type& const_reference;
825 static_assert((is_same<typename allocator_type::value_type, value_type>::value),
826 "Allocator::value_type must be same type as value_type");
829 typedef __tree<value_type, value_compare, allocator_type> __base;
830 typedef allocator_traits<allocator_type> __alloc_traits;
831 typedef typename __base::__node_holder __node_holder;
836 typedef typename __base::pointer pointer;
837 typedef typename __base::const_pointer const_pointer;
838 typedef typename __base::size_type size_type;
839 typedef typename __base::difference_type difference_type;
840 typedef typename __base::const_iterator iterator;
841 typedef typename __base::const_iterator const_iterator;
842 typedef _VSTD::reverse_iterator<iterator> reverse_iterator;
843 typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator;
845 // construct/copy/destroy:
846 _LIBCPP_INLINE_VISIBILITY
849 is_nothrow_default_constructible<allocator_type>::value &&
850 is_nothrow_default_constructible<key_compare>::value &&
851 is_nothrow_copy_constructible<key_compare>::value)
852 : __tree_(value_compare()) {}
854 _LIBCPP_INLINE_VISIBILITY
855 explicit multiset(const value_compare& __comp)
857 is_nothrow_default_constructible<allocator_type>::value &&
858 is_nothrow_copy_constructible<key_compare>::value)
861 _LIBCPP_INLINE_VISIBILITY
862 explicit multiset(const value_compare& __comp, const allocator_type& __a)
863 : __tree_(__comp, __a) {}
864 template <class _InputIterator>
865 _LIBCPP_INLINE_VISIBILITY
866 multiset(_InputIterator __f, _InputIterator __l,
867 const value_compare& __comp = value_compare())
873 #if _LIBCPP_STD_VER > 11
874 template <class _InputIterator>
875 _LIBCPP_INLINE_VISIBILITY
876 multiset(_InputIterator __f, _InputIterator __l, const allocator_type& __a)
877 : multiset(__f, __l, key_compare(), __a) {}
880 template <class _InputIterator>
881 _LIBCPP_INLINE_VISIBILITY
882 multiset(_InputIterator __f, _InputIterator __l,
883 const value_compare& __comp, const allocator_type& __a)
884 : __tree_(__comp, __a)
889 _LIBCPP_INLINE_VISIBILITY
890 multiset(const multiset& __s)
891 : __tree_(__s.__tree_.value_comp(),
892 __alloc_traits::select_on_container_copy_construction(__s.__tree_.__alloc()))
894 insert(__s.begin(), __s.end());
897 _LIBCPP_INLINE_VISIBILITY
898 multiset& operator=(const multiset& __s)
900 __tree_ = __s.__tree_;
904 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
905 _LIBCPP_INLINE_VISIBILITY
906 multiset(multiset&& __s)
907 _NOEXCEPT_(is_nothrow_move_constructible<__base>::value)
908 : __tree_(_VSTD::move(__s.__tree_)) {}
909 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
910 _LIBCPP_INLINE_VISIBILITY
911 explicit multiset(const allocator_type& __a)
913 _LIBCPP_INLINE_VISIBILITY
914 multiset(const multiset& __s, const allocator_type& __a)
915 : __tree_(__s.__tree_.value_comp(), __a)
917 insert(__s.begin(), __s.end());
919 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
920 multiset(multiset&& __s, const allocator_type& __a);
923 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
924 _LIBCPP_INLINE_VISIBILITY
925 multiset(initializer_list<value_type> __il, const value_compare& __comp = value_compare())
928 insert(__il.begin(), __il.end());
931 _LIBCPP_INLINE_VISIBILITY
932 multiset(initializer_list<value_type> __il, const value_compare& __comp,
933 const allocator_type& __a)
934 : __tree_(__comp, __a)
936 insert(__il.begin(), __il.end());
939 #if _LIBCPP_STD_VER > 11
940 _LIBCPP_INLINE_VISIBILITY
941 multiset(initializer_list<value_type> __il, const allocator_type& __a)
942 : multiset(__il, key_compare(), __a) {}
945 _LIBCPP_INLINE_VISIBILITY
946 multiset& operator=(initializer_list<value_type> __il)
948 __tree_.__assign_multi(__il.begin(), __il.end());
951 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
953 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
954 _LIBCPP_INLINE_VISIBILITY
955 multiset& operator=(multiset&& __s)
956 _NOEXCEPT_(is_nothrow_move_assignable<__base>::value)
958 __tree_ = _VSTD::move(__s.__tree_);
961 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
963 _LIBCPP_INLINE_VISIBILITY
964 iterator begin() _NOEXCEPT {return __tree_.begin();}
965 _LIBCPP_INLINE_VISIBILITY
966 const_iterator begin() const _NOEXCEPT {return __tree_.begin();}
967 _LIBCPP_INLINE_VISIBILITY
968 iterator end() _NOEXCEPT {return __tree_.end();}
969 _LIBCPP_INLINE_VISIBILITY
970 const_iterator end() const _NOEXCEPT {return __tree_.end();}
972 _LIBCPP_INLINE_VISIBILITY
973 reverse_iterator rbegin() _NOEXCEPT
974 {return reverse_iterator(end());}
975 _LIBCPP_INLINE_VISIBILITY
976 const_reverse_iterator rbegin() const _NOEXCEPT
977 {return const_reverse_iterator(end());}
978 _LIBCPP_INLINE_VISIBILITY
979 reverse_iterator rend() _NOEXCEPT
980 {return reverse_iterator(begin());}
981 _LIBCPP_INLINE_VISIBILITY
982 const_reverse_iterator rend() const _NOEXCEPT
983 {return const_reverse_iterator(begin());}
985 _LIBCPP_INLINE_VISIBILITY
986 const_iterator cbegin() const _NOEXCEPT {return begin();}
987 _LIBCPP_INLINE_VISIBILITY
988 const_iterator cend() const _NOEXCEPT {return end();}
989 _LIBCPP_INLINE_VISIBILITY
990 const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();}
991 _LIBCPP_INLINE_VISIBILITY
992 const_reverse_iterator crend() const _NOEXCEPT {return rend();}
994 _LIBCPP_INLINE_VISIBILITY
995 bool empty() const _NOEXCEPT {return __tree_.size() == 0;}
996 _LIBCPP_INLINE_VISIBILITY
997 size_type size() const _NOEXCEPT {return __tree_.size();}
998 _LIBCPP_INLINE_VISIBILITY
999 size_type max_size() const _NOEXCEPT {return __tree_.max_size();}
1002 #if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
1003 template <class... _Args>
1004 _LIBCPP_INLINE_VISIBILITY
1005 iterator emplace(_Args&&... __args)
1006 {return __tree_.__emplace_multi(_VSTD::forward<_Args>(__args)...);}
1007 template <class... _Args>
1008 _LIBCPP_INLINE_VISIBILITY
1009 iterator emplace_hint(const_iterator __p, _Args&&... __args)
1010 {return __tree_.__emplace_hint_multi(__p, _VSTD::forward<_Args>(__args)...);}
1011 #endif // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
1012 _LIBCPP_INLINE_VISIBILITY
1013 iterator insert(const value_type& __v)
1014 {return __tree_.__insert_multi(__v);}
1015 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1016 _LIBCPP_INLINE_VISIBILITY
1017 iterator insert(value_type&& __v)
1018 {return __tree_.__insert_multi(_VSTD::move(__v));}
1019 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1020 _LIBCPP_INLINE_VISIBILITY
1021 iterator insert(const_iterator __p, const value_type& __v)
1022 {return __tree_.__insert_multi(__p, __v);}
1023 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1024 _LIBCPP_INLINE_VISIBILITY
1025 iterator insert(const_iterator __p, value_type&& __v)
1026 {return __tree_.__insert_multi(__p, _VSTD::move(__v));}
1027 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1028 template <class _InputIterator>
1029 _LIBCPP_INLINE_VISIBILITY
1030 void insert(_InputIterator __f, _InputIterator __l)
1032 for (const_iterator __e = cend(); __f != __l; ++__f)
1033 __tree_.__insert_multi(__e, *__f);
1036 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1037 _LIBCPP_INLINE_VISIBILITY
1038 void insert(initializer_list<value_type> __il)
1039 {insert(__il.begin(), __il.end());}
1040 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1042 _LIBCPP_INLINE_VISIBILITY
1043 iterator erase(const_iterator __p) {return __tree_.erase(__p);}
1044 _LIBCPP_INLINE_VISIBILITY
1045 size_type erase(const key_type& __k) {return __tree_.__erase_multi(__k);}
1046 _LIBCPP_INLINE_VISIBILITY
1047 iterator erase(const_iterator __f, const_iterator __l)
1048 {return __tree_.erase(__f, __l);}
1049 _LIBCPP_INLINE_VISIBILITY
1050 void clear() _NOEXCEPT {__tree_.clear();}
1052 _LIBCPP_INLINE_VISIBILITY
1053 void swap(multiset& __s)
1054 _NOEXCEPT_(__is_nothrow_swappable<__base>::value)
1055 {__tree_.swap(__s.__tree_);}
1057 _LIBCPP_INLINE_VISIBILITY
1058 allocator_type get_allocator() const _NOEXCEPT {return __tree_.__alloc();}
1059 _LIBCPP_INLINE_VISIBILITY
1060 key_compare key_comp() const {return __tree_.value_comp();}
1061 _LIBCPP_INLINE_VISIBILITY
1062 value_compare value_comp() const {return __tree_.value_comp();}
1065 _LIBCPP_INLINE_VISIBILITY
1066 iterator find(const key_type& __k) {return __tree_.find(__k);}
1067 _LIBCPP_INLINE_VISIBILITY
1068 const_iterator find(const key_type& __k) const {return __tree_.find(__k);}
1069 #if _LIBCPP_STD_VER > 11
1070 template <typename _K2>
1071 _LIBCPP_INLINE_VISIBILITY
1072 typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,iterator>::type
1073 find(const _K2& __k) {return __tree_.find(__k);}
1074 template <typename _K2>
1075 _LIBCPP_INLINE_VISIBILITY
1076 typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,const_iterator>::type
1077 find(const _K2& __k) const {return __tree_.find(__k);}
1080 _LIBCPP_INLINE_VISIBILITY
1081 size_type count(const key_type& __k) const
1082 {return __tree_.__count_multi(__k);}
1083 #if _LIBCPP_STD_VER > 11
1084 template <typename _K2>
1085 _LIBCPP_INLINE_VISIBILITY
1086 typename enable_if<__is_transparent<_Compare, _K2>::value,size_type>::type
1087 count(const _K2& __k) {return __tree_.__count_multi(__k);}
1090 _LIBCPP_INLINE_VISIBILITY
1091 iterator lower_bound(const key_type& __k)
1092 {return __tree_.lower_bound(__k);}
1093 _LIBCPP_INLINE_VISIBILITY
1094 const_iterator lower_bound(const key_type& __k) const
1095 {return __tree_.lower_bound(__k);}
1096 #if _LIBCPP_STD_VER > 11
1097 template <typename _K2>
1098 _LIBCPP_INLINE_VISIBILITY
1099 typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,iterator>::type
1100 lower_bound(const _K2& __k) {return __tree_.lower_bound(__k);}
1102 template <typename _K2>
1103 _LIBCPP_INLINE_VISIBILITY
1104 typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,const_iterator>::type
1105 lower_bound(const _K2& __k) const {return __tree_.lower_bound(__k);}
1108 _LIBCPP_INLINE_VISIBILITY
1109 iterator upper_bound(const key_type& __k)
1110 {return __tree_.upper_bound(__k);}
1111 _LIBCPP_INLINE_VISIBILITY
1112 const_iterator upper_bound(const key_type& __k) const
1113 {return __tree_.upper_bound(__k);}
1114 #if _LIBCPP_STD_VER > 11
1115 template <typename _K2>
1116 _LIBCPP_INLINE_VISIBILITY
1117 typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,iterator>::type
1118 upper_bound(const _K2& __k) {return __tree_.upper_bound(__k);}
1119 template <typename _K2>
1120 _LIBCPP_INLINE_VISIBILITY
1121 typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,const_iterator>::type
1122 upper_bound(const _K2& __k) const {return __tree_.upper_bound(__k);}
1125 _LIBCPP_INLINE_VISIBILITY
1126 pair<iterator,iterator> equal_range(const key_type& __k)
1127 {return __tree_.__equal_range_multi(__k);}
1128 _LIBCPP_INLINE_VISIBILITY
1129 pair<const_iterator,const_iterator> equal_range(const key_type& __k) const
1130 {return __tree_.__equal_range_multi(__k);}
1131 #if _LIBCPP_STD_VER > 11
1132 template <typename _K2>
1133 _LIBCPP_INLINE_VISIBILITY
1134 typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,pair<iterator,iterator>>::type
1135 equal_range(const _K2& __k) {return __tree_.__equal_range_multi(__k);}
1136 template <typename _K2>
1137 _LIBCPP_INLINE_VISIBILITY
1138 typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,pair<const_iterator,const_iterator>>::type
1139 equal_range(const _K2& __k) const {return __tree_.__equal_range_multi(__k);}
1143 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1145 template <class _Key, class _Compare, class _Allocator>
1146 multiset<_Key, _Compare, _Allocator>::multiset(multiset&& __s, const allocator_type& __a)
1147 : __tree_(_VSTD::move(__s.__tree_), __a)
1149 if (__a != __s.get_allocator())
1151 const_iterator __e = cend();
1152 while (!__s.empty())
1153 insert(__e, _VSTD::move(__s.__tree_.remove(__s.begin())->__value_));
1157 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1159 template <class _Key, class _Compare, class _Allocator>
1160 inline _LIBCPP_INLINE_VISIBILITY
1162 operator==(const multiset<_Key, _Compare, _Allocator>& __x,
1163 const multiset<_Key, _Compare, _Allocator>& __y)
1165 return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin());
1168 template <class _Key, class _Compare, class _Allocator>
1169 inline _LIBCPP_INLINE_VISIBILITY
1171 operator< (const multiset<_Key, _Compare, _Allocator>& __x,
1172 const multiset<_Key, _Compare, _Allocator>& __y)
1174 return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
1177 template <class _Key, class _Compare, class _Allocator>
1178 inline _LIBCPP_INLINE_VISIBILITY
1180 operator!=(const multiset<_Key, _Compare, _Allocator>& __x,
1181 const multiset<_Key, _Compare, _Allocator>& __y)
1183 return !(__x == __y);
1186 template <class _Key, class _Compare, class _Allocator>
1187 inline _LIBCPP_INLINE_VISIBILITY
1189 operator> (const multiset<_Key, _Compare, _Allocator>& __x,
1190 const multiset<_Key, _Compare, _Allocator>& __y)
1195 template <class _Key, class _Compare, class _Allocator>
1196 inline _LIBCPP_INLINE_VISIBILITY
1198 operator>=(const multiset<_Key, _Compare, _Allocator>& __x,
1199 const multiset<_Key, _Compare, _Allocator>& __y)
1201 return !(__x < __y);
1204 template <class _Key, class _Compare, class _Allocator>
1205 inline _LIBCPP_INLINE_VISIBILITY
1207 operator<=(const multiset<_Key, _Compare, _Allocator>& __x,
1208 const multiset<_Key, _Compare, _Allocator>& __y)
1210 return !(__y < __x);
1213 template <class _Key, class _Compare, class _Allocator>
1214 inline _LIBCPP_INLINE_VISIBILITY
1216 swap(multiset<_Key, _Compare, _Allocator>& __x,
1217 multiset<_Key, _Compare, _Allocator>& __y)
1218 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
1223 _LIBCPP_END_NAMESPACE_STD
1225 #endif // _LIBCPP_SET