Thread: capacity and reserve

Thanks robatino,


This is what you mentioned before. Do you mean in your good practices you recommend to reserve size N if the max possible size is N ^ 2?

--------------------
For example, if the upper bound is O(N^2), and the "average" is O(N).
--------------------

Originally Posted by robatino

Well, suppose you have a vector v which grows to some size which you don't know exactly in advance, but you only know that the size has an theoretical upper bound of N*N, say, where N is some parameter in the program. Also suppose that in an average case, the vector only grows to something on the order of size N, and it's only in pathological cases that it approaches size N*N. In that case, reserve()'ing space for N*N elements could harm performance, since most of it would probably be unused, and it would be unavailable to the rest of the program, or to other programs. And the machine might not even have that much memory, in which case the reserve() would fail and probably end the program, unless it caught the exception. You would be better off just letting the vector grow on its own to whatever size is needed. BTW, on Stroustrup's website he says that after doing some profiling, he stopped using reserve() unless needed to avoid invalidating iterators. Personally I tend to use it as a "comment", to indicate that this is the maximum amount of memory this vector can require, though for the reasons I gave above I wouldn't use it at all in certain situations.

regards,
George

Hi Mats,


I do not know what do you mean "you don't need to start over searching for the next item" in your sample below, you are talking about insert all the times, right? Why mention search operation suddenly?

Originally Posted by matsp

reserve is only really useful if you have one of two situations [1]:
1. You know for certain what the size should be.
2. You can avoid invalidating iterators by reserving a sufficiently large size "for now" - say for example you can read 5 items at a time, and you use an iterator to find and potentially insert new items in the list, you may want to reserve(size()+5) to make sure you don't need to start over searching for the next item. [Of course, there may be a better solution overall if you need to do this - but that's a different matter].

[1] reserve only has a meaning for collections that are implemented as an array. Collections that consist of linked lists, binary trees and such will not benefit from reserving memory, since an insertion of a new element will not need copying all the data, so it's meaningless to say "I need this much space", because the addition of an individual item is pretty much O(1) in these types of collections.

--
Mats

regards,
George

Originally Posted by George2

Thanks robatino,


This is what you mentioned before. Do you mean in your good practices you recommend to reserve size N if the max possible size is N ^ 2?

No. In my example, since all you know is that the size is usually somewhere on the order of N (meaning it could easily be twice N, or half N, for example), then it doesn't make any sense to reserve() a specific number. Just let it grow by itself. As matsp said, it makes sense if you know the exact size needed, or if you need to avoid invalidating iterators. I also tend to do it if the maximum size needed is fairly small, even if I don't know the exact size, but that's a judgment call.