Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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?

share|improve this question
1  
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
1  
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
1  
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

4 Answers 4

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.

share|improve this answer
2  
+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. –  sparkleshy 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.

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

share|improve this answer
    
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
1  
@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

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.

share|improve this answer
1  
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
2  
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

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.

share|improve this answer
2  
when removing items while iterating, it is usually better to use a vector and just create a new vector for the results –  sparkleshy Jan 30 '13 at 12:23

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.