Page MenuHomePhabricator

[libc++][ranges] Implement `ranges::is_heap{,_until}`.
ClosedPublic

Authored by var-const on Jul 25 2022, 10:03 PM.

Diff Detail

Event Timeline

var-const created this revision.Jul 25 2022, 10:03 PM
Herald added a project: Restricted Project. · View Herald TranscriptJul 25 2022, 10:03 PM
var-const requested review of this revision.Jul 25 2022, 10:03 PM
Herald added a project: Restricted Project. · View Herald Transcript
Herald added a reviewer: Restricted Project. · View Herald Transcript

Use the actual patch number.

var-const updated this revision to Diff 447607.Jul 26 2022, 1:02 AM

Fix the CI and rebase.

huixie90 accepted this revision as: huixie90.Jul 26 2022, 7:34 AM
huixie90 added a subscriber: huixie90.

Almost LGTM thanks!

libcxx/include/__algorithm/is_heap.h
31

i think perhaps not to pass the comp_ref type explicitly since the __is_heap_until already takes it by reference?

libcxx/include/__algorithm/ranges_is_heap.h
59

nit:
for ranges that do model sized_range but their iter/sent pair do not model sized_sentinel_for, by doing this it lost its size information and possibly as a result the ranges::next call becomes linear whereas it could be constant. What do you think?

libcxx/test/std/algorithms/alg.sorting/alg.heap.operations/is.heap/ranges_is_heap.pass.cpp
147–148

most other tests use a different type to test projection. perhaps it is a good idea to adopt the same approach, since having different types sound more realistic use case

ldionne accepted this revision.Jul 26 2022, 1:37 PM
ldionne added a subscriber: ldionne.
ldionne added inline comments.
libcxx/include/__algorithm/ranges_is_heap.h
59

That is an interesting corner case, however that would also require the range's iterator to be a random_access_iterator but not a sized_sentinel_for<It, Sent>. That seems rather broken to me.

For example, imagine a null-terminated string where the iterators are random access (roughly char*), but comparing against the end sentinel checks whether *it == '\0'. If the range is a sized_range, it means that it also stores the size of the string. In a case like that, I can't imagine why one would implement the iterator and the sentinel as different types, because the size is known anyway so end() can be implemented as begin() + size() trivially.

If I'm not imaginative enough, please feel free to enlighten me, however if this is such a tiny corner case, perhaps it is not worth increasing the complexity of our implementation to handle it.

This revision is now accepted and ready to land.Jul 26 2022, 1:37 PM
huixie90 added inline comments.Jul 26 2022, 3:33 PM
libcxx/include/__algorithm/ranges_is_heap.h
59

@ldionne

auto v = std::ranges::iota_view(5, 7L);
using iter = std::ranges::iterator_t<decltype(v)>;
using sent = std::ranges::sentinel_t<decltype(v)>;

static_assert(std::ranges::sized_range<decltype(v)>);
static_assert(std::random_access_iterator<iter>);
static_assert(!std::sized_sentinel_for<sent, iter>);

https://godbolt.org/z/7bd91z5c4

Yes it is a corner case and yes iota_view is weird. so I am happy to NAD this

var-const updated this revision to Diff 447865.Jul 26 2022, 4:01 PM
var-const marked 2 inline comments as done.

Address feedback and rebase.

libcxx/include/__algorithm/is_heap.h
31

Thanks!

This revision was landed with ongoing or failed builds.Jul 26 2022, 4:11 PM
This revision was automatically updated to reflect the committed changes.