Set ADT question

[mrkhtn]

I have an assignment to complete by Friday...and for the love of god I'm trying, I've created what resembles a SET but I need to create a Insert function and i'm unsure of how to check for duplicates...with the STL it would be so much easier! my question is how would i check for duplicates? and if you wish you could also explain how i would create set union and intersection...not much to ask i know !

thanks in advance

[JRevor]

Well well.. i hope this helps. It's not code, but if you're smart enough you'll be able to catch up the idea.


INSERT => If the element is not repeated, then "really" insert it. To check if the element is repeated, you have to compare your candidate-to-be-inserted with every other element already inserted. If the element is repeated, the insertion is discarded. You can use a while loop for that.

UNION => For example,

set<whatever> Union (set<whatever> A, set <whatever>B)
   set<whatever> result; //its created empty
   for every a in A
       result.Insert(a)
   for every b in B
       result.Insert(b)
   //I can do this because the insertion checks for repeated elements
   return result;

INTERSECTION =>A crappy way to do it, is doing A union B, and removing the elements that are not in A and in B. Of course there are more efficient ways of doing this.

set<whatever> Intersection (set<whatever> A, set <whatever>B){
   set<whatever> result = A Union B;
   for every c in result
       if not((c is in A) && (c is in B))
          result.discard(c); // c is removed from the set "result"
   return result;
}

Hope that helped

EDIT: Be careful in the union pseudocode: we're checking all the elements in "result" while we modify "result". An option to avoid this problem could be to use an auxiliary set. Other option is marking the elements as "to be deleted" in the first run, and then deleting them in a second run.

[mrkhtn]

Thanks for the reply, great diagrams....I'm confused by the every a in A part though, can you explain more? or provide an example?

thanks

[Zhuge]

Use a for loop to iterate through the entire set.

[mrkhtn]

I understand that a loop is required, but how would I setup the loop? For every a in A? How do you apply that to a loop?

like below?

for(int a=0; a == A;a++){
}

[mrkhtn]

Where am i going wrong?

Set<int> Union (Set<int> A, Set <int> B)
{
   Set<int> result; //its created empty

for(Set<int> a= 0;a == A;a++)
       result.Insert(a);

for(Set<int> b= 0;b == B;b++)
       result.Insert(b);
	
   
   return result;
}

Error	4	error C2784: 'bool std::operator ==(const std::reverse_iterator<_RanIt> &,const std::reverse_iterator<_RanIt2> &)' : could not deduce template argument for 'const std::reverse_iterator<_RanIt> &' from 'Set<DT>'
Error	13	error C2784: 'bool std::operator ==(const std::reverse_iterator<_RanIt> &,const std::reverse_iterator<_RanIt2> &)' : could not deduce template argument for 'const std::reverse_iterator<_RanIt> &' from 'Set<DT>'
Error	6	error C2784: 'bool std::operator ==(const std::pair<_Ty1,_Ty2> &,const std::pair<_Ty1,_Ty2> &)' : could not deduce template argument for 'const std::pair<_Ty1,_Ty2> &' from 'Set<DT>'11
Error	15	error C2784: 'bool std::operator ==(const std::pair<_Ty1,_Ty2> &,const std::pair<_Ty1,_Ty2> &)' : could not deduce template argument for 'const std::pair<_Ty1,_Ty2> &' from 'Set<DT>'
Error	2	error C2784: 'bool std::operator ==(const std::istreambuf_iterator<_Elem,_Traits> &,const std::istreambuf_iterator<_Elem,_Traits> &)' : could not deduce template argument for 'const std::istreambuf_iterator<_Elem,_Traits> &' from 'Set<DT>'
Error	11	error C2784: 'bool std::operator ==(const std::istreambuf_iterator<_Elem,_Traits> &,const std::istreambuf_iterator<_Elem,_Traits> &)' : could not deduce template argument for 'const std::istreambuf_iterator<_Elem,_Traits> &' from 'Set<DT>'	
Error	3	error C2784: 'bool std::operator ==(const std::allocator<_Ty> &,const std::allocator<_Other> &) throw()' : could not deduce template argument for 'const std::allocator<_Ty> &' from 'Set<DT>'
Error	12	error C2784: 'bool std::operator ==(const std::allocator<_Ty> &,const std::allocator<_Other> &) throw()' : could not deduce template argument for 'const std::allocator<_Ty> &' from 'Set<DT>'
Error	5	error C2784: 'bool std::operator ==(const std::_Revranit<_RanIt,_Base> &,const std::_Revranit<_RanIt2,_Base2> &)' : could not deduce template argument for 'const std::_Revranit<_RanIt,_Base> &' from 'Set<DT>'
Error	14	error C2784: 'bool std::operator ==(const std::_Revranit<_RanIt,_Base> &,const std::_Revranit<_RanIt2,_Base2> &)' : could not deduce template argument for 'const std::_Revranit<_RanIt,_Base> &' from 'Set<DT>'
Error	7	error C2676: binary '==' : 'Set<DT>' does not define this operator or a conversion to a type acceptable to the predefined operator	
Error	16	error C2676: binary '==' : 'Set<DT>' does not define this operator or a conversion to a type acceptable to the predefined operator	
Error	8	error C2676: binary '++' : 'Set<DT>' does not define this operator or a conversion to a type acceptable to the predefined operator
Error	17	error C2676: binary '++' : 'Set<DT>' does not define this operator or a conversion to a type acceptable to the predefined operator	
Error	9	error C2664: 'Set<DT>::Insert' : cannot convert parameter 1 from 'Set<DT>' to 'const int &'
Error	18	error C2664: 'Set<DT>::Insert' : cannot convert parameter 1 from 'Set<DT>' to 'const int &'
Error	1	error C2440: 'initializing' : cannot convert from 'int' to 'Set<DT>'	
Error	10	error C2440: 'initializing' : cannot convert from 'int' to 'Set<DT>'	

[JRevor]

for(Set<int> a= 0;a == A;a++)
       result.Insert(a);

a is a Set<int>. You're asigning a set<int> to an int. That makes no sense at all.
It should be something like

for(Set<int>::iterator a= A.begin();a == A.end();a++)
       result.Insert(a);

Where iterator is a friend class. Another way of doing it is

for(int i = 0;a < A.size(); i++)
       result.Insert( A.element(i));

Where A.element(i) returns the i-th element of the set.

[JRevor]

Did this help you?

[mrkhtn]

Yeh it helped the only problem I had was I had no iterator class in my declaration...I had to hand the assignment in with no intersection or union. Thanks for the help though