This is an archive of the discontinued LLVM Phabricator instance.

[libc++][ranges] implement `std::ranges::inplace_merge`
ClosedPublic

Authored by huixie90 on Jul 27 2022, 5:20 AM.

Details

Diff Detail

Event Timeline

huixie90 created this revision.Jul 27 2022, 5:20 AM
Herald added a project: Restricted Project. · View Herald TranscriptJul 27 2022, 5:20 AM
Herald added a subscriber: mgorny. · View Herald Transcript
huixie90 updated this revision to Diff 448051.Jul 27 2022, 8:22 AM

implement tests

huixie90 published this revision for review.Jul 27 2022, 8:26 AM
Herald added projects: Restricted Project, Restricted Project. · View Herald Transcript
Herald added a reviewer: Restricted Project. · View Herald Transcript
var-const requested changes to this revision.Jul 27 2022, 12:45 PM
var-const added a subscriber: var-const.

Thanks a lot! A few nitpicks, and let's discuss algorithm_family.h offline (I'll post a summary here afterwards).

libcxx/docs/Status/RangesAlgorithms.csv
80

The patch number needs to be updated.

libcxx/include/__algorithm/inplace_merge.h
52

Nit: it's best not to do these refactoring changes in this patch (for the lines that you don't otherwise modify). It increases the delta that needs to be reviewed, but more importantly, it makes it harder to navigate git blame. Ideally, such changes should go to dedicated refactoring patches which can then be added to .git-blame-ignore-revs.

This doesn't apply to the lines that you're modifying anyway -- since those would show up in git blame regardless, might as well refactor them.

libcxx/test/std/algorithms/alg.sorting/alg.merge/ranges_inplace_merge.pass.cpp
91

Optional: consider asserting that (input.begin(), input.begin() + midIdx) and (input.begin() + midIdx, input.end()) are is_sorted.

122

Missing [first, mid).

143

Nit: s/duplictes/duplicates/.

164

Consider also checking mid == first + 1 and mid == last - 1 (to check for off-by-one errors).

272

Please copy the specification from the standard into this comment.

291

Ultranits: s/specify/specifies/ and s/does not/don't/.

291

I noticed the same with shuffle. It could be a simple oversight in the spec.

338

Nit: "yet" makes it a little ambiguous whether it's not constexpr in the standard or just in our implementation. I'd rephrase to inplace_merge is not constexpr in the latest finished Standard.

This revision now requires changes to proceed.Jul 27 2022, 12:45 PM
huixie90 updated this revision to Diff 448171.Jul 27 2022, 2:53 PM
huixie90 marked 9 inline comments as done.

address review feedback

huixie90 updated this revision to Diff 448175.Jul 27 2022, 2:58 PM

add newline

var-const accepted this revision.Jul 27 2022, 3:16 PM
var-const added inline comments.
libcxx/include/__algorithm/algorithm_family.h
26

Nit: since we're using _AlgPolicy, this should be _AlgFamily (no o).

This revision is now accepted and ready to land.Jul 27 2022, 3:16 PM
huixie90 updated this revision to Diff 448188.Jul 27 2022, 3:35 PM
huixie90 marked an inline comment as done.

address comments

This revision was automatically updated to reflect the committed changes.