STL containers - distinction between vector, list and deque

Question

Should I use deque instead of vector if I would like to click elements also at the beginning of the container? When should I use the list and what is its essence?

Answer 1

Use deque if you need efficient insertion / deletion at the beginning and end of a sequence and random access; use list if you need efficient insertion anywhere, with random access victim. Iterators and references to list elements are very stable with almost any mutation of the container, while deque has very peculiar iteration and reference invalidation rules (so read them carefully). A.

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

deque can replace vector almost everywhere and probably should be considered the default container in C ++ (due to its more flexible memory requirements); the only reason vector is preferred is that you must have a guaranteed continuous memory structure for your sequence.

Answer 2

deque and vector provide random access, list provides only linear calls. Therefore, if you need to make container [i], this excludes list . On the other hand, you can effectively insert and remove items anywhere in the list , and operations in the middle of vector and deque are slow.

deque and vector very similar and mostly interchangeable for most purposes. There are only two differences that are worth mentioning. Firstly, vector can only effectively add new elements at the end, while deque can effectively add elements at both ends. So why would you ever use vector ? Unlike deque , vector guarantee that all elements will be stored in adjacent memory cells, which speeds up their repetition in some situations.