# What is the point of using lists over vectors, in C++?

I've run 3 different experiments involving C++ lists and vectors.

Those with vectors proved more efficient, even when a lot of insertions in the middle were involved.

Hence the question: in which case do lists make more sense than vectors?

If vectors seem more efficient in most cases, and considering how alike their members are, then which advantages are left for lists?

1. Generate N integers and put them in a container so that the container remains sorted. The insertion has been performed naively, by reading elements one by one and inserting the new one right before the first larger one.
With a list, time goes through the roof when dimension increases, compared to vectors.

2. Insert N integers at the end of the container.
For lists and vectors, time increased by the same order of magnitude, though it was 3 times faster with vectors.

3. Insert N integers in a container.
Start timer.
Sort the container using list.sort for lists, and std::sort for vectors. Stop timer.
Again, time increases by the same order of magnitude, but it is in average 5 times faster with vectors.

I might continue to perform tests and figure out a couple of examples where lists would prove better.

But the joint experience of you guys reading this message might provide more productive answers.

You might have come across situations where lists were more convenient to use, or performed better?

-
You should take a look at When to use a linked list over an array/array list? if you havent already – Karthik T Jan 30 '13 at 1:18
Here's another good resource on the subject: stackoverflow.com/a/2209564/8360 also, most of the C++ guidance I've heard is to use vector by default, list only if you have a specific reason. – Zachary Yates Jan 30 '13 at 1:22
Thank you. However I do not agree with most of what is said in the favorite answer. Most of these preconceived ideas have been invalidated by my experiments. This person has not made any test and applied widespread theory taught in books or at school. – Marek Stanley Jan 30 '13 at 1:25
A `list` probably does better if you are removing lots of elements. I don't believe a `vector` will ever return memory to the system until the entire vector is deleted. Also keep in mind that your test #1 isn't testing insertion time alone. It's a test combining search and insertion. It's the finding the place to insert where `list` is slow. The actual insert will be faster than vector. – Steven Burnap Jan 30 '13 at 3:37
It is so very typical that this question is described in terms of (run time) performance, performance, and only performance. This seems to be a blind spot of a whole lot of programmers - they focus at this aspect and forget that there are dozens of other aspects which are often much, much more important. – Doc Brown Jan 30 '13 at 9:20

The short answer is that cases seem to be few and far between. There are probably a few though.

One would be when you need to store a small number of large objects -- especially, objects that are so large that it's impractical to allocate space for even a few extra of them. There's basically no way to stop a vector or deque from allocating space for extra objects -- it's how they're defined (i.e., they must allocate extra space to meet their complexity requirements). If you flat-out can't allow that extra space to be allocated, an `std::list` may be the only standard container that meets your needs.

Another would be when/if you'll store an iterator to an "interesting" point in a list for an extended period of time, and when you do insertions and/or deletions, you (nearly) always do it from a spot to which you already have an iterator, so you don't walk through the list to get to the point where you're going to do the insertion or deletion. Obviously the same applies if you work with more than one spot, but still plan on storing an iterator to each place you're likely to work with, so you most manipulate spots you can reach directly, and only rarely walk through the list to get to those spots.

For an example of the first, consider a web browser. It might keep a linked list of `Tab` objects, with each tab object representing on open tab in the browser. Each tab might be a few dozen megabytes of data (of more, especially if something like a video is involved). Your typical number of open tabs might easily be less than a dozen, and 100 is probably close to the upper extreme.

For an example of the second, consider a word processor that stores text as a linked list of chapters, each of which might contain a linked list of (say) paragraphs. When the user is editing, they're typically going to find a particular spot where they're going to edit, and then do a fair amount of work at that spot (or inside that paragraph, anyway). Yes, they'll move from one paragraph to another now and again, but in most cases it'll be a paragraph near where they were already working.

Once in a while (things like global search and replace) you end up walking through all the items in all the lists, but it's fairly uncommon, and even when you do, you're probably going to do enough work searching within an item in the list, that the time to traverse the list is nearly inconsequential.

