Sign in to follow this  
raccoonone

Bug in Visual C++ 2003?

Recommended Posts

I was doing my homework for my data structures class, which involves a priority queue using an array based min heap. I wrote the following code. The problem is that when I use the vSwap(), instead of just writting code to do the swap inside the vReheapify() functions, the pointers in my data get messed up. I'm using the queue in the following manner:
struct PathNode
{
	int iCurVert, iTotalWeight;
	CGenericQueue<int> Path;
};
CHeapPriorityQueue<PathNode> MainQueue;

After calling vSwap, the pointers inside CGenericQueue<int> Path; are pointing to garbage. Is there something wrong with my code, or is this a bug in Visual C++? I showed the code to my teacher, and he thought it must be a bug.
template <class DataType> class Node
{
public:
	int iPriority;
	DataType Data;
	Node *next;
};
template <class DataType> class CGenericQueue
{
protected:
	Node<DataType> *head, *tail;
public:
	CGenericQueue();
	~CGenericQueue();
	void vEnque(const DataType &item);
	int iDeque(DataType &returndata);
	CGenericQueue<DataType> & operator = (const CGenericQueue<DataType> &);
};

template <class DataType> CGenericQueue<DataType> & CGenericQueue<DataType>::operator = (const CGenericQueue<DataType> &From)
{
	//remove everything from the queue
	DataType x;
	while(iDeque(x));
	//enque the new data
	Node<DataType> *cur = From.head;
	for(; cur != NULL; cur = cur->next)
	{
		vEnque(cur->Data);
	}
	return *this;
}

template <class DataType> CGenericQueue<DataType>::~CGenericQueue()
{

	while(head != NULL)
	{
		Node<DataType> *temp = head;
		head = head->next;
		delete temp;
	}
}

template <class DataType> int CGenericQueue<DataType>::iDeque(DataType &returndata)
{
	Node<DataType> *temp;
	//Queue is empty
	if(head == NULL)
		return 0;

	returndata = head->Data;
	temp = head;
	head = head->next;
	delete temp;
	return 1;
}

template <class DataType> void CGenericQueue<DataType>::vEnque(const DataType &item)
{
	Node<DataType> *tempnode = new Node<DataType>;
	tempnode->next = NULL;
	tempnode->Data = item;
	tempnode->iPriority = 0;
	if(head == NULL)
		head = tail = tempnode;
	else
	{
		tail->next = tempnode;
		tail = tail->next;
	}
}

template <class DataType> CGenericQueue<DataType>::CGenericQueue()
{
	head = tail = NULL;
}
template <class Typex> void vSwap(Typex &x, Typex &y)
{
	Typex temp = x;
	x = y;
	y = temp;
}

template <class DataType> class ArrayNode
{
public:
	int iPriority;
	DataType Data;
};

template <class DataType> class CHeapPriorityQueue
{
public:
	void vEnque(const DataType &item, int iPriority);
	int iDeque(DataType &ReturnData);
	CHeapPriorityQueue(int x = 100);
	//~CHeapPriorityQueue();
protected:
	void vReheapifyUp(); //Restores the last item
	void vReheapifyDown(); //Restore the first item
	int iGetParent(int x) {return (x - 1) / 2;}
	int iGetRightChild(int x) {return (x + 1) * 2;}
	int iGetLeftChild(int x) {return ((x + 1) * 2) - 1;}
	ArrayNode<DataType> m_Data[25];
	int m_iLength;
};

template <class DataType> void CHeapPriorityQueue<DataType>::vEnque(const DataType &item, int iPriority)
{
	m_Data[m_iLength].Data = item;
	m_Data[m_iLength].iPriority = iPriority;
	m_iLength++;
	vReheapifyUp();
}

template <class DataType> int CHeapPriorityQueue<DataType>::iDeque(DataType &ReturnData)
{
	if(!m_iLength)
		return 0;
	ReturnData = m_Data[0].Data;
	m_Data[0] = m_Data[m_iLength - 1];
	m_iLength--;
	vReheapifyDown();
	return 1;
}

