[PATCH 2/3] libstdc++: Implement C++20 constrained algorithms

[François Dumont]

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