difference

[stoneJax]

I am in the process of trying to create a function that can find the difference of two sets. It seems to work on some test runs but not others.

For example:
set1: one, two, three
set2: three, four, five
Their difference will be one, two, which is correct.

However, if I change set1 to:
set1: three, two, three
Nothing will be displayed for their difference, but two should be displayed since that is the only element value from set1 that is not in set2.

 template<class ItemType>
ArraySet<ItemType>&ArraySet<ItemType>::setDifference(const ArraySet<ItemType>& set2)const
{
	int count = 0;
	bool Duplicate = false;
	ArraySet<ItemType>* set1_difference_set2 = new ArraySet<ItemType>;

	for (int i = 0; i < getCurrentSize(); i++)
	{
		count = 0;
		while (count < set2.getCurrentSize()) {

			if (items[i] == set2.items[count])
				Duplicate = true;

			if (items[i] != set2.items[count] && !Duplicate) {

				set1_difference_set2->add(items[i]);
			}
			count++;
		}
	}
	return *set1_difference_set2;
}

[dutch]

Your 'insert' method (or whatever it's called) shouldn't allow duplicates to be inserted in the first place.

[stoneJax]

Hi dutch, yes I did get that taken care of (add() function).

So with the latter example:
set1: three, two, three
set2: three, four, five

After going though add() will display:

set1: The set contains 2 items:
three two

set2: The set contains 3 items:
three four five

The duplicated three is removed from set1. However, two arguments, set1 and set2, are sent in to setDifference(), and with those two sets combined into one there is another duplicate set of three.

Then when I call

set5 = set1.setDifference(set2); 
  displaySet(set5);

the output will be "difference: The set contains 0 items:" but the difference should be two.

I know that set1 - set2 will produce their difference (all elements in set1 that are not in set2), but I do not know how to translate that into code. So, I tried the above approach, but the algorithm is not correct.

[dutch]

Try this:

template<class ItemType>
ArraySet<ItemType>* ArraySet<ItemType>::setDifference(const ArraySet<ItemType>& set2)const
{
	int count = 0;
	bool Duplicate = false;
	ArraySet<ItemType>* set1_difference_set2 = new ArraySet<ItemType>;

	for (int i = 0; i < getCurrentSize(); ++i)
	{
		int j = 0;
		for ( ; j < set2.getCurrentSize(); ++j)
			if (items[i] == set2.items[j])
				break;
		if (j == set2.getCurrentSize())
			set1_difference_set2->add(items[i]);
	}
	return set1_difference_set2;
}

Note that you should probably be returning the pointer itself, not a reference.

[stoneJax]

I tried that and got this error:

Severity Code Description Project File Line Suppression State
Message could be 'ArraySet<std::string> &ArraySet<std::string>::operator =(ArraySet<std::string> &&)'

The only guidelines that I am given are to use & in the header, and * in the return. Here is some of what is said about it:

The problem with returning an object by reference is that you have to make sure that you aren't returning a reference to a local variable that was created on the stack, because, as you know, those local variables will be destroyed when control is returned to the calling function, which will cause the reference to be a reference to deallocated memory. To resolve this, we declare a pointer to the type of the object (ArraySet<ItemType>), and use the "new" operator to allocate memory for the object on the heap (so that it is not destroyed when control is returned to the calling function). Then, at the end of the function, we use the pointer to return the object. For example:

ArraySet<ItemType>* resultPtr = new ArraySet<ItemType>;
.
.

.
.
return *resultPtr;

[dutch]

Then do it the other way.
It just seems strange to me.
You allocated the object with new, so you should delete it at some point.
If you have a reference then you need to delete it like delete &ref;.
At which point you'll have a dangling reference.
That seems weird to me.
But if that's how you were told to do it, then whatever.

[stoneJax]

I found an example of the way you mentioned it in my book. It's all new to me so I am not too familiar with the differences between the two comparisons.

If the object created in this function is required outside the function, the function can return a pointer to it so that the caller can access the object. To implement this option, we would change the function’s return type from void to ToyBox<double>* and return someBoxPtr , which is a pointer to a ToyBox<double> object. The resulting function defi nition is

ToyBox< double>* pluggedLeakyFunction( const  double& someItem) 
{    
    ToyBox< double>* someBoxPtr = new ToyBox<double>();  

   someBoxPtr->setItem(someItem); 

   return someBoxPtr; 
}

[stoneJax]

I got the code to work using & in the header * for the return.

In trying to understand some of the stuff you did, what is the purpose of having the j outside the for loop.

int j = 0;
for ( ; j < set2.getCurrentSize(); ++j)

I am not allowed to use break. Gonna continue to play with the logic.

[keskiverto]

That j is used after, outside the loop.

int j = 0;
for ( ; j < set2.getCurrentSize(); ++j )
{
  // something
}
	
if ( j == set2.getCurrentSize() ) // ... 

The loop searches a value from set.

// myfind returns either index of element, or set2.getCurrentSize()
int j = myfind( set2, items[i] );
if ( j == set2.getCurrentSize() ) // ... 

Put other way:

bool has = does set2 already have value items[i]
if ( not has ) // ... 

I am not allowed to use break.

What other arbitrary limitations do you have?


Look at http://www.cplusplus.com/reference/algorithm/set_difference/
That algorithm operates on sorted ranges. (The std::set is sorted.)

[dutch]

I got the code to work using & in the header * for the return.

Do you delete the dynamically-allocated object at some point or just let it leak? (I suspect you let it leak!)

You can easily avoid the break if you must:

	for (int i = 0; i < getCurrentSize(); ++i)
	{
		int j = 0;
		for ( ; j < set2.getCurrentSize() && items[i] != set2.items[j]; ++j)
			;
		if (j == set2.getCurrentSize())
			set1_difference_set2->add(items[i]);
	}

Or if you want it to look more like beginner code:

	for (int i = 0; i < getCurrentSize(); ++i)
	{
		bool dupFound = false;
		for (int j = 0; j < set2.getCurrentSize() && !dupFound; ++j)
			if (items[i] == set2.items[j])
				dupFound = true;
		if (!dupFound)
			set1_difference_set2->add(items[i]);
	}

[stoneJax]

Thought i would mention he topic of memory leak has come up, and the instructor is going to change some things.

I also learned that I can can use a pre-esiting function contains(). If set1 does not contain an element value from set2, then add value to new array.

I appreciate you guys going over this algorithm and talking about it. It helps to become more familiar with code.

[ne555]

To avoid any problems with memory leak or dangling reference
just don't return a reference, just don't return a pointer,

return an object instead

Set
Set::getDifference(const Set &other) const{
	Set set1_difference_set2; //create an object
	//...
	return set1_difference_set2; //return an object
}

simple, less error-prone, efficient (rvo and move)



> Message could be 'ArraySet<std::string> &ArraySet<std::string>::operator =(ArraySet<std::string> &&)'
quite an awful message, ¿what tool? ¿is there any more text?