C++

Forum

 
Set.cpp file implementation

closed account (o1q592yv)
Hi everyone! Currently working on an assignment for data structures. Specifically, the assignment is to create a static implementation of a set. Add the efficiency of each function to the documentation in the header file. Use test_set.cpp as your test program. (header and test file were given to us)

header 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
 
#ifndef _SET_H
#define _SET_H

#include <cstdlib>
#include <iostream>

class set
{
public:
  typedef int value_type;
  typedef std::size_t size_type;
  static const size_type CAPACITY = 30;

  set();
// postcondition: empty set has been created
  
  void insert (const value_type& entry);
  // precondition: if entry is not in the set, set is not full
  // postcondition: entry is in the set

  void remove (const value_type& entry);
// postcondition: entry is not in the set

  size_type size() const;
// postcondition: number of elements in the set has been returned

  bool contains (const value_type& entry) const;
// postcondition: whether entry is in the set has been returned

  friend set set_union (const set& s1, const set& s2);
  //postcondition: union of s1 & s2 has been returned

  friend set set_intersection (const set& s1, const set& s2);
  // postcondition: intersection of s1 & s2 has been returned

  friend set set_difference (const set& s1, const set& s2);
// postcondition: difference of s1 - s2 has been returned

  friend bool is_subset (const set& s1, const set& s2);
// postcondition: returned whether s1 is a subset of s2

  friend bool operator == (const set& s1, const set& s2);
  // postcondition: returned whether s1 & s2 are equal

  friend std::ostream& operator << (std::ostream& output, const set& s);
// postcondition: s has been displayed on output

private:
  size_type find (const value_type& entry) const;
  // returned location of entry in the set if entry is in the set - used otherwise
  value_type data[CAPACITY];
  size_type used;
};


#endif


test_set.cpp:
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 "set.h"
#include <cassert>
#include <iostream>

int main ()
{
  set s;
  assert (!s.contains (7));
  s.insert (7);
  assert (s.contains (7));
  s.remove (7);
  assert (!s.contains (7));
  
  set s1;
  s1.insert (4);
  s1.insert (5);
  s1.insert (-24);
  s1.insert (89);
  s1.insert (34);
  s1.insert (11);
  s1.insert (0);
  s1.insert (3);
  s1.insert (14);
  s1.insert (28);
  std::cout << s1 << std::endl;

  set s2;
  s2.insert (6);
  s2.insert (-5);
  s2.insert (-24);
  s2.insert (-89);
  s2.insert (34);
  s2.insert (-11);
  s2.insert (0);
  s2.insert (3);
  std::cout << s2 << std::endl;

  set s3 = set_union (s1, s2);
  assert (s3.contains (4));
  assert (s3.contains (0));
  assert (s3.contains (-5));
  std::cout << s3 << std::endl;

  set s4 = set_intersection (s1, s2);
  assert (s4.contains (34));
  assert (!s4.contains (4));
  assert (!s4.contains (-5));
  std::cout << s4 << std::endl;

  set s5 = set_difference (s1, s2);
  assert (s5.contains (4));
  assert (!s5.contains (0));
  assert (!s5.contains (-5));
  std::cout << s5 << std::endl;

  assert (is_subset (s5, s1));
  std::cout << "all tests passed" << std::endl;
  return 0;
}


this is my set.cpp file so far: I have most of the functions set up, but I am having trouble on how to approach the other functions, specifically:

1
2
3
4
5
 
friend set set_intersection (const set& s1, const set& s2);
friend set set_difference (const set& s1, const set& s2);
friend bool is_subset (const set& s1, const set& s2);
friend bool operator == (const set& s1, const set& s2);
friend std::ostream& operator << (std::ostream& output, const set& s);

I would appreciate some guidance on how to approach these! :) 
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
 
#include "set.h" //includes header file
#include <cstdlib>
#include <iostream>
#include <cassert> //lets us use assertions in C++

//implementation file
using namespace std;

set::set()
{
  used = 0;
}
//postcondition: empty set has been created

//precondition: if entry is not in the set, the set is not full
void set::insert(const value_type& entry)
{
  if(contains(entry) == true)
  {
      return;
  }
  data[used] = entry;
  used ++; 
}
//postcondition: entry is in the set

