Vector vs Deque insertion in middle

Question

I know that deque is more efficient than vector when insertions are at front or end and vector is better if we have to do pointer arithmetic. But which one to use when we have to perform insertions in middle.? and Why.?

Answer 1

You might think that a deque would have the advantage, because it stores the data broken up into blocks. However to implement operator[] in constant time requires all those blocks to be the same size. Inserting or deleting an element in the middle still requires shifting all the values on one side or the other, same as a vector. Since the vector is simpler and has better locality for caching, it should come out ahead.

Answer 2

Selection criteria with Standard library containers is, You select a container depending upon:

1. Type of data you want to store &
2. The type of operations you want to perform on the data.

If you want to perform large number of insertions in the middle you are much better off using a std::list.

If the choice is just between a std::deque and std::vector then there are a number of factors to consider:

• Typically, there is one more indirection in case of deque to access the elements, so element access and iterator movement of deques are usually a bit slower.
• In systems that have size limitations for blocks of memory, a deque might contain more elements because it uses more than one block of memory. Thus, max_size() might be larger for deques.
• Deques provide no support to control the capacity and the moment of reallocation. In particular, any insertion or deletion of elements other than at the beginning or end invalidates all pointers, references, and iterators that refer to elements of the deque. However, reallocation may perform better than for vectors, because according to their typical internal structure, deques don't have to copy all elements on reallocation.
• Blocks of memory might get freed when they are no longer used, so the memory size of a deque might shrink (this is not a condition imposed by standard but most implementations do)