Now the only ones we're still missing from P0879 are sort and nth_element.
(nth_element is actually not trivial, because the existing implementation uses a goto label.)
Details
Details
- Reviewers
ldionne - Group Reviewers
Restricted Project - Commits
- rG5386aa26277f: [libc++] [P0879] constexpr heap and partial_sort algorithms
Diff Detail
Diff Detail
- Repository
- rG LLVM Github Monorepo
Event Timeline
Comment Actions
Generally looks good, I'm just asking for a bit more manual testing. Thanks a lot for working on this, I love that we're removing dependencies on <random>.
| libcxx/test/std/algorithms/alg.sorting/alg.heap.operations/make.heap/make_heap.pass.cpp | ||
|---|---|---|
| 26–45 | Can you please also add a few dumb hand-written test cases? You know I love those, right? Same for the other algorithms whose tests have been rewritten. | |
| libcxx/test/std/algorithms/alg.sorting/alg.heap.operations/make.heap/make_heap.pass.cpp | ||
|---|---|---|
| 26–45 | The trick for make_heap is that there are multiple possible outputs (theoretically): heapifying {1,2,3} might give you {3,1,2} or it might give you {3,2,1}. Both possibilities are equally conforming, even though I would guess that all implementations really do the same thing in practice. How much do we care about that? Do we mind hard-coding one of the outputs as "blessed"? Anyway, I'm resisting out of laziness — couldn't someone else add ad-hoc tests in a separate commit? — but maybe it'd help to see an example of the kind of test you're thinking of. I mean would it just be like this? TEST_CONSTEXPR_CXX20 bool test_simple() {
int a[] = {5,2,4,1,3};
std::push_heap(a, a+5);
int expected[] = {5,3,4,1,2};
assert(std::equal(a, a+5, expected, expected+5));
return true;
}
TEST_CONSTEXPR_CXX20 bool test_simple() {
int a[] = {5,2,4,1,3};
std::pop_heap(a, a+5);
int expected[] = {4,2,3,1,5};
assert(std::equal(a, a+5, expected, expected+5));
return true;
} | |
| libcxx/test/std/algorithms/alg.sorting/alg.heap.operations/make.heap/make_heap.pass.cpp | ||
|---|---|---|
| 26–45 | What I want is pretty trivial, just "unroll" a few cases from your loop so they are more explicit. I want the tests to be as dumb as possible, because imagine for instance if there was a mistake in your loop conditions and it never ran? The test would be useless. Having at least a few really dumb tests removes this sort of issue. Of course, there's a balance to strike. It doesn't always make sense to push too far with this sort of defensive behavior, but here it's pretty easy. For make_heap, something like this would satisfy me: {
int input[] = {3, 4, 1, 2, 5};
std::make_heap(Iter(input), Iter(input + 5));
assert(std::is_heap(input, input + 5));
std::pop_heap(input, input + 5); assert(input[4] == 5);
std::pop_heap(input, input + 4); assert(input[3] == 4);
std::pop_heap(input, input + 3); assert(input[2] == 3);
std::pop_heap(input, input + 2); assert(input[1] == 2);
std::pop_heap(input, input + 1); assert(input[0] == 1);
}You can put that inside test() itself. Does that make sense to you? Another way to think about this: Imagine you're a user and you try to use libc++'s std::make_heap. Imagine the very first and most basic thing you might write just to try it out. Wouldn't it be a huge embarrassment if it didn't work for some reason? Well, we might as well just check-in a few of the most common and dumb examples of how to use facilities to guard us from that. | |
Comment Actions
Poke buildbot. (The last build https://reviews.llvm.org/B86646 seems to have failed in a devopsy way, and clicking "Restart Builds" just tells me I haven't got permissions for that.)
Comment Actions
@ldionne: I don't think buildkite is ever going to finish a build here. I propose that you approve this revision and I just go again and land it, and we'll see what happens with the buildbots after that. (If it somehow does break buildbots, we can revert it.) Thoughts?
Comment Actions
I've restarted the failing job. I've been having a few issues with the builders for the past 2 days. The laptops are being overworked :-)
Let's land this once https://buildkite.com/llvm-project/libcxx-ci/builds/1140 has succeeded.
Can you please also add a few dumb hand-written test cases? You know I love those, right?
Same for the other algorithms whose tests have been rewritten.