Note that in a typical case, this is likely to fit the first criterion as well -- a chapter contains a fairly small number of paragraphs, each of which is likely to be fairly large (at least relative to the size of the pointers in the node, and such). Likewise, you have a relatively small number of chapters, each of which might be several kilobytes or so.

That said, I have to admit that both of these examples are probably a little contrived, and while a linked list might work perfectly well for either, it probably wouldn't provide a huge advantage in either case as well. In both cases, for example, allocating extra space in a vector for either some (empty) web pages/tabs or some empty chapters is unlikely to be any real problem.

-
+1, but: The first case vanishes when you use pointers, which you should always be using with large objects. Linked lists aren't suitable for the example of the second, either; arrays own for all operations when they're that short. – naiad Jan 30 '13 at 12:21
The large object case doesn't work at all. Using a `std::vector` of pointers will be more efficient then all those linked list node objects. – Winston Ewert Feb 8 '13 at 17:57
There are many uses for linked lists - it's just that they are not as common as dynamic arrays. An LRU cache is one common use of a linked list. – Charles Salvia Feb 8 '13 at 20:20

According to Bjarne Stroustrup himself, vectors should always be the default collection for sequences of data. You can choose the list if you want to optimize for insertion and deletion of elements, but normally you shouldn't. The costs of the list is slow traversal and memory usage.

Compactness matters. Vectors are more compact than lists. And predictable usage patterns matters enormously. With vectors you have to shove a lot of elements over but caches are really, really good at that. ... Lists don't have random access. But when you traverse a list, you keep doing random access. There's a node here, and it goes to that node, in memory. So you are actually random accessing your memory, and you are maximizing your cache misses, which is exactly the opposite of what you want.

What we should see it that we need a sequence of elements. And the default sequence of elements in C++ is the vector. Now, because that is compact and efficient. Implementation, mapping to hardware, matters. Now, if you want to optimize for insertion and deletion - you say, 'well, I don't want the default version of a sequence. I want the specialized one, which is a list'. And if you do that, you should know enough to say, 'I'm accepting some costs and some problems, like slow traversals and more memory usage'.

-
would you mind writing in brief what is said in the presentation you link to "at about 0:44 and 1:08"? – gnat Feb 8 '13 at 18:02
@gnat - certainly. I have tried to quote the stuff that makes sense separately, and that does need the context of the slides. – Pete Feb 8 '13 at 19:09

The only place where I usually use lists is where I need to erase elements and not invalidate iterators. `std::vector` invalidates all iterators on insert and erase. `std::list` guarantees that iterators to existing elements are still valid after insert or delete.

-

In addition to the other answers already provided, lists have certain features that don't exist in vectors (because they would be insanely expensive.) The splice and merge operations being the most significant. If you frequently have a bunch of lists that need to be appended or merged together, a list is probably a good choice.

But if you don't need to perform these operations, then probably not.

-

The lack of inherent cache/page-friendliness of linked lists tend to make them almost dismissed entirely by a lot of C++ developers, and with good justification in that default form.

Linked Lists Can Still Be Wonderful

Yet linked lists can be wonderful when backed by a fixed allocator that gives them back that spatial locality they inherently lack.

Where they excel is that we can split a list into two lists, for example, by simply storing a new pointer and manipulating a pointer or two. We can move nodes from one list to another in constant time by mere pointer manipulation, and an empty list can simply have the memory cost of a single `head` pointer.

Simple Grid Accelerator

As a practical example, consider a 2D visual simulation. It has a scrolling screen with a map that spans 400x400 (160,000 grid cells) used for accelerating things like collision detection between millions of particles moving around at each frame (we avoid quad-trees here as they actually tend to perform worse with this level of dynamic data). A whole bunch of particles are constantly moving around at every frame, meaning they go from residing in one grid cell to another constantly.

In this case, if each particle is a singly-linked list node, each grid cell can start off as just a `head` pointer which points to `nullptr`. When a new particle is born, we just put it in the grid cell it resides by setting the `head` pointer of that cell to point to this particle node. When a particle moves from one grid cell to the next, we just manipulate pointers.

