[RESOLVED] reallocating vectors

[kempofighter]

I've seen numerous threads on the question related to whether vector elements are always stored in contiguous memory. I think I understand but I just want to ask some of the experienced programmers if vector can be trusted to always keep things contiguous even after reallocating.

Lets just use a simple example where I have:

std::vector<unsigned int> dataContainer(1024);
dataContainer.reserve(2048);

So I have created a vector containing 1024 elements and a capacity of 2048. So I can insert another 1024 elements before reallocation occurs. If later, I do this:

// double capacity
dataContainer.reserve(4096)

Is the vector still contiguous? Will it release the original memory and reallocate a new block such that all elements can be moved and put into a new block of memory where elements can continue to be contiguous? If I understand things correctly, this is the reason that sometimes you want a deque. Because a deque won't move things around if you add capacity or insert in the middle. It will maintain pointers to different chunks of memory. If a vector is guaranteed to contain contiguous elements, it sometimes must do a tremendous amount of copying especially if you exceed the initial capacity of the object. If program is using lots of heap memory, the vector cannot be fragmented so reallocating *could involve* moving all existing elements to a new block of memory. is that right?

In my program, I expect that I may have to reallocate occasionally. If I do I will reserve an additional chunk so that I can minimize reallocation. I just want to make sure it is safe and portable to treat vector as a dynamic array and trust that memory will be rearranged even after increasing capacity significantly.

Thanks in advance for the help.

Shawn

[jfaust]

vector will always be contiguous, even after reallocating.

The usual reason for choosing a deque over a vector is that it may not be possible for the OS to find a large block of contiguous memory, and the operation may fail.

Performance is probably not an issue. vectors grow exponentially, so allocation is done in "amortized constant time" over the lifetime of the vector.

If you are worried about performance, benchmark it first on a release build.

Jeff

[exterminator]

The idea is to call reserve knowledgeably guessing the closest size that you can grow upto.

If you keep calling reserve multiple times, what purpose does it serve? It is nearly the same as letting the vector work out its capacity. You are decreasing the reallocation calls but still you are causing them at times. If 4096 blocks are not a problem to reserve at the beginning itself (which I dont think would be if thats the exact figure, but if it is larger, may be), then do it, rather than calling reserve twice or more.

deque does not have reserve functionality.