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

François Dumont frs.dumont@gmail.com
Fri Feb 14 06:00:00 GMT 2020


Thanks for those additional information.

I still think that the same way we rely on STL algos for 
push_heap/pop_heap/... we should do it for copy/move/... from 
stl_algobase.h for RAI.

In fact range algos that are already trying to call C functions should 
just try to call the STL counterparts which will then forward to C 
functions.

On 2/13/20 8:00 PM, Jonathan Wakely wrote:
> 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.
>>>
>>
>



More information about the Libstdc++ mailing list