29 #ifndef _GLIBCXX_DEBUG_SET_H
30 #define _GLIBCXX_DEBUG_SET_H 1
37 namespace std _GLIBCXX_VISIBILITY(default)
42 template<
typename _Key,
typename _Compare = std::less<_Key>,
43 typename _Allocator = std::allocator<_Key> >
46 set<_Key, _Compare, _Allocator>, _Allocator,
47 __gnu_debug::_Safe_node_sequence>,
48 public _GLIBCXX_STD_C::set<_Key,_Compare,_Allocator>
50 typedef _GLIBCXX_STD_C::set<_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
104 set(
const set&) =
default;
108 const _Compare& __comp = _Compare(),
109 const allocator_type& __a = allocator_type())
110 :
_Base(__l, __comp, __a) { }
113 set(
const allocator_type& __a)
116 set(
const set& __x,
const __type_identity_t<allocator_type>& __a)
117 :
_Base(__x, __a) { }
119 set(
set&& __x,
const __type_identity_t<allocator_type>& __a)
125 :
_Base(__l, __a) { }
127 template<
typename _InputIterator>
128 set(_InputIterator __first, _InputIterator __last,
129 const allocator_type& __a)
131 __glibcxx_check_valid_constructor_range(__first, __last)),
134 #if __glibcxx_containers_ranges
139 template<std::__detail::__container_compatible_range<_Key> _Rg>
140 set(std::from_range_t __t, _Rg&& __rg,
142 const allocator_type& __a = allocator_type())
143 :
_Base(__t, std::forward<_Rg>(__rg), __c, __a)
146 template<std::__detail::__container_compatible_range<_Key> _Rg>
147 set(std::from_range_t __t, _Rg&& __rg,
148 const allocator_type& __a = allocator_type())
149 :
_Base(__t, std::forward<_Rg>(__rg), __a)
156 explicit set(
const _Compare& __comp,
157 const _Allocator& __a = _Allocator())
158 :
_Base(__comp, __a) { }
160 template<
typename _InputIterator>
161 set(_InputIterator __first, _InputIterator __last,
162 const _Compare& __comp = _Compare(),
163 const _Allocator& __a = _Allocator())
165 __glibcxx_check_valid_constructor_range(__first, __last)),
170 :
_Base(__x._M_ref) { }
172 #if __cplusplus >= 201103L
174 operator=(
const set&) =
default;
177 operator=(
set&&) =
default;
182 _Base::operator=(__l);
183 this->_M_invalidate_all();
188 using _Base::get_allocator;
192 begin() _GLIBCXX_NOEXCEPT
193 {
return iterator(_Base::begin(),
this); }
196 begin()
const _GLIBCXX_NOEXCEPT
200 end() _GLIBCXX_NOEXCEPT
201 {
return iterator(_Base::end(),
this); }
204 end()
const _GLIBCXX_NOEXCEPT
208 rbegin() _GLIBCXX_NOEXCEPT
212 rbegin()
const _GLIBCXX_NOEXCEPT
216 rend() _GLIBCXX_NOEXCEPT
220 rend()
const _GLIBCXX_NOEXCEPT
223 #if __cplusplus >= 201103L
225 cbegin()
const noexcept
229 cend()
const noexcept
233 crbegin()
const noexcept
237 crend()
const noexcept
244 using _Base::max_size;
247 #if __cplusplus >= 201103L
248 template<
typename... _Args>
250 emplace(_Args&&... __args)
252 auto __res = _Base::emplace(std::forward<_Args>(__args)...);
253 return { { __res.first,
this }, __res.second };
256 template<
typename... _Args>
263 _Base::emplace_hint(__pos.
base(), std::forward<_Args>(__args)...),
270 insert(
const value_type& __x)
277 #if __cplusplus >= 201103L
279 insert(value_type&& __x)
281 auto __res = _Base::insert(
std::move(__x));
282 return { { __res.first,
this }, __res.second };
290 return iterator(_Base::insert(__position.
base(), __x),
this);
293 #if __cplusplus >= 201103L
298 return { _Base::insert(__position.
base(),
std::move(__x)),
this };
302 template <
typename _InputIterator>
304 insert(_InputIterator __first, _InputIterator __last)
307 __glibcxx_check_valid_range2(__first, __last, __dist);
309 if (__dist.
second >= __gnu_debug::__dp_sign)
310 _Base::insert(__gnu_debug::__unsafe(__first),
311 __gnu_debug::__unsafe(__last));
313 _Base::insert(__first, __last);
316 #if __cplusplus >= 201103L
319 { _Base::insert(__l); }
322 #if __cplusplus > 201402L
323 using node_type =
typename _Base::node_type;
331 return _Base::extract(__position.
base());
335 extract(
const key_type& __key)
337 const auto __position = find(__key);
338 if (__position != end())
339 return extract(__position);
344 insert(node_type&& __nh)
346 auto __ret = _Base::insert(
std::move(__nh));
348 return { __pos, __ret.inserted,
std::move(__ret.node) };
355 return { _Base::insert(__hint.
base(),
std::move(__nh)),
this };
361 #if __cplusplus >= 201103L
362 _GLIBCXX_ABI_TAG_CXX11
367 return { erase(__position.
base()),
this };
373 __glibcxx_check_erase2(__position);
375 return _Base::erase(__position);
383 _Base::erase(__position.
base());
388 erase(
const key_type& __x)
391 if (__victim == _Base::end())
396 _Base::erase(__victim);
401 #if __cplusplus >= 201103L
402 _GLIBCXX_ABI_TAG_CXX11
410 __victim != __last.
base(); ++__victim)
412 _GLIBCXX_DEBUG_VERIFY(__victim != _Base::cend(),
413 _M_message(__gnu_debug::__msg_valid_range)
414 ._M_iterator(__first,
"first")
415 ._M_iterator(__last,
"last"));
419 return { _Base::erase(__first.base(), __last.
base()),
this };
429 __victim != __last.
base(); ++__victim)
431 _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(),
432 _M_message(__gnu_debug::__msg_valid_range)
433 ._M_iterator(__first,
"first")
434 ._M_iterator(__last,
"last"));
437 _Base::erase(__first.base(), __last.
base());
443 _GLIBCXX_NOEXCEPT_IF( noexcept(declval<_Base&>().swap(__x)) )
450 clear() _GLIBCXX_NOEXCEPT
452 this->_M_invalidate_all();
457 using _Base::key_comp;
458 using _Base::value_comp;
462 find(
const key_type& __x)
463 {
return iterator(_Base::find(__x),
this); }
468 find(
const key_type& __x)
const
471 #if __cplusplus > 201103L
472 template<
typename _Kt,
474 typename __has_is_transparent<_Compare, _Kt>::type>
477 {
return { _Base::find(__x),
this }; }
479 template<
typename _Kt,
481 typename __has_is_transparent<_Compare, _Kt>::type>
483 find(
const _Kt& __x)
const
484 {
return { _Base::find(__x),
this }; }
490 lower_bound(
const key_type& __x)
491 {
return iterator(_Base::lower_bound(__x),
this); }
496 lower_bound(
const key_type& __x)
const
499 #if __cplusplus > 201103L
500 template<
typename _Kt,
502 typename __has_is_transparent<_Compare, _Kt>::type>
504 lower_bound(
const _Kt& __x)
505 {
return { _Base::lower_bound(__x),
this }; }
507 template<
typename _Kt,
509 typename __has_is_transparent<_Compare, _Kt>::type>
511 lower_bound(
const _Kt& __x)
const
512 {
return { _Base::lower_bound(__x),
this }; }
516 upper_bound(
const key_type& __x)
517 {
return iterator(_Base::upper_bound(__x),
this); }
522 upper_bound(
const key_type& __x)
const
525 #if __cplusplus > 201103L
526 template<
typename _Kt,
528 typename __has_is_transparent<_Compare, _Kt>::type>
530 upper_bound(
const _Kt& __x)
531 {
return { _Base::upper_bound(__x),
this }; }
533 template<
typename _Kt,
535 typename __has_is_transparent<_Compare, _Kt>::type>
537 upper_bound(
const _Kt& __x)
const
538 {
return { _Base::upper_bound(__x),
this }; }
542 equal_range(
const key_type& __x)
545 _Base::equal_range(__x);
553 equal_range(
const key_type& __x)
const
556 _Base::equal_range(__x);
561 #if __cplusplus > 201103L
562 template<
typename _Kt,
564 typename __has_is_transparent<_Compare, _Kt>::type>
566 equal_range(
const _Kt& __x)
568 auto __res = _Base::equal_range(__x);
569 return { { __res.first,
this }, { __res.second,
this } };
572 template<
typename _Kt,
574 typename __has_is_transparent<_Compare, _Kt>::type>
576 equal_range(
const _Kt& __x)
const
578 auto __res = _Base::equal_range(__x);
579 return { { __res.first,
this }, { __res.second,
this } };
584 _M_base() _GLIBCXX_NOEXCEPT {
return *
this; }
587 _M_base()
const _GLIBCXX_NOEXCEPT {
return *
this; }
590 #if __cpp_deduction_guides >= 201606
592 template<
typename _InputIterator,
595 typename _Allocator =
597 typename = _RequireInputIter<_InputIterator>,
598 typename = _RequireNotAllocator<_Compare>,
599 typename = _RequireAllocator<_Allocator>>
600 set(_InputIterator, _InputIterator,
601 _Compare = _Compare(), _Allocator = _Allocator())
603 _Compare, _Allocator>;
605 template<
typename _Key,
typename _Compare = less<_Key>,
606 typename _Allocator = allocator<_Key>,
607 typename = _RequireNotAllocator<_Compare>,
608 typename = _RequireAllocator<_Allocator>>
610 _Compare = _Compare(), _Allocator = _Allocator())
613 template<
typename _InputIterator,
typename _Allocator,
614 typename = _RequireInputIter<_InputIterator>,
615 typename = _RequireAllocator<_Allocator>>
616 set(_InputIterator, _InputIterator, _Allocator)
621 template<
typename _Key,
typename _Allocator,
622 typename = _RequireAllocator<_Allocator>>
626 #if __glibcxx_containers_ranges
627 template<ranges::input_range _Rg,
630 set(from_range_t, _Rg&&, _Compare = _Compare(), _Alloc = _Alloc())
633 template<ranges::input_range _Rg, __allocator_like _Alloc>
634 set(from_range_t, _Rg&&, _Alloc)
639 template<
typename _Key,
typename _Compare,
typename _Allocator>
643 {
return __lhs._M_base() == __rhs._M_base(); }
645 #if __cpp_lib_three_way_comparison
646 template<
typename _Key,
typename _Compare,
typename _Alloc>
647 inline __detail::__synth3way_t<_Key>
650 {
return __lhs._M_base() <=> __rhs._M_base(); }
652 template<
typename _Key,
typename _Compare,
typename _Allocator>
654 operator!=(
const set<_Key, _Compare, _Allocator>& __lhs,
655 const set<_Key, _Compare, _Allocator>& __rhs)
656 {
return __lhs._M_base() != __rhs._M_base(); }
658 template<
typename _Key,
typename _Compare,
typename _Allocator>
660 operator<(
const set<_Key, _Compare, _Allocator>& __lhs,
661 const set<_Key, _Compare, _Allocator>& __rhs)
662 {
return __lhs._M_base() < __rhs._M_base(); }
664 template<
typename _Key,
typename _Compare,
typename _Allocator>
666 operator<=(
const set<_Key, _Compare, _Allocator>& __lhs,
667 const set<_Key, _Compare, _Allocator>& __rhs)
668 {
return __lhs._M_base() <= __rhs._M_base(); }
670 template<
typename _Key,
typename _Compare,
typename _Allocator>
672 operator>=(
const set<_Key, _Compare, _Allocator>& __lhs,
673 const set<_Key, _Compare, _Allocator>& __rhs)
674 {
return __lhs._M_base() >= __rhs._M_base(); }
676 template<
typename _Key,
typename _Compare,
typename _Allocator>
678 operator>(
const set<_Key, _Compare, _Allocator>& __lhs,
679 const set<_Key, _Compare, _Allocator>& __rhs)
680 {
return __lhs._M_base() > __rhs._M_base(); }
683 template<
typename _Key,
typename _Compare,
typename _Allocator>
685 swap(set<_Key, _Compare, _Allocator>& __x,
686 set<_Key, _Compare, _Allocator>& __y)
687 _GLIBCXX_NOEXCEPT_IF(noexcept(__x.swap(__y)))
688 {
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.
Return type of insert(node_handle&&) on unique maps/sets.
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 unique keys, which can be retrieved in logarithmic time.
void _M_invalidate_if(_Predicate __pred)
Safe class dealing with some allocator dependent operations.
Like _Safe_sequence but with a special _M_invalidate_all implementation not invalidating past-the-end...
Class std::set with safety/checking/debug instrumentation.