Introduction to Computer Programming: C++

Assignment #4, Generic Set Class


Tuesday, 4th November at noon


This is an assignment where you will gain experience using templates. You'll have to write several functions to implement a Set class. A Set is a collection of elements where no 2 elements are equal. Sets are maintained in sorted order of least to greatest.


Your Set class can internally use any container you want to store elements, such as a vector, but make sure that the set is always sorted. Any kind of element can be added (primitive or object types) as long as it implements the following operators: <, >, and ==. You will define your own Set class in a file called Set.h, with the private member variables that you will need. You will implement the following methods in your Set class (besides other constructors, if you wish, and other necessary or helper methods) where T represents the element type:

  1. Set(); //constructor with no parameters
  2. bool insert(const T &);
  3. bool remove(const T&);
  4. bool find(const T&) const;
  5. void print() const;
  6. int getNumElements() const;
You can use the "In-Place" version of quicksort to make sure the set is always sorted. I recommend that the quicksort method be implemented outside of the Set class, as it could be useful to other code to have a quicksort method that takes a generic vector (or list) and sorts it.

You should write your own testSet.cpp that tests your generic Set classes' methods and verifies their functionality. Make sure you are satisfied that your set does what is expected, and you could give it to a customer (for example) if they needed to use it! I will grade you on how thoroughly it tests your Set methods.

Compile and run your code in Visual Studio. Turn in a folder labeled Set_[yourlastname] containing your files to DropBox in Minerva, including the following files: Set.h and testSet.cpp. Make sure your name is at the top of each file.

Submission Checklist

Extra Credit (+6%)

Answer the following questions in written form in comments after your name at the top of testSet.cpp.