https://gcc.gnu.org/bugzilla/show_bug.cgi?id=121890
--- Comment #3 from GCC Commits <cvs-commit at gcc dot gnu.org> --- The master branch has been updated by Jonathan Wakely <r...@gcc.gnu.org>: https://gcc.gnu.org/g:7b99d184bc9eada80992f7134c6c8e3b0eb0d19d commit r16-3834-g7b99d184bc9eada80992f7134c6c8e3b0eb0d19d Author: Jonathan Wakely <jwak...@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 <ppa...@redhat.com> Reviewed-by: Tomasz KamiÅski <tkami...@redhat.com>
