What's the difference between deque and list STL containers?

c++ list stl deque
Lazer picture Lazer · Sep 17, 2009 · Viewed 68k times · Source

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

aJ. picture aJ. · Sep 17, 2009

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, including 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/erase at the beginning       in middle        at the end

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

Related questions

vector vs. list in STL

I noticed in Effective STL that vector is the type of sequence that should be used by default. What's does it mean? It seems that ignore the efficiency vector can do anything. Could anybody offer me a scenario where vector …

Read More
How to get a certain element in a list, given the position?

So I've got a list: list<Object> myList; myList.push_back(Object myObject); I'm not sure but I'm confident that this would be the "0th" element in the array. Is there any function I can use that will …

Read More
How could i create a list in c++?

How can I create a list in C++? I need it to create a linked list. How would I go about doing that? Are there good tutorials or examples I could follow?

Read More