15

Should I use deque instead of vector if i'd like to push elements also in the beginning of the container? When should I use list and what's the point of it?

Cœur
  • 37,241
  • 25
  • 195
  • 267
fex
  • 3,488
  • 5
  • 30
  • 46

2 Answers2

19

Use deque if you need efficient insertion/removal at the beginning and end of the sequence and random access; use list if you need efficient insertion anywhere, at the sacrifice of random access. Iterators and references to list elements are very stable under almost any mutation of the container, while deque has very peculiar iterator and reference invalidation rules (so check them out carefully).

Also, list is a node-based container, while a deque uses chunks of contiguous memory, so memory locality may have performance effects that cannot be captured by asymptotic complexity estimates.

deque can serve as a replacement for vector almost everywhere and should probably have been considered the "default" container in C++ (on account of its more flexible memory requirements); the only reason to prefer vector is when you must have a guaranteed contiguous memory layout of your sequence.

Kerrek SB
  • 464,522
  • 92
  • 875
  • 1,084
  • 1
    `vector` almost always performs better than `deque`, in my experience. – Don Reba Mar 10 '12 at 21:31
  • 3
    @DonReba: it depends on the use case, and profiling is really the only answer. A vector might struggle if you want to allocate a huge range, while the deque can allocate new chunks without moving the old ones. And of course it depends on what you're doing. – Kerrek SB Mar 10 '12 at 21:33
  • @KerrekSB Could you give some profiling data here. That will be very evident in deciding the performance. – Sisir Nov 12 '18 at 04:05
  • @Sisir: This isn't a very good answer. While "deque" is in principle a good idea, there are many bad implementations out there that use too small a chunk size and thus effectively turn into linked lists. So you'll definitely need to compare and profile; `std::vector` often performs better even for insertions other than at the end for many "typical" container sizes. – Kerrek SB Nov 12 '18 at 14:14
14

deque and vector provide random access, list provides only linear accesses. So if you need to be able to do container[i], that rules out list. On the other hand, you can insert and remove items anywhere in a list efficiently, and operations in the middle of vector and deque are slow.

deque and vector are very similar, and are basically interchangeable for most purposes. There are only two differences worth mentioning. First, vector can only efficiently add new items at the end, while deque can add items at either end efficiently. So why would you ever use a vector then? Unlike deque, vector guarantee that all items will be stored in contiguous memory locations, which makes iterating through them faster in some situations.

deong
  • 3,820
  • 21
  • 18
  • Could you give some profiling data here. That will be very evident in deciding the performance. – Sisir Nov 12 '18 at 04:05