56 #ifndef _STL_MULTISET_H
57 #define _STL_MULTISET_H 1
60 #if __cplusplus >= 201103L
64 namespace std _GLIBCXX_VISIBILITY(default)
66 _GLIBCXX_BEGIN_NAMESPACE_VERSION
67 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
69 template<
typename _Key,
typename _Compare,
typename _Alloc>
94 template <
typename _Key,
typename _Compare = std::less<_Key>,
95 typename _Alloc = std::allocator<_Key> >
98 #ifdef _GLIBCXX_CONCEPT_CHECKS
100 typedef typename _Alloc::value_type _Alloc_value_type;
101 # if __cplusplus < 201103L
102 __glibcxx_class_requires(_Key, _SGIAssignableConcept)
104 __glibcxx_class_requires4(_Compare,
bool, _Key, _Key,
105 _BinaryFunctionConcept)
106 __glibcxx_class_requires2(_Key, _Alloc_value_type, _SameTypeConcept)
109 #if __cplusplus >= 201103L
110 static_assert(
is_same<
typename remove_cv<_Key>::type, _Key>::value,
111 "std::multiset must have a non-const, non-volatile value_type");
112 # if __cplusplus > 201703L || defined __STRICT_ANSI__
114 "std::multiset must have the same value_type as its allocator");
120 typedef _Key key_type;
121 typedef _Key value_type;
122 typedef _Compare key_compare;
123 typedef _Compare value_compare;
124 typedef _Alloc allocator_type;
129 rebind<_Key>::other _Key_alloc_type;
131 typedef _Rb_tree<key_type, value_type, _Identity<value_type>,
132 key_compare, _Key_alloc_type> _Rep_type;
139 typedef typename _Alloc_traits::pointer pointer;
140 typedef typename _Alloc_traits::const_pointer const_pointer;
141 typedef typename _Alloc_traits::reference reference;
142 typedef typename _Alloc_traits::const_reference const_reference;
146 typedef typename _Rep_type::const_iterator iterator;
147 typedef typename _Rep_type::const_iterator const_iterator;
150 typedef typename _Rep_type::size_type size_type;
151 typedef typename _Rep_type::difference_type difference_type;
153 #if __cplusplus > 201402L
154 using node_type =
typename _Rep_type::node_type;
161 #if __cplusplus < 201103L
174 const allocator_type& __a = allocator_type())
175 : _M_t(__comp, _Key_alloc_type(__a)) { }
186 template<
typename _InputIterator>
187 multiset(_InputIterator __first, _InputIterator __last)
189 { _M_t._M_insert_range_equal(__first, __last); }
202 template<
typename _InputIterator>
203 multiset(_InputIterator __first, _InputIterator __last,
204 const _Compare& __comp,
205 const allocator_type& __a = allocator_type())
206 : _M_t(__comp, _Key_alloc_type(__a))
207 { _M_t._M_insert_range_equal(__first, __last); }
214 #if __cplusplus < 201103L
240 const _Compare& __comp = _Compare(),
241 const allocator_type& __a = allocator_type())
242 : _M_t(__comp, _Key_alloc_type(__a))
243 { _M_t._M_insert_range_equal(__l.begin(), __l.end()); }
248 : _M_t(_Key_alloc_type(__a)) { }
252 : _M_t(__m._M_t, _Key_alloc_type(__a)) { }
257 && _Alloc_traits::_S_always_equal())
258 : _M_t(
std::
move(__m._M_t), _Key_alloc_type(__a)) { }
262 : _M_t(_Key_alloc_type(__a))
263 { _M_t._M_insert_range_equal(__l.begin(), __l.end()); }
266 template<
typename _InputIterator>
267 multiset(_InputIterator __first, _InputIterator __last,
268 const allocator_type& __a)
269 : _M_t(_Key_alloc_type(__a))
270 { _M_t._M_insert_range_equal(__first, __last); }
285 #if __cplusplus < 201103L
314 _M_t._M_assign_equal(__l.begin(), __l.end());
324 {
return _M_t.key_comp(); }
328 {
return _M_t.key_comp(); }
332 {
return allocator_type(_M_t.get_allocator()); }
341 {
return _M_t.begin(); }
349 end() const _GLIBCXX_NOEXCEPT
350 {
return _M_t.end(); }
359 {
return _M_t.rbegin(); }
368 {
return _M_t.rend(); }
370 #if __cplusplus >= 201103L
378 {
return _M_t.begin(); }
387 {
return _M_t.end(); }
396 {
return _M_t.rbegin(); }
405 {
return _M_t.rend(); }
409 _GLIBCXX_NODISCARD
bool
411 {
return _M_t.empty(); }
416 {
return _M_t.size(); }
421 {
return _M_t.max_size(); }
438 _GLIBCXX_NOEXCEPT_IF(__is_nothrow_swappable<_Compare>::value)
439 { _M_t.swap(__x._M_t); }
442 #if __cplusplus >= 201103L
455 template<
typename... _Args>
458 {
return _M_t._M_emplace_equal(std::forward<_Args>(__args)...); }
481 template<
typename... _Args>
485 return _M_t._M_emplace_hint_equal(__pos,
486 std::forward<_Args>(__args)...);
503 {
return _M_t._M_insert_equal(__x); }
505 #if __cplusplus >= 201103L
508 {
return _M_t._M_insert_equal(
std::move(__x)); }
532 insert(const_iterator __position,
const value_type& __x)
533 {
return _M_t._M_insert_equal_(__position, __x); }
535 #if __cplusplus >= 201103L
537 insert(const_iterator __position, value_type&& __x)
538 {
return _M_t._M_insert_equal_(__position,
std::move(__x)); }
549 template<
typename _InputIterator>
551 insert(_InputIterator __first, _InputIterator __last)
552 { _M_t._M_insert_range_equal(__first, __last); }
554 #if __cplusplus >= 201103L
564 { this->
insert(__l.begin(), __l.end()); }
567 #if __cplusplus > 201402L
570 extract(const_iterator __pos)
572 __glibcxx_assert(__pos !=
end());
573 return _M_t.extract(__pos);
578 extract(
const key_type& __x)
579 {
return _M_t.extract(__x); }
584 {
return _M_t._M_reinsert_node_equal(
std::move(__nh)); }
588 insert(const_iterator __hint, node_type&& __nh)
589 {
return _M_t._M_reinsert_node_hint_equal(__hint,
std::move(__nh)); }
591 template<
typename,
typename>
592 friend class std::_Rb_tree_merge_helper;
594 template<
typename _Compare1>
596 merge(multiset<_Key, _Compare1, _Alloc>& __source)
598 using _Merge_helper = _Rb_tree_merge_helper<multiset, _Compare1>;
599 _M_t._M_merge_equal(_Merge_helper::_S_get_tree(__source));
602 template<
typename _Compare1>
604 merge(multiset<_Key, _Compare1, _Alloc>&& __source)
607 template<
typename _Compare1>
609 merge(set<_Key, _Compare1, _Alloc>& __source)
611 using _Merge_helper = _Rb_tree_merge_helper<multiset, _Compare1>;
612 _M_t._M_merge_equal(_Merge_helper::_S_get_tree(__source));
615 template<
typename _Compare1>
617 merge(set<_Key, _Compare1, _Alloc>&& __source)
621 #if __cplusplus >= 201103L
637 _GLIBCXX_ABI_TAG_CXX11
640 {
return _M_t.erase(__position); }
654 { _M_t.erase(__position); }
670 {
return _M_t.erase(__x); }
672 #if __cplusplus >= 201103L
689 _GLIBCXX_ABI_TAG_CXX11
691 erase(const_iterator __first, const_iterator __last)
692 {
return _M_t.erase(__first, __last); }
708 { _M_t.erase(__first, __last); }
731 {
return _M_t.count(__x); }
733 #if __cplusplus > 201103L
734 template<
typename _Kt>
736 count(
const _Kt& __x)
const -> decltype(_M_t._M_count_tr(__x))
737 {
return _M_t._M_count_tr(__x); }
741 #if __cplusplus > 201703L
749 contains(
const key_type& __x)
const
750 {
return _M_t.find(__x) != _M_t.end(); }
752 template<
typename _Kt>
754 contains(
const _Kt& __x)
const
755 -> decltype(_M_t._M_find_tr(__x),
void(),
true)
756 {
return _M_t._M_find_tr(__x) != _M_t.end(); }
776 {
return _M_t.find(__x); }
779 find(
const key_type& __x)
const
780 {
return _M_t.find(__x); }
782 #if __cplusplus > 201103L
783 template<
typename _Kt>
786 -> decltype(iterator{_M_t._M_find_tr(__x)})
787 {
return iterator{_M_t._M_find_tr(__x)}; }
789 template<
typename _Kt>
791 find(
const _Kt& __x)
const
792 -> decltype(const_iterator{_M_t._M_find_tr(__x)})
793 {
return const_iterator{_M_t._M_find_tr(__x)}; }
811 {
return _M_t.lower_bound(__x); }
815 {
return _M_t.lower_bound(__x); }
817 #if __cplusplus > 201103L
818 template<
typename _Kt>
821 -> decltype(iterator(_M_t._M_lower_bound_tr(__x)))
822 {
return iterator(_M_t._M_lower_bound_tr(__x)); }
824 template<
typename _Kt>
827 -> decltype(iterator(_M_t._M_lower_bound_tr(__x)))
828 {
return iterator(_M_t._M_lower_bound_tr(__x)); }
841 {
return _M_t.upper_bound(__x); }
845 {
return _M_t.upper_bound(__x); }
847 #if __cplusplus > 201103L
848 template<
typename _Kt>
851 -> decltype(iterator(_M_t._M_upper_bound_tr(__x)))
852 {
return iterator(_M_t._M_upper_bound_tr(__x)); }
854 template<
typename _Kt>
857 -> decltype(iterator(_M_t._M_upper_bound_tr(__x)))
858 {
return iterator(_M_t._M_upper_bound_tr(__x)); }
880 {
return _M_t.equal_range(__x); }
884 {
return _M_t.equal_range(__x); }
886 #if __cplusplus > 201103L
887 template<
typename _Kt>
890 -> decltype(pair<iterator, iterator>(_M_t._M_equal_range_tr(__x)))
891 {
return pair<iterator, iterator>(_M_t._M_equal_range_tr(__x)); }
893 template<
typename _Kt>
896 -> decltype(pair<iterator, iterator>(_M_t._M_equal_range_tr(__x)))
897 {
return pair<iterator, iterator>(_M_t._M_equal_range_tr(__x)); }
901 template<
typename _K1,
typename _C1,
typename _A1>
903 operator==(
const multiset<_K1, _C1, _A1>&,
904 const multiset<_K1, _C1, _A1>&);
906 template<
typename _K1,
typename _C1,
typename _A1>
908 operator< (
const multiset<_K1, _C1, _A1>&,
909 const multiset<_K1, _C1, _A1>&);
912 #if __cpp_deduction_guides >= 201606
914 template<
typename _InputIterator,
916 less<typename iterator_traits<_InputIterator>::value_type>,
917 typename _Allocator =
918 allocator<typename iterator_traits<_InputIterator>::value_type>,
919 typename = _RequireInputIter<_InputIterator>,
920 typename = _RequireNotAllocator<_Compare>,
921 typename = _RequireAllocator<_Allocator>>
922 multiset(_InputIterator, _InputIterator,
923 _Compare = _Compare(), _Allocator = _Allocator())
924 -> multiset<typename iterator_traits<_InputIterator>::value_type,
925 _Compare, _Allocator>;
927 template<
typename _Key,
928 typename _Compare = less<_Key>,
929 typename _Allocator = allocator<_Key>,
930 typename = _RequireNotAllocator<_Compare>,
931 typename = _RequireAllocator<_Allocator>>
932 multiset(initializer_list<_Key>,
933 _Compare = _Compare(), _Allocator = _Allocator())
934 -> multiset<_Key, _Compare, _Allocator>;
936 template<
typename _InputIterator,
typename _Allocator,
937 typename = _RequireInputIter<_InputIterator>,
938 typename = _RequireAllocator<_Allocator>>
939 multiset(_InputIterator, _InputIterator, _Allocator)
940 -> multiset<typename iterator_traits<_InputIterator>::value_type,
941 less<typename iterator_traits<_InputIterator>::value_type>,
944 template<
typename _Key,
typename _Allocator,
945 typename = _RequireAllocator<_Allocator>>
946 multiset(initializer_list<_Key>, _Allocator)
947 -> multiset<_Key, less<_Key>, _Allocator>;
962 template<
typename _Key,
typename _Compare,
typename _Alloc>
966 {
return __x._M_t == __y._M_t; }
979 template<
typename _Key,
typename _Compare,
typename _Alloc>
983 {
return __x._M_t < __y._M_t; }
986 template<
typename _Key,
typename _Compare,
typename _Alloc>
990 {
return !(__x == __y); }
993 template<
typename _Key,
typename _Compare,
typename _Alloc>
997 {
return __y < __x; }
1000 template<
typename _Key,
typename _Compare,
typename _Alloc>
1004 {
return !(__y < __x); }
1007 template<
typename _Key,
typename _Compare,
typename _Alloc>
1011 {
return !(__x < __y); }
1014 template<
typename _Key,
typename _Compare,
typename _Alloc>
1018 _GLIBCXX_NOEXCEPT_IF(noexcept(__x.swap(__y)))
1021 _GLIBCXX_END_NAMESPACE_CONTAINER
1023 #if __cplusplus > 201402L
1025 template<
typename _Val,
typename _Cmp1,
typename _Alloc,
typename _Cmp2>
1027 _Rb_tree_merge_helper<_GLIBCXX_STD_C::multiset<_Val, _Cmp1, _Alloc>,
1031 friend class _GLIBCXX_STD_C::multiset<_Val, _Cmp1, _Alloc>;
1034 _S_get_tree(_GLIBCXX_STD_C::set<_Val, _Cmp2, _Alloc>& __set)
1035 {
return __set._M_t; }
1038 _S_get_tree(_GLIBCXX_STD_C::multiset<_Val, _Cmp2, _Alloc>& __set)
1039 {
return __set._M_t; }
1043 _GLIBCXX_END_NAMESPACE_VERSION