CODEWITHSUNDEEP
c++stlvectordeque
user1543957
user1543957

Reputation: 1838

Vector vs Deque insertion in middle

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.?

Upvotes: 11

Views: 4153

Answers (4)

juanchopanza
juanchopanza

Reputation: 227618

std::deque could perform better for large containers because it is typically implemented as a linked sequence of contiguous data blocks, as opposed to the single block used in an std::vector. So an insertion in the middle would result in less data being copied from one place to another, and potentially less reallocations.

Of course, whether that matters or not depends on the size of the containers and the cost of copying the elements stored. With C++11 move semantics, the cost of the latter is less important. But in the end, the only way of knowing is profiling with a realistic application.

Upvotes: 1

Mark Ransom
Mark Ransom

Reputation: 308538

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.

Upvotes: 14

Alok Save
Alok Save

Reputation: 206656

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)

Upvotes: 3

Qnan
Qnan

Reputation: 3744

Deque would still be more efficient, as it doesn't have to move half of the array every time you insert an element.

Of course, this will only really matter if you consider large numbers of elements, and even than it is advisable to run a benchmark and see which one works better in your particular case. Remember that premature optimization is the root of all evil.

Upvotes: 0

Related Questions