Problems with dynamic memory

[Duki]

Hey everyone,

I'm trying to work with Sets. I have a function Union that takes a class type Set as it's parameter. The function returns the union of class A and B.

Here is my code:

Set Set::Union(Set setB)
{
	Set result (maxItems);
	for (int i = 0 ; i < maxItems ; i++)
		result.items[i] = (items[i] || setB.items[i]) ;

	return result ;
}
************************
//copy c-tor if you need it
Set::Set(const Set & sB)		// copy c-tor
{
	maxItems = sB.maxItems;
	items = new bool[maxItems];
	for ( int k = 0; k < maxItems; ++k )
		items[k] = sB.items[k];
}

Example Use: Set testClass = classA.Union(classB) ;

I'm getting run-time errors, and I'm fairly positive it has something to do with the use of dynamic memory in this function. I need to return the address of the new class result. Thanks for any help. If you need more of my code, just let me know.

[Agni]

If you are passing the address of result then it's definitely a problem because you have not allocated 'result' on the heap. It's a local variable in the function Union and it disappears when we exit the function, if you try to access that address you can get run-time errors.

[MrSpigot]

If you are passing the address of result then it's definitely a problem because you have not allocated 'result' on the heap. It's a local variable in the function Union and it disappears when we exit the function, if you try to access that address you can get run-time errors.

The address of result is not being returned, so that is not an issue. However, in Union(), if setB has less items than the first set then the for loop will be trying to access invalid memory because setB.items will not exist when i >= setB.maxItems.
Some smarter logic is required to handle this case.

It would also be interesting to see your Set assignment operator (I hope you have one) to check that you are copying the dynamic memory correctly in the return from Union.

[Agni]

My bad, i didn't see the function signature properly, you're returning by value so the copy ctor will get called.

However, in Union(), if setB has less items than the first set then the for loop will be trying to access invalid memory because setB.items will not exist when i >= setB.maxItems.

that doesn't seem to be so because

maxItems = sB.maxItems;

and hence the loop will never go out of bounds for sB.items.
can you post the entire code if it's not too big, or alteast a compilable portion of it.

[MrSpigot]

that doesn't seem to be so because
maxItems = sB.maxItems;
and hence the loop will never go out of bounds for sB.items.

The for loop in the copy ctor is ok, it is the for loop in Union() which is vulnerable if setB.maxItems < maxItems.

[Duki]

It seems the problem might be something different, for now anyways. I ran the debugger and found that the program was crashing before it ever got to the Union() function.

If you look at my driver file (bottom), I've made comments where the program crashes.

Here is my full code:

//map.h
#pragma once
#include <iostream> 
#include <cctype> 
using namespace std;

typedef char ItemType;
const char SPACE = ' ';

int map(char ch);			// prototype

void printItem(int k);		// prototype

// map.cpp
#include "map.h" 

int map(char ch)  
{   
    if ( islower(ch) )
	 return int(ch - 'a') + 25;
    else if ( isupper(ch) )
	   return int(ch - 'A');
    else
    {  cout << "\n !! illegal input for map() !!\n";
	 return -99;  } // endif
} // end map()

void printItem(int k)
{   
    cout << SPACE;			// space
    if ( k >= 25 )
    {	k += 72;			// lowercase
	cout << char(k); }
    else
    {	k += 65;			// uppercase
	cout << char(k); }
    return;
} // end printItem()


//set.h
#include "map.h"
// Specification for SetType using explicit representation.
// File map.h must include a definition of ItemType and a function 
//  named "map" that maps an item of ItemType into an index between 
//  0 and max - 1 if the parameterized constructor is used and
//  between 0 and 399 if the default constructor is used.
class Set
{
public:
  Set();		// Default constructor: Array size is 400.
  Set(int max);	// Paramaterized constructor
  //~Set();		// Destructor
  Set(const Set & anotherSet); // Copy constructor

  void MakeEmpty();
  void Store(ItemType item);
  void Delete(ItemType item);
  bool IsEmpty();
  bool IsFull();
  int CardinalityIs();
  Set Union(Set setB);
  Set Intersection(Set setB);
  Set Difference(Set setB);
  void Print();
private:
  int maxItems;
  bool *items;
};


// set.cpp - Set implementation file

#include "set.h"

Set::Set() : maxItems(100)	  // default c-tor - array size is 100
{
	items = new bool[maxItems];
	for ( int k = 0; k < maxItems; ++k )
		items[k] = false;
}

Set::Set(int max) : maxItems(max)	   // parameterized c-tor
{
	items = new bool[maxItems];
	for ( int k = 0; k < maxItems; ++k )
		items[k] = false;
}

Set::Set(const Set & sB)		// copy c-tor
{
	maxItems = sB.maxItems;
	items = new bool[maxItems];
	for ( int k = 0; k < maxItems; ++k )
		items[k] = sB.items[k];
}

void Set::Store(ItemType itm)
{
   items[map(itm)] = true;
} // end Store()

void Set::Delete(ItemType itm)
{
   items[map(itm)] = false;
} // end Delete()

void Set::MakeEmpty()
{
	for (int i = 0 ; i < maxItems ; i++)
		items[i] = false ;
} // end MakeEmpty()

void Set::Print()
{
	for (int i = 0 ; i < maxItems ; i++)
			cout << items[i] << endl ;
} // end Print()

int Set::CardinalityIs()
{
	int card = 0 ;
	for (int i = 0 ; i < maxItems ; i++)
		if (items[i])
			card++ ;

	return card ;
} // end CardinalityIs()

bool Set::IsEmpty()
{
	return (CardinalityIs() == 0) ;
} // end IsEmpty()

bool Set::IsFull()
{
	return (CardinalityIs() == maxItems) ;
} // end IsFull()

Set Set::Union(Set setB)
{
	cout << "TEST" << endl ;
	Set result(maxItems) ;
	cout << "test1" << endl ;
	for (int i = 0 ; i < maxItems ; i++)
		result.items[i] = (items[i] || setB.items[i]) ;

	cout << "test" << endl ;
	return result ;
}


//example driver
#include "map.h"
#include "set.h"

int main()
{
	Set combo ;
	Set test(10) ;
	test.Store('A') ;
	test.Store('B') ;
	test.Store('Z') ;
	test.Store('D') ;
	test.Store('E') ;
	test.Store('G') ;
	test.Store('J') ;

	test.Store('A') ;
	test.Store('B') ;

	test.Print() ;
	cout << "Cardinality of Test:  " << test.CardinalityIs() << endl ;

	Set other(10) ;
	other.Store('A') ;
	other.Store('Z') ;
	other.Store('W') ;
	other.Store('N') ;
	other.Store('I') ;

	other.Print() ;  //works to here
	Set t ;  //crashes here
	cout << "-- Program End --" << endl ;

	return 0 ;
}

[Duki]

I found my problem. My map() function assumes a letter is being given, and maps it to an array[0-51]. When initializing my objects to have less than that, my dynamic memory was getting buggered when I would try to map anything above index 9.

Thanks for the help!