Std :: vector keystroke?

Question

I am using a vector to manage my big data structure. But unexpectedly, upon discovering the source code for vector , I am very surprised to see the following code:

 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); ////////////////////////////////////////////////////////////// } 

This is the code for the fragment that destroys and then redistributes all of its vector data. This is so annoying because my structure is large and the vector needs to control hundreds of elements, while I use only vector::operator [] and vector::push_back() , especially pushing back takes up most of my program time ( This is time-consuming). In my case, is there a better container that can work faster than std::vector , and I tried Google, but no luck?

Answer 1

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

You can pre-allocate vector capacity using the reserve() function.

Answer 2

If you reserve all the necessary space before adding items, solve your problem?

Answer 3

Redistribution occurs only if the size of your vector increases compared to its throughput. If you know in advance (even roughly) how many objects your vector will contain, you can use its reserve to pre-allocate sufficient capacity, you can also initiate a redistribution of yourself in a controlled way, even when filling the vector, to reduce the number of times it is called , and thereby increase productivity.

Now, if you need a guaranteed permanent installation, there are containers that can be used for this, but with a compromise (for example, std::list will allocate many small blocks of memory that may not be faster than your current one because new pretty slow and memory usage will be more important and you will lose random access, but make sure that each insert takes about the same time as the rest).

Answer 4

If you know your final data size, you can use reserve to predefine the memory needed for the vector. This will remove all redistribution and copying.

If you do not know the exact size, make an educated guess based on what you know about your input.

Answer 5

A vector is a dynamically expanding container, but its contents should be in a continuous block of memory (as I recall, this was not specified in pre-C ++ 11, but everyone did it). Therefore, if your vector already contains 8 elements, and the current capacity of the vector is 8 elements, then when you push_back the 9th element, the container should allocate a new space for a larger capacity, copy 8 elements that are already in the container, copy 9- th element into a new space, then destroy the old one. If you use C ++ 11, and your elements support move-construction, then 8 copies can become 8 moves. Or, if you want to bear the overhead of control pointers, you can store pointers to elements instead of elements (copying the pointer is cheap, but now you need to deal with the problem of lifespan).

As for the container is faster than for the vector, this is a big open question. It depends on all kinds of access / manipulation patterns. std :: list was mentioned as a candidate. O (1), adding to the end of the list, but probably more O (1) than the amortized O (1), which uses the vector. You are losing random access to the container.

Answer 6

Yes, push_back() , as you know, is constant most of the time, but it needs to redistribute the entire vector when size() reaches capacity() .

If you want to set a constant time, you should try std::list or std::deque . Especially std::deque provides the right performance for inserting at the end of your container, being close to a vector in its interface.

Excerpt from cpp link :

Therefore, they provide similar functionality as vectors, but with effective insertion and deletion of elements also at the beginning of a sequence, and not just from its end. But, unlike vectors, deques does not guarantee the preservation of all its elements in adjacent storage locations, which does not allow direct access by shifting pointers to elements.