On Wed, 11 Jun 2025 at 12:42, Tomasz Kaminski <tkami...@redhat.com> wrote:
>
>
>
> On Tue, Jun 10, 2025 at 3:05 AM Patrick Palka <ppa...@redhat.com> wrote:
>>
>> 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_algo.h implementation, with the following
>> changes for compatibility with the C++20 iterator system:
>>
>> - handle non-common ranges by computing the corresponding end iterator
>> - pass and invoke a projection function as necessary
>> - use std::__invoke when invoking the comparator
>> - 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_algo.h implementations, for ease of
>> maintenance and review.
>>
>> PR libstdc++/100795
>>
>> libstdc++-v3/ChangeLog:
>>
>> * include/bits/ranges_algo.h (__detail::__push_heap): New,
>> based on the stl_algo.h implementation.
>> (__push_heap_fn::operator()): Reimplement in terms of the above.
>> (__detail::__adjust_heap): New, based on the stl_algo.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.
>> ---
>> libstdc++-v3/include/bits/ranges_algo.h | 138 ++++++++++++++++--
>> .../25_algorithms/heap/constrained.cc | 46 ++++++
>> 2 files changed, 168 insertions(+), 16 deletions(-)
>
> LGTM, only requests to pass the predicates by reference to match stl_heap.
That was done by r7-6137-g437f43cc78d460 for PR67085
> I have validated the impl against the stl_heap, and implementations are the
> same modulo described changes.
>>
>>
>> diff --git a/libstdc++-v3/include/bits/ranges_algo.h
>> b/libstdc++-v3/include/bits/ranges_algo.h
>> index a62c3cd3954d..f84e0c42d76a 100644
>> --- a/libstdc++-v3/include/bits/ranges_algo.h
>> +++ b/libstdc++-v3/include/bits/ranges_algo.h
>> @@ -1881,6 +1881,30 @@ namespace ranges
>>
>> inline constexpr __shuffle_fn shuffle{};
>>
>> + namespace __detail
>> + {
>> + template<typename _Iter, typename _Comp, typename _Proj>
>> + constexpr void
>> + __push_heap(_Iter __first,
>> + iter_difference_t<_Iter> __holeIndex,
>> + iter_difference_t<_Iter> __topIndex,
>> + iter_value_t<_Iter> __value,
>> + _Comp __comp, _Proj __proj)
>
> stl_heap implementation does not copy __comp and __proj, and uses
> _Comp& instead. I think I would do that also here.
>>
>> + {
>> + auto __parent = (__holeIndex - 1) / 2;
>> + while (__holeIndex > __topIndex
>> + && std::__invoke(__comp,
>> + std::__invoke(__proj, *(__first + __parent)),
>> + std::__invoke(__proj, __value)))
>> + {
>> + *(__first + __holeIndex) = ranges::iter_move(__first + __parent);
>> + __holeIndex = __parent;
>> + __parent = (__holeIndex - 1) / 2;
>> + }
>> + *(__first + __holeIndex) = std::move(__value);
>> + }
>> + } // namespace __detail
>> +
>> struct __push_heap_fn
>> {
>> template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
>> @@ -1890,10 +1914,16 @@ namespace ranges
>> operator()(_Iter __first, _Sent __last,
>> _Comp __comp = {}, _Proj __proj = {}) const
>> {
>> - auto __lasti = ranges::next(__first, __last);
>> - std::push_heap(__first, __lasti,
>> - __detail::__make_comp_proj(__comp, __proj));
>> - return __lasti;
>> + if constexpr (!same_as<_Iter, _Sent>)
>> + return (*this)(__first, ranges::next(__first, __last),
>> + std::move(__comp), std::move(__proj));
>
>
>> + else
>> + {
>> + __detail::__push_heap(__first, (__last - __first) - 1,
>> + 0, ranges::iter_move(__last - 1),
>> + __comp, __proj);
>> + return __last;
>> + }
>> }
>>
>> template<random_access_range _Range,
>> @@ -1909,6 +1939,50 @@ namespace ranges
>>
>> inline constexpr __push_heap_fn push_heap{};
>>
>> + namespace __detail
>> + {
>> + template<typename _Iter, typename _Comp, typename _Proj>
>> + constexpr void
>> + __adjust_heap(_Iter __first,
>> + iter_difference_t<_Iter> __holeIndex,
>> + iter_difference_t<_Iter> __len,
>> + iter_value_t<_Iter> __value,
>> + _Comp __comp, _Proj __proj)
>
> Same comment about references.
>>
>> + {
>> + auto __topIndex = __holeIndex;
>> + auto __secondChild = __holeIndex;
>> + while (__secondChild < (__len - 1) / 2)
>> + {
>> + __secondChild = 2 * (__secondChild + 1);
>> + if (std::__invoke(__comp,
>> + std::__invoke(__proj, *(__first +
>> __secondChild)),
>> + std::__invoke(__proj, *(__first +
>> (__secondChild - 1)))))
>> + __secondChild--;
>> + *(__first + __holeIndex) = ranges::iter_move(__first +
>> __secondChild);
>> + __holeIndex = __secondChild;
>> + }
>> + if ((__len & 1) == 0 && __secondChild == (__len - 2) / 2)
>> + {
>> + __secondChild = 2 * (__secondChild + 1);
>> + *(__first + __holeIndex) = ranges::iter_move(__first +
>> (__secondChild - 1));
>> + __holeIndex = __secondChild - 1;
>> + }
>> + __detail::__push_heap(__first, __holeIndex, __topIndex,
>> + std::move(__value), __comp, __proj);
>> + }
>> +
>> + template<typename _Iter, typename _Comp, typename _Proj>
>> + constexpr void
>> + __pop_heap(_Iter __first, _Iter __last, _Iter __result,
>> + _Comp __comp, _Proj __proj)
>
> Also here.
>>
>> + {
>> + iter_value_t<_Iter> __value = ranges::iter_move(__result);
>> + *__result = ranges::iter_move(__first);
>> + __detail::__adjust_heap(__first, 0, __last - __first,
>> + std::move(__value), __comp, __proj);
>> + }
>> + } // namespace __detail
>> +
>> struct __pop_heap_fn
>> {
>> template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
>> @@ -1918,10 +1992,15 @@ namespace ranges
>> operator()(_Iter __first, _Sent __last,
>> _Comp __comp = {}, _Proj __proj = {}) const
>> {
>> - auto __lasti = ranges::next(__first, __last);
>> - std::pop_heap(__first, __lasti,
>> - __detail::__make_comp_proj(__comp, __proj));
>> - return __lasti;
>> + if constexpr (!same_as<_Iter, _Sent>)
>> + return (*this)(__first, ranges::next(__first, __last),
>> + std::move(__comp), std::move(__proj));
>> + else
>> + {
>> + if (__last - __first > 1)
>> + __detail::__pop_heap(__first, __last - 1, __last - 1, __comp,
>> __proj);
>> + return __last;
>> + }
>> }
>>
>> template<random_access_range _Range,
>> @@ -1946,10 +2025,28 @@ namespace ranges
>> operator()(_Iter __first, _Sent __last,
>> _Comp __comp = {}, _Proj __proj = {}) const
>> {
>> - auto __lasti = ranges::next(__first, __last);
>> - std::make_heap(__first, __lasti,
>> - __detail::__make_comp_proj(__comp, __proj));
>> - return __lasti;
>> + if constexpr (!same_as<_Iter, _Sent>)
>> + return (*this)(__first, ranges::next(__first, __last),
>> + std::move(__comp), std::move(__proj));
>> + else
>> + {
>> + if (__last - __first > 1)
>
> I would prefer early if, matching the stl_heap closer:
> const auto __len = __last - __first;
> if (__len < 2)
> return __last;
>>
>> + {
>> + const auto __len = __last - __first;
>> + auto __parent = (__len - 2) / 2;
>> + while (true)
>> + {
>> + iter_value_t<_Iter> __value = ranges::iter_move(__first
>> + __parent);
>> + __detail::__adjust_heap(__first, __parent, __len,
>> + std::move(__value),
>> + __comp, __proj);
>> + if (__parent == 0)
>> + break;
>> + __parent--;
>> + }
>> + }
>> + return __last;
>> + }
>> }
>>
>> template<random_access_range _Range,
>> @@ -1974,10 +2071,19 @@ namespace ranges
>> operator()(_Iter __first, _Sent __last,
>> _Comp __comp = {}, _Proj __proj = {}) const
>> {
>> - auto __lasti = ranges::next(__first, __last);
>> - std::sort_heap(__first, __lasti,
>> - __detail::__make_comp_proj(__comp, __proj));
>> - return __lasti;
>> + if constexpr (!same_as<_Iter, _Sent>)
>> + return (*this)(__first, ranges::next(__first, __last),
>> + std::move(__comp), std::move(__proj));
>> + else
>> + {
>> + _Iter __ret = __last;
>> + while (__last - __first > 1)
>> + {
>> + --__last;
>> + __detail::__pop_heap(__first, __last, __last, __comp,
>> __proj);
>> + }
>> + return __ret;
>> + }
>> }
>>
>> template<random_access_range _Range,
>> diff --git a/libstdc++-v3/testsuite/25_algorithms/heap/constrained.cc
>> b/libstdc++-v3/testsuite/25_algorithms/heap/constrained.cc
>> index 8037a2db6b80..5486c8552d03 100644
>> --- a/libstdc++-v3/testsuite/25_algorithms/heap/constrained.cc
>> +++ b/libstdc++-v3/testsuite/25_algorithms/heap/constrained.cc
>> @@ -20,6 +20,7 @@
>>
>> #include <algorithm>
>> #include <random>
>> +#include <ranges>
>> #include <testsuite_hooks.h>
>> #include <testsuite_iterators.h>
>>
>> @@ -97,10 +98,55 @@ test02()
>> return ok;
>> }
>>
>> +constexpr bool
>> +test03()
>> +{
>> + // PR libstdc++/100795 - ranges::heap algos should not use std::heap
>> directly
>> +#if __SIZEOF_INT128__
>> + auto v = std::views::iota(__int128(0), __int128(20));
>> +#else
>> + auto v = std::views::iota(0ll, 20ll);
>> +#endif
>> +
>> + int storage[20] = {2,5,4,3,1,6,7,9,10,8,11,14,12,13,15,16,18,0,19,17};
>> + auto w = v | std::views::transform([&](auto i) -> int& { return
>> storage[i]; });
>> + using type = decltype(w);
>> + using cat =
>> std::iterator_traits<std::ranges::iterator_t<type>>::iterator_category;
>> + static_assert( std::same_as<cat, std::output_iterator_tag> );
>> + static_assert( std::ranges::random_access_range<type> );
>> +
>> + for (int i = 1; i < 20; i++)
>> + ranges::push_heap(w.begin(), w.begin() + i);
>> + ranges::sort_heap(w);
>> + VERIFY( ranges::equal(w, v) );
>> + ranges::make_heap(w);
>> + auto it = ranges::pop_heap(w);
>> + VERIFY( it[-1] == 19 );
>> +
>> + for (int i = 1; i < 20; i++)
>> + ranges::push_heap(w.begin(), w.begin() + i, std::ranges::greater{});
>> + ranges::sort_heap(w, std::ranges::greater{});
>> + VERIFY( ranges::equal(w, v | std::views::reverse) );
>> + ranges::make_heap(w, std::ranges::greater{});
>> + it = ranges::pop_heap(w, std::ranges::greater{});
>> + VERIFY( it[-1] == 0 );
>> +
>> + for (int i = 1; i < 20; i++)
>> + ranges::push_heap(w.begin(), w.begin() + i, std::ranges::greater{},
>> std::negate{});
>> + ranges::sort_heap(w, std::ranges::greater{}, std::negate{});
>> + VERIFY( ranges::equal(w, v) );
>> + ranges::make_heap(w, std::ranges::greater{}, std::negate{});
>> + it = ranges::pop_heap(w, std::ranges::greater{}, std::negate{});
>> + VERIFY( it[-1] == 19 );
>> +
>> + return true;
>> +}
>> +
>> int
>> main()
>> {
>> test01<test_range>();
>> test01<test_container>();
>> static_assert(test02());
>> + static_assert(test03());
>> }
>> --
>> 2.50.0.rc1.89.g8db3019401
>>
