Details
- Reviewers
Mordante var-const ldionne jdoerfert - Group Reviewers
Restricted Project - Commits
- rG8171586176ee: [libc++][ranges] Implement ranges::binary_search and ranges::{lower…
Diff Detail
- Repository
- rG LLVM Github Monorepo
Event Timeline
libcxx/docs/Status/RangesAlgorithms.csv | ||
---|---|---|
14–15 | Can you please add a link to this patch? | |
libcxx/include/__algorithm/ranges_lower_bound.h | ||
37 | I think for consistency with other patches, it should use longer names (_Iterator, etc.). | |
42 | Nit: can you split this function into ~3 logical blocks? I find it a little hard(er) to read as a monolithic block of code. I'd suggest a blank line before while (to separate the initial setup from the main part), before the return statement (similarly to make the main part stand out), and either before or after the call to std::advance. | |
libcxx/include/__algorithm/ranges_upper_bound.h | ||
39 | Nit: similar to another patch, can you name this lambda something like __comp_lhs_rhs_swapped? (or just __comp_swapped) | |
libcxx/test/std/algorithms/alg.sorting/alg.binary.search/binary.search/ranges.binary_search.pass.cpp | ||
3 | (please note that many comments in this file apply to other test files as well) | |
72 | Similar to another patch, it probably makes sense to test that the comparator works when:
| |
133 | I'd add tests for:
| |
178 | Please add return 0. | |
libcxx/test/std/algorithms/alg.sorting/alg.binary.search/upper.bound/ranges.upper_bound.pass.cpp | ||
66 | Optional: perhaps check the return type here as well? |
libcxx/include/__algorithm/ranges_lower_bound.h | ||
---|---|---|
39 | Have you considered sharing the implementation of the algorithm between the ranges and non-ranges versions? This algorithm, while not very complicated, isn't trivial and is quite prone to off-by-one errors. Personally, I'm on the fence. (cc'ing @ldionne as well) |
libcxx/include/__algorithm/ranges_lower_bound.h | ||
---|---|---|
39 | Yes, but I think it's simple enough to not warrant sharing the implementation, but I'm on the fence too. | |
libcxx/test/std/algorithms/alg.sorting/alg.binary.search/binary.search/ranges.binary_search.pass.cpp | ||
72 | I'll add the convertible to bool tests once D122011 landed. Taking only non-const lvalues doesn't model indirect_strict_weak_order. |
In general looks good, but some remarks.
libcxx/include/CMakeLists.txt | ||
---|---|---|
82 | Were these files not already in CMakeLists.txt? | |
libcxx/test/std/algorithms/alg.sorting/alg.binary.search/binary.search/ranges.binary_search.pass.cpp | ||
63 | assert(base(ret)); looks wrong, I expect this should be assert(ret); | |
164 | Please add some tests for the complexity requirements for comparisons and projections. |
libcxx/include/CMakeLists.txt | ||
---|---|---|
82 | I guess you mean the find things? Must have been a merge conflict. | |
libcxx/test/std/algorithms/alg.sorting/alg.binary.search/binary.search/ranges.binary_search.pass.cpp | ||
164 | How exactly would you like them to look like? The standard says that the complexity is log_2(last - first) + O(1) How could I (without a statistical analysis) find out what the constant is? |
LGTM. Please check with @ldionne regarding whether it's best to share the implementation of the algorithm with the non-ranges version.
LGTM! But please address @var-const's request before landing.
libcxx/include/__algorithm/ranges_lower_bound.h | ||
---|---|---|
39 | I don't have a strong opinion whether to combine these two versions or keep them separate. std::invoke requires C++17, but our implementation of std::invoke uses std::__invoke requires C++11. So it seems to be an issue to use invoke on C++03. | |
libcxx/test/std/algorithms/alg.sorting/alg.binary.search/binary.search/ranges.binary_search.pass.cpp | ||
164 | Good point O(1) makes it hard :-( std::search's O(1) can differ from std::lower_bound's O(1). |
Sorry for being MIA, but I do have a few comments. Some of them may apply to algorithms that we've shipped previously as well.
libcxx/include/__algorithm/ranges_lower_bound.h | ||
---|---|---|
39 | I would really like to share this with the implementation in <__algorithm/__lower_bound.h>. I suspect it's not too difficult to do that, and we'll avoid duplicating code. | |
41 | Shouldn't this be ranges::distance? | |
libcxx/include/__algorithm/ranges_upper_bound.h | ||
50 | Should we be forwarding __lhs and __rhs? I think we're not losing anything if we do it, and I suspect we might be required to (if so, then we're also missing a test case). | |
51 | This is not ADL-proof. Same above. I think we should have ADL proofing tests for ranges algorithms. |
- Address comments
libcxx/include/__algorithm/ranges_upper_bound.h | ||
---|---|---|
50 | indirect_strict_weak_order requires that _Comp is equality preserving (meaning that cv ref qualifications still give the same output) and it's callable with l- and rvalues, so only the const-ness has to stay (unless I missed some requirement). Because of this I see no reason to make the code harder to read. I think this should actually just be auto& __lhs, auto& __rhs. | |
51 | The design of projected isn't ADL-proof, so we can't add tests. If you want more context see https://wg21.link/P2538. |
libcxx/include/__algorithm/ranges_upper_bound.h | ||
---|---|---|
50 | Ignore the last part. Using auto& would just make the implementation weirder. |
LGTM with my comments addressed. I don't think I need to see this again whatever you do for the auto const& issue.
libcxx/include/__algorithm/equal_range.h | ||
---|---|---|
54 | Can you please make sure that we have a test for the STL classic algorithms that will fail if you make a copy of __comp here? You can just add auto __dummy = __comp; (void)__dummy; to test it. | |
libcxx/include/__algorithm/lower_bound.h | ||
47–48 | Can you please add a libc++ specific test to check that we diagnose if you pass something that isn't a proper function object to lower_bound (and the other algorithms in this patch too), please? | |
libcxx/include/__algorithm/ranges_upper_bound.h | ||
50 | If it's true that cv-qualification doesn't matter, perhaps we should make this auto const& instead? That definitely removes a mental burden when reading this sort of code, IMO. |
- Address comments
libcxx/include/__algorithm/equal_range.h | ||
---|---|---|
54 | We've got libcxx/algorithms/robust_against_copying_comparators.pass.cpp. |
Amazing tests. Unfortunately, this change causes breakages in std::lower_bound because ranges::distance is not a drop-in replacement for std::distance, and that breaks existing code as it switches between C++17 and C++20.
I'm working on minimizing a reproducer.
libcxx/test/std/algorithms/alg.sorting/alg.binary.search/binary.search/ranges.binary_search.pass.cpp | ||
---|---|---|
9 | Great tests BTW. |
Can you please add a link to this patch?