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
428 explicit set(const value_compare& __comp = value_compare())
430 is_nothrow_default_constructible<allocator_type>::value &&
431 is_nothrow_default_constructible<key_compare>::value &&
432 is_nothrow_copy_constructible<key_compare>::value)
434 _LIBCPP_INLINE_VISIBILITY
435 set(const value_compare& __comp, const allocator_type& __a)
436 : __tree_(__comp, __a) {}
437 template <class _InputIterator>
438 _LIBCPP_INLINE_VISIBILITY
439 set(_InputIterator __f, _InputIterator __l,
440 const value_compare& __comp = value_compare())
446 template <class _InputIterator>
447 _LIBCPP_INLINE_VISIBILITY
448 set(_InputIterator __f, _InputIterator __l, const value_compare& __comp,
449 const allocator_type& __a)
450 : __tree_(__comp, __a)
455 #if _LIBCPP_STD_VER > 11
456 template <class _InputIterator>
457 _LIBCPP_INLINE_VISIBILITY
458 set(_InputIterator __f, _InputIterator __l, const allocator_type& __a)
459 : set(__f, __l, key_compare(), __a) {}
462 _LIBCPP_INLINE_VISIBILITY
464 : __tree_(__s.__tree_)
466 insert(__s.begin(), __s.end());
469 _LIBCPP_INLINE_VISIBILITY
470 set& operator=(const set& __s)
472 __tree_ = __s.__tree_;
476 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
477 _LIBCPP_INLINE_VISIBILITY
479 _NOEXCEPT_(is_nothrow_move_constructible<__base>::value)
480 : __tree_(_VSTD::move(__s.__tree_)) {}
481 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
483 _LIBCPP_INLINE_VISIBILITY
484 explicit set(const allocator_type& __a)
487 _LIBCPP_INLINE_VISIBILITY
488 set(const set& __s, const allocator_type& __a)
489 : __tree_(__s.__tree_.value_comp(), __a)
491 insert(__s.begin(), __s.end());
494 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
495 set(set&& __s, const allocator_type& __a);
498 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
499 _LIBCPP_INLINE_VISIBILITY
500 set(initializer_list<value_type> __il, const value_compare& __comp = value_compare())
503 insert(__il.begin(), __il.end());
506 _LIBCPP_INLINE_VISIBILITY
507 set(initializer_list<value_type> __il, const value_compare& __comp,
508 const allocator_type& __a)
509 : __tree_(__comp, __a)
511 insert(__il.begin(), __il.end());
514 #if _LIBCPP_STD_VER > 11
515 _LIBCPP_INLINE_VISIBILITY
516 set(initializer_list<value_type> __il, const allocator_type& __a)
517 : set(__il, key_compare(), __a) {}
520 _LIBCPP_INLINE_VISIBILITY
521 set& operator=(initializer_list<value_type> __il)
523 __tree_.__assign_unique(__il.begin(), __il.end());
526 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
528 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
529 _LIBCPP_INLINE_VISIBILITY
530 set& operator=(set&& __s)
531 _NOEXCEPT_(is_nothrow_move_assignable<__base>::value)
533 __tree_ = _VSTD::move(__s.__tree_);
536 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
538 _LIBCPP_INLINE_VISIBILITY
539 iterator begin() _NOEXCEPT {return __tree_.begin();}
540 _LIBCPP_INLINE_VISIBILITY
541 const_iterator begin() const _NOEXCEPT {return __tree_.begin();}
542 _LIBCPP_INLINE_VISIBILITY
543 iterator end() _NOEXCEPT {return __tree_.end();}
544 _LIBCPP_INLINE_VISIBILITY
545 const_iterator end() const _NOEXCEPT {return __tree_.end();}
547 _LIBCPP_INLINE_VISIBILITY
548 reverse_iterator rbegin() _NOEXCEPT
549 {return reverse_iterator(end());}
550 _LIBCPP_INLINE_VISIBILITY
551 const_reverse_iterator rbegin() const _NOEXCEPT
552 {return const_reverse_iterator(end());}
553 _LIBCPP_INLINE_VISIBILITY
554 reverse_iterator rend() _NOEXCEPT
555 {return reverse_iterator(begin());}
556 _LIBCPP_INLINE_VISIBILITY
557 const_reverse_iterator rend() const _NOEXCEPT
558 {return const_reverse_iterator(begin());}
560 _LIBCPP_INLINE_VISIBILITY
561 const_iterator cbegin() const _NOEXCEPT {return begin();}
562 _LIBCPP_INLINE_VISIBILITY
563 const_iterator cend() const _NOEXCEPT {return end();}
564 _LIBCPP_INLINE_VISIBILITY
565 const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();}
566 _LIBCPP_INLINE_VISIBILITY
567 const_reverse_iterator crend() const _NOEXCEPT {return rend();}
569 _LIBCPP_INLINE_VISIBILITY
570 bool empty() const _NOEXCEPT {return __tree_.size() == 0;}
571 _LIBCPP_INLINE_VISIBILITY
572 size_type size() const _NOEXCEPT {return __tree_.size();}
573 _LIBCPP_INLINE_VISIBILITY
574 size_type max_size() const _NOEXCEPT {return __tree_.max_size();}
577 #if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
578 template <class... _Args>
579 _LIBCPP_INLINE_VISIBILITY
580 pair<iterator, bool> emplace(_Args&&... __args)
581 {return __tree_.__emplace_unique(_VSTD::forward<_Args>(__args)...);}
582 template <class... _Args>
583 _LIBCPP_INLINE_VISIBILITY
584 iterator emplace_hint(const_iterator __p, _Args&&... __args)
585 {return __tree_.__emplace_hint_unique(__p, _VSTD::forward<_Args>(__args)...);}
586 #endif // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
587 _LIBCPP_INLINE_VISIBILITY
588 pair<iterator,bool> insert(const value_type& __v)
589 {return __tree_.__insert_unique(__v);}
590 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
591 _LIBCPP_INLINE_VISIBILITY
592 pair<iterator,bool> insert(value_type&& __v)
593 {return __tree_.__insert_unique(_VSTD::move(__v));}
594 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
595 _LIBCPP_INLINE_VISIBILITY
596 iterator insert(const_iterator __p, const value_type& __v)
597 {return __tree_.__insert_unique(__p, __v);}
598 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
599 _LIBCPP_INLINE_VISIBILITY
600 iterator insert(const_iterator __p, value_type&& __v)
601 {return __tree_.__insert_unique(__p, _VSTD::move(__v));}
602 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
603 template <class _InputIterator>
604 _LIBCPP_INLINE_VISIBILITY
605 void insert(_InputIterator __f, _InputIterator __l)
607 for (const_iterator __e = cend(); __f != __l; ++__f)
608 __tree_.__insert_unique(__e, *__f);
611 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
612 _LIBCPP_INLINE_VISIBILITY
613 void insert(initializer_list<value_type> __il)
614 {insert(__il.begin(), __il.end());}
615 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
617 _LIBCPP_INLINE_VISIBILITY
618 iterator erase(const_iterator __p) {return __tree_.erase(__p);}
619 _LIBCPP_INLINE_VISIBILITY
620 size_type erase(const key_type& __k)
621 {return __tree_.__erase_unique(__k);}
622 _LIBCPP_INLINE_VISIBILITY
623 iterator erase(const_iterator __f, const_iterator __l)
624 {return __tree_.erase(__f, __l);}
625 _LIBCPP_INLINE_VISIBILITY
626 void clear() _NOEXCEPT {__tree_.clear();}
628 _LIBCPP_INLINE_VISIBILITY
629 void swap(set& __s) _NOEXCEPT_(__is_nothrow_swappable<__base>::value)
630 {__tree_.swap(__s.__tree_);}
632 _LIBCPP_INLINE_VISIBILITY
633 allocator_type get_allocator() const _NOEXCEPT {return __tree_.__alloc();}
634 _LIBCPP_INLINE_VISIBILITY
635 key_compare key_comp() const {return __tree_.value_comp();}
636 _LIBCPP_INLINE_VISIBILITY
637 value_compare value_comp() const {return __tree_.value_comp();}
640 _LIBCPP_INLINE_VISIBILITY
641 iterator find(const key_type& __k) {return __tree_.find(__k);}
642 _LIBCPP_INLINE_VISIBILITY
643 const_iterator find(const key_type& __k) const {return __tree_.find(__k);}
644 #if _LIBCPP_STD_VER > 11
645 template <typename _K2>
646 _LIBCPP_INLINE_VISIBILITY
647 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
648 find(const _K2& __k) {return __tree_.find(__k);}
649 template <typename _K2>
650 _LIBCPP_INLINE_VISIBILITY
651 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
652 find(const _K2& __k) const {return __tree_.find(__k);}
655 _LIBCPP_INLINE_VISIBILITY
656 size_type count(const key_type& __k) const
657 {return __tree_.__count_unique(__k);}
658 _LIBCPP_INLINE_VISIBILITY
659 iterator lower_bound(const key_type& __k)
660 {return __tree_.lower_bound(__k);}
661 _LIBCPP_INLINE_VISIBILITY
662 const_iterator lower_bound(const key_type& __k) const
663 {return __tree_.lower_bound(__k);}
664 #if _LIBCPP_STD_VER > 11
665 template <typename _K2>
666 _LIBCPP_INLINE_VISIBILITY
667 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
668 lower_bound(const _K2& __k) {return __tree_.lower_bound(__k);}
670 template <typename _K2>
671 _LIBCPP_INLINE_VISIBILITY
672 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
673 lower_bound(const _K2& __k) const {return __tree_.lower_bound(__k);}
676 _LIBCPP_INLINE_VISIBILITY
677 iterator upper_bound(const key_type& __k)
678 {return __tree_.upper_bound(__k);}
679 _LIBCPP_INLINE_VISIBILITY
680 const_iterator upper_bound(const key_type& __k) const
681 {return __tree_.upper_bound(__k);}
682 #if _LIBCPP_STD_VER > 11
683 template <typename _K2>
684 _LIBCPP_INLINE_VISIBILITY
685 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
686 upper_bound(const _K2& __k) {return __tree_.upper_bound(__k);}
687 template <typename _K2>
688 _LIBCPP_INLINE_VISIBILITY
689 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
690 upper_bound(const _K2& __k) const {return __tree_.upper_bound(__k);}
693 _LIBCPP_INLINE_VISIBILITY
694 pair<iterator,iterator> equal_range(const key_type& __k)
695 {return __tree_.__equal_range_unique(__k);}
696 _LIBCPP_INLINE_VISIBILITY
697 pair<const_iterator,const_iterator> equal_range(const key_type& __k) const
698 {return __tree_.__equal_range_unique(__k);}
699 #if _LIBCPP_STD_VER > 11
700 template <typename _K2>
701 _LIBCPP_INLINE_VISIBILITY
702 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<iterator,iterator>>::type
703 equal_range(const _K2& __k) {return __tree_.__equal_range_unique(__k);}
704 template <typename _K2>
705 _LIBCPP_INLINE_VISIBILITY
706 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<const_iterator,const_iterator>>::type
707 equal_range(const _K2& __k) const {return __tree_.__equal_range_unique(__k);}
711 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
713 template <class _Key, class _Compare, class _Allocator>
714 set<_Key, _Compare, _Allocator>::set(set&& __s, const allocator_type& __a)
715 : __tree_(_VSTD::move(__s.__tree_), __a)
717 if (__a != __s.get_allocator())
719 const_iterator __e = cend();
721 insert(__e, _VSTD::move(__s.__tree_.remove(__s.begin())->__value_));
725 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
727 template <class _Key, class _Compare, class _Allocator>
728 inline _LIBCPP_INLINE_VISIBILITY
730 operator==(const set<_Key, _Compare, _Allocator>& __x,
731 const set<_Key, _Compare, _Allocator>& __y)
733 return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin());
736 template <class _Key, class _Compare, class _Allocator>
737 inline _LIBCPP_INLINE_VISIBILITY
739 operator< (const set<_Key, _Compare, _Allocator>& __x,
740 const set<_Key, _Compare, _Allocator>& __y)
742 return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
745 template <class _Key, class _Compare, class _Allocator>
746 inline _LIBCPP_INLINE_VISIBILITY
748 operator!=(const set<_Key, _Compare, _Allocator>& __x,
749 const set<_Key, _Compare, _Allocator>& __y)
751 return !(__x == __y);
754 template <class _Key, class _Compare, class _Allocator>
755 inline _LIBCPP_INLINE_VISIBILITY
757 operator> (const set<_Key, _Compare, _Allocator>& __x,
758 const set<_Key, _Compare, _Allocator>& __y)
763 template <class _Key, class _Compare, class _Allocator>
764 inline _LIBCPP_INLINE_VISIBILITY
766 operator>=(const set<_Key, _Compare, _Allocator>& __x,
767 const set<_Key, _Compare, _Allocator>& __y)
772 template <class _Key, class _Compare, class _Allocator>
773 inline _LIBCPP_INLINE_VISIBILITY
775 operator<=(const set<_Key, _Compare, _Allocator>& __x,
776 const set<_Key, _Compare, _Allocator>& __y)
781 // specialized algorithms:
782 template <class _Key, class _Compare, class _Allocator>
783 inline _LIBCPP_INLINE_VISIBILITY
785 swap(set<_Key, _Compare, _Allocator>& __x,
786 set<_Key, _Compare, _Allocator>& __y)
787 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
792 template <class _Key, class _Compare = less<_Key>,
793 class _Allocator = allocator<_Key> >
794 class _LIBCPP_TYPE_VIS_ONLY multiset
798 typedef _Key key_type;
799 typedef key_type value_type;
800 typedef _Compare key_compare;
801 typedef key_compare value_compare;
802 typedef _Allocator allocator_type;
803 typedef value_type& reference;
804 typedef const value_type& const_reference;
807 typedef __tree<value_type, value_compare, allocator_type> __base;
808 typedef allocator_traits<allocator_type> __alloc_traits;
809 typedef typename __base::__node_holder __node_holder;
814 typedef typename __base::pointer pointer;
815 typedef typename __base::const_pointer const_pointer;
816 typedef typename __base::size_type size_type;
817 typedef typename __base::difference_type difference_type;
818 typedef typename __base::const_iterator iterator;
819 typedef typename __base::const_iterator const_iterator;
820 typedef _VSTD::reverse_iterator<iterator> reverse_iterator;
821 typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator;
823 // construct/copy/destroy:
824 _LIBCPP_INLINE_VISIBILITY
825 explicit multiset(const value_compare& __comp = value_compare())
827 is_nothrow_default_constructible<allocator_type>::value &&
828 is_nothrow_default_constructible<key_compare>::value &&
829 is_nothrow_copy_constructible<key_compare>::value)
831 _LIBCPP_INLINE_VISIBILITY
832 multiset(const value_compare& __comp, const allocator_type& __a)
833 : __tree_(__comp, __a) {}
834 template <class _InputIterator>
835 _LIBCPP_INLINE_VISIBILITY
836 multiset(_InputIterator __f, _InputIterator __l,
837 const value_compare& __comp = value_compare())
843 #if _LIBCPP_STD_VER > 11
844 template <class _InputIterator>
845 _LIBCPP_INLINE_VISIBILITY
846 multiset(_InputIterator __f, _InputIterator __l, const allocator_type& __a)
847 : multiset(__f, __l, key_compare(), __a) {}
850 template <class _InputIterator>
851 _LIBCPP_INLINE_VISIBILITY
852 multiset(_InputIterator __f, _InputIterator __l,
853 const value_compare& __comp, const allocator_type& __a)
854 : __tree_(__comp, __a)
859 _LIBCPP_INLINE_VISIBILITY
860 multiset(const multiset& __s)
861 : __tree_(__s.__tree_.value_comp(),
862 __alloc_traits::select_on_container_copy_construction(__s.__tree_.__alloc()))
864 insert(__s.begin(), __s.end());
867 _LIBCPP_INLINE_VISIBILITY
868 multiset& operator=(const multiset& __s)
870 __tree_ = __s.__tree_;
874 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
875 _LIBCPP_INLINE_VISIBILITY
876 multiset(multiset&& __s)
877 _NOEXCEPT_(is_nothrow_move_constructible<__base>::value)
878 : __tree_(_VSTD::move(__s.__tree_)) {}
879 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
880 _LIBCPP_INLINE_VISIBILITY
881 explicit multiset(const allocator_type& __a)
883 _LIBCPP_INLINE_VISIBILITY
884 multiset(const multiset& __s, const allocator_type& __a)
885 : __tree_(__s.__tree_.value_comp(), __a)
887 insert(__s.begin(), __s.end());
889 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
890 multiset(multiset&& __s, const allocator_type& __a);
893 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
894 _LIBCPP_INLINE_VISIBILITY
895 multiset(initializer_list<value_type> __il, const value_compare& __comp = value_compare())
898 insert(__il.begin(), __il.end());
901 _LIBCPP_INLINE_VISIBILITY
902 multiset(initializer_list<value_type> __il, const value_compare& __comp,
903 const allocator_type& __a)
904 : __tree_(__comp, __a)
906 insert(__il.begin(), __il.end());
909 #if _LIBCPP_STD_VER > 11
910 _LIBCPP_INLINE_VISIBILITY
911 multiset(initializer_list<value_type> __il, const allocator_type& __a)
912 : multiset(__il, key_compare(), __a) {}
915 _LIBCPP_INLINE_VISIBILITY
916 multiset& operator=(initializer_list<value_type> __il)
918 __tree_.__assign_multi(__il.begin(), __il.end());
921 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
923 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
924 _LIBCPP_INLINE_VISIBILITY
925 multiset& operator=(multiset&& __s)
926 _NOEXCEPT_(is_nothrow_move_assignable<__base>::value)
928 __tree_ = _VSTD::move(__s.__tree_);
931 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
933 _LIBCPP_INLINE_VISIBILITY
934 iterator begin() _NOEXCEPT {return __tree_.begin();}
935 _LIBCPP_INLINE_VISIBILITY
936 const_iterator begin() const _NOEXCEPT {return __tree_.begin();}
937 _LIBCPP_INLINE_VISIBILITY
938 iterator end() _NOEXCEPT {return __tree_.end();}
939 _LIBCPP_INLINE_VISIBILITY
940 const_iterator end() const _NOEXCEPT {return __tree_.end();}
942 _LIBCPP_INLINE_VISIBILITY
943 reverse_iterator rbegin() _NOEXCEPT
944 {return reverse_iterator(end());}
945 _LIBCPP_INLINE_VISIBILITY
946 const_reverse_iterator rbegin() const _NOEXCEPT
947 {return const_reverse_iterator(end());}
948 _LIBCPP_INLINE_VISIBILITY
949 reverse_iterator rend() _NOEXCEPT
950 {return reverse_iterator(begin());}
951 _LIBCPP_INLINE_VISIBILITY
952 const_reverse_iterator rend() const _NOEXCEPT
953 {return const_reverse_iterator(begin());}
955 _LIBCPP_INLINE_VISIBILITY
956 const_iterator cbegin() const _NOEXCEPT {return begin();}
957 _LIBCPP_INLINE_VISIBILITY
958 const_iterator cend() const _NOEXCEPT {return end();}
959 _LIBCPP_INLINE_VISIBILITY
960 const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();}
961 _LIBCPP_INLINE_VISIBILITY
962 const_reverse_iterator crend() const _NOEXCEPT {return rend();}
964 _LIBCPP_INLINE_VISIBILITY
965 bool empty() const _NOEXCEPT {return __tree_.size() == 0;}
966 _LIBCPP_INLINE_VISIBILITY
967 size_type size() const _NOEXCEPT {return __tree_.size();}
968 _LIBCPP_INLINE_VISIBILITY
969 size_type max_size() const _NOEXCEPT {return __tree_.max_size();}
972 #if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
973 template <class... _Args>
974 _LIBCPP_INLINE_VISIBILITY
975 iterator emplace(_Args&&... __args)
976 {return __tree_.__emplace_multi(_VSTD::forward<_Args>(__args)...);}
977 template <class... _Args>
978 _LIBCPP_INLINE_VISIBILITY
979 iterator emplace_hint(const_iterator __p, _Args&&... __args)
980 {return __tree_.__emplace_hint_multi(__p, _VSTD::forward<_Args>(__args)...);}
981 #endif // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
982 _LIBCPP_INLINE_VISIBILITY
983 iterator insert(const value_type& __v)
984 {return __tree_.__insert_multi(__v);}
985 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
986 _LIBCPP_INLINE_VISIBILITY
987 iterator insert(value_type&& __v)
988 {return __tree_.__insert_multi(_VSTD::move(__v));}
989 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
990 _LIBCPP_INLINE_VISIBILITY
991 iterator insert(const_iterator __p, const value_type& __v)
992 {return __tree_.__insert_multi(__p, __v);}
993 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
994 _LIBCPP_INLINE_VISIBILITY
995 iterator insert(const_iterator __p, value_type&& __v)
996 {return __tree_.__insert_multi(_VSTD::move(__v));}
997 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
998 template <class _InputIterator>
999 _LIBCPP_INLINE_VISIBILITY
1000 void insert(_InputIterator __f, _InputIterator __l)
1002 for (const_iterator __e = cend(); __f != __l; ++__f)
1003 __tree_.__insert_multi(__e, *__f);
1006 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1007 _LIBCPP_INLINE_VISIBILITY
1008 void insert(initializer_list<value_type> __il)
1009 {insert(__il.begin(), __il.end());}
1010 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1012 _LIBCPP_INLINE_VISIBILITY
1013 iterator erase(const_iterator __p) {return __tree_.erase(__p);}
1014 _LIBCPP_INLINE_VISIBILITY
1015 size_type erase(const key_type& __k) {return __tree_.__erase_multi(__k);}
1016 _LIBCPP_INLINE_VISIBILITY
1017 iterator erase(const_iterator __f, const_iterator __l)
1018 {return __tree_.erase(__f, __l);}
1019 _LIBCPP_INLINE_VISIBILITY
1020 void clear() _NOEXCEPT {__tree_.clear();}
1022 _LIBCPP_INLINE_VISIBILITY
1023 void swap(multiset& __s)
1024 _NOEXCEPT_(__is_nothrow_swappable<__base>::value)
1025 {__tree_.swap(__s.__tree_);}
1027 _LIBCPP_INLINE_VISIBILITY
1028 allocator_type get_allocator() const _NOEXCEPT {return __tree_.__alloc();}
1029 _LIBCPP_INLINE_VISIBILITY
1030 key_compare key_comp() const {return __tree_.value_comp();}
1031 _LIBCPP_INLINE_VISIBILITY
1032 value_compare value_comp() const {return __tree_.value_comp();}
1035 _LIBCPP_INLINE_VISIBILITY
1036 iterator find(const key_type& __k) {return __tree_.find(__k);}
1037 _LIBCPP_INLINE_VISIBILITY
1038 const_iterator find(const key_type& __k) const {return __tree_.find(__k);}
1039 #if _LIBCPP_STD_VER > 11
1040 template <typename _K2>
1041 _LIBCPP_INLINE_VISIBILITY
1042 typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,iterator>::type
1043 find(const _K2& __k) {return __tree_.find(__k);}
1044 template <typename _K2>
1045 _LIBCPP_INLINE_VISIBILITY
1046 typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,const_iterator>::type
1047 find(const _K2& __k) const {return __tree_.find(__k);}
1050 _LIBCPP_INLINE_VISIBILITY
1051 size_type count(const key_type& __k) const
1052 {return __tree_.__count_multi(__k);}
1054 _LIBCPP_INLINE_VISIBILITY
1055 iterator lower_bound(const key_type& __k)
1056 {return __tree_.lower_bound(__k);}
1057 _LIBCPP_INLINE_VISIBILITY
1058 const_iterator lower_bound(const key_type& __k) const
1059 {return __tree_.lower_bound(__k);}
1060 #if _LIBCPP_STD_VER > 11
1061 template <typename _K2>
1062 _LIBCPP_INLINE_VISIBILITY
1063 typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,iterator>::type
1064 lower_bound(const _K2& __k) {return __tree_.lower_bound(__k);}
1066 template <typename _K2>
1067 _LIBCPP_INLINE_VISIBILITY
1068 typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,const_iterator>::type
1069 lower_bound(const _K2& __k) const {return __tree_.lower_bound(__k);}
1072 _LIBCPP_INLINE_VISIBILITY
1073 iterator upper_bound(const key_type& __k)
1074 {return __tree_.upper_bound(__k);}
1075 _LIBCPP_INLINE_VISIBILITY
1076 const_iterator upper_bound(const key_type& __k) const
1077 {return __tree_.upper_bound(__k);}
1078 #if _LIBCPP_STD_VER > 11
1079 template <typename _K2>
1080 _LIBCPP_INLINE_VISIBILITY
1081 typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,iterator>::type
1082 upper_bound(const _K2& __k) {return __tree_.upper_bound(__k);}
1083 template <typename _K2>
1084 _LIBCPP_INLINE_VISIBILITY
1085 typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,const_iterator>::type
1086 upper_bound(const _K2& __k) const {return __tree_.upper_bound(__k);}
1089 _LIBCPP_INLINE_VISIBILITY
1090 pair<iterator,iterator> equal_range(const key_type& __k)
1091 {return __tree_.__equal_range_multi(__k);}
1092 _LIBCPP_INLINE_VISIBILITY
1093 pair<const_iterator,const_iterator> equal_range(const key_type& __k) const
1094 {return __tree_.__equal_range_multi(__k);}
1095 #if _LIBCPP_STD_VER > 11
1096 template <typename _K2>
1097 _LIBCPP_INLINE_VISIBILITY
1098 typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,pair<iterator,iterator>>::type
1099 equal_range(const _K2& __k) {return __tree_.__equal_range_multi(__k);}
1100 template <typename _K2>
1101 _LIBCPP_INLINE_VISIBILITY
1102 typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,pair<const_iterator,const_iterator>>::type
1103 equal_range(const _K2& __k) const {return __tree_.__equal_range_multi(__k);}
1107 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1109 template <class _Key, class _Compare, class _Allocator>
1110 multiset<_Key, _Compare, _Allocator>::multiset(multiset&& __s, const allocator_type& __a)
1111 : __tree_(_VSTD::move(__s.__tree_), __a)
1113 if (__a != __s.get_allocator())
1115 const_iterator __e = cend();
1116 while (!__s.empty())
1117 insert(__e, _VSTD::move(__s.__tree_.remove(__s.begin())->__value_));
1121 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1123 template <class _Key, class _Compare, class _Allocator>
1124 inline _LIBCPP_INLINE_VISIBILITY
1126 operator==(const multiset<_Key, _Compare, _Allocator>& __x,
1127 const multiset<_Key, _Compare, _Allocator>& __y)
1129 return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin());
1132 template <class _Key, class _Compare, class _Allocator>
1133 inline _LIBCPP_INLINE_VISIBILITY
1135 operator< (const multiset<_Key, _Compare, _Allocator>& __x,
1136 const multiset<_Key, _Compare, _Allocator>& __y)
1138 return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
1141 template <class _Key, class _Compare, class _Allocator>
1142 inline _LIBCPP_INLINE_VISIBILITY
1144 operator!=(const multiset<_Key, _Compare, _Allocator>& __x,
1145 const multiset<_Key, _Compare, _Allocator>& __y)
1147 return !(__x == __y);
1150 template <class _Key, class _Compare, class _Allocator>
1151 inline _LIBCPP_INLINE_VISIBILITY
1153 operator> (const multiset<_Key, _Compare, _Allocator>& __x,
1154 const multiset<_Key, _Compare, _Allocator>& __y)
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 < __y);
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 !(__y < __x);
1177 template <class _Key, class _Compare, class _Allocator>
1178 inline _LIBCPP_INLINE_VISIBILITY
1180 swap(multiset<_Key, _Compare, _Allocator>& __x,
1181 multiset<_Key, _Compare, _Allocator>& __y)
1182 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
1187 _LIBCPP_END_NAMESPACE_STD
1189 #endif // _LIBCPP_SET