[PATCH] Optimize inserting value_type into std::vector

[Yubin Ruan]

Hi, I find the libc++'s `insert(const_iterator, const value_type&)` that 
you mentioned really interesting(and really clever). Just need some help 
to understand some libstdc++ specified code:

 >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;

my question is in regard to the two lines below

 >   *end() = std::move(*it);
 >   ++this->_M_impl._M_finish;

Isn't it illegal to dereference `end()` ?
what does `++this->_M_impl._M_finish` do here ?
Any libstdc++ specified stuff here ?
I haven't read through all of the libstdc++ source, hope that anyone can 
help me understand it or give me some hints.

 >   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;

really clever.

 >   }
 >   *pos = *from;
 > }
 >
 >Clever.


Thanks,
Ruan