[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 #13 from Jonathan Wakely <redi at gcc dot gnu.org> ---
(In reply to Marc Glisse from comment #11)
> Or one could (not legal) directly start a new allocation, copy the beginning
> of the vector, append the range, then append the end of the vector. Or a
> combination of all that: first try appending the range to the vector. If
> that works without reallocating, rotate. If a reallocation is necessary,
> 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.

Or something like this (which would require lots of <algorithm> for
std::rotate):

--- a/libstdc++-v3/include/bits/vector.tcc
+++ b/libstdc++-v3/include/bits/vector.tcc
@@ -617,10 +617,28 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       _M_range_insert(iterator __pos, _InputIterator __first,
                      _InputIterator __last, std::input_iterator_tag)
       {
-       for (; __first != __last; ++__first)
+       const size_type __orig_size = size();
+       pointer& __finish = this->_M_impl._M_finish;
+       while (__finish != this->_M_impl._M_end_of_storage
+           && __first != __last)
          {
-           __pos = insert(__pos, *__first);
-           ++__pos;
+           _Alloc_traits::construct(_M_get_Tp_allocator(),
+                                    std::__addressof(*__finish),
+                                    *__first);
+           ++__finish;
+           ++__first;
+         }
+
+       if (__first != __last)
+         {
+           const size_type __elems_before = __pos - begin();
+           vector __tmp(__first, __last, _M_get_Tp_allocator());
+           reserve(size() + __tmp.size());
+           iterator __prev_end = end();
+           insert(__prev_end,
+                  _GLIBCXX_MAKE_MOVE_ITERATOR(__tmp.begin()),
+                  _GLIBCXX_MAKE_MOVE_ITERATOR(__tmp.end()));
+           std::rotate(begin() + __elems_before, __prev_end, end());
          }
       }