[gcc r16-3834] libstdc++: Fix algorithms to use iterators' difference_type for arithmetic [PR121890]
Jonathan Wakely
redi@gcc.gnu.org
Fri Sep 12 20:47:20 GMT 2025
https://gcc.gnu.org/g:7b99d184bc9eada80992f7134c6c8e3b0eb0d19d
commit r16-3834-g7b99d184bc9eada80992f7134c6c8e3b0eb0d19d
Author: Jonathan Wakely <jwakely@redhat.com>
Date: Wed Sep 10 12:00:57 2025 +0100
libstdc++: Fix algorithms to use iterators' difference_type for arithmetic [PR121890]
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/lexicographical_compare/diff_type.cc:
New test.
Reviewed-by: Patrick Palka <ppalka@redhat.com>
Reviewed-by: Tomasz Kamiński <tkaminsk@redhat.com>
Diff:
---
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 | 20 ++++--
libstdc++-v3/include/std/functional | 2 +-
.../24_iterators/range_operations/advance.cc | 2 +-
.../testsuite/25_algorithms/fill_n/diff_type.cc | 13 ++++
.../testsuite/25_algorithms/heap/constrained.cc | 20 +++---
.../lexicographical_compare/diff_type.cc | 57 +++++++++++++++
.../testsuite/25_algorithms/nth_element/58800.cc | 2 +-
.../25_algorithms/nth_element/constrained.cc | 2 +-
.../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 +-
.../25_algorithms/partial_sort_copy/constrained.cc | 4 +-
.../25_algorithms/partial_sort_copy/random_test.cc | 4 +-
libstdc++-v3/testsuite/std/ranges/adaptors/drop.cc | 2 +-
libstdc++-v3/testsuite/util/testsuite_iterators.h | 18 +++++
20 files changed, 230 insertions(+), 91 deletions(-)
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
@@ -1683,9 +1683,11 @@ namespace ranges
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;
@@ -1709,8 +1711,10 @@ namespace ranges
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)};
}
@@ -1970,7 +1974,7 @@ namespace ranges
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
@@ -1979,7 +1983,7 @@ namespace ranges
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,
@@ -1990,11 +1994,11 @@ namespace ranges
{
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;
@@ -2002,9 +2006,11 @@ namespace ranges
__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;
}
@@ -2060,7 +2066,7 @@ namespace ranges
{
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;
}
@@ -2137,8 +2143,9 @@ namespace ranges
{
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;
}
@@ -2356,12 +2363,12 @@ namespace ranges
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
@@ -2383,10 +2390,11 @@ namespace ranges
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
@@ -2416,8 +2424,10 @@ namespace ranges
__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>
@@ -2745,7 +2755,7 @@ namespace ranges
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);
@@ -2812,7 +2822,7 @@ namespace ranges
{
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);
}
@@ -2924,7 +2934,8 @@ namespace ranges
{
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;
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
@@ -900,7 +900,7 @@ namespace ranges
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)
@@ -920,7 +920,7 @@ namespace ranges
{
// 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;
}
}
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
@@ -204,7 +204,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
while (__unary_pred(--__backTrack))
{
if (--__remainder == 0)
- return (__first - __count); // Success
+ return __first - _DistanceType(__count); // Success
}
__remainder = __count + 1 - (__first - __backTrack);
}
@@ -1258,9 +1258,12 @@ _GLIBCXX_BEGIN_INLINE_ABI_NAMESPACE(_V2)
{
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;
@@ -1281,8 +1284,11 @@ _GLIBCXX_BEGIN_INLINE_ABI_NAMESPACE(_V2)
__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;
}
@@ -1770,15 +1776,18 @@ _GLIBCXX_END_INLINE_ABI_NAMESPACE(_V2)
__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
@@ -1812,10 +1821,13 @@ _GLIBCXX_END_INLINE_ABI_NAMESPACE(_V2)
__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
@@ -1851,10 +1863,14 @@ _GLIBCXX_END_INLINE_ABI_NAMESPACE(_V2)
__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>
@@ -1916,11 +1932,14 @@ _GLIBCXX_END_INLINE_ABI_NAMESPACE(_V2)
_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;
@@ -3822,7 +3841,8 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
{
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;
}
@@ -4544,6 +4564,9 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
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))
{
@@ -4551,14 +4574,15 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
// 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);
}
@@ -4566,11 +4590,11 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
}
#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);
}
@@ -4611,9 +4635,14 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
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);
}
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
@@ -1150,10 +1150,12 @@ _GLIBCXX_END_NAMESPACE_CONTAINER
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;
}
/**
@@ -1310,11 +1312,11 @@ _GLIBCXX_END_NAMESPACE_CONTAINER
__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>
diff --git a/libstdc++-v3/include/bits/stl_heap.h b/libstdc++-v3/include/bits/stl_heap.h
index 028ac83eeb70..f2b1e87e42a8 100644
--- a/libstdc++-v3/include/bits/stl_heap.h
+++ b/libstdc++-v3/include/bits/stl_heap.h
@@ -76,6 +76,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
__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)
{
@@ -94,8 +100,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
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,
@@ -104,9 +111,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
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>
@@ -172,10 +180,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
__glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
__glibcxx_requires_valid_range(__first, __last);
__glibcxx_requires_irreflexive(__first, __last);
- __glibcxx_requires_heap(__first, __last - 1);
+ __glibcxx_requires_heap(__first, __last - _DistanceType(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);
}
@@ -208,11 +216,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_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);
}
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
@@ -1345,7 +1345,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
}
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]),
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
@@ -42,7 +42,7 @@ test01()
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());
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/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
@@ -53,17 +53,17 @@ test01()
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;
@@ -71,9 +71,9 @@ test01()
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);
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
@@ -43,7 +43,7 @@ void test01()
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()
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
@@ -38,7 +38,7 @@ test01()
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);
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
@@ -37,9 +37,9 @@ 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());
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
@@ -43,7 +43,7 @@ test01()
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 );
@@ -59,7 +59,7 @@ test02()
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)
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
@@ -47,7 +47,8 @@ test01()
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<>{});
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
@@ -37,9 +37,9 @@ 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());
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
@@ -35,7 +35,7 @@ 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);
@@ -45,7 +45,7 @@ test01()
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};
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
@@ -38,9 +38,9 @@ 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
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
@@ -243,7 +243,7 @@ test08()
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> );
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
@@ -607,6 +607,16 @@ namespace __gnu_test
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
{
@@ -645,6 +655,14 @@ namespace __gnu_test
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
More information about the Libstdc++-cvs
mailing list