A question regarding reallocation

Here is the code,

Code:

---

vector<int> v;

for(int i = 0;i<1000;++i)
    v.push_back(i);

---

Is it possible to know how many reallocations happen during the loop? Thanks.

Why do you want to know how many reallocations will happen? If that is a concern, then insert a:

Code:

---

v.reserve(1000);

---

before the loop, upon which you know that the number of reallocations will be zero.

Quote:

---

Originally Posted by LarryChen

Is it possible to know how many reallocations happen during the loop? Thanks.

---

Yes it's possible to determine this - but it's a real hack and not recommended. You need to modify the STL vector header for push_back. Do not try this at home unless you absolutely know what you are doing and all usual precautions are taken!

On my system, the answer is 18.

As laserlight asked, why do you want to know? A more pertinent question might be 'How do I know how many elements are used in the vector'. If this is known then the vector can be pre-sized to reduce/eliminate reallocations. The size() class function returns the actual number of elements in the vector.

You can use the capacity() function to determine if a reallocation occurred:

Code:

---

    vector<int> v;

    size_t saved_capacity = v.capacity();
    int    number_of_reallocations = 0;

    for (int i=0; i<1000; ++i)
    {
        v.push_back(i);
        size_t current_capacity = v.capacity();

        if (current_capacity != saved_capacity)
        {
            ++number_of_reallocations;
            saved_capacity = current_capacity;
        }
    }

---

On my system, (VC 2010), the answer is also 18.

Nice one!:cool:

But as stated... don't worry about it, assume that the designers of the lib tried their best to find a good balance between performance (as few reallocations as possible) and memory usage (as few excess as possible).

if you know you'll need a certain amount of items, reserve that amount.
if you know there'll be between X and Y items, then reserve at least X, at most Y, but you probably want to find some "magic" amount in between that'll give you the best case scenario. This'll be different for each case so nobody here can help, knowing what you're making and how your datasets will behave is the only thing that'll help you here.


if you don't trust the standard lib... then make your own.

Quote:

---

Originally Posted by Philip Nicoletti

You can use the capacity() function to determine if a reallocation occurred:

Code:

---

    vector<int> v;

    size_t saved_capacity = v.capacity();
    int    number_of_reallocations = 0;

    for (int i=0; i<1000; ++i)
    {
        v.push_back(i);
        size_t current_capacity = v.capacity();

        if (current_capacity != saved_capacity)
        {
            ++number_of_reallocations;
            saved_capacity = current_capacity;
        }
    }

---

On my system, (VC 2010), the answer is also 18.

---

This is what I am looking for. Thanks.

@LarryChen: Don't assume the answer will always be the same as this, though. On my system (Ubuntu Linux using g++ 4.2.3) the following code (Philip Nicoletti's code with some output added):

Code:

---

#include <vector>
#include <iostream>

using namespace std;

int main()
{
        vector<int> v;

        size_t saved_capacity = v.capacity();
        int    number_of_reallocations = 0;

        for (int i=0; i<1000; ++i)
        {
                v.push_back(i);
                size_t current_capacity = v.capacity();

                if (current_capacity != saved_capacity)
                {
                        ++number_of_reallocations;
                        saved_capacity = current_capacity;

                        cout << "Reallocation at I = " << i << "\tCapacity\t" << current_capacity << endl;

                }
        }

        cout << endl << "Total reallocations = " << number_of_reallocations << endl;

        return 0;
}

---

Gives the following output:

Code:

---

Reallocation at I = 0    Capacity        1
Reallocation at I = 1    Capacity        2
Reallocation at I = 2    Capacity        4
Reallocation at I = 4    Capacity        8
Reallocation at I = 8    Capacity        16
Reallocation at I = 16  Capacity        32
Reallocation at I = 32  Capacity        64
Reallocation at I = 64  Capacity        128
Reallocation at I = 128  Capacity        256
Reallocation at I = 256  Capacity        512
Reallocation at I = 512  Capacity        1024

Total reallocations = 11

---

I.e. there are 11 reallocations, and the capacity is doubled each time a reallocation is required.

It would be interesting to see what strategy the VC 2010 implementation is using to take 18 reallocations.

VC 2010 : 1,2,3,4,5,6,9,13,19,28,42,63,94,211,316,474,711,1066

I know I did this before with VC version 6, and it doubled each time.

edit: so it is using 1.5 as the factor in each case (with a minimum increase
of 1 in the case of 1 to 2).