template <class DataType> void CHeapPriorityQueue<DataType>::vReheapifyDown()
{
	for(int cur = 0; iGetLeftChild(cur) < m_iLength;)
	{
		if(m_Data[iGetLeftChild(cur)].iPriority < m_Data[iGetRightChild(cur)].iPriority)
		{
			//vSwap(m_Data[iGetLeftChild(cur)], m_Data[cur]);
			ArrayNode<DataType> temp;
			temp = m_Data[iGetLeftChild(cur)];
			m_Data[iGetLeftChild(cur)] = m_Data[cur];
			m_Data[cur] = temp;
			cur = iGetLeftChild(cur);
		}
		else
		{
			//vSwap(m_Data[iGetRightChild(cur)], m_Data[cur]);
			ArrayNode<DataType> temp;
			temp = m_Data[iGetRightChild(cur)];
			m_Data[iGetRightChild(cur)] = m_Data[cur];
			m_Data[cur] = temp;
			cur = iGetRightChild(cur);
		}
	}
}

template <class DataType> void CHeapPriorityQueue<DataType>::vReheapifyUp()
{
	for(int cur = m_iLength - 1; cur > 0;)
	{
		if(m_Data[cur].iPriority < m_Data[iGetParent(cur)].iPriority)
		{
			//vSwap(m_Data[iGetParent(cur)], m_Data[cur]);
			ArrayNode<DataType> temp;
			temp = m_Data[iGetParent(cur)];
			m_Data[iGetParent(cur)] = m_Data[cur];
			m_Data[cur] = temp;
			cur = iGetParent(cur);
		}
		else
			return;
	}
}

template <class DataType> CHeapPriorityQueue<DataType>::CHeapPriorityQueue(int x)
{
	//m_Data = new ArrayNode<DataType>[x];
	m_iLength = 0;
}

Share this post


Link to post
Share on other sites
Have you stepped through the code in a debugger and seen exactly when the pointers are getting thrashed? You can stare at code all day without learning nearly as much as actually watching the program run for five minutes.

CM

Share this post


Link to post
Share on other sites
Yes I have. The pointers are fine until the vSwap() function returns. In fact inside the function they're ok, but after it returns they point to garbage.

Share this post


Link to post
Share on other sites
From looking at it, it seems the problem is that you haven't declared a copy constructor for your class. The default copy constructor generated by the compiler just copies the pointers, which means that bad voodoo magic happens when the temporary gets deleted.

And yes, I know it looks like you never use the copy constructor, but the temp declaration in your vSwap() function is actually calling a copy constructor instead of default constructing and then calling assign.

Share this post


Link to post
Share on other sites
I declared a copy constuctor here:

*edit* That is a copy constructor that I declared, right? Sorry, I'm not familiar with all the terms yet.


template <class DataType> CGenericQueue<DataType> & CGenericQueue<DataType>::operator = (const CGenericQueue<DataType> &From)
{
//remove everything from the queue
DataType x;
while(iDeque(x));
//enque the new data
Node<DataType> *cur = From.head;
for(; cur != NULL; cur = cur->next)
{
vEnque(cur->Data);
}
return *this;
}




Do I need one for ArrayNode also? I thought that when the default copy constuctor for ArrayNode was called, it would call the custom copy constructor for CGenericQueue.

Share this post


Link to post
Share on other sites
That's not a copy constructor; that's the assignment operator. A copy constructor is a constructor that takes a (const) reference to the type as a parameter. In this case it'd be CGenericQueue(const CGenericQueue &);

Share this post


Link to post
Share on other sites
Quote:
Original post by Procyon Lotor
I declared a copy constuctor here:

That's not a copy constructor, that's an assignment operator. You want both if you have either. Those, plus a destructor [which you've already got under control].

CM

Share this post


Link to post
Share on other sites
Quote:
Original post by Procyon Lotor
Oh ok, thanks:)

And in the copy constructor I would want to do the same thing I did in the assignment operator, basicly?

Exactly the same, except without cleaning up at the begining and returning *this at the end.

CM

Share this post


Link to post
Share on other sites
Yay! You guys are my heros, that's fixed it:) I was pretty dubious when my teacher said he thought it was a bug in Visual C++, but I wasn't in much of a position to argue, since I had no clue what was wrong.

Just so I understand why this happened. Copy constructors are called when I do something like this?

DataType x = y;

Share this post


Link to post
Share on other sites
Yes.

DataType x = y;
DataType x(y);

Both yeild calls to DataType's copy constructor.

DataType x;
x = y;

This yeild's a call to DataType's default constructor, followed by a call to the assignment operator.

DataType x(y);
x = y;

This does both.

CM

Share this post


Link to post
Share on other sites
This kind of problem is covered by something known as the "Rule of Three": if you have a user defined copy constructor, assignment operator or destructor, then you generally need to define all three. After a while you start associating problems with objects being destroyed with this rule.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this