On 2/4/20 3:07 AM, Patrick Palka wrote:
This patch implements the C++20 ranges overloads for the algorithms in
[algorithms]. Most of the algorithms were reimplemented, with each of their
implementations very closely following the existing implementation in
bits/stl_algo.h and bits/stl_algobase.h. The reason for reimplementing most of
the algorithms instead of forwarding to their STL-style overload is because
forwarding cannot be conformantly and efficiently performed for algorithms that
operate on non-random-access iterators.
Why ? Do you have a clear counter-example ?
Maybe at the time you wrote this code those algos were not constexpr
qualified, but they are now.
But algorithms that operate on random
access iterators can safely and efficiently be forwarded to the STL-style
implementation, and this patch does so for push_heap, pop_heap, make_heap,
sort_heap, sort, stable_sort, nth_element, inplace_merge and stable_partition.
IMHO we should try as much as possible to forward to algos in
stl_algobase.h.
Those are highly customized and will be even more in the future when
some patches I have on my side will be integrated (I hope).
If you do so you won't have to care much about _GLIBCXX_DEBUG iterators.
What's missing from this patch is debug-iterator and container specializations
that are present for some of the STL-style algorithms that need to be ported
over to the ranges algos. I marked them missing at TODO comments. There are
also some other minor outstanding TODOs.
The code that could use the most thorough review is ranges::__copy_or_move,
ranges::__copy_or_move_backward, ranges::__equal and
ranges::__lexicographical_compare. In the tests, I tried to test the interface
of each new overload, as well as the correctness of the new implementation.
