C++

Forum

 
 
Intersection and Difference in a Set.

Happy2bhere (3)
I need someone to explain to me how to implement Intersection and Difference in a Set. I know how to do the Union but I'm stumped on the other two. I also need help finding a certain number in the set (under isThere).
Thank you in advance.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
 
Set Set::Union(const Set &setB) const
{
	Set setNew(items);
	Set tempSet;

	for (int i = 0; i < setB.items.size(); i++)
	{
		if (setNew.IsThere(setB.items[i]) == false)
		{
			tempSet.items.push_back(setB.items[i]);
		}
	}
	setNew.items.insert(setNew.items.end(), tempSet.items.begin(), tempSet.items.end());

	return setNew;
}

Set Set::Intersection(const Set &setB) const
{
	Set setNew;


	return setNew;
}

Set Set::Difference(const Set &setB) const
{
	Set setNew;


	return setNew;
}

bool Set::IsThere(int item) const
{
	bool numFound = false;


	return numFound;
}

Main:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
 
#include <iostream>
#include <string>
#include "Set.h"
#include <vector>

using namespace std;

void ShowDetails(const Set& mySet, string setName);

int main()
{
	vector<int> myVector = { 1, 3, 5, 7, 9 };
	vector<int> myVector2 = { 1, 13, 5 };

	//Create the Sets:
	Set setA(myVector);
	Set setB(myVector2);
	Set setC;

	//Add item(s) to sets:
	setA.Add(77);
	setB.Add(777);
	setC.Add(7777);

	//Display details of the Sets:
	ShowDetails(setA, "setA");
	ShowDetails(setB, "setB");
	ShowDetails(setC, "setC");

	//########## Test the IsThere member function ##########//
	
	cout << "===== Testing IsThere Member Function =====" << endl;
	cout << "5 is in setA: " << setA.IsThere(5) << endl;
	cout << "20 is in setA: " << setA.IsThere(20) << endl;
	cout << "============================================" << endl;
	

	//Create the Sets:
	Set setU_AB;
	Set setU_BA;
	Set setI_AB;
	Set setI_BA;
	Set setD_AB;
	Set setD_BA;

	//Run set operations & display details of the Sets:
	//########## Test the Union member function ##########//
	
	setU_AB = setA.Union(setB);
	setU_BA = setB.Union(setA);
	ShowDetails(setU_AB, "setU_AB (A U B)");
	ShowDetails(setU_BA, "setU_BA (B U A)");
	
	
	//########## Test the Intersection member function ##########//
	
	setI_AB = setA.Intersection(setB);
	setI_BA = setB.Intersection(setA);
	ShowDetails(setI_AB, "setI_AB (A & B)");
	ShowDetails(setI_BA, "setI_BA (B & A)");
	
	
	//########## Test the Difference member function ##########//
	
	setD_AB = setA.Difference(setB);
	setD_BA = setB.Difference(setA);
	ShowDetails(setD_AB, "setD_AB (A - B)");
	ShowDetails(setD_BA, "setD_BA (B - A)");
	

	return 0;
}

void ShowDetails(const Set& mySet, string setName)
{
	cout << "Member(s) in "<< setName <<": "; mySet.Print(); cout << endl;
	cout << "Member count: " << mySet.Count() << endl;
	cout << "============================================" << endl;
}
jonnin (11437)
you need an efficient way to know whether an item is in a set ... like a binary search, or if allowed, make the core of your set class an unordered_map. If you did not, it may be wise to ensure that an item can only be put in the set once.

that said, intersection is
for everything in this set
if it is also in the other set
add to new set

and difference is
for everything in this set
if it is not in the other set
add to new set

so that implies that 'isthere' needs to be written first, but again, if you use the map, its easy. If you do something else, you have to implement some kind of search, preferably the search needs to be very efficient or large sets will bog down into N*N work when doing the intersection/difference routines.
Last edited on
againtry (2313)
@OP You have a lot of problems but these two changes including the one mentioned by @jonnin will get you moving:
Keep it really simple and don't worry about binary searches and maps because you won't need them

1
2
3
4
5
6
7
8
9
10
 
bool IsThere(int item) const
    {
        bool numFound = false;
        for(auto i: items)
        {
            if(i == item)
                numFound = true;
        }
        return numFound;
    }


1
2
3
4
5
6
7
8
9
10
 
void ShowDetails(const Set& mySet, string setName)
{
    cout << "Member(s) in "<< setName << ": ";
    for(auto i: mySet.items)
        cout << i << ' ';
    cout << '\n';
    
    cout << "Member count: " << mySet.items.size() << endl;
    cout << "============================================" << endl;
}
againtry (2313)
Check it out thoroughly but here are union and intersection, you can do difference:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
 
Set Union(const Set &setB) const
    {
        Set new_set;
        new_set.items = setB.items;
        
        int element;
        for (int i = 0; i < this->items.size(); i++)
        {
            element = this->items[i];
            if (new_set.IsThere(element) == false)
            {
                new_set.items.push_back(element);
            }
        }
        return new_set;
    }
    
    Set Intersection(const Set &setB) const
    {
        Set new_set;
        
        int element;
        for (int i = 0; i < this->items.size(); i++)
        {
            element = this->items[i];
            if (setB.IsThere(element) == true)
            {
                new_set.items.push_back(element);
            }
        }
        return new_set;
    }
againtry (2313)
Member(s) in setA: 1 3 5 7 9 
Member count: 5
============================================
Member(s) in setB: 1 13 5 
Member count: 3
============================================
Member(s) in setC: 
Member count: 0
============================================
===== Testing IsThere Member Function =====
5 is in setA: 1
20 is in setA: 0
============================================
Member(s) in setU_AB (A U B): 1 13 5 3 7 9 
Member count: 6
============================================
Member(s) in setU_BA (B U A): 1 3 5 7 9 13 
Member count: 6
============================================
Member(s) in setI_AB (A intersection B): 1 5 
Member count: 2
============================================
Member(s) in setI_BA (B intersection A): 1 5 
Member count: 2
============================================
Member(s) in setD_AB (A - B): 3 7 9 
Member count: 3
============================================
Member(s) in setD_BA (B - A): 13 
Member count: 1
============================================
Program ended with exit code: 0


Oops wrong <>tag now fixed. BTW I commented out .Add hence strange result
Last edited on
Happy2bhere (3)
Thank you all so much for your help.
Topic archived. No new replies allowed.