[PATCH 1/2] libstdc++: Directly implement ranges::heap algos [PR100795]
Tomasz Kaminski
tkaminsk@redhat.com
Thu Jun 12 15:04:35 GMT 2025
On Thu, Jun 12, 2025 at 4:56 PM Patrick Palka <ppalka@redhat.com> wrote:
> On Wed, 11 Jun 2025, Tomasz Kaminski wrote:
>
> >
> >
> > On Wed, Jun 11, 2025 at 1:56 PM Jonathan Wakely <jwakely@redhat.com>
> wrote:
> > On Wed, 11 Jun 2025 at 12:42, Tomasz Kaminski <tkaminsk@redhat.com>
> wrote:
> > >
> > >
> > >
> > > On Tue, Jun 10, 2025 at 3:05 AM Patrick Palka <ppalka@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.
>
LGTM. Thanks.
>
> >
> >
> >
> > > 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
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://gcc.gnu.org/pipermail/libstdc++/attachments/20250612/b114ca4a/attachment-0001.htm>
More information about the Libstdc++
mailing list