Skip to main content
GameDev.net gamedev.net
🔒 Locked

Implementing a queue data structure -- hea corruption [SOLVED]

Started by v0dKA Apr 22, 2009 at 10:22 PM 1 replies 1.3k views
Original Post
v0dKA
v0dKA
Hi, I'm trying to implement a queue class in C++ for my data structures course. The program seems to run fine, but on exit, Visual C++ tells me: Windows has triggered a breakpoint in exp.exe. This may be due to a corruption of the heap, which indicates a bug in exp.exe or any of the DLLs it has loaded. I can't figure out why this is happening. My guess would be that there's a problem with the part of the code that reallocates more memory for the data structure when the user adds more elements than the queue could originally hold (this is in the push function below). Here's my class: Queue.h

#pragma once

#include <stdexcept>
#include <iostream>

template<class T>
class Queue
{
	public:

		Queue(void);
		~Queue(void);

		/**
		 * IsEmpty - Returns true if the queue has no elements.
		 */
		bool IsEmpty() const; 
		
		/**
		 * size - Returns the number of elements in the queue.
		 */
		int size() const; 
		
		/**
		 * front - Returns the oldest element in the queue, without
		 * removing the element from the queue.
		 */
		T& front() const; 
		
		/**
		 * back - Returns the most recently added element in the queue,
		 * without removing it from the queue.
		 */
		T& back() const; 
		
		/**
		 * pop - Dequeues the oldest element in the queue.
		 */
		void pop(); 
	
		/**
		 * push - Adds a new element to the back of the queue.
		 * @theElement: the element to be added.
		 */
		void push(const T& theElement);



		// TEMPORARILY PUBLIC, FOR DEBUGGING
		/**
		 * capacity - The number of elements the queue can currently
		 * hold based on the amount of memory allocated to it.
		 * Distinct from the number of elements actually in
		 * the queue.
		 */
		unsigned int capacity;




	private:

		/**
		 * The number of elements actually in the queue (as opposed
		 * to capacity).
		 */
		unsigned int q_size;

		/**
		 * The elements of the queue itself.
		 */
		T *theQueue;

		/*
		 * Points to the current start and end of the queue.
		 */
		T *q_front, *q_rear;
};


template<class T>
Queue<T>::Queue(void)
{
	capacity = 10;
	theQueue = new T[capacity];
	q_size = 0;
	q_front = theQueue;
	q_rear = theQueue + (capacity-1);
}

template<class T>
Queue<T>::~Queue(void)
{
	delete [] theQueue;
}

template<class T>
bool Queue<T>::IsEmpty() const
{
	return (q_size == 0);
}

template<class T>
int Queue<T>::size() const
{
	return q_size;
}

template<class T>
T& Queue<T>::front() const
{
	if (q_size <= 0)
		throw std::out_of_range("Attempted to retrieve front item of an empty queue.");

	return *q_front;
}

template<class T>
T& Queue<T>::back() const
{
	if (q_size <= 0)
		throw std::out_of_range("Attempted to retrieve rear item of an empty queue.");

	return *q_rear;
}

template<class T>
void Queue<T>::pop()
{
	if (q_size <= 0)
	{
		std::cout << "Warning: pop() called on empty queue.  Ignoring request." << std::endl;
		return;
	}

	T *t_front = theQueue + q_front;
	delete t_front;

	--q_size;
	++q_front;
	if (q_front - theQueue >= (int)capacity)
		q_front = theQueue;
}

template<class T>
void Queue<T>::push(const T& theElement)
{
	if (q_size == capacity)
	{
		// Allocate more capacity.
		capacity *= 2;
		T *newQueue = new T[capacity];
		memcpy(newQueue, theQueue, q_size*sizeof(T));
		unsigned int frontOffset = q_front - theQueue;
		delete [] theQueue;
		theQueue = newQueue;
		q_front = theQueue + frontOffset;
	}

	++q_size;
	++q_rear;
	if (q_rear - theQueue >= (int)capacity)
		q_rear = theQueue;

	*q_rear = theElement;
}




