Possible missed optimization for non-common bidirectional ranges in `<algorithm>`
Nobody has claimed this yet.
- Dominant language
- C++
- Stars
- 11.1k
- Forks
- 1.7k
- Avg merge
- 4d 15h
- Merged PRs (30d)
- 22
Description
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
https://github.com/microsoft/STL/blob/5459853bf78ceef1137d845bfeca98f658659691/stl/inc/algorithm#L3439
_Find_last_if_unchecked
https://github.com/microsoft/STL/blob/5459853bf78ceef1137d845bfeca98f658659691/stl/inc/algorithm#L3522
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
https://github.com/microsoft/STL/blob/5459853bf78ceef1137d845bfeca98f658659691/stl/inc/algorithm#L6989
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.
Contributor guide
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
Research direction
Start in stl/inc/algorithm at the _Find_last_unchecked and _Find_last_if_unchecked locations, and compare the prior discussion in #5886 and PR #5887. Inspect other _Bidi_common references, including _Shift_right_impl, and verify that non-common bidirectional ranges search from the end with no unnecessary projection or predicate applications.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- cpp
- Domain
- performance
- Issue type
- Bug
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 42/100