reserve method of vector

This is a discussion on reserve method of vector within the C++ Programming forums, part of the General Programming Boards category; Hello everyone, I read MSDN document about reserve method of vector, but I can not find answers to the following ...

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

    reserve method of vector

    Hello everyone,


    I read MSDN document about reserve method of vector, but I can not find answers to the following 2 questions after reading it,

    1. if we reserve 10,000 size, will the memory actually be occupied 10,000 size (like committed memory of Windows Virtual Memory management) or the memory will just be reserved for future use (like reserved memory of Windows Virtual Memory management);

    2. Will reserve method of vector improve performance? If yes, could anyone share some experiences please?

    If reserve method has any additional benefits beyond performance, please also let me know. :-)


    thanks in advance,
    George

  2. #2
    Registered User
    Join Date
    Jan 2005
    Posts
    7,319
    1. The memory will be requested and held by the program just as if you had used new to allocate 10000 objects yourself (although more memory might be requested by the vector if it prefers specific increments).

    2. Theoretically, yes, if you are using push_back to add many elements to an empty vector, then calling reserve would help avoid the several reallocations it would take to eventually get big enough to hold all the data. However, the only programs I have seen that noticeably benefit from reserve are test programs meant to test vector's performance. Otherwise it does a good job of keeping re-allocations minimal. Bjarne Stroustrup says in his FAQ that he no longer uses reserve for that purpose because it wasn't helping him significantly: http://www.research.att.com/~bs/bs_f...low-containers (last paragraph of this section).

  3. #3
    and the hat of sweating
    Join Date
    Aug 2007
    Location
    Toronto, ON
    Posts
    3,545
    I've never used reserve(), since I usually don't create huge vectors, but if I were you I probably wouldn't worry about using reserve() unless you actually notice a performance issue and find out exactly where the bottleneck is.
    From what I've read, most implementations of std::string & std::vector start with some default size, then once it's exceeded, it automatically allocates twice as much as it had before. So it might go something like: 256, 512, 1024, 2048...

  4. #4
    The larch
    Join Date
    May 2006
    Posts
    3,573
    From what I've read, most implementations of std::string & std::vector start with some default size, then once it's exceeded, it automatically allocates twice as much as it had before. So it might go something like: 256, 512, 1024, 2048...
    I tried it with both MingW and VC++ and in both an empty vector starts out with zero capacity. So MingW went 0, 1, 2, 4, 8, 16 etc, and MS VC++ grew by a factor of 1.5: 0, 1, 2, 3, 4, 6, 9 etc.

    But the idea is that while reallocations are frequent, the number of items is low and copying wouldn't be a problem. And by the time the array has grown large, reallocations are relatively infrequent.
    Last edited by anon; 11-15-2007 at 10:55 AM.
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  5. #5
    Registered User
    Join Date
    Sep 2006
    Posts
    835
    > If reserve method has any additional benefits beyond performance, please also let me know. :-)

    Performance is the only benefit (such as it is). It never affects correctness. For that, you have to make sure that the size (not just capacity) are big enough when you read or write elements. If you add or delete elements stackwise using push_back() and pop_back(), the size is managed automatically. If you need to write elements nonconsecutively, then you have to make sure that the vector has the necessary size in advance (either by using resize() or the vector constructor that takes the size as argument), and here there is no use for reserve at all, since setting the size to its final value automatically makes the capacity big enough. Even when using push_back() and pop_back(), if I know in advance an upper bound on the size, and it's not too much bigger than the "average", I use reserve anyway, as a "comment" that this is as big as the vector can get, though this is not enforced. Note that if the mathematically largest possible size is much bigger than the "average", using reserve() could actually hurt performance by demanding too much memory (say if the upper bound was O(N^2) but the "average" maximum size was O(N)).

  6. #6
    Registered User
    Join Date
    Jan 2005
    Posts
    7,319
    >> It never affects correctness.

    Actually, it can affect correctness.

    Using reserve guarantees that your iterators will not become invalidated when you push_back data on to the vector up until the size reserved. So if you are maintaining iterators that refer to vector elements then reserve might be necessary to keep your program correct.

  7. #7
    Registered User
    Join Date
    Sep 2006
    Posts
    835
    Quote Originally Posted by Daved View Post
    >> It never affects correctness.

    Actually, it can affect correctness.

    Using reserve guarantees that your iterators will not become invalidated when you push_back data on to the vector up until the size reserved. So if you are maintaining iterators that refer to vector elements then reserve might be necessary to keep your program correct.
    Yes, you're right. I've been using indices exclusively to access vector elements and forgot about the iterator invalidation issue. (I struggled with that for a while and then decided that for what I was working on, indices would probably be just as efficient and less troublesome.) Just out of curiosity, could you give some examples of situations where using iterators instead is necessary?

  8. #8
    Registered User
    Join Date
    Jan 2005
    Posts
    7,319
    I generally use indexes as well, at least for vectors. I can't think of a situation where an iterator would work better than an index.

    The Stroustrup FAQ comment is what reminded me of it. He mentioned that he only uses reserve in those cases, but I don't know how often those occur for him either.

  9. #9
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,893
    Just out of curiosity, could you give some examples of situations where using iterators instead is necessary?
    When you call a standard or 3rd party function that expects iterators, like those in <algorithm>.
    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

  10. #10
    Registered User
    Join Date
    Jan 2005
    Posts
    7,319
    But why would you need to maintain those iterators during a push_back operation? They would be used during the algorithm and discarded.

  11. #11
    Registered User
    Join Date
    Nov 2006
    Posts
    519
    Quote Originally Posted by Daved View Post
    I generally use indexes as well, at least for vectors. I can't think of a situation where an iterator would work better than an index.
    Aren't iterators the better style because one is able to see immediately if the loop will change the vector (const_iterator vs. iterator)?

  12. #12
    Registered User
    Join Date
    Jan 2005
    Posts
    7,319
    When looping I prefer iterators (although my reasoning is usually that it's more consistent with other containers).

    I was referring to situations where you must maintain a reference to a vector element. I would use an index for that purpose, not an iterator.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Vector of Strings help
    By CowsOFFmylawn in forum C++ Programming
    Replies: 7
    Last Post: 01-11-2009, 08:38 PM
  2. vector of arrays of pointers to structures
    By Marksman in forum C++ Programming
    Replies: 13
    Last Post: 02-01-2008, 03:44 AM
  3. Glad this board is back! Vector question
    By hpy_gilmore8 in forum C++ Programming
    Replies: 9
    Last Post: 02-23-2004, 11:13 AM
  4. my vector class..easy dynamic arrays
    By nextus in forum C++ Programming
    Replies: 5
    Last Post: 02-03-2003, 09:14 AM
  5. Operators for 3D Vector Mathematics
    By Anarchist in forum C++ Programming
    Replies: 10
    Last Post: 01-31-2003, 06:33 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21