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
<https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2017/p0467r2.html#6.0>
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.

Cheers,
Arthur