This can be vastly more efficient than storing 160,000 `vectors` for each grid cell and pushing back and erasing from the middle all the time on a frame-by-frame basis.

std::list

This is for hand-rolled, intrusive, singly-linked lists backed by a fixed allocator though. `std::list` represents a doubly-linked list and it might not be nearly as compact when empty as a single pointer (varies by vendor implementation), plus it's kind of a pain to implement custom allocators in `std::allocator` form.

I must admit I never use `list` whatsoever. But linked lists can be still wonderful! Yet they're not wonderful for the reasons people are often tempted to use them, and not so wonderful unless they're backed by a very efficient fixed allocator which mitigates a lot of at least the compulsory page faults and cache misses associated.

-

You should consider the size of the elements in the container.

`int` elements vector is very fast as most of the data fits inside the CPU cache (and SIMD instructions can probably be used for data copying).

If the element's size is greater then the result of test 1 and 3 could change significantly.

This draw simple conclusions on usage of each data structure:

• Number crunching: use `std::vector` or `std::deque`
• Linear search: use `std::vector` or `std::deque`
• Random Insert/Remove:
• Small data size: use `std::vector`
• Large element size: use `std::list` (unless if intended principally for searching)
• Non-trivial data type: use `std::list` unless you need the container especially for searching. But for multiple modifications of the container, it will be very slow.
• Push to front: use `std::deque` or `std::list`

(as a side note `std::deque` is a very underestimated data structure).

From a convenience point of view `std::list` provides the guarantee that iterators never become invalidated as you insert and remove other elements. It's often a key aspect.

-

In short, there is no good reason for using `std::list<>`:

• If you need an unsorted container, `std::vector<>` rules.
(Delete elements by replacing them with the last element of the vector.)

• If you need a sorted container, `std::vector<shared_ptr<>>` rules.

• If you need a sparse index, `std::unordered_map<>` rules.

That's it.

I find that there is only one situation where I tend to use a linked list: When I have preexisting objects that need to be connected in some way to implement some additional application logic. However, in that case I never use `std::list<>`, rather I resort to a (smart) next pointer inside the object, especially since most use cases result in a tree rather than a linear list. In some cases, the resulting structure is a linked list, in others, it is a tree, or a directed acyclic graph. The primary purpose of these pointers is always to build logical structure, never to manage objects. We have `std::vector<>` for that.

-

You need to show how you were doing the inserts in your first test. Your second and third tests, vector will easily win.

A significant use of lists is when you have to support removing items while iterating. When the vector is modified, all iterators are (potentially) invalid. With a list, only an iterator to the removed element is invalid. All other iterators remain valid.

The typical order of use for containers is vector, deque, then list. The choice of container is usually based on push_back choose vector, pop_front choose deque, insert choose list.

-
when removing items while iterating, it is usually better to use a vector and just create a new vector for the results – naiad Jan 30 '13 at 12:23

One factor I can think of is that as a vector grows, free memory will get fragmented as the vector deallocates its memory and allocates a larger block over and over. This will not be an issue with lists.

This is in addition to the fact that large number of `push_back`s without reserve will also cause a copy during each resize which makes it inefficient. Inserting in the middle similarly causes a move of all the elements to the right, and is even worse.

I dont know if this is a major concern though, but was the reason given to me at my work(mobile game development), to avoid vectors.

-
no, the vector will copy and that's expensive. But traversing the linked list (to figure out where to insert) is also expensive. The key is indeed to measure – Kate Gregory Jan 30 '13 at 3:49
@KateGregory I meant in addition to that, Let me edit accordingly – Karthik T Jan 30 '13 at 4:42
Right, but believe it or not (and most people don't believe it) the cost you didn't mention, traversing the linked list to find where to insert OUTWEIGHS those copies (especially if the elements are small (or movable, because then they are moves)) and vector is often (or even usually) faster. Believe it or not. – Kate Gregory Jan 30 '13 at 13:51