Write the implementation of an ADT class ArraySet, given a .h declaration of the class that has already been written.
An ArraySet is an implementation of a set of unique integers (no duplicates) using an unfilled unsorted array as its internal representation.
The set does not have many members, but it is still useful for building a set and testing for membership.
It has the following .h file contents that are already written for you:
// arrayset.h
class ArraySet {
public:
ArraySet(); // construct empty set
void add(int value); // adds value, if not already in set
bool contains(int value) const; // returns true if value is in set
private:
int* _elements; // array of set elements (data begins at index 0)
int _size; // number of elements in set
int _capacity; // length of array
};
Your job is to write the .cpp file contents for the ArraySet implementation.
This means that you must write the complete implementation of the constructor and the two member function bodies.
Initializing the set:
Your set should start out initially empty.
Its internal array should have room for 10 elements.
You must set the initial values of all member variables.
Adding to the set:
Your add member function should add a value to the set, if it is not already found in the set.
The array set is implemented as an unfilled unsorted array, which means that elements are added to the next available slot.
For example, suppose the client adds the three values 22, 11, 22 again (a duplicate), and 33:
// client code that uses the ArraySet
ArraySet set;
set.add(22);
set.add(11);
set.add(22); // duplicate; no effect
set.add(33);
If the internal array is size 10, it would store the following contents (with uninitialized values shown as ..):
index 0 1 2 3 4 5 6 7 8 9
value {22, 11, 33, .., .., .., .., .., .., ..}
For the purposes of this problem we will not worry about resizing.
You should leave your set's internal array at a fixed length of 10.
Once your array runs out of space, you should simply not add any further elements.
Searching the set:
Your contains member function should return true if a given value is present in the set and false if not.
Since the set is unordered, you must perform a linear search over the array to search the entire set to know whether an element is found in the set.
In the example above, the call of set.contains(11) would need to examine 22 and 11 before returning true.
The call of set.contains(44) would need to examine 22, 11, and 33 before returning false.
The search should not ever examine any more of the elements than necessary.
- Your code must work with the existing
ArraySet declarations as shown above.
- You may not declare any additional member variables nor member functions.
- You must demonstrate proper understanding of classes and objects, including showing when to take advantage of behavior from one part of the class in another part of the class.
- You should not create any auxiliary data structures (arrays, vectors, stacks, queues, maps, sets, strings, etc.).
