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;
105 set(
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 allocator_type& __a)
117 : _Base(__x, __a) { }
119 set(
set&& __x,
const allocator_type& __a)
120 noexcept( noexcept(_Base(
std::move(__x._M_base()), __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)),
137 explicit set(
const _Compare& __comp,
138 const _Allocator& __a = _Allocator())
139 : _Base(__comp, __a) { }
141 template<
typename _InputIterator>
142 set(_InputIterator __first, _InputIterator __last,
143 const _Compare& __comp = _Compare(),
144 const _Allocator& __a = _Allocator())
146 __glibcxx_check_valid_constructor_range(__first, __last)),
151 : _Base(__x._M_ref) { }
153 #if __cplusplus < 201103L 155 operator=(
const set& __x)
157 this->_M_safe() = __x;
163 operator=(
const set&) =
default;
166 operator=(
set&&) =
default;
172 this->_M_invalidate_all();
177 using _Base::get_allocator;
181 begin() _GLIBCXX_NOEXCEPT
182 {
return iterator(_Base::begin(),
this); }
185 begin()
const _GLIBCXX_NOEXCEPT
186 {
return const_iterator(_Base::begin(),
this); }
189 end() _GLIBCXX_NOEXCEPT
190 {
return iterator(_Base::end(),
this); }
193 end()
const _GLIBCXX_NOEXCEPT
194 {
return const_iterator(_Base::end(),
this); }
197 rbegin() _GLIBCXX_NOEXCEPT
198 {
return reverse_iterator(
end()); }
200 const_reverse_iterator
201 rbegin()
const _GLIBCXX_NOEXCEPT
202 {
return const_reverse_iterator(
end()); }
205 rend() _GLIBCXX_NOEXCEPT
206 {
return reverse_iterator(
begin()); }
208 const_reverse_iterator
209 rend()
const _GLIBCXX_NOEXCEPT
210 {
return const_reverse_iterator(
begin()); }
212 #if __cplusplus >= 201103L 215 {
return const_iterator(_Base::begin(),
this); }
218 cend()
const noexcept
219 {
return const_iterator(_Base::end(),
this); }
221 const_reverse_iterator
223 {
return const_reverse_iterator(
end()); }
225 const_reverse_iterator
226 crend()
const noexcept
227 {
return const_reverse_iterator(
begin()); }
233 using _Base::max_size;
236 #if __cplusplus >= 201103L 237 template<
typename... _Args>
239 emplace(_Args&&... __args)
241 auto __res = _Base::emplace(std::forward<_Args>(__args)...);
242 return { { __res.first,
this }, __res.second };
245 template<
typename... _Args>
247 emplace_hint(const_iterator __pos, _Args&&... __args)
252 _Base::emplace_hint(__pos.
base(), std::forward<_Args>(__args)...),
259 insert(
const value_type& __x)
266 #if __cplusplus >= 201103L 268 insert(value_type&& __x)
270 auto __res = _Base::insert(
std::move(__x));
271 return { { __res.first,
this }, __res.second };
276 insert(const_iterator __position,
const value_type& __x)
279 return iterator(_Base::insert(__position.
base(), __x),
this);
282 #if __cplusplus >= 201103L 284 insert(const_iterator __position, value_type&& __x)
287 return { _Base::insert(__position.
base(),
std::move(__x)),
this };
291 template <
typename _InputIterator>
293 insert(_InputIterator __first, _InputIterator __last)
296 __glibcxx_check_valid_range2(__first, __last, __dist);
298 if (__dist.
second >= __gnu_debug::__dp_sign)
299 _Base::insert(__gnu_debug::__unsafe(__first),
300 __gnu_debug::__unsafe(__last));
302 _Base::insert(__first, __last);
305 #if __cplusplus >= 201103L 308 { _Base::insert(__l); }
311 #if __cplusplus > 201402L 312 using node_type =
typename _Base::node_type;
316 extract(const_iterator __position)
320 return _Base::extract(__position.
base());
324 extract(
const key_type& __key)
326 const auto __position = find(__key);
327 if (__position !=
end())
328 return extract(__position);
333 insert(node_type&& __nh)
335 auto __ret = _Base::insert(
std::move(__nh));
336 iterator __pos = iterator(__ret.position,
this);
337 return { __pos, __ret.inserted,
std::move(__ret.node) };
341 insert(const_iterator __hint, node_type&& __nh)
344 return { _Base::insert(__hint.
base(),
std::move(__nh)),
this };
350 #if __cplusplus >= 201103L 351 _GLIBCXX_ABI_TAG_CXX11
353 erase(const_iterator __position)
357 return { _Base::erase(__position.
base()),
this };
361 erase(iterator __position)
365 _Base::erase(__position.
base());
370 erase(
const key_type& __x)
372 _Base_iterator __victim = _Base::find(__x);
373 if (__victim == _Base::end())
378 _Base::erase(__victim);
383 #if __cplusplus >= 201103L 384 _GLIBCXX_ABI_TAG_CXX11
386 erase(const_iterator __first, const_iterator __last)
391 for (_Base_const_iterator __victim = __first.
base();
392 __victim != __last.
base(); ++__victim)
394 _GLIBCXX_DEBUG_VERIFY(__victim != _Base::cend(),
395 _M_message(__gnu_debug::__msg_valid_range)
396 ._M_iterator(__first,
"first")
397 ._M_iterator(__last,
"last"));
401 return { _Base::erase(__first.
base(), __last.
base()),
this };
405 erase(iterator __first, iterator __last)
410 for (_Base_iterator __victim = __first.
base();
411 __victim != __last.
base(); ++__victim)
413 _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(),
414 _M_message(__gnu_debug::__msg_valid_range)
415 ._M_iterator(__first,
"first")
416 ._M_iterator(__last,
"last"));
419 _Base::erase(__first.
base(), __last.
base());
425 _GLIBCXX_NOEXCEPT_IF( noexcept(declval<_Base&>().swap(__x)) )
432 clear() _GLIBCXX_NOEXCEPT
434 this->_M_invalidate_all();
439 using _Base::key_comp;
440 using _Base::value_comp;
444 find(
const key_type& __x)
445 {
return iterator(_Base::find(__x),
this); }
450 find(
const key_type& __x)
const 451 {
return const_iterator(_Base::find(__x),
this); }
453 #if __cplusplus > 201103L 454 template<
typename _Kt,
456 typename __has_is_transparent<_Compare, _Kt>::type>
459 {
return { _Base::find(__x),
this }; }
461 template<
typename _Kt,
463 typename __has_is_transparent<_Compare, _Kt>::type>
465 find(
const _Kt& __x)
const 466 {
return { _Base::find(__x),
this }; }
472 lower_bound(
const key_type& __x)
473 {
return iterator(_Base::lower_bound(__x),
this); }
478 lower_bound(
const key_type& __x)
const 479 {
return const_iterator(_Base::lower_bound(__x),
this); }
481 #if __cplusplus > 201103L 482 template<
typename _Kt,
484 typename __has_is_transparent<_Compare, _Kt>::type>
486 lower_bound(
const _Kt& __x)
487 {
return { _Base::lower_bound(__x),
this }; }
489 template<
typename _Kt,
491 typename __has_is_transparent<_Compare, _Kt>::type>
493 lower_bound(
const _Kt& __x)
const 494 {
return { _Base::lower_bound(__x),
this }; }
498 upper_bound(
const key_type& __x)
499 {
return iterator(_Base::upper_bound(__x),
this); }
504 upper_bound(
const key_type& __x)
const 505 {
return const_iterator(_Base::upper_bound(__x),
this); }
507 #if __cplusplus > 201103L 508 template<
typename _Kt,
510 typename __has_is_transparent<_Compare, _Kt>::type>
512 upper_bound(
const _Kt& __x)
513 {
return { _Base::upper_bound(__x),
this }; }
515 template<
typename _Kt,
517 typename __has_is_transparent<_Compare, _Kt>::type>
519 upper_bound(
const _Kt& __x)
const 520 {
return { _Base::upper_bound(__x),
this }; }
524 equal_range(
const key_type& __x)
527 _Base::equal_range(__x);
528 return std::make_pair(iterator(__res.
first,
this),
529 iterator(__res.
second,
this));
535 equal_range(
const key_type& __x)
const 538 _Base::equal_range(__x);
539 return std::make_pair(const_iterator(__res.
first,
this),
540 const_iterator(__res.
second,
this));
543 #if __cplusplus > 201103L 544 template<
typename _Kt,
546 typename __has_is_transparent<_Compare, _Kt>::type>
548 equal_range(
const _Kt& __x)
550 auto __res = _Base::equal_range(__x);
551 return { { __res.first,
this }, { __res.second,
this } };
554 template<
typename _Kt,
556 typename __has_is_transparent<_Compare, _Kt>::type>
558 equal_range(
const _Kt& __x)
const 560 auto __res = _Base::equal_range(__x);
561 return { { __res.first,
this }, { __res.second,
this } };
566 _M_base() _GLIBCXX_NOEXCEPT {
return *
this; }
569 _M_base()
const _GLIBCXX_NOEXCEPT {
return *
this; }
572 #if __cpp_deduction_guides >= 201606 574 template<
typename _InputIterator,
577 typename _Allocator =
579 typename = _RequireInputIter<_InputIterator>,
580 typename = _RequireNotAllocator<_Compare>,
581 typename = _RequireAllocator<_Allocator>>
582 set(_InputIterator, _InputIterator,
583 _Compare = _Compare(), _Allocator = _Allocator())
585 _Compare, _Allocator>;
587 template<
typename _Key,
typename _Compare = less<_Key>,
588 typename _Allocator = allocator<_Key>,
589 typename = _RequireNotAllocator<_Compare>,
590 typename = _RequireAllocator<_Allocator>>
592 _Compare = _Compare(), _Allocator = _Allocator())
595 template<
typename _InputIterator,
typename _Allocator,
596 typename = _RequireInputIter<_InputIterator>,
597 typename = _RequireAllocator<_Allocator>>
598 set(_InputIterator, _InputIterator, _Allocator)
603 template<
typename _Key,
typename _Allocator,
604 typename = _RequireAllocator<_Allocator>>
605 set(initializer_list<_Key>, _Allocator)
608 #endif // deduction guides 610 template<
typename _Key,
typename _Compare,
typename _Allocator>
614 {
return __lhs._M_base() == __rhs._M_base(); }
616 #if __cpp_lib_three_way_comparison 617 template<
typename _Key,
typename _Compare,
typename _Alloc>
618 inline __detail::__synth3way_t<_Key>
621 {
return __lhs._M_base() <=> __rhs._M_base(); }
623 template<
typename _Key,
typename _Compare,
typename _Allocator>
627 {
return __lhs._M_base() != __rhs._M_base(); }
629 template<
typename _Key,
typename _Compare,
typename _Allocator>
631 operator<(const set<_Key, _Compare, _Allocator>& __lhs,
633 {
return __lhs._M_base() < __rhs._M_base(); }
635 template<
typename _Key,
typename _Compare,
typename _Allocator>
637 operator<=(const set<_Key, _Compare, _Allocator>& __lhs,
639 {
return __lhs._M_base() <= __rhs._M_base(); }
641 template<
typename _Key,
typename _Compare,
typename _Allocator>
645 {
return __lhs._M_base() >= __rhs._M_base(); }
647 template<
typename _Key,
typename _Compare,
typename _Allocator>
651 {
return __lhs._M_base() > __rhs._M_base(); }
652 #endif // three-way comparison 654 template<
typename _Key,
typename _Compare,
typename _Allocator>
658 _GLIBCXX_NOEXCEPT_IF(noexcept(__x.swap(__y)))
659 {
return __x.swap(__y); }
#define __glibcxx_check_insert(_Position)
_T2 second
The second member.
Like _Safe_sequence but with a special _M_invalidate_all implementation not invalidating past-the-end...
constexpr auto crend(const _Container &__cont) -> decltype(std::rend(__cont))
Return a reverse iterator pointing one past the first element of the const container.
constexpr auto rbegin(_Container &__cont) -> decltype(__cont.rbegin())
Return a reverse iterator pointing to the last element of the container.
The standard allocator, as per C++03 [20.4.1].
_Iterator & base() noexcept
Return the underlying iterator.
_T1 first
The first member.
Class std::set with safety/checking/debug instrumentation.
_Tp * end(valarray< _Tp > &__va) noexcept
Return an iterator pointing to one past the last element of the valarray.
One of the comparison functors.
constexpr auto empty(const _Container &__cont) noexcept(noexcept(__cont.empty())) -> decltype(__cont.empty())
Return whether a container is empty.
constexpr auto crbegin(const _Container &__cont) -> decltype(std::rbegin(__cont))
Return a reverse iterator pointing to the last element of the const container.
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
Struct holding two objects of arbitrary type.
void _M_invalidate_if(_Predicate __pred)
constexpr auto size(const _Container &__cont) noexcept(noexcept(__cont.size())) -> decltype(__cont.size())
Return the size of a container.
Traits class for iterators.
_Tp * begin(valarray< _Tp > &__va) noexcept
Return an iterator pointing to the first element of the valarray.
constexpr auto cbegin(const _Container &__cont) noexcept(noexcept(std::begin(__cont))) -> decltype(std::begin(__cont))
Return an iterator pointing to the first element of the const container.
constexpr auto rend(_Container &__cont) -> decltype(__cont.rend())
Return a reverse iterator pointing one past the first element of the container.
#define __glibcxx_check_erase_range(_First, _Last)
constexpr auto cend(const _Container &__cont) noexcept(noexcept(std::end(__cont))) -> decltype(std::end(__cont))
Return an iterator pointing to one past the last element of the const container.
Return type of insert(node_handle&&) on unique maps/sets.
ISO C++ entities toplevel namespace is std.
constexpr _Iterator __base(_Iterator __it)
Safe class dealing with some allocator dependent operations.
#define __glibcxx_check_erase(_Position)