7 Replies - 505 Views - Last Post: 30 January 2013 - 05:15 PM Rate Topic: -----

#1 totgeburt  Icon User is offline

  • D.I.C Head

Reputation: 57
  • View blog
  • Posts: 227
  • Joined: 03-August 11

heap corruption?

Posted 30 January 2013 - 02:42 AM

First of all, yes, this is a homework assignment. But as you'll see, I've already written the entire thing myself.
My program works how I want it to (excuse the poor coding :P i'm only a first year student) but everytime I end it, i get an error about a heap corruption. It triggers a breakpoint and says something like BLOCK_TYPE_IS_VALID. I've been trying to fix it for like 5 hours and have gotten nowhere. I looked at all my functions and they don't seem to be accessing out of bounds. I'd appreciate it if someone could spot where I'm going wrong and tell me how to fix it :) Here is all my code, nothing excluded.

myArray.h
#ifndef H_myArray
#define H_myArray

#include <iostream>

using namespace std;

class myArray
{
public:
	int& operator[] (int loc);
	const int& operator[] (int loc) const;
	myArray(int size = 20);
	myArray(int start = 0, int end = 20);
	~myArray();
	void showMenu();
	bool isEmpty() const;
	bool isFull() const;
	int getMaxSize() const;
	int getLength() const;
	int getStartLoc() const;
	void print() const;
	void sortAscending();
	void insertAt(const int& item, int position);
	int getChoice() const;
	void initialize();
	void search(const int& item) const;
private:
	int maxSize;
	int length;
	int startLocation;
	int *list;
	int choice;
};

#endif 



the implementation .cpp file for the class myArray
#include "myArray.h"
#include <iostream>
#include <cassert>
#include <string>

using namespace std;

//overload the [] operator to accomodate for start position
int& myArray::operator[] (int loc)
{
	assert(loc >= startLocation && loc < (maxSize + startLocation));
	loc = loc - startLocation;
	return list[loc];
}

//overload [] for constant arrays
const int& myArray::operator[] (int loc) const
{
	assert(loc >= startLocation && loc < (maxSize + startLocation));
	loc = loc - startLocation;
	return list[loc];
}

myArray::myArray(int size)
{
	startLocation = 0;
	maxSize = size;
	length = 0;
	if(maxSize == 0)
		list = NULL;
	else
	{
		list = new int[maxSize];
		initialize();
	}
}

myArray::myArray(int start, int end)
{
	startLocation = start;
	maxSize = (end - startLocation);
	length = 0;
	if(maxSize == 0)
		list = NULL;
	else
	{
		list = new int[maxSize];
		initialize();
	}
}

myArray::~myArray()
{
	delete [] list;
}

//display a menu and return the option selected
void myArray::showMenu()
{
	string input;
	bool valid = false;
	choice = 0;

	cout << "1: Insert an item into the list" << endl;
	cout << "2: Print the contents of the list" << endl;
	cout << "3: Search for an item" << endl;
	cout << "4: Sort the list in ascending order" << endl;
	cout << "5: Exit" << endl;
	cout << endl << ">> ";

	getline(cin, input);

	while(!valid)
	{
		if(input == "1")
		{
			choice = 1;
			valid = true;
		}
		else if(input == "2")
		{
			choice = 2;
			valid = true;
		}
		else if(input == "3")
		{
			choice = 3;
			valid = true;
		}
		else if(input == "4")
		{
			choice = 4;
			valid = true;
		}
		else if(input == "5")
		{
			choice = 5;
			valid = true;
		}
		else
		{
			cout << endl << "Invalid choice, please try again >> ";
			getline(cin, input);
		}
	}
	cout << string(50, '\n'); //clear the screen
}

//return true if the list is empty, false if not
bool myArray::isEmpty() const
{
	return (length == 0);
}

//return true if the list is full, false if not
bool myArray::isFull() const
{
	return (length == maxSize);
}

int myArray::getMaxSize() const
{
	return maxSize;
}

int myArray::getLength() const
{
	return length;
}

int myArray::getStartLoc() const
{
	return startLocation;
}

void myArray::print() const
{
	for(int i = startLocation; i < (maxSize + startLocation); i++)
	{
		cout << list[i] << " ";
	}
	cout << endl;
}

//sort the list in ascending order (lowest to highest) using bubble sort
void myArray::sortAscending()
{
	int temp;
	int iteration;
	int index;
	for(iteration = 1; iteration < maxSize; iteration++)
	{
		for(index = startLocation; index < (maxSize + startLocation) - iteration; index++)
		{
			if(list[index] > list[index + 1])
			{
				temp = list[index];
				list[index] = list[index + 1];
				list[index + 1] = temp;
			}
		}
	}
}

void myArray::insertAt(const int& item, int position)
{
	assert(position >= startLocation && position < (maxSize + startLocation));
	list[position] = item;
	length++;
}

int myArray::getChoice() const
{
	return choice;
}

void myArray::initialize()
{
	for(int i = startLocation; i < (maxSize + startLocation); i++)
		insertAt(0, i);
}

void myArray::search(const int& item) const
{
	bool found = false;
	int index;

	for(int i = startLocation; i < (maxSize + startLocation); i++)
	{
		if(list[i] == item)
		{
			found = true;
			index = i;
		}
	}
	if(found == false)
		cout << item << " was not found" << endl;
	else
		cout << item << " was found in the list " << endl;
}



main
/* Author: hehe
   Date: January 30, 2013
   Course: CS218a
   Assignment: Programming Exercise Week 4
   Purpose: Create and manipulate a dynamic array 
			with a custom starting index
*/
#include <iostream>
#include <string>
#include "myArray.h"

using namespace std;

int main()
{
	string input;
	while(input != "N" && input != "n" && input != "y" && input != "Y")
	{
		cout << "Create a list? [Y/N] >> ";
		getline(cin, input);
	}
	
	if(input != "N" && input != "n")
	{
		int start;
		int end;
		int choice = 0;

		cout << endl;
		cout << "Begin the array index starting at >> ";
		cin >> start;
		cout << "End the array at >> ";
		cin >> end;
		cout << string(50, '\n'); //clear the screen
		cin.ignore();
		//create the object with necessary parameters
		myArray arrayObj(start, end);

		//cycle the menu and options
		while(choice != 5)
		{
			arrayObj.showMenu();
	
			switch(arrayObj.getChoice())
			{
			case 1:
				int item;
				int pos;
				cout << "What number do you want to insert? >> ";
				cin >> item;
				cout << "At which index do you want to insert " << item << "? >> ";
				cin >> pos;
				cout << string(50, '\n');
				arrayObj.insertAt(item, pos);
				cout << item << " was inserted at index " << pos;
				cout << string(3, '\n');
				cin.ignore();
				break;
			case 2:
				cout << "Contents of the list:" << endl;
				arrayObj.print();
				cout << string(3, '\n');
				break;
			case 3:
				int num;
				cout << "Which number do you want to search for? >> ";
				cin >> num;
				cout << string(50, '\n');
				arrayObj.search(num);
				cout << string(3, '\n');
				cin.ignore();
				break;
			case 4:
				arrayObj.sortAscending();
				cout << "List sorted" << endl;
				cout << string(3, '\n');
				break;
			case 5:
				cout << "Have a nice day :)/>" << endl;
				break;
			}//end switch
			choice = arrayObj.getChoice();
		}//end while
	}//end if

	cout << endl;
	system("pause");
	return 0;
}



Is This A Good Question/Topic? 0
  • +

Replies To: heap corruption?

#2 jimblumberg  Icon User is online

  • member icon


Reputation: 4025
  • View blog
  • Posts: 12,421
  • Joined: 25-December 09

Re: heap corruption?

Posted 30 January 2013 - 07:20 AM

Part of your problem is in this function:
void myArray::initialize()
{
	for(int i = startLocation; i < (maxSize + startLocation); i++)

You have initialized your array with a size of maxSize, so if start location is not zero you will try to access your array out of bounds. Arrays in C/C++ start at zero and end at size - 1.

Jim
Was This Post Helpful? 1
  • +
  • -

#3 totgeburt  Icon User is offline

  • D.I.C Head

Reputation: 57
  • View blog
  • Posts: 227
  • Joined: 03-August 11

Re: heap corruption?

Posted 30 January 2013 - 10:36 AM

View Postjimblumberg, on 30 January 2013 - 02:20 PM, said:

Part of your problem is in this function:
void myArray::initialize()
{
	for(int i = startLocation; i < (maxSize + startLocation); i++)

You have initialized your array with a size of maxSize, so if start location is not zero you will try to access your array out of bounds. Arrays in C/C++ start at zero and end at size - 1.

Jim


I tried throwing in some size - 1 in place of what I had and I'm still getting the same error. I have no idea what's going on :(/> I really don't want to start from scratch and dumb it down even more just to get it working, because it's due in about 11 hours.
That narrowed it down though, for sure. I commented out the initialize function and everything seems to be going smoothly.. but now all my values in the array are weird until i put something in them :P

This post has been edited by totgeburt: 30 January 2013 - 10:39 AM

Was This Post Helpful? 0
  • +
  • -

#4 jimblumberg  Icon User is online

  • member icon


Reputation: 4025
  • View blog
  • Posts: 12,421
  • Joined: 25-December 09

Re: heap corruption?

Posted 30 January 2013 - 01:05 PM

You are doing that same thing in several of your functions. You need to insure that you never try to access your array out of bounds. Your array size is maxSize so if startLocation is not zero you will be accessing your array out of bounds. Arrays start at zero, not some random value, they then go to size - 1, not size plus some random value. By random value I mean the value entered by the user.

So actually your problem starts because of this:
		cout << "Begin the array index starting at >> ";
		cin >> start;

Why are you asking the user for the starting index, the starting index should always be zero. Remember arrays start at zero and end at size - 1.

If you "must" have a starting index entered by the user then you must add this starting point to maxSize when you allocate memory to your array. Remember arrays always start at zero and always end at size - 1.

Jim
Was This Post Helpful? 0
  • +
  • -

#5 totgeburt  Icon User is offline

  • D.I.C Head

Reputation: 57
  • View blog
  • Posts: 227
  • Joined: 03-August 11

Re: heap corruption?

Posted 30 January 2013 - 01:25 PM

i should've clarified: the point of this assignment was to allow (or simulate, whatever) an array to begin at whichever index the user chooses, which is why i overloaded the [] operator. i have everything working fine for any positive start, but when it gets to negatives, it always crashes at the end. sorry for not being clear at the start
Was This Post Helpful? 0
  • +
  • -

#6 jimblumberg  Icon User is online

  • member icon


Reputation: 4025
  • View blog
  • Posts: 12,421
  • Joined: 25-December 09

Re: heap corruption?

Posted 30 January 2013 - 01:39 PM

The code you posted will not work for positive start values unless you have made major changes to your code. This is illustrated by the following snippet if startLocation is greater than zero.:
void myArray::print() const
{
	for(int i = startLocation; i < (maxSize + startLocation); i++)
	{
		cout << list[i] << " ";
	}
	cout << endl;
}


You are doing this in several places. You can only access maxSize - 1 array elements, period.

I didn't even try negative values, but since array indexes can never be negative, entering a negative value would probably be a big problem. The above snippet will also fail if startLocation is less than zero.

Jim
Was This Post Helpful? 1
  • +
  • -

#7 totgeburt  Icon User is offline

  • D.I.C Head

Reputation: 57
  • View blog
  • Posts: 227
  • Joined: 03-August 11

Re: heap corruption?

Posted 30 January 2013 - 05:03 PM

thanks Jim, i'm going to take what you said and try to sort it out. i really want to learn assembly now so i understand this better :(
Was This Post Helpful? 0
  • +
  • -

#8 totgeburt  Icon User is offline

  • D.I.C Head

Reputation: 57
  • View blog
  • Posts: 227
  • Joined: 03-August 11

Re: heap corruption?

Posted 30 January 2013 - 05:15 PM

oh. my. god. i got it working :D thanks a ton jim, you saved my life. i guess i just misunderstood how my overloaded [] operator worked. many thanks
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1