[Bug libstdc++/111685] Segfault while sorting on array element address

["redi at gcc dot gnu.org" <gcc-bugzilla@gcc.gnu.org>]

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.