Deque vs Vector
In this article, we are going to see the difference between the STL sequential containers std::deque and std::vector with their appropriate usage.
VECTOR :
- Vectors are dynamic arrays that can shrink and expand when an element is added.
- The container handles the memory automatically.
- The data can be inserted at the middle or at the end.
- The elements are stored in contiguous storage.
DEQUE :
- Deques or double-ended queues are sequence containers that shrink and expand from both the ends.
- Data can be inserted from the start, middle and ends.
- The data is not stored in contiguous storage locations always.
What’s the difference ?
- While vector is like Dynamic array. Deque is the data structure implementation of the double-ended queue.
- While in vector insertion and deletion at end has good performance, however insertion and deletion from middle performs badly. But deque provides the same performance like vector insertion and deletion at end for both end and middle. Also has good performance with insertion and deletion at start.
- While vectors store elements contiguous which makes it faster to operate at the end faster than deques. The deques are not stored contiguous but are a list of various locations where the elements are stored so overall operations at first, mid and end positions are faster than vectors as it does not have to shift elements to store an element.
Appropriate place to use :
When there are list like operations, where additions and deletion only happen at the bottom, vectors are suitable to use. In case we want to operate on the top position as well it is suitable to use deques for the purpose.