On Thu, 11 Sept 2025 at 15:31, Patrick Palka wrote:
>
> On Thu, 11 Sep 2025, Jonathan Wakely 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.
> > (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.
> > ---
> >
> > v2: Applied Tomasz's suggestion to use 'p + D(n - 1)' in __rotate
> > instead of 'p + n + D(1)'. Also used local variables to store the
> > results of those expressions, removing duplicate subexpressions.
> >
> > libstdc++-v3/include/bits/ranges_algo.h | 56 +++++++------
> > 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, 306 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..65356fd2dfd0 100644
> > --- a/libstdc++-v3/include/bits/ranges_algo.h
> > +++ b/libstdc++-v3/include/bits/ranges_algo.h
> > @@ -1684,8 +1684,9 @@ namespace ranges
> > if (__k == 1)
> > {
> > auto __t = std::move(*__p);
> > - ranges::move(__p + 1, __p + __n, __p);
> > - *(__p + __n - 1) = std::move(__t);
> > + ranges::move(ranges::next(__p),
> > + ranges::next(__p, __n), __p);
>
> Does __p + __n actually need to be changed? __n seems to have the
> proper integral type:
>
> auto __n = __lasti - __first;
>
> If it's for consistency with the __p + 1 change, I'm fine with that,
> just double checking.
Ah I guess I got carried away and was changing things on auto-pilot.
I agree that __p + __n is fine here.
However, I'll make the corresponding refactoring here that I did to
std::rotate after Tomasz's comments, i.e. introduce local vars __mid
and __end for the results of the p+n-1 and p+n calculations:
auto __mid = ranges::next(__p, __n - 1);
auto __end = ranges::next(__mid);
auto __t = std::move(*__p);
ranges::move(ranges::next(__p), __end, __p);
*__mid = std::move(__t);
N.B. I think the std::move(*p) should be ranges::iter_move(p). I'll do
that in a follow-up patch.
> > + *ranges::next(__p, __n - 1) = std::move(__t);
> > return {std::move(__ret), std::move(__lasti)};
> > }
> > auto __q = __p + __k;
> > @@ -1709,8 +1710,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 __t = std::move(*ranges::next(__p, __n - 1));
> > + ranges::move_backward(__p,
> > + ranges::next(__p, __n - 1),
> > + ranges::next(__p, __n));
>
> Same here
Yep. This one becomes:
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);
Should be ranges::iter_move here too.
