Question 6 of 9: Object-Oriented Design — A C++ Set Class

Question 6: Object-Oriented Design — A C++ Set Class (20 marks)

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

Given. No numeric data; a design requirement for a templated class supporting empty and pre-populated construction, member addition, deletion and membership test, over any numeric element type.

Find. A Set<T> class, split into Set.h (declaration) and Set.cc (implementation), whose member functions never allow a duplicate element to be stored.

Approach. A class template Set<T> wraps a dynamically resized array holding the current elements and a count of how many are in use. add is the only place duplicates are guarded against — every other operation (delete, membership test) is a plain linear scan over that array. Assumption: mathematical set operations beyond the three named (union, intersection, etc.) are out of scope, since the question lists exactly addition, deletion and membership; elements are compared with ==, which is why the class is restricted to number types (as stated) rather than arbitrary objects.

1. Choose the internal representation. A hash table would give faster membership tests, but the exercise is about supplying what C++ lacks natively with the simplest correct mechanism; a dynamic array demonstrates manual memory management (the actual point of the exercise) without extra machinery. Capacity doubles when full, like a minimal std::vector.
2. Write Set.h. The Big Three (copy constructor, copy assignment, destructor) must be declared because the class owns a raw T*; omitting them lets the compiler-generated shallow copy double-free the same buffer when a Set is copied.

   // Set.h
   #ifndef SET_H
   #define SET_H
   
   template <class T>
   class Set {
   public:
       Set();                                  // empty set
       Set(const T *elems, int n);             // initialized with n elements
       Set(const Set &other);                  // copy constructor
       Set &operator=(const Set &other);       // copy assignment
       ~Set();
   
       void add(const T &value);               // no-op if value already present
       void remove(const T &value);            // no-op if value not present
       bool contains(const T &value) const;
       int  size() const { return count; }
   
   private:
       T   *items;
       int  count;
       int  capacity;
       void grow();                            // doubles capacity
   };
   
   // The definitions live in Set.cc, which ends with explicit instantiations of
   // Set<int>, Set<float> and Set<double> so that this header can be included on
   // its own and Set.cc compiled as an ordinary separate translation unit.
   #endif

3. Write Set.cc. Every mutator funnels through contains, so the "no duplicates" invariant is enforced in exactly one place.

   // Set.cc
   #include "Set.h"
   
   template <class T>
   Set<T>::Set() : items(nullptr), count(0), capacity(0) {}
   
   template <class T>
   Set<T>::Set(const T *elems, int n) : items(nullptr), count(0), capacity(0)
   {
       for (int i = 0; i < n; i++)
           add(elems[i]);                      // add() rejects duplicates in the input too
   }
   
   template <class T>
   Set<T>::Set(const Set &other)
       : items(new T[other.capacity]), count(other.count), capacity(other.capacity)
   {
       for (int i = 0; i < count; i++) items[i] = other.items[i];
   }
   
   template <class T>
   Set<T> &Set<T>::operator=(const Set &other)
   {
       if (this != &other) {
           delete[] items;
           capacity = other.capacity;
           count    = other.count;
           items    = new T[capacity];
           for (int i = 0; i < count; i++) items[i] = other.items[i];
       }
       return *this;
   }
   
   template <class T>
   Set<T>::~Set() { delete[] items; }
   
   template <class T>
   void Set<T>::grow()
   {
       int newCap = (capacity == 0) ? 4 : capacity * 2;
       T *bigger = new T[newCap];
       for (int i = 0; i < count; i++) bigger[i] = items[i];
       delete[] items;
       items = bigger;
       capacity = newCap;
   }
   
   template <class T>
   void Set<T>::add(const T &value)
   {
       if (contains(value)) return;            // the ONE place duplicates are blocked
       if (count == capacity) grow();
       items[count++] = value;
   }
   
   template <class T>
   void Set<T>::remove(const T &value)
   {
       for (int i = 0; i < count; i++) {
           if (items[i] == value) {
               items[i] = items[count - 1];    // swap-with-last: O(1), order not guaranteed
               count--;
               return;
           }
       }
   }
   
   template <class T>
   bool Set<T>::contains(const T &value) const
   {
       for (int i = 0; i < count; i++)
           if (items[i] == value) return true;
       return false;
   }
   
   // Explicit instantiations for the number types this Set is required to
   // support. These are what let Set.cc be compiled separately from Set.h: the
   // compiler emits the member code for these three types here, so a translation
   // unit that only sees Set.h still links. Adding a new element type means
   // adding one more line below.
   template class Set<int>;
   template class Set<float>;
   template class Set<double>;

4. Confirm the contract with example usage.

   Set<int> s;                    // empty set
   s.add(3); s.add(1); s.add(3);  // second add(3) is a no-op: size() stays 2
   s.contains(1);                 // true
   s.remove(1);
   s.contains(1);                 // false
   
   int init[] = {2, 4, 2, 6};
   Set<int> t(init, 4);           // constructs {2, 4, 6}: duplicate 2 collapsed

   $$\boxed{\text{size after } s.add(3);\,s.add(1);\,s.add(3); \;=\; 2}$$