void set::remove(const value_type& entry)
{
  for(int i = 0; i < used; i++)
  {
    if(data[i] == entry)
    {
      data [i]  = data [used - 1];
      used --;
      return;
    }
  }
}
//post condition: entry is not in the set

set::size_type size() const
{
  return used;
}
//post condition: number of elements in the set has been returned

set::bool contains(const value_type& entry) const
{
  for(int i = 0; i < used; i++)
  {
    if(data[i] == entry)
    {
	return true;
    }
  }
  return false;
}
//post condition: whether entry is in the set that has been returned

set::friend set set_union(const set& s1, const set& s2)
{
  assert (CAPACITY >= s1.size + s2.size);
  set uniset;//creates a set variable named uniset
  for(int i = 0; i <= s1.used; i++)
  {
    uniset.insert(s1.data[i]);
  }
    
}
//post condition: union of s1 and s2 has been returned

set::friend set set_intersection(const set& s1, const set& s2)
{
  assert (CAPACITY >= s1.size + s2.size);
  set interset;//creates a variable named interset
  for(int i = 0; i<= s1.used; i++)
  {
    for(int j = 0; j<= s2.used; j++)
    {
      if(s1.size == s2.size)
      {
	  return true;
      }
    }
  }
}
//post condition: intersection of s1 and s2 has been returned

set::friend set set_difference(const set& s1, const set& s2)
{
    assert (CAPACITY >= s1.size - s2.size);
    set s3 = s1 - s2;
    return s3;
}
//post condition: difference of s1 and s2 has been returned

set::friend bool is_subset(const set& s1, const set& s2)
{
}
//post condition: returned whether s1 is a subset of s2

set::friend bool operator == (const set& s1, const set& s2)
{
   assert( s1 == s2);
   if(s1.size == s2.size)
      return true;

   else
     return false;
}

//post condition: returned whether s1 and s2 are equal

set::friend std::ostream& operator << (std::ostream& output, const set& s)
{

}
//post condition: s has been displayed on output


Last edited on
gunnerfunner (2127)
value_type data[CAPACITY]

The set ctor declares set objects with an array of int's size 30 (== CAPACITY) but upon initialization this array is just filled with garbage values, so it would be useful for the set class to have another variable:
size_type elements
that would go ++elements upon each insert() and --elements upon each remove(), subject to upper(CAPACITY) and lower(0) boundaries, to keep track of how many actual elements are there in each set.

Then for set_intersection() start with (a) the set that has the fewer elements and (b) a declared set object setIntersect.
For each element in the set that has fewer elements check if this elements exists in the other set. If yes, insert this element into setInsersect ... return setIntersect

set_difference(): to get A - B you'd check each element of A to see if it was present in B, if not then that element is a candidate for A - B, so insert this element into another locally declared set setDifference ... return setDifference

is_subset() - you should be able to have a go at this one if you can make set_intersection() work
1
2
3
4
5
6
7
8
 
std::ostream& operator << (std::ostream& output, const set& s)
{
	for (size_type t = 0; t < elements; ++t)
	output << (s.getdata())[t] << " ";
        //where getdata() is the getter for private member data of const set object s
	//again print only upto elements, not CAPACITY
	return output;
}

Last edited on
closed account (o1q592yv)
So in my set.h file I would need to declare a variable called size_type elements, which would go: elements ++. Then I would need to call the size_type elements variable for both my insert and remove functions?
gunnerfunner (2127)
Yes, I'd suggest declaring elements with a default value of 0 in set.h and then the insert method could look like:
1
2
 
data[elements] = entry; 
++elements;


