[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