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

[Jonathan Wakely]

On 13/02/20 19:07 +0100, François Dumont wrote:
>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.

It has nothing to do with constexpr.

If you call a ranges algo with an iterator and a sentinel that is a
different type to the iterator, you can't call the old STL algo unless
you can efficiently get an end iterator that refers to the same
position as the sentinel. For random access iterators that is:

auto last2 = first + (last - first);

But for non-random access iterators finding the distance between first
and last is not possible in O(1), and incrementing first by that
distance is also not possible in O(1).

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

That would not be conforming in many cases.

The old code assumes iterators can be copied. It assumes they have an
iterator_category. It assumes they have operator->(). Most
importantly, it assumes the begin and end iterators have the same
type.

The old algorithms do tag dispatching, which adds function call
overhead at run-time and overload resolution overhead at compile-time.

The new constrained algos can be implemented much more cleanly using
if-constexpr and the new iterator concepts.

There are very good reasons to reimplement the new ranges algos.

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