C++

Forum

 
 
I cannot use iterator.

leeli0830 (23)
My code is finding symmetric difference between two sets. I got many errors but two major errors were about using iterator and not using return type. However, my professor gave that I need to use 

1
2
 
template <typename T>
set<T> symDifference(const set<T>& setA, const set<T>& setB)


This format. I'm confused....

Below is the whole file

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
 
#include <iostream>
#include <set>
#include <iterator>

using namespace std;

template <typename T>
set<T> symDifference(const set<T>& setA, const set<T>& setB)
{
	set<T> setSymDifference;

	set<T>::iterator setAiter = setA.begin(), setBiter = setB.begin();

	while(setAiter != setA.end() && setBiter != setB.end())
	{
		if(*setAiter < *setBiter)
		{
			setSymDifference.insert(*setAiter);
			setSymDifference.insert(*setBiter);
			setAiter++;
		}
		else if(*setAiter > *setBiter)
		{
			setSymDifference.insert(*setAiter);
			setSymDifference.insert(*setBiter);
			setBiter++;
		}
		else if(*setAiter == *setBiter)
		{
			setSymDifference.erase(*setAiter);
		}
	}
	return setSymDifference;

}

int main() {

	int arr[] = {1, 2, 4, 6, 7, 9};
	int arrSize = sizeof(arr)/sizeof(int);
	set<int> aset(arr,arr+arrSize);

		int array[] = {2, 3, 4, 5, 6, 10};
	int arraySize = sizeof(array)/sizeof(int);
	set<int> bset(array,array+arrSize);

	set<int> cset::iterator iter = cset.begin();
	cset = symDifference(aset, bset);

	while(iter != cset.end())
	{
		cout << *iter << " ";
	}

	cout << endl << endl;

}
JLBorges (13770)
Brute force:

1
2
3
4
5
6
7
8
9
10
11
12
13
 
#include <set>

template < typename T >
std::set<T> symmetric_difference( const std::set<T>& first, const std::set<T>& second )
{
    if( first.empty() ) return second ;
    else if( second.empty() ) return first ;

    std::set<T> result ;
    for( const T& v : first ) if( second.find(v) == second.end() ) result.insert(v) ;
    for( const T& v : second ) if( first.find(v) == first.end() ) result.insert(v) ;
    return result ;
}

http://coliru.stacked-crooked.com/a/72156997e9983a90

For a faster algorithm, see 'Possible implementation' in: http://en.cppreference.com/w/cpp/algorithm/set_symmetric_difference
leeli0830 (23)
1
2
 
    for( const T& v : first ) if( second.find(v) == second.end() ) result.insert(v) ;
    for( const T& v : second ) if( first.find(v) == first.end() ) result.insert(v) ;


can you explain about those two lines?

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
 
#include <iostream>
#include <set>
#include <iterator>

using namespace std;

template <typename T>
set<T> symDifference(const set<T>& setA, const set<T>& setB)
{
	set<T> result;

	typename set<T>::const_iterator setAiter = setA.begin(), setBiter = setB.begin();

	while(setAiter != setA.end() && setBiter != setB.end())
	{
		if(*setAiter < *setBiter)
		{
			result.insert(*setAiter);
			result.insert(*setBiter);
			setAiter++;
		}
		else if(*setAiter > *setBiter)
		{
			result.insert(*setAiter);
			result.insert(*setBiter);
			setBiter++;
		}
		else if(*setAiter == *setBiter)
		{
			result.erase(*setAiter);
		}
	}
	return result;

}

int main() {

int arr[] = {1, 2, 4, 6, 7, 9};
int arrSize = sizeof(arr)/sizeof(int);
set<int> aset(arr,arr+arrSize);

int array[] = {2, 3, 4, 5, 6, 10};
int arraySize = sizeof(array)/sizeof(int);
set<int> bset(array,array+arrSize);

set<int> cset;
cset = symDifference(aset, bset);
set<int>::iterator iter = cset.begin();

while(iter != cset.end())
{
	cout << *iter << " ";
}
cout << endl << endl;
}


And I put '"typename", so I can get rid of the errors about iterator. However, it takes forever to get the output....
JLBorges (13770)
for( const T& v : first ) // for each item in set 'first'
Range-based loop: http://www.stroustrup.com/C++11FAQ.html#for

second.find(v) // try to find the item v in set 'second'
http://en.cppreference.com/w/cpp/container/set/find

1
2
 
if( second.find(v) == second.end() ) // if the item v is not present in set 'second'
                              result.insert(v) ; // add the item to the result


