[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