[C++] [STL] vector.insert cache affinity concern.

Blog post:
Microsoft’s vector::insert is slower than it should be

Reference:
http://en.cppreference.com/w/cpp/container/vector/insert

The blog post is not really anything special but did a research on
cache affinity with vector.insert.

The author was fascinated by MS's implementation of
vector.insert with PRValue, which uses 3 reverse function call.

The trick has been mentioned in the book(thus i don't see any 'wow' factor out of it):
Programming Pearls(2nd edition) Ch. 2 Section 3, P.14 while ago.
And it honors cache locality if the range of data fits into the cache.

The author also brought up using
memmove
to do the rotation.

The memmove() function shall copy n bytes from the object pointed to by s2 into the object pointed to by s1. 

Copying takes place as if the n bytes from the object pointed to by s2 are first copied into a temporary array of n bytes that does not overlap the objects pointed to by s1 and s2, and 

then the n bytes from the temporary array are copied into the object pointed to by s1.

That is, memmove needs an extra temporary space. And not cache locality friendly if data range is too large.

Will look into Folly's implementation later this week.

Reference:

https://github.com/facebook/folly/blob/master/folly/FBVector.h

[C++] Allocator

Reference:
A visitor’s guide to C++ allocators

[C++11] std::unique_ptr / std::shared_ptr

Quote from Effective Modern C++:

For std::unique_ptr, the type of the deleter is part of the
type of the smart pointer, and this makes it possible for compilers to generate
smaller runtime data structures and faster runtime code.
A consequence of this greater efficiency is that pointed-to types must be
complete when compiler generated special functions
(e.g., destructors or move operations) are used.

For std::shared_ptr, the type of the deleter is not part of the type of the smart
pointer. This necessitates larger runtime data structures and somewhat slower
code, but pointed-to types need not be complete when compiler-generated special
functions are employed.

[C++11] STL container, emplacement push_back

Quote from Effective Modern C++:

• Emplacement functions are often more efficient than their insertion counter parts, and they’re never less efficient.
• For containers of resource-managing objects, emplacement functions may suffer resource leaks that would not arise through use of insertion functions.
• Emplacement functions may perform type conversions that would be rejectedby insertion functions.