vector std::bad_alloc

[omr]

Hello,
the following code is crashing with an instance of std::bad_alloc

void print_partitions(vector <vector <int> > &partitions)
{
    vector <int> tmp;
    for (int i = 0; i < partitions.size(); i++)
    {
        tmp = partitions[i];
        ...
    }
}

vector <vector <int> > partitions' is being filled in another recursive function where a temporary vector <int> 'tmp_partition' fills up with values untill it is pushed back into partitions then cleared again to be filled with new values.
The first time tmp_partition is pushed back partitions holds the right values but then when tmp_partition takes new values printing the value of partition[0][i] return <error reading variable>.


any ideas on why this is the case or how I could debug it would be appreciated.

[R0mai]

vector <int> tmp;
Now tmp's size is 0.
Either you have to push_back() items into it, or resize() it, or construct it with the appropriate constuctor:
vector <int> tmp(initial_size);

[ne555]

You don't have enough memory. Is it necessary the copy to tmp?
You could reserve at the beginning of the function the memory for tmp to avoid reallocation.

Could you post the code of the second problem? (the creation of tmp_partition and the lecture of partition[0][i])

[kempofighter]

That's not true R0mai. He is using the assignment operator which will appropriately resize the tmp. I don't see how reserving the memory will work any better since the assignment operator will determine the size.

The bottom line is that there just isn't enough information to provide a lot of assistance. What is the OS? How much heap is allocated to the program and how much data is in the container?

[R0mai]

@kempofighter: Yes, you're right, I missed that partitions is a vector of vectors, instead of just a vector.

[omr]

I'm coding on ubuntu lucid. Here is the code to fill the partitions:

void restrictedPartitions(vector <vector <int> > &partitions, vector <int> & tmp_partition, int pos, int max_value)
{
    int i = minw // min_value
    bool completed = false;
    while (i <= max_value && !completed)
    {
        tmp_partition.push_back(i);
        sum += i;
        if (sum == NE && pos >= minb) //if sum is reached and we have min num of elements requiered
        {
           completed = true;
           partitions.push_back(tmp_partition);
           tmp_partition.clear();
           sum = 0;
         }
         else //if num of elements still within bounds and we can add the min value
         {
              if (pos < maxb && sum <= NE - minw)
                  restrictedPartitions(partitions, tmp_partition, pos + 1, i);
         }
         i++;
         tmp_partition.pop_back(); //pruning
    }
}

and finally in main I declare:

vector <int> tmp_partition;
vector <vector <int> > partitions;

and call

restrictedPartitions(partitions, tmp_partition, 1, maxw);
print_partitions(partitions);

This is causing a std::bad_alloc. When I try to print the value of partitions[i].size() in gdb i get the MAX_INT value 4294967295. However, when I initialize my vector tmp_partition

vector <int> tmp_partition(MAXE);
tmp_partition.clear() //to remove the zeros? 

it runs smoothly.

[LB]

Try this for your partitions function.

void print_partitions(vector <vector <int> > &partitions)
{
   	for (unsigned int i = 0; i < partitions.size(); i++)
	{
		for(unsigned int l = 0; l < partitions[i].size(); l++)
		{
			//do stuff here with partions[i][l];
		}
	}
}

This way you avoid a temporary vector taking up more memory than needed.

[ne555]

In your recursive function you have

if(condition1)
   tmp.clear(); //tmp.size() == 0
else if([i]condition2])
   recursive_call(); //tmp.size() may be 0
tmp.pop_back();

pop_back() just reduce the size by one. So you're doing 0-1 = 4294967295. Corrupting the vector.
(Actually you're doing it twice but I couldn't find the other one).

You could add a check for the size before the pop_back()

[ne555]

vector <int> tmp_partition(MAXE); //what is MAXE?
tmp_partition.clear();
//it's equivalent to 
vector<int> tmp_partition;
tmp_partition.reserve(MAXE);

That is used to avoid reallocation.
If a vector is at full capacity and you want to push another value, it'll duplicate its capacity (maybe this is system dependent) so you need enough memory to hold three instances of your vector.

[omr]

indeed your suggestion was correct, thanks ne555. I still don't quiet understand why or when we should reserve memory for the vector. I thought one of the advantages of using vectors over arrays was not having to worry about memory allocation.