`ranges::make_heap`;`ranges::push_heap`;`ranges::pop_heap`;`ranges::sort_heap`.

# Details

- Reviewers
jdoerfert huixie90 - Group Reviewers
Restricted Project - Commits
- rGc945bd0da652: [libc++][ranges] Implement modifying heap algorithms:

# Diff Detail

- Repository
- rG LLVM Github Monorepo

### Event Timeline

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

26 | Note: a few of these existing internal functions were missing the | |

41 | The main purpose of this function is to avoid leaking the | |

libcxx/include/__algorithm/ranges_pop_heap.h | ||

42 | Note: the Standard specifies that the range has to be non-empty in pop.heap: Preconditions: The range [first, last) is a valid **non-empty** heap However, our existing non-ranges version of |

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

26 | It must have been because they didn't want to | |

libcxx/include/__algorithm/ranges_make_heap.h | ||

47 | Probably applies elsewhere too. | |

libcxx/include/__algorithm/ranges_pop_heap.h | ||

42 | I would add a |

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

42 | Just to clarify, do you mean also adding it to the classic algorithm, or just to the ranges version? In the former case, would that require a release note? |

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

33 | I think | |

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

33 | I believe this needs to call | |

40 | same as above | |

43 | I think this does not do the right thing for ranges overload | |

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

35–37 | should use iter_move for | |

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

31 | This won't call the |

Address feedback.

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

33 | Thanks _a lot_ for finding this! I'd prefer to address this for all recently-implemented algorithms in a follow-up patch -- would that work for you? | |

libcxx/include/__algorithm/ranges_pop_heap.h | ||

42 | From offline discussion: we should add an assertion for the classic version as well. A release note is not necessary because it's undefined behavior. |

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

33 | Yes. sounds good to me. |

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

40 | I would suggest: - Swapping the names
`__make_heap_impl`and`__make_heap`. - Inlining the new
`__make_heap_impl`into the new`__make_heap` - Removing
`__make_heap_impl`, which isn't used anywhere anymore.
This gives: template <class _RandomAccessIterator, class _Compare> inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 void __make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare& __comp) { using _Comp_ref = typename __comp_ref_type<_Compare>::type; _Comp_ref __comp_ref = __comp; using difference_type = typename iterator_traits<_RandomAccessIterator>::difference_type; difference_type __n = __last - __first; if (__n > 1) { // start from the first parent, there is no need to consider children for (difference_type __start = (__n - 2) / 2; __start >= 0; --__start) { std::__sift_down<_Compare>(__first, __comp_ref, __n, __first + __start); } } } I think the same comment applies to all the other heap algorithms. | |

libcxx/test/std/algorithms/alg.sorting/alg.heap.operations/pop.heap/assert.pop_heap.pass.cpp | ||

10 ↗ | (On Diff #440683) | This is not needed -- we support basic assertions even when the "debug" mode is disabled. It's kind of messy right now (I'm in the process of cleaning that up), but basically Debug Mode = heavyweight checks that change ABI and/or complexity, and Assertions = lightweight checks that don't impact ABI/complexity. Debug Mode implies Assertions, but not the other way around. Here you only need to turn Assertions on with This comment applies to the other |

libcxx/test/std/algorithms/alg.sorting/alg.heap.operations/pop.heap/assert.ranges_pop_heap.pass.cpp | ||

15–24 ↗ | (On Diff #440683) | I am not sure that the full synopsis is useful here. Also applies to other |

Address feedback.

libcxx/test/std/algorithms/alg.sorting/alg.heap.operations/pop.heap/assert.pop_heap.pass.cpp | ||
---|---|---|

10 ↗ | (On Diff #440683) | Thanks! |

LGTM. I think you changed some signatures of some `__` function to take an "Tag" template argument in the `partial_sort` patch and this change might need to rebase that change?

libcxx/include/algorithm | ||
---|---|---|

276 | unresolved merge conflicts? |

In general looks good, but there are some small issues.

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

39–48 | Maybe drop the | |

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

39 | Can you put the | |

53 | You need to calculate | |

libcxx/include/__algorithm/ranges_pop_heap.h | ||

49 | Here | |

libcxx/test/std/algorithms/alg.sorting/alg.heap.operations/make.heap/ranges_make_heap.pass.cpp | ||

44 | I think it would be good to test with all iterator categories to see only random access and contiguous are valid. | |

218 | I really would like to see the maximum complexity to be validated for all heap operations. Especially since they all have different complexities. |

Address feedback, fix the CI.

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

39–48 | This seems like more than a purely mechanical change; I'd rather keep as is. | |

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

53 | Thanks! | |

libcxx/include/algorithm | ||

276 | Sorry about that! | |

libcxx/test/std/algorithms/alg.sorting/alg.heap.operations/make.heap/ranges_make_heap.pass.cpp | ||

44 | This would apply to every test range algorithm test and make it more verbose without increasing coverage. The types from | |

218 | I think this is valuable but I'd rather do a follow-up after we finished the initial implementation of range algorithms dedicated solely to testing complexity where possible. |

A few comments other than that LGTM! But I like to see the CI green before approving.

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

53 | I would prefer not to use | |

libcxx/test/std/algorithms/alg.sorting/alg.heap.operations/make.heap/ranges_make_heap.pass.cpp | ||

44 | Fair point. | |

218 | Should we add a note on the Status page as a reminder? |

libcxx/test/std/algorithms/alg.sorting/alg.heap.operations/make.heap/ranges_make_heap.pass.cpp | ||
---|---|---|

218 | I'll get to this pretty soon -- I don't think there should be need for a TODO. |