[Bug libstdc++/81476] severe slow-down with range-v3 library compared to clang

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

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=81476

--- Comment #14 from Jonathan Wakely <redi at gcc dot gnu.org> ---
Oops, the rotate needs to be done unconditionally.

The advantage of doing it as in comment 13, rather than:

(In reply to Marc Glisse from comment #11)
> switch to the "new allocation" strategy, create a new vector, copy the
> beginning of the vector, copy what we already inserted at the end, append
> the rest of the inputrange, copy the rest of the original vector, and
> finally adopt this new vector.

is that when inserting the inputrange causes reallocations we only have to
transfer the already inserted elements of the inputrange to the new storage,
not the elements preceding the insertion point ("the beginning of the vector"
and "what we already inserted at the end").

Another solution would be to grow the vector exponentially during range
insertion from input iterators, as we do for a push_back. Either manually in
_M_range_insert<_InputIterator> or in _M_realloc_insert.

I think at the moment I prefer comment 12 (but using
_GLIBCXX_MAKE_MOVE_ITERATOR to avoid copies when possible).