Is there a reason to use std :: list?

Question

After you read this question and looked at some of the results here , it seems like lists should be completely avoided in C ++. I always expected linked lists to be containers of choice for cases where I only need to iterate over all the contents, because insertion is a matter of pointer manipulation, and redistribution is never required.

Apparently, due to the "locality of the cache", lists are repeated very slowly, so any advantage of using less backup memory or faster additions (which is not so fast, it seems from the second link) It seems worth it.

Having said that, when should I, in terms of performance, use std::list over std::deque or, if possible, std::vector ?

On the side of the note, will std::forward_list also have a lot of cache misses?

Answer 1

When should I use std::list in terms of performance

In terms of performance, rarely. The only situation that comes to mind is if you have a lot of lists that you need to split and join other lists; a linked list can do this without allocating memory or moving objects.

The real advantage of list is stability: elements must not be movable, and iterators and links are never invalid unless they refer to an element to be erased.

On the side of the note, will std::forward_list also have a lot of cache misses?

Yes; it is still a linked list.

Answer 2

std::list is useful in several corner cases.

However, the general rule for C ++ sequential containers is "if your algorithm is compatible, use std::vector . If your algorithms are incompatible, change your algorithms so you can use std::vector ."

There are exceptions, and here's an attempt to exhaustively list the reasons std::list is the best choice:

• When you need to (A) insert in the middle of the container and (B), you need to keep every location of objects in memory stable. Requirement (B) can usually be removed by having an unstable container consisting of pointers to elements, so this is not a serious reason to use std::list .

• If you need to (A) insert or remove orders in the middle of the container (B) more often than you need to iterate over the container. This is also an extreme edge case: in order to find an item to remove from a list , you usually need to iterate!

That leads to

3. you need to (A) insert or remove in the middle of the container and (B) include iterators for all other elements. This becomes a hidden requirement for case 1 and case 2: it is difficult to remove or insert it more often than you repeat when you do not have constant iterators, and the stability of iterators and objects is very interconnected.

4. The latter case, the splicing case, was once the reason for using std::list .

In C ++ 03, all versions of std::list::splice can (theoretically) run O (1) times. However, the extremely efficient forms of splice required that size be an O (n) operation. C ++ 11 required that the size on a list be O (1), so the maximum performance of splice limited to "splicing a whole other list" and "sub-list self-alignment". In the case of splicing with one element, this is just insertion and deletion. In the case of sub-band splicing, the code should now visit each node in splices only to count them, in order to maintain size as O (1) (except for self-fusion).

So, if you are only executing entire chains of a list or a submenu of your own splice s list , list can perform these operations much faster than other non-list containers.

Answer 3

The biggest improvement std::list can provide is when you move one or more items from the middle of one list to another list. This splice operation is extremely efficient with list , while it can include distributing and moving items in random access containers such as vector . However, this is very rare, and most of the time vector is your best container in terms of performance and simplicity.

Always review your code if you suspect performance issues when choosing a container.

Answer 4

You chose std::list over std::deque and std::vector (and other neighboring memory containers) when you often add / remove items in the middle of your container, see also .