Also set.h already has size_type size() const; which could be defined as return elements;, thus linking elements to its getter
closed account (o1q592yv)
Thank you very much for your help! I managed to get my cpp file working on CLion, and I am currently trying to compile it on emacs, which uses a g++ compiler. I keep getting these errors: I am unsure what its trying to tell me with " comparison between signed and unsigned integer expressions.... CLion doesn't seem to have a problem with it because it runs perfect there... but my professor requires all of us to use the g++ compiler, so how does one go about fixing these types of errors??

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
set.cpp: In member function âvoid set::remove(const set::value_type&)â:
set.cpp:30: warning: comparison between signed and unsigned integer expressions
set.cpp: In member function âbool set::contains(const set::value_type&) constâ:
set.cpp:50: warning: comparison between signed and unsigned integer expressions
set.cpp: In function âset set_union(const set&, const set&)â:
set.cpp:65: warning: comparison between signed and unsigned integer expressions
set.cpp: In function âset set_intersection(const set&, const set&)â:
set.cpp:76: warning: comparison between signed and unsigned integer expressions
set.cpp: In function âset set_difference(const set&, const set&)â:
set.cpp:90: warning: comparison between signed and unsigned integer expressions
set.cpp: In function âbool is_subset(const set&, const set&)â:
set.cpp:104: warning: comparison between signed and unsigned integer expressions
set.cpp: In function âbool operator==(const set&, const set&)â:
set.cpp:118: warning: comparison between signed and unsigned integer expressions
set.cpp: In function âstd::ostream& operator<<(std::ostream&, const set&)â:
set.cpp:131: warning: comparison between signed and unsigned integer expressions


my updated set.cpp file is as follows:
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
 
#include "set.h" //includes header file
#include <cstdlib>
#include <iostream>
#include <cassert> //lets us use assertions in C++

//implementation file
using namespace std;

//default constructor
set::set()
{
    used = 0;
}
//postcondition: empty set has been created

//precondition: if entry is not in the set, the set is not full
void set::insert(const value_type& entry)
{
    if(contains(entry) == true)
    {
        return;
    }
    data[used] = entry;
    used ++;
}
//postcondition: entry is in the set

void set::remove(const value_type& entry)
{
    for(int i = 0; i < used; i++)
    {
        if(data[i] == entry)
        {
            data [i]  = data [used - 1];
            used --;
            return;
        }
    }
}
//post condition: entry is not in the set

set::size_type set::size()const
{
    return used;
}
//post condition: number of elements in the set has been returned

bool set::contains(const value_type& entry) const
{
    for(int i = 0; i < used; i++)
    {
        if(data[i] == entry)
        {
            return true;
        }
    }
    return false;
}
//post condition: whether entry is in the set that has been returned

set set_union(const set& s1, const set& s2)
{
    //assert (CAPACITY >= s1.size + s2.size);
    set uniset;//creates a set variable named uniset
    for(int i = 0; i <= s1.used; i++)
    {
        uniset.insert(s1.data[i]);
    }
    return uniset;
}
//post condition: union of s1 and s2 has been returned

set set_intersection(const set& s1, const set& s2)
{
    set intersect;//creates a variable named intersect
    for(int i = 0; i < s1.used; i++)
    {
        if(s2.contains(s1.data[i]))
        {
            intersect.insert(s1.data[i]);
        }
    }
    return intersect;
}
//post condition: intersection of s1 and s2 has been returned

set set_difference(const set& s1, const set& s2)
{
    set setDiff;
    for(int i = 0; i <s1.used; i++)
    {
        if(!s2.contains(s1.data[i]))
        {
            setDiff.remove(s1.data[i]);
        }
    }
    return setDiff;
}
//post condition: difference of s1 and s2 has been returned

bool is_subset(const set& s1, const set& s2)
{
    set sub;//creates a variable named sub
    for(int i = 0; i < s1.used; i++)
    {
        if(s2.contains(s1.data[i]))
        {
            sub.insert(s1.data[i]);
        }
        return true;
    }
    return false;
}
//post condition: returned whether s1 is a subset of s2

bool operator == (const set& s1, const set& s2)
{
    for(int i =0; i < s1.used; i++)
    {
        if(!s2.contains(s1.data[i]))
        {
            return false;
        }
    }
    return true;
}
//post condition: returned whether s1 and s2 are equal

ostream& operator << (std::ostream& output, const set& s)
{
    for (int i = 0; i < s.used; ++i)
    {
        output << (s.data[i]) << " ";
    }
    return output;
}
Last edited on
gunnerfunner (2127)
Topic archived. No new replies allowed.