A Real World Example of Vector vs List showing scenario where each is more efficient than the other

Question

I was actually asked this question at a job interview and I froze. The question gave me food for thought so I thought I'd also ask if any of you can help with examples. Can you please focus on efficiency in your real world examples showing how one is more efficient than the other and vice versa?

Thanks much

Edit:

Thanks everybody for your input. Just to clarify I was asking for real world examples, don't worry about if they are trivial examples or not, any will do.

Answer 1

+1 NetVipeC

One advantage list has over vector is in terms of iterator invalidation. If you have an iterator to an element in a vector and you modify the vector, the iterator is no longer guaranteed to be valid. For a list the iterator is still valid (unless you remove the element it was pointing to). From this it should be easy to create examples (artificial maybe) where list is more efficient than vector.

Answer 2

The normal perception before listen for the first time that you should avoid std::list and prefer std::vector as default always is that the topics learn in the university apply as learned (Big-O). See the references for the Big-O of the method of the two containers.

That std::list (a double linked list), should be more performance in insertion, deletion (O(1)) if it's in the middle of the container (is where the big performance gain should manifest).

The problem with this statements is that the hardware love continuous memory, and a lot of features have been invented to take advantage of this (prefetch, cache, etc...), the compiler have been optimized to recognize pattern (eg: memcpy, memmove), and generate the best performance code (sometime directly in assembly).

The previous consideration conclude for even big container size (eg: half million, I think was the max size that Bjarne test) the std::vector outperform the std::list in performance (and much more in memory size).

In the new standard (C++11) this difference grow more because of move semantic making the grow in push_back lower cost in some cases.

My recommendation is always use std::vector until you have a reason not to used.

More info:

• http://isocpp.org/blog/2014/06/stroustrup-lists
• http://blog.davidecoppola.com/2014/05/20/cpp-benchmarks-vector-vs-list-vs-deque/

A video for more information: Why you should avoid Linked Lists

Answer 3

He is asking for real examples about that, so I assume you are asking about real applications of these data sctructures.

Vector better than list: any aplication that requires a grid representation for example (any computer vision algorithm, for instance) in which the size of the grid is not known in advance (otherwise you would use array). In this case, you would need random access to container elements and vector is O(1) (constant time). Another example is for example when you have to build a tree (for a tree-based path planning algorithm, for instance). You do not know the number of nodes in advance, so you just push_back nodes all the time and store in their nodes the indices of the parents.

List better than vector: when you are going to do a lot of insertions/deletions in the middle of the container (note middle I mean not first/last elements). Imagine you are implementing a videogame in which many enemies are appearing and you have to kill them. Everytime you kill one, the proper thing to do is to detele that enemy so that it does not consume memory. However, it is very unlikely that you kill enemy 1. Therefore, you would need to remove that enemy from a list of enemies. If you are implementing insertion-sort-like algorithms a list can be also very helpful since you are all the time moving elements within the list.

Answer 4

If you want to randomly access an item efficiently and don't care about efficiency of insertion and deletion, use vector.

Otherwise, if you may have many insertion and deletion and care little about access the items, use list.