0

I need to make an object which owns lists that can grow indefinitely. Items in the list are structs composed of basic types.

So, I want to know if using a vector for it could lead to memory fragmentation if it grows too much. If so, what should I use instead?

Would a pointer to vector be enough? I don't know if memory fragmentation would be less important if the vector is stored outside the object.

Guillem Tb
  • 3
  • 2
  • So, do you want to use list or vector? – PcAF Jun 21 '16 at 11:07
  • I want to use the most efficient option for the situation I described. If they are equally efficient, I prefer the vector, as I'm used to it. – Guillem Tb Jun 21 '16 at 11:16
  • This depends for what do you want to use it. `list` is fast in inserting items in the middle(`vector` is only fast at inserting them at the end), but `vector` is continuous, therefore it's faster than `list` when iterating through whole `vector`. – PcAF Jun 21 '16 at 11:36
  • I only need to push elements in the end. However, I want to know it it is efficient when the vector grows bigger than the reserved space and if it can lead to being less efficient than the list in those cases. – Guillem Tb Jun 21 '16 at 11:38
  • 1
    `std::vector` has function `reserve` ,which will reserve some memory(you'll have to choose how much), thus avoiding copying whole array( when there isn't any space left `vector` allocates new dynamic array and copies every element from old array into new array) – PcAF Jun 21 '16 at 11:43
  • When you try adding new element to vector and it doesn't have enough memory allocated it allocates new memory (twice as much), copies old memory to the start of new one and frees old one, and it has drawback, like if you want to store 33 elements, you have to allocate memory enough for 64 (unless you specify otherwise) with constructor. – MaciekGrynda Jun 21 '16 at 11:47
  • What order of magnitude are you talking about ? A thousand items (a few kB) ? A billion (a few GB) ? – Nelfeal Jun 21 '16 at 11:48
  • In the biggest test case I have, the mother object with the biggest list has 10000 elements. However, there are 23000 mother objects in that case. So, we could speak of a total of 230,000,000 "basic structs" as maximum, given there are not bigger cases than this. – Guillem Tb Jun 21 '16 at 13:02

2 Answers2

0

From the comments :

n the biggest test case I have, the mother object with the biggest list has 10000 elements. However, there are 23000 mother objects in that case. So, we could speak of a total of 230,000,000 "basic structs" as maximum, given there are not bigger cases than this.

Use vectors.

You shouldn't worry about memory fragmentation when the biggest contiguous array of memory you need contains about 10000 elements (let's say 30 bytes per element, that means 300kB). Today's memory models are efficient enough, they can manage a few kilobytes of contiguous memory. If you want to know more about memory fragmentation, here's a question about it.

The fact that you can have a lot of "mother objects" doesn't matter, since they don't require to be contiguous in memory.

You can also read about deques if you want to dig a little deeper.

Community
  • 1
  • 1
Nelfeal
  • 12,593
  • 1
  • 20
  • 39
  • Ok, I'll do. However, I'd like to ask one thing more. Using a pointer to vector would be better or worse than the raw data? I don't know if having a big attribute that can also grow bigger is detrimental and such it'd be better to store it somewhere else outside the object. – Guillem Tb Jun 21 '16 at 16:45
  • @GuillemTb `std::vector` already uses a pointer under the cover. It has to because it manages memory allocation for you : the actual data location may change (during reallocation). An `std::vector` probably contains three pointers : begin, end, end-of-storage. They can be read from `::begin`, `::end` and `::capacity` (that last one doesn't return a pointer, but `::begin() + ::capacity()` gives the location for the end of storage. – Nelfeal Jun 21 '16 at 17:10
0

It shouldn't make a big difference unless the sequence is very big, but vectors use contiguous memory, so they don't lead to fragmentation, whereas if you do it with a list, it will be asking for space in different portions of the memory, witch could eventually lead to fragmentation.

Martin Ventura
  • 167
  • 1
  • 3
  • 14