śr., 29 kwi 2026 o 03:23 Arthur O'Dwyer via Std-Proposals
<std-proposals_at_[hidden]> napisał(a):
>
> Hi std-proposals,
>
> Has anyone previously brought up that `std::is_heap` is currently specified to take random-access iterators, but in fact (AFAICT) can easily be implemented to use only forward-iterator operations?
>
> Here's a libc++-inspired implementation (that passes libc++'s own test suite):
>
> template <class _Compare, class _ForwardIterator, class _Sentinel>
> _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _ForwardIterator
> __is_heap_until(_ForwardIterator __first, _Sentinel __last, _Compare&& __comp) {
> _ForwardIterator __child = __first;
> if (__child == __last) {
> return __child;
> }
> while (true) {
> ++__child;
> if (__child == __last || __comp(*__first, *__child)) {
> break;
> }
> ++__child;
> if (__child == __last || __comp(*__first, *__child)) {
> break;
> }
> ++__first;
> }
> return __child;
> }
>
> I have vague recollections of some paper asking to weaken the iterator requirements for some STL algorithms — maybe std::partition? — but I don't remember any details and haven't been able to dig it up (if it exists). P0467 strengthened some iterator requirements for parallel algorithms; maybe I'm just garbling a memory of that paper.
>
> I'm interested in (1) refutations of the algorithm above; (2) prior papers in this area, especially if anyone's proposed exactly this weakening for is_heap before; (3) anything else that seems relevant.
>

But any other operation on this heap needs random-access, right?
If this is true then the forward version will not be very useful as
any other operation will be not available until you
convert to some random access container.

> Cheers,
> Arthur
> --
> Std-Proposals mailing list
> Std-Proposals_at_[hidden]
> https://lists.isocpp.org/mailman/listinfo.cgi/std-proposals