-1

Two STL containers, std::vector and std::list, seem to provide very similar functions. As far as I can tell, the only difference is that a std::list provides O(1) time for modification, and O(n) time for reading, and vice-versa for the vector. Ignoring efficiency, are there any other differences? The proposed duplicate seems to focus on efficiency, whereas I am wondering about how the memory differences manifest in semantics differences (such as std::list's splicing capability)?

パスカル
  • 479
  • 4
  • 13
  • 1
    Left for Bjarne Stroustrup, [almost](https://www.youtube.com/watch?v=YQs6IC-vgmo) every time. Quips aside. This is a very broad question. – WhiZTiM Mar 04 '17 at 16:21
  • Why? I know that the memory structure is different, but why are the semantics different? – パスカル Mar 04 '17 at 16:24
  • Google will yield the answers you are looking for. It has to do with speed of random acess and insertion of elements within the container http://stackoverflow.com/questions/2209224/vector-vs-list-in-stl almighty Google – user Mar 04 '17 at 16:24
  • Almost never use `std::list`. One can splice in a part in a list, but as I recall that was made O(n) in order to get the size operation down to O(1), in C++11. Andrew Koenig started on an interesting example in DDJ, about how linked lists could be at least pretty dang convenient in some concrete examples, but it turned out that `std::vector` could provide the same convenience and performance. – Cheers and hth. - Alf Mar 04 '17 at 16:31
  • There are two main problems with `std::vector`, namely the specialization for `bool` item type (getting proxy objects rather than real references out of the iterators), and that the standard library lacks a cursor gap wrapper à la queue and stack. But neither problem is solved with `std::list'`. – Cheers and hth. - Alf Mar 04 '17 at 16:33
  • Thanks, @Alf. Helpful answers. You should post them in an answer. – パスカル Mar 04 '17 at 16:34
  • you should actually prefer vector over list in majority of cases https://www.youtube.com/watch?v=YQs6IC-vgmo – LiorA Mar 04 '17 at 16:38

2 Answers2

2

List has a (much) bigger memory footprint per element, and less cache coherency (even when ignoring the larger element size) than a vector does. This means that it will rely much more on your cache line fetches & memory read speed, which typically is your performance bottleneck, rather than the assumed "read/write for one element" that was used for list/vector's comparison originally.

As a pathological example, consider a vector of 16 int versus a list of 16 int. The first has a single cache line with 16 ints in it and can do any operation in 1 cache line fetch, where the second has:

  • One memory allocation block overhead (16 bytes)
  • One pointer to the previous block (8 bytes)
  • One pointer to the next block (8 bytes)
  • One int (4 bytes)

in every allocated unit. Using the guesstimated sizes above, this puts it at about 36 bytes, rounded up to 40 (because of alignment reasons) and probably to 48 (because of malloc's internal alignment reasons). That would, in the ideal case, load 12 full cache lines, and in the worst case 32 cache lines.

Given that your performance bottleneck is the cache, having everything in 1 or maybe 2 cache lines instead of 12-32 way trumps list's theoretical advantages.

dascandy
  • 7,184
  • 1
  • 29
  • 50
  • I agree with most here, but what exactly are " list's theoretical advantages"`? – Cheers and hth. - Alf Mar 04 '17 at 16:38
  • A list can be split and/or joined efficiently (by virtue of it being discontinuous segments to start with); a list supports O(1) insertion/deletion in the middle. This only actually helps if you already know the locations, because iteration is O(n) in cache lines, where a vector is O(n/(sizeof(cacheline)/sizeof(item))) - strictly still O(n) but usually much less. – dascandy Mar 04 '17 at 16:52
  • O(1) time for modification, theoretically. – パスカル Mar 04 '17 at 16:52
  • @dascandy: As far as I can see with `std::list` those operations are decidedly inefficient, O(n), with `std::list`, except insertion/removal of single item, which can be better done with O(1) complexity for cursor gap wrapper of `std::vector`. – Cheers and hth. - Alf Mar 04 '17 at 18:44
0

To summarize what I have seen in the comments and answers so far, here are the pros/cons of lists over vectors:

  • Much worse performance in almost all areas
  • Splicing capabilities that vector does not support
  • Less cache coherency, meaning more reliance on memory reading
  • Larger item size in list.
  • Issues with both vector and list with bools and wrappers Thanks so much for all the help!
パスカル
  • 479
  • 4
  • 13