[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