C++

Forum

 
Need help writing a union function

InfiniteLoop (16)
I've been staring at this code all day and haven't made much progress. I'm supposed to complete the two functions for set_union and intersection, without using the std functions, but with the classes I was given, I'm not even sure where to start. Could someone help me get on the right track?

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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
 
#include <iostream>
#include <list>

using namespace std;

class SetIterator;

class Set
{  
public:
   Set();
   bool is_element(int x);
   void insert(int x);
   void erase(int x);
   void print();
   SetIterator begin();
   SetIterator end();
private:
   list<int> items;
};

class SetIterator
{
public:
   SetIterator();
   SetIterator(list<int>::iterator p);
   void next();
   int get();
   bool equals(SetIterator other);
private:
   list<int>::iterator pos;
};

Set::Set()
{  
}

bool Set::is_element(int x)
{
   list<int>::iterator pos;
   for (pos = items.begin(); pos != items.end(); pos++)
      if (*pos == x) return true;
   return false;
}

void Set::insert(int x)
{
   if (!is_element(x))
      items.push_back(x);
}

void Set::erase(int x)
{
   list<int>::iterator pos;
   for (pos = items.begin(); pos != items.end(); pos++)
      if (*pos == x) 
      {
         items.erase(pos);
         return;
      }
}

void Set::print()
{
   SetIterator pos;
   cout << "{ ";
   for (pos = items.begin(); !pos.equals(items.end()); pos.next())
      cout << pos.get() << " ";
   cout << "}\n";
}

SetIterator Set::begin()
{
   return SetIterator(items.begin());
}

SetIterator Set::end()
{
   return SetIterator(items.end());
}

SetIterator::SetIterator()
{
}

SetIterator::SetIterator(list<int>::iterator p)
{
   pos = p;
}

void SetIterator::next()
{
   pos++;
}

int SetIterator::get()
{
   return *pos;
}

bool SetIterator::equals(SetIterator other)
{
   return pos == other.pos;
}

Set set_union(Set a, Set b)
{
   Set c;
   //Complete code
   return c;
}

Set intersection(Set a, Set b)
{
   Set c;
   //complete code
   return c;
}

int main()
{
   Set s;
   s.insert(3);
   s.insert(4);
   s.insert(5);

   cout << "The first set contains: ";
   s.print();

   Set t;
   t.insert(1);
   t.insert(2);
   t.insert(3);

   cout << "The second set contains: ";
   t.print();

   Set u = set_union(s, t);
   Set v = intersection(s, t);

   cout << "The union of the two sets is: ";
   u.print();

   cout << "The intersection of the two sets is: ";
   v.print();
}
JLBorges (13770)
Intersection:

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
 
std::list<int> intersection( std::list<int> a, std::list<int> b )
{
    std::list<int> result ;

    // sort both lists
    a.sort() ;
    b.sort() ;

    auto iter_a = a.begin() ;
    const auto end_a = a.end() ;
    auto iter_b = b.begin() ;
    const auto end_b = b.end() ;
    
    // start iterating through the two lists in tandem
    while( iter_a != end_a && iter_b != end_b ) // till we reach the end of either list
    {
        if( *iter_a < *iter_b ) ++iter_a ; // element in list a is smaller; move forward to the next element in list a

        else if( *iter_b < *iter_a ) ++iter_b ; // element in list b is smaller; move forward to the next element in list b

        else // the elements are equal
        {
            result.push_back(*iter_a) ; // add the element to the intersection
            ++iter_a ; // and move forward to the next element
            ++iter_b ; // in both lists
        }
    }

    return result ;
}

Now, try implementing set union on your own.
InfiniteLoop (16)
Thanks! But how would that translate into the class I'm using? That's one of the biggest problems I've been having. I have no idea what to use for what purpose.
JLBorges (13770)
1
2
3
4
5
6
7
8
9
10
11
12
13
 
struct set
{
    // ...

    private:
         std::list<int> items ;
         set( std::list<int> lst ) : items(lst) {} // private constructor
         friend set intersection( set a, set b ) ; // friend
};

