This is an archive of the discontinued LLVM Phabricator instance.

[libc++][ranges] Implement ranges::max_element
ClosedPublic

Authored by philnik on Jan 17 2022, 4:29 PM.

Details

Summary

Implement ranges::max_element

Diff Detail

Event Timeline

philnik created this revision.Jan 17 2022, 4:29 PM
philnik requested review of this revision.Jan 17 2022, 4:29 PM
Herald added a project: Restricted Project. · View Herald TranscriptJan 17 2022, 4:29 PM
Herald added a reviewer: Restricted Project. · View Herald Transcript

In general looks good, but I'd like a bit more test coverage.

libcxx/test/std/algorithms/alg.sorting/alg.min.max/ranges.max_element.pass.cpp
29

Would it be possible to use special comparison and projection to validate the complexity?
Complexity: Exactly max(last - first - 1,0) comparisons and twice as many projections.

84

I would like a test where the maximum value occurs twice to validate whether it returns the first, per Returns: The first iterator i in the range….

90

For reviewing it would be nice to also validate the value assert(*ret == x); in all these tests.

philnik planned changes to this revision.Feb 9 2022, 12:12 PM

In general looks good, but I'd like a bit more test coverage.

Could you first review D117025? It's basically the same. I'll apply the changes there over here, once D117025 is done.

In general looks good, but I'd like a bit more test coverage.

Could you first review D117025? It's basically the same. I'll apply the changes there over here, once D117025 is done.

I'll look at it.

libcxx/test/std/algorithms/alg.sorting/alg.min.max/ranges.max_element.pass.cpp
84

I see in D117025 it has two times a min_element of 1 in the test at line 85.

philnik updated this revision to Diff 407977.Feb 11 2022, 12:02 PM
  • Fix CI
  • Copy test from min_element

Please git grep ranges::max_element and fix what you find. std/library/description/conventions/customization.point.object/niebloid.compile.pass.cpp needs updating at least.

philnik updated this revision to Diff 408507.Feb 14 2022, 10:48 AM
  • Enable niebloid test
philnik updated this revision to Diff 410707.Feb 22 2022, 9:47 PM
  • Rebased
  • Fix CI
Herald added a project: Restricted Project. · View Herald TranscriptMar 6 2022, 4:23 AM
Quuxplusone accepted this revision.Mar 6 2022, 7:06 AM

LGTM % comments, and the only significant comment affects the already-committed test for ranges::min_element. I think this is good to go, to get min and max back into parity; but then after that, they should both get some improved tests.

Also, before landing, please run a diff <(sed s/min/foo/g ranges_min_element.h) <(sed s/max/foo/g ranges_max_element.h) and make sure there are no extraneous differences between the two source files. If I understand correctly, there should only be one diff: the order of the arguments to __comp!

libcxx/include/__algorithm/ranges_max_element.h
35
libcxx/test/std/algorithms/alg.sorting/alg.min.max/ranges.max_element.pass.cpp
58–67

test_range is called only once — both here and in ranges.min_element.pass.cpp, although I feel sure I commented multiple times about this kind of thing. Replace its call-site there with

int a2[] = {7, 6, 5, 3, 4, 2, 1, 8};
assert(std::ranges::min_element(a) == a + 6);

and here with

int a2[] = {7, 6, 5, 3, 4, 2, 1, 8};
assert(std::ranges::max_element(a) == a + 7);

After that, think about whether there's any test coverage missing. (Hint: probably.)

This revision is now accepted and ready to land.Mar 6 2022, 7:06 AM
This revision was automatically updated to reflect the committed changes.
philnik marked an inline comment as done.
ldionne added inline comments.May 20 2022, 9:08 AM
libcxx/include/algorithm
749

This forgot to update the synopsis with ranges::max_element. @philnik do you mind adding it?