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);
71 set& operator=(const set& s);
72 set& operator=(set&& s)
74 allocator_type::propagate_on_container_move_assignment::value &&
75 is_nothrow_move_assignable<allocator_type>::value &&
76 is_nothrow_move_assignable<key_compare>::value);
77 set& operator=(initializer_list<value_type> il);
80 iterator begin() noexcept;
81 const_iterator begin() const noexcept;
82 iterator end() noexcept;
83 const_iterator end() const noexcept;
85 reverse_iterator rbegin() noexcept;
86 const_reverse_iterator rbegin() const noexcept;
87 reverse_iterator rend() noexcept;
88 const_reverse_iterator rend() const noexcept;
90 const_iterator cbegin() const noexcept;
91 const_iterator cend() const noexcept;
92 const_reverse_iterator crbegin() const noexcept;
93 const_reverse_iterator crend() const noexcept;
96 bool empty() const noexcept;
97 size_type size() const noexcept;
98 size_type max_size() const noexcept;
101 template <class... Args>
102 pair<iterator, bool> emplace(Args&&... args);
103 template <class... Args>
104 iterator emplace_hint(const_iterator position, Args&&... args);
105 pair<iterator,bool> insert(const value_type& v);
106 pair<iterator,bool> insert(value_type&& v);
107 iterator insert(const_iterator position, const value_type& v);
108 iterator insert(const_iterator position, value_type&& v);
109 template <class InputIterator>
110 void insert(InputIterator first, InputIterator last);
111 void insert(initializer_list<value_type> il);
113 iterator erase(const_iterator position);
114 size_type erase(const key_type& k);
115 iterator erase(const_iterator first, const_iterator last);
116 void clear() noexcept;
120 __is_nothrow_swappable<key_compare>::value &&
121 (!allocator_type::propagate_on_container_swap::value ||
122 __is_nothrow_swappable<allocator_type>::value));
125 allocator_type get_allocator() const noexcept;
126 key_compare key_comp() const;
127 value_compare value_comp() const;
130 iterator find(const key_type& k);
131 const_iterator find(const key_type& k) const;
132 size_type count(const key_type& k) const;
133 iterator lower_bound(const key_type& k);
134 const_iterator lower_bound(const key_type& k) const;
135 iterator upper_bound(const key_type& k);
136 const_iterator upper_bound(const key_type& k) const;
137 pair<iterator,iterator> equal_range(const key_type& k);
138 pair<const_iterator,const_iterator> equal_range(const key_type& k) const;
141 template <class Key, class Compare, class Allocator>
143 operator==(const set<Key, Compare, Allocator>& x,
144 const set<Key, Compare, Allocator>& y);
146 template <class Key, class Compare, class Allocator>
148 operator< (const set<Key, Compare, Allocator>& x,
149 const set<Key, Compare, Allocator>& y);
151 template <class Key, class Compare, class Allocator>
153 operator!=(const set<Key, Compare, Allocator>& x,
154 const set<Key, Compare, Allocator>& y);
156 template <class Key, class Compare, class Allocator>
158 operator> (const set<Key, Compare, Allocator>& x,
159 const set<Key, Compare, Allocator>& y);
161 template <class Key, class Compare, class Allocator>
163 operator>=(const set<Key, Compare, Allocator>& x,
164 const set<Key, Compare, Allocator>& y);
166 template <class Key, class Compare, class Allocator>
168 operator<=(const set<Key, Compare, Allocator>& x,
169 const set<Key, Compare, Allocator>& y);
171 // specialized algorithms:
172 template <class Key, class Compare, class Allocator>
174 swap(set<Key, Compare, Allocator>& x, set<Key, Compare, Allocator>& y)
175 noexcept(noexcept(x.swap(y)));
177 template <class Key, class Compare = less<Key>,
178 class Allocator = allocator<Key>>
183 typedef Key key_type;
184 typedef key_type value_type;
185 typedef Compare key_compare;
186 typedef key_compare value_compare;
187 typedef Allocator allocator_type;
188 typedef typename allocator_type::reference reference;
189 typedef typename allocator_type::const_reference const_reference;
190 typedef typename allocator_type::size_type size_type;
191 typedef typename allocator_type::difference_type difference_type;
192 typedef typename allocator_type::pointer pointer;
193 typedef typename allocator_type::const_pointer const_pointer;
195 typedef implementation-defined iterator;
196 typedef implementation-defined const_iterator;
197 typedef std::reverse_iterator<iterator> reverse_iterator;
198 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
200 // construct/copy/destroy:
203 is_nothrow_default_constructible<allocator_type>::value &&
204 is_nothrow_default_constructible<key_compare>::value &&
205 is_nothrow_copy_constructible<key_compare>::value);
206 explicit multiset(const value_compare& comp);
207 multiset(const value_compare& comp, const allocator_type& a);
208 template <class InputIterator>
209 multiset(InputIterator first, InputIterator last,
210 const value_compare& comp = value_compare());
211 template <class InputIterator>
212 multiset(InputIterator first, InputIterator last,
213 const value_compare& comp, const allocator_type& a);
214 multiset(const multiset& s);
215 multiset(multiset&& s)
217 is_nothrow_move_constructible<allocator_type>::value &&
218 is_nothrow_move_constructible<key_compare>::value);
219 explicit multiset(const allocator_type& a);
220 multiset(const multiset& s, const allocator_type& a);
221 multiset(multiset&& s, const allocator_type& a);
222 multiset(initializer_list<value_type> il, const value_compare& comp = value_compare());
223 multiset(initializer_list<value_type> il, const value_compare& comp,
224 const allocator_type& a);
227 multiset& operator=(const multiset& s);
228 multiset& operator=(multiset&& s)
230 allocator_type::propagate_on_container_move_assignment::value &&
231 is_nothrow_move_assignable<allocator_type>::value &&
232 is_nothrow_move_assignable<key_compare>::value);
233 multiset& operator=(initializer_list<value_type> il);
236 iterator begin() noexcept;
237 const_iterator begin() const noexcept;
238 iterator end() noexcept;
239 const_iterator end() const noexcept;
241 reverse_iterator rbegin() noexcept;
242 const_reverse_iterator rbegin() const noexcept;
243 reverse_iterator rend() noexcept;
244 const_reverse_iterator rend() const noexcept;
246 const_iterator cbegin() const noexcept;
247 const_iterator cend() const noexcept;
248 const_reverse_iterator crbegin() const noexcept;
249 const_reverse_iterator crend() const noexcept;
252 bool empty() const noexcept;
253 size_type size() const noexcept;
254 size_type max_size() const noexcept;
257 template <class... Args>
258 iterator emplace(Args&&... args);
259 template <class... Args>
260 iterator emplace_hint(const_iterator position, Args&&... args);
261 iterator insert(const value_type& v);
262 iterator insert(value_type&& v);
263 iterator insert(const_iterator position, const value_type& v);
264 iterator insert(const_iterator position, value_type&& v);
265 template <class InputIterator>
266 void insert(InputIterator first, InputIterator last);
267 void insert(initializer_list<value_type> il);
269 iterator erase(const_iterator position);
270 size_type erase(const key_type& k);
271 iterator erase(const_iterator first, const_iterator last);
272 void clear() noexcept;
274 void swap(multiset& s)
276 __is_nothrow_swappable<key_compare>::value &&
277 (!allocator_type::propagate_on_container_swap::value ||
278 __is_nothrow_swappable<allocator_type>::value));
281 allocator_type get_allocator() const noexcept;
282 key_compare key_comp() const;
283 value_compare value_comp() const;
286 iterator find(const key_type& k);
287 const_iterator find(const key_type& k) const;
288 size_type count(const key_type& k) const;
289 iterator lower_bound(const key_type& k);
290 const_iterator lower_bound(const key_type& k) const;
291 iterator upper_bound(const key_type& k);
292 const_iterator upper_bound(const key_type& k) const;
293 pair<iterator,iterator> equal_range(const key_type& k);
294 pair<const_iterator,const_iterator> equal_range(const key_type& k) const;
297 template <class Key, class Compare, class Allocator>
299 operator==(const multiset<Key, Compare, Allocator>& x,
300 const multiset<Key, Compare, Allocator>& y);
302 template <class Key, class Compare, class Allocator>
304 operator< (const multiset<Key, Compare, Allocator>& x,
305 const multiset<Key, Compare, Allocator>& y);
307 template <class Key, class Compare, class Allocator>
309 operator!=(const multiset<Key, Compare, Allocator>& x,
310 const multiset<Key, Compare, Allocator>& y);
312 template <class Key, class Compare, class Allocator>
314 operator> (const multiset<Key, Compare, Allocator>& x,
315 const multiset<Key, Compare, Allocator>& y);
317 template <class Key, class Compare, class Allocator>
319 operator>=(const multiset<Key, Compare, Allocator>& x,
320 const multiset<Key, Compare, Allocator>& y);
322 template <class Key, class Compare, class Allocator>
324 operator<=(const multiset<Key, Compare, Allocator>& x,
325 const multiset<Key, Compare, Allocator>& y);
327 // specialized algorithms:
328 template <class Key, class Compare, class Allocator>
330 swap(multiset<Key, Compare, Allocator>& x, multiset<Key, Compare, Allocator>& y)
331 noexcept(noexcept(x.swap(y)));
339 #include <functional>
341 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
342 #pragma GCC system_header
345 _LIBCPP_BEGIN_NAMESPACE_STD
347 template <class _Key, class _Compare = less<_Key>,
348 class _Allocator = allocator<_Key> >
349 class _LIBCPP_TYPE_VIS set
353 typedef _Key key_type;
354 typedef key_type value_type;
355 typedef _Compare key_compare;
356 typedef key_compare value_compare;
357 typedef _Allocator allocator_type;
358 typedef value_type& reference;
359 typedef const value_type& const_reference;
362 typedef __tree<value_type, value_compare, allocator_type> __base;
363 typedef allocator_traits<allocator_type> __alloc_traits;
364 typedef typename __base::__node_holder __node_holder;
369 typedef typename __base::pointer pointer;
370 typedef typename __base::const_pointer const_pointer;
371 typedef typename __base::size_type size_type;
372 typedef typename __base::difference_type difference_type;
373 typedef typename __base::const_iterator iterator;
374 typedef typename __base::const_iterator const_iterator;
375 typedef _VSTD::reverse_iterator<iterator> reverse_iterator;
376 typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator;
378 _LIBCPP_INLINE_VISIBILITY
379 explicit set(const value_compare& __comp = value_compare())
381 is_nothrow_default_constructible<allocator_type>::value &&
382 is_nothrow_default_constructible<key_compare>::value &&
383 is_nothrow_copy_constructible<key_compare>::value)
385 _LIBCPP_INLINE_VISIBILITY
386 set(const value_compare& __comp, const allocator_type& __a)
387 : __tree_(__comp, __a) {}
388 template <class _InputIterator>
389 _LIBCPP_INLINE_VISIBILITY
390 set(_InputIterator __f, _InputIterator __l,
391 const value_compare& __comp = value_compare())
397 template <class _InputIterator>
398 _LIBCPP_INLINE_VISIBILITY
399 set(_InputIterator __f, _InputIterator __l, const value_compare& __comp,
400 const allocator_type& __a)
401 : __tree_(__comp, __a)
406 _LIBCPP_INLINE_VISIBILITY
408 : __tree_(__s.__tree_)
410 insert(__s.begin(), __s.end());
413 _LIBCPP_INLINE_VISIBILITY
414 set& operator=(const set& __s)
416 __tree_ = __s.__tree_;
420 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
421 _LIBCPP_INLINE_VISIBILITY
423 _NOEXCEPT_(is_nothrow_move_constructible<__base>::value)
424 : __tree_(_VSTD::move(__s.__tree_)) {}
425 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
427 _LIBCPP_INLINE_VISIBILITY
428 explicit set(const allocator_type& __a)
431 _LIBCPP_INLINE_VISIBILITY
432 set(const set& __s, const allocator_type& __a)
433 : __tree_(__s.__tree_.value_comp(), __a)
435 insert(__s.begin(), __s.end());
438 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
439 set(set&& __s, const allocator_type& __a);
442 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
443 _LIBCPP_INLINE_VISIBILITY
444 set(initializer_list<value_type> __il, const value_compare& __comp = value_compare())
447 insert(__il.begin(), __il.end());
450 _LIBCPP_INLINE_VISIBILITY
451 set(initializer_list<value_type> __il, const value_compare& __comp,
452 const allocator_type& __a)
453 : __tree_(__comp, __a)
455 insert(__il.begin(), __il.end());
458 _LIBCPP_INLINE_VISIBILITY
459 set& operator=(initializer_list<value_type> __il)
461 __tree_.__assign_unique(__il.begin(), __il.end());
464 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
466 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
467 _LIBCPP_INLINE_VISIBILITY
468 set& operator=(set&& __s)
469 _NOEXCEPT_(is_nothrow_move_assignable<__base>::value)
471 __tree_ = _VSTD::move(__s.__tree_);
474 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
476 _LIBCPP_INLINE_VISIBILITY
477 iterator begin() _NOEXCEPT {return __tree_.begin();}
478 _LIBCPP_INLINE_VISIBILITY
479 const_iterator begin() const _NOEXCEPT {return __tree_.begin();}
480 _LIBCPP_INLINE_VISIBILITY
481 iterator end() _NOEXCEPT {return __tree_.end();}
482 _LIBCPP_INLINE_VISIBILITY
483 const_iterator end() const _NOEXCEPT {return __tree_.end();}
485 _LIBCPP_INLINE_VISIBILITY
486 reverse_iterator rbegin() _NOEXCEPT
487 {return reverse_iterator(end());}
488 _LIBCPP_INLINE_VISIBILITY
489 const_reverse_iterator rbegin() const _NOEXCEPT
490 {return const_reverse_iterator(end());}
491 _LIBCPP_INLINE_VISIBILITY
492 reverse_iterator rend() _NOEXCEPT
493 {return reverse_iterator(begin());}
494 _LIBCPP_INLINE_VISIBILITY
495 const_reverse_iterator rend() const _NOEXCEPT
496 {return const_reverse_iterator(begin());}
498 _LIBCPP_INLINE_VISIBILITY
499 const_iterator cbegin() const _NOEXCEPT {return begin();}
500 _LIBCPP_INLINE_VISIBILITY
501 const_iterator cend() const _NOEXCEPT {return end();}
502 _LIBCPP_INLINE_VISIBILITY
503 const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();}
504 _LIBCPP_INLINE_VISIBILITY
505 const_reverse_iterator crend() const _NOEXCEPT {return rend();}
507 _LIBCPP_INLINE_VISIBILITY
508 bool empty() const _NOEXCEPT {return __tree_.size() == 0;}
509 _LIBCPP_INLINE_VISIBILITY
510 size_type size() const _NOEXCEPT {return __tree_.size();}
511 _LIBCPP_INLINE_VISIBILITY
512 size_type max_size() const _NOEXCEPT {return __tree_.max_size();}
515 #if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
516 template <class... _Args>
517 _LIBCPP_INLINE_VISIBILITY
518 pair<iterator, bool> emplace(_Args&&... __args)
519 {return __tree_.__emplace_unique(_VSTD::forward<_Args>(__args)...);}
520 template <class... _Args>
521 _LIBCPP_INLINE_VISIBILITY
522 iterator emplace_hint(const_iterator __p, _Args&&... __args)
523 {return __tree_.__emplace_hint_unique(__p, _VSTD::forward<_Args>(__args)...);}
524 #endif // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
525 _LIBCPP_INLINE_VISIBILITY
526 pair<iterator,bool> insert(const value_type& __v)
527 {return __tree_.__insert_unique(__v);}
528 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
529 _LIBCPP_INLINE_VISIBILITY
530 pair<iterator,bool> insert(value_type&& __v)
531 {return __tree_.__insert_unique(_VSTD::move(__v));}
532 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
533 _LIBCPP_INLINE_VISIBILITY
534 iterator insert(const_iterator __p, const value_type& __v)
535 {return __tree_.__insert_unique(__p, __v);}
536 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
537 _LIBCPP_INLINE_VISIBILITY
538 iterator insert(const_iterator __p, value_type&& __v)
539 {return __tree_.__insert_unique(__p, _VSTD::move(__v));}
540 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
541 template <class _InputIterator>
542 _LIBCPP_INLINE_VISIBILITY
543 void insert(_InputIterator __f, _InputIterator __l)
545 for (const_iterator __e = cend(); __f != __l; ++__f)
546 __tree_.__insert_unique(__e, *__f);
549 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
550 _LIBCPP_INLINE_VISIBILITY
551 void insert(initializer_list<value_type> __il)
552 {insert(__il.begin(), __il.end());}
553 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
555 _LIBCPP_INLINE_VISIBILITY
556 iterator erase(const_iterator __p) {return __tree_.erase(__p);}
557 _LIBCPP_INLINE_VISIBILITY
558 size_type erase(const key_type& __k)
559 {return __tree_.__erase_unique(__k);}
560 _LIBCPP_INLINE_VISIBILITY
561 iterator erase(const_iterator __f, const_iterator __l)
562 {return __tree_.erase(__f, __l);}
563 _LIBCPP_INLINE_VISIBILITY
564 void clear() _NOEXCEPT {__tree_.clear();}
566 _LIBCPP_INLINE_VISIBILITY
567 void swap(set& __s) _NOEXCEPT_(__is_nothrow_swappable<__base>::value)
568 {__tree_.swap(__s.__tree_);}
570 _LIBCPP_INLINE_VISIBILITY
571 allocator_type get_allocator() const _NOEXCEPT {return __tree_.__alloc();}
572 _LIBCPP_INLINE_VISIBILITY
573 key_compare key_comp() const {return __tree_.value_comp();}
574 _LIBCPP_INLINE_VISIBILITY
575 value_compare value_comp() const {return __tree_.value_comp();}
578 _LIBCPP_INLINE_VISIBILITY
579 iterator find(const key_type& __k) {return __tree_.find(__k);}
580 _LIBCPP_INLINE_VISIBILITY
581 const_iterator find(const key_type& __k) const {return __tree_.find(__k);}
582 _LIBCPP_INLINE_VISIBILITY
583 size_type count(const key_type& __k) const
584 {return __tree_.__count_unique(__k);}
585 _LIBCPP_INLINE_VISIBILITY
586 iterator lower_bound(const key_type& __k)
587 {return __tree_.lower_bound(__k);}
588 _LIBCPP_INLINE_VISIBILITY
589 const_iterator lower_bound(const key_type& __k) const
590 {return __tree_.lower_bound(__k);}
591 _LIBCPP_INLINE_VISIBILITY
592 iterator upper_bound(const key_type& __k)
593 {return __tree_.upper_bound(__k);}
594 _LIBCPP_INLINE_VISIBILITY
595 const_iterator upper_bound(const key_type& __k) const
596 {return __tree_.upper_bound(__k);}
597 _LIBCPP_INLINE_VISIBILITY
598 pair<iterator,iterator> equal_range(const key_type& __k)
599 {return __tree_.__equal_range_unique(__k);}
600 _LIBCPP_INLINE_VISIBILITY
601 pair<const_iterator,const_iterator> equal_range(const key_type& __k) const
602 {return __tree_.__equal_range_unique(__k);}
605 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
607 template <class _Key, class _Compare, class _Allocator>
608 set<_Key, _Compare, _Allocator>::set(set&& __s, const allocator_type& __a)
609 : __tree_(_VSTD::move(__s.__tree_), __a)
611 if (__a != __s.get_allocator())
613 const_iterator __e = cend();
615 insert(__e, _VSTD::move(__s.__tree_.remove(__s.begin())->__value_));
619 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
621 template <class _Key, class _Compare, class _Allocator>
622 inline _LIBCPP_INLINE_VISIBILITY
624 operator==(const set<_Key, _Compare, _Allocator>& __x,
625 const set<_Key, _Compare, _Allocator>& __y)
627 return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin());
630 template <class _Key, class _Compare, class _Allocator>
631 inline _LIBCPP_INLINE_VISIBILITY
633 operator< (const set<_Key, _Compare, _Allocator>& __x,
634 const set<_Key, _Compare, _Allocator>& __y)
636 return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
639 template <class _Key, class _Compare, class _Allocator>
640 inline _LIBCPP_INLINE_VISIBILITY
642 operator!=(const set<_Key, _Compare, _Allocator>& __x,
643 const set<_Key, _Compare, _Allocator>& __y)
645 return !(__x == __y);
648 template <class _Key, class _Compare, class _Allocator>
649 inline _LIBCPP_INLINE_VISIBILITY
651 operator> (const set<_Key, _Compare, _Allocator>& __x,
652 const set<_Key, _Compare, _Allocator>& __y)
657 template <class _Key, class _Compare, class _Allocator>
658 inline _LIBCPP_INLINE_VISIBILITY
660 operator>=(const set<_Key, _Compare, _Allocator>& __x,
661 const set<_Key, _Compare, _Allocator>& __y)
666 template <class _Key, class _Compare, class _Allocator>
667 inline _LIBCPP_INLINE_VISIBILITY
669 operator<=(const set<_Key, _Compare, _Allocator>& __x,
670 const set<_Key, _Compare, _Allocator>& __y)
675 // specialized algorithms:
676 template <class _Key, class _Compare, class _Allocator>
677 inline _LIBCPP_INLINE_VISIBILITY
679 swap(set<_Key, _Compare, _Allocator>& __x,
680 set<_Key, _Compare, _Allocator>& __y)
681 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
686 template <class _Key, class _Compare = less<_Key>,
687 class _Allocator = allocator<_Key> >
688 class _LIBCPP_TYPE_VIS multiset
692 typedef _Key key_type;
693 typedef key_type value_type;
694 typedef _Compare key_compare;
695 typedef key_compare value_compare;
696 typedef _Allocator allocator_type;
697 typedef value_type& reference;
698 typedef const value_type& const_reference;
701 typedef __tree<value_type, value_compare, allocator_type> __base;
702 typedef allocator_traits<allocator_type> __alloc_traits;
703 typedef typename __base::__node_holder __node_holder;
708 typedef typename __base::pointer pointer;
709 typedef typename __base::const_pointer const_pointer;
710 typedef typename __base::size_type size_type;
711 typedef typename __base::difference_type difference_type;
712 typedef typename __base::const_iterator iterator;
713 typedef typename __base::const_iterator const_iterator;
714 typedef _VSTD::reverse_iterator<iterator> reverse_iterator;
715 typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator;
717 // construct/copy/destroy:
718 _LIBCPP_INLINE_VISIBILITY
719 explicit multiset(const value_compare& __comp = value_compare())
721 is_nothrow_default_constructible<allocator_type>::value &&
722 is_nothrow_default_constructible<key_compare>::value &&
723 is_nothrow_copy_constructible<key_compare>::value)
725 _LIBCPP_INLINE_VISIBILITY
726 multiset(const value_compare& __comp, const allocator_type& __a)
727 : __tree_(__comp, __a) {}
728 template <class _InputIterator>
729 _LIBCPP_INLINE_VISIBILITY
730 multiset(_InputIterator __f, _InputIterator __l,
731 const value_compare& __comp = value_compare())
737 template <class _InputIterator>
738 _LIBCPP_INLINE_VISIBILITY
739 multiset(_InputIterator __f, _InputIterator __l,
740 const value_compare& __comp, const allocator_type& __a)
741 : __tree_(__comp, __a)
746 _LIBCPP_INLINE_VISIBILITY
747 multiset(const multiset& __s)
748 : __tree_(__s.__tree_.value_comp(),
749 __alloc_traits::select_on_container_copy_construction(__s.__tree_.__alloc()))
751 insert(__s.begin(), __s.end());
754 _LIBCPP_INLINE_VISIBILITY
755 multiset& operator=(const multiset& __s)
757 __tree_ = __s.__tree_;
761 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
762 _LIBCPP_INLINE_VISIBILITY
763 multiset(multiset&& __s)
764 _NOEXCEPT_(is_nothrow_move_constructible<__base>::value)
765 : __tree_(_VSTD::move(__s.__tree_)) {}
766 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
767 _LIBCPP_INLINE_VISIBILITY
768 explicit multiset(const allocator_type& __a)
770 _LIBCPP_INLINE_VISIBILITY
771 multiset(const multiset& __s, const allocator_type& __a)
772 : __tree_(__s.__tree_.value_comp(), __a)
774 insert(__s.begin(), __s.end());
776 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
777 multiset(multiset&& __s, const allocator_type& __a);
780 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
781 _LIBCPP_INLINE_VISIBILITY
782 multiset(initializer_list<value_type> __il, const value_compare& __comp = value_compare())
785 insert(__il.begin(), __il.end());
788 _LIBCPP_INLINE_VISIBILITY
789 multiset(initializer_list<value_type> __il, const value_compare& __comp,
790 const allocator_type& __a)
791 : __tree_(__comp, __a)
793 insert(__il.begin(), __il.end());
796 _LIBCPP_INLINE_VISIBILITY
797 multiset& operator=(initializer_list<value_type> __il)
799 __tree_.__assign_multi(__il.begin(), __il.end());
802 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
804 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
805 _LIBCPP_INLINE_VISIBILITY
806 multiset& operator=(multiset&& __s)
807 _NOEXCEPT_(is_nothrow_move_assignable<__base>::value)
809 __tree_ = _VSTD::move(__s.__tree_);
812 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
814 _LIBCPP_INLINE_VISIBILITY
815 iterator begin() _NOEXCEPT {return __tree_.begin();}
816 _LIBCPP_INLINE_VISIBILITY
817 const_iterator begin() const _NOEXCEPT {return __tree_.begin();}
818 _LIBCPP_INLINE_VISIBILITY
819 iterator end() _NOEXCEPT {return __tree_.end();}
820 _LIBCPP_INLINE_VISIBILITY
821 const_iterator end() const _NOEXCEPT {return __tree_.end();}
823 _LIBCPP_INLINE_VISIBILITY
824 reverse_iterator rbegin() _NOEXCEPT
825 {return reverse_iterator(end());}
826 _LIBCPP_INLINE_VISIBILITY
827 const_reverse_iterator rbegin() const _NOEXCEPT
828 {return const_reverse_iterator(end());}
829 _LIBCPP_INLINE_VISIBILITY
830 reverse_iterator rend() _NOEXCEPT
831 {return reverse_iterator(begin());}
832 _LIBCPP_INLINE_VISIBILITY
833 const_reverse_iterator rend() const _NOEXCEPT
834 {return const_reverse_iterator(begin());}
836 _LIBCPP_INLINE_VISIBILITY
837 const_iterator cbegin() const _NOEXCEPT {return begin();}
838 _LIBCPP_INLINE_VISIBILITY
839 const_iterator cend() const _NOEXCEPT {return end();}
840 _LIBCPP_INLINE_VISIBILITY
841 const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();}
842 _LIBCPP_INLINE_VISIBILITY
843 const_reverse_iterator crend() const _NOEXCEPT {return rend();}
845 _LIBCPP_INLINE_VISIBILITY
846 bool empty() const _NOEXCEPT {return __tree_.size() == 0;}
847 _LIBCPP_INLINE_VISIBILITY
848 size_type size() const _NOEXCEPT {return __tree_.size();}
849 _LIBCPP_INLINE_VISIBILITY
850 size_type max_size() const _NOEXCEPT {return __tree_.max_size();}
853 #if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
854 template <class... _Args>
855 _LIBCPP_INLINE_VISIBILITY
856 iterator emplace(_Args&&... __args)
857 {return __tree_.__emplace_multi(_VSTD::forward<_Args>(__args)...);}
858 template <class... _Args>
859 _LIBCPP_INLINE_VISIBILITY
860 iterator emplace_hint(const_iterator __p, _Args&&... __args)
861 {return __tree_.__emplace_hint_multi(__p, _VSTD::forward<_Args>(__args)...);}
862 #endif // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
863 _LIBCPP_INLINE_VISIBILITY
864 iterator insert(const value_type& __v)
865 {return __tree_.__insert_multi(__v);}
866 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
867 _LIBCPP_INLINE_VISIBILITY
868 iterator insert(value_type&& __v)
869 {return __tree_.__insert_multi(_VSTD::move(__v));}
870 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
871 _LIBCPP_INLINE_VISIBILITY
872 iterator insert(const_iterator __p, const value_type& __v)
873 {return __tree_.__insert_multi(__p, __v);}
874 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
875 _LIBCPP_INLINE_VISIBILITY
876 iterator insert(const_iterator __p, value_type&& __v)
877 {return __tree_.__insert_multi(_VSTD::move(__v));}
878 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
879 template <class _InputIterator>
880 _LIBCPP_INLINE_VISIBILITY
881 void insert(_InputIterator __f, _InputIterator __l)
883 for (const_iterator __e = cend(); __f != __l; ++__f)
884 __tree_.__insert_multi(__e, *__f);
887 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
888 _LIBCPP_INLINE_VISIBILITY
889 void insert(initializer_list<value_type> __il)
890 {insert(__il.begin(), __il.end());}
891 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
893 _LIBCPP_INLINE_VISIBILITY
894 iterator erase(const_iterator __p) {return __tree_.erase(__p);}
895 _LIBCPP_INLINE_VISIBILITY
896 size_type erase(const key_type& __k) {return __tree_.__erase_multi(__k);}
897 _LIBCPP_INLINE_VISIBILITY
898 iterator erase(const_iterator __f, const_iterator __l)
899 {return __tree_.erase(__f, __l);}
900 _LIBCPP_INLINE_VISIBILITY
901 void clear() _NOEXCEPT {__tree_.clear();}
903 _LIBCPP_INLINE_VISIBILITY
904 void swap(multiset& __s)
905 _NOEXCEPT_(__is_nothrow_swappable<__base>::value)
906 {__tree_.swap(__s.__tree_);}
908 _LIBCPP_INLINE_VISIBILITY
909 allocator_type get_allocator() const _NOEXCEPT {return __tree_.__alloc();}
910 _LIBCPP_INLINE_VISIBILITY
911 key_compare key_comp() const {return __tree_.value_comp();}
912 _LIBCPP_INLINE_VISIBILITY
913 value_compare value_comp() const {return __tree_.value_comp();}
916 _LIBCPP_INLINE_VISIBILITY
917 iterator find(const key_type& __k) {return __tree_.find(__k);}
918 _LIBCPP_INLINE_VISIBILITY
919 const_iterator find(const key_type& __k) const {return __tree_.find(__k);}
920 _LIBCPP_INLINE_VISIBILITY
921 size_type count(const key_type& __k) const
922 {return __tree_.__count_multi(__k);}
923 _LIBCPP_INLINE_VISIBILITY
924 iterator lower_bound(const key_type& __k)
925 {return __tree_.lower_bound(__k);}
926 _LIBCPP_INLINE_VISIBILITY
927 const_iterator lower_bound(const key_type& __k) const
928 {return __tree_.lower_bound(__k);}
929 _LIBCPP_INLINE_VISIBILITY
930 iterator upper_bound(const key_type& __k)
931 {return __tree_.upper_bound(__k);}
932 _LIBCPP_INLINE_VISIBILITY
933 const_iterator upper_bound(const key_type& __k) const
934 {return __tree_.upper_bound(__k);}
935 _LIBCPP_INLINE_VISIBILITY
936 pair<iterator,iterator> equal_range(const key_type& __k)
937 {return __tree_.__equal_range_multi(__k);}
938 _LIBCPP_INLINE_VISIBILITY
939 pair<const_iterator,const_iterator> equal_range(const key_type& __k) const
940 {return __tree_.__equal_range_multi(__k);}
943 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
945 template <class _Key, class _Compare, class _Allocator>
946 multiset<_Key, _Compare, _Allocator>::multiset(multiset&& __s, const allocator_type& __a)
947 : __tree_(_VSTD::move(__s.__tree_), __a)
949 if (__a != __s.get_allocator())
951 const_iterator __e = cend();
953 insert(__e, _VSTD::move(__s.__tree_.remove(__s.begin())->__value_));
957 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
959 template <class _Key, class _Compare, class _Allocator>
960 inline _LIBCPP_INLINE_VISIBILITY
962 operator==(const multiset<_Key, _Compare, _Allocator>& __x,
963 const multiset<_Key, _Compare, _Allocator>& __y)
965 return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin());
968 template <class _Key, class _Compare, class _Allocator>
969 inline _LIBCPP_INLINE_VISIBILITY
971 operator< (const multiset<_Key, _Compare, _Allocator>& __x,
972 const multiset<_Key, _Compare, _Allocator>& __y)
974 return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
977 template <class _Key, class _Compare, class _Allocator>
978 inline _LIBCPP_INLINE_VISIBILITY
980 operator!=(const multiset<_Key, _Compare, _Allocator>& __x,
981 const multiset<_Key, _Compare, _Allocator>& __y)
983 return !(__x == __y);
986 template <class _Key, class _Compare, class _Allocator>
987 inline _LIBCPP_INLINE_VISIBILITY
989 operator> (const multiset<_Key, _Compare, _Allocator>& __x,
990 const multiset<_Key, _Compare, _Allocator>& __y)
995 template <class _Key, class _Compare, class _Allocator>
996 inline _LIBCPP_INLINE_VISIBILITY
998 operator>=(const multiset<_Key, _Compare, _Allocator>& __x,
999 const multiset<_Key, _Compare, _Allocator>& __y)
1001 return !(__x < __y);
1004 template <class _Key, class _Compare, class _Allocator>
1005 inline _LIBCPP_INLINE_VISIBILITY
1007 operator<=(const multiset<_Key, _Compare, _Allocator>& __x,
1008 const multiset<_Key, _Compare, _Allocator>& __y)
1010 return !(__y < __x);
1013 template <class _Key, class _Compare, class _Allocator>
1014 inline _LIBCPP_INLINE_VISIBILITY
1016 swap(multiset<_Key, _Compare, _Allocator>& __x,
1017 multiset<_Key, _Compare, _Allocator>& __y)
1018 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
1023 _LIBCPP_END_NAMESPACE_STD
1025 #endif // _LIBCPP_SET