<vector> push_back implementation internal

Question

In std::vectors push_back implemetation, when size()==capacity() , the part, that it allocates two times more place and copy the elements of old , I want to ask, the most effective way of that copying?

Answer 1

Sounds a bit as if you wanted to implement std::vector<> yourself.
The most efficient way is to avoid reallocations in the first place, which often but not always is possible.

If you have prior knowledge about how many items you will push_back() next, you can use std::vector<>::reserve() and avoid reallocations altogether.

If you really were to implement yourself, you might want to use realloc(), in spite of the fact that this is a horrible function which can do - depending on parameter values anything from malloc() to free() to realloc().

The reason, why this function can be helpful is, that there is a good chance that there is still room behind the data block on the heap. realloc() is the only function which can avoid a 100% of the time moving of the data by expanding this heap blocks size, not touching the data at all, if there is enough room to do that.

The drawback of using realloc() is that your "special performance" implementation would forego the concept of allocators as well as fail to handle element types which require copy constructor calls etc. So you would best not name your vector vector but something like "SimpleDataVector" and possibly build in some mechanism to detect misuse.

Answer 2

This is not really specified in the standard, but left for the implementation. Thus, different C++ library versions will do this differently. However, the allocator of the vector must be used for any allocation and de-allocations (hence no usage of realloc()).

What the standard does specify, though is that if objects can be moved (instead of copied) then they should be moved (since C++11). Typically, a new block of raw memory will be allocated, typically twice the size of the previous, and then the elements moved (or copied and destroyed) from the previous to the old. For the generic case, this moving/copying must be done one by one (since otherwise the integrity of the moves/copied cannot be guaranteed without knowledege of the internals of the respective move/copy constructors). Of course, for pod (=plain old data) types optimisations via std::memcpy() are possible (and most likely implemented).

You can try to look at your C++ library implementation, but be warned that the code can be quite opaque to those unfamiliar with meta template programming: the code is complicated because of the various optimisations (for pod, movable types, etc.).