Stl: <algorithm>: Consider using *_Prev_iter(it) instead of *(it - 1)

[StephanTLavavej]

We have a helper function that's a simplified form of std::prev:

https://github.com/microsoft/STL/blob/fd04f77dd217a7502c77e0cbf45e24fcb84ed17c/stl/inc/xutility#L1638-L1641

We also have algorithms that need to access the element immediately before where an iterator points to:

https://github.com/microsoft/STL/blob/fd04f77dd217a7502c77e0cbf45e24fcb84ed17c/stl/inc/algorithm#L3459

It may be more efficient to use _Prev_iter for user-defined iterators where decrementing is cheaper than general-purpose subtraction. There are several occurrences in the STL (more after #464 is merged). Currently, I see no occurrences of + 1 that could benefit from _Next_iter.

[BillyONeal]

I suspect we don't see _Next_iter cases because most algorithms that do that need to work with forward iterators that already need to advance / next.

I believe I found all the nexts and replaced them with _Next_iter when I added _Next_iter, but probably good to audit for missed ones when resolving this PR.

[StephanTLavavej]

I just checked and I don't see any occurrences of prev or next that should be changed, so I think that's fine.

[JeanPhilippeKernel]

@StephanTLavavej can I work on this ?

[CaseyCarter]

@StephanTLavavej can I work on this ?

* making cat sounds * Yes! I, @StephanTLavavej, assure you that we are happy for you to work on this! 😸

[JeanPhilippeKernel]

in Algorithm.h , I found the following algorithms that are candidate of this change :
prev_permutation, next_permutation, _Partition_by_median_guess_unchecked,
_OutIt reverse_copy(_BidIt _First, _BidIt _Last, _OutIt _Dest)

[CaseyCarter]

The rationale "It may be more efficient to use _Prev_iter for user-defined iterators where decrementing is cheaper than general-purpose subtraction" has nothing to do with dereferencing, so I can't help but wonder why this issue is "Consider using *_Prev_iter(it) instead of *(it - 1)" instead of "Consider using _Prev_iter(it) or _Next_iter(it) instead of it - 1 or it + 1 (respectively)".

[BillyONeal]

@CaseyCarter I don't believe there were any of those cases left.

[CaseyCarter]

Here are the occurrences in <algorithm>:
https://github.com/microsoft/STL/blob/430b569d0a5157d7c95251668fc4607041bdf907/stl/inc/algorithm#L1546

https://github.com/microsoft/STL/blob/430b569d0a5157d7c95251668fc4607041bdf907/stl/inc/algorithm#L1626

https://github.com/microsoft/STL/blob/430b569d0a5157d7c95251668fc4607041bdf907/stl/inc/algorithm#L3471

https://github.com/microsoft/STL/blob/430b569d0a5157d7c95251668fc4607041bdf907/stl/inc/algorithm#L3506

https://github.com/microsoft/STL/blob/430b569d0a5157d7c95251668fc4607041bdf907/stl/inc/algorithm#L3763

https://github.com/microsoft/STL/blob/430b569d0a5157d7c95251668fc4607041bdf907/stl/inc/algorithm#L3765

https://github.com/microsoft/STL/blob/430b569d0a5157d7c95251668fc4607041bdf907/stl/inc/algorithm#L3795-L3796

And one in <deque> so poor <algorithm> won't feel singled out:

https://github.com/microsoft/STL/blob/430b569d0a5157d7c95251668fc4607041bdf907/stl/inc/deque#L1274

[BillyONeal]

@CaseyCarter: OK then we missed some

[StephanTLavavej]

I filed #802 to track the remaining cases (with a standalone explanation). I also noticed that the two occurrences of _Backout._Last - 1 are _Ptr_ty which is a raw pointer; I don't believe those should be changed.