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
90 template <
typename _Key,
typename _Compare = std::less<_Key>,
91 typename _Alloc = std::allocator<_Key> >
95 typedef typename _Alloc::value_type _Alloc_value_type;
96 __glibcxx_class_requires(_Key, _SGIAssignableConcept)
97 __glibcxx_class_requires4(_Compare,
bool, _Key, _Key,
98 _BinaryFunctionConcept)
99 __glibcxx_class_requires2(_Key, _Alloc_value_type, _SameTypeConcept)
103 typedef _Key key_type;
104 typedef _Key value_type;
105 typedef _Compare key_compare;
106 typedef _Compare value_compare;
107 typedef _Alloc allocator_type;
112 rebind<_Key>::other _Key_alloc_type;
114 typedef _Rb_tree<key_type, value_type, _Identity<value_type>,
115 key_compare, _Key_alloc_type> _Rep_type;
122 typedef typename _Alloc_traits::pointer pointer;
123 typedef typename _Alloc_traits::const_pointer const_pointer;
124 typedef typename _Alloc_traits::reference reference;
125 typedef typename _Alloc_traits::const_reference const_reference;
129 typedef typename _Rep_type::const_iterator iterator;
130 typedef typename _Rep_type::const_iterator const_iterator;
133 typedef typename _Rep_type::size_type size_type;
134 typedef typename _Rep_type::difference_type difference_type;
141 #if __cplusplus >= 201103L
142 noexcept(is_nothrow_default_constructible<allocator_type>::value)
153 const allocator_type& __a = allocator_type())
154 : _M_t(__comp, _Key_alloc_type(__a)) { }
165 template<
typename _InputIterator>
166 multiset(_InputIterator __first, _InputIterator __last)
168 { _M_t._M_insert_equal(__first, __last); }
181 template<
typename _InputIterator>
182 multiset(_InputIterator __first, _InputIterator __last,
183 const _Compare& __comp,
184 const allocator_type& __a = allocator_type())
185 : _M_t(__comp, _Key_alloc_type(__a))
186 { _M_t._M_insert_equal(__first, __last); }
195 multiset(
const multiset& __x)
198 #if __cplusplus >= 201103L
206 multiset(multiset&& __x)
207 noexcept(is_nothrow_copy_constructible<_Compare>::value)
208 : _M_t(std::move(__x._M_t)) { }
220 multiset(initializer_list<value_type> __l,
221 const _Compare& __comp = _Compare(),
222 const allocator_type& __a = allocator_type())
223 : _M_t(__comp, _Key_alloc_type(__a))
224 { _M_t._M_insert_equal(__l.begin(), __l.end()); }
228 multiset(
const allocator_type& __a)
229 : _M_t(_Compare(), _Key_alloc_type(__a)) { }
232 multiset(
const multiset& __m,
const allocator_type& __a)
233 : _M_t(__m._M_t, _Key_alloc_type(__a)) { }
236 multiset(multiset&& __m,
const allocator_type& __a)
237 noexcept(is_nothrow_copy_constructible<_Compare>::value
238 && _Alloc_traits::_S_always_equal())
239 : _M_t(std::move(__m._M_t), _Key_alloc_type(__a)) { }
242 multiset(initializer_list<value_type> __l,
const allocator_type& __a)
243 : _M_t(_Compare(), _Key_alloc_type(__a))
244 { _M_t._M_insert_equal(__l.begin(), __l.end()); }
247 template<
typename _InputIterator>
248 multiset(_InputIterator __first, _InputIterator __last,
249 const allocator_type& __a)
250 : _M_t(_Compare(), _Key_alloc_type(__a))
251 { _M_t._M_insert_equal(__first, __last); }
268 #if __cplusplus >= 201103L
287 _M_t._M_assign_equal(__l.begin(), __l.end());
297 {
return _M_t.key_comp(); }
301 {
return _M_t.key_comp(); }
305 {
return allocator_type(_M_t.get_allocator()); }
314 {
return _M_t.begin(); }
322 end() const _GLIBCXX_NOEXCEPT
323 {
return _M_t.end(); }
332 {
return _M_t.rbegin(); }
341 {
return _M_t.rend(); }
343 #if __cplusplus >= 201103L
351 {
return _M_t.begin(); }
360 {
return _M_t.end(); }
369 {
return _M_t.rbegin(); }
378 {
return _M_t.rend(); }
384 {
return _M_t.empty(); }
389 {
return _M_t.size(); }
394 {
return _M_t.max_size(); }
409 #if __cplusplus >= 201103L
410 noexcept(_Alloc_traits::_S_nothrow_swap())
412 { _M_t.swap(__x._M_t); }
415 #if __cplusplus >= 201103L
428 template<
typename... _Args>
431 {
return _M_t._M_emplace_equal(std::forward<_Args>(__args)...); }
454 template<
typename... _Args>
458 return _M_t._M_emplace_hint_equal(__pos,
459 std::forward<_Args>(__args)...);
476 {
return _M_t._M_insert_equal(__x); }
478 #if __cplusplus >= 201103L
481 {
return _M_t._M_insert_equal(std::move(__x)); }
505 insert(const_iterator __position,
const value_type& __x)
506 {
return _M_t._M_insert_equal_(__position, __x); }
508 #if __cplusplus >= 201103L
510 insert(const_iterator __position, value_type&& __x)
511 {
return _M_t._M_insert_equal_(__position, std::move(__x)); }
522 template<
typename _InputIterator>
524 insert(_InputIterator __first, _InputIterator __last)
525 { _M_t._M_insert_equal(__first, __last); }
527 #if __cplusplus >= 201103L
537 { this->
insert(__l.begin(), __l.end()); }
540 #if __cplusplus >= 201103L
556 _GLIBCXX_ABI_TAG_CXX11
559 {
return _M_t.erase(__position); }
573 { _M_t.erase(__position); }
589 {
return _M_t.erase(__x); }
591 #if __cplusplus >= 201103L
608 _GLIBCXX_ABI_TAG_CXX11
610 erase(const_iterator __first, const_iterator __last)
611 {
return _M_t.erase(__first, __last); }
627 { _M_t.erase(__first, __last); }
650 {
return _M_t.count(__x); }
652 #if __cplusplus > 201103L
653 template<
typename _Kt>
655 count(
const _Kt& __x)
const -> decltype(_M_t._M_count_tr(__x))
656 {
return _M_t._M_count_tr(__x); }
676 {
return _M_t.find(__x); }
679 find(
const key_type& __x)
const
680 {
return _M_t.find(__x); }
682 #if __cplusplus > 201103L
683 template<
typename _Kt>
685 find(
const _Kt& __x) -> decltype(_M_t._M_find_tr(__x))
686 {
return _M_t._M_find_tr(__x); }
688 template<
typename _Kt>
690 find(
const _Kt& __x)
const -> decltype(_M_t._M_find_tr(__x))
691 {
return _M_t._M_find_tr(__x); }
709 {
return _M_t.lower_bound(__x); }
713 {
return _M_t.lower_bound(__x); }
715 #if __cplusplus > 201103L
716 template<
typename _Kt>
719 -> decltype(_M_t._M_lower_bound_tr(__x))
720 {
return _M_t._M_lower_bound_tr(__x); }
722 template<
typename _Kt>
725 -> decltype(_M_t._M_lower_bound_tr(__x))
726 {
return _M_t._M_lower_bound_tr(__x); }
739 {
return _M_t.upper_bound(__x); }
743 {
return _M_t.upper_bound(__x); }
745 #if __cplusplus > 201103L
746 template<
typename _Kt>
749 -> decltype(_M_t._M_upper_bound_tr(__x))
750 {
return _M_t._M_upper_bound_tr(__x); }
752 template<
typename _Kt>
755 -> decltype(_M_t._M_upper_bound_tr(__x))
756 {
return _M_t._M_upper_bound_tr(__x); }
778 {
return _M_t.equal_range(__x); }
782 {
return _M_t.equal_range(__x); }
784 #if __cplusplus > 201103L
785 template<
typename _Kt>
788 -> decltype(_M_t._M_equal_range_tr(__x))
789 {
return _M_t._M_equal_range_tr(__x); }
791 template<
typename _Kt>
794 -> decltype(_M_t._M_equal_range_tr(__x))
795 {
return _M_t._M_equal_range_tr(__x); }
799 template<
typename _K1,
typename _C1,
typename _A1>
801 operator==(
const multiset<_K1, _C1, _A1>&,
802 const multiset<_K1, _C1, _A1>&);
804 template<
typename _K1,
typename _C1,
typename _A1>
806 operator< (const multiset<_K1, _C1, _A1>&,
807 const multiset<_K1, _C1, _A1>&);
821 template<
typename _Key,
typename _Compare,
typename _Alloc>
825 {
return __x._M_t == __y._M_t; }
838 template<
typename _Key,
typename _Compare,
typename _Alloc>
840 operator<(const multiset<_Key, _Compare, _Alloc>& __x,
842 {
return __x._M_t < __y._M_t; }
845 template<
typename _Key,
typename _Compare,
typename _Alloc>
849 {
return !(__x == __y); }
852 template<
typename _Key,
typename _Compare,
typename _Alloc>
856 {
return __y < __x; }
859 template<
typename _Key,
typename _Compare,
typename _Alloc>
861 operator<=(const multiset<_Key, _Compare, _Alloc>& __x,
863 {
return !(__y < __x); }
866 template<
typename _Key,
typename _Compare,
typename _Alloc>
870 {
return !(__x < __y); }
873 template<
typename _Key,
typename _Compare,
typename _Alloc>
879 _GLIBCXX_END_NAMESPACE_CONTAINER
void swap(basic_filebuf< _CharT, _Traits > &__x, basic_filebuf< _CharT, _Traits > &__y)
Swap specialization for filebufs.
size_type erase(const key_type &__x)
Erases elements according to the provided key.
const_iterator find(const key_type &__x) const
Tries to locate an element in a set.
allocator_type get_allocator() const noexcept
Returns the memory allocation object.
Uniform interface to C++98 and C++0x allocators.
bool empty() const noexcept
Returns true if the set is empty.
iterator emplace_hint(const_iterator __pos, _Args &&...__args)
Builds and inserts an element into the multiset.
iterator begin() const noexcept
key_compare key_comp() const
Returns the comparison object.
size_type max_size() const noexcept
Returns the maximum size of the set.
iterator end() const noexcept
iterator upper_bound(const key_type &__x)
Finds the end of a subsequence matching given key.
multiset & operator=(initializer_list< value_type > __l)
Multiset list assignment operator.
iterator lower_bound(const key_type &__x)
Finds the beginning of a subsequence matching given key.
const_iterator upper_bound(const key_type &__x) const
Finds the end of a subsequence matching given key.
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.
reverse_iterator rbegin() const noexcept
reverse_iterator crend() const noexcept
iterator cend() const noexcept
size_type size() const noexcept
Returns the size of the set.
reverse_iterator rend() const noexcept
size_type count(const key_type &__x) const
Finds the number of elements with given key.
_GLIBCXX_ABI_TAG_CXX11 iterator erase(const_iterator __first, const_iterator __last)
Erases a [first,last) range of elements from a multiset.
const_iterator lower_bound(const key_type &__x) const
Finds the beginning of a subsequence matching given key.
iterator emplace(_Args &&...__args)
Builds and inserts an element into the multiset.
std::pair< iterator, iterator > equal_range(const key_type &__x)
Finds a subsequence matching given key.
reverse_iterator crbegin() const noexcept
void insert(initializer_list< value_type > __l)
Attempts to insert a list of elements into the multiset.
A standard container made up of elements, which can be retrieved in logarithmic time.
iterator insert(const value_type &__x)
Inserts an element into the multiset.
std::pair< const_iterator, const_iterator > equal_range(const key_type &__x) const
Finds a subsequence matching given key.
value_compare value_comp() const
Returns the comparison object.
iterator insert(const_iterator __position, const value_type &__x)
Inserts an element into the multiset.
iterator cbegin() const noexcept
void insert(_InputIterator __first, _InputIterator __last)
A template function that tries to insert a range of elements.
Struct holding two objects of arbitrary type.