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_TYPE_VIS_ONLY 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;
413 typedef __tree<value_type, value_compare, allocator_type> __base;
414 typedef allocator_traits<allocator_type> __alloc_traits;
415 typedef typename __base::__node_holder __node_holder;
420 typedef typename __base::pointer pointer;
421 typedef typename __base::const_pointer const_pointer;
422 typedef typename __base::size_type size_type;
423 typedef typename __base::difference_type difference_type;
424 typedef typename __base::const_iterator iterator;
425 typedef typename __base::const_iterator const_iterator;
426 typedef _VSTD::reverse_iterator<iterator> reverse_iterator;
427 typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator;
429 _LIBCPP_INLINE_VISIBILITY
432 is_nothrow_default_constructible<allocator_type>::value &&
433 is_nothrow_default_constructible<key_compare>::value &&
434 is_nothrow_copy_constructible<key_compare>::value)
435 : __tree_(value_compare()) {}
437 _LIBCPP_INLINE_VISIBILITY
438 explicit set(const value_compare& __comp)
440 is_nothrow_default_constructible<allocator_type>::value &&
441 is_nothrow_copy_constructible<key_compare>::value)
444 _LIBCPP_INLINE_VISIBILITY
445 explicit set(const value_compare& __comp, const allocator_type& __a)
446 : __tree_(__comp, __a) {}
447 template <class _InputIterator>
448 _LIBCPP_INLINE_VISIBILITY
449 set(_InputIterator __f, _InputIterator __l,
450 const value_compare& __comp = value_compare())
456 template <class _InputIterator>
457 _LIBCPP_INLINE_VISIBILITY
458 set(_InputIterator __f, _InputIterator __l, const value_compare& __comp,
459 const allocator_type& __a)
460 : __tree_(__comp, __a)
465 #if _LIBCPP_STD_VER > 11
466 template <class _InputIterator>
467 _LIBCPP_INLINE_VISIBILITY
468 set(_InputIterator __f, _InputIterator __l, const allocator_type& __a)
469 : set(__f, __l, key_compare(), __a) {}
472 _LIBCPP_INLINE_VISIBILITY
474 : __tree_(__s.__tree_)
476 insert(__s.begin(), __s.end());
479 _LIBCPP_INLINE_VISIBILITY
480 set& operator=(const set& __s)
482 __tree_ = __s.__tree_;
486 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
487 _LIBCPP_INLINE_VISIBILITY
489 _NOEXCEPT_(is_nothrow_move_constructible<__base>::value)
490 : __tree_(_VSTD::move(__s.__tree_)) {}
491 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
493 _LIBCPP_INLINE_VISIBILITY
494 explicit set(const allocator_type& __a)
497 _LIBCPP_INLINE_VISIBILITY
498 set(const set& __s, const allocator_type& __a)
499 : __tree_(__s.__tree_.value_comp(), __a)
501 insert(__s.begin(), __s.end());
504 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
505 set(set&& __s, const allocator_type& __a);
508 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
509 _LIBCPP_INLINE_VISIBILITY
510 set(initializer_list<value_type> __il, const value_compare& __comp = value_compare())
513 insert(__il.begin(), __il.end());
516 _LIBCPP_INLINE_VISIBILITY
517 set(initializer_list<value_type> __il, const value_compare& __comp,
518 const allocator_type& __a)
519 : __tree_(__comp, __a)
521 insert(__il.begin(), __il.end());
524 #if _LIBCPP_STD_VER > 11
525 _LIBCPP_INLINE_VISIBILITY
526 set(initializer_list<value_type> __il, const allocator_type& __a)
527 : set(__il, key_compare(), __a) {}
530 _LIBCPP_INLINE_VISIBILITY
531 set& operator=(initializer_list<value_type> __il)
533 __tree_.__assign_unique(__il.begin(), __il.end());
536 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
538 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
539 _LIBCPP_INLINE_VISIBILITY
540 set& operator=(set&& __s)
541 _NOEXCEPT_(is_nothrow_move_assignable<__base>::value)
543 __tree_ = _VSTD::move(__s.__tree_);
546 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
548 _LIBCPP_INLINE_VISIBILITY
549 iterator begin() _NOEXCEPT {return __tree_.begin();}
550 _LIBCPP_INLINE_VISIBILITY
551 const_iterator begin() const _NOEXCEPT {return __tree_.begin();}
552 _LIBCPP_INLINE_VISIBILITY
553 iterator end() _NOEXCEPT {return __tree_.end();}
554 _LIBCPP_INLINE_VISIBILITY
555 const_iterator end() const _NOEXCEPT {return __tree_.end();}
557 _LIBCPP_INLINE_VISIBILITY
558 reverse_iterator rbegin() _NOEXCEPT
559 {return reverse_iterator(end());}
560 _LIBCPP_INLINE_VISIBILITY
561 const_reverse_iterator rbegin() const _NOEXCEPT
562 {return const_reverse_iterator(end());}
563 _LIBCPP_INLINE_VISIBILITY
564 reverse_iterator rend() _NOEXCEPT
565 {return reverse_iterator(begin());}
566 _LIBCPP_INLINE_VISIBILITY
567 const_reverse_iterator rend() const _NOEXCEPT
568 {return const_reverse_iterator(begin());}
570 _LIBCPP_INLINE_VISIBILITY
571 const_iterator cbegin() const _NOEXCEPT {return begin();}
572 _LIBCPP_INLINE_VISIBILITY
573 const_iterator cend() const _NOEXCEPT {return end();}
574 _LIBCPP_INLINE_VISIBILITY
575 const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();}
576 _LIBCPP_INLINE_VISIBILITY
577 const_reverse_iterator crend() const _NOEXCEPT {return rend();}
579 _LIBCPP_INLINE_VISIBILITY
580 bool empty() const _NOEXCEPT {return __tree_.size() == 0;}
581 _LIBCPP_INLINE_VISIBILITY
582 size_type size() const _NOEXCEPT {return __tree_.size();}
583 _LIBCPP_INLINE_VISIBILITY
584 size_type max_size() const _NOEXCEPT {return __tree_.max_size();}
587 #if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
588 template <class... _Args>
589 _LIBCPP_INLINE_VISIBILITY
590 pair<iterator, bool> emplace(_Args&&... __args)
591 {return __tree_.__emplace_unique(_VSTD::forward<_Args>(__args)...);}
592 template <class... _Args>
593 _LIBCPP_INLINE_VISIBILITY
594 iterator emplace_hint(const_iterator __p, _Args&&... __args)
595 {return __tree_.__emplace_hint_unique(__p, _VSTD::forward<_Args>(__args)...);}
596 #endif // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
597 _LIBCPP_INLINE_VISIBILITY
598 pair<iterator,bool> insert(const value_type& __v)
599 {return __tree_.__insert_unique(__v);}
600 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
601 _LIBCPP_INLINE_VISIBILITY
602 pair<iterator,bool> insert(value_type&& __v)
603 {return __tree_.__insert_unique(_VSTD::move(__v));}
604 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
605 _LIBCPP_INLINE_VISIBILITY
606 iterator insert(const_iterator __p, const value_type& __v)
607 {return __tree_.__insert_unique(__p, __v);}
608 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
609 _LIBCPP_INLINE_VISIBILITY
610 iterator insert(const_iterator __p, value_type&& __v)
611 {return __tree_.__insert_unique(__p, _VSTD::move(__v));}
612 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
613 template <class _InputIterator>
614 _LIBCPP_INLINE_VISIBILITY
615 void insert(_InputIterator __f, _InputIterator __l)
617 for (const_iterator __e = cend(); __f != __l; ++__f)
618 __tree_.__insert_unique(__e, *__f);
621 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
622 _LIBCPP_INLINE_VISIBILITY
623 void insert(initializer_list<value_type> __il)
624 {insert(__il.begin(), __il.end());}
625 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
627 _LIBCPP_INLINE_VISIBILITY
628 iterator erase(const_iterator __p) {return __tree_.erase(__p);}
629 _LIBCPP_INLINE_VISIBILITY
630 size_type erase(const key_type& __k)
631 {return __tree_.__erase_unique(__k);}
632 _LIBCPP_INLINE_VISIBILITY
633 iterator erase(const_iterator __f, const_iterator __l)
634 {return __tree_.erase(__f, __l);}
635 _LIBCPP_INLINE_VISIBILITY
636 void clear() _NOEXCEPT {__tree_.clear();}
638 _LIBCPP_INLINE_VISIBILITY
639 void swap(set& __s) _NOEXCEPT_(__is_nothrow_swappable<__base>::value)
640 {__tree_.swap(__s.__tree_);}
642 _LIBCPP_INLINE_VISIBILITY
643 allocator_type get_allocator() const _NOEXCEPT {return __tree_.__alloc();}
644 _LIBCPP_INLINE_VISIBILITY
645 key_compare key_comp() const {return __tree_.value_comp();}
646 _LIBCPP_INLINE_VISIBILITY
647 value_compare value_comp() const {return __tree_.value_comp();}
650 _LIBCPP_INLINE_VISIBILITY
651 iterator find(const key_type& __k) {return __tree_.find(__k);}
652 _LIBCPP_INLINE_VISIBILITY
653 const_iterator find(const key_type& __k) const {return __tree_.find(__k);}
654 #if _LIBCPP_STD_VER > 11
655 template <typename _K2>
656 _LIBCPP_INLINE_VISIBILITY
657 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
658 find(const _K2& __k) {return __tree_.find(__k);}
659 template <typename _K2>
660 _LIBCPP_INLINE_VISIBILITY
661 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
662 find(const _K2& __k) const {return __tree_.find(__k);}
665 _LIBCPP_INLINE_VISIBILITY
666 size_type count(const key_type& __k) const
667 {return __tree_.__count_unique(__k);}
668 #if _LIBCPP_STD_VER > 11
669 template <typename _K2>
670 _LIBCPP_INLINE_VISIBILITY
671 typename enable_if<__is_transparent<_Compare, _K2>::value,size_type>::type
672 count(const _K2& __k) {return __tree_.__count_unique(__k);}
674 _LIBCPP_INLINE_VISIBILITY
675 iterator lower_bound(const key_type& __k)
676 {return __tree_.lower_bound(__k);}
677 _LIBCPP_INLINE_VISIBILITY
678 const_iterator lower_bound(const key_type& __k) const
679 {return __tree_.lower_bound(__k);}
680 #if _LIBCPP_STD_VER > 11
681 template <typename _K2>
682 _LIBCPP_INLINE_VISIBILITY
683 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
684 lower_bound(const _K2& __k) {return __tree_.lower_bound(__k);}
686 template <typename _K2>
687 _LIBCPP_INLINE_VISIBILITY
688 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
689 lower_bound(const _K2& __k) const {return __tree_.lower_bound(__k);}
692 _LIBCPP_INLINE_VISIBILITY
693 iterator upper_bound(const key_type& __k)
694 {return __tree_.upper_bound(__k);}
695 _LIBCPP_INLINE_VISIBILITY
696 const_iterator upper_bound(const key_type& __k) const
697 {return __tree_.upper_bound(__k);}
698 #if _LIBCPP_STD_VER > 11
699 template <typename _K2>
700 _LIBCPP_INLINE_VISIBILITY
701 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
702 upper_bound(const _K2& __k) {return __tree_.upper_bound(__k);}
703 template <typename _K2>
704 _LIBCPP_INLINE_VISIBILITY
705 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
706 upper_bound(const _K2& __k) const {return __tree_.upper_bound(__k);}
709 _LIBCPP_INLINE_VISIBILITY
710 pair<iterator,iterator> equal_range(const key_type& __k)
711 {return __tree_.__equal_range_unique(__k);}
712 _LIBCPP_INLINE_VISIBILITY
713 pair<const_iterator,const_iterator> equal_range(const key_type& __k) const
714 {return __tree_.__equal_range_unique(__k);}
715 #if _LIBCPP_STD_VER > 11
716 template <typename _K2>
717 _LIBCPP_INLINE_VISIBILITY
718 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<iterator,iterator>>::type
719 equal_range(const _K2& __k) {return __tree_.__equal_range_unique(__k);}
720 template <typename _K2>
721 _LIBCPP_INLINE_VISIBILITY
722 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<const_iterator,const_iterator>>::type
723 equal_range(const _K2& __k) const {return __tree_.__equal_range_unique(__k);}
727 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
729 template <class _Key, class _Compare, class _Allocator>
730 set<_Key, _Compare, _Allocator>::set(set&& __s, const allocator_type& __a)
731 : __tree_(_VSTD::move(__s.__tree_), __a)
733 if (__a != __s.get_allocator())
735 const_iterator __e = cend();
737 insert(__e, _VSTD::move(__s.__tree_.remove(__s.begin())->__value_));
741 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
743 template <class _Key, class _Compare, class _Allocator>
744 inline _LIBCPP_INLINE_VISIBILITY
746 operator==(const set<_Key, _Compare, _Allocator>& __x,
747 const set<_Key, _Compare, _Allocator>& __y)
749 return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin());
752 template <class _Key, class _Compare, class _Allocator>
753 inline _LIBCPP_INLINE_VISIBILITY
755 operator< (const set<_Key, _Compare, _Allocator>& __x,
756 const set<_Key, _Compare, _Allocator>& __y)
758 return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
761 template <class _Key, class _Compare, class _Allocator>
762 inline _LIBCPP_INLINE_VISIBILITY
764 operator!=(const set<_Key, _Compare, _Allocator>& __x,
765 const set<_Key, _Compare, _Allocator>& __y)
767 return !(__x == __y);
770 template <class _Key, class _Compare, class _Allocator>
771 inline _LIBCPP_INLINE_VISIBILITY
773 operator> (const set<_Key, _Compare, _Allocator>& __x,
774 const set<_Key, _Compare, _Allocator>& __y)
779 template <class _Key, class _Compare, class _Allocator>
780 inline _LIBCPP_INLINE_VISIBILITY
782 operator>=(const set<_Key, _Compare, _Allocator>& __x,
783 const set<_Key, _Compare, _Allocator>& __y)
788 template <class _Key, class _Compare, class _Allocator>
789 inline _LIBCPP_INLINE_VISIBILITY
791 operator<=(const set<_Key, _Compare, _Allocator>& __x,
792 const set<_Key, _Compare, _Allocator>& __y)
797 // specialized algorithms:
798 template <class _Key, class _Compare, class _Allocator>
799 inline _LIBCPP_INLINE_VISIBILITY
801 swap(set<_Key, _Compare, _Allocator>& __x,
802 set<_Key, _Compare, _Allocator>& __y)
803 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
808 template <class _Key, class _Compare = less<_Key>,
809 class _Allocator = allocator<_Key> >
810 class _LIBCPP_TYPE_VIS_ONLY multiset
814 typedef _Key key_type;
815 typedef key_type value_type;
816 typedef _Compare key_compare;
817 typedef key_compare value_compare;
818 typedef _Allocator allocator_type;
819 typedef value_type& reference;
820 typedef const value_type& const_reference;
823 typedef __tree<value_type, value_compare, allocator_type> __base;
824 typedef allocator_traits<allocator_type> __alloc_traits;
825 typedef typename __base::__node_holder __node_holder;
830 typedef typename __base::pointer pointer;
831 typedef typename __base::const_pointer const_pointer;
832 typedef typename __base::size_type size_type;
833 typedef typename __base::difference_type difference_type;
834 typedef typename __base::const_iterator iterator;
835 typedef typename __base::const_iterator const_iterator;
836 typedef _VSTD::reverse_iterator<iterator> reverse_iterator;
837 typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator;
839 // construct/copy/destroy:
840 _LIBCPP_INLINE_VISIBILITY
843 is_nothrow_default_constructible<allocator_type>::value &&
844 is_nothrow_default_constructible<key_compare>::value &&
845 is_nothrow_copy_constructible<key_compare>::value)
846 : __tree_(value_compare()) {}
848 _LIBCPP_INLINE_VISIBILITY
849 explicit multiset(const value_compare& __comp)
851 is_nothrow_default_constructible<allocator_type>::value &&
852 is_nothrow_copy_constructible<key_compare>::value)
855 _LIBCPP_INLINE_VISIBILITY
856 explicit multiset(const value_compare& __comp, const allocator_type& __a)
857 : __tree_(__comp, __a) {}
858 template <class _InputIterator>
859 _LIBCPP_INLINE_VISIBILITY
860 multiset(_InputIterator __f, _InputIterator __l,
861 const value_compare& __comp = value_compare())
867 #if _LIBCPP_STD_VER > 11
868 template <class _InputIterator>
869 _LIBCPP_INLINE_VISIBILITY
870 multiset(_InputIterator __f, _InputIterator __l, const allocator_type& __a)
871 : multiset(__f, __l, key_compare(), __a) {}
874 template <class _InputIterator>
875 _LIBCPP_INLINE_VISIBILITY
876 multiset(_InputIterator __f, _InputIterator __l,
877 const value_compare& __comp, const allocator_type& __a)
878 : __tree_(__comp, __a)
883 _LIBCPP_INLINE_VISIBILITY
884 multiset(const multiset& __s)
885 : __tree_(__s.__tree_.value_comp(),
886 __alloc_traits::select_on_container_copy_construction(__s.__tree_.__alloc()))
888 insert(__s.begin(), __s.end());
891 _LIBCPP_INLINE_VISIBILITY
892 multiset& operator=(const multiset& __s)
894 __tree_ = __s.__tree_;
898 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
899 _LIBCPP_INLINE_VISIBILITY
900 multiset(multiset&& __s)
901 _NOEXCEPT_(is_nothrow_move_constructible<__base>::value)
902 : __tree_(_VSTD::move(__s.__tree_)) {}
903 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
904 _LIBCPP_INLINE_VISIBILITY
905 explicit multiset(const allocator_type& __a)
907 _LIBCPP_INLINE_VISIBILITY
908 multiset(const multiset& __s, const allocator_type& __a)
909 : __tree_(__s.__tree_.value_comp(), __a)
911 insert(__s.begin(), __s.end());
913 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
914 multiset(multiset&& __s, const allocator_type& __a);
917 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
918 _LIBCPP_INLINE_VISIBILITY
919 multiset(initializer_list<value_type> __il, const value_compare& __comp = value_compare())
922 insert(__il.begin(), __il.end());
925 _LIBCPP_INLINE_VISIBILITY
926 multiset(initializer_list<value_type> __il, const value_compare& __comp,
927 const allocator_type& __a)
928 : __tree_(__comp, __a)
930 insert(__il.begin(), __il.end());
933 #if _LIBCPP_STD_VER > 11
934 _LIBCPP_INLINE_VISIBILITY
935 multiset(initializer_list<value_type> __il, const allocator_type& __a)
936 : multiset(__il, key_compare(), __a) {}
939 _LIBCPP_INLINE_VISIBILITY
940 multiset& operator=(initializer_list<value_type> __il)
942 __tree_.__assign_multi(__il.begin(), __il.end());
945 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
947 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
948 _LIBCPP_INLINE_VISIBILITY
949 multiset& operator=(multiset&& __s)
950 _NOEXCEPT_(is_nothrow_move_assignable<__base>::value)
952 __tree_ = _VSTD::move(__s.__tree_);
955 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
957 _LIBCPP_INLINE_VISIBILITY
958 iterator begin() _NOEXCEPT {return __tree_.begin();}
959 _LIBCPP_INLINE_VISIBILITY
960 const_iterator begin() const _NOEXCEPT {return __tree_.begin();}
961 _LIBCPP_INLINE_VISIBILITY
962 iterator end() _NOEXCEPT {return __tree_.end();}
963 _LIBCPP_INLINE_VISIBILITY
964 const_iterator end() const _NOEXCEPT {return __tree_.end();}
966 _LIBCPP_INLINE_VISIBILITY
967 reverse_iterator rbegin() _NOEXCEPT
968 {return reverse_iterator(end());}
969 _LIBCPP_INLINE_VISIBILITY
970 const_reverse_iterator rbegin() const _NOEXCEPT
971 {return const_reverse_iterator(end());}
972 _LIBCPP_INLINE_VISIBILITY
973 reverse_iterator rend() _NOEXCEPT
974 {return reverse_iterator(begin());}
975 _LIBCPP_INLINE_VISIBILITY
976 const_reverse_iterator rend() const _NOEXCEPT
977 {return const_reverse_iterator(begin());}
979 _LIBCPP_INLINE_VISIBILITY
980 const_iterator cbegin() const _NOEXCEPT {return begin();}
981 _LIBCPP_INLINE_VISIBILITY
982 const_iterator cend() const _NOEXCEPT {return end();}
983 _LIBCPP_INLINE_VISIBILITY
984 const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();}
985 _LIBCPP_INLINE_VISIBILITY
986 const_reverse_iterator crend() const _NOEXCEPT {return rend();}
988 _LIBCPP_INLINE_VISIBILITY
989 bool empty() const _NOEXCEPT {return __tree_.size() == 0;}
990 _LIBCPP_INLINE_VISIBILITY
991 size_type size() const _NOEXCEPT {return __tree_.size();}
992 _LIBCPP_INLINE_VISIBILITY
993 size_type max_size() const _NOEXCEPT {return __tree_.max_size();}
996 #if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
997 template <class... _Args>
998 _LIBCPP_INLINE_VISIBILITY
999 iterator emplace(_Args&&... __args)
1000 {return __tree_.__emplace_multi(_VSTD::forward<_Args>(__args)...);}
1001 template <class... _Args>
1002 _LIBCPP_INLINE_VISIBILITY
1003 iterator emplace_hint(const_iterator __p, _Args&&... __args)
1004 {return __tree_.__emplace_hint_multi(__p, _VSTD::forward<_Args>(__args)...);}
1005 #endif // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
1006 _LIBCPP_INLINE_VISIBILITY
1007 iterator insert(const value_type& __v)
1008 {return __tree_.__insert_multi(__v);}
1009 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1010 _LIBCPP_INLINE_VISIBILITY
1011 iterator insert(value_type&& __v)
1012 {return __tree_.__insert_multi(_VSTD::move(__v));}
1013 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1014 _LIBCPP_INLINE_VISIBILITY
1015 iterator insert(const_iterator __p, const value_type& __v)
1016 {return __tree_.__insert_multi(__p, __v);}
1017 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1018 _LIBCPP_INLINE_VISIBILITY
1019 iterator insert(const_iterator __p, value_type&& __v)
1020 {return __tree_.__insert_multi(_VSTD::move(__v));}
1021 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1022 template <class _InputIterator>
1023 _LIBCPP_INLINE_VISIBILITY
1024 void insert(_InputIterator __f, _InputIterator __l)
1026 for (const_iterator __e = cend(); __f != __l; ++__f)
1027 __tree_.__insert_multi(__e, *__f);
1030 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1031 _LIBCPP_INLINE_VISIBILITY
1032 void insert(initializer_list<value_type> __il)
1033 {insert(__il.begin(), __il.end());}
1034 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1036 _LIBCPP_INLINE_VISIBILITY
1037 iterator erase(const_iterator __p) {return __tree_.erase(__p);}
1038 _LIBCPP_INLINE_VISIBILITY
1039 size_type erase(const key_type& __k) {return __tree_.__erase_multi(__k);}
1040 _LIBCPP_INLINE_VISIBILITY
1041 iterator erase(const_iterator __f, const_iterator __l)
1042 {return __tree_.erase(__f, __l);}
1043 _LIBCPP_INLINE_VISIBILITY
1044 void clear() _NOEXCEPT {__tree_.clear();}
1046 _LIBCPP_INLINE_VISIBILITY
1047 void swap(multiset& __s)
1048 _NOEXCEPT_(__is_nothrow_swappable<__base>::value)
1049 {__tree_.swap(__s.__tree_);}
1051 _LIBCPP_INLINE_VISIBILITY
1052 allocator_type get_allocator() const _NOEXCEPT {return __tree_.__alloc();}
1053 _LIBCPP_INLINE_VISIBILITY
1054 key_compare key_comp() const {return __tree_.value_comp();}
1055 _LIBCPP_INLINE_VISIBILITY
1056 value_compare value_comp() const {return __tree_.value_comp();}
1059 _LIBCPP_INLINE_VISIBILITY
1060 iterator find(const key_type& __k) {return __tree_.find(__k);}
1061 _LIBCPP_INLINE_VISIBILITY
1062 const_iterator find(const key_type& __k) const {return __tree_.find(__k);}
1063 #if _LIBCPP_STD_VER > 11
1064 template <typename _K2>
1065 _LIBCPP_INLINE_VISIBILITY
1066 typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,iterator>::type
1067 find(const _K2& __k) {return __tree_.find(__k);}
1068 template <typename _K2>
1069 _LIBCPP_INLINE_VISIBILITY
1070 typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,const_iterator>::type
1071 find(const _K2& __k) const {return __tree_.find(__k);}
1074 _LIBCPP_INLINE_VISIBILITY
1075 size_type count(const key_type& __k) const
1076 {return __tree_.__count_multi(__k);}
1077 #if _LIBCPP_STD_VER > 11
1078 template <typename _K2>
1079 _LIBCPP_INLINE_VISIBILITY
1080 typename enable_if<__is_transparent<_Compare, _K2>::value,size_type>::type
1081 count(const _K2& __k) {return __tree_.__count_multi(__k);}
1084 _LIBCPP_INLINE_VISIBILITY
1085 iterator lower_bound(const key_type& __k)
1086 {return __tree_.lower_bound(__k);}
1087 _LIBCPP_INLINE_VISIBILITY
1088 const_iterator lower_bound(const key_type& __k) const
1089 {return __tree_.lower_bound(__k);}
1090 #if _LIBCPP_STD_VER > 11
1091 template <typename _K2>
1092 _LIBCPP_INLINE_VISIBILITY
1093 typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,iterator>::type
1094 lower_bound(const _K2& __k) {return __tree_.lower_bound(__k);}
1096 template <typename _K2>
1097 _LIBCPP_INLINE_VISIBILITY
1098 typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,const_iterator>::type
1099 lower_bound(const _K2& __k) const {return __tree_.lower_bound(__k);}
1102 _LIBCPP_INLINE_VISIBILITY
1103 iterator upper_bound(const key_type& __k)
1104 {return __tree_.upper_bound(__k);}
1105 _LIBCPP_INLINE_VISIBILITY
1106 const_iterator upper_bound(const key_type& __k) const
1107 {return __tree_.upper_bound(__k);}
1108 #if _LIBCPP_STD_VER > 11
1109 template <typename _K2>
1110 _LIBCPP_INLINE_VISIBILITY
1111 typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,iterator>::type
1112 upper_bound(const _K2& __k) {return __tree_.upper_bound(__k);}
1113 template <typename _K2>
1114 _LIBCPP_INLINE_VISIBILITY
1115 typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,const_iterator>::type
1116 upper_bound(const _K2& __k) const {return __tree_.upper_bound(__k);}
1119 _LIBCPP_INLINE_VISIBILITY
1120 pair<iterator,iterator> equal_range(const key_type& __k)
1121 {return __tree_.__equal_range_multi(__k);}
1122 _LIBCPP_INLINE_VISIBILITY
1123 pair<const_iterator,const_iterator> equal_range(const key_type& __k) const
1124 {return __tree_.__equal_range_multi(__k);}
1125 #if _LIBCPP_STD_VER > 11
1126 template <typename _K2>
1127 _LIBCPP_INLINE_VISIBILITY
1128 typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,pair<iterator,iterator>>::type
1129 equal_range(const _K2& __k) {return __tree_.__equal_range_multi(__k);}
1130 template <typename _K2>
1131 _LIBCPP_INLINE_VISIBILITY
1132 typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,pair<const_iterator,const_iterator>>::type
1133 equal_range(const _K2& __k) const {return __tree_.__equal_range_multi(__k);}
1137 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1139 template <class _Key, class _Compare, class _Allocator>
1140 multiset<_Key, _Compare, _Allocator>::multiset(multiset&& __s, const allocator_type& __a)
1141 : __tree_(_VSTD::move(__s.__tree_), __a)
1143 if (__a != __s.get_allocator())
1145 const_iterator __e = cend();
1146 while (!__s.empty())
1147 insert(__e, _VSTD::move(__s.__tree_.remove(__s.begin())->__value_));
1151 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1153 template <class _Key, class _Compare, class _Allocator>
1154 inline _LIBCPP_INLINE_VISIBILITY
1156 operator==(const multiset<_Key, _Compare, _Allocator>& __x,
1157 const multiset<_Key, _Compare, _Allocator>& __y)
1159 return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin());
1162 template <class _Key, class _Compare, class _Allocator>
1163 inline _LIBCPP_INLINE_VISIBILITY
1165 operator< (const multiset<_Key, _Compare, _Allocator>& __x,
1166 const multiset<_Key, _Compare, _Allocator>& __y)
1168 return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
1171 template <class _Key, class _Compare, class _Allocator>
1172 inline _LIBCPP_INLINE_VISIBILITY
1174 operator!=(const multiset<_Key, _Compare, _Allocator>& __x,
1175 const multiset<_Key, _Compare, _Allocator>& __y)
1177 return !(__x == __y);
1180 template <class _Key, class _Compare, class _Allocator>
1181 inline _LIBCPP_INLINE_VISIBILITY
1183 operator> (const multiset<_Key, _Compare, _Allocator>& __x,
1184 const multiset<_Key, _Compare, _Allocator>& __y)
1189 template <class _Key, class _Compare, class _Allocator>
1190 inline _LIBCPP_INLINE_VISIBILITY
1192 operator>=(const multiset<_Key, _Compare, _Allocator>& __x,
1193 const multiset<_Key, _Compare, _Allocator>& __y)
1195 return !(__x < __y);
1198 template <class _Key, class _Compare, class _Allocator>
1199 inline _LIBCPP_INLINE_VISIBILITY
1201 operator<=(const multiset<_Key, _Compare, _Allocator>& __x,
1202 const multiset<_Key, _Compare, _Allocator>& __y)
1204 return !(__y < __x);
1207 template <class _Key, class _Compare, class _Allocator>
1208 inline _LIBCPP_INLINE_VISIBILITY
1210 swap(multiset<_Key, _Compare, _Allocator>& __x,
1211 multiset<_Key, _Compare, _Allocator>& __y)
1212 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
1217 _LIBCPP_END_NAMESPACE_STD
1219 #endif // _LIBCPP_SET