Thread: capacity and reserve

  1. #1
    Registered User
    Join Date
    May 2006
    Posts
    1,579

    capacity and reserve

    Hello everyone,


    Why deque does not provide capacity and reserve function?


    thanks in advance,
    George

  2. #2
    Registered User
    Join Date
    Sep 2006
    Posts
    835
    Found this by searching for "deque capacity:"

    GotW #54: Using Vector and Deque

  3. #3
    Registered User
    Join Date
    May 2006
    Posts
    1,579
    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?

    Quote Originally Posted by robatino View Post
    Found this by searching for "deque capacity:"

    GotW #54: Using Vector and Deque

    regards,
    George

  4. #4
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    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.

  5. #5
    Registered User
    Join Date
    May 2006
    Posts
    1,579
    Thanks Daved,


    I understand why vector needs reserve method. 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?

    Quote Originally Posted by Daved View Post
    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.

    regards,
    George

  6. #6
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    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?
    I agree. It so happens that the deque will already reserve some space. That's the point.

    Why not try writing your own deque class template?
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  7. #7
    Registered User
    Join Date
    May 2006
    Posts
    1,579
    Thanks laserlight,

    What do you mean "so happens that the deque will already reserve some space."?

    Quote Originally Posted by laserlight View Post
    I agree. It so happens that the deque will already reserve some space. That's the point.

    Why not try writing your own deque class template?

    regards,
    George

  8. #8
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    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

  9. #9
    Registered User
    Join Date
    May 2006
    Posts
    1,579
    Thanks CornedBee,


    Quote Originally Posted by CornedBee View Post
    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.
    Question answered.


    regards,
    George

  10. #10
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    >> Question answered.
    But I'm not sure you understand.

    Why does reserving space in a vector potentially increase performance?

  11. #11
    Registered User
    Join Date
    Nov 2006
    Posts
    519
    - 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

  12. #12
    Registered User
    Join Date
    Sep 2006
    Posts
    835
    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).

  13. #13
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    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?

  14. #14
    Registered User
    Join Date
    May 2006
    Posts
    1,579
    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?

    Quote Originally Posted by robatino View Post
    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).
    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

  15. #15
    Registered User
    Join Date
    Sep 2006
    Posts
    835
    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Vector vs. array V2.
    By matsp in forum C++ Programming
    Replies: 38
    Last Post: 11-26-2008, 01:05 AM
  2. Can you free memory allocated by a std::string?
    By BrianK in forum C++ Programming
    Replies: 17
    Last Post: 05-15-2008, 11:57 AM
  3. Error with a vector
    By Tropicalia in forum C++ Programming
    Replies: 20
    Last Post: 09-28-2006, 07:45 PM
  4. Help!A simple question...
    By Lorin_sz in forum C++ Programming
    Replies: 5
    Last Post: 03-15-2005, 05:07 PM
  5. Glad this board is back! Vector question
    By hpy_gilmore8 in forum C++ Programming
    Replies: 9
    Last Post: 02-23-2004, 12:13 PM