Public Group

Bug in Visual C++ 2003?

This topic is 4621 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

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:
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
for(; cur != NULL; cur = cur->next)
{
vEnque(cur->Data);
}
return *this;
}

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

{
delete temp;
}
}

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

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;
else
{
tail->next = tempnode;
tail = tail->next;
}
}

template <class DataType> CGenericQueue<DataType>::CGenericQueue()
{
}
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 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 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 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 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 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 on other sites
Quote:
 Original post by Procyon LotorI 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 on other sites
Oh ok, thanks:)

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

Share on other sites
Quote:
 Original post by Procyon LotorOh 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 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;

1. 1
2. 2
3. 3
Rutin
19
4. 4
5. 5

• 10
• 14
• 30
• 13
• 11
• Forum Statistics

• Total Topics
631782
• Total Posts
3002338
×