2

I understand the difference between vector and list regarding the complexity of common operations on them. But supposing we need to deal with very large lists or vectors (i.e. millions of elements), can we say that memory allocation is more likely to fail when working with vectors?

AFAIK, when working with vectors, the elements are stored contiguously. This means that a big block of memory needs to be allocated in order to store all elements, which seems more likely to fail in case of a fragmented heap.

On the other hand, no big blocks of memory are allocated when working with a list; elements aren't stored contiguously.

jbgs
  • 2,795
  • 2
  • 21
  • 28
  • 5
    "Seems" is the magic word. Thanks to the virtual memory architecture of modern (i.e. post 1990s) computers, there's actually no problem of obtaining memory for "a few million elements". – Kerrek SB Apr 02 '13 at 19:06
  • I think you've nailed the difference here. – Marshall Clow Apr 02 '13 at 19:07
  • 4
    A list typically adds two pointers to each data item, so overall memory usage is higher than for a vector. – Pete Becker Apr 02 '13 at 19:13
  • 2
    Read up on `std::deque`. It's non-contiguous like `list` and uses less memory and allows random access. – Drew Dormann Apr 02 '13 at 19:26
  • Related: http://stackoverflow.com/a/13824260/179910 – Jerry Coffin Apr 02 '13 at 19:28
  • 1
    It all depends on what you mean by *fail*. A `std::vector` requires contiguous memory (virtual memory addresses), but far less memory for simple types than a `std::list`. You are more likely to run out of memory with a `std::list` than you are with `std::vector` – David Rodríguez - dribeas Apr 02 '13 at 19:48

2 Answers2

3

There are definitely scenarios under which an std::list is more likely to keep working than a std::vector. The most straight forward one is when applications have a high amount of memory fragmentation. Essentially when allocations are spread out amongst the virtual memory address space. This leads to a large gap between the amount of memory available and the largest contiguous block of memory. In this scenario it's more likely that a std::vector wiht a large amount of elements will fail than an std::list with the same amount of elements.

However this is not something I would base my decision on blindly. If the application in question suffered from memory fragmentation and it was affecting my ability to use an std::vector then I would consider jumping to std::list. But at the start I would choose whatever collection I felt best suited my needs.

JaredPar
  • 733,204
  • 149
  • 1,241
  • 1,454
  • I find this analysis a bit simplistic... for simple/small types, the overhead of `std::list` is much larger than that of `std::vector`, so you can also claim that you are far more likely to run out of memory with `std::list` than `std::vector` if you estimate and `reserve` an approximate number upfront... there are quite a few unknowns to make a statement in either direction here. – David Rodríguez - dribeas Apr 02 '13 at 19:51
  • @DavidRodríguez-dribeas yes there are definitely other scenarios to consider. My intent was to outline a single concrete scenario where by one collection would be more likley to fail than the other. Many other scenarios exist and could influence you one way or the other. – JaredPar Apr 02 '13 at 19:57
3

The comparison is incomplete without mentioning that the two containers carry different per-element memory requirements:

  • On average, a vector of size N requires N*sizeof(T) bytes (you may need to trim the memory to get the size to exactly N)
  • A list of size N requires N*(sizeof(T)+2*sizeof(void*)) bytes.

Since each element of a list carries two additional pointers, a list of very small objects (say, ints) may require three to five times the amount of memory required by a vector of identical size. As the size of a list element increases, the additional memory requirements become less pronounced, but for small objects the implications are huge. That is why it is not fair to say that vectors are more likely to fail on memory allocation: although a vector requires a contiguous block of memory, the total amount may be a lot smaller, letting you have vectors of significantly larger sizes before entering the territory of potential failures.

For objects of sizes significantly (say, ten or more times) larger than two pointers you can safely neglect the additional memory requirements: due to the need of vectors to allocate contiguous space, the possibility of not finding a suitable chunk of memory is significantly higher.

Sergey Kalinichenko
  • 714,442
  • 84
  • 1,110
  • 1,523
  • We can neglect these two pointers. I didn't mention it, but I was considering lists of big objects, not simple ints. – jbgs Apr 02 '13 at 19:18