std::vector pushing speed?

Question

I'm using vector to manage my large structure data. But suddenly, when discovering vector source code, I am very surprised to see some code below :

inline void push_back(const _Ty& _X)
    {insert(end(), _X); }
//...

void insert(iterator _P, size_type _M, const _Ty& _X)
    {
//////////////////////////////////////////////////////////////
        iterator _S = allocator.allocate(_N, (void *)0);
        iterator _Q = _Ucopy(_First, _P, _S);
        _Ufill(_Q, _M, _X);
        _Ucopy(_P, _Last, _Q + _M);
        _Destroy(_First, _Last);
        allocator.deallocate(_First, _End - _First);
//////////////////////////////////////////////////////////////
    }

It's the snippet code which "destroys" then reallocates its whole vector data. It's so annoying, because my structure has a large size and a vector has to manage hundreds of elements, while I only use vector::operator [] and vector::push_back(), especially pushing back takes most of my program time (it's time-consuming). In my case, is there any better container which can perform faster than std::vector, while I tried to google but no luck?

Answer 1

The allocate-copy-delete (or allocate-move-delete in C++11) only happens once each time the vector exceeds its current capacity. With each such reallocation, the capacity doubles. This averages out over time, so the amortized complexity of push_back() is constant.

You can pre-allocate the vector's capacity by using its reserve() member function.

Answer 2

A vector is a dynamically expanding container, but its contents are required to be in a contiguous block of memory (as I recall, this was unspecified in pre-C++11 but everybody did it). So if your vector already holds 8 elements, and the current capacity of the vector is 8 elements, then when you push_back a 9th element, the container must allocate new space for the larger capacity, copy the 8 elements that are already in the container, copy the 9th element into the new space, then destroy the old. If you are using C++11, and your elements support move-construction, then the 8 copies can become 8 moves. Or if you want to incur the overheads of managing pointers, you could store pointers to elements instead of elements (copying a pointer is cheap, but now you need to deal with the lifespan issue).

As for which container is faster than vector, that's a large open-ended question. It depends on all sorts of access/manipulation patterns. std::list was mentioned as a candidate. O(1) adding to the end of the list, but is probably a bigger O(1) than the amortized O(1) that vector uses. You lose random-access into the container.

Answer 3

Reallocation only occurs if your vector size increases past its capacity. If you know in advance (even roughly) how many items your vector will contain, you can use its reserve member to pre-allocate enough capacity. You can also trigger reallocation yourself in a controlled manner, even while filling the vector, to reduce the number of times it is called and thus get better performance.

Now if you want guaranteed constant-time insertion there are containers that can be used for that but at a trade-off (eg. std::list will allocate lots of small memory blocks which may end up not any faster that your current vector use, because new is quite slow, and the memory usage will be more important too, and you lose random access, but sure every insertion will take roughly the same time as the others).

Answer 4

Yes push_back() is known to be constant most of time, but needs to re-allocate the whole vector when the size() reach the capacity().

If you want constant time insertion, you must try a std::list or a std::deque. Especially a std::deque provides correct performance for insertion at the end of your container while being close to a vector in its interface.

Extract from cpp reference:

Therefore they provide a similar functionality as vectors, but with efficient insertion and deletion of elements also at the beginning of the sequence, and not only at its end. But, unlike vectors, deques are not guaranteed to store all its elements in contiguous storage locations, thus not allowing direct access by offsetting pointers to elements.

Answer 5

If you know your final data size, you can use reserve to preallocate the memory needed for the vector. That will remove all reallocating and copying.

If you don't know the exact size, make an educated guess based on what you do know about your incoming data.

Answer 6

Would reserving all the space you need before adding elements solve your problem ?