Details
- Reviewers
jdoerfert philnik ldionne Mordante - Group Reviewers
Restricted Project - Commits
- rG94c7b89fe5b0: [libc++][ranges] Implement `ranges::stable_sort`.
Diff Detail
- Repository
- rG LLVM Github Monorepo
Unit Tests
Event Timeline
Thanks for working on this! Some small remarks.
libcxx/include/__algorithm/ranges_stable_sort.h | ||
---|---|---|
39 | Please remove the constexpr | |
libcxx/include/__algorithm/stable_sort.h | ||
211 | While you're at it. | |
libcxx/test/std/algorithms/alg.sorting/alg.sort/stable.sort/ranges.stable.sort.pass.cpp | ||
139 | I would suggest to make the original_order member a simple integer sequence: 1, 2, 3, etc. That makes it easier to verify whether the output is correct. Identical values will have incrementing values. | |
150 | Is the trailing comma allowed? | |
168 | It would be good to validate stability in these tests too. | |
246 | Here we can validate complexity. Obviously implementations can make different choices regarding when there's not "enough extra memory" but we can test the N log (N) for a small number of items. | |
255 | Interesting since it's possible to allocate memory in constexpr functions. |
Rebase on main, apply changes from the ranges::sort patch, address feedback.
libcxx/include/__algorithm/ranges_stable_sort.h | ||
---|---|---|
39 | Thanks! | |
libcxx/test/std/algorithms/alg.sorting/alg.sort/stable.sort/ranges.stable.sort.pass.cpp | ||
139 | I started with that, but then I had the idea of enumerating each duplicate value instead (read those 31, 32, 33 as 3.1, 3.2, 3.3, etc.). I think it makes it more readable because following the numbering within a duplicate is much easier than following the numbering across all the elements. What do you think? | |
150 | Yes. Removed it for redundancy. | |
168 | To clarify, do you mean all the tests in test()? Or just the tests with a custom comparator? | |
246 | Similar to the sort patch, I don't think we have a great way of doing this:
| |
255 | I know that P0202 was adding constexpr to algorithms. At the time (in 2017), making stable_sort constexpr was infeasible:
I don't know if there's been any work in that direction since then. Perhaps it's ripe for a new paper? |
Nothing major, but I'd like to take another look after my comments have been addressed.
libcxx/include/__algorithm/ranges_stable_sort.h | ||
---|---|---|
42–43 | Why is this not static but instead marked const? | |
43 | Maybe name it __ranges_stable_sort_impl? | |
46 | This probably also applies to ranges::sort. | |
libcxx/include/__algorithm/stable_sort.h | ||
212 | Would you be interested in removing std::get_temporary_buffer and std::return_temporary_buffer in a follow-up patch? It's deprecated and just forwards to new and delete. | |
libcxx/test/std/algorithms/alg.sorting/alg.sort/stable.sort/ranges.stable.sort.pass.cpp | ||
130–133 | As always, I think this should work. I'm not yet fluent in spaceship operator. | |
138 | Does it not work to just use std::array orig_in = {V{10, 101}, ...}? | |
188 | Isn't this be unnecessary and even counter-productive? | |
214 | Again, I don't think this should be here. |
I'll let others give final approval, but this LGTM.
libcxx/docs/Status/RangesAlgorithms.csv | ||
---|---|---|
77 | Once you commit this, it'll be done, not under review. |
libcxx/test/std/algorithms/alg.sorting/alg.sort/stable.sort/ranges.stable.sort.pass.cpp | ||
---|---|---|
139 | How do you feel about making the original_order a double and use 3.1? Since the same constants written the same in the source there shouldn't be an issue with floating point rounding. | |
150 | TIL, fun that it's allowed in some places. | |
168 | I think it's mainly important for this test and the ones below. | |
246 | Here http://eel.is/c++draft/stable.sort#5 lists the exact number of comparisons to do and that the number of projections is double of that. So I think we can use that value as an upper bound, for example with N = 10. | |
255 | I didn't investigate the reason, but this is indeed what I expected :-) Based on the unanimous consent in this poll https://github.com/cplusplus/papers/issues/1222#issuecomment-1159203566 |
Address feedback
libcxx/include/__algorithm/ranges_stable_sort.h | ||
---|---|---|
42–43 | Thanks for spotting! | |
43 | I somewhat prefer the current version (name of the algorithm + fn to indicate that the function is contained within the function object + impl for disambiguation). I'd keep the current state unless you feel strongly about it. | |
46 | Thanks! Fixed both. | |
libcxx/include/__algorithm/stable_sort.h | ||
212 | Yes, I can do this in a follow-up (unless you beat me to it :) ). | |
libcxx/test/std/algorithms/alg.sorting/alg.sort/stable.sort/ranges.stable.sort.pass.cpp | ||
138 | It does -- it just gives an easy way to make sure both arrays have the same number of elements (since they are long, it's easier to make a mistake). | |
139 | I really like this, thanks -- makes the intention a lot clearer and looks better, too. | |
188 | It's used to compare check the in array after it's sorted: assert((in == std::array{A{1}, A{2}, A{3}})); Perhaps I'm missing something? | |
214 | Same -- it's necessary to compare arrays. | |
246 | I'd rather do this in a follow-up. I think perhaps it would be good to have a dedicated test file for this, similar to the robust_against_copying_*. | |
255 | Thanks for finding that paper! |
LGTM.
libcxx/test/std/algorithms/alg.sorting/alg.sort/stable.sort/ranges.stable.sort.pass.cpp | ||
---|---|---|
188 | Ah OK, I missed that. |
clang-format not found in user’s local PATH; not linting file.