On Thu, Jun 12, 2025 at 6:53 PM Patrick Palka <ppa...@redhat.com> wrote:
> Changes in v4: > * Don't pass a projection function throughout the helpers, instead > create a pass a composite predicate via __make_comp_proj. > LGTM. > > -- >8 -- > > 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 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_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. > --- > libstdc++-v3/include/bits/ranges_algo.h | 141 ++++++++++++++++-- > .../25_algorithms/heap/constrained.cc | 46 ++++++ > 2 files changed, 171 insertions(+), 16 deletions(-) > > diff --git a/libstdc++-v3/include/bits/ranges_algo.h > b/libstdc++-v3/include/bits/ranges_algo.h > index a62c3cd3954d..4f10501956a7 100644 > --- a/libstdc++-v3/include/bits/ranges_algo.h > +++ b/libstdc++-v3/include/bits/ranges_algo.h > @@ -1881,6 +1881,28 @@ namespace ranges > > inline constexpr __shuffle_fn shuffle{}; > > + namespace __detail > + { > + template<typename _Iter, typename _Comp> > + constexpr void > + __push_heap(_Iter __first, > + iter_difference_t<_Iter> __holeIndex, > + iter_difference_t<_Iter> __topIndex, > + iter_value_t<_Iter> __value, > + _Comp __comp) > + { > + auto __parent = (__holeIndex - 1) / 2; > + while (__holeIndex > __topIndex > + && std::__invoke(__comp, *(__first + __parent), __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 +1912,17 @@ 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 > + { > + auto __comp_proj = __detail::__make_comp_proj(__comp, __proj); > + __detail::__push_heap(__first, (__last - __first) - 1, > + 0, ranges::iter_move(__last - 1), > + __comp_proj); > + return __last; > + } > } > > template<random_access_range _Range, > @@ -1909,6 +1938,49 @@ namespace ranges > > inline constexpr __push_heap_fn push_heap{}; > > + namespace __detail > + { > + template<typename _Iter, typename _Comp> > + constexpr void > + __adjust_heap(_Iter __first, > + iter_difference_t<_Iter> __holeIndex, > + iter_difference_t<_Iter> __len, > + iter_value_t<_Iter> __value, > + _Comp __comp) > + { > + auto __topIndex = __holeIndex; > + auto __secondChild = __holeIndex; > + while (__secondChild < (__len - 1) / 2) > + { > + __secondChild = 2 * (__secondChild + 1); > + if (std::__invoke(__comp, > + *(__first + __secondChild), > + *(__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); > + } > + > + template<typename _Iter, typename _Comp> > + constexpr void > + __pop_heap(_Iter __first, _Iter __last, _Iter __result, _Comp > __comp) > + { > + 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); > + } > + } // namespace __detail > + > struct __pop_heap_fn > { > template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent, > @@ -1918,10 +1990,18 @@ 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) > + { > + auto __comp_proj = __detail::__make_comp_proj(__comp, > __proj); > + __detail::__pop_heap(__first, __last - 1, __last - 1, > __comp_proj); > + } > + return __last; > + } > } > > template<random_access_range _Range, > @@ -1946,10 +2026,29 @@ 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 > + { > + const auto __len = __last - __first; > + if (__len < 2) > + return __last; > + > + auto __comp_proj = __detail::__make_comp_proj(__comp, __proj); > + 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 +2073,20 @@ 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 > + { > + auto __comp_proj = __detail::__make_comp_proj(__comp, __proj); > + _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.rc2 > >