Re: [PATCH] Optimize inserting value_type into std::vector

[Yubin Ruan <ablacktshirt at gmail dot com>]

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