std::list<int> intersection( std::list<int>, std::list<int> ) ; // the earlier function

set intersection( set a, set b ) { return set( intersection( a.items, b.items ) ) ; }
InfiniteLoop (16)
Well, I think I put all that in correctly. But it's giving me an error:
no match for call to '(Set) (std::list<int>)'


Here's the changes I made, did I do it right, or am I completely off track?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
class Set
{  
public:
   Set();
   bool is_element(int x);
   void insert(int x);
   void erase(int x);
   void print();
   SetIterator begin();
   SetIterator end();
private:
   list<int> items;
   Set(std::list<int> lst) : items(lst) {}
   friend Set intersection(Set a, Set b);
};


1
2
3
4
5
6
7
8
 
list<int> intersection(list<int>, list<int>);
Set intersection(Set a, Set b)
{
   Set c;
   //complete code
   
   return c(intersection(a.items, b.items));
}
JLBorges (13770)
1
2
3
4
5
6
7
8
9
10
 
Set intersection(Set a, Set b)
{
   // Set c;
   //complete code
   
   // return c(intersection(a.items, b.items));

   // return an anonymous object of type Set
   return Set( intersection( a.items, b.items ) ) ;
}


Or:
1
2
3
4
5
 
Set intersection(Set a, Set b)
{
   Set c( intersection( a.items, b.items ) ) ;
   return c ; // named return value
}
InfiniteLoop (16)
Now I've got a linker error:

