[RESOLVED] Vector reserving memory, vs linked list

[nixius]

Hey all,

due to the generic nature of what I am searching for I am finding it difficult to google my question so sorry if it seems obvious.

When a vector is initialised it creates a space in memory, if reserve is used it will reserve enough for X elements.

Does this mean then, that somewhere in memory you will need a chunk of X*NumBytes of unused space to allocate?

What I am trying to get at is, if you were working on a system with limited memory would it be better to use a linked list because you can allocate memory all over the place and point to it as opposed to needing a chunk in one place?

That is my perception so far, please do correct me if that is wrong.

[laserlight]

Does this mean then, that somewhere in memory you will need a chunk of X*NumBytes of unused space to allocate?

Yes, you would.

What I am trying to get at is, if you were working on a system with limited memory would it be better to use a linked list because you can allocate memory all over the place and point to it as opposed to needing a chunk in one place?

I think that you still have to consider the complexity of the operations. Also, if the objects that are stored are not very large, then the additional overhead of book keeping for a linked list might become significant in comparison to a vector. Perhaps a deque would be a compromise, where you want similiar complexity as the operations of a vector, but also want smaller chunks of memory to be allocated, which is the typical implementation of a deque (a doubly linked list of blocks).

[nixius]

Perhaps a deque would be a compromise

Thanks, I will look into Deque, it is something I have never actually studied.