29 #ifndef _GLIBCXX_DEBUG_MULTISET_H
30 #define _GLIBCXX_DEBUG_MULTISET_H 1
37 namespace std _GLIBCXX_VISIBILITY(default)
42 template<
typename _Key,
typename _Compare = std::less<_Key>,
43 typename _Allocator = std::allocator<_Key> >
46 multiset<_Key, _Compare, _Allocator>, _Allocator,
47 __gnu_debug::_Safe_node_sequence>,
48 public _GLIBCXX_STD_C::multiset<_Key, _Compare, _Allocator>
50 typedef _GLIBCXX_STD_C::multiset<_Key, _Compare, _Allocator>
_Base;
58 template<
typename _ItT,
typename _SeqT,
typename _CatT>
59 friend class ::__gnu_debug::_Safe_iterator;
66 _Base_ref(
const _Base& __r) : _M_ref(__r) { }
73 typedef _Key key_type;
74 typedef _Key value_type;
75 typedef _Compare key_compare;
76 typedef _Compare value_compare;
77 typedef _Allocator allocator_type;
78 typedef typename _Base::reference reference;
79 typedef typename _Base::const_reference const_reference;
86 typedef typename _Base::size_type size_type;
87 typedef typename _Base::difference_type difference_type;
88 typedef typename _Base::pointer pointer;
89 typedef typename _Base::const_pointer const_pointer;
95 #if __cplusplus < 201103L
108 const _Compare& __comp = _Compare(),
109 const allocator_type& __a = allocator_type())
110 :
_Base(__l, __comp, __a) { }
117 const __type_identity_t<allocator_type>& __a)
118 :
_Base(__m, __a) { }
129 template<
typename _InputIterator>
130 multiset(_InputIterator __first, _InputIterator __last,
131 const allocator_type& __a)
133 __glibcxx_check_valid_constructor_range(__first, __last)),
136 #if __glibcxx_containers_ranges
141 template<std::__detail::__container_compatible_range<value_type> _Rg>
142 multiset(std::from_range_t __t, _Rg&& __rg,
144 const allocator_type& __a = allocator_type())
145 :
_Base(__t, std::forward<_Rg>(__rg), __c, __a)
148 template<std::__detail::__container_compatible_range<value_type> _Rg>
149 multiset(std::from_range_t __t, _Rg&& __rg,
150 const allocator_type& __a = allocator_type())
151 :
_Base(__t, std::forward<_Rg>(__rg), __a)
158 explicit multiset(
const _Compare& __comp,
159 const _Allocator& __a = _Allocator())
160 :
_Base(__comp, __a) { }
162 template<
typename _InputIterator>
163 multiset(_InputIterator __first, _InputIterator __last,
164 const _Compare& __comp = _Compare(),
165 const _Allocator& __a = _Allocator())
167 __glibcxx_check_valid_constructor_range(__first, __last)),
172 :
_Base(__x._M_ref) { }
174 #if __cplusplus >= 201103L
176 operator=(
const multiset&) =
default;
184 _Base::operator=(__l);
185 this->_M_invalidate_all();
190 using _Base::get_allocator;
194 begin() _GLIBCXX_NOEXCEPT
195 {
return iterator(_Base::begin(),
this); }
198 begin()
const _GLIBCXX_NOEXCEPT
202 end() _GLIBCXX_NOEXCEPT
203 {
return iterator(_Base::end(),
this); }
206 end()
const _GLIBCXX_NOEXCEPT
210 rbegin() _GLIBCXX_NOEXCEPT
214 rbegin()
const _GLIBCXX_NOEXCEPT
218 rend() _GLIBCXX_NOEXCEPT
222 rend()
const _GLIBCXX_NOEXCEPT
225 #if __cplusplus >= 201103L
227 cbegin()
const noexcept
231 cend()
const noexcept
235 crbegin()
const noexcept
239 crend()
const noexcept
246 using _Base::max_size;
249 #if __cplusplus >= 201103L
250 template<
typename... _Args>
252 emplace(_Args&&... __args)
253 {
return { _Base::emplace(std::forward<_Args>(__args)...),
this }; }
255 template<
typename... _Args>
262 _Base::emplace_hint(__pos.
base(), std::forward<_Args>(__args)...),
269 insert(
const value_type& __x)
270 {
return iterator(_Base::insert(__x),
this); }
272 #if __cplusplus >= 201103L
274 insert(value_type&& __x)
275 {
return { _Base::insert(
std::move(__x)),
this }; }
282 return iterator(_Base::insert(__position.
base(), __x),
this);
285 #if __cplusplus >= 201103L
290 return { _Base::insert(__position.
base(),
std::move(__x)),
this };
294 template<
typename _InputIterator>
296 insert(_InputIterator __first, _InputIterator __last)
299 __glibcxx_check_valid_range2(__first, __last, __dist);
301 if (__dist.
second >= __gnu_debug::__dp_sign)
302 _Base::insert(__gnu_debug::__unsafe(__first),
303 __gnu_debug::__unsafe(__last));
305 _Base::insert(__first, __last);
308 #if __cplusplus >= 201103L
311 { _Base::insert(__l); }
314 #if __cplusplus > 201402L
315 using node_type =
typename _Base::node_type;
322 return _Base::extract(__position.
base());
326 extract(
const key_type& __key)
328 const auto __position = find(__key);
329 if (__position != end())
330 return extract(__position);
335 insert(node_type&& __nh)
336 {
return { _Base::insert(
std::move(__nh)),
this }; }
342 return { _Base::insert(__hint.
base(),
std::move(__nh)),
this };
348 #if __cplusplus >= 201103L
349 _GLIBCXX_ABI_TAG_CXX11
354 return { erase(__position.
base()),
this };
360 __glibcxx_check_erase2(__position);
362 return _Base::erase(__position);
370 _Base::erase(__position.
base());
375 erase(
const key_type& __x)
378 _Base::equal_range(__x);
379 size_type __count = 0;
381 while (__victim != __victims.
second)
384 _Base::erase(__victim++);
390 #if __cplusplus >= 201103L
391 _GLIBCXX_ABI_TAG_CXX11
399 __victim != __last.
base(); ++__victim)
401 _GLIBCXX_DEBUG_VERIFY(__victim != _Base::cend(),
402 _M_message(__gnu_debug::__msg_valid_range)
403 ._M_iterator(__first,
"first")
404 ._M_iterator(__last,
"last"));
408 return { _Base::erase(__first.base(), __last.
base()),
this };
418 __victim != __last.
base(); ++__victim)
420 _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(),
421 _M_message(__gnu_debug::__msg_valid_range)
422 ._M_iterator(__first,
"first")
423 ._M_iterator(__last,
"last"));
426 _Base::erase(__first.base(), __last.
base());
432 _GLIBCXX_NOEXCEPT_IF( noexcept(declval<_Base&>().swap(__x)) )
439 clear() _GLIBCXX_NOEXCEPT
441 this->_M_invalidate_all();
446 using _Base::key_comp;
447 using _Base::value_comp;
451 find(
const key_type& __x)
452 {
return iterator(_Base::find(__x),
this); }
457 find(
const key_type& __x)
const
460 #if __cplusplus > 201103L
461 template<
typename _Kt,
463 typename __has_is_transparent<_Compare, _Kt>::type>
466 {
return { _Base::find(__x),
this }; }
468 template<
typename _Kt,
470 typename __has_is_transparent<_Compare, _Kt>::type>
472 find(
const _Kt& __x)
const
473 {
return { _Base::find(__x),
this }; }
479 lower_bound(
const key_type& __x)
480 {
return iterator(_Base::lower_bound(__x),
this); }
485 lower_bound(
const key_type& __x)
const
488 #if __cplusplus > 201103L
489 template<
typename _Kt,
491 typename __has_is_transparent<_Compare, _Kt>::type>
493 lower_bound(
const _Kt& __x)
494 {
return { _Base::lower_bound(__x),
this }; }
496 template<
typename _Kt,
498 typename __has_is_transparent<_Compare, _Kt>::type>
500 lower_bound(
const _Kt& __x)
const
501 {
return { _Base::lower_bound(__x),
this }; }
505 upper_bound(
const key_type& __x)
506 {
return iterator(_Base::upper_bound(__x),
this); }
511 upper_bound(
const key_type& __x)
const
514 #if __cplusplus > 201103L
515 template<
typename _Kt,
517 typename __has_is_transparent<_Compare, _Kt>::type>
519 upper_bound(
const _Kt& __x)
520 {
return { _Base::upper_bound(__x),
this }; }
522 template<
typename _Kt,
524 typename __has_is_transparent<_Compare, _Kt>::type>
526 upper_bound(
const _Kt& __x)
const
527 {
return { _Base::upper_bound(__x),
this }; }
531 equal_range(
const key_type& __x)
534 _Base::equal_range(__x);
542 equal_range(
const key_type& __x)
const
545 _Base::equal_range(__x);
550 #if __cplusplus > 201103L
551 template<
typename _Kt,
553 typename __has_is_transparent<_Compare, _Kt>::type>
555 equal_range(
const _Kt& __x)
557 auto __res = _Base::equal_range(__x);
558 return { { __res.first,
this }, { __res.second,
this } };
561 template<
typename _Kt,
563 typename __has_is_transparent<_Compare, _Kt>::type>
565 equal_range(
const _Kt& __x)
const
567 auto __res = _Base::equal_range(__x);
568 return { { __res.first,
this }, { __res.second,
this } };
573 _M_base() _GLIBCXX_NOEXCEPT {
return *
this; }
576 _M_base()
const _GLIBCXX_NOEXCEPT {
return *
this; }
579 #if __cpp_deduction_guides >= 201606
581 template<
typename _InputIterator,
584 typename _Allocator =
586 typename = _RequireInputIter<_InputIterator>,
587 typename = _RequireNotAllocator<_Compare>,
588 typename = _RequireAllocator<_Allocator>>
589 multiset(_InputIterator, _InputIterator,
590 _Compare = _Compare(), _Allocator = _Allocator())
592 _Compare, _Allocator>;
594 template<
typename _Key,
597 typename = _RequireNotAllocator<_Compare>,
598 typename = _RequireAllocator<_Allocator>>
600 _Compare = _Compare(), _Allocator = _Allocator())
603 template<
typename _InputIterator,
typename _Allocator,
604 typename = _RequireInputIter<_InputIterator>,
605 typename = _RequireAllocator<_Allocator>>
606 multiset(_InputIterator, _InputIterator, _Allocator)
611 template<
typename _Key,
typename _Allocator,
612 typename = _RequireAllocator<_Allocator>>
616 #if __glibcxx_containers_ranges
617 template<ranges::input_range _Rg,
620 multiset(from_range_t, _Rg&&, _Compare = _Compare(), _Alloc = _Alloc())
623 template<ranges::input_range _Rg, __allocator_like _Alloc>
624 multiset(from_range_t, _Rg&&, _Alloc)
629 template<
typename _Key,
typename _Compare,
typename _Allocator>
633 {
return __lhs._M_base() == __rhs._M_base(); }
635 #if __cpp_lib_three_way_comparison
636 template<
typename _Key,
typename _Compare,
typename _Alloc>
637 inline __detail::__synth3way_t<_Key>
640 {
return __lhs._M_base() <=> __rhs._M_base(); }
642 template<
typename _Key,
typename _Compare,
typename _Allocator>
644 operator!=(
const multiset<_Key, _Compare, _Allocator>& __lhs,
645 const multiset<_Key, _Compare, _Allocator>& __rhs)
646 {
return __lhs._M_base() != __rhs._M_base(); }
648 template<
typename _Key,
typename _Compare,
typename _Allocator>
650 operator<(
const multiset<_Key, _Compare, _Allocator>& __lhs,
651 const multiset<_Key, _Compare, _Allocator>& __rhs)
652 {
return __lhs._M_base() < __rhs._M_base(); }
654 template<
typename _Key,
typename _Compare,
typename _Allocator>
656 operator<=(
const multiset<_Key, _Compare, _Allocator>& __lhs,
657 const multiset<_Key, _Compare, _Allocator>& __rhs)
658 {
return __lhs._M_base() <= __rhs._M_base(); }
660 template<
typename _Key,
typename _Compare,
typename _Allocator>
662 operator>=(
const multiset<_Key, _Compare, _Allocator>& __lhs,
663 const multiset<_Key, _Compare, _Allocator>& __rhs)
664 {
return __lhs._M_base() >= __rhs._M_base(); }
666 template<
typename _Key,
typename _Compare,
typename _Allocator>
668 operator>(
const multiset<_Key, _Compare, _Allocator>& __lhs,
669 const multiset<_Key, _Compare, _Allocator>& __rhs)
670 {
return __lhs._M_base() > __rhs._M_base(); }
673 template<
typename _Key,
typename _Compare,
typename _Allocator>
675 swap(multiset<_Key, _Compare, _Allocator>& __x,
676 multiset<_Key, _Compare, _Allocator>& __y)
677 _GLIBCXX_NOEXCEPT_IF(noexcept(__x.swap(__y)))
678 {
return __x.swap(__y); }
#define __glibcxx_check_insert(_Position)
#define __glibcxx_check_erase_range(_First, _Last)
#define __glibcxx_check_erase(_Position)
constexpr bool operator<=(const duration< _Rep1, _Period1 > &__lhs, const duration< _Rep2, _Period2 > &__rhs)
constexpr bool operator>=(const duration< _Rep1, _Period1 > &__lhs, const duration< _Rep2, _Period2 > &__rhs)
constexpr bool operator<(const duration< _Rep1, _Period1 > &__lhs, const duration< _Rep2, _Period2 > &__rhs)
constexpr bool operator>(const duration< _Rep1, _Period1 > &__lhs, const duration< _Rep2, _Period2 > &__rhs)
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
ISO C++ entities toplevel namespace is std.
constexpr auto empty(const _Container &__cont) noexcept(noexcept(__cont.empty())) -> decltype(__cont.empty())
Return whether a container is empty.
constexpr auto size(const _Container &__cont) noexcept(noexcept(__cont.size())) -> decltype(__cont.size())
Return the size of a container.
constexpr _Iterator __base(_Iterator __it)
The standard allocator, as per C++03 [20.4.1].
constexpr _Iterator & base() noexcept
Return the underlying iterator.
One of the comparison functors.
Struct holding two objects of arbitrary type.
_T1 first
The first member.
_T2 second
The second member.
A standard container made up of elements, which can be retrieved in logarithmic time.
void _M_invalidate_if(_Predicate __pred)
Class std::multiset with safety/checking/debug instrumentation.
Safe class dealing with some allocator dependent operations.
Like _Safe_sequence but with a special _M_invalidate_all implementation not invalidating past-the-end...