This is an archive of the discontinued LLVM Phabricator instance.

[libc++][ranges] Implement `std::ranges::partial_sort_copy`.
ClosedPublic

Authored by var-const on Jul 25 2022, 4:53 PM.

Diff Detail

Event Timeline

var-const created this revision.Jul 25 2022, 4:53 PM
Herald added a project: Restricted Project. · View Herald TranscriptJul 25 2022, 4:53 PM
Herald added a subscriber: mgrang. · View Herald Transcript
var-const requested review of this revision.Jul 25 2022, 4:53 PM
Herald added a project: Restricted Project. · View Herald Transcript
Herald added a reviewer: Restricted Project. · View Herald Transcript

Fix the CI and rebase.

huixie90 accepted this revision.Jul 26 2022, 5:59 AM
huixie90 added a subscriber: huixie90.
huixie90 added inline comments.
libcxx/docs/Status/RangesAlgorithms.csv
62

can fill in the patch number

libcxx/test/std/algorithms/alg.sorting/alg.sort/partial.sort.copy/ranges_partial_sort_copy.pass.cpp
77

nit: would MoveOnly.hwork?

This revision is now accepted and ready to land.Jul 26 2022, 5:59 AM
ldionne accepted this revision.Jul 26 2022, 12:56 PM
ldionne added a subscriber: ldionne.

LGTM % comments and CI

libcxx/include/__algorithm/partial_sort_copy.h
34

This is a pre-existing issue, but I think our implementation doesn't work for single-pass input iterators, since we go over the input range twice. Since this is a pre-existing issue, let's fix it after the dust has settled with the release, but let's please make sure to remember. We should start filing bugs for issues like this that we encounter, to make sure they are not forgotten.

51

As we discussed just now, IMO this is better since it shields __sort_heap & friends from having to know about projections. I don't have a strong preference though, I'll defer to your judgement/preference.

55

We are recomputing next(__first, __last) here, however this wouldn't work for a single-pass input iterator. Fortunately, we just computed that in the loop above, so it should be possible to extract it from there. Definitely not for this patch, as this will fail when we have a test for single-pass input iterators anyway.

libcxx/test/std/algorithms/ranges_robust_against_differing_projections.pass.cpp
2

This is part of another commit.

huixie90 added inline comments.Jul 26 2022, 1:25 PM
libcxx/include/__algorithm/partial_sort_copy.h
34

@ldionne, Could you please clarify a bit more? the input range [__first, __last) seems to be iterated only once unless I missed anything?

55

@ldionne, I don't think we are recomputing it or multi-passing the range. __first at this stage is already pointing to very end if not the __last. We are never going to iterating from the beginning but only iterating from the point that we haven't iterated yet. or do I miss anything?

var-const updated this revision to Diff 447912.Jul 26 2022, 7:10 PM
var-const marked 5 inline comments as done.

Address feedback and rebase.

libcxx/docs/Status/RangesAlgorithms.csv
62

Thanks!

libcxx/include/__algorithm/partial_sort_copy.h
34

In either case, I've added it to my backlog to prepare a robust test that we support single-pass input iterators in all the relevant algorithms.

51

Unfortunately, for this to work, __make_projected_comp would have to support C++03. I took a stab at it: https://reviews.llvm.org/D130611, and it's a bit ugly. Let's discuss in the linked patch -- I can submit it as a follow up.

55

From the offline discussion, this is probably unnecessary because __first should already point to __last. I'm a little reluctant to remove this from this patch, though -- it seems like it should be a no-op in that case, but if the assumption is somehow wrong, the function would be broken. I'll do a follow-up instead.

var-const updated this revision to Diff 448217.Jul 27 2022, 5:25 PM

Address feedback (__make_projected now supports the C++03 mode).

var-const updated this revision to Diff 448275.Jul 28 2022, 2:20 AM

Fix the CI.

huixie90 added inline comments.Jul 28 2022, 4:04 AM
libcxx/include/__algorithm/make_projected.h
81–84 ↗(On Diff #448217)

why is the enable_if logic written twice?
Also, usually for sfinae multiple overloads, we use non-type template parameter

template <class A, enable_if<C>* = nullptr>
var-const updated this revision to Diff 448768.Jul 29 2022, 8:06 PM
var-const marked an inline comment as done.

Address feedback and rebase.

libcxx/include/__algorithm/make_projected.h
81–84 ↗(On Diff #448217)

Thanks for spotting!

Fix the CI and rebase.