In C++, the STL deque is a sequential container that provides the functionality of a double-ended queue data structure. In a regular queue, elements are added from the rear and removed from the front. However, in a deque, we can insert and remove elements from both the front and rear. Deque Data Structure.
In the case of random insert, in theory, the list should be much faster, its insert operation being in O(1) versus O(n) for a vector or a deque.
std::deque (double-ended queue) is an indexed sequence container that allows fast insertion and deletion at both its beginning and its end. In addition, insertion and deletion at either end of a deque never invalidates pointers or references to the rest of the elements.
Let me list down the differences:
Complexity
Insert/erase at the beginning in middle at the end
Deque: Amortized constant Linear Amortized constant
List: Constant Constant Constant
From the (dated but still very useful) SGI STL summary of deque
:
A deque is very much like a vector: like vector, it is a sequence that supports random access to elements, constant time insertion and removal of elements at the end of the sequence, and linear time insertion and removal of elements in the middle.
The main way in which deque differs from vector is that deque also supports constant time insertion and removal of elements at the beginning of the sequence. Additionally, deque does not have any member functions analogous to vector's capacity() and reserve(), and does not provide any of the guarantees on iterator validity that are associated with those member functions.
Here's the summary on list
from the same site:
A list is a doubly linked list. That is, it is a Sequence that supports both forward and backward traversal, and (amortized) constant time insertion and removal of elements at the beginning or the end, or in the middle. Lists have the important property that insertion and splicing do not invalidate iterators to list elements, and that even removal invalidates only the iterators that point to the elements that are removed. The ordering of iterators may be changed (that is, list::iterator might have a different predecessor or successor after a list operation than it did before), but the iterators themselves will not be invalidated or made to point to different elements unless that invalidation or mutation is explicit.
In summary the containers may have shared routines but the time guarantees for those routines differ from container to container. This is very important when considering which of these containers to use for a task: taking into account how the container will be most frequently used (e.g., more for searching than for insertion/deletion) goes a long way in directing you to the right container.
std::list
is basically a doubly linked list.
std::deque
, on the other hand, is implemented more like std::vector
. It has constant access time by index, as well as insertion and removal at the beginning and end, which provides dramatically different performance characteristics than a list.
Another important guarantee is the way each different container stores its data in memory:
Note that the deque was designed to try to balance the advantages of both vector and list without their respective drawbacks. It is a specially interesting container in memory limited platforms, for example, microcontrollers.
The memory storage strategy is often overlooked, however, it is frequently one of the most important reasons to select the most suitable container for a certain application.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With