# 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

### Event Timeline

libcxx/test/std/algorithms/alg.sorting/alg.sort/stable.sort/ranges.stable.sort.pass.cpp | ||
---|---|---|

139 | For some reason, the compiler fails to parse this construct as an initializer list of | |

libcxx/test/support/almost_satisfies_types.h | ||

304 ↗ | (On Diff #437076) | This is copied from the |

Thanks for working on this! Some small remarks.

libcxx/include/__algorithm/ranges_stable_sort.h | ||
---|---|---|

39 | Please remove the | |

libcxx/include/__algorithm/stable_sort.h | ||

224 | While you're at it. | |

libcxx/test/std/algorithms/alg.sorting/alg.sort/stable.sort/ranges.stable.sort.pass.cpp | ||

140 | I would suggest to make the | |

151 | Is the trailing comma allowed? | |

169 | It would be good to validate stability in these tests too. | |

247 | 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. | |

256 | Interesting since it's possible to allocate memory in |

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 | ||

140 | I started with that, but then I had the idea of enumerating each duplicate value instead (read those | |

151 | Yes. Removed it for redundancy. | |

169 | To clarify, do you mean all the tests in | |

247 | Similar to the - we can use the exact number of operations our implementation happens to perform (we have some precedent in e.g.
`test/libcxx/algorithms/alg.sorting/alg.heap.operations/make.heap/complexity.pass.cpp`), but that would make it libc++-specific and, IMO, has limited usefulness; - simply testing for
`num_operations < N*log(N)`isn't going to work because it's actually`k*N*log(N)`, where`k`is an arbitrary constant; - the "proper" way would be to test with increasingly large inputs and applying some math to calculate the growth factor, but that seems like a sizable project in itself, even assuming it's worth the implementation effort.
| |

256 | I know that P0202 was adding
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–44 | Why is this not | |

43 | Maybe name it | |

45–46 | This probably also applies to | |

libcxx/include/__algorithm/stable_sort.h | ||

225 | Would you be interested in removing | |

libcxx/test/std/algorithms/alg.sorting/alg.sort/stable.sort/ranges.stable.sort.pass.cpp | ||

130–133 | As always, I think this | |

138 | Does it not work to just use | |

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 | ||
---|---|---|

140 | How do you feel about making the Since the same constants written the same in the source there shouldn't be an issue with floating point rounding. | |

151 | TIL, fun that it's allowed in some places. | |

169 | I think it's mainly important for this test and the ones below. | |

247 | 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. | |

256 | 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–44 | Thanks for spotting! | |

43 | I somewhat prefer the current version (name of the algorithm + | |

45–46 | Thanks! Fixed both. | |

libcxx/include/__algorithm/stable_sort.h | ||

225 | 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). | |

140 | I really like this, thanks -- makes the intention a lot clearer and looks better, too. | |

188 | It's used to compare check the assert((in == std::array{A{1}, A{2}, A{3}})); Perhaps I'm missing something? | |

214 | Same -- it's necessary to compare arrays. | |

247 | 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 | |

256 | 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. |