And here's a little test program, which works as expected (though it doesn't test all functionality of the class): main.cpp

#include <iostream>
#include "Queue.h"

using namespace std;

void printinfo(Queue<int>& q)
{
	cout << "Front=" << q.front() 
		<< ", Back=" << q.back() 
		<< ", Size=" << q.size() 
		<< ", Capacity=" << q.capacity 
		<< endl;
}

int main()
{
	Queue<int> queue;
	
	queue.push(1);
	printinfo(queue);

	queue.push(2);
	printinfo(queue);

	queue.push(3);
	printinfo(queue);

	queue.push(4);
	printinfo(queue);

	queue.push(5);
	printinfo(queue);

	queue.push(6);
	printinfo(queue);

	queue.push(7);
	printinfo(queue);

	queue.push(8);
	printinfo(queue);

	queue.push(9);
	printinfo(queue);

	queue.push(10);
	printinfo(queue);

	queue.push(11);
	printinfo(queue);

	queue.push(12);
	printinfo(queue);

	cin.get();
	return 0;
}




Thank you, I would really appreciate your help! [Edited by - v0dKA on April 23, 2009 1:11:26 AM]
.:-v0d[KA]-:. <<>>
Zahlman
Zahlman
0) You should put some comment at the top to explain that you intend to use the allocated space in a "circular" manner :) Also, explain that q_rear points to the last element when there are elements, but to one "before" q_front when the queue is empty.

1) q_size should never be allowed to be negative, so checking for it being negative is useless.

2) As a stylistic point, it makes sense to reuse IsEmpty for checking for an empty queue in other member functions.

3) In fact, there is no reason to store q_size, since you can calculate it from the distance between front and rear pointers. Well, almost: you can't tell a full buffer from an empty one that way. You could solve that problem by using a separate flag, or by letting the allocation be a NULL pointer for empty queues (thus you would have to deallocate the buffer and null out the pointer whenever the queue is emptied), or by allocating space for one extra element (so that the buffer is never full and you know you have an empty buffer if it "looks full").

4) You are trying in pop() to call 'delete' on individual elements of an array that was allocated with 'new[]'. This is undefined behaviour and not a logical thing to do, anyway: elements aren't constructed when they're push()ed (they're instead assigned), so they shouldn't be destructed when they're pop()ped. To "clear" that memory, you could assign a default-constructed T to that location.

Or you could base your queue on a dynamic array of T* (instead of a dynamic array of T). Or you could base your queue on a linked list of T. Either of those approaches would let you sanely construct elements (copy-construct, to be specific) when you push() them and destruct them to pop() them.

By the way, std::vector does some very tricky C++-specific stuff to make this work with destructors and copy constructors getting called. Google "placement new" to learn more.

5) pop() also adds 'theQueue + q_front', which are both pointers. That would trigger a compiler error, except that your test program doesn't actually instantiate the pop() function.

6) In C++, don't use memcpy() to copy ranges; use std::copy(). This function will work on non-POD data and properly call constructors. The call would look something like std::copy(theQueue, theQueue + q_size, newQueue);.

7) Think carefully about where each element from the old allocation goes in the new allocation when you copy it. You should consider "un-wrapping" the queue whenever you resize it (by making two copies) so that q_front is always at the beginning of a new allocation.

8) Your test program could be written with a loop :)

9) Don't rely on #pragma once ; it's compiler specific. It doesn't hurt to leave it in, but you should *also* put proper include guards.

10) You shouldn't print messages within the class implementation. You could have pop() return bool, and return false if the queue was empty. The standard library queue leaves the behaviour undefined in this case, BTW, AFAIK.
v0dKA
v0dKA
Zahlman,

Thank you very, very much! That was very helpful.
.:-v0d[KA]-:. <<>>

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.