[PATCH] libstdc++: Fix algorithms to use iterators' difference_type for arithmetic [PR121890]
Patrick Palka
ppalka@redhat.com
Fri Sep 12 17:16:02 GMT 2025
On Fri, 12 Sep 2025, Jonathan Wakely wrote:
> On Thu, 11 Sept 2025 at 22:41, Jonathan Wakely <jwakely@redhat.com> wrote:
> >
> > 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.
>
> I found one more change that's needed for debug mode:
>
> --- a/libstdc++-v3/include/bits/stl_heap.h
> +++ b/libstdc++-v3/include/bits/stl_heap.h
> @@ -180,7 +180,7 @@ _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 - _DistanceType(1)));
>
>
> I'm also removing all but these two of the new tests:
>
> * testsuite/25_algorithms/fill_n/diff_type.cc: New test.
> * testsuite/25_algorithms/lexicographical_compare/diff_type.cc
>
> That's because for the other algos the existing tests already use
> __gnu_test::random_access_iterator_wrapper and so already fail with
> the new deleted operators in that wrapper. So we don't need new tests
> to check things that we're already checking.
>
> For fill_n and lexicographical_compare, the existing tests didn't
> trigger the deleted operators.
LGTM
More information about the Libstdc++
mailing list