[Linker Error] undefined reference to `intersection(std::list<int, std::allocator<int> >, std::list<int, std::allocator<int> >)'
JLBorges (13770)
So, provide the implementation of this function:
std::list<int> intersection( std::list<int>, std::list<int> ) ;
InfiniteLoop (16)
Thanks again! But now its spitting out lots of operator errors. Things like this:

 no match for 'operator<' in 'p < a.Set::end()'


I know I'm asking for a lot of help, but this thing and its error messages have me stumped.
JLBorges (13770)
Hard to say what causes that error without seeing the context.
Post your complete code, and a complete listing of the error messages.
InfiniteLoop (16)
Sure thing.

This is the code I put up in my original post with the suggested changes:

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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
 
#include <iostream>
#include <list>

using namespace std;

class SetIterator;

class Set
{  
public:
   Set();
   bool is_element(int x);
   void insert(int x);
   void erase(int x);
   void print();
   SetIterator begin();
   SetIterator end();
private:
   list<int> items;
    Set(std::list<int> lst) : items(lst) {}
   friend Set intersection(Set a, Set b);
};

class SetIterator
{
public:
   SetIterator();
   SetIterator(list<int>::iterator p);
   void next();
   int get();
   bool equals(SetIterator other);
private:
   list<int>::iterator pos;
};

Set::Set()
{  
}

bool Set::is_element(int x)
{
   list<int>::iterator pos;
   for (pos = items.begin(); pos != items.end(); pos++)
      if (*pos == x) return true;
   return false;
}

void Set::insert(int x)
{
   if (!is_element(x))
      items.push_back(x);
}

void Set::erase(int x)
{
   list<int>::iterator pos;
   for (pos = items.begin(); pos != items.end(); pos++)
      if (*pos == x) 
      {
         items.erase(pos);
         return;
      }
}

void Set::print()
{
   SetIterator pos;
   cout << "{ ";
   for (pos = items.begin(); !pos.equals(items.end()); pos.next())
      cout << pos.get() << " ";
   cout << "}\n";
}

SetIterator Set::begin()
{
   return SetIterator(items.begin());
}

SetIterator Set::end()
{
   return SetIterator(items.end());
}

SetIterator::SetIterator()
{
}

SetIterator::SetIterator(list<int>::iterator p)
{
   pos = p;
}

void SetIterator::next()
{
   pos++;
}

int SetIterator::get()
{
   return *pos;
}

bool SetIterator::equals(SetIterator other)
{
   return pos == other.pos;
}

Set set_union(Set a, Set b)
{
   Set c; //result
   //Complete code
   
   return c;
}

list<int> intersection(list<int> a, list<int> b)
{
    std::list<int> result ;

    // sort both lists
    a.sort() ;
    b.sort() ;

    SetIterator iter_a = a.begin() ;
    SetIterator iter_b = b.begin() ;
    
    // start iterating through the two lists in tandem
    while( iter_a != a.end() && iter_b != b.end ) // till we reach the end of either list
    {
        if( *iter_a < *iter_b ) ++iter_a ; // element in list a is smaller; move forward to the next element in list a

        else if( *iter_b < *iter_a ) ++iter_b ; // element in list b is smaller; move forward to the next element in list b

        else // the elements are equal
        {
            result.push_back(*iter_a) ; // add the element to the intersection
            ++iter_a ; // and move forward to the next element
            ++iter_b ; // in both lists
        }
    }

    return result ;
}

Set intersection(Set a, Set b)
{
   Set c(intersection(a.items, b.items));
   //complete code
   return c;
}

int main()
{
   Set s;
   s.insert(3);
   s.insert(4);
   s.insert(5);

   cout << "The first set contains: ";
   s.print();

   Set t;
   t.insert(1);
   t.insert(2);
   t.insert(3);

   cout << "The second set contains: ";
   t.print();

   Set u = set_union(s, t);
   Set v = intersection(s, t);

   cout << "The union of the two sets is: ";
   u.print();

   cout << "The intersection of the two sets is: ";
   v.print();
   int hi;
   cin>>hi;
}


 In function 'std::list<int> intersection(std::list<int>, std::list<int>)'::
no match for 'operator!=' in 'iter_a != a.std::list<_Tp, _Alloc>::end [with _Tp = int, _Alloc = std::allocator<int>, std::list<_Tp, _Alloc>::iterator = std::_List_iterator<int>]()'

no match for 'operator!=' in 'iter_a != a.std::list<_Tp, _Alloc>::end [with _Tp = int, _Alloc = std::allocator<int>, std::list<_Tp, _Alloc>::iterator = std::_List_iterator<int>]()'

no match for 'operator!=' in 'iter_a != a.std::list<_Tp, _Alloc>::end [with _Tp = int, _Alloc = std::allocator<int>, std::list<_Tp, _Alloc>::iterator = std::_List_iterator<int>]()'

no match for 'operator!=' in 'iter_a != a.std::list<_Tp, _Alloc>::end [with _Tp = int, _Alloc = std::allocator<int>, std::list<_Tp, _Alloc>::iterator = std::_List_iterator<int>]()'

no match for 'operator!=' in 'iter_a != a.std::list<_Tp, _Alloc>::end [with _Tp = int, _Alloc = std::allocator<int>, std::list<_Tp, _Alloc>::iterator = std::_List_iterator<int>]()'

no match for 'operator!=' in 'iter_a != a.std::list<_Tp, _Alloc>::end [with _Tp = int, _Alloc = std::allocator<int>, std::list<_Tp, _Alloc>::iterator = std::_List_iterator<int>]()'

no match for 'operator!=' in 'iter_a != a.std::list<_Tp, _Alloc>::end [with _Tp = int, _Alloc = std::allocator<int>, std::list<_Tp, _Alloc>::iterator = std::_List_iterator<int>]()'


Then I tried using just the original code with something similar in the empty functions, but I get these same types of errors.
JLBorges (13770)
Lines 124, 125 and 128
1
2
3
4
5
6
7
8
9
10
 
    // SetIterator iter_a = a.begin() ; // line 124
    // SetIterator iter_b = b.begin() ; // line 125
    std::list<int>::iterator iter_a = a.begin() ;
    std::list<int>::iterator iter_b = b.begin() ;

    // start iterating through the two lists in tandem
    //while( iter_a != a.end() && iter_b != b.end ) // till we reach the end of either list // line 128
    while( iter_a != a.end() && iter_b != b.end() ) // till we reach the end of either list
    {
         // ...

InfiniteLoop (16)
Yes! It works! I figured out the union function, too! Thanks!!
Topic archived. No new replies allowed.