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 size_type erase(const key_type& k);
120 iterator erase(const_iterator first, const_iterator last);
121 void clear() noexcept;
125 __is_nothrow_swappable<key_compare>::value &&
126 (!allocator_type::propagate_on_container_swap::value ||
127 __is_nothrow_swappable<allocator_type>::value));
130 allocator_type get_allocator() const noexcept;
131 key_compare key_comp() const;
132 value_compare value_comp() const;
135 iterator find(const key_type& k);
136 const_iterator find(const key_type& k) const;
138 iterator find(const K& x);
140 const_iterator find(const K& x) const; // C++14
142 size_type count(const K& x) const; // C++14
144 size_type count(const key_type& k) const;
145 iterator lower_bound(const key_type& k);
146 const_iterator lower_bound(const key_type& k) const;
148 iterator lower_bound(const K& x); // C++14
150 const_iterator lower_bound(const K& x) const; // C++14
152 iterator upper_bound(const key_type& k);
153 const_iterator upper_bound(const key_type& k) const;
155 iterator upper_bound(const K& x); // C++14
157 const_iterator upper_bound(const K& x) const; // C++14
158 pair<iterator,iterator> equal_range(const key_type& k);
159 pair<const_iterator,const_iterator> equal_range(const key_type& k) const;
161 pair<iterator,iterator> equal_range(const K& x); // C++14
163 pair<const_iterator,const_iterator> equal_range(const K& x) const; // C++14
166 template <class Key, class Compare, class Allocator>
168 operator==(const set<Key, Compare, Allocator>& x,
169 const set<Key, Compare, Allocator>& y);
171 template <class Key, class Compare, class Allocator>
173 operator< (const set<Key, Compare, Allocator>& x,
174 const set<Key, Compare, Allocator>& y);
176 template <class Key, class Compare, class Allocator>
178 operator!=(const set<Key, Compare, Allocator>& x,
179 const set<Key, Compare, Allocator>& y);
181 template <class Key, class Compare, class Allocator>
183 operator> (const set<Key, Compare, Allocator>& x,
184 const set<Key, Compare, Allocator>& y);
186 template <class Key, class Compare, class Allocator>
188 operator>=(const set<Key, Compare, Allocator>& x,
189 const set<Key, Compare, Allocator>& y);
191 template <class Key, class Compare, class Allocator>
193 operator<=(const set<Key, Compare, Allocator>& x,
194 const set<Key, Compare, Allocator>& y);
196 // specialized algorithms:
197 template <class Key, class Compare, class Allocator>
199 swap(set<Key, Compare, Allocator>& x, set<Key, Compare, Allocator>& y)
200 noexcept(noexcept(x.swap(y)));
202 template <class Key, class Compare = less<Key>,
203 class Allocator = allocator<Key>>
208 typedef Key key_type;
209 typedef key_type value_type;
210 typedef Compare key_compare;
211 typedef key_compare value_compare;
212 typedef Allocator allocator_type;
213 typedef typename allocator_type::reference reference;
214 typedef typename allocator_type::const_reference const_reference;
215 typedef typename allocator_type::size_type size_type;
216 typedef typename allocator_type::difference_type difference_type;
217 typedef typename allocator_type::pointer pointer;
218 typedef typename allocator_type::const_pointer const_pointer;
220 typedef implementation-defined iterator;
221 typedef implementation-defined const_iterator;
222 typedef std::reverse_iterator<iterator> reverse_iterator;
223 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
225 // construct/copy/destroy:
228 is_nothrow_default_constructible<allocator_type>::value &&
229 is_nothrow_default_constructible<key_compare>::value &&
230 is_nothrow_copy_constructible<key_compare>::value);
231 explicit multiset(const value_compare& comp);
232 multiset(const value_compare& comp, const allocator_type& a);
233 template <class InputIterator>
234 multiset(InputIterator first, InputIterator last,
235 const value_compare& comp = value_compare());
236 template <class InputIterator>
237 multiset(InputIterator first, InputIterator last,
238 const value_compare& comp, const allocator_type& a);
239 multiset(const multiset& s);
240 multiset(multiset&& s)
242 is_nothrow_move_constructible<allocator_type>::value &&
243 is_nothrow_move_constructible<key_compare>::value);
244 explicit multiset(const allocator_type& a);
245 multiset(const multiset& s, const allocator_type& a);
246 multiset(multiset&& s, const allocator_type& a);
247 multiset(initializer_list<value_type> il, const value_compare& comp = value_compare());
248 multiset(initializer_list<value_type> il, const value_compare& comp,
249 const allocator_type& a);
250 template <class InputIterator>
251 multiset(InputIterator first, InputIterator last, const allocator_type& a)
252 : set(first, last, Compare(), a) {} // C++14
253 multiset(initializer_list<value_type> il, const allocator_type& a)
254 : set(il, Compare(), a) {} // C++14
257 multiset& operator=(const multiset& s);
258 multiset& operator=(multiset&& s)
260 allocator_type::propagate_on_container_move_assignment::value &&
261 is_nothrow_move_assignable<allocator_type>::value &&
262 is_nothrow_move_assignable<key_compare>::value);
263 multiset& operator=(initializer_list<value_type> il);
266 iterator begin() noexcept;
267 const_iterator begin() const noexcept;
268 iterator end() noexcept;
269 const_iterator end() const noexcept;
271 reverse_iterator rbegin() noexcept;
272 const_reverse_iterator rbegin() const noexcept;
273 reverse_iterator rend() noexcept;
274 const_reverse_iterator rend() const noexcept;
276 const_iterator cbegin() const noexcept;
277 const_iterator cend() const noexcept;
278 const_reverse_iterator crbegin() const noexcept;
279 const_reverse_iterator crend() const noexcept;
282 bool empty() const noexcept;
283 size_type size() const noexcept;
284 size_type max_size() const noexcept;
287 template <class... Args>
288 iterator emplace(Args&&... args);
289 template <class... Args>
290 iterator emplace_hint(const_iterator position, Args&&... args);
291 iterator insert(const value_type& v);
292 iterator insert(value_type&& v);
293 iterator insert(const_iterator position, const value_type& v);
294 iterator insert(const_iterator position, value_type&& v);
295 template <class InputIterator>
296 void insert(InputIterator first, InputIterator last);
297 void insert(initializer_list<value_type> il);
299 iterator erase(const_iterator position);
300 size_type erase(const key_type& k);
301 iterator erase(const_iterator first, const_iterator last);
302 void clear() noexcept;
304 void swap(multiset& s)
306 __is_nothrow_swappable<key_compare>::value &&
307 (!allocator_type::propagate_on_container_swap::value ||
308 __is_nothrow_swappable<allocator_type>::value));
311 allocator_type get_allocator() const noexcept;
312 key_compare key_comp() const;
313 value_compare value_comp() const;
316 iterator find(const key_type& k);
317 const_iterator find(const key_type& k) const;
319 iterator find(const K& x);
321 const_iterator find(const K& x) const; // C++14
323 size_type count(const key_type& k) const;
324 iterator lower_bound(const key_type& k);
325 const_iterator lower_bound(const key_type& k) const;
327 iterator lower_bound(const K& x); // C++14
329 const_iterator lower_bound(const K& x) const; // C++14
331 iterator upper_bound(const key_type& k);
332 const_iterator upper_bound(const key_type& k) const;
334 iterator upper_bound(const K& x); // C++14
336 const_iterator upper_bound(const K& x) const; // C++14
338 pair<iterator,iterator> equal_range(const key_type& k);
339 pair<const_iterator,const_iterator> equal_range(const key_type& k) const;
341 pair<iterator,iterator> equal_range(const K& x); // C++14
343 pair<const_iterator,const_iterator> equal_range(const K& x) const; // C++14
346 template <class Key, class Compare, class Allocator>
348 operator==(const multiset<Key, Compare, Allocator>& x,
349 const multiset<Key, Compare, Allocator>& y);
351 template <class Key, class Compare, class Allocator>
353 operator< (const multiset<Key, Compare, Allocator>& x,
354 const multiset<Key, Compare, Allocator>& y);
356 template <class Key, class Compare, class Allocator>
358 operator!=(const multiset<Key, Compare, Allocator>& x,
359 const multiset<Key, Compare, Allocator>& y);
361 template <class Key, class Compare, class Allocator>
363 operator> (const multiset<Key, Compare, Allocator>& x,
364 const multiset<Key, Compare, Allocator>& y);
366 template <class Key, class Compare, class Allocator>
368 operator>=(const multiset<Key, Compare, Allocator>& x,
369 const multiset<Key, Compare, Allocator>& y);
371 template <class Key, class Compare, class Allocator>
373 operator<=(const multiset<Key, Compare, Allocator>& x,
374 const multiset<Key, Compare, Allocator>& y);
376 // specialized algorithms:
377 template <class Key, class Compare, class Allocator>
379 swap(multiset<Key, Compare, Allocator>& x, multiset<Key, Compare, Allocator>& y)
380 noexcept(noexcept(x.swap(y)));
388 #include <functional>
390 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
391 #pragma GCC system_header
394 _LIBCPP_BEGIN_NAMESPACE_STD
396 template <class _Key, class _Compare = less<_Key>,
397 class _Allocator = allocator<_Key> >
398 class _LIBCPP_TYPE_VIS_ONLY set
402 typedef _Key key_type;
403 typedef key_type value_type;
404 typedef _Compare key_compare;
405 typedef key_compare value_compare;
406 typedef _Allocator allocator_type;
407 typedef value_type& reference;
408 typedef const value_type& const_reference;
411 typedef __tree<value_type, value_compare, allocator_type> __base;
412 typedef allocator_traits<allocator_type> __alloc_traits;
413 typedef typename __base::__node_holder __node_holder;
418 typedef typename __base::pointer pointer;
419 typedef typename __base::const_pointer const_pointer;
420 typedef typename __base::size_type size_type;
421 typedef typename __base::difference_type difference_type;
422 typedef typename __base::const_iterator iterator;
423 typedef typename __base::const_iterator const_iterator;
424 typedef _VSTD::reverse_iterator<iterator> reverse_iterator;
425 typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator;
427 _LIBCPP_INLINE_VISIBILITY
430 is_nothrow_default_constructible<allocator_type>::value &&
431 is_nothrow_default_constructible<key_compare>::value &&
432 is_nothrow_copy_constructible<key_compare>::value)
433 : __tree_(value_compare()) {}
435 _LIBCPP_INLINE_VISIBILITY
436 explicit set(const value_compare& __comp)
438 is_nothrow_default_constructible<allocator_type>::value &&
439 is_nothrow_copy_constructible<key_compare>::value)
442 _LIBCPP_INLINE_VISIBILITY
443 explicit set(const value_compare& __comp, const allocator_type& __a)
444 : __tree_(__comp, __a) {}
445 template <class _InputIterator>
446 _LIBCPP_INLINE_VISIBILITY
447 set(_InputIterator __f, _InputIterator __l,
448 const value_compare& __comp = value_compare())
454 template <class _InputIterator>
455 _LIBCPP_INLINE_VISIBILITY
456 set(_InputIterator __f, _InputIterator __l, const value_compare& __comp,
457 const allocator_type& __a)
458 : __tree_(__comp, __a)
463 #if _LIBCPP_STD_VER > 11
464 template <class _InputIterator>
465 _LIBCPP_INLINE_VISIBILITY
466 set(_InputIterator __f, _InputIterator __l, const allocator_type& __a)
467 : set(__f, __l, key_compare(), __a) {}
470 _LIBCPP_INLINE_VISIBILITY
472 : __tree_(__s.__tree_)
474 insert(__s.begin(), __s.end());
477 _LIBCPP_INLINE_VISIBILITY
478 set& operator=(const set& __s)
480 __tree_ = __s.__tree_;
484 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
485 _LIBCPP_INLINE_VISIBILITY
487 _NOEXCEPT_(is_nothrow_move_constructible<__base>::value)
488 : __tree_(_VSTD::move(__s.__tree_)) {}
489 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
491 _LIBCPP_INLINE_VISIBILITY
492 explicit set(const allocator_type& __a)
495 _LIBCPP_INLINE_VISIBILITY
496 set(const set& __s, const allocator_type& __a)
497 : __tree_(__s.__tree_.value_comp(), __a)
499 insert(__s.begin(), __s.end());
502 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
503 set(set&& __s, const allocator_type& __a);
506 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
507 _LIBCPP_INLINE_VISIBILITY
508 set(initializer_list<value_type> __il, const value_compare& __comp = value_compare())
511 insert(__il.begin(), __il.end());
514 _LIBCPP_INLINE_VISIBILITY
515 set(initializer_list<value_type> __il, const value_compare& __comp,
516 const allocator_type& __a)
517 : __tree_(__comp, __a)
519 insert(__il.begin(), __il.end());
522 #if _LIBCPP_STD_VER > 11
523 _LIBCPP_INLINE_VISIBILITY
524 set(initializer_list<value_type> __il, const allocator_type& __a)
525 : set(__il, key_compare(), __a) {}
528 _LIBCPP_INLINE_VISIBILITY
529 set& operator=(initializer_list<value_type> __il)
531 __tree_.__assign_unique(__il.begin(), __il.end());
534 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
536 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
537 _LIBCPP_INLINE_VISIBILITY
538 set& operator=(set&& __s)
539 _NOEXCEPT_(is_nothrow_move_assignable<__base>::value)
541 __tree_ = _VSTD::move(__s.__tree_);
544 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
546 _LIBCPP_INLINE_VISIBILITY
547 iterator begin() _NOEXCEPT {return __tree_.begin();}
548 _LIBCPP_INLINE_VISIBILITY
549 const_iterator begin() const _NOEXCEPT {return __tree_.begin();}
550 _LIBCPP_INLINE_VISIBILITY
551 iterator end() _NOEXCEPT {return __tree_.end();}
552 _LIBCPP_INLINE_VISIBILITY
553 const_iterator end() const _NOEXCEPT {return __tree_.end();}
555 _LIBCPP_INLINE_VISIBILITY
556 reverse_iterator rbegin() _NOEXCEPT
557 {return reverse_iterator(end());}
558 _LIBCPP_INLINE_VISIBILITY
559 const_reverse_iterator rbegin() const _NOEXCEPT
560 {return const_reverse_iterator(end());}
561 _LIBCPP_INLINE_VISIBILITY
562 reverse_iterator rend() _NOEXCEPT
563 {return reverse_iterator(begin());}
564 _LIBCPP_INLINE_VISIBILITY
565 const_reverse_iterator rend() const _NOEXCEPT
566 {return const_reverse_iterator(begin());}
568 _LIBCPP_INLINE_VISIBILITY
569 const_iterator cbegin() const _NOEXCEPT {return begin();}
570 _LIBCPP_INLINE_VISIBILITY
571 const_iterator cend() const _NOEXCEPT {return end();}
572 _LIBCPP_INLINE_VISIBILITY
573 const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();}
574 _LIBCPP_INLINE_VISIBILITY
575 const_reverse_iterator crend() const _NOEXCEPT {return rend();}
577 _LIBCPP_INLINE_VISIBILITY
578 bool empty() const _NOEXCEPT {return __tree_.size() == 0;}
579 _LIBCPP_INLINE_VISIBILITY
580 size_type size() const _NOEXCEPT {return __tree_.size();}
581 _LIBCPP_INLINE_VISIBILITY
582 size_type max_size() const _NOEXCEPT {return __tree_.max_size();}
585 #if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
586 template <class... _Args>
587 _LIBCPP_INLINE_VISIBILITY
588 pair<iterator, bool> emplace(_Args&&... __args)
589 {return __tree_.__emplace_unique(_VSTD::forward<_Args>(__args)...);}
590 template <class... _Args>
591 _LIBCPP_INLINE_VISIBILITY
592 iterator emplace_hint(const_iterator __p, _Args&&... __args)
593 {return __tree_.__emplace_hint_unique(__p, _VSTD::forward<_Args>(__args)...);}
594 #endif // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
595 _LIBCPP_INLINE_VISIBILITY
596 pair<iterator,bool> insert(const value_type& __v)
597 {return __tree_.__insert_unique(__v);}
598 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
599 _LIBCPP_INLINE_VISIBILITY
600 pair<iterator,bool> insert(value_type&& __v)
601 {return __tree_.__insert_unique(_VSTD::move(__v));}
602 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
603 _LIBCPP_INLINE_VISIBILITY
604 iterator insert(const_iterator __p, const value_type& __v)
605 {return __tree_.__insert_unique(__p, __v);}
606 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
607 _LIBCPP_INLINE_VISIBILITY
608 iterator insert(const_iterator __p, value_type&& __v)
609 {return __tree_.__insert_unique(__p, _VSTD::move(__v));}
610 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
611 template <class _InputIterator>
612 _LIBCPP_INLINE_VISIBILITY
613 void insert(_InputIterator __f, _InputIterator __l)
615 for (const_iterator __e = cend(); __f != __l; ++__f)
616 __tree_.__insert_unique(__e, *__f);
619 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
620 _LIBCPP_INLINE_VISIBILITY
621 void insert(initializer_list<value_type> __il)
622 {insert(__il.begin(), __il.end());}
623 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
625 _LIBCPP_INLINE_VISIBILITY
626 iterator erase(const_iterator __p) {return __tree_.erase(__p);}
627 _LIBCPP_INLINE_VISIBILITY
628 size_type erase(const key_type& __k)
629 {return __tree_.__erase_unique(__k);}
630 _LIBCPP_INLINE_VISIBILITY
631 iterator erase(const_iterator __f, const_iterator __l)
632 {return __tree_.erase(__f, __l);}
633 _LIBCPP_INLINE_VISIBILITY
634 void clear() _NOEXCEPT {__tree_.clear();}
636 _LIBCPP_INLINE_VISIBILITY
637 void swap(set& __s) _NOEXCEPT_(__is_nothrow_swappable<__base>::value)
638 {__tree_.swap(__s.__tree_);}
640 _LIBCPP_INLINE_VISIBILITY
641 allocator_type get_allocator() const _NOEXCEPT {return __tree_.__alloc();}
642 _LIBCPP_INLINE_VISIBILITY
643 key_compare key_comp() const {return __tree_.value_comp();}
644 _LIBCPP_INLINE_VISIBILITY
645 value_compare value_comp() const {return __tree_.value_comp();}
648 _LIBCPP_INLINE_VISIBILITY
649 iterator find(const key_type& __k) {return __tree_.find(__k);}
650 _LIBCPP_INLINE_VISIBILITY
651 const_iterator find(const key_type& __k) const {return __tree_.find(__k);}
652 #if _LIBCPP_STD_VER > 11
653 template <typename _K2>
654 _LIBCPP_INLINE_VISIBILITY
655 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
656 find(const _K2& __k) {return __tree_.find(__k);}
657 template <typename _K2>
658 _LIBCPP_INLINE_VISIBILITY
659 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
660 find(const _K2& __k) const {return __tree_.find(__k);}
663 _LIBCPP_INLINE_VISIBILITY
664 size_type count(const key_type& __k) const
665 {return __tree_.__count_unique(__k);}
666 #if _LIBCPP_STD_VER > 11
667 template <typename _K2>
668 _LIBCPP_INLINE_VISIBILITY
669 typename enable_if<__is_transparent<_Compare, _K2>::value,size_type>::type
670 count(const _K2& __k) {return __tree_.__count_unique(__k);}
672 _LIBCPP_INLINE_VISIBILITY
673 iterator lower_bound(const key_type& __k)
674 {return __tree_.lower_bound(__k);}
675 _LIBCPP_INLINE_VISIBILITY
676 const_iterator lower_bound(const key_type& __k) const
677 {return __tree_.lower_bound(__k);}
678 #if _LIBCPP_STD_VER > 11
679 template <typename _K2>
680 _LIBCPP_INLINE_VISIBILITY
681 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
682 lower_bound(const _K2& __k) {return __tree_.lower_bound(__k);}
684 template <typename _K2>
685 _LIBCPP_INLINE_VISIBILITY
686 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
687 lower_bound(const _K2& __k) const {return __tree_.lower_bound(__k);}
690 _LIBCPP_INLINE_VISIBILITY
691 iterator upper_bound(const key_type& __k)
692 {return __tree_.upper_bound(__k);}
693 _LIBCPP_INLINE_VISIBILITY
694 const_iterator upper_bound(const key_type& __k) const
695 {return __tree_.upper_bound(__k);}
696 #if _LIBCPP_STD_VER > 11
697 template <typename _K2>
698 _LIBCPP_INLINE_VISIBILITY
699 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
700 upper_bound(const _K2& __k) {return __tree_.upper_bound(__k);}
701 template <typename _K2>
702 _LIBCPP_INLINE_VISIBILITY
703 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
704 upper_bound(const _K2& __k) const {return __tree_.upper_bound(__k);}
707 _LIBCPP_INLINE_VISIBILITY
708 pair<iterator,iterator> equal_range(const key_type& __k)
709 {return __tree_.__equal_range_unique(__k);}
710 _LIBCPP_INLINE_VISIBILITY
711 pair<const_iterator,const_iterator> equal_range(const key_type& __k) const
712 {return __tree_.__equal_range_unique(__k);}
713 #if _LIBCPP_STD_VER > 11
714 template <typename _K2>
715 _LIBCPP_INLINE_VISIBILITY
716 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<iterator,iterator>>::type
717 equal_range(const _K2& __k) {return __tree_.__equal_range_unique(__k);}
718 template <typename _K2>
719 _LIBCPP_INLINE_VISIBILITY
720 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<const_iterator,const_iterator>>::type
721 equal_range(const _K2& __k) const {return __tree_.__equal_range_unique(__k);}
725 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
727 template <class _Key, class _Compare, class _Allocator>
728 set<_Key, _Compare, _Allocator>::set(set&& __s, const allocator_type& __a)
729 : __tree_(_VSTD::move(__s.__tree_), __a)
731 if (__a != __s.get_allocator())
733 const_iterator __e = cend();
735 insert(__e, _VSTD::move(__s.__tree_.remove(__s.begin())->__value_));
739 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
741 template <class _Key, class _Compare, class _Allocator>
742 inline _LIBCPP_INLINE_VISIBILITY
744 operator==(const set<_Key, _Compare, _Allocator>& __x,
745 const set<_Key, _Compare, _Allocator>& __y)
747 return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin());
750 template <class _Key, class _Compare, class _Allocator>
751 inline _LIBCPP_INLINE_VISIBILITY
753 operator< (const set<_Key, _Compare, _Allocator>& __x,
754 const set<_Key, _Compare, _Allocator>& __y)
756 return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
759 template <class _Key, class _Compare, class _Allocator>
760 inline _LIBCPP_INLINE_VISIBILITY
762 operator!=(const set<_Key, _Compare, _Allocator>& __x,
763 const set<_Key, _Compare, _Allocator>& __y)
765 return !(__x == __y);
768 template <class _Key, class _Compare, class _Allocator>
769 inline _LIBCPP_INLINE_VISIBILITY
771 operator> (const set<_Key, _Compare, _Allocator>& __x,
772 const set<_Key, _Compare, _Allocator>& __y)
777 template <class _Key, class _Compare, class _Allocator>
778 inline _LIBCPP_INLINE_VISIBILITY
780 operator>=(const set<_Key, _Compare, _Allocator>& __x,
781 const set<_Key, _Compare, _Allocator>& __y)
786 template <class _Key, class _Compare, class _Allocator>
787 inline _LIBCPP_INLINE_VISIBILITY
789 operator<=(const set<_Key, _Compare, _Allocator>& __x,
790 const set<_Key, _Compare, _Allocator>& __y)
795 // specialized algorithms:
796 template <class _Key, class _Compare, class _Allocator>
797 inline _LIBCPP_INLINE_VISIBILITY
799 swap(set<_Key, _Compare, _Allocator>& __x,
800 set<_Key, _Compare, _Allocator>& __y)
801 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
806 template <class _Key, class _Compare = less<_Key>,
807 class _Allocator = allocator<_Key> >
808 class _LIBCPP_TYPE_VIS_ONLY multiset
812 typedef _Key key_type;
813 typedef key_type value_type;
814 typedef _Compare key_compare;
815 typedef key_compare value_compare;
816 typedef _Allocator allocator_type;
817 typedef value_type& reference;
818 typedef const value_type& const_reference;
821 typedef __tree<value_type, value_compare, allocator_type> __base;
822 typedef allocator_traits<allocator_type> __alloc_traits;
823 typedef typename __base::__node_holder __node_holder;
828 typedef typename __base::pointer pointer;
829 typedef typename __base::const_pointer const_pointer;
830 typedef typename __base::size_type size_type;
831 typedef typename __base::difference_type difference_type;
832 typedef typename __base::const_iterator iterator;
833 typedef typename __base::const_iterator const_iterator;
834 typedef _VSTD::reverse_iterator<iterator> reverse_iterator;
835 typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator;
837 // construct/copy/destroy:
838 _LIBCPP_INLINE_VISIBILITY
841 is_nothrow_default_constructible<allocator_type>::value &&
842 is_nothrow_default_constructible<key_compare>::value &&
843 is_nothrow_copy_constructible<key_compare>::value)
844 : __tree_(value_compare()) {}
846 _LIBCPP_INLINE_VISIBILITY
847 explicit multiset(const value_compare& __comp)
849 is_nothrow_default_constructible<allocator_type>::value &&
850 is_nothrow_copy_constructible<key_compare>::value)
853 _LIBCPP_INLINE_VISIBILITY
854 explicit multiset(const value_compare& __comp, const allocator_type& __a)
855 : __tree_(__comp, __a) {}
856 template <class _InputIterator>
857 _LIBCPP_INLINE_VISIBILITY
858 multiset(_InputIterator __f, _InputIterator __l,
859 const value_compare& __comp = value_compare())
865 #if _LIBCPP_STD_VER > 11
866 template <class _InputIterator>
867 _LIBCPP_INLINE_VISIBILITY
868 multiset(_InputIterator __f, _InputIterator __l, const allocator_type& __a)
869 : multiset(__f, __l, key_compare(), __a) {}
872 template <class _InputIterator>
873 _LIBCPP_INLINE_VISIBILITY
874 multiset(_InputIterator __f, _InputIterator __l,
875 const value_compare& __comp, const allocator_type& __a)
876 : __tree_(__comp, __a)
881 _LIBCPP_INLINE_VISIBILITY
882 multiset(const multiset& __s)
883 : __tree_(__s.__tree_.value_comp(),
884 __alloc_traits::select_on_container_copy_construction(__s.__tree_.__alloc()))
886 insert(__s.begin(), __s.end());
889 _LIBCPP_INLINE_VISIBILITY
890 multiset& operator=(const multiset& __s)
892 __tree_ = __s.__tree_;
896 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
897 _LIBCPP_INLINE_VISIBILITY
898 multiset(multiset&& __s)
899 _NOEXCEPT_(is_nothrow_move_constructible<__base>::value)
900 : __tree_(_VSTD::move(__s.__tree_)) {}
901 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
902 _LIBCPP_INLINE_VISIBILITY
903 explicit multiset(const allocator_type& __a)
905 _LIBCPP_INLINE_VISIBILITY
906 multiset(const multiset& __s, const allocator_type& __a)
907 : __tree_(__s.__tree_.value_comp(), __a)
909 insert(__s.begin(), __s.end());
911 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
912 multiset(multiset&& __s, const allocator_type& __a);
915 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
916 _LIBCPP_INLINE_VISIBILITY
917 multiset(initializer_list<value_type> __il, const value_compare& __comp = value_compare())
920 insert(__il.begin(), __il.end());
923 _LIBCPP_INLINE_VISIBILITY
924 multiset(initializer_list<value_type> __il, const value_compare& __comp,
925 const allocator_type& __a)
926 : __tree_(__comp, __a)
928 insert(__il.begin(), __il.end());
931 #if _LIBCPP_STD_VER > 11
932 _LIBCPP_INLINE_VISIBILITY
933 multiset(initializer_list<value_type> __il, const allocator_type& __a)
934 : multiset(__il, key_compare(), __a) {}
937 _LIBCPP_INLINE_VISIBILITY
938 multiset& operator=(initializer_list<value_type> __il)
940 __tree_.__assign_multi(__il.begin(), __il.end());
943 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
945 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
946 _LIBCPP_INLINE_VISIBILITY
947 multiset& operator=(multiset&& __s)
948 _NOEXCEPT_(is_nothrow_move_assignable<__base>::value)
950 __tree_ = _VSTD::move(__s.__tree_);
953 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
955 _LIBCPP_INLINE_VISIBILITY
956 iterator begin() _NOEXCEPT {return __tree_.begin();}
957 _LIBCPP_INLINE_VISIBILITY
958 const_iterator begin() const _NOEXCEPT {return __tree_.begin();}
959 _LIBCPP_INLINE_VISIBILITY
960 iterator end() _NOEXCEPT {return __tree_.end();}
961 _LIBCPP_INLINE_VISIBILITY
962 const_iterator end() const _NOEXCEPT {return __tree_.end();}
964 _LIBCPP_INLINE_VISIBILITY
965 reverse_iterator rbegin() _NOEXCEPT
966 {return reverse_iterator(end());}
967 _LIBCPP_INLINE_VISIBILITY
968 const_reverse_iterator rbegin() const _NOEXCEPT
969 {return const_reverse_iterator(end());}
970 _LIBCPP_INLINE_VISIBILITY
971 reverse_iterator rend() _NOEXCEPT
972 {return reverse_iterator(begin());}
973 _LIBCPP_INLINE_VISIBILITY
974 const_reverse_iterator rend() const _NOEXCEPT
975 {return const_reverse_iterator(begin());}
977 _LIBCPP_INLINE_VISIBILITY
978 const_iterator cbegin() const _NOEXCEPT {return begin();}
979 _LIBCPP_INLINE_VISIBILITY
980 const_iterator cend() const _NOEXCEPT {return end();}
981 _LIBCPP_INLINE_VISIBILITY
982 const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();}
983 _LIBCPP_INLINE_VISIBILITY
984 const_reverse_iterator crend() const _NOEXCEPT {return rend();}
986 _LIBCPP_INLINE_VISIBILITY
987 bool empty() const _NOEXCEPT {return __tree_.size() == 0;}
988 _LIBCPP_INLINE_VISIBILITY
989 size_type size() const _NOEXCEPT {return __tree_.size();}
990 _LIBCPP_INLINE_VISIBILITY
991 size_type max_size() const _NOEXCEPT {return __tree_.max_size();}
994 #if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
995 template <class... _Args>
996 _LIBCPP_INLINE_VISIBILITY
997 iterator emplace(_Args&&... __args)
998 {return __tree_.__emplace_multi(_VSTD::forward<_Args>(__args)...);}
999 template <class... _Args>
1000 _LIBCPP_INLINE_VISIBILITY
1001 iterator emplace_hint(const_iterator __p, _Args&&... __args)
1002 {return __tree_.__emplace_hint_multi(__p, _VSTD::forward<_Args>(__args)...);}
1003 #endif // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
1004 _LIBCPP_INLINE_VISIBILITY
1005 iterator insert(const value_type& __v)
1006 {return __tree_.__insert_multi(__v);}
1007 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1008 _LIBCPP_INLINE_VISIBILITY
1009 iterator insert(value_type&& __v)
1010 {return __tree_.__insert_multi(_VSTD::move(__v));}
1011 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1012 _LIBCPP_INLINE_VISIBILITY
1013 iterator insert(const_iterator __p, const value_type& __v)
1014 {return __tree_.__insert_multi(__p, __v);}
1015 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1016 _LIBCPP_INLINE_VISIBILITY
1017 iterator insert(const_iterator __p, value_type&& __v)
1018 {return __tree_.__insert_multi(_VSTD::move(__v));}
1019 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1020 template <class _InputIterator>
1021 _LIBCPP_INLINE_VISIBILITY
1022 void insert(_InputIterator __f, _InputIterator __l)
1024 for (const_iterator __e = cend(); __f != __l; ++__f)
1025 __tree_.__insert_multi(__e, *__f);
1028 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1029 _LIBCPP_INLINE_VISIBILITY
1030 void insert(initializer_list<value_type> __il)
1031 {insert(__il.begin(), __il.end());}
1032 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1034 _LIBCPP_INLINE_VISIBILITY
1035 iterator erase(const_iterator __p) {return __tree_.erase(__p);}
1036 _LIBCPP_INLINE_VISIBILITY
1037 size_type erase(const key_type& __k) {return __tree_.__erase_multi(__k);}
1038 _LIBCPP_INLINE_VISIBILITY
1039 iterator erase(const_iterator __f, const_iterator __l)
1040 {return __tree_.erase(__f, __l);}
1041 _LIBCPP_INLINE_VISIBILITY
1042 void clear() _NOEXCEPT {__tree_.clear();}
1044 _LIBCPP_INLINE_VISIBILITY
1045 void swap(multiset& __s)
1046 _NOEXCEPT_(__is_nothrow_swappable<__base>::value)
1047 {__tree_.swap(__s.__tree_);}
1049 _LIBCPP_INLINE_VISIBILITY
1050 allocator_type get_allocator() const _NOEXCEPT {return __tree_.__alloc();}
1051 _LIBCPP_INLINE_VISIBILITY
1052 key_compare key_comp() const {return __tree_.value_comp();}
1053 _LIBCPP_INLINE_VISIBILITY
1054 value_compare value_comp() const {return __tree_.value_comp();}
1057 _LIBCPP_INLINE_VISIBILITY
1058 iterator find(const key_type& __k) {return __tree_.find(__k);}
1059 _LIBCPP_INLINE_VISIBILITY
1060 const_iterator find(const key_type& __k) const {return __tree_.find(__k);}
1061 #if _LIBCPP_STD_VER > 11
1062 template <typename _K2>
1063 _LIBCPP_INLINE_VISIBILITY
1064 typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,iterator>::type
1065 find(const _K2& __k) {return __tree_.find(__k);}
1066 template <typename _K2>
1067 _LIBCPP_INLINE_VISIBILITY
1068 typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,const_iterator>::type
1069 find(const _K2& __k) const {return __tree_.find(__k);}
1072 _LIBCPP_INLINE_VISIBILITY
1073 size_type count(const key_type& __k) const
1074 {return __tree_.__count_multi(__k);}
1075 #if _LIBCPP_STD_VER > 11
1076 template <typename _K2>
1077 _LIBCPP_INLINE_VISIBILITY
1078 typename enable_if<__is_transparent<_Compare, _K2>::value,size_type>::type
1079 count(const _K2& __k) {return __tree_.__count_multi(__k);}
1082 _LIBCPP_INLINE_VISIBILITY
1083 iterator lower_bound(const key_type& __k)
1084 {return __tree_.lower_bound(__k);}
1085 _LIBCPP_INLINE_VISIBILITY
1086 const_iterator lower_bound(const key_type& __k) const
1087 {return __tree_.lower_bound(__k);}
1088 #if _LIBCPP_STD_VER > 11
1089 template <typename _K2>
1090 _LIBCPP_INLINE_VISIBILITY
1091 typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,iterator>::type
1092 lower_bound(const _K2& __k) {return __tree_.lower_bound(__k);}
1094 template <typename _K2>
1095 _LIBCPP_INLINE_VISIBILITY
1096 typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,const_iterator>::type
1097 lower_bound(const _K2& __k) const {return __tree_.lower_bound(__k);}
1100 _LIBCPP_INLINE_VISIBILITY
1101 iterator upper_bound(const key_type& __k)
1102 {return __tree_.upper_bound(__k);}
1103 _LIBCPP_INLINE_VISIBILITY
1104 const_iterator upper_bound(const key_type& __k) const
1105 {return __tree_.upper_bound(__k);}
1106 #if _LIBCPP_STD_VER > 11
1107 template <typename _K2>
1108 _LIBCPP_INLINE_VISIBILITY
1109 typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,iterator>::type
1110 upper_bound(const _K2& __k) {return __tree_.upper_bound(__k);}
1111 template <typename _K2>
1112 _LIBCPP_INLINE_VISIBILITY
1113 typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,const_iterator>::type
1114 upper_bound(const _K2& __k) const {return __tree_.upper_bound(__k);}
1117 _LIBCPP_INLINE_VISIBILITY
1118 pair<iterator,iterator> equal_range(const key_type& __k)
1119 {return __tree_.__equal_range_multi(__k);}
1120 _LIBCPP_INLINE_VISIBILITY
1121 pair<const_iterator,const_iterator> equal_range(const key_type& __k) const
1122 {return __tree_.__equal_range_multi(__k);}
1123 #if _LIBCPP_STD_VER > 11
1124 template <typename _K2>
1125 _LIBCPP_INLINE_VISIBILITY
1126 typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,pair<iterator,iterator>>::type
1127 equal_range(const _K2& __k) {return __tree_.__equal_range_multi(__k);}
1128 template <typename _K2>
1129 _LIBCPP_INLINE_VISIBILITY
1130 typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,pair<const_iterator,const_iterator>>::type
1131 equal_range(const _K2& __k) const {return __tree_.__equal_range_multi(__k);}
1135 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1137 template <class _Key, class _Compare, class _Allocator>
1138 multiset<_Key, _Compare, _Allocator>::multiset(multiset&& __s, const allocator_type& __a)
1139 : __tree_(_VSTD::move(__s.__tree_), __a)
1141 if (__a != __s.get_allocator())
1143 const_iterator __e = cend();
1144 while (!__s.empty())
1145 insert(__e, _VSTD::move(__s.__tree_.remove(__s.begin())->__value_));
1149 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1151 template <class _Key, class _Compare, class _Allocator>
1152 inline _LIBCPP_INLINE_VISIBILITY
1154 operator==(const multiset<_Key, _Compare, _Allocator>& __x,
1155 const multiset<_Key, _Compare, _Allocator>& __y)
1157 return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin());
1160 template <class _Key, class _Compare, class _Allocator>
1161 inline _LIBCPP_INLINE_VISIBILITY
1163 operator< (const multiset<_Key, _Compare, _Allocator>& __x,
1164 const multiset<_Key, _Compare, _Allocator>& __y)
1166 return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
1169 template <class _Key, class _Compare, class _Allocator>
1170 inline _LIBCPP_INLINE_VISIBILITY
1172 operator!=(const multiset<_Key, _Compare, _Allocator>& __x,
1173 const multiset<_Key, _Compare, _Allocator>& __y)
1175 return !(__x == __y);
1178 template <class _Key, class _Compare, class _Allocator>
1179 inline _LIBCPP_INLINE_VISIBILITY
1181 operator> (const multiset<_Key, _Compare, _Allocator>& __x,
1182 const multiset<_Key, _Compare, _Allocator>& __y)
1187 template <class _Key, class _Compare, class _Allocator>
1188 inline _LIBCPP_INLINE_VISIBILITY
1190 operator>=(const multiset<_Key, _Compare, _Allocator>& __x,
1191 const multiset<_Key, _Compare, _Allocator>& __y)
1193 return !(__x < __y);
1196 template <class _Key, class _Compare, class _Allocator>
1197 inline _LIBCPP_INLINE_VISIBILITY
1199 operator<=(const multiset<_Key, _Compare, _Allocator>& __x,
1200 const multiset<_Key, _Compare, _Allocator>& __y)
1202 return !(__y < __x);
1205 template <class _Key, class _Compare, class _Allocator>
1206 inline _LIBCPP_INLINE_VISIBILITY
1208 swap(multiset<_Key, _Compare, _Allocator>& __x,
1209 multiset<_Key, _Compare, _Allocator>& __y)
1210 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
1215 _LIBCPP_END_NAMESPACE_STD
1217 #endif // _LIBCPP_SET