# Details

- Reviewers
jdoerfert huixie90 philnik ldionne - Group Reviewers
Restricted Project - Commits
- rG5dd19ada571b: [libc++][ranges] Implement `ranges::partial_sort`.

# Diff Detail

- Repository
- rG LLVM Github Monorepo

### Event Timeline

Remove unnecessary underscores from names.

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

30 ↗ | (On Diff #441918) | I took a stab at consolidating the two -- the only change I did (other than adding new functions) is using the tag approach for reasons outlined above (more generic). Please let me know what you think. |

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

82 ↗ | (On Diff #443127) | is it just |

Could you maybe move the `_IterOps` changes into it's own PR? There are quite a few changes unrelated to `ranges::partial_sort` in here.

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

30 ↗ | (On Diff #441918) | FWIW we can still change it later if we want to. But for now, I don't think you are using the |

libcxx/include/__algorithm/iterator_operations.h | ||

38 ↗ | (On Diff #443127) | I think you have to use |

68 ↗ | (On Diff #443127) | Why is the |

73 ↗ | (On Diff #443127) | Why aren't this one and the next also marked |

82 ↗ | (On Diff #443127) | +1 |

libcxx/include/__algorithm/lower_bound.h | ||

30 ↗ | (On Diff #443127) | The name |

@philnik I have moved the changes to `iterator_operations.h` to https://reviews.llvm.org/D129390 and addressed the related feedback there.

It's true that we can go for the more generic version later, but it also gives me a certain peace of mind that no matter what kind of issues may come up from sharing the same implementation, they can be worked around (even if they turn out not to be related to iterator operations).

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

68 ↗ | (On Diff #443127) | This is to make the implementation as similar as possible to the actual C++20 |

libcxx/include/__algorithm/lower_bound.h | ||

30 ↗ | (On Diff #443127) | How about something like |

libcxx/include/__algorithm/sift_down.h | ||

42 ↗ | (On Diff #441918) | Thank you! |

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

66–68 ↗ | (On Diff #443127) | FWIW, value_type temp = std::move(*it); because auto temp = std::move(*it); does the wrong thing for So here this explicit return type does the conversion sometimes and probably IS what the caller wants |

libcxx/include/__algorithm/lower_bound.h | ||

30 ↗ | (On Diff #443127) | Or |

libcxx/include/__algorithm/make_heap.h | ||

30 ↗ | (On Diff #443127) | For C++20 algorithms, we should use the (Note this applies to all other usages of |

libcxx/include/__algorithm/pop_heap.h | ||

28–29 | For C++20 ranges algorithms, we should use This applies to all other places we use | |

libcxx/test/std/algorithms/alg.sorting/alg.sort/partial.sort/ranges_partial_sort.pass.cpp | ||

282 | btw, you can rebase and try sorting the |

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

30 ↗ | (On Diff #443127) | Actually, it is fine for this algorithm to use iterator_traits since the input are required to model c++20 random_access_iterator and C++ 20 random_access_iterator implies c++17 input iterator and that makes sure that iterator_traits exists and consistent with c++20’s iter_differnece_t (and iter_value_t for the value_type) I think this can be a problem only in algorithms that take c++20 input iterators, because c++ 20 input_iterators can have empty iterator_traits |

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

30 ↗ | (On Diff #443127) | I really like "policy" -- went with |

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

30 ↗ | (On Diff #443127) | Thanks a lot for spotting this. I've added checking algorithms that take input iterators to my backlog. |

Rebase on `main` (including the `iterator_operations.h` changes from

https://reviews.llvm.org/D129390).

libcxx/test/std/algorithms/alg.sorting/alg.sort/partial.sort/ranges_partial_sort.pass.cpp | ||
---|---|---|

282 | I'd prefer to do this in a follow-up once this lands. |

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

32 | Can we have a naming convention for this? It would be good to distinguish the purpose of It would be good to distinguish - helper function purely for implementation of the classic algorithm (perhaps with some assumptions that the iterators are classic iterators)
- helper function purely for the implementation of ranges algorithm (perhaps with assumptions that iterators are c++20 iterators)
- helper function that is meant to be shared between the classic algorithm and the ranges algorithm
- helper function can be reused any other algorithms
The reason why I was asking is that when I implemented other algorithms and I'd like to call | |

37 | question. why do we need |

Mostly nits, but I'd like to see the portability trap addressed. Did you add any `move`s in other classic algorithms? If yes, please also update them.

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

36 | Could you add a TODO to remove this and update | |

100–101 | Could you either not move these or | |

libcxx/include/__algorithm/pop_heap.h | ||

62 | Pre-existing: Please also remove the | |

libcxx/include/__algorithm/push_heap.h | ||

66 | Also here. | |

libcxx/include/__algorithm/sort_heap.h | ||

50–51 | Same here. | |

libcxx/test/libcxx/algorithms/partial_sort_stability.pass.cpp | ||

37–38 | Shouldn't this be | |

libcxx/test/std/algorithms/alg.sorting/alg.sort/partial.sort/ranges_partial_sort.pass.cpp | ||

71–73 | Could you rename these to | |

89 | Why aren't you using | |

106–136 | Could you put this into a function? The calls below look really weird. | |

158–160 | Why aren't these in a single line? | |

210–246 | This should be unnecessary now, right? | |

248–284 | And this. |

Address feedback (partial).

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

32 | My intention was for I'm not sure the finer-grained distinction is necessary -- from what I've seen, we're rewriting all the internal functions to be agnostic to whether they're invoked from a classic or a range algorithm. Please let me know if there's an example where it would be helpful. Note that in this case, I can't easily combine these two functions -- | |

37 | It was unnecessary, thanks for spotting it. | |

42–48 | Added a TODO -- this will be much easier to implement once | |

libcxx/test/std/algorithms/alg.sorting/alg.sort/partial.sort/ranges_partial_sort.pass.cpp | ||

71–73 | Personally, I much prefer the shorter names in cases like this (where the meaning is easy to understand because the pattern of having | |

89 | Because of | |

106–136 | This was suggested by @ldionne. The advantage is to have all the related code in the same scope, i.e. to avoid the details spilling out of the function. | |

158–160 | I find it easier to read this way. Reverted. |

Note: this was rebased on https://reviews.llvm.org/D129823 which significantly reduced the delta.

libcxx/test/std/algorithms/alg.sorting/alg.sort/partial.sort/ranges_partial_sort.pass.cpp | ||
---|---|---|

106–136 | By that logic, shouldn't everything be in nested lambdas in tests? You aren't capturing anything, so I really don't see how that's better than having it as an extra function. What exactly do you think is "spilling out of the function"? |

libcxx/test/std/algorithms/alg.sorting/alg.sort/partial.sort/ranges_partial_sort.pass.cpp | ||
---|---|---|

106–136 | Let's leave this debate for another day, after the release. Changed. |

libcxx/test/std/algorithms/alg.sorting/alg.sort/partial.sort/ranges_partial_sort.pass.cpp | ||
---|---|---|

106–136 |
FWIW the idea is that a top-level function exposes a name, whereas a lambda doesn't because it's a local variable in another scope. It makes it clearer that it's only an implementation detail of e.g. |

This LGTM at a glance, but I'll leave final approval to the other reviewers who had comments.

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

100–101 | Ah, this is a very good catch. Added static assertions and added auditing those to my backlog. |