And like-wise for the other set.
leeli0830 (23)
I'm very appreciate for your help! Can you figure out why my program does not output anything? Is it because too complicated?
dhayden (5798)
leeli0830, look at your program again and compare lines 18-19 with lines 24-25.
JLBorges (13770)
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
 
#include <set>

template < typename T >
std::set<T> symDifference( const std::set<T>& setA, const std::set<T>& setB )
{
    std::set<T> result;

    // typename std::set<T>::const_iterator setAiter = setA.begin(), setBiter = setB.begin();
    // simpler: let the compiler figure out what the type is
    // http://www.stroustrup.com/C++11FAQ.html#auto
    auto setAiter = setA.begin() ;
    auto setBiter = setB.begin();

    while( setAiter != setA.end() )
    {
        if( setBiter == setB.end() ) // reached the end of setB
        {
            result.insert( *setAiter ) ; // insert into result
            ++setAiter ;
        }

        else if( *setAiter < *setBiter )
        {
            result.insert(*setAiter);
            // result.insert(*setBiter);
            setAiter++;
        }

        else if( *setAiter > *setBiter )
        {
            // result.insert(*setAiter);
            result.insert(*setBiter);
            setBiter++;
        }

        else if( *setAiter == *setBiter ) // found in both; skip this item
        {
            ++setAiter ;
            ++setBiter ;
        }
    }

    // once we have reached the end of setA,
    while( setBiter != setB.end() ) // if there are items left over in setB
    {
        result.insert( *setBiter ) ; // insert them into the result
        ++setBiter ;
    }

    return result;
}

http://coliru.stacked-crooked.com/a/51747904a7bdcaa7
leeli0830 (23)
As you did, I corrected my program, but the output is infinite 1. Can you give me advice to improve it? I think the main program is the problem.

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
 
#include <iostream>
#include <set>
#include <iterator>

using namespace std;

template <typename T>
set<T> symDifference(const set<T>& setA, const set<T>& setB)
{
	set<T> result;

	typename set<T>::const_iterator setAiter = setA.begin(), setBiter = setB.begin();

	while(setAiter != setA.end())
	{
		if(setBiter == setB.end())
		{
			result.insert(*setAiter);
			++setAiter;
		}

		else if(*setAiter < *setBiter)
		{
			result.insert(*setAiter);
			++setAiter;
		}
		else if(*setAiter > *setBiter)
		{
			result.insert(*setBiter);
			setBiter++;
		}
		else if(*setAiter == *setBiter)
		{
			++setAiter;
			++setBiter;
		}
	}

	while(setBiter != setB.end())
	{
		result.insert(*setBiter);
		++setBiter;
	}

	return result;
}

int main() {

int arr[] = {1, 2, 4, 6, 7, 9};
int arrSize = sizeof(arr)/sizeof(int);
set<int> aset(arr,arr+arrSize);

int array[] = {2, 3, 4, 5, 6, 10};
int arraySize = sizeof(array)/sizeof(int);
set<int> bset(array,array+arrSize);

for( int v : symDifference(aset,bset)) cout << v << ' '; // I think I need another way to set the range.
cout << endl << endl;
Last edited on
leeli0830 (23)
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
 
#include <iostream>
#include <set>
#include <iterator>

using namespace std;

template <typename T>
set<T> symDifference(const set<T>& setA, const set<T>& setB)
{
	set<T> result;

	typename set<T>::const_iterator setAiter = setA.begin(), setBiter = setB.begin();

	while(setAiter != setA.end())
	{
		if(setBiter == setB.end())
		{
			result.insert(*setAiter);
			++setAiter;
		}

		else if(*setAiter < *setBiter)
		{
			result.insert(*setAiter);
			++setAiter;
		}
		else if(*setAiter > *setBiter)
		{
			result.insert(*setBiter);
			setBiter++;
		}
		else if(*setAiter == *setBiter)
		{
			++setAiter;
			++setBiter;
		}
	}

	while(setBiter != setB.end())
	{
		result.insert(*setBiter);
		++setBiter;
	}

	return result;
}

int main() {

int arr[] = {1, 2, 4, 6, 7, 9};
int arrSize = sizeof(arr)/sizeof(int);
set<int> aset(arr,arr+arrSize);

int array[] = {2, 3, 4, 5, 6, 10};
int arraySize = sizeof(array)/sizeof(int);
set<int> bset(array,array+arrSize);

set<int>cset = symDifference(aset,bset);
for(set<int>::iterator iter = cset.begin(); iter != cset.end(); iter++)
{
	cout << *iter << ' ';
}
cout << endl << endl;


}

I figured out thanks a lot. Have a good night
Last edited on
Topic archived. No new replies allowed.