C++ STL containers: what's the difference between deque and list?

Question

What is the difference between the two? I mean the methods are all the same. So, for a user, they work identically.

Is that correct??

Answer 1

No. A deque only supports O(1) insertion and deletion at the front and back. It may, for example, be implemented in a vector with wrap-around. Since it also guarantees O(1) random access, you can be sure it's not using (just) a doubly linked list.

Answer 2

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.

Answer 3

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.

Answer 4

The performance differences have been explained well by others. I just wanted to add that similar or even identical interfaces are common in object-oriented programming -- part of the general methodology of writing object-oriented software. You should IN NO WAY assume that two classes work the same way simply because they implement the same interface, any more than you should assume that a horse works like a dog because they both implement attack() and make_noise().

Answer 5

Let me list down the differences:

• Deque manages its elements with a dynamic array, provides random access, and has almost the same interface as a vector.
• List manages its elements as a doubly linked list and does not provide random access.

• Deque provides Fast insertions and deletions at both the end and the beginning. Inserting and deleting elements in the middle is relatively slow because all elements up to either of both ends may be moved to make room or to fill a gap
• In List, inserting and removing elements is fast at each position, and not only at one or both ends .

• Deque : 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.
• List: Inserting and deleting elements does not invalidate pointers, references, and iterators to other elements

Complexity

             Insert/eraser at the beginning      in middle        at the end

Deque: .............. Amortized constant.......................................... Linear.................... Amortized constant List: ....................Constant...........................................................Constant.................Constant