https://gcc.gnu.org/bugzilla/show_bug.cgi?id=111685
--- Comment #8 from Jonathan Wakely <redi at gcc dot gnu.org> ---
The standard only defines sorting in terms of comparisons on "every iterator i
pointing to the sequence", which seems to preclude using a temporary object on
the stack that is outside the sequence.
That said, the comparison object seems like nonsense and I don't see any great
need to support this case.
We could define the linear insertion in terms of swaps, something like:
template<typename _RandomAccessIterator, typename _Compare>
_GLIBCXX20_CONSTEXPR
void
__unguarded_linear_insert(_RandomAccessIterator __last,
_Compare __comp)
{
_RandomAccessIterator __next = __last;
--__next;
while (__comp(*__last, __next))
{
std::iter_swap(__last, __next);
__last = __next;
--__next;
}
}
However, that would perform 3N copies, where the current code does N.
Alternatively, find the partition point first and then do N copies, something
like:
template<typename _RandomAccessIterator, typename _Compare>
_GLIBCXX20_CONSTEXPR
void
__unguarded_linear_insert(_RandomAccessIterator __last,
_Compare __comp)
{
_RandomAccessIterator __next = __last;
--__next;
while (__comp(*__last, __next))
--__next;
typename iterator_traits<_RandomAccessIterator>::value_type
__val = _GLIBCXX_MOVE(*__last);
_RandomAccessIterator __prev = __last;
--__prev;
while (__prev != __next)
{
*__last = _GLIBCXX_MOVE(*__prev);
__last = __prev;
}
*__last = _GLIBCXX_MOVE(__val);
}
But this traverses the sequence twice, where the original does it in one
traversal.
