How to avoid reallocation using the STL (C++)

Question

This question is derived of the topic:

http://stackoverflow.com/questions/2280655/vector-reserve-c

I am using a datastructur of the type vector<vector<vector<double> > >. It is not possible to know the size of each of these vector (except the outer one) before items (doubles) are added. I can get an approximate size (upper bound) on the number of items in each "dimension".

A solution with the shared pointers might be the way to go, but I would like to try a solution where the vector<vector<vector<double> > > simply has .reserve()'ed enough space (or in some other way has allocated enough memory).

Will A.reserve(500) (assumming 500 is the size or, alternatively an upper bound on the size) be enough to hold "2D" vectors of large size, say [1000][10000]?

The reason for my question is mainly because I cannot see any way of reasonably estimating the size of the interior of A at the time of .reserve(500).

An example of my question:

vector > > A; A.reserve(500+1); vector > temp2; vector temp1 (666,666); for(int i=0;i<500;i++) { A.push_back(temp2); for(int j=0; j< 10000;j++) { A.back().push_back(temp1); } } Will this ensure that no reallocation is done for A?

If temp2.reserve(100000) and temp1.reserve(1000) where added at creation will this ensure no reallocation at all will occur at all?

In the above please disregard the fact that memory could be wasted due to conservative .reserve() calls.

Thank you all in advance!

Answer 1

How can reserving 500 entries in A beforehand be enough for [1000][1000]?

You need to reserve > 1000 for A (which is your actual upperbound value), and then whenever you add an entry to A, reserve in it another 1000 or so (again, the upperbound but for the second value).

i.e.

A.reserve(UPPERBOUND);

for(int i = 0; i < 10000000; ++i)
   A[i].reserve(UPPERBOUND);

BTW, reserve reserves the number of elements, not the number of bytes.

Answer 2

your example will cause a lot of copying and allocations.

vector<vector<vector<double>>>  A;
 A.reserve(500+1);
 vector<vector<double>>  temp2; 
vector<double> temp1 (666,666);
 for(int i=0;i<500;i++) 
{
 A.push_back(temp2);
 for(int j=0; j< 10000;j++)
 {
 A.back().push_back(temp1);
 }
} 

Q: Will this ensure that no reallocation is done for A?
A: Yes.

Q: If temp2.reserve(100000) and temp1.reserve(1000) where added at creation will this ensure no reallocation at all will occur at all?
A: Here temp1 already knows its own length on creation time and will not be modified, so adding the temp1.reserve(1000) will only force an unneeded reallocation.
I don't know what the vector classes copy in their copy ctor, using A.back().reserve(10000) should work for this example.
Update: Just tested with g++, the capacity of temp2 will not be copied. So temp2.reserve(10000) will not work.

And please use the source formating when you post code, makes it more readable :-).

Answer 3

The reserve function will work properly for you vector A, but will not work as you are expecting for temp1 and temp2.

The temp1 vector is initialized with a given size, so it will be set with the proper capacity and you don't need to use reserve with this as long as you plan to not increase its size.

Regarding temp2, the capacity attribute is not carried over in a copy. Considering whenever you use push_back function you are adding a copy to your vector, code like this

vector<vector<double>> temp2;
temp2.reserve(1000);
A.push_back(temp2); //A.back().capacity() == 0

you are just increasing the allocated memory for temps that will be deallocated soon and not increasing the vector elements capacity as you expect. If you really want to use vector of vector as your solution, you will have to do something like this

vector<vector<double>> temp2;
A.push_back(temp2);
A.back().reserve(1000); //A.back().capacity() == 1000

Answer 4

It seems to me that you need a real matrix class instead of nesting vectors. Have a look at boost, which has some strong sparse matrix classes.

Answer 5

Ok, now I have done some small scale testing on my own. I used a "2DArray" obtained from http://www.tek-tips.com/faqs.cfm?fid=5575 to represent a structure allocating memory static. For the dynamic allocation I used vectors almost as indicated in my original post.

I tested the following code (hr_time is a timing routine found on web which I due to anti spam unfortunately cannot post, but credits to David Bolton for providing it)

#include <vector>
#include "hr_time.h"
#include "2dArray.h"
#include <iostream>
using namespace std;

int main()
{
    vector<int> temp;

    vector<vector<int> > temp2;

    CStopWatch mytimer;

    mytimer.startTimer();

    for(int i=0; i<1000; i++)
    {
        temp2.push_back(temp);
        for(int j=0; j< 2000; j++)
        {
            temp2.back().push_back(j);
        }
    }

    mytimer.stopTimer();

    cout << "With vectors without reserved: " << mytimer.getElapsedTime() << endl;

    vector<int> temp3;

    vector<vector<int> > temp4;

    temp3.reserve(1001);

    mytimer.startTimer();

    for(int i=0; i<1000; i++)
    {
        temp4.push_back(temp3);
        for(int j=0; j< 2000; j++)
        {
            temp4.back().push_back(j);
        }
    }

    mytimer.stopTimer();

    cout << "With vectors with reserved: " << mytimer.getElapsedTime() << endl;

    int** MyArray = Allocate2DArray<int>(1000,2000);

    mytimer.startTimer();
    for(int i=0; i<1000; i++)
    {
        for(int j=0; j< 2000; j++)
        {
            MyArray[i][j]=j;
        }
    }


    mytimer.stopTimer();

    cout << "With 2DArray: " << mytimer.getElapsedTime() << endl;

    //Test
    for(int i=0; i<1000; i++)
    {
        for(int j=0; j< 200; j++)
        {
            //cout << "My Array stores :" << MyArray[i][j] << endl;
        }
    }

    return 0;
}

It turns out that there is approx a factor 10 for these sizes. I should thus reconsider if dynamic allocation is appropriate for my application since speed is of utmost importance!

Answer 6

I had the same issue one day. A clean way to do this (I think) is to write your own Allocator and use it for the inner vectors (last template parameter of std::vector<>). The idea is to write an allocator that don't actually allocate memory but simply return the right address inside the memory of your outter vector. You can easely know this address if you know the size of each previous vectors.

Answer 7

Why not subclass the inner containers and reserve() in constructors ?

Answer 8

In order to avoid copy and reallocation for a datastructure such as vector<vector<vector<double> > >, i would suggest the following:

vector<vector<vector<double> > > myVector(FIXED_SIZE);

in order to 'assign' value to it, don't define your inner vectors until you actually know their rquired dimensions, then use swap() instead of assignment:

vector<vector<double> > innerVector( KNOWN_DIMENSION );
myVector[i].swap( innerVector );

Note that push_back() will do a copy operation and might cause reallocation, while swap() won't (assuming same allocator types are used for both vectors).

Answer 9

If the Matrix does get really large and spare I'd try a sparse matrix lib too. Otherwise, before messing with allocaters, I'd try replacing vector with deque. A deque won't reallocate on growing and offers almost as fast random access as a vector.

Answer 10

This was more or less answered here. So your code would look something like this:

vector<vector<vector<double> > > foo(maxdim1,
    vector<vector<double> >(maxdim2,
    vector<double>(maxdim3)));