This is an archive of the discontinued LLVM Phabricator instance.

[libc++] Implement ranges::find_first_of
ClosedPublic

Authored by philnik on May 27 2022, 3:59 AM.

Details

Reviewers
ldionne
Mordante
var-const
Group Reviewers
Restricted Project
Commits
rGb79b2b677256: [libc++] Implement ranges::find_first_of

Diff Detail

Event Timeline

philnik created this revision.May 27 2022, 3:59 AM
Herald added a project: Restricted Project. · View Herald TranscriptMay 27 2022, 3:59 AM
Herald added a subscriber: mgorny. · View Herald Transcript
philnik requested review of this revision.May 27 2022, 3:59 AM
Herald added a project: Restricted Project. · View Herald TranscriptMay 27 2022, 3:59 AM
Herald added a reviewer: Restricted Project. · View Herald Transcript

In general looks good modulo some minor issues. But before approving I like to know whether or not we want to avoid code duplication between the "old" algorithms and their ranges based equivalents.

libcxx/include/__algorithm/ranges_find_first_of.h
43

I saw @ldionne recently raised some concerns regarding duplicating algorithms for the ranges and non-ranges version. Have we found a solution for that concern?

libcxx/test/std/algorithms/alg.nonmodifying/alg.find.first.of/ranges.find_first_of.pass.cpp
76

I find it a bit confusion the have an array<int, x> and an int expected not related.
Since the expected is an offset giving it a better type helps to avoid the confusion for me.

102

This is a duplicate of line 99.

113

I would like to see two non-empty ranges that have no match at all. For example
test<Iter1, Sent1, Iter2, Sent2, 4, 4>({.input1 = {1, 3, 5, 7}, .input2 = {0, 2, 4, 6}, .expected = 5});

148

For clarity I would prefer to use std::begin() and std::end() here.

208
philnik updated this revision to Diff 432979.May 30 2022, 1:37 PM
philnik marked 5 inline comments as done.
  • Address comments
libcxx/include/__algorithm/ranges_find_first_of.h
43

I think we have to decide that on a case-by-case basis. There are cases where I think it's more hassle than it's worth like here and there are cases where it's a definite win, like copy or move. There are of course also cases where it's not really clear, like binary_search. Note that there are optimizations possible for the ranges algorithms which are simply not possible for the classical algorithms (like in ranges::is_permutation) and ones where making optimizations for the ranges version properly is a lot harder (like ranges::move).

Mordante accepted this revision as: Mordante.Jun 1 2022, 11:45 AM

LGTM, modulo one comment.
Since I'm not too involved in ranges I prefer to leave the final approval to @var-const or @ldionne.

libcxx/include/__algorithm/ranges_find_first_of.h
43

Thanks for the info!

libcxx/test/std/algorithms/alg.nonmodifying/alg.find.first.of/ranges.find_first_of.pass.cpp
148

Can you do the same for similar places in the tests?

var-const requested changes to this revision.Jun 3 2022, 10:17 PM

Almost LGTM, just some nits.

libcxx/docs/Status/RangesAlgorithms.csv
7–8

Nit: please update the link. Also, I don't think there should be a space between the tilde and the < character.

libcxx/include/__algorithm/ranges_find_first_of.h
44

Why are we creating a new variable instead of incrementing __first2, which would be consistent with __first1?

libcxx/test/std/algorithms/alg.nonmodifying/alg.find.first.of/ranges.find_first_of.pass.cpp
98

(By the way, I like these "named arguments")

107

For exhaustiveness, I'd also add a test case when input2 consists of a single element (currently, all the successful cases have input2 with several elements).

123

Nit: unnecessary blank line.

171

Great test, can you please check if there are any other range algorithm tests where a similar test would be valuable?

183

Nit: swap the order, so that the iterator overload goes before the range overload?

222

Question: perhaps check for the exact value?

This revision now requires changes to proceed.Jun 3 2022, 10:17 PM
philnik marked 8 inline comments as done.Jun 6 2022, 4:58 AM
philnik added inline comments.
libcxx/include/__algorithm/ranges_find_first_of.h
44

Because we go a few times over [__first2, __last2).

libcxx/test/std/algorithms/alg.nonmodifying/alg.find.first.of/ranges.find_first_of.pass.cpp
171

I think I mostly added this test to other ranges algorithms. A few of the first ones might be missing a few tests, but I think that is a problem for later. They should probably be refactored and extended at some point.

philnik updated this revision to Diff 434437.Jun 6 2022, 4:58 AM
philnik marked an inline comment as done.
  • Address comments
var-const accepted this revision.Jun 6 2022, 1:25 PM
var-const added inline comments.
libcxx/include/__algorithm/ranges_find_first_of.h
44

Oh, sorry for missing that, it's quite obvious.

This revision is now accepted and ready to land.Jun 6 2022, 1:25 PM
This revision was automatically updated to reflect the committed changes.