CODEWITHSUNDEEP
c++stl
jbgs
jbgs

Reputation: 2885

Is a std::vector more likely to fail than a std::list (STL containers)

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.

Upvotes: 2

Views: 163

Answers (2)

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 726569

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.

Upvotes: 3

JaredPar
JaredPar

Reputation: 754715

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.

Upvotes: 3

Related Questions