set vector step length when resize?

[eltonsky]

Hi everyone,

When I use vectory.push_back(obj), if the length is out of reserved bound, it will deallocate the whole vector and reallocate a big piece of memory. From my understanding I think c++ only allocates 1 more place for the new obj. This is quite inefficient. Is there a way to set the step length whenever the size is out of bound? e.g. 50 more spaces.

Regards,
Elton

[JLBorges]

> From my understanding I think c++ only allocates 1 more place for the new obj.

No. C++ requires that insertion of an element at the end take amortized constant time.

> Is there a way to set the step length whenever the size is out of bound? e.g. 50 more spaces.

std::vector<>::reserve()

The storage of the vector is handled automatically, being expanded and contracted as needed. Vectors usually occupy more space than static arrays, because more memory is allocated to handle future growth. This way a vector does not need to reallocate each time an element is inserted, but only when the additional memory is exhausted. The total amount of allocated memory can be queried using capacity() function. Extra memory can be returned to the system via a call to shrink_to_fit().

Reallocations are usually costly operations in terms of performance. reserve() function can be used to eliminate reallocations if the number of elements is known beforehand. http://en.cppreference.com/w/cpp/container/vector

[eltonsky]

Hello JL Borges,

You are right I think I should use reserve().

Actually in my case, the vector always need to extend. To clarify my question a little bit, in the snippet below I guess push_back/insert doesn't reallocate more space automatically..

...
vector<int> v1;
v1.reserve(16);

for(int i=0;i<10000;I++) {

  // I think I need to do this, as push_back or insert doesn't do this automatically, is it?
  if(v1.capacity() <= i)
      v1.reserve(v1.capacity()<<1);

  v1.push_back(i);   
}
...

So I need to reserve more space whenever needed.

Regards,
Elton

[firedraco]

No, push_back and insert do increase the size if needed so you don't need to increase it yourself.

[JLBorges]

Try this:

#include <iostream>
#include <vector>

int main()
{
    std::vector<int> vec ;
    vec.reserve(17) ;
    std::cout << "size: " << vec.size() << "  capacity: " << vec.capacity() << '\n' ;
    std::vector<int>::size_type old_capacity = vec.capacity() ;

    for( int i = 0 ; i < 100000 ; ++i )
    {
        vec.push_back(i) ;
        if( vec.capacity() !=  old_capacity )
        {
            std::cout << "size: " << vec.size() << "  capacity: " << vec.capacity() << '\n' ;
            old_capacity = vec.capacity() ;
        }
    }
}

[eltonsky]

Thanks JLBorges,

This is answers my question, push_back does increase the capacity 2x when there's not enough space. Brilliant.

Cheers,
Elton

[JLBorges]

> push_back does increase the capacity 2x when there's not enough space.

Not necessarily doubling every time.

What is required is that if the current size and capacity is N, and capacity is increased by M, the amortized time taken to add M elements at the back is:

( ( O(N) * 1 ) + O(1) * (M-1) ) / N.

This needs to be O(1); therefore M must be proportional to N.

If N is small, say 2, instead of doubling the capacity, an implementation may decide to increase it to 8 * N. Conversely, if N is large, say 100000, an implementation may decide to increase it to 1.25 * N. On a platform where memory is tight, an implementation could be more conservative. And on a platform with oodles of memory, an implementation can be more aggressive. All that is required is that M must be proportional to N.

In practice, frequent invocations of reserve may degrade performance. If we have a rough idea of what the eventual size may be, call reserve once and leave the rest to the implementation.