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

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).

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...

Quote:

---

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.

> 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)).

>> 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.

Quote:

---

Originally Posted by Daved

>> 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?

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.

Quote:

---

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>.

But why would you need to maintain those iterators during a push_back operation? They would be used during the algorithm and discarded.

Quote:

---

Originally Posted by Daved

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)?

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.