CODEWITHSUNDEEP
c++vectorstdvector
Othman Benchekroun
Othman Benchekroun

Reputation: 2018

std::vector capacity smart implementation

I know that std::vector capacity behavior is implementation specific, is there any smart implementation that does this :

vector<int> v;
for(int i = 0; i < 10000 ; ++i){
    v.push_back(i);
}

At initialisation, it can predict the capacity of the 'vector', in this example it will initiate the capacity to 10000

I am asking for this because I always thought gcc does this kind of predictions, but I couldn't find anything about this ... I think I have seen this somewhere, so is there any implementation that does this ?

Upvotes: 1

Views: 199

Answers (2)

Joel Falcou
Joel Falcou

Reputation: 6357

Nothing get predicted. However:

  • one can use reserve to preallocate the maximum required amount of elements. push_back will then never need to reallocate.

  • push_back use the growth strategy of vector that allocate more than just one mor element. IIRC the growth factor is 2, which means that the number of reallocation in a serie of push_back tends to become logarithmic. Therefore, the cost of N calls to push_back converges toward log2(N).

Upvotes: 3

blashser
blashser

Reputation: 1031

It exists different constructor for std::vector. One of these possibilities is to say the default value and the number of values that you want to your vector.

From the documentation of std::vector:

// constructors used in the same order as described above:
std::vector<int> first;                                // empty vector of ints
std::vector<int> second (4,100);                       // four ints with value 100
std::vector<int> third (second.begin(),second.end());  // iterating through second
std::vector<int> fourth (third);                       // a copy of third

This is useful if you know in advance the maximum size of your vector.

Upvotes: -4

Related Questions