How to size a vector properly?

Question

One place where you can run into a performance issue, is not sizing the vector correctly to begin with.

So, how does one size a vector correctly when it is a property of a class? Is there a (best) way to set the capacity of vector (at initialisation)?

score 2 · Accepted Answer · edited Dec 05 '12 at 13:00

Yes there is. See the reserve method. It will request that a vector's capacity be at least enough to contain the number of elements sent as its argument. If you can anticipate an upper bound on the number of items that you want to store in a vector, then you can reserve that amount of space in your vector.

Example from the above link -

// vector::reserve
#include <iostream>
#include <vector>

int main ()
{
    std::vector<int>::size_type sz;

    std::vector<int> foo;
    sz = foo.capacity();
    std::cout << "making foo grow:\n";
    for (int i=0; i<100; ++i) {
        foo.push_back(i);
        if (sz!=foo.capacity()) {
            sz = foo.capacity();
            std::cout << "capacity changed: " << sz << '\n';
        }
    }

    std::vector<int> bar;
    sz = bar.capacity();
    bar.reserve(100);   // this is the only difference with foo above
    std::cout << "making bar grow:\n";
    for (int i=0; i<100; ++i) {
        bar.push_back(i);

        // This block will execute only once
        if (sz!=bar.capacity()) {
            sz = bar.capacity();
            std::cout << "capacity changed: " << sz << '\n';
        }
    }

    return 0;
}

You will see that as you add more elements to the foo vector, its capacity keeps increasing, but in the second case, since it has already reserved 100 element's space, the capacity is changed only once.

Here is a running example.

The cost of failing to `reserve` is significant, but not ridiculous. If the `vector` grows capacity by a factor of phi (the golden ratio) every time you pass it, doing naive `push_back` will cause you to copy each element an average of 2.6 times if I did the math right: `(1/(1-1/phi))`. I am given to understand that a phi-capacity multiplier is typical, and in general some kind of exponential capacity growth is effectively required by the standard. One thing you should not do is before each `push_back` call `vec.reserve(vec.capacity()+1)`. That would O(n^2) yourself... — Yakk - Adam Nevraumont, Dec 05 '12 at 12:33
@Yakk - the original implementation in the STL (before it was adopted into the C++ standard) used a growth factor of 2. Later implementations of the standard library have, I believe, pretty much settled on 1.5. — Pete Becker, Dec 05 '12 at 12:40

score 1 · Answer 2 · answered Dec 05 '12 at 12:21

Considering the class is given a value during the constructor the smart thing would be to store an initial size of the vector. Inefficiency comes along when the user is constantly extending the size of the vector as opposed to setting a base length of the vector to begin with.

//consider the vector reads in chars from a string
VecClass::VecCalss(char * str)
{
    size_t LEN = strlen(str);
    Vect = std::vector<char>(LEN, '\0'); //start with the initial size of the char
}

setting an initial size reduces the amount of times a vector is needed to be extended in a program.

EDIT: or the reserve method would do just about the same, never knew a reserve function existed(pretty handy!).

How to size a vector properly?

2 Answers2