[PATCH] Optimize inserting value_type into std::vector

[Jonathan Wakely]

On 15/06/16 11:34 +0100, Jonathan Wakely wrote:
>On 15/06/16 11:15 +0100, Jonathan Wakely wrote:
>>	* include/bits/stl_vector.h (vector::_S_insert_aux_assign): Define
>>	new overloaded functions.
>>	* include/bits/vector.tcc (vector::_M_insert_aux): Use new functions
>>	to avoid creating a redundant temporary.
>>	* testsuite/23_containers/vector/modifiers/insert_vs_emplace.cc: New
>>	test.
>>
>>Tested x86_64-linux.
>>
>>This improves our performance on Howard Hinnant's "insert vs emplace"
>>experiment at
>>http://htmlpreview.github.io/?https://github.com/HowardHinnant/papers/blob/master/insert_vs_emplace.html
>>
>>With this small change there is no difference between emplacing or
>>using the relevant insert / push_back function. That also means we
>>beat libc++ in some cases, making us the bestest, whoo!
>
>We still lose to libc++ in one case. For the "lvalue no reallocation"
>test our insert and emplace are equal to libc++'s emplace, but
>libc++'s insert is even better.

Libc++'s insert(const_iterator, const value_type&) is *really* clever.
It notices when the object to insert is an element of the vector, and
then works out where its updated position would be after shifting the
existing elements along, and then copies from the new position. That
avoids the copy we make upfront to handle that case safely. Our
approach is inefficient for the common case where the object *isn't*
in the vector.

I guess it's something like:

  void
  insert(const_iterator pos, const value_type& x)
  {
    if (cpacity() == size())
      {
        // reallocate and insert ...
        return;
      }
    auto it = end() - 1;
    *end() = std::move(*it);
    ++this->_M_impl._M_finish;
    const value_type* from = std::addressof(x);
    for (; it != pos; --it)
    {
      auto prev = it - 1;
      *it = std::move(*prev);
      if (std::addressof(*prev) == from)
        ++from;
    }
    *pos = *from;
  }

Clever.