Vector vs Deque insert in the middle

Question

I know that deque is more efficient than a vector when inserts are in front or at the end, and a vector is better if we need to do pointer arithmetic. But which one to use when we need to insert in the middle? and why.?

Answer 1

You might think that the advantage of deque would be advantageous, since it stores data in blocks. However, the implementation of operator[] in constant time requires that all of these blocks be the same size. Inserting or deleting an element in the middle still requires shifting all values ​​from one side or the other, the same as vector . Since vector simpler and has better locality for caching, it should come forward.

Answer 2

Selection criteria with standard library containers: you select a container depending on:

• The type of data you want to save &
• The type of operations you want to perform on the data.

If you want to do a lot of inserts in the middle, you are much better off using std::list .

If the choice is only between a std::deque and std::vector , then several factors must be considered:

• As a rule, there is one more indirectness in the event that a deque gains access to elements, so accessing and moving iterators with deques is usually a bit slower.
• On systems with size restrictions for memory blocks, a deck can contain more elements because it uses more than one memory block. So max_size() may be larger for deques.
• Deques does not provide support for monitoring capacity and timing of redistribution. In particular, any insertion or deletion of elements other than the beginning or end will invalidate all pointers, references, and iterators related to deque elements. However, redistribution may work better than for vectors, because according to their typical internal structure, deques do not need to copy all elements when redistributing.
• Memory blocks can free up when they are no longer in use, so deque memory size can be reduced (this is not a condition imposed by the standard, but most implementations)

Answer 3

std :: deque may work better for large containers, since it is usually implemented as a linked sequence of adjacent data blocks, unlike the one block used in std::vector . Thus, pasting in the middle will reduce the amount of data being copied from one place to another and potentially less redistribution.

Of course, it depends or depends on the size of the containers and the cost of copying the saved items. With the semantics of C ++ 11 relocation, the cost of the latter is less important. But, in the end, the only way to learn is by profiling with a realistic application.

Answer 4

Deque will still be more efficient, since it does not need to move half the array every time you insert an element.

Of course, this will only matter if you are considering a large number of elements, and even if it is desirable to conduct a test and see which one works best in your particular case. Remember that premature optimization is the root of all evil .