How to display the difference between two sets?
Feb 10, 2017 at 2:40am UTC
My intent is to display the difference between two sets,using arrays, in two different objects in my bag class. For example, suppose that bag1 and bag2 are bags; bag1 contains the strings a, b, and c; and bag2 contains the strings b, b, d, and e. The expression bag1.difference(bag2); returns a bag containing only the strings a and c. My current code returns 0 0 when it should be returning 2, 5.
1@file SetInterface.h
1 #ifndef SET_INTERFACE_
2 #define SET_INTERFACE_
3
4 #include <vector>
5
6 /** @class SetInterface SetInterface.h "SetInterface.h"
7 *
8 * SetInterface abstract base class template. */
9 template <typename ItemType>
10 class SetInterface {
11 public :
12 /** Virtual destructor. (See C++ Interlude 2.) */
13 virtual ~SetInterface() {}
14
15 /** Gets the current number of entries in this set.
16 *
17 * @return The integer number of entries currently in the set. */
18 virtual int getCurrentSize() const = 0;
19
20 /** Sees whether this set is empty.
21 *
22 * @return True if the set is empty, or false if not. */
23 virtual bool isEmpty() const = 0;
24
25 /** Adds a new entry to this set.
26 *
27 * @post If successful, newEntry is stored in the set and the
28 * count of items in the set has increased by 1.
29 *
30 * @param newEntry The object to be added as a new entry.
31 *
32 * @return True if addition was successful, or false if not. */
33 virtual bool add(const ItemType& newEntry) = 0;
44 virtual bool remove(const ItemType& anEntry) = 0;
49 virtual void clear() = 0;
57 virtual int getFrequencyOf(const ItemType& anEntry) const = 0;
65 virtual bool contains(const ItemType& anEntry) const = 0;
73 #endif
1@file ArraySet.h
19 #ifndef ARRAY_SET_
20 #define ARRAY_SET_
21
22 #include <vector>
23
24 #include "SetInterface.h"
29 template <typename ItemType>
30 class ArraySet : public SetInterface<ItemType> {
31 private :
32 /** Maximum capacity of this bag. */
33 static const int DEFAULT_CAPACITY = 6;
34
35 /** Data storage. */
36 ItemType* items = nullptr ;;
37
38 /** Number of items in this bag. */
39 int itemCount = 0;
40
41 /** Maximum capacity of this bag. */
42 int maxItems = DEFAULT_CAPACITY;
51 int getIndexOf(const ItemType& target) const ;
52
53 public :
54 /** Default constructor. */
55 ArraySet();
56
57 /** Virtual destructor. */
58 virtual ~ArraySet();
59
60 virtual ArraySet<ItemType> difference(const ArraySet<ItemType>&bag);
61
62 virtual void display(const ArraySet<ItemType>&bag1);
63
64 virtual int getCurrentSize() const ;
65
66 virtual bool isEmpty() const ;
67
68 virtual bool add(const ItemType& newEntry);
69
70 virtual bool remove(const ItemType& anEntry);
71
72 virtual void clear();
73
74 virtual int getFrequencyOf(const ItemType& anEntry) const ;
75
76 virtual bool contains(const ItemType& anEntry) const ;
77
78 virtual std::vector<ItemType> toVector() const ;
79 };
80 #include "ArraySet.cpp"
81 #endif
1@file ArraySet.cpp
1 #include <vector>
2 template <typename ItemType>
3 void ArraySet<ItemType>::display(const ArraySet<ItemType>&bag1){
4 for (int i(0);i<itemCount;i++){
5 std::cout << bag1.items[i];
6 }
7 }
8
9 template <typename ItemType>
10 ArraySet<ItemType>::ArraySet()
11 : items(new ItemType[maxItems]) {
12 }
13
14 template <typename ItemType>
15 ArraySet<ItemType>::~ArraySet() {
16
17 delete [] items;
18 }
19
20 template <typename ItemType>
21 int ArraySet<ItemType>::getCurrentSize() const {
22
23 return itemCount;
24 }
25
26 template <typename ItemType>
27 bool ArraySet<ItemType>::isEmpty() const {
28
29 return itemCount == 0;
30 }
31
32
33 template <typename ItemType>
34 ArraySet<ItemType> ArraySet<ItemType>::difference(const ArraySet<ItemType>&bag){
35 ArraySet<ItemType> returnBag;
36 for (int i=0;i<itemCount;i++){
37 for (int j=0;j<bag.getCurrentSize();++j){
38 if (items[i]!=bag.items[j])
39 returnBag.add(items[i]);
40 }
41 return returnBag;
42 }
43 }
44
45 template <typename ItemType>
46 bool ArraySet<ItemType>::add(const ItemType& newEntry) {
47
48 bool hasRoomToAdd(itemCount < maxItems);
49
50 if (!hasRoomToAdd) {
51 ItemType* oldArray(items);
52 items = new ItemType[2 * maxItems];
53 for (int index(0); index < maxItems; ++index) {
54 items[index] = oldArray[index];
55 }
56 delete [] oldArray;
57 maxItems = 2 * maxItems;
58 }
59
60 items[itemCount] = newEntry;
61 ++itemCount;
62
63 return true ;
64 }
65
66 template <typename ItemType>
67 bool ArraySet<ItemType>::remove(const ItemType& anEntry) {
68
69 int locatedIndex(getIndexOf(anEntry) );
70 bool canRemoveItem(!isEmpty() && locatedIndex > -1);
71
72 if (canRemoveItem) {
73 --itemCount;
74 items[locatedIndex] = items[itemCount];
75 }
76
77 return canRemoveItem;
78 }
79
80 template <typename ItemType>
81 void ArraySet<ItemType>::clear() {
82
83 itemCount = 0;
84 }
85
86 template <typename ItemType>
87 bool ArraySet<ItemType>::contains(const ItemType& anEntry) const {
88
89 bool isFound(false );
90 int curIndex(0);
91
92 while (!isFound && curIndex < itemCount) {
93 isFound = anEntry == items[curIndex];
94 ++curIndex;
95 }
96
97 return isFound;
98 }
99
100 template <typename ItemType>
101 int ArraySet<ItemType>::getFrequencyOf(const ItemType& anEntry) const {
102
103 int frequency(0);
104 int curIndex(0);
105
106 while (curIndex < itemCount) {
107 if (items[curIndex] == anEntry) {
108 ++frequency;
109 }
110 ++curIndex;
111 }
112
113 return frequency;
114 }
115
116 template <typename ItemType>
117 std::vector<ItemType> ArraySet<ItemType>::toVector() const {
118
119 std::vector<ItemType> bagContents;
120
121 for (int i(0); i < itemCount; ++i) {
122 bagContents.push_back(items[i]);
123 }
124
125 return bagContents;
126 }
127
128 template <typename ItemType>
129 int ArraySet<ItemType>::getIndexOf(const ItemType& target) const {
130
131 bool isFound(false );
132 int targetIndex(-1);
133 int searchIndex(0);
134
135 while (!isFound && searchIndex < itemCount) {
136 isFound = items[searchIndex] == target;
137
138 if (isFound) {
139 targetIndex = searchIndex;
140 }
141 ++searchIndex;
142 }
143
144 return targetIndex;
145 }
1@file main.cpp
1 #include <iostream>
2 #include <vector>
3 #include "ArraySet.h"
4
5 int main(){
6 ArraySet<int > set1;
7 ArraySet<int > set2;
8 ArraySet<int > result;
9 std::vector<int > resultVector;
10 set1.add(1);
11 set1.add(2);
12 set1.add(3);
13 set2.add(1);
14 set2.add(3);
15 set2.add(5);
16 result = set1.difference(set2);
17 set2.display(set2);
18 }
19
Feb 10, 2017 at 6:52am UTC
In the difference function you have placed the return statement inside the loop.
Feb 10, 2017 at 3:22pm UTC
1for (int i=0;i<itemCount;i++){
for (int j=0;j<bag.getCurrentSize();++j){
if (items[i]!=bag.items[j])
returnBag.add(items[i]);
this code will give inaccurate results, consider:
1*this .items = {a, b, c};
bag.items = {b, b, d, e};
when items[i] == b and items[j] == e, items[i] != items[j] and hence, according to above, items[i] i.e. b would be added to returnBag.items
instead consider using
http://www.cplusplus.com/reference/algorithm/find/ instead
Topic archived. No new replies allowed.
