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 # ifdef __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_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_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_equal(__l.begin(), __l.end()); }
248 : _M_t(_Compare(), _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(_Compare(), _Key_alloc_type(__a))
263 { _M_t._M_insert_equal(__l.begin(), __l.end()); }
266 template<
typename _InputIterator>
267 multiset(_InputIterator __first, _InputIterator __last,
268 const allocator_type& __a)
269 : _M_t(_Compare(), _Key_alloc_type(__a))
270 { _M_t._M_insert_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(); }
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_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>
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>
607 template<
typename _Compare1>
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>
621 #if __cplusplus >= 201103L 637 _GLIBCXX_ABI_TAG_CXX11
640 {
return _M_t.erase(__position); }
653 erase(iterator __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); }
707 erase(iterator __first, iterator __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); }
757 {
return _M_t.find(__x); }
760 find(
const key_type& __x)
const 761 {
return _M_t.find(__x); }
763 #if __cplusplus > 201103L 764 template<
typename _Kt>
767 -> decltype(iterator{_M_t._M_find_tr(__x)})
768 {
return iterator{_M_t._M_find_tr(__x)}; }
770 template<
typename _Kt>
773 -> decltype(const_iterator{_M_t._M_find_tr(__x)})
774 {
return const_iterator{_M_t._M_find_tr(__x)}; }
792 {
return _M_t.lower_bound(__x); }
796 {
return _M_t.lower_bound(__x); }
798 #if __cplusplus > 201103L 799 template<
typename _Kt>
802 -> decltype(iterator(_M_t._M_lower_bound_tr(__x)))
803 {
return iterator(_M_t._M_lower_bound_tr(__x)); }
805 template<
typename _Kt>
808 -> decltype(iterator(_M_t._M_lower_bound_tr(__x)))
809 {
return iterator(_M_t._M_lower_bound_tr(__x)); }
822 {
return _M_t.upper_bound(__x); }
826 {
return _M_t.upper_bound(__x); }
828 #if __cplusplus > 201103L 829 template<
typename _Kt>
832 -> decltype(iterator(_M_t._M_upper_bound_tr(__x)))
833 {
return iterator(_M_t._M_upper_bound_tr(__x)); }
835 template<
typename _Kt>
838 -> decltype(iterator(_M_t._M_upper_bound_tr(__x)))
839 {
return iterator(_M_t._M_upper_bound_tr(__x)); }
861 {
return _M_t.equal_range(__x); }
865 {
return _M_t.equal_range(__x); }
867 #if __cplusplus > 201103L 868 template<
typename _Kt>
874 template<
typename _Kt>
882 template<
typename _K1,
typename _C1,
typename _A1>
887 template<
typename _K1,
typename _C1,
typename _A1>
889 operator< (const multiset<_K1, _C1, _A1>&,
893 #if __cpp_deduction_guides >= 201606 895 template<
typename _InputIterator,
898 typename _Allocator =
900 typename = _RequireInputIter<_InputIterator>,
901 typename = _RequireAllocator<_Allocator>>
902 multiset(_InputIterator, _InputIterator,
903 _Compare = _Compare(), _Allocator = _Allocator())
905 _Compare, _Allocator>;
907 template<
typename _Key,
910 typename = _RequireAllocator<_Allocator>>
912 _Compare = _Compare(), _Allocator = _Allocator())
915 template<
typename _InputIterator,
typename _Allocator,
916 typename = _RequireInputIter<_InputIterator>,
917 typename = _RequireAllocator<_Allocator>>
918 multiset(_InputIterator, _InputIterator, _Allocator)
923 template<
typename _Key,
typename _Allocator,
924 typename = _RequireAllocator<_Allocator>>
941 template<
typename _Key,
typename _Compare,
typename _Alloc>
945 {
return __x._M_t == __y._M_t; }
958 template<
typename _Key,
typename _Compare,
typename _Alloc>
960 operator<(const multiset<_Key, _Compare, _Alloc>& __x,
962 {
return __x._M_t < __y._M_t; }
965 template<
typename _Key,
typename _Compare,
typename _Alloc>
969 {
return !(__x == __y); }
972 template<
typename _Key,
typename _Compare,
typename _Alloc>
976 {
return __y < __x; }
979 template<
typename _Key,
typename _Compare,
typename _Alloc>
981 operator<=(const multiset<_Key, _Compare, _Alloc>& __x,
983 {
return !(__y < __x); }
986 template<
typename _Key,
typename _Compare,
typename _Alloc>
990 {
return !(__x < __y); }
993 template<
typename _Key,
typename _Compare,
typename _Alloc>
997 _GLIBCXX_NOEXCEPT_IF(noexcept(__x.swap(__y)))
1000 _GLIBCXX_END_NAMESPACE_CONTAINER
1002 #if __cplusplus > 201402L 1004 template<
typename _Val,
typename _Cmp1,
typename _Alloc,
typename _Cmp2>
1006 _Rb_tree_merge_helper<_GLIBCXX_STD_C::multiset<_Val, _Cmp1, _Alloc>,
1010 friend class _GLIBCXX_STD_C::multiset<_Val, _Cmp1, _Alloc>;
1013 _S_get_tree(_GLIBCXX_STD_C::set<_Val, _Cmp2, _Alloc>& __set)
1014 {
return __set._M_t; }
1017 _S_get_tree(_GLIBCXX_STD_C::multiset<_Val, _Cmp2, _Alloc>& __set)
1018 {
return __set._M_t; }
1023 _GLIBCXX_END_NAMESPACE_VERSION
iterator insert(const_iterator __position, const value_type &__x)
Inserts an element into the multiset.
size_type count(const key_type &__x) const
Finds the number of elements with given key.
One of the comparison functors.
iterator end() const noexcept
Struct holding two objects of arbitrary type.
iterator begin() const noexcept
The standard allocator, as per [20.4].
auto find(const _Kt &__x) -> decltype(iterator
Tries to locate an element in a set.
bool empty() const noexcept
Returns true if the set is empty.
auto lower_bound(const _Kt &__x) const -> decltype(iterator(_M_t._M_lower_bound_tr(__x)))
Finds the beginning of a subsequence matching given key.
multiset()=default
Default constructor creates no elements.
iterator find(const key_type &__x)
Tries to locate an element in a set.
_GLIBCXX_ABI_TAG_CXX11 iterator erase(const_iterator __position)
Erases an element from a multiset.
size_type erase(const key_type &__x)
Erases elements according to the provided key.
reverse_iterator rend() const noexcept
iterator upper_bound(const key_type &__x)
Finds the end of a subsequence matching given key.
reverse_iterator crend() const noexcept
value_compare value_comp() const
Returns the comparison object.
allocator_type get_allocator() const noexcept
Returns the memory allocation object.
multiset(const _Compare &__comp, const allocator_type &__a=allocator_type())
Creates a multiset with no elements.
multiset(const allocator_type &__a)
Allocator-extended default constructor.
iterator cbegin() const noexcept
auto find(const _Kt &__x) const -> decltype(const_iterator
Tries to locate an element in a set.
iterator insert(const value_type &__x)
Inserts an element into the multiset.
Uniform interface to C++98 and C++11 allocators.
void insert(_InputIterator __first, _InputIterator __last)
A template function that tries to insert a range of elements.
size_type max_size() const noexcept
Returns the maximum size of the set.
_GLIBCXX_ABI_TAG_CXX11 iterator erase(const_iterator __first, const_iterator __last)
Erases a [first,last) range of elements from a multiset.
is_nothrow_copy_constructible
key_compare key_comp() const
Returns the comparison object.
std::pair< const_iterator, const_iterator > equal_range(const key_type &__x) const
Finds a subsequence matching given key.
multiset(multiset &&__m, const allocator_type &__a) noexcept(is_nothrow_copy_constructible< _Compare >::value &&_Alloc_traits::_S_always_equal())
Allocator-extended move constructor.
size_type size() const noexcept
Returns the size of the set.
multiset(initializer_list< value_type > __l, const _Compare &__comp=_Compare(), const allocator_type &__a=allocator_type())
Builds a multiset from an initializer_list.
multiset(_InputIterator __first, _InputIterator __last)
Builds a multiset from a range.
ISO C++ entities toplevel namespace is std.
iterator cend() const noexcept
A standard container made up of elements, which can be retrieved in logarithmic time.
std::pair< iterator, iterator > equal_range(const key_type &__x)
Finds a subsequence matching given key.
multiset(_InputIterator __first, _InputIterator __last, const _Compare &__comp, const allocator_type &__a=allocator_type())
Builds a multiset from a range.
multiset & operator=(initializer_list< value_type > __l)
Multiset list assignment operator.
multiset(initializer_list< value_type > __l, const allocator_type &__a)
Allocator-extended initialier-list constructor.
const_iterator lower_bound(const key_type &__x) const
Finds the beginning of a subsequence matching given key.
auto upper_bound(const _Kt &__x) -> decltype(iterator(_M_t._M_upper_bound_tr(__x)))
Finds the end of a subsequence matching given key.
auto equal_range(const _Kt &__x) const -> decltype(pair< iterator, iterator >(_M_t._M_equal_range_tr(__x)))
Finds a subsequence matching given key.
auto count(const _Kt &__x) const -> decltype(_M_t._M_count_tr(__x))
Finds the number of elements with given key.
auto equal_range(const _Kt &__x) -> decltype(pair< iterator, iterator >(_M_t._M_equal_range_tr(__x)))
Finds a subsequence matching given key.
const_iterator upper_bound(const key_type &__x) const
Finds the end of a subsequence matching given key.
iterator lower_bound(const key_type &__x)
Finds the beginning of a subsequence matching given key.
multiset & operator=(const multiset &)=default
Multiset assignment operator.
A standard container made up of unique keys, which can be retrieved in logarithmic time...
auto upper_bound(const _Kt &__x) const -> decltype(iterator(_M_t._M_upper_bound_tr(__x)))
Finds the end of a subsequence matching given key.
auto lower_bound(const _Kt &__x) -> decltype(iterator(_M_t._M_lower_bound_tr(__x)))
Finds the beginning of a subsequence matching given key.
iterator emplace_hint(const_iterator __pos, _Args &&... __args)
Builds and inserts an element into the multiset.
iterator emplace(_Args &&... __args)
Builds and inserts an element into the multiset.
reverse_iterator rbegin() const noexcept
multiset(_InputIterator __first, _InputIterator __last, const allocator_type &__a)
Allocator-extended range constructor.
multiset(const multiset &__m, const allocator_type &__a)
Allocator-extended copy constructor.
const_iterator find(const key_type &__x) const
Tries to locate an element in a set.
void insert(initializer_list< value_type > __l)
Attempts to insert a list of elements into the multiset.
reverse_iterator crbegin() const noexcept
void swap(multiset &__x) noexcept(/*conditional */)
Swaps data with another multiset.