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_CONTAINER
68 template<
typename _Key,
typename _Compare,
typename _Alloc>
93 template <
typename _Key,
typename _Compare = std::less<_Key>,
94 typename _Alloc = std::allocator<_Key> >
97 #ifdef _GLIBCXX_CONCEPT_CHECKS
99 typedef typename _Alloc::value_type _Alloc_value_type;
100 # if __cplusplus < 201103L
101 __glibcxx_class_requires(_Key, _SGIAssignableConcept)
103 __glibcxx_class_requires4(_Compare,
bool, _Key, _Key,
104 _BinaryFunctionConcept)
105 __glibcxx_class_requires2(_Key, _Alloc_value_type, _SameTypeConcept)
110 typedef _Key key_type;
111 typedef _Key value_type;
112 typedef _Compare key_compare;
113 typedef _Compare value_compare;
114 typedef _Alloc allocator_type;
119 rebind<_Key>::other _Key_alloc_type;
121 typedef _Rb_tree<key_type, value_type, _Identity<value_type>,
122 key_compare, _Key_alloc_type> _Rep_type;
129 typedef typename _Alloc_traits::pointer pointer;
130 typedef typename _Alloc_traits::const_pointer const_pointer;
131 typedef typename _Alloc_traits::reference reference;
132 typedef typename _Alloc_traits::const_reference const_reference;
136 typedef typename _Rep_type::const_iterator iterator;
137 typedef typename _Rep_type::const_iterator const_iterator;
140 typedef typename _Rep_type::size_type size_type;
141 typedef typename _Rep_type::difference_type difference_type;
143 #if __cplusplus > 201402L
144 using node_type =
typename _Rep_type::node_type;
151 #if __cplusplus < 201103L
164 const allocator_type& __a = allocator_type())
165 : _M_t(__comp, _Key_alloc_type(__a)) { }
176 template<
typename _InputIterator>
177 multiset(_InputIterator __first, _InputIterator __last)
179 { _M_t._M_insert_equal(__first, __last); }
192 template<
typename _InputIterator>
193 multiset(_InputIterator __first, _InputIterator __last,
194 const _Compare& __comp,
195 const allocator_type& __a = allocator_type())
196 : _M_t(__comp, _Key_alloc_type(__a))
197 { _M_t._M_insert_equal(__first, __last); }
204 #if __cplusplus < 201103L
230 const _Compare& __comp = _Compare(),
231 const allocator_type& __a = allocator_type())
232 : _M_t(__comp, _Key_alloc_type(__a))
233 { _M_t._M_insert_equal(__l.begin(), __l.end()); }
238 : _M_t(_Compare(), _Key_alloc_type(__a)) { }
242 : _M_t(__m._M_t, _Key_alloc_type(__a)) { }
246 noexcept(is_nothrow_copy_constructible<_Compare>::value
247 && _Alloc_traits::_S_always_equal())
248 : _M_t(
std::move(__m._M_t), _Key_alloc_type(__a)) { }
252 : _M_t(_Compare(), _Key_alloc_type(__a))
253 { _M_t._M_insert_equal(__l.begin(), __l.end()); }
256 template<
typename _InputIterator>
257 multiset(_InputIterator __first, _InputIterator __last,
258 const allocator_type& __a)
259 : _M_t(_Compare(), _Key_alloc_type(__a))
260 { _M_t._M_insert_equal(__first, __last); }
275 #if __cplusplus < 201103L
304 _M_t._M_assign_equal(__l.begin(), __l.end());
314 {
return _M_t.key_comp(); }
318 {
return _M_t.key_comp(); }
322 {
return allocator_type(_M_t.get_allocator()); }
331 {
return _M_t.begin(); }
339 end() const _GLIBCXX_NOEXCEPT
340 {
return _M_t.end(); }
349 {
return _M_t.rbegin(); }
358 {
return _M_t.rend(); }
360 #if __cplusplus >= 201103L
368 {
return _M_t.begin(); }
377 {
return _M_t.end(); }
386 {
return _M_t.rbegin(); }
395 {
return _M_t.rend(); }
401 {
return _M_t.empty(); }
406 {
return _M_t.size(); }
411 {
return _M_t.max_size(); }
428 _GLIBCXX_NOEXCEPT_IF(__is_nothrow_swappable<_Compare>::value)
429 { _M_t.swap(__x._M_t); }
432 #if __cplusplus >= 201103L
445 template<
typename... _Args>
448 {
return _M_t._M_emplace_equal(std::forward<_Args>(__args)...); }
471 template<
typename... _Args>
475 return _M_t._M_emplace_hint_equal(__pos,
476 std::forward<_Args>(__args)...);
493 {
return _M_t._M_insert_equal(__x); }
495 #if __cplusplus >= 201103L
498 {
return _M_t._M_insert_equal(std::move(__x)); }
522 insert(const_iterator __position,
const value_type& __x)
523 {
return _M_t._M_insert_equal_(__position, __x); }
525 #if __cplusplus >= 201103L
527 insert(const_iterator __position, value_type&& __x)
528 {
return _M_t._M_insert_equal_(__position, std::move(__x)); }
539 template<
typename _InputIterator>
541 insert(_InputIterator __first, _InputIterator __last)
542 { _M_t._M_insert_equal(__first, __last); }
544 #if __cplusplus >= 201103L
554 { this->
insert(__l.begin(), __l.end()); }
557 #if __cplusplus > 201402L
560 extract(const_iterator __pos)
562 __glibcxx_assert(__pos !=
end());
563 return _M_t.extract(__pos);
568 extract(
const key_type& __x)
569 {
return _M_t.extract(__x); }
574 {
return _M_t._M_reinsert_node_equal(std::move(__nh)); }
578 insert(const_iterator __hint, node_type&& __nh)
579 {
return _M_t._M_reinsert_node_hint_equal(__hint, std::move(__nh)); }
581 template<
typename,
typename>
582 friend class _Rb_tree_merge_helper;
584 template<
typename _Compare1>
586 merge(multiset<_Key, _Compare1, _Alloc>& __source)
588 using _Merge_helper = _Rb_tree_merge_helper<multiset, _Compare1>;
589 _M_t._M_merge_equal(_Merge_helper::_S_get_tree(__source));
592 template<
typename _Compare1>
594 merge(multiset<_Key, _Compare1, _Alloc>&& __source)
597 template<
typename _Compare1>
599 merge(set<_Key, _Compare1, _Alloc>& __source)
601 using _Merge_helper = _Rb_tree_merge_helper<multiset, _Compare1>;
602 _M_t._M_merge_equal(_Merge_helper::_S_get_tree(__source));
605 template<
typename _Compare1>
607 merge(set<_Key, _Compare1, _Alloc>&& __source)
611 #if __cplusplus >= 201103L
627 _GLIBCXX_ABI_TAG_CXX11
630 {
return _M_t.erase(__position); }
644 { _M_t.erase(__position); }
660 {
return _M_t.erase(__x); }
662 #if __cplusplus >= 201103L
679 _GLIBCXX_ABI_TAG_CXX11
681 erase(const_iterator __first, const_iterator __last)
682 {
return _M_t.erase(__first, __last); }
698 { _M_t.erase(__first, __last); }
721 {
return _M_t.count(__x); }
723 #if __cplusplus > 201103L
724 template<
typename _Kt>
726 count(
const _Kt& __x)
const -> decltype(_M_t._M_count_tr(__x))
727 {
return _M_t._M_count_tr(__x); }
747 {
return _M_t.find(__x); }
750 find(
const key_type& __x)
const
751 {
return _M_t.find(__x); }
753 #if __cplusplus > 201103L
754 template<
typename _Kt>
757 -> decltype(iterator{_M_t._M_find_tr(__x)})
758 {
return iterator{_M_t._M_find_tr(__x)}; }
760 template<
typename _Kt>
762 find(
const _Kt& __x)
const
763 -> decltype(const_iterator{_M_t._M_find_tr(__x)})
764 {
return const_iterator{_M_t._M_find_tr(__x)}; }
782 {
return _M_t.lower_bound(__x); }
786 {
return _M_t.lower_bound(__x); }
788 #if __cplusplus > 201103L
789 template<
typename _Kt>
792 -> decltype(iterator(_M_t._M_lower_bound_tr(__x)))
793 {
return iterator(_M_t._M_lower_bound_tr(__x)); }
795 template<
typename _Kt>
798 -> decltype(iterator(_M_t._M_lower_bound_tr(__x)))
799 {
return iterator(_M_t._M_lower_bound_tr(__x)); }
812 {
return _M_t.upper_bound(__x); }
816 {
return _M_t.upper_bound(__x); }
818 #if __cplusplus > 201103L
819 template<
typename _Kt>
822 -> decltype(iterator(_M_t._M_upper_bound_tr(__x)))
823 {
return iterator(_M_t._M_upper_bound_tr(__x)); }
825 template<
typename _Kt>
828 -> decltype(iterator(_M_t._M_upper_bound_tr(__x)))
829 {
return iterator(_M_t._M_upper_bound_tr(__x)); }
851 {
return _M_t.equal_range(__x); }
855 {
return _M_t.equal_range(__x); }
857 #if __cplusplus > 201103L
858 template<
typename _Kt>
861 -> decltype(pair<iterator, iterator>(_M_t._M_equal_range_tr(__x)))
862 {
return pair<iterator, iterator>(_M_t._M_equal_range_tr(__x)); }
864 template<
typename _Kt>
867 -> decltype(pair<iterator, iterator>(_M_t._M_equal_range_tr(__x)))
868 {
return pair<iterator, iterator>(_M_t._M_equal_range_tr(__x)); }
872 template<
typename _K1,
typename _C1,
typename _A1>
875 const multiset<_K1, _C1, _A1>&);
877 template<
typename _K1,
typename _C1,
typename _A1>
879 operator< (
const multiset<_K1, _C1, _A1>&,
880 const multiset<_K1, _C1, _A1>&);
894 template<
typename _Key,
typename _Compare,
typename _Alloc>
898 {
return __x._M_t == __y._M_t; }
911 template<
typename _Key,
typename _Compare,
typename _Alloc>
915 {
return __x._M_t < __y._M_t; }
918 template<
typename _Key,
typename _Compare,
typename _Alloc>
922 {
return !(__x == __y); }
925 template<
typename _Key,
typename _Compare,
typename _Alloc>
929 {
return __y < __x; }
932 template<
typename _Key,
typename _Compare,
typename _Alloc>
936 {
return !(__y < __x); }
939 template<
typename _Key,
typename _Compare,
typename _Alloc>
943 {
return !(__x < __y); }
946 template<
typename _Key,
typename _Compare,
typename _Alloc>
950 _GLIBCXX_NOEXCEPT_IF(noexcept(__x.swap(__y)))
953 _GLIBCXX_END_NAMESPACE_CONTAINER
955 #if __cplusplus > 201402L
956 _GLIBCXX_BEGIN_NAMESPACE_VERSION
958 template<
typename _Val,
typename _Cmp1,
typename _Alloc,
typename _Cmp2>
960 _Rb_tree_merge_helper<_GLIBCXX_STD_C::multiset<_Val, _Cmp1, _Alloc>,
964 friend class _GLIBCXX_STD_C::multiset<_Val, _Cmp1, _Alloc>;
967 _S_get_tree(_GLIBCXX_STD_C::set<_Val, _Cmp2, _Alloc>& __set)
968 {
return __set._M_t; }
971 _S_get_tree(_GLIBCXX_STD_C::multiset<_Val, _Cmp2, _Alloc>& __set)
972 {
return __set._M_t; }
974 _GLIBCXX_END_NAMESPACE_VERSION