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.
