Choice between vector::resize() and vector::reserve()

Question

I am pre-allocating some memory to my a vector data member. Example:

class A {
    vector<string> t_Names;
  public:
      A () : t_Names(1000) {}
};

At some point in time, if the t_Names.size() equals 1000, I intend to increase the size by 100. Once it reaches 1100, increase it by 100 and so on.

Which do I choose out of vector::resize() and vector::reserve()? Is there any better choice in this kind of scenario?

Edit: I have sort of precise estimate for the t_Names. I estimate it to be around 700 to 800. However in certain (seldom) situations, it can grow more than 1000.

You realize that doing this means that vector growth is no longer _amortized constant time_ and you lose one of the performance benefits of using `std::vector`. — Blastfurnace, Sep 13 '11 at 07:37
Related, see [C++ Made Easier: How Vectors Grow](http://www.drdobbs.com/c-made-easier-how-vectors-grow/184401375) on Dr. Dobbs site. — jww, Dec 22 '16 at 05:21

score 345 · Accepted Answer · edited Mar 30 '16 at 18:18

345

The two functions do vastly different things!

The resize() method (and passing argument to constructor is equivalent to that) will insert or delete appropriate number of elements to the vector to make it given size (it has optional second argument to specify their value). It will affect the size(), iteration will go over all those elements, push_back will insert after them and you can directly access them using the operator[].

The reserve() method only allocates memory, but leaves it uninitialized. It only affects capacity(), but size() will be unchanged. There is no value for the objects, because nothing is added to the vector. If you then insert the elements, no reallocation will happen, because it was done in advance, but that's the only effect.

So it depends on what you want. If you want an array of 1000 default items, use resize(). If you want an array to which you expect to insert 1000 items and want to avoid a couple of allocations, use reserve().

EDIT: Blastfurnace's comment made me read the question again and realize, that in your case the correct answer is don't preallocate manually. Just keep inserting the elements at the end as you need. The vector will automatically reallocate as needed and will do it more efficiently than the manual way mentioned. The only case where reserve() makes sense is when you have reasonably precise estimate of the total size you'll need easily available in advance.

EDIT2: Ad question edit: If you have initial estimate, then reserve() that estimate. If it turns out to be not enough, just let the vector do it's thing.

edited Mar 30 '16 at 18:18

Community

1
1

answered Sep 13 '11 at 06:49

Jan Hudec

73,652
13
125
172

I have edited the question. I do have certain estimate for the `vector`. – iammilind Sep 13 '11 at 08:37
1

"The only case where reserve() makes sense is when you have reasonably precise estimate of the total size you'll need easily available in advance." - not strictly true, since calling `reserve()` yourself at specific times might sometimes help you manage any pointers or iterators that you have for elements of the vector (and in particular that they're invalidated by reallocation). Not that there's any sign in this question that such things are going on. And it's true that you need to know an upper bound on how many elements you'll add during the time your pointers/iterators are needed. – Steve Jessop Sep 13 '11 at 09:20
@Steve: Yes, right. Any code relying on that is somewhat fragile though, since if you make a mistake and don't allocate enough, you'll be up for very hard debugging session. – Jan Hudec Sep 13 '11 at 09:25
4

@Jan: well, it's fragile or not according to how difficult you've made it for yourself to maintain the required property. Something like `x.reserve(x.size() + newdata); vector::iterator special_element = get_special_element(x); for (int i = 0; i < newdata; ++i) { if some_function(i, special_element) x.push_back(i); }` is pretty robust as far as reserving the space is concerned. I've no idea how many elements will actually be added, but I have an upper bound. Of course when in doubt, with vectors you can just use indexes instead of iterators, the difference is usually negligible. – Steve Jessop Sep 13 '11 at 09:33
5

Your wording makes sense to someone already aware of the correct answer, but could easily mislead people needing to ask the question. "resize()...will insert given number of elements to the vector" - only true the first time it's used - it generally inserts the difference between the requested number and the pre-existing `size()`. "The reserve() method only allocates memory" - it may or may not allocate memory depending on whether `capacity()` is already sufficient, it may also need to move elements and deallocate their original memory. "want to avoid a couple of allocations" and copies etc – Tony Delroy Dec 28 '11 at 08:46
31

Actually, reserving before pushing is vital and must be used. Assume that you are coding some kind of 3d model loader and the model has like 15000 vertices. If you try to push_back each vertex while loading without pre-allocating them first, it will take serious time. I personally experienced that, I tried to load a car .obj model with near 100000 vertices, It took 30 seconds. Then I refactored the code using pre-allocation with .reserve(), now it takes 3 seconds. Just putting a .reserve(100000) in the beginning of the code saved 27 seconds. – deniz Oct 12 '13 at 07:25
"will insert given number of elements to the vector" makes it sound like the primary argument of the function is the number of elements to add, not the desired size of the vector. – Pharap Sep 07 '14 at 06:10
To spell this out a bit more, think of the consequences of calling `push_back(element)` on your vector after calling `reserve()` or `resize()`. In case you `resize()`d the vector, the effect is probably not what you intended. – Tom Sep 13 '16 at 09:10
2

@deniz That's trivial true at 100000 scale, but very not true at the 100-300 scale, where reserving can be wasteful if done unnecessarily. – deworde Mar 21 '17 at 10:20
1

@deniz Actually, when storing something like vertices, and you know how many will come, then `resize()` and assign by using `operator[]` or a walking pointer. Saves even more time. Also don't over-use `reserve`. One should at least be very wary not to cripple `push_back` performance by reserving in small increments. E.g. something like `vec.reserve(vec.size() + 1)`, to make sure that the following `push_back` won't throw, is poison for performance. – Paul Groke Jul 18 '17 at 17:28
1

@PaulGroke You might be right for sufficiently basic types, but the statement is hard to rate without a scenario/benchmark. Also: Why would `push_back()` "throw" if the current `capacity` wasn't sufficient for a new element? How would `reserve()` solve that? It seems to me that if your `vector` is going to throw, it's because it can't allocate any more memory, so `reserve()` will fail just as much. And even without throwing, such a `reserve()` seems pointless because the `push_back()` (or `insert` or `emplace` etc.) would do it anyway. – underscore_d Nov 19 '18 at 00:53
@underscore_d The point is that after you have successfully `reserve()`d, you're guaranteed that `push_back` will not throw (assuming the ctor of the element doesn't throw). That means you can move the point of failure to some earlier point in time. Which is often required or at least very convenient when trying to keep invariants. – Paul Groke Nov 20 '18 at 07:16
@underscore_d, the allocation that `push_back` may call may fail with `std::bad_alloc` exception. Very rare and completely fatal for most software, but there are cases where one might actually care. – Jan Hudec Nov 20 '18 at 21:26

score 45 · Answer 2 · edited Mar 03 '14 at 15:45

45

resize() not only allocates memory, it also creates as many instances as the desired size which you pass to resize() as argument. But reserve() only allocates memory, it doesn't create instances. That is,

std::vector<int> v1;
v1.resize(1000); //allocation + instance creation
cout <<(v1.size() == 1000)<< endl;   //prints 1
cout <<(v1.capacity()==1000)<< endl; //prints 1

std::vector<int> v2;
v2.reserve(1000); //only allocation
cout <<(v2.size() == 1000)<< endl;   //prints 0
cout <<(v2.capacity()==1000)<< endl; //prints 1

Output (online demo):

So resize() may not be desirable, if you don't want the default-created objects. It will be slow as well. Besides, if you push_back() new elements to it, the size() of the vector will further increase by allocating new memory (which also means moving the existing elements to the newly allocated memory space). If you have used reserve() at the start to ensure there is already enough allocated memory, the size() of the vector will increase when you push_back() to it, but it will not allocate new memory again until it runs out of the space you reserved for it.

edited Mar 03 '14 at 15:45

phonetagger

7,701
3
31
55

answered Sep 13 '11 at 06:47

Nawaz

353,942
115
666
851

8

After doing `reserve(N)`, we can use `operator []` harmlessly. correct ? – iammilind Sep 13 '11 at 08:48
2

While most implementations will allocate the exact amount you request by `reserve`, the specification only requires it allocates at least that much, so some implementations may round up to some boundary and thus show higher capacity than 1000. – Jan Hudec Sep 13 '11 at 08:49
18

@iammilind: No, if the index is greater or equal to `v.size()`. Note that `reserve(N)` doesn't change `size()` of vector. – Nawaz Sep 13 '11 at 08:51
7

@iammilind: INcorrect. After calling reSERVE, no entries are added, only enough memory for adding them is obtained. – Jan Hudec Sep 13 '11 at 08:51

score 2 · Answer 3 · answered Sep 13 '11 at 06:51

2

From your description, it looks like that you want to "reserve" the allocated storage space of vector t_Names.

Take note that resize initialize the newly allocated vector where reserve just allocates but does not construct. Hence, 'reserve' is much faster than 'resize'

You can refer to the documentation regarding the difference of resize and reserve

answered Sep 13 '11 at 06:51

dip

530
3
7

1

Please refer here instead: [vector](http://www.sgi.com/tech/stl/Vector.html) and [capacity](http://www.sgi.com/tech/stl/Vector.html#3) _([why?](http://programmers.stackexchange.com/questions/88241/whats-wrong-with-cplusplus-com]))_ – sehe Sep 13 '11 at 08:06
1

Thanks for the addition of link, sehe – dip Sep 13 '11 at 08:58

score 2 · Answer 4 · answered Sep 13 '11 at 06:57

reserve when you do not want the objects to be initialized when reserved. also, you may prefer to logically differentiate and track its count versus its use count when you resize. so there is a behavioral difference in the interface - the vector will represent the same number of elements when reserved, and will be 100 elements larger when resized in your scenario.

Is there any better choice in this kind of scenario?

it depends entirely on your aims when fighting the default behavior. some people will favor customized allocators -- but we really need a better idea of what it is you are attempting to solve in your program to advise you well.

fwiw, many vector implementations will simply double the allocated element count when they must grow - are you trying to minimize peak allocation sizes or are you trying to reserve enough space for some lock free program or something else?

"_reserve when you do not want the objects to be initialized when reserved._" The correct formulation is when you do not want the objects to **exist**. It's not like an uninitialised array of a trivially constructible type, where the objects can't be read but could be assigned to; rather, only memory is reserved, but no objects exist in it, so they can't be accessed using `operator[]` or anything. — underscore_d, Nov 19 '18 at 00:58

Choice between vector::resize() and vector::reserve()

4 Answers4

Linked

Related