[Bug libstdc++/100795] ranges::sample, ranges::sort etc should not use std::sample, std::sort etc directly

[cvs-commit at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=100795

--- Comment #15 from GCC Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Patrick Palka <ppalka@gcc.gnu.org>:

https://gcc.gnu.org/g:a148b0377805376e33f36bed0e48a401a6dd82c6

commit r16-1740-ga148b0377805376e33f36bed0e48a401a6dd82c6
Author: Patrick Palka <ppalka@redhat.com>
Date:   Fri Jun 27 13:52:56 2025 -0400

    libstdc++: Directly implement ranges::heap algos [PR100795]

    ranges::push_heap, ranges::pop_heap, ranges::make_heap and
    ranges::sort_heap are currently defined in terms of the corresponding
    STL-style algorithms, but this is incorrect because the STL-style
    algorithms rely on the legacy iterator system, and so misbehave when
    passed a narrowly C++20 random access iterator.  The other ranges heap
    algos, ranges::is_heap and ranges::is_heap_until, are implemented
    directly already and have no known issues.

    This patch reimplements these ranges:: algos directly instead, based
    closely on the legacy stl_heap.h implementation, with the following
    changes for compatibility with the C++20 iterator system:

      - handle non-common ranges by computing the corresponding end iterator
      - use ranges::iter_move instead of std::move(*iter)
      - use iter_value_t / iter_difference_t instead of iterator_traits

    Besides these changes, the implementation of these algorithms is
    intended to mirror the stl_heap.h implementations, for ease of
    maintenance and review.

    Note that we don't explicitly pass the projection function throughout,
    instead we just create and pass a composite predicate via __make_comp_proj.

            PR libstdc++/100795

    libstdc++-v3/ChangeLog:

            * include/bits/ranges_algo.h (__detail::__push_heap): New,
            based on the stl_heap.h implementation.
            (__push_heap_fn::operator()): Reimplement in terms of the above.
            (__detail::__adjust_heap): New, based on the stl_heap.h
            implementation.
            (__deatil::__pop_heap): Likewise.
            (__pop_heap_fn::operator()): Reimplement in terms of the above.
            (__make_heap_fn::operator()): Likewise.
            (__sort_heap_fn::operator()): Likewise.
            * testsuite/25_algorithms/heap/constrained.cc (test03): New
            test.

    Reviewed-by: Tomasz KamiÅski <tkaminsk@redhat.com>
    Reviewed-by: Jonathan Wakely <jwakely@redhat.com>