This is an archive of the discontinued LLVM Phabricator instance.

[libc++] Implement ranges::is_sorted{, _until}
ClosedPublic

Authored by philnik on May 14 2022, 7:25 AM.

Details

Diff Detail

Event Timeline

philnik created this revision.May 14 2022, 7:25 AM
Herald added a project: Restricted Project. · View Herald TranscriptMay 14 2022, 7:25 AM
Herald added a subscriber: mgorny. · View Herald Transcript
philnik requested review of this revision.May 14 2022, 7:25 AM
Herald added a project: Restricted Project. · View Herald TranscriptMay 14 2022, 7:25 AM
Herald added a reviewer: Restricted Project. · View Herald Transcript
Mordante requested changes to this revision.May 15 2022, 8:18 AM

Thanks for working on this! It needs a bit more work.

libcxx/docs/Status/RangesAlgorithms.csv
31

Please update to the right URL.

libcxx/include/__algorithm/ranges_is_sorted.h
11

3 occurrences here and the same for the guards of the _until header.

47

This looks sensible, however it seems the Standard doesn't specify this overload. Is there an LWG issue?

libcxx/include/__algorithm/ranges_is_sorted_until.h
45

The move semantics in this function are inconsistent and wrong in some places.
while (++__i != __last) uses a moved from iterator.
one return moves, the other doesn't. Why move in the return, a forward_iterator is copyable.

libcxx/test/std/algorithms/alg.sorting/alg.sort/is.sorted/ranges.is_sorted.pass.cpp
8

libcxx/test/libcxx/algorithms/ranges_robust_against_copying_comparators.pass.cpp and libcxx/test/std/library/description/conventions/customization.point.object/niebloid.compile.pass.cpp need to be updated.

47

Then please make the fifth element sorted.

89

Can you also test a range with 1 element?

112

Originally I wanted to say I missed tests for the projection ;-)

libcxx/test/std/algorithms/alg.sorting/alg.sort/is.sorted/ranges.is_sorted_until.pass.cpp
48

The comments for the sorted test apply here too, except this specific test.
You can update it, but since you test the location of the "failure" I deem the sorting of the last element not too important.

131

The interesting question is, does std::ranges::sorted work with a temporary?
I expect it should, but please add a test for sorted in the sorted test.

This revision now requires changes to proceed.May 15 2022, 8:18 AM
philnik updated this revision to Diff 429539.May 15 2022, 8:40 AM
philnik marked 10 inline comments as done.
  • Address comments
libcxx/include/__algorithm/ranges_is_sorted.h
47

I'm not sure what you mean. It's both in the current standard and in the one ranges proposal. Did you just miss it? It's right after http://eel.is/c++draft/alg.sort#is.sorted-4.

libcxx/include/__algorithm/ranges_is_sorted_until.h
45

Idk. I must have thought these are input_iterators for some reason.

Mordante accepted this revision as: Mordante.May 16 2022, 10:51 AM

LGTM, except for the CI failure. I'll only approve it on my name to give others some time to have a look too.

libcxx/include/__algorithm/ranges_is_sorted.h
47

Nevermind, it seems I missed http://eel.is/c++draft/algorithms#requirements-15, which makes the wording clear. (Unless you want to be pedantic, then ranges::end(__range) seems not to be specified.)

var-const requested changes to this revision.May 24 2022, 1:11 PM

Looks really good, just a few extra test cases to add plus a couple nits.

libcxx/include/__algorithm/ranges_is_sorted.h
38

Nit: move?

47

Nit: store the result in a variable so we don't have to call end twice?

libcxx/include/__algorithm/ranges_is_sorted_until.h
55

Nit: move the iterator and the sentinel for consistency with other algorithms?

libcxx/include/algorithm
279

A couple nits:

  • in the standard, is_sorted goes before is_sorted_until, can you reorder for consistency?
  • there's an empty line between two overloads of is_sorted_until but not is_sorted, can you make this consistent?
libcxx/test/std/algorithms/alg.sorting/alg.sort/is.sorted/ranges.is_sorted.pass.cpp
35

Optional: consider creating a helper function that takes care of both the (iterator, sentinel) and the (range) overloads:

test_one({1, 2, 3, 4, 3}, /*expected=*/true); // Might need to use `std::array` as input
36

Nit: decltype(auto).

118

Please also add SFINAE tests.

119

I think we also need to test the case when the sentinel is a different type from the iterator.

libcxx/test/std/algorithms/alg.sorting/alg.sort/is.sorted/ranges.is_sorted_until.pass.cpp
31

Same comments as the other test file.

145

Nit: decltype(auto).

This revision now requires changes to proceed.May 24 2022, 1:11 PM
philnik updated this revision to Diff 432222.May 26 2022, 2:27 AM
philnik marked 9 inline comments as done.
  • Address comments
philnik updated this revision to Diff 432272.May 26 2022, 7:09 AM
  • Try to fix CI
var-const accepted this revision.May 26 2022, 6:07 PM

LGTM when the CI is green.

This revision is now accepted and ready to land.May 26 2022, 6:07 PM
This revision was automatically updated to reflect the committed changes.