On Wed, 11 Jun 2025, Tomasz Kaminski wrote:
>
>
> On Wed, Jun 11, 2025 at 1:56 PM Jonathan Wakely <jwak...@redhat.com> wrote:
> 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
>
> So the PR does not seem relevant for the range algorithm, and given that
> helper sort functions
> pass comparator by value via multiple layers, I think we should default
> by-value, given no reason
> to do otherwise.
Ack. Also I think by-value is optimal (in terms of codegen) for the
common case where the comparator/projection are empty types, if the
helper functions for some reason don't get inlined.
>
>
>
> > 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;
Fixed.
Here's an updated patch, with the above early if change and also
changed stl_algo.h mentions to stl_heap.h in the commit message.
-- >8 --
Subject: [PATCH 1/2] 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
- 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_heap.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_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 | 138 ++++++++++++++++--
.../25_algorithms/heap/constrained.cc | 46 ++++++
2 files changed, 168 insertions(+), 16 deletions(-)
diff --git a/libstdc++-v3/include/bits/ranges_algo.h
b/libstdc++-v3/include/bits/ranges_algo.h
index a62c3cd3954d..ca86f63812f4 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)
+ {
+ 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)
+ {
+ 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)
+ {
+ 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
+ {
+ const auto __len = __last - __first;
+ if (__len < 2)
+ return __last;
+
+ 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.rc2
