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.

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.

He talks about this in this presentation.

At about 0:44 he talks about vectors vs. lists in general.

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.

At about 1:08, he is given a question about this issue.

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’.

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 400×400 (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.

From a very comprehensive performance comparison:

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.

The most prominent reason to use lists in my opinion is iterator invalidation : if you add / remove elements to a vector, all the pointers, references, iterators that you held to particular elements of this vector may be invalidated and lead to subtle bugs… or segmentation faults.

This is not the case with lists.

The precise rules for all the standard containers are given in this StackOverflow post.

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.

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_backs 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.