Possible missed optimization for non-common bidirectional ranges in `<algorithm>`

[vmichal]

This issue is an extension of #5886 (and the corresponding PR #5887), as it appears that there are other locations where _Bidi_common<_It, _Se> is checked, where I believe the less strict bidirectional_iterator<_It> would suffice.

In the following cases, for a non-common range with bidirectional iterators, the search runs from the beginning instead of from the end, resulting in more applications of projection and predicate than necessary.

_Find_last_unchecked

STL/stl/inc/algorithm

Line 3439 in 5459853

if constexpr (_Bidi_common<_It, _Se>) {

_Find_last_if_unchecked

STL/stl/inc/algorithm

Line 3522 in 5459853

if constexpr (_Bidi_common<_It, _Se>) {

However I have not checked all references to _Bidi_common (e.g. in _Shift_right_impl), so there could be more.

Note that _Partition_unchecked is already covered by #5886

STL/stl/inc/algorithm

Line 6989 in 5459853

if constexpr (_Bidi_common<_It, _Se>) {

I can look into it, but I would like someone with more experience to first confirm that I have not come to an incorrect conclusion.

[mirion-dev]

I think using _Bidi_common is reasonable here. std::ranges::next(first, last) would incur its own overhead for non-random-access iterators or non-sized sentinels. Unlike partition, the standard does not mandate the bidirectional optimization for find_last{_if}.