Whenever we use operator+ or similar operators on random access
iterators we need to be careful to use the iterator's difference_type
rather than some other integer type. It's not guaranteed that an
expression with an arbitrary integer type, such as `it + 1u`, has the
same effects as `it + iter_difference_t<It>(1)`.
Some of our algorithms need changes to cast values to the correct type,
or to use std::next or ranges::next instead of `it + n`. Several tests
also need fixes where the arithmetic occurs directly in the test.
The __gnu_test::random_access_iterator_wrapper class template is
adjusted to have deleted operators that make programs ill-formed if the
argument to relevant operators is not the difference_type. This will
make it easier to avoid regressing in future.
libstdc++-v3/ChangeLog:
PR libstdc++/121890
* include/bits/ranges_algo.h (ranges::rotate, ranges::shuffle)
(__insertion_sort, __unguarded_partition_pivot, __introselect):
Use ranges::next to advance iterators. Use local variables in
rotate to avoid duplicate expressions.
(ranges::push_heap, ranges::pop_heap, ranges::partial_sort)
(ranges::partial_sort_copy): Use ranges::prev.
(__final_insertion_sort): Use iter_difference_t<Iter>
for operand of operator+ on iterator.
* include/bits/ranges_base.h (ranges::advance): Use iterator's
difference_type for all iterator arithmetic.
* include/bits/stl_algo.h (__search_n_aux, __rotate)
(__insertion_sort, __unguarded_partition_pivot, __introselect)
(__final_insertion_sort, for_each_n, random_shuffle): Likewise.
Use local variables in __rotate to avoid duplicate expressions.
* include/bits/stl_algobase.h (__fill_n_a, __lc_rai::__newlast1):
Likewise.
* include/bits/stl_heap.h (push_heap): Likewise.
(__is_heap_until): Add static_assert.
(__is_heap): Convert distance to difference_type.
* include/std/functional (boyer_moore_searcher::operator()): Use
iterator's difference_type for iterator arithmetic.
* testsuite/util/testsuite_iterators.h
(random_access_iterator_wrapper): Add deleted overloads of
operators that should be called with difference_type.
* testsuite/24_iterators/range_operations/advance.cc: Use
ranges::next.
* testsuite/25_algorithms/heap/constrained.cc: Use ranges::next
and ranges::prev.
* testsuite/25_algorithms/nth_element/58800.cc: Use std::next.
* testsuite/25_algorithms/nth_element/constrained.cc: Use
ptrdiff_t for loop variable.
* testsuite/25_algorithms/nth_element/random_test.cc: Use
iterator's difference_type instead of int.
* testsuite/25_algorithms/partial_sort/check_compare_by_value.cc:
Use std::next.
* testsuite/25_algorithms/partial_sort/constrained.cc: Use
ptrdiff_t for loop variable.
* testsuite/25_algorithms/partial_sort/random_test.cc: Use
iterator's difference_type instead of int.
* testsuite/25_algorithms/partial_sort_copy/constrained.cc:
Use ptrdiff_t for loop variable.
* testsuite/25_algorithms/partial_sort_copy/random_test.cc:
Use iterator's difference_type instead of int.
* testsuite/std/ranges/adaptors/drop.cc: Use ranges::next.
* testsuite/25_algorithms/fill_n/diff_type.cc: New test.
* testsuite/25_algorithms/for_each/diff_type.cc: New test.
* testsuite/25_algorithms/lexicographical_compare/diff_type.cc:
New test.
* testsuite/25_algorithms/push_heap/diff_type.cc: New test.
* testsuite/25_algorithms/nth_element/diff_type.cc: New test.
* testsuite/25_algorithms/rotate/diff_type.cc: New test.
* testsuite/25_algorithms/search_n/diff_type.cc: New test.
* testsuite/25_algorithms/sort/diff_type.cc: New test.
---
v3: Change in boyer_moore_searcher suggested by Tomasz. Reverted
unnecessary ranges::next in ranges::rotate noticed by Patrick, and
changed it to use local variables as done for std::rotate in v2.
Tested powerpc64le-linux.
libstdc++-v3/include/bits/ranges_algo.h | 57 +++++++------
libstdc++-v3/include/bits/ranges_base.h | 4 +-
libstdc++-v3/include/bits/stl_algo.h | 81 +++++++++++++------
libstdc++-v3/include/bits/stl_algobase.h | 18 +++--
libstdc++-v3/include/bits/stl_heap.h | 18 +++--
libstdc++-v3/include/std/functional | 2 +-
.../24_iterators/range_operations/advance.cc | 2 +-
.../25_algorithms/fill_n/diff_type.cc | 13 +++
.../25_algorithms/for_each/diff_type.cc | 13 +++
.../25_algorithms/heap/constrained.cc | 20 ++---
.../lexicographical_compare/diff_type.cc | 57 +++++++++++++
.../25_algorithms/nth_element/58800.cc | 2 +-
.../25_algorithms/nth_element/constrained.cc | 2 +-
.../25_algorithms/nth_element/diff_type.cc | 13 +++
.../25_algorithms/nth_element/random_test.cc | 4 +-
.../partial_sort/check_compare_by_value.cc | 4 +-
.../25_algorithms/partial_sort/constrained.cc | 3 +-
.../25_algorithms/partial_sort/random_test.cc | 4 +-
.../partial_sort_copy/constrained.cc | 4 +-
.../partial_sort_copy/random_test.cc | 4 +-
.../25_algorithms/push_heap/diff_type.cc | 13 +++
.../25_algorithms/rotate/diff_type.cc | 13 +++
.../25_algorithms/search_n/diff_type.cc | 13 +++
.../testsuite/25_algorithms/sort/diff_type.cc | 13 +++
.../testsuite/std/ranges/adaptors/drop.cc | 2 +-
.../testsuite/util/testsuite_iterators.h | 18 +++++
26 files changed, 307 insertions(+), 90 deletions(-)
create mode 100644 libstdc++-v3/testsuite/25_algorithms/fill_n/diff_type.cc
create mode 100644 libstdc++-v3/testsuite/25_algorithms/for_each/diff_type.cc
create mode 100644
libstdc++-v3/testsuite/25_algorithms/lexicographical_compare/diff_type.cc
create mode 100644
libstdc++-v3/testsuite/25_algorithms/nth_element/diff_type.cc
create mode 100644 libstdc++-v3/testsuite/25_algorithms/push_heap/diff_type.cc
create mode 100644 libstdc++-v3/testsuite/25_algorithms/rotate/diff_type.cc
create mode 100644 libstdc++-v3/testsuite/25_algorithms/search_n/diff_type.cc
create mode 100644 libstdc++-v3/testsuite/25_algorithms/sort/diff_type.cc
diff --git a/libstdc++-v3/include/bits/ranges_algo.h
b/libstdc++-v3/include/bits/ranges_algo.h
index 6e1e06cb2d0f..609b82e26d8a 100644
--- a/libstdc++-v3/include/bits/ranges_algo.h
+++ b/libstdc++-v3/include/bits/ranges_algo.h
@@ -1666,68 +1666,72 @@ namespace ranges
auto __k = __middle - __first;
if (__k == __n - __k)
{
ranges::swap_ranges(__first, __middle, __middle, __middle +
__k);
return {std::move(__middle), std::move(__lasti)};
}
auto __p = __first;
auto __ret = __first + (__lasti - __middle);
for (;;)
{
if (__k < __n - __k)
{
// TODO: is_pod is deprecated, but this condition is
// consistent with the STL implementation.
if constexpr (__is_pod(iter_value_t<_Iter>))
if (__k == 1)
{
+ auto __mid = ranges::next(__p, __n - 1);
+ auto __end = ranges::next(__mid);
auto __t = std::move(*__p);
- ranges::move(__p + 1, __p + __n, __p);
- *(__p + __n - 1) = std::move(__t);
+ ranges::move(ranges::next(__p), __end, __p);
+ *__mid = std::move(__t);
return {std::move(__ret), std::move(__lasti)};
}
auto __q = __p + __k;
for (decltype(__n) __i = 0; __i < __n - __k; ++ __i)
{
ranges::iter_swap(__p, __q);
++__p;
++__q;
}
__n %= __k;
if (__n == 0)
return {std::move(__ret), std::move(__lasti)};
ranges::swap(__n, __k);
__k = __n - __k;
}
else
{
__k = __n - __k;
// TODO: is_pod is deprecated, but this condition is
// consistent with the STL implementation.
if constexpr (__is_pod(iter_value_t<_Iter>))
if (__k == 1)
{
- auto __t = std::move(*(__p + __n - 1));
- ranges::move_backward(__p, __p + __n - 1, __p + __n);
+ auto __mid = ranges::next(__p, __n - 1);
+ auto __end = ranges::next(__mid);
+ auto __t = std::move(*__mid);
+ ranges::move_backward(__p, __mid, __end);
*__p = std::move(__t);
return {std::move(__ret), std::move(__lasti)};
}
auto __q = __p + __n;
__p = __q - __k;
for (decltype(__n) __i = 0; __i < __n - __k; ++ __i)
{
--__p;
--__q;
ranges::iter_swap(__p, __q);
}
__n %= __k;
if (__n == 0)
return {std::move(__ret), std::move(__lasti)};
std::swap(__n, __k);
}
}
}
else if constexpr (bidirectional_iterator<_Iter>)
{
@@ -1953,75 +1957,77 @@ namespace ranges
operator()(_Iter __first, _Sent __last, _Gen&& __g) const
{
// FIXME: Correctly handle integer-class difference types.
if (__first == __last)
return __first;
using _DistanceType = iter_difference_t<_Iter>;
using __ud_type = __detail::__make_unsigned_like_t<_DistanceType>;
using __distr_type = std::uniform_int_distribution<__ud_type>;
using __p_type = typename __distr_type::param_type;
using __uc_type
= common_type_t<typename remove_reference_t<_Gen>::result_type,
__ud_type>;
const __uc_type __urngrange = __g.max() - __g.min();
const __uc_type __urange = __uc_type(__last - __first);
if (__urngrange / __urange >= __urange)
// I.e. (__urngrange >= __urange * __urange) but without wrap issues.
{
- _Iter __i = __first + 1;
+ _Iter __i = ranges::next(__first);
// Since we know the range isn't empty, an even number of elements
// means an uneven number of elements /to swap/, in which case we
// do the first one up front:
if ((__urange % 2) == 0)
{
__distr_type __d{0, 1};
- ranges::iter_swap(__i++, __first + __d(__g));
+ ranges::iter_swap(__i++, ranges::next(__first, __d(__g)));
}
// Now we know that __last - __i is even, so we do the rest in
pairs,
// using a single distribution invocation to produce swap positions
// for two successive elements at a time:
while (__i != __last)
{
const __uc_type __swap_range = __uc_type(__i - __first) + 1;
- const pair<__uc_type, __uc_type> __pospos =
+ const pair<_DistanceType, _DistanceType> __pospos =
__gen_two_uniform_ints(__swap_range, __swap_range + 1, __g);
- ranges::iter_swap(__i++, __first + __pospos.first);
- ranges::iter_swap(__i++, __first + __pospos.second);
+ ranges::iter_swap(__i++, ranges::next(__first, __pospos.first));
+ ranges::iter_swap(__i++, ranges::next(__first,
__pospos.second));
}
return __i;
}
__distr_type __d;
- _Iter __i = __first + 1;
+ _Iter __i = ranges::next(__first);
for (; __i != __last; ++__i)
- ranges::iter_swap(__i, __first + __d(__g, __p_type(0, __i -
__first)));
+ ranges::iter_swap(__i,
+ ranges::next(__first,
+ __d(__g, __p_type(0, __i - __first))));
return __i;
}
template<random_access_range _Range, typename _Gen>
requires permutable<iterator_t<_Range>>
&& uniform_random_bit_generator<remove_reference_t<_Gen>>
borrowed_iterator_t<_Range>
operator()(_Range&& __r, _Gen&& __g) const
{
return (*this)(ranges::begin(__r), ranges::end(__r),
std::forward<_Gen>(__g));
}
};
inline constexpr __shuffle_fn shuffle{};
namespace __detail
{
template<typename _Iter, typename _Comp>
@@ -2043,41 +2049,41 @@ namespace ranges
*(__first + __holeIndex) = std::move(__value);
}
} // namespace __detail
struct __push_heap_fn
{
template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
typename _Comp = ranges::less, typename _Proj = identity>
requires sortable<_Iter, _Comp, _Proj>
constexpr _Iter
operator()(_Iter __first, _Sent __last,
_Comp __comp = {}, _Proj __proj = {}) const
{
if constexpr (!same_as<_Iter, _Sent>)
return (*this)(__first, ranges::next(__first, __last),
std::move(__comp), std::move(__proj));
else
{
auto __comp_proj = __detail::__make_comp_proj(__comp, __proj);
__detail::__push_heap(__first, (__last - __first) - 1,
- 0, ranges::iter_move(__last - 1),
+ 0, ranges::iter_move(ranges::prev(__last)),
__comp_proj);
return __last;
}
}
template<random_access_range _Range,
typename _Comp = ranges::less, typename _Proj = identity>
requires sortable<iterator_t<_Range>, _Comp, _Proj>
constexpr borrowed_iterator_t<_Range>
operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const
{
return (*this)(ranges::begin(__r), ranges::end(__r),
std::move(__comp), std::move(__proj));
}
};
inline constexpr __push_heap_fn push_heap{};
namespace __detail
{
@@ -2120,42 +2126,43 @@ namespace ranges
std::move(__value), __comp);
}
} // namespace __detail
struct __pop_heap_fn
{
template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
typename _Comp = ranges::less, typename _Proj = identity>
requires sortable<_Iter, _Comp, _Proj>
constexpr _Iter
operator()(_Iter __first, _Sent __last,
_Comp __comp = {}, _Proj __proj = {}) const
{
if constexpr (!same_as<_Iter, _Sent>)
return (*this)(__first, ranges::next(__first, __last),
std::move(__comp), std::move(__proj));
else
{
if (__last - __first > 1)
{
+ auto __back = ranges::prev(__last);
auto __comp_proj = __detail::__make_comp_proj(__comp, __proj);
- __detail::__pop_heap(__first, __last - 1, __last - 1,
__comp_proj);
+ __detail::__pop_heap(__first, __back, __back, __comp_proj);
}
return __last;
}
}
template<random_access_range _Range,
typename _Comp = ranges::less, typename _Proj = identity>
requires sortable<iterator_t<_Range>, _Comp, _Proj>
constexpr borrowed_iterator_t<_Range>
operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const
{
return (*this)(ranges::begin(__r), ranges::end(__r),
std::move(__comp), std::move(__proj));
}
};
inline constexpr __pop_heap_fn pop_heap{};
struct __make_heap_fn
{
@@ -2339,102 +2346,105 @@ namespace ranges
{
iter_value_t<_Iter> __val = ranges::iter_move(__last);
_Iter __next = __last;
--__next;
while (__comp(__val, *__next))
{
*__last = ranges::iter_move(__next);
__last = __next;
--__next;
}
*__last = std::move(__val);
}
template<typename _Iter, typename _Comp>
constexpr void
__insertion_sort(_Iter __first, _Iter __last, _Comp __comp)
{
if (__first == __last)
return;
- for (_Iter __i = __first + 1; __i != __last; ++__i)
+ for (_Iter __i = ranges::next(__first); __i != __last; ++__i)
{
if (__comp(*__i, *__first))
{
iter_value_t<_Iter> __val = ranges::iter_move(__i);
- ranges::move_backward(__first, __i, __i + 1);
+ ranges::move_backward(__first, __i, ranges::next(__i));
*__first = std::move(__val);
}
else
__detail::__unguarded_linear_insert(__i, __comp);
}
}
template<typename _Iter, typename _Comp>
constexpr void
__unguarded_insertion_sort(_Iter __first, _Iter __last, _Comp __comp)
{
for (_Iter __i = __first; __i != __last; ++__i)
__detail::__unguarded_linear_insert(__i, __comp);
}
inline constexpr int __sort_threshold = 16;
template<typename _Iter, typename _Comp>
constexpr void
__final_insertion_sort(_Iter __first, _Iter __last, _Comp __comp)
{
- if (__last - __first > __sort_threshold)
+ constexpr iter_difference_t<_Iter> __threshold = __sort_threshold;
+ if (__last - __first > __threshold)
{
- __detail::__insertion_sort(__first, __first + __sort_threshold,
__comp);
- __detail::__unguarded_insertion_sort(__first + __sort_threshold,
__last,
+ __detail::__insertion_sort(__first, __first + __threshold, __comp);
+ __detail::__unguarded_insertion_sort(__first + __threshold, __last,
__comp);
}
else
__detail::__insertion_sort(__first, __last, __comp);
}
template<typename _Iter, typename _Comp>
constexpr _Iter
__unguarded_partition(_Iter __first, _Iter __last, _Iter __pivot, _Comp
__comp)
{
while (true)
{
while (__comp(*__first, *__pivot))
++__first;
--__last;
while (__comp(*__pivot, *__last))
--__last;
if (!(__first < __last))
return __first;
ranges::iter_swap(__first, __last);
++__first;
}
}
template<typename _Iter, typename _Comp>
constexpr _Iter
__unguarded_partition_pivot(_Iter __first, _Iter __last, _Comp __comp)
{
_Iter __mid = __first + (__last - __first) / 2;
- __detail::__move_median_to_first(__first, __first + 1, __mid, __last -
1, __comp);
- return __detail::__unguarded_partition(__first + 1, __last, __first,
__comp);
+ __detail::__move_median_to_first(__first, ranges::next(__first), __mid,
+ ranges::prev(__last), __comp);
+ return __detail::__unguarded_partition(ranges::next(__first), __last,
+ __first, __comp);
}
template<typename _Iter, typename _Comp>
constexpr void
__heap_select(_Iter __first, _Iter __middle, _Iter __last, _Comp __comp)
{
ranges::make_heap(__first, __middle, __comp);
for (_Iter __i = __middle; __i < __last; ++__i)
if (__comp(*__i, *__first))
__detail::__pop_heap(__first, __middle, __i, __comp);
}
template<typename _Iter, typename _Comp>
constexpr void
__partial_sort(_Iter __first, _Iter __middle, _Iter __last, _Comp __comp)
{
__detail::__heap_select(__first, __middle, __last, __comp);
ranges::sort_heap(__first, __middle, __comp);
}
@@ -2728,41 +2738,41 @@ namespace ranges
struct __partial_sort_fn
{
template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
typename _Comp = ranges::less, typename _Proj = identity>
requires sortable<_Iter, _Comp, _Proj>
constexpr _Iter
operator()(_Iter __first, _Iter __middle, _Sent __last,
_Comp __comp = {}, _Proj __proj = {}) const
{
if (__first == __middle)
return ranges::next(__first, __last);
ranges::make_heap(__first, __middle, __comp, __proj);
auto __i = __middle;
for (; __i != __last; ++__i)
if (std::__invoke(__comp,
std::__invoke(__proj, *__i),
std::__invoke(__proj, *__first)))
{
ranges::pop_heap(__first, __middle, __comp, __proj);
- ranges::iter_swap(__middle-1, __i);
+ ranges::iter_swap(std::prev(__middle), __i);
ranges::push_heap(__first, __middle, __comp, __proj);
}
ranges::sort_heap(__first, __middle, __comp, __proj);
return __i;
}
template<random_access_range _Range,
typename _Comp = ranges::less, typename _Proj = identity>
requires sortable<iterator_t<_Range>, _Comp, _Proj>
constexpr borrowed_iterator_t<_Range>
operator()(_Range&& __r, iterator_t<_Range> __middle,
_Comp __comp = {}, _Proj __proj = {}) const
{
return (*this)(ranges::begin(__r), std::move(__middle),
ranges::end(__r),
std::move(__comp), std::move(__proj));
}
};
@@ -2795,41 +2805,41 @@ namespace ranges
std::move(__last));
return {std::move(__lasti), std::move(__result_first)};
}
auto __result_real_last = __result_first;
while (__first != __last && __result_real_last != __result_last)
{
*__result_real_last = *__first;
++__result_real_last;
++__first;
}
ranges::make_heap(__result_first, __result_real_last, __comp, __proj2);
for (; __first != __last; ++__first)
if (std::__invoke(__comp,
std::__invoke(__proj1, *__first),
std::__invoke(__proj2, *__result_first)))
{
ranges::pop_heap(__result_first, __result_real_last,
__comp, __proj2);
- *(__result_real_last-1) = *__first;
+ *ranges::prev(__result_real_last) = *__first;
ranges::push_heap(__result_first, __result_real_last,
__comp, __proj2);
}
ranges::sort_heap(__result_first, __result_real_last, __comp, __proj2);
return {std::move(__first), std::move(__result_real_last)};
}
template<input_range _Range1, random_access_range _Range2,
typename _Comp = ranges::less,
typename _Proj1 = identity, typename _Proj2 = identity>
requires indirectly_copyable<iterator_t<_Range1>, iterator_t<_Range2>>
&& sortable<iterator_t<_Range2>, _Comp, _Proj2>
&& indirect_strict_weak_order<_Comp,
projected<iterator_t<_Range1>, _Proj1>,
projected<iterator_t<_Range2>, _Proj2>>
constexpr partial_sort_copy_result<borrowed_iterator_t<_Range1>,
borrowed_iterator_t<_Range2>>
operator()(_Range1&& __r, _Range2&& __out, _Comp __comp = {},
_Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
@@ -2907,41 +2917,42 @@ namespace ranges
operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const
{
return (*this)(ranges::begin(__r), ranges::end(__r),
std::move(__comp), std::move(__proj));
}
};
inline constexpr __is_sorted_fn is_sorted{};
namespace __detail
{
template<typename _Iter, typename _Comp>
constexpr void
__introselect(_Iter __first, _Iter __nth, _Iter __last,
iter_difference_t<_Iter> __depth_limit, _Comp __comp)
{
while (__last - __first > 3)
{
if (__depth_limit == 0)
{
- __detail::__heap_select(__first, __nth + 1, __last, __comp);
+ __detail::__heap_select(__first, ranges::next(__nth), __last,
+ __comp);
// Place the nth largest element in its final position.
ranges::iter_swap(__first, __nth);
return;
}
--__depth_limit;
_Iter __cut = __detail::__unguarded_partition_pivot(__first,
__last, __comp);
if (__cut <= __nth)
__first = __cut;
else
__last = __cut;
}
__detail::__insertion_sort(__first, __last, __comp);
}
} // namespace __detail
struct __nth_element_fn
{
template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
typename _Comp = ranges::less, typename _Proj = identity>
requires sortable<_Iter, _Comp, _Proj>
diff --git a/libstdc++-v3/include/bits/ranges_base.h
b/libstdc++-v3/include/bits/ranges_base.h
index 27829086a351..1c4bf432c8f4 100644
--- a/libstdc++-v3/include/bits/ranges_base.h
+++ b/libstdc++-v3/include/bits/ranges_base.h
@@ -883,61 +883,61 @@ namespace ranges
{
while (__it != __bound)
++__it;
}
}
template<input_or_output_iterator _It, sentinel_for<_It> _Sent>
constexpr iter_difference_t<_It>
operator()(_It& __it, iter_difference_t<_It> __n, _Sent __bound) const
{
if constexpr (sized_sentinel_for<_Sent, _It>)
{
const iter_difference_t<_It> __diff = __bound - __it;
if (__diff == 0)
{
// inline any possible side effects of advance(it, bound)
if constexpr (assignable_from<_It&, _Sent>)
__it = std::move(__bound);
else if constexpr (random_access_iterator<_It>)
- __it += 0;
+ __it += iter_difference_t<_It>(0);
return __n;
}
else if (__diff > 0 ? __n >= __diff : __n <= __diff)
{
(*this)(__it, __bound);
return __n - __diff;
}
else if (__n != 0) [[likely]]
{
// n and bound must not lead in opposite directions:
__glibcxx_assert((__n < 0) == (__diff < 0));
(*this)(__it, __n);
return 0;
}
else
{
// inline any possible side effects of advance(it, n)
if constexpr (random_access_iterator<_It>)
- __it += 0;
+ __it += iter_difference_t<_It>(0);
return 0;
}
}
else if (__n == 0 || __it == __bound)
return __n;
else if (__n > 0)
{
iter_difference_t<_It> __m = 0;
do
{
++__it;
++__m;
}
while (__m != __n && __it != __bound);
return __n - __m;
}
else if constexpr (bidirectional_iterator<_It> && same_as<_It, _Sent>)
{
iter_difference_t<_It> __m = 0;
do
diff --git a/libstdc++-v3/include/bits/stl_algo.h
b/libstdc++-v3/include/bits/stl_algo.h
index 81a2457ae6f2..78c63e79a279 100644
--- a/libstdc++-v3/include/bits/stl_algo.h
+++ b/libstdc++-v3/include/bits/stl_algo.h
@@ -187,41 +187,41 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
__search_n_aux(_RandomAccessIter __first, _RandomAccessIter __last,
_Integer __count, _UnaryPredicate __unary_pred,
std::random_access_iterator_tag)
{
typedef typename std::iterator_traits<_RandomAccessIter>::difference_type
_DistanceType;
_DistanceType __tailSize = __last - __first;
_DistanceType __remainder = __count;
while (__remainder <= __tailSize) // the main loop...
{
__first += __remainder;
__tailSize -= __remainder;
// __first here is always pointing to one past the last element of
// next possible match.
_RandomAccessIter __backTrack = __first;
while (__unary_pred(--__backTrack))
{
if (--__remainder == 0)
- return (__first - __count); // Success
+ return __first - _DistanceType(__count); // Success
}
__remainder = __count + 1 - (__first - __backTrack);
}
return __last; // Failure
}
template<typename _ForwardIterator, typename _Integer,
typename _UnaryPredicate>
_GLIBCXX20_CONSTEXPR
_ForwardIterator
__search_n(_ForwardIterator __first, _ForwardIterator __last,
_Integer __count,
_UnaryPredicate __unary_pred)
{
if (__count <= 0)
return __first;
if (__count == 1)
return std::__find_if(__first, __last, __unary_pred);
@@ -1241,65 +1241,71 @@ _GLIBCXX_BEGIN_INLINE_ABI_NAMESPACE(_V2)
#endif
_Distance __n = __last - __first;
_Distance __k = __middle - __first;
if (__k == __n - __k)
{
std::swap_ranges(__first, __middle, __middle);
return __middle;
}
_RandomAccessIterator __p = __first;
_RandomAccessIterator __ret = __first + (__last - __middle);
for (;;)
{
if (__k < __n - __k)
{
if (__is_pod(_ValueType) && __k == 1)
{
+ _RandomAccessIterator __mid = __p + _Distance(__n - 1);
+ _RandomAccessIterator __end = __mid;
+ ++__end;
_ValueType __t = _GLIBCXX_MOVE(*__p);
- _GLIBCXX_MOVE3(__p + 1, __p + __n, __p);
- *(__p + __n - 1) = _GLIBCXX_MOVE(__t);
+ _GLIBCXX_MOVE3(__p + _Distance(1), __end, __p);
+ *__mid = _GLIBCXX_MOVE(__t);
return __ret;
}
_RandomAccessIterator __q = __p + __k;
for (_Distance __i = 0; __i < __n - __k; ++ __i)
{
std::iter_swap(__p, __q);
++__p;
++__q;
}
__n = static_cast<_UDistance>(__n) % static_cast<_UDistance>(__k);
if (__n == 0)
return __ret;
std::swap(__n, __k);
__k = __n - __k;
}
else
{
__k = __n - __k;
if (__is_pod(_ValueType) && __k == 1)
{
- _ValueType __t = _GLIBCXX_MOVE(*(__p + __n - 1));
- _GLIBCXX_MOVE_BACKWARD3(__p, __p + __n - 1, __p + __n);
+ _RandomAccessIterator __mid = __p + _Distance(__n - 1);
+ _RandomAccessIterator __end = __mid;
+ ++__end;
+ _ValueType __t = _GLIBCXX_MOVE(*__mid);
+ _GLIBCXX_MOVE_BACKWARD3(__p, __mid, __end);
*__p = _GLIBCXX_MOVE(__t);
return __ret;
}
_RandomAccessIterator __q = __p + __n;
__p = __q - __k;
for (_Distance __i = 0; __i < __n - __k; ++ __i)
{
--__p;
--__q;
std::iter_swap(__p, __q);
}
__n = static_cast<_UDistance>(__n) % static_cast<_UDistance>(__k);
if (__n == 0)
return __ret;
std::swap(__n, __k);
}
}
}
// _GLIBCXX_RESOLVE_LIB_DEFECTS
@@ -1753,125 +1759,135 @@ _GLIBCXX_END_INLINE_ABI_NAMESPACE(_V2)
typename iterator_traits<_RandomAccessIterator>::value_type
__val = _GLIBCXX_MOVE(*__last);
_RandomAccessIterator __next = __last;
--__next;
while (__comp(__val, __next))
{
*__last = _GLIBCXX_MOVE(*__next);
__last = __next;
--__next;
}
*__last = _GLIBCXX_MOVE(__val);
}
/// This is a helper function for the sort routine.
template<typename _RandomAccessIterator, typename _Compare>
_GLIBCXX20_CONSTEXPR
void
__insertion_sort(_RandomAccessIterator __first,
_RandomAccessIterator __last, _Compare __comp)
{
- if (__first == __last) return;
+ if (__first == __last)
+ return;
- for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
+ typedef iterator_traits<_RandomAccessIterator> _IterTraits;
+ typedef typename _IterTraits::difference_type _Dist;
+
+ for (_RandomAccessIterator __i = __first + _Dist(1); __i != __last;
++__i)
{
if (__comp(__i, __first))
{
- typename iterator_traits<_RandomAccessIterator>::value_type
- __val = _GLIBCXX_MOVE(*__i);
- _GLIBCXX_MOVE_BACKWARD3(__first, __i, __i + 1);
+ typename _IterTraits::value_type __val = _GLIBCXX_MOVE(*__i);
+ _GLIBCXX_MOVE_BACKWARD3(__first, __i, __i + _Dist(1));
*__first = _GLIBCXX_MOVE(__val);
}
else
std::__unguarded_linear_insert(__i,
__gnu_cxx::__ops::__val_comp_iter(__comp));
}
}
/// This is a helper function for the sort routine.
template<typename _RandomAccessIterator, typename _Compare>
_GLIBCXX20_CONSTEXPR
inline void
__unguarded_insertion_sort(_RandomAccessIterator __first,
_RandomAccessIterator __last, _Compare __comp)
{
for (_RandomAccessIterator __i = __first; __i != __last; ++__i)
std::__unguarded_linear_insert(__i,
__gnu_cxx::__ops::__val_comp_iter(__comp));
}
/**
* @doctodo
* This controls some aspect of the sort routines.
*/
enum { _S_threshold = 16 };
/// This is a helper function for the sort routine.
template<typename _RandomAccessIterator, typename _Compare>
_GLIBCXX20_CONSTEXPR
void
__final_insertion_sort(_RandomAccessIterator __first,
_RandomAccessIterator __last, _Compare __comp)
{
- if (__last - __first > int(_S_threshold))
+ typename iterator_traits<_RandomAccessIterator>::difference_type
+ __threshold = _S_threshold;
+
+ if (__last - __first > __threshold)
{
- std::__insertion_sort(__first, __first + int(_S_threshold), __comp);
- std::__unguarded_insertion_sort(__first + int(_S_threshold), __last,
+ std::__insertion_sort(__first, __first + __threshold, __comp);
+ std::__unguarded_insertion_sort(__first + __threshold, __last,
__comp);
}
else
std::__insertion_sort(__first, __last, __comp);
}
/// This is a helper function...
template<typename _RandomAccessIterator, typename _Compare>
_GLIBCXX20_CONSTEXPR
_RandomAccessIterator
__unguarded_partition(_RandomAccessIterator __first,
_RandomAccessIterator __last,
_RandomAccessIterator __pivot, _Compare __comp)
{
while (true)
{
while (__comp(__first, __pivot))
++__first;
--__last;
while (__comp(__pivot, __last))
--__last;
if (!(__first < __last))
return __first;
std::iter_swap(__first, __last);
++__first;
}
}
/// This is a helper function...
template<typename _RandomAccessIterator, typename _Compare>
_GLIBCXX20_CONSTEXPR
inline _RandomAccessIterator
__unguarded_partition_pivot(_RandomAccessIterator __first,
_RandomAccessIterator __last, _Compare __comp)
{
- _RandomAccessIterator __mid = __first + (__last - __first) / 2;
- std::__move_median_to_first(__first, __first + 1, __mid, __last - 1,
+ typedef iterator_traits<_RandomAccessIterator> _IterTraits;
+ typedef typename _IterTraits::difference_type _Dist;
+
+ _RandomAccessIterator __mid = __first + _Dist((__last - __first) / 2);
+ _RandomAccessIterator __second = __first + _Dist(1);
+ std::__move_median_to_first(__first, __second, __mid, __last - _Dist(1),
__comp);
- return std::__unguarded_partition(__first + 1, __last, __first, __comp);
+ return std::__unguarded_partition(__second, __last, __first, __comp);
}
template<typename _RandomAccessIterator, typename _Compare>
_GLIBCXX20_CONSTEXPR
inline void
__partial_sort(_RandomAccessIterator __first,
_RandomAccessIterator __middle,
_RandomAccessIterator __last,
_Compare __comp)
{
std::__heap_select(__first, __middle, __last, __comp);
std::__sort_heap(__first, __middle, __comp);
}
/// This is a helper function for the sort routine.
template<typename _RandomAccessIterator, typename _Size, typename _Compare>
_GLIBCXX20_CONSTEXPR
void
__introsort_loop(_RandomAccessIterator __first,
_RandomAccessIterator __last,
@@ -1899,45 +1915,48 @@ _GLIBCXX_END_INLINE_ABI_NAMESPACE(_V2)
inline void
__sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
_Compare __comp)
{
if (__first != __last)
{
std::__introsort_loop(__first, __last,
std::__lg(__last - __first) * 2,
__comp);
std::__final_insertion_sort(__first, __last, __comp);
}
}
template<typename _RandomAccessIterator, typename _Size, typename _Compare>
_GLIBCXX20_CONSTEXPR
void
__introselect(_RandomAccessIterator __first, _RandomAccessIterator __nth,
_RandomAccessIterator __last, _Size __depth_limit,
_Compare __comp)
{
+ _RandomAccessIterator __after_nth = __nth;
+ ++__after_nth;
+
while (__last - __first > 3)
{
if (__depth_limit == 0)
{
- std::__heap_select(__first, __nth + 1, __last, __comp);
+ std::__heap_select(__first, __after_nth, __last, __comp);
// Place the nth largest element in its final position.
std::iter_swap(__first, __nth);
return;
}
--__depth_limit;
_RandomAccessIterator __cut =
std::__unguarded_partition_pivot(__first, __last, __comp);
if (__cut <= __nth)
__first = __cut;
else
__last = __cut;
}
std::__insertion_sort(__first, __last, __comp);
}
/// @endcond
// nth_element
// lower_bound moved to stl_algobase.h
@@ -3805,41 +3824,42 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
* @param __first An input iterator.
* @param __n A value convertible to an integer.
* @param __f A unary function object.
* @return `__first+__n`
*
* Applies the function object `__f` to each element in the range
* `[first, first+n)`. `__f` must not modify the order of the sequence.
* If `__f` has a return value it is ignored.
*/
template<typename _InputIterator, typename _Size, typename _Function>
_GLIBCXX20_CONSTEXPR
_InputIterator
for_each_n(_InputIterator __first, _Size __n, _Function __f)
{
auto __n2 = std::__size_to_integer(__n);
using _Cat = typename iterator_traits<_InputIterator>::iterator_category;
if constexpr (is_base_of_v<random_access_iterator_tag, _Cat>)
{
if (__n2 <= 0)
return __first;
- auto __last = __first + __n2;
+ typename iterator_traits<_InputIterator>::difference_type __d = __n2;
+ auto __last = __first + __d;
std::for_each(__first, __last, std::move(__f));
return __last;
}
else
{
while (__n2-->0)
{
__f(*__first);
++__first;
}
return __first;
}
}
#endif // C++17
/**
* @brief Find the first occurrence of a value in a sequence.
* @ingroup non_mutating_algorithms
* @param __first An input iterator.
* @param __last An input iterator.
@@ -4527,110 +4547,119 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
* distribution, so that every possible ordering of the sequence is
* equally likely.
*
* @deprecated
* Since C++17, `std::random_shuffle` is not part of the C++ standard.
* Use `std::shuffle` instead, which was introduced in C++11.
*/
template<typename _RandomAccessIterator>
_GLIBCXX14_DEPRECATED_SUGGEST("std::shuffle")
inline void
random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last)
{
// concept requirements
__glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
_RandomAccessIterator>)
__glibcxx_requires_valid_range(__first, __last);
if (__first == __last)
return;
+ typedef typename iterator_traits<_RandomAccessIterator>::difference_type
+ _Dist;
+
#if RAND_MAX < __INT_MAX__
if (__builtin_expect((__last - __first) >= RAND_MAX / 4, 0))
{
// Use a xorshift implementation seeded by two calls to rand()
// instead of using rand() for all the random numbers needed.
unsigned __xss
= (unsigned)std::rand() ^ ((unsigned)std::rand() << 15);
- for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
+ for (_RandomAccessIterator __i = __first + _Dist(1); __i != __last;
+ ++__i)
{
__xss += !__xss;
__xss ^= __xss << 13;
__xss ^= __xss >> 17;
__xss ^= __xss << 5;
- _RandomAccessIterator __j = __first
- + (__xss % ((__i - __first) + 1));
+ _RandomAccessIterator __j
+ = __first + _Dist(__xss % ((__i - __first) + 1));
if (__i != __j)
std::iter_swap(__i, __j);
}
return;
}
#endif
- for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
+ for (_RandomAccessIterator __i = __first + _Dist(1); __i != __last;
++__i)
{
// XXX rand() % N is not uniformly distributed
- _RandomAccessIterator __j = __first
- + (std::rand() % ((__i - __first) + 1));
+ _RandomAccessIterator __j
+ = __first + _Dist(std::rand() % ((__i - __first) + 1));
if (__i != __j)
std::iter_swap(__i, __j);
}
}
/**
* @brief Shuffle the elements of a sequence using a random number
* generator.
* @ingroup mutating_algorithms
* @param __first A forward iterator.
* @param __last A forward iterator.
* @param __rand The RNG functor or function.
* @return Nothing.
*
* Reorders the elements in the range `[__first, __last)` using `__rand`
* to provide a random distribution. Calling `__rand(N)` for a positive
* integer `N` should return a randomly chosen integer from the
* range `[0, N)`.
*
* @deprecated
* Since C++17, `std::random_shuffle` is not part of the C++ standard.
* Use `std::shuffle` instead, which was introduced in C++11.
*/
template<typename _RandomAccessIterator, typename _RandomNumberGenerator>
_GLIBCXX14_DEPRECATED_SUGGEST("std::shuffle")
void
random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
#if __cplusplus >= 201103L
_RandomNumberGenerator&& __rand)
#else
_RandomNumberGenerator& __rand)
#endif
{
// concept requirements
__glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
_RandomAccessIterator>)
__glibcxx_requires_valid_range(__first, __last);
if (__first == __last)
return;
- for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
+
+ typedef typename iterator_traits<_RandomAccessIterator>::difference_type
+ _Dist;
+
+ for (_RandomAccessIterator __i = __first + _Dist(1); __i != __last;
++__i)
{
- _RandomAccessIterator __j = __first + __rand((__i - __first) + 1);
+ _RandomAccessIterator __j
+ = __first + _Dist(__rand((__i - __first) + 1));
if (__i != __j)
std::iter_swap(__i, __j);
}
}
#endif // HOSTED
#endif // <= C++11 || USE_DEPRECATED
/**
* @brief Move elements for which a predicate is true to the beginning
* of a sequence.
* @ingroup mutating_algorithms
* @param __first A forward iterator.
* @param __last A forward iterator.
* @param __pred A predicate functor.
* @return An iterator `middle` such that `__pred(i)` is true for each
* iterator `i` in the range `[__first, middle)` and false for each `i`
* in the range `[middle, __last)`.
*
* `__pred` must not modify its operand. `partition()` does not preserve
* the relative ordering of elements in each group, use
diff --git a/libstdc++-v3/include/bits/stl_algobase.h
b/libstdc++-v3/include/bits/stl_algobase.h
index b104ec2536a0..820091aee2dc 100644
--- a/libstdc++-v3/include/bits/stl_algobase.h
+++ b/libstdc++-v3/include/bits/stl_algobase.h
@@ -1133,44 +1133,46 @@ _GLIBCXX_END_NAMESPACE_CONTAINER
{
#if __cplusplus >= 201103L
static_assert(is_integral<_Size>{}, "fill_n must pass integral size");
#endif
return __fill_n_a1(__first, __n, __value);
}
template<typename _OutputIterator, typename _Size, typename _Tp>
__attribute__((__always_inline__))
_GLIBCXX20_CONSTEXPR
inline _OutputIterator
__fill_n_a(_OutputIterator __first, _Size __n, const _Tp& __value,
std::random_access_iterator_tag)
{
#if __cplusplus >= 201103L
static_assert(is_integral<_Size>{}, "fill_n must pass integral size");
#endif
if (__n <= 0)
return __first;
- __glibcxx_requires_can_increment(__first, __n);
+ typename iterator_traits<_OutputIterator>::difference_type __d = __n;
+ __glibcxx_requires_can_increment(__first, __d);
- std::__fill_a(__first, __first + __n, __value);
- return __first + __n;
+ _OutputIterator __last = __first + __d;
+ std::__fill_a(__first, __last, __value);
+ return __last;
}
/**
* @brief Fills the range [first,first+n) with copies of value.
* @ingroup mutating_algorithms
* @param __first An output iterator.
* @param __n The count of copies to perform.
* @param __value A reference-to-const of arbitrary type.
* @return The iterator at first+n.
*
* This function fills a range with copies of the same value. For char
* types filling contiguous areas of memory, this becomes an inline call
* to @c memset or @c wmemset.
*
* If @p __n is negative, the function does nothing.
*/
// _GLIBCXX_RESOLVE_LIB_DEFECTS
// DR 865. More algorithms that throw away information
// DR 426. search_n(), fill_n(), and generate_n() with negative n
template<typename _OI, typename _Size, typename _Tp>
@@ -1293,45 +1295,45 @@ _GLIBCXX_END_NAMESPACE_CONTAINER
static _II1
__newlast1(_II1, _II1 __last1, _II2, _II2)
{ return __last1; }
template<typename _II>
_GLIBCXX20_CONSTEXPR
static bool
__cnd2(_II __first, _II __last)
{ return __first != __last; }
};
template<>
struct __lc_rai<random_access_iterator_tag, random_access_iterator_tag>
{
template<typename _RAI1, typename _RAI2>
_GLIBCXX20_CONSTEXPR
static _RAI1
__newlast1(_RAI1 __first1, _RAI1 __last1,
_RAI2 __first2, _RAI2 __last2)
{
- const typename iterator_traits<_RAI1>::difference_type
- __diff1 = __last1 - __first1;
- const typename iterator_traits<_RAI2>::difference_type
- __diff2 = __last2 - __first2;
- return __diff2 < __diff1 ? __first1 + __diff2 : __last1;
+ typedef typename iterator_traits<_RAI1>::difference_type _Diff1;
+ typedef typename iterator_traits<_RAI2>::difference_type _Diff2;
+ const _Diff1 __diff1 = __last1 - __first1;
+ const _Diff2 __diff2 = __last2 - __first2;
+ return __diff2 < __diff1 ? __first1 + _Diff1(__diff2) : __last1;
}
template<typename _RAI>
static _GLIBCXX20_CONSTEXPR bool
__cnd2(_RAI, _RAI)
{ return true; }
};
template<typename _II1, typename _II2, typename _Compare>
_GLIBCXX20_CONSTEXPR
bool
__lexicographical_compare_impl(_II1 __first1, _II1 __last1,
_II2 __first2, _II2 __last2,
_Compare __comp)
{
typedef typename iterator_traits<_II1>::iterator_category _Category1;
typedef typename iterator_traits<_II2>::iterator_category _Category2;
typedef std::__lc_rai<_Category1, _Category2> __rai_type;
__last1 = __rai_type::__newlast1(__first1, __last1, __first2, __last2);
diff --git a/libstdc++-v3/include/bits/stl_heap.h
b/libstdc++-v3/include/bits/stl_heap.h
index 028ac83eeb70..0e9c94c6865b 100644
--- a/libstdc++-v3/include/bits/stl_heap.h
+++ b/libstdc++-v3/include/bits/stl_heap.h
@@ -59,71 +59,79 @@
#include <bits/move.h>
#include <bits/predefined_ops.h>
#include <bits/stl_iterator_base_funcs.h>
namespace std _GLIBCXX_VISIBILITY(default)
{
_GLIBCXX_BEGIN_NAMESPACE_VERSION
/**
* @defgroup heap_algorithms Heap
* @ingroup sorting_algorithms
*/
template<typename _RandomAccessIterator, typename _Distance,
typename _Compare>
_GLIBCXX20_CONSTEXPR
_Distance
__is_heap_until(_RandomAccessIterator __first, _Distance __n,
_Compare& __comp)
{
+#if __cplusplus >= 201103L
+ using _IterTraits = iterator_traits<_RandomAccessIterator>;
+ static_assert(is_same<typename _IterTraits::difference_type,
+ _Distance>::value,
+ "Argument 'n' must be the iterator's difference type");
+#endif
_Distance __parent = 0;
for (_Distance __child = 1; __child < __n; ++__child)
{
if (__comp(__first + __parent, __first + __child))
return __child;
if ((__child & 1) == 0)
++__parent;
}
return __n;
}
// __is_heap, a predicate testing whether or not a range is a heap.
// This function is an extension, not part of the C++ standard.
template<typename _RandomAccessIterator, typename _Distance>
_GLIBCXX20_CONSTEXPR
inline bool
__is_heap(_RandomAccessIterator __first, _Distance __n)
{
+ typename iterator_traits<_RandomAccessIterator>::difference_type
__d(__n);
__gnu_cxx::__ops::_Iter_less_iter __comp;
- return std::__is_heap_until(__first, __n, __comp) == __n;
+ return std::__is_heap_until(__first, __d, __comp) == __n;
}
template<typename _RandomAccessIterator, typename _Compare,
typename _Distance>
_GLIBCXX20_CONSTEXPR
inline bool
__is_heap(_RandomAccessIterator __first, _Compare __comp, _Distance __n)
{
+ typename iterator_traits<_RandomAccessIterator>::difference_type
__d(__n);
typedef __decltype(__comp) _Cmp;
__gnu_cxx::__ops::_Iter_comp_iter<_Cmp> __cmp(_GLIBCXX_MOVE(__comp));
- return std::__is_heap_until(__first, __n, __cmp) == __n;
+ return std::__is_heap_until(__first, __d, __cmp) == __n;
}
template<typename _RandomAccessIterator>
_GLIBCXX20_CONSTEXPR
inline bool
__is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
{ return std::__is_heap(__first, std::distance(__first, __last)); }
template<typename _RandomAccessIterator, typename _Compare>
_GLIBCXX20_CONSTEXPR
inline bool
__is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
_Compare __comp)
{
return std::__is_heap(__first, _GLIBCXX_MOVE(__comp),
std::distance(__first, __last));
}
// Heap-manipulation functions: push_heap, pop_heap, make_heap, sort_heap,
// + is_heap and is_heap_until in C++0x.
@@ -158,78 +166,78 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
*/
template<typename _RandomAccessIterator>
_GLIBCXX20_CONSTEXPR
inline void
push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
{
typedef typename iterator_traits<_RandomAccessIterator>::value_type
_ValueType;
typedef typename iterator_traits<_RandomAccessIterator>::difference_type
_DistanceType;
// concept requirements
__glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
_RandomAccessIterator>)
__glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
__glibcxx_requires_valid_range(__first, __last);
__glibcxx_requires_irreflexive(__first, __last);
__glibcxx_requires_heap(__first, __last - 1);
__gnu_cxx::__ops::_Iter_less_val __comp;
- _ValueType __value = _GLIBCXX_MOVE(*(__last - 1));
+ _ValueType __value = _GLIBCXX_MOVE(*(__last - _DistanceType(1)));
std::__push_heap(__first, _DistanceType((__last - __first) - 1),
_DistanceType(0), _GLIBCXX_MOVE(__value), __comp);
}
/**
* @brief Push an element onto a heap using comparison functor.
* @param __first Start of heap.
* @param __last End of heap + element.
* @param __comp Comparison functor.
* @ingroup heap_algorithms
*
* This operation pushes the element at __last-1 onto the valid
* heap over the range [__first,__last-1). After completion,
* [__first,__last) is a valid heap. Compare operations are
* performed using comp.
*/
template<typename _RandomAccessIterator, typename _Compare>
_GLIBCXX20_CONSTEXPR
inline void
push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
_Compare __comp)
{
typedef typename iterator_traits<_RandomAccessIterator>::value_type
_ValueType;
typedef typename iterator_traits<_RandomAccessIterator>::difference_type
_DistanceType;
// concept requirements
__glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
_RandomAccessIterator>)
__glibcxx_requires_valid_range(__first, __last);
__glibcxx_requires_irreflexive_pred(__first, __last, __comp);
- __glibcxx_requires_heap_pred(__first, __last - 1, __comp);
+ __glibcxx_requires_heap_pred(__first, __last - _DistanceType(1), __comp);
__decltype(__gnu_cxx::__ops::__iter_comp_val(_GLIBCXX_MOVE(__comp)))
__cmp(_GLIBCXX_MOVE(__comp));
- _ValueType __value = _GLIBCXX_MOVE(*(__last - 1));
+ _ValueType __value = _GLIBCXX_MOVE(*(__last - _DistanceType(1)));
std::__push_heap(__first, _DistanceType((__last - __first) - 1),
_DistanceType(0), _GLIBCXX_MOVE(__value), __cmp);
}
template<typename _RandomAccessIterator, typename _Distance,
typename _Tp, typename _Compare>
_GLIBCXX20_CONSTEXPR
void
__adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
_Distance __len, _Tp __value, _Compare __comp)
{
const _Distance __topIndex = __holeIndex;
_Distance __secondChild = __holeIndex;
while (__secondChild < (__len - 1) / 2)
{
__secondChild = 2 * (__secondChild + 1);
if (__comp(__first + __secondChild,
__first + (__secondChild - 1)))
__secondChild--;
*(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __secondChild));
diff --git a/libstdc++-v3/include/std/functional
b/libstdc++-v3/include/std/functional
index bf40995659d1..f86030d4ebf0 100644
--- a/libstdc++-v3/include/std/functional
+++ b/libstdc++-v3/include/std/functional
@@ -1328,38 +1328,38 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
// to give consistent results for lookup in the map.
static_assert(is_same_v<iter_value_t<_RAIter>,
iter_value_t<_RandomAccessIterator2>>);
#endif
auto __patlen = _M_pat_end - _M_pat;
if (__patlen == 0)
return std::make_pair(__first, __first);
const auto& __pred = this->_M_pred();
__diff_type __i = __patlen - 1;
auto __stringlen = __last - __first;
while (__i < __stringlen)
{
__diff_type __j = __patlen - 1;
while (__j >= 0 && __pred(__first[__i], _M_pat[__j]))
{
--__i;
--__j;
}
if (__j < 0)
{
- const auto __match = __first + __i + 1;
+ const auto __match = __first + __diff_type(__i + 1);
return std::make_pair(__match, __match + __patlen);
}
__i += std::max(_M_bad_char_shift(__first[__i]),
_M_good_suffix[__j]);
}
return std::make_pair(__last, __last);
}
#endif // __cpp_lib_boyer_moore_searcher
#endif // C++17
#endif // C++14
#endif // C++11
_GLIBCXX_END_NAMESPACE_VERSION
} // namespace std
#endif // _GLIBCXX_FUNCTIONAL
diff --git a/libstdc++-v3/testsuite/24_iterators/range_operations/advance.cc
b/libstdc++-v3/testsuite/24_iterators/range_operations/advance.cc
index 2f48181fb675..8229b1ee6c16 100644
--- a/libstdc++-v3/testsuite/24_iterators/range_operations/advance.cc
+++ b/libstdc++-v3/testsuite/24_iterators/range_operations/advance.cc
@@ -25,41 +25,41 @@ using __gnu_test::test_range;
using __gnu_test::random_access_iterator_wrapper;
using __gnu_test::bidirectional_iterator_wrapper;
using __gnu_test::forward_iterator_wrapper;
using __gnu_test::input_iterator_wrapper;
using __gnu_test::output_iterator_wrapper;
void
test01()
{
int a[2] = { };
test_range<int, random_access_iterator_wrapper> r(a);
auto iter = r.begin();
std::ranges::advance(iter, 1);
VERIFY( iter != r.begin() );
VERIFY( iter != r.end() );
std::ranges::advance(iter, 1);
VERIFY( iter == r.end() );
std::ranges::advance(iter, -2);
VERIFY( iter == r.begin() );
- std::ranges::advance(iter, r.begin() + 1);
+ std::ranges::advance(iter, std::ranges::next(r.begin()));
VERIFY( iter != r.begin() );
VERIFY( iter != r.end() );
std::ranges::advance(iter, r.begin());
VERIFY( iter == r.begin() );
auto diff = std::ranges::advance(iter, 99, r.end());
VERIFY( iter == r.end() );
VERIFY( diff == 97 );
diff = std::ranges::advance(iter, -222, r.begin());
VERIFY( iter == r.begin() );
VERIFY( diff == -220 );
}
void
test02()
{
int a[2] = { };
test_range<int, bidirectional_iterator_wrapper> r(a);
auto iter = r.begin();
std::ranges::advance(iter, 1);
diff --git a/libstdc++-v3/testsuite/25_algorithms/fill_n/diff_type.cc
b/libstdc++-v3/testsuite/25_algorithms/fill_n/diff_type.cc
new file mode 100644
index 000000000000..7265d396217d
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/fill_n/diff_type.cc
@@ -0,0 +1,13 @@
+// { dg-do compile { target c++11 } }
+
+#include <algorithm>
+#include <testsuite_iterators.h>
+
+void
+test_pr121890()
+{
+ // algorithms do not use iterator's difference_type for arithmetic
+ int a[1];
+ __gnu_test::random_access_container<int> c(a);
+ std::fill_n(c.begin(), 1U, 0);
+}
diff --git a/libstdc++-v3/testsuite/25_algorithms/for_each/diff_type.cc
b/libstdc++-v3/testsuite/25_algorithms/for_each/diff_type.cc
new file mode 100644
index 000000000000..d78ba192fa8f
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/for_each/diff_type.cc
@@ -0,0 +1,13 @@
+// { dg-do compile { target c++17 } }
+
+#include <algorithm>
+#include <testsuite_iterators.h>
+
+void
+test_pr121890()
+{
+ // algorithms do not use iterator's difference_type for arithmetic
+ int a[1];
+ __gnu_test::random_access_container<int> c(a);
+ std::for_each_n(c.begin(), 1U, [](int){});
+}
diff --git a/libstdc++-v3/testsuite/25_algorithms/heap/constrained.cc
b/libstdc++-v3/testsuite/25_algorithms/heap/constrained.cc
index 5486c8552d03..2f818e2b2870 100644
--- a/libstdc++-v3/testsuite/25_algorithms/heap/constrained.cc
+++ b/libstdc++-v3/testsuite/25_algorithms/heap/constrained.cc
@@ -36,61 +36,61 @@ test01()
{
int x[50];
auto pred = std::greater{};
auto proj = [] (int a) { return -a; };
for (int i = 0; i < 50; i++)
{
std::iota(x, x+50, 1);
container<int, random_access_iterator_wrapper> rx(x);
std::ranlux48_base g(i);
ranges::shuffle(rx, g);
auto iter = ranges::make_heap(rx, pred, proj);
VERIFY( iter == rx.end() );
VERIFY( ranges::is_heap(rx, pred, proj) );
VERIFY( ranges::is_heap_until(rx, pred, proj) == rx.end() );
iter = ranges::pop_heap(rx, pred, proj);
VERIFY( iter == rx.end() );
- VERIFY( *(iter-1) == 50 );
- VERIFY( ranges::is_heap_until(rx, pred, proj) == iter-1 );
+ VERIFY( *ranges::prev(iter) == 50 );
+ VERIFY( ranges::is_heap_until(rx, pred, proj) == ranges::prev(iter) );
- iter = ranges::pop_heap(rx.begin(), iter-1, pred, proj);
- VERIFY( iter+1 == rx.end() );
- VERIFY( *(iter-1) == 49 );
- VERIFY( ranges::is_heap_until(rx, pred, proj) == iter-1 );
+ iter = ranges::pop_heap(rx.begin(), ranges::prev(iter), pred, proj);
+ VERIFY( ranges::next(iter) == rx.end() );
+ VERIFY( *ranges::prev(iter) == 49 );
+ VERIFY( ranges::is_heap_until(rx, pred, proj) == ranges::prev(iter) );
- *(iter-1) = i;
+ *ranges::prev(iter) = i;
iter = ranges::push_heap(rx.begin(), iter, pred, proj);
- VERIFY( iter+1 == rx.end() );
+ VERIFY( ranges::next(iter) == rx.end() );
VERIFY( ranges::is_heap_until(rx, pred, proj) == iter );
*iter = 2*i;
iter = ranges::push_heap(rx.begin(), rx.end(), pred, proj);
VERIFY( iter == rx.end() );
VERIFY( ranges::is_heap_until(rx, pred, proj) == iter );
- *(rx.begin()+1) *= -1;
+ *ranges::next(rx.begin()) *= -1;
VERIFY( !ranges::is_heap(rx, pred, proj) );
- *(rx.begin()+1) *= -1;
+ *ranges::next(rx.begin()) *= -1;
VERIFY( ranges::is_heap(rx, pred, proj) );
iter = ranges::sort_heap(rx, pred, proj);
VERIFY( iter == rx.end() );
VERIFY( ranges::is_sorted(rx, pred, proj) );
}
}
constexpr bool
test02()
{
bool ok = true;
int x[] = {1,2,3,4,5};
ranges::make_heap(x);
ranges::pop_heap(x);
x[4] = 7;
ranges::push_heap(x);
ok &= ranges::is_heap(x);
ok &= ranges::is_heap_until(x) == x+5;
ranges::sort_heap(x);
diff --git
a/libstdc++-v3/testsuite/25_algorithms/lexicographical_compare/diff_type.cc
b/libstdc++-v3/testsuite/25_algorithms/lexicographical_compare/diff_type.cc
new file mode 100644
index 000000000000..b790197715b6
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/lexicographical_compare/diff_type.cc
@@ -0,0 +1,57 @@
+// { dg-do compile { target c++11 } }
+
+#include <algorithm>
+#include <testsuite_iterators.h>
+
+struct Iter
+{
+ using value_type = int;
+ using difference_type = short;
+ using iterator_category = std::random_access_iterator_tag;
+ using pointer = const value_type*;
+ using reference = const value_type&;
+
+ Iter() : p(nullptr) { }
+ explicit Iter(pointer p) : p(p) { }
+ reference operator*() const { return *p; }
+ pointer operator->() const { return p; }
+ reference operator[](difference_type n) const { return p[n]; }
+ Iter& operator++() { ++p; return *this; }
+ Iter& operator--() { --p; return *this; }
+ Iter operator++(int) { return Iter(p++); }
+ Iter operator--(int) { return Iter(p--); }
+ Iter& operator+=(difference_type n) { p += n; return *this; }
+ Iter& operator-=(difference_type n) { p -= n; return *this; }
+
+ friend Iter operator+(Iter i, difference_type n) { return i += n; }
+ friend Iter operator+(difference_type n, Iter i) { return i += n; }
+ friend Iter operator-(Iter i, difference_type n) { return i -= n; }
+ friend difference_type operator-(Iter i, Iter j) { return i.p - j.p; }
+
+ template<typename D> void operator[](D) const = delete;
+ template<typename D> void operator+=(D) = delete;
+ template<typename D> void operator-=(D) = delete;
+ template<typename D> friend void operator+(Iter, difference_type) = delete;
+ template<typename D> friend void operator+(difference_type, Iter) = delete;
+ template<typename D> friend void operator-(Iter, difference_type) = delete;
+
+ friend bool operator==(Iter i, Iter j) { return i.p == j.p; }
+ friend bool operator!=(Iter i, Iter j) { return i.p != j.p; }
+ friend bool operator<(Iter i, Iter j) { return i.p < j.p; }
+ friend bool operator<=(Iter i, Iter j) { return i.p <= j.p; }
+ friend bool operator>(Iter i, Iter j) { return i.p > j.p; }
+ friend bool operator>=(Iter i, Iter j) { return i.p >= j.p; }
+
+private:
+ pointer p;
+};
+
+void
+test_pr121890()
+{
+ // algorithms do not use iterator's difference_type for arithmetic
+ int a[1] = { };
+ __gnu_test::random_access_container<int> c(a);
+ (void) std::lexicographical_compare(c.begin(), c.end(), Iter(a), Iter(a+1));
+ (void) std::lexicographical_compare(Iter(a), Iter(a+1), c.begin(), c.end());
+}
diff --git a/libstdc++-v3/testsuite/25_algorithms/nth_element/58800.cc
b/libstdc++-v3/testsuite/25_algorithms/nth_element/58800.cc
index 3989ee0bbb50..ff86c63614f5 100644
--- a/libstdc++-v3/testsuite/25_algorithms/nth_element/58800.cc
+++ b/libstdc++-v3/testsuite/25_algorithms/nth_element/58800.cc
@@ -26,28 +26,28 @@
using __gnu_test::test_container;
using __gnu_test::random_access_iterator_wrapper;
typedef test_container<int, random_access_iterator_wrapper> Container;
void test01()
{
std::vector<int> v = {
207089,
202585,
180067,
157549,
211592,
216096,
207089
};
Container con(v.data(), v.data() + 7);
- std::nth_element(con.begin(), con.begin() + 3, con.end());
+ std::nth_element(con.begin(), std::next(con.begin(), 3), con.end());
}
int main()
{
test01();
return 0;
}
diff --git a/libstdc++-v3/testsuite/25_algorithms/nth_element/constrained.cc
b/libstdc++-v3/testsuite/25_algorithms/nth_element/constrained.cc
index 8cb1625dd4d5..8d3a057e93dc 100644
--- a/libstdc++-v3/testsuite/25_algorithms/nth_element/constrained.cc
+++ b/libstdc++-v3/testsuite/25_algorithms/nth_element/constrained.cc
@@ -21,41 +21,41 @@
#include <algorithm>
#include <random>
#include <ranges>
#include <testsuite_hooks.h>
#include <testsuite_iterators.h>
using __gnu_test::test_container;
using __gnu_test::test_range;
using __gnu_test::random_access_iterator_wrapper;
namespace ranges = std::ranges;
void
test01()
{
int x[50];
std::iota(x, x+50, 0);
auto pred = std::greater{};
auto proj = [] (int a) { return -a; };
- for (int i = 0; i < 50; i++)
+ for (std::ptrdiff_t i = 0; i < 50; i++)
{
test_range<int, random_access_iterator_wrapper> rx(x);
std::ranlux48_base g(i);
ranges::shuffle(rx, g);
auto result = ranges::nth_element(rx, rx.begin()+i, pred, proj);
VERIFY( result == rx.end() );
VERIFY( x[i] == i );
for (int j = 0; j < i; j++)
for (int k = i; k < 50; k++)
VERIFY( !pred(proj(x[k]), proj(x[j])) );
result = ranges::nth_element(rx, rx.begin()+i, pred);
VERIFY( result == rx.end() );
VERIFY( x[i] == 49-i );
for (int j = 0; j < i; j++)
for (int k = i; k < 50; k++)
VERIFY( !pred(x[k], x[j]) );
}
}
diff --git a/libstdc++-v3/testsuite/25_algorithms/nth_element/diff_type.cc
b/libstdc++-v3/testsuite/25_algorithms/nth_element/diff_type.cc
new file mode 100644
index 000000000000..4cc9ca92698a
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/nth_element/diff_type.cc
@@ -0,0 +1,13 @@
+// { dg-do compile { target c++11 } }
+
+#include <algorithm>
+#include <testsuite_iterators.h>
+
+void
+test_pr121890()
+{
+ // algorithms do not use iterator's difference_type for arithmetic
+ int a[1] = { };
+ __gnu_test::random_access_container<int> c(a);
+ std::nth_element(c.begin(), c.begin(), c.end());
+}
diff --git a/libstdc++-v3/testsuite/25_algorithms/nth_element/random_test.cc
b/libstdc++-v3/testsuite/25_algorithms/nth_element/random_test.cc
index 2e9d4b3b6e1e..9eaef61c1690 100644
--- a/libstdc++-v3/testsuite/25_algorithms/nth_element/random_test.cc
+++ b/libstdc++-v3/testsuite/25_algorithms/nth_element/random_test.cc
@@ -20,42 +20,42 @@
// { dg-require-cstdint "" }
// 25.4.2 [lib.alg.nth.element]
#include <algorithm>
#include <random>
#include <testsuite_hooks.h>
#include <testsuite_iterators.h>
#include <testsuite_containergen.h>
using __gnu_test::test_container;
using __gnu_test::random_access_iterator_wrapper;
typedef test_container<int, random_access_iterator_wrapper> Container;
struct testNthElement
{
template<typename Container, typename RandomGen>
void operator()(Container con, RandomGen& rg)
{
- const int size = con.end() - con.begin();
+ const auto size = con.end() - con.begin();
auto dist = std::uniform_int_distribution<>(0, size);
- const int element = dist(rg);
+ const decltype(size) element = dist(rg);
std::nth_element(con.begin(), con.begin() + element, con.end());
if (element < size)
{
for (int i = 0; i < element; ++i)
VERIFY( con.val(i) <= con.val(element) );
for (int i = element + 1; i < size; ++i)
VERIFY( con.val(i) >= con.val(element) );
}
}
};
int
main()
{
__gnu_test::test_containers<Container>(testNthElement());
}
diff --git
a/libstdc++-v3/testsuite/25_algorithms/partial_sort/check_compare_by_value.cc
b/libstdc++-v3/testsuite/25_algorithms/partial_sort/check_compare_by_value.cc
index 05f4f1cbdb55..e1ba840a5a3c 100644
---
a/libstdc++-v3/testsuite/25_algorithms/partial_sort/check_compare_by_value.cc
+++
b/libstdc++-v3/testsuite/25_algorithms/partial_sort/check_compare_by_value.cc
@@ -26,57 +26,57 @@
#undef _GLIBCXX_PARALLEL
#include <algorithm>
#include <testsuite_hooks.h>
#include <testsuite_iterators.h>
#include <testsuite_rvalref.h>
using __gnu_test::test_container;
using __gnu_test::random_access_iterator_wrapper;
typedef __gnu_test::rvalstruct_compare_by_value V;
typedef test_container<V, random_access_iterator_wrapper> Container;
void
test01()
{
V s1[] = { 10, 20, 1, 11, 2, 12, 3, 13, 4, 14, 5, 15, 6, 16, 7,
17, 8, 18, 9, 19 };
const int N = sizeof(s1) / sizeof(V);
Container con(s1, s1 + N);
- std::partial_sort(con.begin(), con.begin() + 10, con.end());
+ std::partial_sort(con.begin(), std::next(con.begin(), 10), con.end());
VERIFY( s1[0].ok );
for(int i = 1; i < 10; ++i)
VERIFY( s1[i].val > s1[i - 1].val && s1[i].ok );
for(int i = 10; i < N; ++i)
VERIFY( s1[i].val > s1[9].val && s1[i].ok );
}
void
test02()
{
V s1[] = { 10, 20, 1, 11, 2, 12, 3, 13, 4, 14, 5, 15, 6, 16, 7,
17, 8, 18, 9, 19 };
const int N = sizeof(s1) / sizeof(V);
Container con(s1, s1 + N);
- std::partial_sort(con.begin(), con.begin() + 10, con.end(),
+ std::partial_sort(con.begin(), std::next(con.begin(), 10), con.end(),
__gnu_test::order);
VERIFY( s1[0].ok );
for(int i = 1; i < 10; ++i)
VERIFY( s1[i].val > s1[i - 1].val && s1[i].ok );
for(int i = 10; i < N; ++i)
VERIFY( s1[i].val > s1[9].val && s1[i].ok );
}
void
test03()
{
V vvs[] = { 2, 0 };
std::partial_sort(vvs, vvs + 2, vvs + 2);
VERIFY( vvs[0].ok && vvs[0].val == 0 );
VERIFY( vvs[1].ok && vvs[1].val == 2 );
}
int
main()
{
diff --git a/libstdc++-v3/testsuite/25_algorithms/partial_sort/constrained.cc
b/libstdc++-v3/testsuite/25_algorithms/partial_sort/constrained.cc
index 032ffe75d890..554a8d76a4b8 100644
--- a/libstdc++-v3/testsuite/25_algorithms/partial_sort/constrained.cc
+++ b/libstdc++-v3/testsuite/25_algorithms/partial_sort/constrained.cc
@@ -30,41 +30,42 @@ using __gnu_test::random_access_iterator_wrapper;
namespace ranges = std::ranges;
void
test01()
{
for (unsigned size = 0; size < 50; ++size)
{
std::vector<int> vref(size);
std::iota(vref.begin(), vref.end(), 0);
std::vector<int> v1(vref), v2(vref);
test_container<int, random_access_iterator_wrapper> c
= {v1.data(), v1.data() + size};
test_range<int, random_access_iterator_wrapper> r
= {v2.data(), v2.data() + size};
std::ranlux48_base g1(size), g2(size + 1);
ranges::shuffle(c, g1);
ranges::shuffle(ranges::begin(r), ranges::end(r), g2);
- for (unsigned middle = 0; middle < std::min(size, 10U); ++middle)
+ for (std::ptrdiff_t middle = 0, end = std::min(size, 10U);
+ middle < end; ++middle)
{
auto res1 = ranges::partial_sort(c.begin(), c.begin()+middle, c.end(),
{}, std::negate<>{});
VERIFY( res1 == c.end() );
auto res2 = ranges::partial_sort(r,
ranges::begin(r)+middle,
ranges::greater{});
VERIFY( res2 == ranges::end(r) );
VERIFY( ranges::equal(c.begin(), c.begin()+middle,
r.begin(), r.begin()+middle) );
VERIFY( ranges::equal(c.begin(), c.begin()+middle,
vref.rbegin(), vref.rbegin()+middle) );
}
}
}
constexpr bool
test02()
diff --git a/libstdc++-v3/testsuite/25_algorithms/partial_sort/random_test.cc
b/libstdc++-v3/testsuite/25_algorithms/partial_sort/random_test.cc
index 89eb99266608..4e690008e74a 100644
--- a/libstdc++-v3/testsuite/25_algorithms/partial_sort/random_test.cc
+++ b/libstdc++-v3/testsuite/25_algorithms/partial_sort/random_test.cc
@@ -20,41 +20,41 @@
// { dg-require-cstdint "" }
// 25.4.1.3 [lib.alg.partial.sort]
#include <algorithm>
#include <random>
#include <testsuite_hooks.h>
#include <testsuite_iterators.h>
#include <testsuite_containergen.h>
using __gnu_test::test_container;
using __gnu_test::random_access_iterator_wrapper;
typedef test_container<int, random_access_iterator_wrapper> Container;
struct testPartialSort
{
template<typename Container, typename RandomGen>
void operator()(Container con, RandomGen& rg)
{
- const int size = con.end() - con.begin();
+ const auto size = con.end() - con.begin();
auto dist = std::uniform_int_distribution<>(0, size);
- const int element = dist(rg);
+ const decltype(size) element = dist(rg);
std::partial_sort(con.begin(), con.begin() + element, con.end());
VERIFY( std::is_sorted(con.begin(), con.begin() + element) );
if (element > 0)
{
for (int i = element; i < size; ++i)
VERIFY( con.val(element - 1) <= con.val(i) );
}
}
};
int
main()
{
__gnu_test::test_containers<Container>(testPartialSort());
}
diff --git
a/libstdc++-v3/testsuite/25_algorithms/partial_sort_copy/constrained.cc
b/libstdc++-v3/testsuite/25_algorithms/partial_sort_copy/constrained.cc
index a0bd48be638b..38b2dda45199 100644
--- a/libstdc++-v3/testsuite/25_algorithms/partial_sort_copy/constrained.cc
+++ b/libstdc++-v3/testsuite/25_algorithms/partial_sort_copy/constrained.cc
@@ -18,51 +18,51 @@
// { dg-do run { target c++20 } }
// { dg-require-cstdint "" }
#include <algorithm>
#include <random>
#include <vector>
#include <testsuite_hooks.h>
#include <testsuite_iterators.h>
using __gnu_test::test_container;
using __gnu_test::test_range;
using __gnu_test::input_iterator_wrapper;
using __gnu_test::forward_iterator_wrapper;
using __gnu_test::random_access_iterator_wrapper;
namespace ranges = std::ranges;
void
test01()
{
- for (unsigned size = 0; size < 50; ++size)
+ for (std::ptrdiff_t size = 0; size < 50; ++size)
{
std::vector<int> vref(size);
std::iota(vref.begin(), vref.end(), 0);
std::vector<int> v1(vref), v2(vref);
std::ranlux48_base g1(size), g2(size + 1);
ranges::shuffle(v1, g1);
ranges::shuffle(v2, g2);
- for (unsigned middle = 0; middle < 10; ++middle)
+ for (std::ptrdiff_t middle = 0; middle < 10; ++middle)
{
test_container<int, forward_iterator_wrapper> c
= {v1.data(), v1.data() + size};
test_range<int, input_iterator_wrapper> r
= {v2.data(), v2.data() + size};
std::vector<int> o1(middle), o2(middle);
test_range<int, random_access_iterator_wrapper> w1
= {o1.data(), o1.data()+middle};
test_range<int, random_access_iterator_wrapper> w2
= {o2.data(), o2.data()+middle};
auto [in1, out1] = ranges::partial_sort_copy(c.begin(), c.end(),
w1.begin(), w1.end(),
{},
std::negate<>{},
std::negate<>{});
VERIFY( in1 == c.end() );
VERIFY( out1 == w1.begin() + std::min(size, middle) );
diff --git
a/libstdc++-v3/testsuite/25_algorithms/partial_sort_copy/random_test.cc
b/libstdc++-v3/testsuite/25_algorithms/partial_sort_copy/random_test.cc
index 2c0b8bca2bef..be033a240140 100644
--- a/libstdc++-v3/testsuite/25_algorithms/partial_sort_copy/random_test.cc
+++ b/libstdc++-v3/testsuite/25_algorithms/partial_sort_copy/random_test.cc
@@ -21,43 +21,43 @@
// 25.4.1.4 [lib.alg.partial.sort.copy]
#include <algorithm>
#include <random>
#include <vector>
#include <testsuite_hooks.h>
#include <testsuite_iterators.h>
#include <testsuite_containergen.h>
using __gnu_test::test_container;
using __gnu_test::random_access_iterator_wrapper;
typedef test_container<int, random_access_iterator_wrapper> Container;
struct testPartialSortCopy
{
template<typename Container, typename RandomGen>
void operator()(Container con, RandomGen& rg)
{
- const int size = con.end() - con.begin();
+ const auto size = con.end() - con.begin();
auto dist = std::uniform_int_distribution<>(0, size);
- const int element = dist(rg);
+ const decltype(size) element = dist(rg);
std::vector<int> outvec(element + 1); // add +1 to avoid empty issues
Container out(outvec.data(), outvec.data() + element);
std::partial_sort_copy(con.begin(), con.end(),
out.begin(), out.begin() + element);
VERIFY( std::is_sorted(out.begin(), out.begin() + element) );
std::sort(con.begin(), con.end());
for (int i = 0; i < element; ++i)
VERIFY( con.val(i) == out.val(i) );
}
};
int
main()
{
diff --git a/libstdc++-v3/testsuite/25_algorithms/push_heap/diff_type.cc
b/libstdc++-v3/testsuite/25_algorithms/push_heap/diff_type.cc
new file mode 100644
index 000000000000..ab4587e946d0
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/push_heap/diff_type.cc
@@ -0,0 +1,13 @@
+// { dg-do compile { target c++11 } }
+
+#include <algorithm>
+#include <testsuite_iterators.h>
+
+void
+test_pr121890()
+{
+ // algorithms do not use iterator's difference_type for arithmetic
+ int a[1] = { };
+ __gnu_test::random_access_container<int> c(a);
+ std::push_heap(c.begin(), c.end());
+}
diff --git a/libstdc++-v3/testsuite/25_algorithms/rotate/diff_type.cc
b/libstdc++-v3/testsuite/25_algorithms/rotate/diff_type.cc
new file mode 100644
index 000000000000..cbf2958df0fb
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/rotate/diff_type.cc
@@ -0,0 +1,13 @@
+// { dg-do compile { target c++11 } }
+
+#include <algorithm>
+#include <testsuite_iterators.h>
+
+void
+test_pr121890()
+{
+ // algorithms do not use iterator's difference_type for arithmetic
+ int a[1] = { };
+ __gnu_test::random_access_container<int> c(a);
+ std::rotate(c.begin(), c.begin(), c.end());
+}
diff --git a/libstdc++-v3/testsuite/25_algorithms/search_n/diff_type.cc
b/libstdc++-v3/testsuite/25_algorithms/search_n/diff_type.cc
new file mode 100644
index 000000000000..20253e9ca2a6
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/search_n/diff_type.cc
@@ -0,0 +1,13 @@
+// { dg-do compile { target c++11 } }
+
+#include <algorithm>
+#include <testsuite_iterators.h>
+
+void
+test_pr121890()
+{
+ // algorithms do not use iterator's difference_type for arithmetic
+ int a[1] = { };
+ __gnu_test::random_access_container<int> c(a);
+ (void) std::search_n(c.begin(), c.begin(), 1U, 0);
+}
diff --git a/libstdc++-v3/testsuite/25_algorithms/sort/diff_type.cc
b/libstdc++-v3/testsuite/25_algorithms/sort/diff_type.cc
new file mode 100644
index 000000000000..52a83e88ff81
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/sort/diff_type.cc
@@ -0,0 +1,13 @@
+// { dg-do compile { target c++11 } }
+
+#include <algorithm>
+#include <testsuite_iterators.h>
+
+void
+test_pr121890()
+{
+ // algorithms do not use iterator's difference_type for arithmetic
+ int a[1] = { };
+ __gnu_test::random_access_container<int> c(a);
+ std::sort(c.begin(), c.begin());
+}
diff --git a/libstdc++-v3/testsuite/std/ranges/adaptors/drop.cc
b/libstdc++-v3/testsuite/std/ranges/adaptors/drop.cc
index 4583fb0e7130..57db806069ed 100644
--- a/libstdc++-v3/testsuite/std/ranges/adaptors/drop.cc
+++ b/libstdc++-v3/testsuite/std/ranges/adaptors/drop.cc
@@ -226,41 +226,41 @@ test08()
short a[10]{ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
test_range<short, ra_test_wrapper> ra(a);
static_assert( ranges::random_access_range<decltype(ra)> );
ranges::subrange nonsized = {ra.begin(), std::unreachable_sentinel};
using Nonsized = decltype(nonsized);
static_assert( ranges::random_access_range<Nonsized> );
static_assert( ! ranges::sized_range<Nonsized> );
auto v1 = nonsized | views::drop(5);
VERIFY( ra_test_wrapper<short>::increment_count == 0 );
auto b1 = v1.begin();
VERIFY( ra_test_wrapper<short>::increment_count == 5 );
VERIFY( v1.begin() == b1 );
VERIFY( ra_test_wrapper<short>::increment_count == 5 );
VERIFY( *b1 == 5 );
VERIFY( *v1.begin() == 5 );
VERIFY( ra_test_wrapper<short>::increment_count == 5 );
long b[10]{ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
test_range<long, ra_test_wrapper> rb(b);
- ranges::subrange sized = {rb.begin(), rb.begin()+6};
+ ranges::subrange sized = {rb.begin(), ranges::next(rb.begin(), 6)};
using Sized = decltype(sized);
static_assert( ranges::random_access_range<Sized> );
static_assert( ranges::sized_range<Sized> );
auto v2 = sized | views::drop(6);
auto b2 = v2.begin();
VERIFY( ra_test_wrapper<long>::increment_count == 0 );
VERIFY( v2.begin() == b2 );
VERIFY( ra_test_wrapper<long>::increment_count == 0 );
VERIFY( *b2 == 6 );
VERIFY( *v2.begin() == 6 );
VERIFY( ra_test_wrapper<long>::increment_count == 0 );
}
template<auto drop = views::drop>
void
test09()
{
// Verify SFINAE behavior.
extern int x[5];
int* n = 0;
diff --git a/libstdc++-v3/testsuite/util/testsuite_iterators.h
b/libstdc++-v3/testsuite/util/testsuite_iterators.h
index acd412af0f22..5bf2e704e843 100644
--- a/libstdc++-v3/testsuite/util/testsuite_iterators.h
+++ b/libstdc++-v3/testsuite/util/testsuite_iterators.h
@@ -590,78 +590,96 @@ namespace __gnu_test
_GLIBCXX14_CONSTEXPR
random_access_iterator_wrapper
operator-(std::ptrdiff_t n) const
{
random_access_iterator_wrapper<T> tmp = *this;
return tmp -= n;
}
_GLIBCXX14_CONSTEXPR
std::ptrdiff_t
operator-(const random_access_iterator_wrapper<T>& in) const
{
ITERATOR_VERIFY(this->SharedInfo == in.SharedInfo);
return this->ptr - in.ptr;
}
_GLIBCXX14_CONSTEXPR
T& operator[](std::ptrdiff_t n) const
{ return *(*this + n); }
+#if __cplusplus >= 201103L
+ // Ensure that the iterator's difference_type is always used.
+ template<typename D> void operator+=(D) = delete;
+ template<typename D> void operator-=(D) = delete;
+ template<typename D> void operator[](D) const = delete;
+ template<typename D>
+ typename std::enable_if<std::is_integral<D>::value>::type
+ operator-(D) const = delete;
+#endif
+
_GLIBCXX14_CONSTEXPR
bool operator<(const random_access_iterator_wrapper<T>& in) const
{
ITERATOR_VERIFY(this->SharedInfo == in.SharedInfo);
return this->ptr < in.ptr;
}
_GLIBCXX14_CONSTEXPR
bool operator>(const random_access_iterator_wrapper<T>& in) const
{
return in < *this;
}
_GLIBCXX14_CONSTEXPR
bool operator>=(const random_access_iterator_wrapper<T>& in) const
{
return !(*this < in);
}
_GLIBCXX14_CONSTEXPR
bool operator<=(const random_access_iterator_wrapper<T>& in) const
{
return !(*this > in);
}
};
template<typename T>
_GLIBCXX14_CONSTEXPR
random_access_iterator_wrapper<T>
operator+(random_access_iterator_wrapper<T> it, std::ptrdiff_t n)
{ return it += n; }
template<typename T>
_GLIBCXX14_CONSTEXPR
random_access_iterator_wrapper<T>
operator+(std::ptrdiff_t n, random_access_iterator_wrapper<T> it)
{ return it += n; }
+#if __cplusplus >= 201103L
+ // Ensure that the iterator's difference_type is always used.
+ template<typename T, typename D>
+ void operator+(random_access_iterator_wrapper<T>, D) = delete;
+ template<typename T, typename D>
+ void operator+(D, random_access_iterator_wrapper<T>) = delete;
+#endif
+
/**
* @brief A container-type class for holding iterator wrappers
* test_container takes two parameters, a class T and an iterator
* wrapper templated by T (for example forward_iterator_wrapper<T>.
* It takes two pointers representing a range and presents them as
* a container of iterators.
*/
template <class T, template<class TT> class ItType>
struct test_container
{
typename ItType<T>::ContainerType bounds;
_GLIBCXX_CONSTEXPR
test_container(T* _first, T* _last) : bounds(_first, _last)
{ }
template<std::size_t N>
explicit
_GLIBCXX_CONSTEXPR
--
2.51.0
