Page MenuHomePhabricator

[libcxx][algorithms] adds ranges::lower_bound and ranges::upper_bound
Needs RevisionPublic

Authored by cjdb on Jul 12 2021, 12:15 AM.

Details

Reviewers
ldionne
zoecarver
Mordante
EricWF
jdoerfert
Group Reviewers
Restricted Project
Summary

Implements part of http://wg21.link/p0896.
Implements [lower.bound] and [upper.bound].

Depends on D105794.

Diff Detail

Event Timeline

cjdb requested review of this revision.Jul 12 2021, 12:15 AM
cjdb created this revision.
Herald added a project: Restricted Project. · View Herald Transcript
Herald added a reviewer: Restricted Project. · View Herald Transcript
cjdb updated this revision to Diff 358153.Jul 12 2021, 10:10 PM

rebases to activate CI

cjdb updated this revision to Diff 358305.Jul 13 2021, 9:27 AM

rebases to activate CI

cjdb updated this revision to Diff 358375.Jul 13 2021, 11:39 AM

rebases to activate CI

tcanens added inline comments.
libcxx/include/__algorithm/lower_bound.h
95

indirect_strict_weak_order doesn't guarantee that the projected element is comparable after it's been turned into a const lvalue.

boolean-testable doesn't guarantee that it can be copied or moved.

cjdb added inline comments.Jul 13 2021, 1:10 PM
libcxx/include/__algorithm/lower_bound.h
95

indirect_strict_weak_order doesn't guarantee that the projected element is comparable after it's been turned into a const lvalue.

If this were your only comment, I'd change it to this.

auto __pred = [&__value, &__comp]<class _ProjElem>(_ProjElem&& __proj_elem) {
  return _VSTD::invoke(__comp, _VSTD::forward<_ProjElem>(__proj_elem), __value);
};

boolean-testable doesn't guarantee that it can be copied or moved.

This gives me pause. Can I rely on perfect forwarding to do the right thing here?

tcanens added inline comments.Jul 13 2021, 2:15 PM
libcxx/include/__algorithm/lower_bound.h
95

boolean-testable doesn't guarantee that it can be copied or moved.

This gives me pause. Can I rely on perfect forwarding to do the right thing here?

You can just have __pred explicitly return bool and let the implicit conversion handle it. There's no real reason to forward the result all the way through.

cjdb updated this revision to Diff 359372.Jul 16 2021, 9:56 AM

rebases to activate CI

zoecarver added inline comments.Jul 16 2021, 10:06 AM
libcxx/test/std/algorithms/alg.sorting/alg.binary.search/lower.bound/ranges_lower_bound/ranges_lower_bound.pass.cpp
34

libcxx_log2? Why can't we use std::log2?

42

Nit: space.

cjdb added inline comments.Jul 16 2021, 10:32 AM
libcxx/test/std/algorithms/alg.sorting/alg.binary.search/lower.bound/ranges_lower_bound/ranges_lower_bound.pass.cpp
34

std::log2 isn't constexpr :(((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((

ldionne requested changes to this revision.Jul 22 2021, 2:57 PM

I think it would be fine to have a couple of test cases that use the complexity_xxx machinery, but it shouldn't be *all* the test cases. It increases the complexity of understanding the test cases and also we end up only testing with the complexity_invocable, not the actual predicates.

libcxx/include/__algorithm/lower_bound.h
101

We definitely want to enable this check only when the user requests a stronger level of debugging. It should be possible to enable _LIBCPP_ASSERT without violating any complexity guarantee, such that one could in theory enable _LIBCPP_ASSERT in the released version of an application. Those expensive checks should be enabled only when a proper debug mode is requested.

However, things are a bit of a mess and we already can't do that today with _LIBCPP_ASSERT, so I won't hold you to that here. You can leave as-is, I just wanted to mention it so it's known that we should eventually go back and decide which checks are to be enabled in "debug" mode and which ones when "minimal assertions" are enabled.

libcxx/test/std/algorithms/alg.sorting/alg.binary.search/lower.bound/ranges_lower_bound/ranges_lower_bound.pass.cpp
84

Here and elsewhere, please make sure you assign the result of lower_bound to a variable with a proper type. In the tests, it's useful to pin down the type of things to test that we return the right types (whereas I would agree in normal code auto improves readability).

153

Just it?

This revision now requires changes to proceed.Jul 22 2021, 2:57 PM
miscco added a subscriber: miscco.Jul 23 2021, 3:34 AM
miscco added inline comments.
libcxx/test/std/algorithms/alg.sorting/alg.binary.search/lower.bound/ranges_lower_bound/ranges_lower_bound.pass.cpp
84

Actually that would be a bit harmfull due to implicit conversions.

You should assign to auto and then check the type of the variable via a static assert.

With concepts you could also do a same_as<expected_type> auto it = ...

Quuxplusone added inline comments.
libcxx/test/std/algorithms/alg.sorting/alg.binary.search/lower.bound/ranges_lower_bound/ranges_lower_bound.pass.cpp
64

Maybe this is redundant with a point @ldionne has already made re complexity_foo; but it's important that we test some of these algorithms with predicates that are not std::reference_wrapper.

84

"A bit harmful" is overstating the case (since that's libc++ style everywhere). But in any test that already requires C++20 Concepts support, I agree:

std::same_as<decltype(input.begin())> auto it = ranges::lower_bound(input.begin(), input.end(), ...);

would be a pretty neat way to encode the assertion into the test. Let's do that (in tests that already require Concepts, at least).