This is an archive of the discontinued LLVM Phabricator instance.

[libc++][ranges] Implement `ranges::nth_element`.
ClosedPublic

Authored by var-const on Jun 19 2022, 8:08 PM.

Diff Detail

Event Timeline

var-const created this revision.Jun 19 2022, 8:08 PM
Herald added a project: Restricted Project. · View Herald TranscriptJun 19 2022, 8:08 PM
Herald added subscribers: mgrang, mgorny. · View Herald Transcript
var-const requested review of this revision.Jun 19 2022, 8:08 PM
Herald added a project: Restricted Project. · View Herald Transcript
Herald added a reviewer: Restricted Project. · View Herald Transcript
var-const updated this revision to Diff 438241.Jun 19 2022, 8:10 PM

Use the actual patch number.

var-const added inline comments.Jun 19 2022, 8:11 PM
libcxx/include/__algorithm/nth_element.h
32–38

The ABI annotation was missing.

var-const updated this revision to Diff 438242.Jun 19 2022, 8:12 PM

Rebase on main.

philnik requested changes to this revision.Jun 20 2022, 3:39 AM
philnik added a subscriber: philnik.
philnik added inline comments.
libcxx/include/__algorithm/nth_element.h
31

Could you do the whitespace formatting in a different patch?

libcxx/include/__algorithm/ranges_nth_element.h
47
libcxx/test/std/algorithms/alg.sorting/alg.nth.element/ranges_nth_element.pass.cpp
73

I don't think we should do that. It's quite fragile and we even have _LIBCPP_DEBUG_RANDOMIZE_RANGE to avoid that users depend on the exact output.

147
196

Descending?

247

I don't think this should be here.

276

Also this.

This revision now requires changes to proceed.Jun 20 2022, 3:39 AM
ldionne accepted this revision as: ldionne.Jun 21 2022, 1:25 PM
ldionne added a subscriber: ldionne.

All in all, LGTM with some comments.

You should poke the CI.

libcxx/include/__algorithm/nth_element.h
31

+1, it'll make it possible to ignore it for git blame. We should really strive to do these mostly-whitespace changes in NFC patches, otherwise we'll destroy our ability to git blame, and we'll pay for that in the future.

libcxx/test/std/algorithms/alg.sorting/alg.nth.element/ranges_nth_element.pass.cpp
73

I agree. I think this is going to be brittle if we make changes to our algorithms. Also, if you remove this, you can (and should) still check that the value of the nth element is as expected (i.e. instead of passing an expected array, you can pass an expected value (or iterator to validate the position)).

165–169

IMO this is a bit complicated, we could instead just manually call test_all_cases with each (input, n, expected) combination. And that would allow getting rid of the array<array<...>> overload of test_all_cases, which I had to pause quite a bit on.

215

Instead of having multiple test_iterator_n functions, I would do something like this (IMO it localizes things which makes it more obvious where they are used):

constexpr void test_iterators() {
  auto check = []<class Iter, class Sent> {
    // all checks
  };

  check.operator()<random_access_iterator<int*>, random_access_iterator<int*>>();
  check.operator()<random_access_iterator<int*>, sentinel_wrapper<random_access_iterator<int*>>>();

  // etc.
}

If you dislike the lambda, you could define it as a function template named e.g. test_iterators_impl, but the point here is to make it obvious that it's only an implementation detail of test_iterators. Otherwise, I'd have to check whether test_iterators_1 is somehow called from elsewhere in the file, and whether that might be the reason for giving it a "global" name.

huixie90 requested changes to this revision.Jun 27 2022, 10:25 AM
huixie90 added a subscriber: huixie90.
huixie90 added inline comments.
libcxx/include/__algorithm/nth_element.h
71

similar for other reiviews, ranges overload require the implementation to use iter_move and iter_swap

97

ranges overload needs to use iter_swap. same for the rest of swaps

var-const updated this revision to Diff 440532.Jun 28 2022, 1:41 AM
var-const marked 13 inline comments as done.

Address feedback.

libcxx/include/__algorithm/nth_element.h
71

Thanks a lot for finding this issue! Will fix in a follow-up.

97

Same as the other comment -- will fix in a follow-up.

libcxx/test/std/algorithms/alg.sorting/alg.nth.element/ranges_nth_element.pass.cpp
73

Thanks, this makes the tests way less verbose. Rather than passing values explicitly, it seems easier to create a copy of the input and sort it, then compare the nth elements between the partially-sorted and fully-sorted sequences.

165–169

(no longer applies now that we're not checking for the exact output)

247

Same as the other review -- this is necessary to compare the value of the nth element.

276

(see the other comment)

Fix the CI.

var-const updated this revision to Diff 441909.Jul 2 2022, 3:57 PM
  • Don't randomize the range if nth == last -- otherwise, the function isn't a no-op;
  • rebase on main.
var-const added inline comments.Jul 2 2022, 3:59 PM
libcxx/include/__algorithm/nth_element.h
239

I think this condition is necessary -- otherwise, the function isn't a no-op when __nth == __last. The standard doesn't say it should be a no-op explicitly, but nevertheless, it seems strange to have a call to nth_element(vector.begin(), vector.end(), vector.end()); reshuffle the vector.

var-const updated this revision to Diff 441916.Jul 2 2022, 6:53 PM

Fix wrong interval

var-const updated this revision to Diff 441919.Jul 2 2022, 7:11 PM

Fix the interval.

huixie90 accepted this revision.Jul 6 2022, 10:01 AM
huixie90 added inline comments.
libcxx/include/__algorithm/nth_element.h
243

question: why do we need inline in these function templates?

var-const updated this revision to Diff 443108.Jul 7 2022, 7:12 PM

Fix the CI.

var-const updated this revision to Diff 443131.Jul 7 2022, 8:39 PM

Rebase on main.

This revision was not accepted when it landed; it landed in state Needs Review.Jul 8 2022, 11:26 AM
This revision was automatically updated to reflect the committed changes.