C++ – the point of using lists over vectors, in C++

cdata structuresmemory usageperformancestl

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?

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

Best Answer

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.

Related Solutions

Merge sort versus quick sort performance

If you look at your code for swapping you:

// If current element is lower than pivot
// then swap it with the element at store_index
// and move the store_index to the right.

But, ~50% of the time that string you just swapped needs to be moved back, which is why faster merge sorts work from both ends at the same time.

Next if you check to see if the first and last elements are the same before doing each of the recursive call you avoid wasting time calling a function only to quickly exit it. This happens 10000000 in your final test which does add noticeable amounts of time.

Use,

if (pivot_index -1 > start) quick_sort(lines, start, pivot_index - 1);

if (pivot_index + 1 < end) quick_sort(lines, pivot_index + 1, end);

You still want an outer function to do an initial if (start < end) but that only needs to happen once so that function can just call an unsafe version of your code without that outer comparison.

Also, picking a random pivot tends to avoid N^2 worst case results, but it's probably not a big deal with your random data set.

Finally, the hidden problem is QuickSort is comparing strings in ever smaller buckets that are ever closer together,

(Edit: So, AAAAA, AAAAB, AAAAC, AAAAD then AAAAA, AAAAB. So, strcmp needs to step though a lot of A's before looking the useful parts of the strings.)

but with Merge sort you look at the smallest buckets first while they are vary random. Mergsorts final passes do compare a lot of strings close to each other, but it's less of an issue then. One way to make Quick sorts faster for strings is to compare the first digits of the outer strings and if there the same ignore them when doing the inner comparisons, but you have to be careful that all strings have enough digits that your not skipping past the null terminator.

C++ – 2D linked list vs. multidimensional array/vector

I hope it's ok to answer my own question. I believe I have found the optimal (without overcomplicating the problem) data structure for my problem. There was at least minor idiocy on my part for not recognising this earlier. The data doesn't need to be accessed by (x,y,z) but instead by (x, y, range of z (say 0 - 3)). This give a C++ struct as follows:

struct node {
  struct node *next;
  int zGroup;
  int z;
  50 bytes of misc data };

I can then address this through a 3D dynamic array (vectors):

vector< vector < vector < node* > > > Data;

Any given Data[x][y][zGroup] points to the first element of a linked list, the entirety of which is needed every time one element of it is needed. No value of this array is NULL, every one contains a linked-list of at least one element.

The third dimension of the array - the zGroup has jagged dimensions, but with dynamic arrays this isn't an issue. Given the data and computations being performed on it, I know that the max x and y values are set when the file is read and do not change, neither does the number of z groups on any given (x,y) line, the actual z-values of nodes may change, but they will remain inside the same z-groups, giving a constant-sized, fully populated array.

With the way that the file is structured it is also easy enough to page it in and out of memory if I am brought to do this with much larger data sets.

Best Answer

Related Solutions

Merge sort versus quick sort performance

C++ – 2D linked list vs. multidimensional array/vector

Related Topic