Help with dynamic arrays

[nizbit]

I need some dire help. Whenever I execute my program I get this message "./main: free(): invalid next size (fast)". Which leads me to believe something with my dynamic allocation of an array. I've used a debugger and pinpointed the error to the method where I'm trying to increase the size of the array. I've been pouring over the code for hours and cant seem to find whats wrong. I was hoping someone could take a look and tell me whats wrong.

void buildMinHeap(int key) 
{
	
	if (len == 1) //array is already allocated one int
	{
		a[0] = key;
		pos++;
	}
	else
	{
		int len = pos+1; //pos is the length
		ItemType *temp = new ItemType[len+1]; //ItemType is int
		for(int i=0; i<len; i++)
		{
			temp[i] = a[i];
		}
	
		delete[] a;
		a = NULL; 
		len = length(temp);
		temp[len-1] = key;
		cout << len <<endl;
		a = new ItemType[len];
		for(int i=0; i<len-1; i++)
		{
			a[i] = temp[i];
		}
		pos++;
		int first = 0;
		while(first < pos)
		{
		
			heapifyMax(a, 0, first);
			first++;
		}
	}
}

[nizbit]

I've cleaned up my code a bit. It seems to fail when adding the 4th element.

void buildMinHeap(int key) 
{
	cout << "init before:"<< pos <<endl;	
	if (pos == 1)
	{
		a[0] = key;
		cout << "pos=1" << endl;
		pos++;
	}
	else
	{
		//len = pos+1;		
		ItemType *temp = new ItemType[pos];
		for(int i=0; i<pos; i++)
		{
			temp[i] = a[i];
		}
	
		delete[] a;
		a = NULL; 
		temp[pos-1] = key;
		cout << "after insert" << pos <<endl;
		a = new ItemType[pos];
		for(int i=0; i<pos; i++)
		{
			a[i] = temp[i];
			cout << a[i] << endl;
		}
		pos++;
		int first = 0;
		while(first < pos)
		{
		
			heapifyMax(a, 0, first);
			first++;
		}
	}
}

[Lerner]

>>I'm trying to increase the size of the array

I'm confused with all the len, length(), pos stuff.

Basically if array a is too small and you want to enlarge it, then you can copy the contents to a second array, temp, delete a, redeclare a with additional memory than it had and then recopy temp back to a. I can tease most of that sequence out of your code, but I can't keep track of all the sizes and distracting assignments, etc.

int len = pos+1; //pos is the length
ItemType *temp = new ItemType[len+1]; //ItemType is int

temp needs to be at least the same size as a, but why is len first assigned pos + 1 and then the memory requested for temp increased by one again using len +1. If pos is the size of a then why not declare temp with memory equal to pos. Then if you want to increase the size of a by 2 do so here:

a = new ItemType[pos + 2];

Is length() a user defined function? If so, please post it.

[nizbit]

I came to the same realization that I should just us pos as my length. I fixed my code and seems to be working:

void buildMaxHeap(int key)
{
	if (pos == 1)
	{
		a[0] = key;
		pos++;
	}
	else
	{	
		ItemType *temp = new ItemType[pos];
		for(int i=0; i<pos; i++)
		{
			temp[i] = a[i];
		}
	
		delete[] a;
		a = NULL; 
		temp[pos-1] = key;
		a = new ItemType[pos];
		for(int i=0; i<pos; i++)
		{
			a[i] = temp[i];
		}
		pos++;
		int len = pos - 1;
		int first = 0;
		while(first < len)
		{
		
			heapifyMax(a, 0, first);
			first++;
		}
	}
}

Now I have a new problem. When I'm done with the first set of values, I want to clear a to start reading in the new set of values, so I did:

void makeEmpty()
{
	delete [] a;
	a = NULL;
	a = new ItemType[1];
	pos = 1;
}

Which I get another error about a double free. When I looked that up, basically I'm trying to delete something that has already been unallocated.

[WaltP]

Then every time you delete , set a to NULL as you did here. And every time you delete , if a is NULL, don't. There is no a to delete.

[nizbit]

If I understand correctly I changed the doe to:

void makeEmpty()
{
	if(a != NULL)
	{
		delete [] a;
		a = NULL;
	}
	a = new ItemType[1];
	pos = 1;
}

I still get the same error.

[WaltP]

Then that spot wasn't the problem. You might have to resort to the debugger.

[nizbit]

I am currently using DDD. I get that error when I step into makeEmpty().

[nizbit]

Please anyone?

[tetron]

your code appears to moving around a bit and Iwould make sure that everything is as safe as can be

is pos an int?

ItemType *temp = new ItemType[pos];

them new would fail with a -1;
if so safer
to have

if (pos == 1)
	{
		a[0] = key;
		pos++;
	}
	else if(pos > 0)
	{

next where are a[] and pos coming from ?

is ItemType an typedef int as temp is being set to key an int so a warning should be showing or can its constructor throw

pos++;
int len = pos - 1;

little things like this means that you might want to check on paper for on case as
why not simply

int len(pos);
++pos; //what is this doing? it does nothing inside the function

finally does Heapify alter a or first it seems odd that you are going for 0 to first every time

there are many gaps in what you have shown which could cause a problem in your code you could perhaps use a vector and size() but for no rather than the debugger I would recommend placing in as much code safety as possible and if you use cout in between every function then you can find which line is throwing in case you have multiple errors it can be faster than stepping through the debugger each time.

but as you just have one a[] there are any number of places outside of here where it could be being cleared in which case a[0] could even be the culprit.

I came to the same realization that I should just us pos as my length. I fixed my code and seems to be working:

void buildMaxHeap(int key)
{
	if (pos == 1)
	{
		a[0] = key;
		pos++;
	}
	else
	{	
		ItemType *temp = new ItemType[pos];
		for(int i=0; i<pos; i++)
		{
			temp[i] = a[i];
		}
	
		delete[] a;
		a = NULL; 
		temp[pos-1] = key;
		a = new ItemType[pos];
		for(int i=0; i<pos; i++)
		{
			a[i] = temp[i];
		}
		pos++;
		int len = pos - 1;
		int first = 0;
		while(first < len)
		{
		
			heapifyMax(a, 0, first);
			first++;
		}
	}
}

Now I have a new problem. When I'm done with the first set of values, I want to clear a to start reading in the new set of values, so I did:

void makeEmpty()
{
	delete [] a;
	a = NULL;
	a = new ItemType[1];
	pos = 1;
}

Which I get another error about a double free. When I looked that up, basically I'm trying to delete something that has already been unallocated.