Hello everyone,
Why deque does not provide capacity and reserve function?
thanks in advance,
George
Hello everyone,
Why deque does not provide capacity and reserve function?
thanks in advance,
George
Found this by searching for "deque capacity:"
GotW #54: Using Vector and Deque
Thanks robatino,
Found it, here it is.
--------------------
A deque has no such problem, and having a deque::reserve() before a large number of push_back()s would not eliminate any allocations (or any other work) because none of the allocations are redundant; the deque has to allocate the same number of extra pages whether it does it all at once or as elements are actually appended.
--------------------
Why "none of the allocations are redundant" and "allocate the same number of extra pages whether it does it all at once or as elements are actually appended"?
I do not know why in internal implementation deque can not reserve space to improve performance (for example, allocate a couple of chunks in advance)? If yes, why not provide reserve function?
regards,
George
Why does a vector allocate space in advance? Is it because allocating space early is faster than waiting until later? Or is there another reason?
First answer that, then you can think about how the situation differs with a deque.
I agree. It so happens that the deque will already reserve some space. That's the point.But my question is make deque reserve some space is not bad idea -- it could improve performance to allocate later and manipulate memory management for chunks later. Any comments?
Why not try writing your own deque class template?
Look up a C++ Reference and learn How To Ask Questions The Smart WayOriginally Posted by Bjarne Stroustrup (2000-10-14)
The way deque works, there is no difference in performance or invalidation behaviour between pre-allocating and allocating when needed. Thus, it is not possible to explicitly pre-allocate.
All the buzzt!
CornedBee
"There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
- Flon's Law
>> Question answered.
But I'm not sure you understand.
Why does reserving space in a vector potentially increase performance?
- because if it pre-allocates and run out of space it has to allocate a bigger block, copy the old one and release the old one.
- another reason is one allocation (searching for a fitting peace of memory) is faster than doing the same thing ofetn.
I might be wrong, so George2 has to think self anyway
Although if the exact size needed isn't known in advance, and one only has an upper bound which is much larger than the "average", then asking the OS to allocate that much could be counterproductive, or even impossible if that much isn't available. For example, if the upper bound is O(N^2), and the "average" is O(N).
In this case it really was important that George2 answer that question himself. I should have been more explicit.
However, George2, I'd still like you to chime in and explain in your own words your answer to the question: Why does reserving space in a vector potentially increase performance?
Hi robatino,
I do not understand what is your context about average and upper bound, could you provide more information please? Average/upper bound for what?
Hello everyone,
As requested, here is my answer and understanding. Allocate in advance could save time to reallocate if size grows larger than capacity. My understanding. You know copy and move object instance is not an efficient thing.
regards,
George
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.
Last edited by robatino; 03-04-2008 at 04:48 AM.