Page MenuHomePhabricator

[libc++][ranges] Implement `std::ranges::partition_{point,copy}`.
ClosedPublic

Authored by var-const on Jul 19 2022, 2:34 AM.

Diff Detail

Event Timeline

var-const created this revision.Jul 19 2022, 2:34 AM
Herald added a project: Restricted Project. · View Herald TranscriptJul 19 2022, 2:34 AM
var-const requested review of this revision.Jul 19 2022, 2:34 AM
Herald added a project: Restricted Project. · View Herald TranscriptJul 19 2022, 2:34 AM
Herald added a reviewer: Restricted Project. · View Herald Transcript
var-const updated this revision to Diff 445750.Jul 19 2022, 2:35 AM

Use the actual patch number.

var-const added inline comments.Jul 19 2022, 2:39 AM
libcxx/include/__algorithm/ranges_partition_copy.h
44

These two algorithms seem borderline when choosing whether to delegate or reimplement. I'm quite open to delegate if you feel it would be beneficial.

libcxx/test/std/algorithms/alg.modifying.operations/alg.partitions/ranges_partition_copy.pass.cpp
200

I am concerned about the combinatorial explosion here. Perhaps it is sufficient to test with just the weakest and the "strongest" iterator types that satisfy the necessary constraints?

(Note that I think partition_copy is the only algorithm to have two different output iterator types)

Fix the CI.

huixie90 added inline comments.Jul 19 2022, 1:18 PM
libcxx/test/std/algorithms/alg.modifying.operations/alg.partitions/ranges_partition_copy.pass.cpp
297

perhaps also tests "Complexity: Exactly last - first applications of pred and proj."

libcxx/test/std/algorithms/alg.modifying.operations/alg.partitions/ranges_partition_point.pass.cpp
170

can we have at least one test where the comparator is not is_odd?

ldionne accepted this revision as: ldionne.Jul 19 2022, 1:36 PM

Leaving final approval to @huixie90

libcxx/include/__algorithm/ranges_partition_copy.h
44

I would have a preference for delegating. I'm also fine with a TODO to do it after the release, since you have it implemented right now and it works (according to the tests).

libcxx/test/std/algorithms/alg.modifying.operations/alg.partitions/ranges_partition_copy.pass.cpp
200

Yes, I think it's OK to test only the weakest and the strongest iterator types, with a comment.

209–211

Note that I would remove those and replace them by an explanation, otherwise it looks like you simply forgot to uncomment before committing.

var-const updated this revision to Diff 445997.Jul 19 2022, 6:11 PM
var-const marked 5 inline comments as done.

Address feedback, rebase on main.

libcxx/include/__algorithm/ranges_partition_copy.h
44

Thanks! Added a TODO.

libcxx/test/std/algorithms/alg.modifying.operations/alg.partitions/ranges_partition_copy.pass.cpp
297

I want to consolidate these checks as well, but realistically won't have time before the branch cut. Added the test.

libcxx/test/std/algorithms/alg.modifying.operations/alg.partitions/ranges_partition_point.pass.cpp
170

Done (also in partition and stable_partition).

var-const updated this revision to Diff 446006.Jul 19 2022, 6:23 PM

Rebase on main.

var-const updated this revision to Diff 446008.Jul 19 2022, 6:30 PM

Rebase on main, fix new test.

var-const updated this revision to Diff 446018.Jul 19 2022, 7:40 PM

Fix the CI.

var-const updated this revision to Diff 446026.Jul 19 2022, 8:18 PM

Fix the CI and rebase on main.

var-const updated this revision to Diff 446033.Jul 19 2022, 8:53 PM

Rebase on main.

huixie90 accepted this revision.Jul 20 2022, 1:50 AM

LGTM with nits

libcxx/include/__algorithm/ranges_partition_copy.h
45

nit:
_InIter can be a reference type if we don't do std::move on the caller. Since this is a local static function, it is unlikely to be used elsewhere. so it is ok to leave it as it is. If this were an __ function, I would either uncvref them, or pass them by value to make sure we have a partition_copy_result of value types

libcxx/test/std/algorithms/alg.modifying.operations/alg.partitions/ranges_partition_copy.pass.cpp
133–134

nit: It is OK to allocate N2 and N3 I think. In case the algorithm goes wrong and cause buffer overflow, the constexpr test would fail. It also simplifies the verification to just ranges::all_of(out1, pred)

143–144

can we also verify ranges::equal(out1, expected_true) and ranges::equal(out2, expected_false)
otherwise the test would still pass if the algorithm simply repeatedly copies the first element in the group

This revision is now accepted and ready to land.Jul 20 2022, 1:50 AM
var-const updated this revision to Diff 446084.Jul 20 2022, 2:07 AM
var-const marked 3 inline comments as done.

Address feedback.

libcxx/test/std/algorithms/alg.modifying.operations/alg.partitions/ranges_partition_copy.pass.cpp
133–134

Very good point re. constexpr. I dropped the checks for all_of altogether in favor of just comparing to expected_* explicitly.

143–144

Thanks for spotting this, this is an oversight on my part.