Objective

C++ unordered_set overview

The C++ Standard Library contains an unordered_set class that implements a dynamic set. unordered_set supports range-based for loops to iterate through the set's items. Additional functionality is described in online documentation.

Step 1: Inspect StaticSet.h

Inspect the StaticSet template class declaration in the StaticSet.h file. Access StaticSet.h by clicking on the orange arrow next to main.cpp at the top of the coding window. StaticSet uses an unordered_set to implement a static set. The unordered_set's contents are assigned at construction time and must not change after.

Constructors and some additional member functions are already implemented:

Contains(const T& item) uses the unordered_set's count() function to determine if the set contains the item. If count() returns 1, the item is in the set and Contains() returns true. Otherwise the item is not in the set and Contains() returns false.
GetSize() uses the unordered_set's size() function to determine the number of elements in the set. GetSize() returns the set's size as an integer.

Step 2: Implement StaticSet's Union(), Intersection(), Difference(), Filter(), and Map() member functions

Implement the StaticSet class's Union(), Intersection(), Difference(), Filter(), and Map() member functions. Each must not change the StaticSet itself, but rather build and return a new StaticSet.

Step 3: Test in develop mode, then submit

File main.cpp contains test cases for each of the five operations. Running code in develop mode displays the test results, with 3 points possible for the Union(), Intersection(), and Difference() operations, and 2 points for the Filter() and Map() operations. After each member function is implemented and all tests pass in develop mode, submit the code. The unit tests run on submitted code are similar, but use different sets and template types.

Code Starter

StaticSet.h

#ifndef STATICSET_H
#define STATICSET_H

#include <functional>
#include <iostream>
#include <unordered_set>
#include <vector>

template <typename T>
class StaticSet {
private:
   std::unordered_set<T> set;

public:
   // Constructs an empty StaticSet
   StaticSet() {
   }

   // Constructs the StaticSet by adding all vector items
   StaticSet(const std::vector<T>& items) {
      for (const T& item : items) {
         set.insert(item);
      }
   }
   
   // Constructs the StaticSet by copying itemsToCopy's items
   StaticSet(const std::unordered_set<T>& itemsToCopy) : set(itemsToCopy) {
   }
   
   virtual ~StaticSet() {
   }
   
   bool Contains(const T& item) const {
      return 1 == set.count(item);
   }
   
   int GetSize() const {
      return (int) set.size();
   }
   
   void Print(std::ostream& output, std::string separator,
      std::string prefix="", std::string suffix="") const {
      output << prefix;
      bool firstItem = true;
      for (const T& item : set) {
         if (firstItem) {
            output << item;
            firstItem = false;
         }
         else {
            output << separator << item;
         }
      }
      output << suffix;
   }
   
   // Returns a StaticSet<T> containing each element from this set that is not
   // in otherSet.
   StaticSet<T> Difference(const StaticSet& otherSet) const {
      // Your code here (remove placeholder line below)
      return StaticSet<T>();
   }
   
   // Returns a StaticSet<T> containing each element from this set that
   // satisfies the predicate.
   // - If predicate(item) returns true, item satisfies the predicate.
   // - If predicate(item) returns false, item does not satisfy the predicate.
   StaticSet<T> Filter(std::function<bool(const T&)> predicate) const {
      // Your code here (remove placeholder line below)
      return StaticSet<T>();
   }
   
   // Returns a StaticSet<T> containing each element from this set that is also
   // in otherSet.
   StaticSet<T> Intersection(const StaticSet& otherSet) const {
      // Your code here (remove placeholder line below)
      return StaticSet<T>();
   }
   
   // Calls mapFunction(item) for each item in this set and adds the returned
   // item to a StaticSet<U>. After mapFunction has been called for each item
   // in this set, the StaticSet<U> object is returned.
   template <typename U>
   StaticSet<U> Map(std::function<U(const T&)> mapFunction) const {
      // Your code here (remove placeholder line below)
      return StaticSet<U>();
   }
   
   // Returns a StaticSet<T> containing every element from this set and every
   // element from otherSet.
   StaticSet<T> Union(const StaticSet& otherSet) const {
      // Your code here (remove placeholder line below)
      return StaticSet<T>();
   }
};

#endif

StaticSetTestCases.h

#ifndef STATICSETTESTCASES_H
#define STATICSETTESTCASES_H

#include <iostream>
#include <string>
#include <tuple>
#include <unordered_set>
#include <vector>
#include "StaticSet.h"

class StaticSetTestCase {
public:
   template <typename T>
   static double CompareSets(std::ostream& testFeedback,
      StaticSet<T>& actual, std::unordered_set<T>& expected,
      std::string title, double points) {
      using namespace std;
      bool pass = true;
      
      // Compare actual vs. expected sets
      if (actual.GetSize() != (int)expected.size()) {
         pass = false;
      }
      else {
         // Expected and actual have equal sizes, so compare contents
         for (const T& item : expected) {
            if (!actual.Contains(item)) {
               pass = false;
            }
         }
      }
      
      // Print the pass or fail message with expected and actual sets
      testFeedback << (pass ? "PASS: " : "FAIL: ");
      testFeedback << title << endl;
      StaticSetTestCase::Print<unordered_set<T>, T>(testFeedback, expected,
         ", ", "  Expected: {", "}\n");
      actual.Print(testFeedback, ", ", "  Actual:   {", "}\n");
      
      return pass ? points : 0.0;
   }
   
   template <typename ContainerType, typename ItemType>
   static void Print(std::ostream& output, const ContainerType& iterable,
      std::string separator = ", ", std::string prefix = "",
      std::string suffix = "") {
      // Print the prefix first
      output << prefix;
      
      bool firstItem = true;
      for (const ItemType& item : iterable) {
         if (firstItem) {
            // Print first item without separator
            output << item;
            firstItem = false;
         }
         else {
            // Print item preceeded by separator
            output << separator << item;
         }
      }
      
      // Print the suffix last
      output << suffix;
   }
   
   virtual int Execute(std::ostream& testFeedback) = 0;
};


// BinaryOpsTestCase represents an executable test case for the StaticSet's
// Union(), Intersection(), and Difference() member functions
template <typename T>
class BinaryOpsTestCase : public StaticSetTestCase {
private:
   std::unordered_set<T> setA;
   std::unordered_set<T> setB;
   std::unordered_set<T> expectedUnion;
   std::unordered_set<T> expectedIntersection;
   std::unordered_set<T> expectedAMinusB;
   std::unordered_set<T> expectedBMinusA;
   
public:
   BinaryOpsTestCase(const std::unordered_set<T>& setA,
      const std::unordered_set<T>& setB,
      const std::unordered_set<T>& expectedUnion,
      const std::unordered_set<T>& expectedIntersection,
      const std::unordered_set<T>& expectedAMinusB,
      const std::unordered_set<T>& expectedBMinusA) {
      this->setA = setA;
      this->setB = setB;
      this->expectedUnion = expectedUnion;
      this->expectedIntersection = expectedIntersection;
      this->expectedAMinusB = expectedAMinusB;
      this->expectedBMinusA = expectedBMinusA;
   }
   
   virtual int Execute(std::ostream& testFeedback) override {
      using namespace std;
      
      // Print sets A and B first
      Print<unordered_set<T>, T>(testFeedback, setA, ", ", "A = {", "}\n");
      Print<unordered_set<T>, T>(testFeedback, setB, ", ", "B = {", "}\n");

      // Create the two StaticSet objects from the unordered_set objects
      StaticSet<T> staticSetA(setA);
      StaticSet<T> staticSetB(setB);
      
      // Create the union, intersection, and differences
      StaticSet<T> actualUnion = staticSetA.Union(staticSetB);
      StaticSet<T> actualIntersection = staticSetA.Intersection(staticSetB);
      StaticSet<T> actualAMinusB = staticSetA.Difference(staticSetB);
      StaticSet<T> actualBMinusA = staticSetB.Difference(staticSetA);
      
      // Verify that performing operations didn't change either StaticSet's size
      vector<tuple<StaticSet<T>*,unordered_set<T>*,string>> sizeChecks = {
         make_tuple(&staticSetA, &setA, "A"),
         make_tuple(&staticSetB, &setB, "B")
      };
      for (auto& sizeCheckTuple : sizeChecks) {
         StaticSet<T>* staticSet = std::get<0>(sizeCheckTuple);
         unordered_set<T>* unorderedSet = std::get<1>(sizeCheckTuple);
         string staticSetName = std::get<2>(sizeCheckTuple);
         if (staticSet->GetSize() != (int)unorderedSet->size()) {
            testFeedback << "FAIL: Creating the union/intersection/difference ";
            testFeedback << " of StaticSets A and B changed set ";
            testFeedback << staticSetName << "'s size from ";
            testFeedback << unorderedSet->size();
            testFeedback << " to " << staticSetA.GetSize() << std::endl;
            return 0.0;
         }
      }
      
      // Compare actual vs. expected sets
      double totalPoints = 0.0;
      totalPoints += StaticSetTestCase::CompareSets<T>(testFeedback,
         actualUnion, expectedUnion, "Union operation", 1.0);
      totalPoints += StaticSetTestCase::CompareSets<T>(testFeedback,
         actualIntersection, expectedIntersection, "Intersection operation",
         1.0);
      totalPoints += StaticSetTestCase::CompareSets<T>(testFeedback,
         actualAMinusB, expectedAMinusB, "A \\ B operation", 0.5);
      totalPoints += StaticSetTestCase::CompareSets<T>(testFeedback,
         actualBMinusA, expectedBMinusA, "B \\ A operation", 0.5);
      
      return (int) totalPoints;
   }
};

// UnaryOpsTestCase represents an executable test case for the StaticSet's
// Filter() and Map() member functions
template <typename T, typename MappedItemType>
class UnaryOpsTestCase : public StaticSetTestCase {
private:
   std::unordered_set<T> sourceSet;
   std::function<bool(const T&)> filterPredicate;
   std::function<MappedItemType(const T&)> mapFunction;
   std::unordered_set<T> expectedFiltered;
   std::unordered_set<MappedItemType> expectedMapped;
   
public:
   UnaryOpsTestCase(const std::unordered_set<T>& sourceSet,
      std::function<bool(const T&)> filterPredicate,
      std::function<MappedItemType(const T&)> mapFunction,
      const std::unordered_set<T>& expectedFiltered,
      const std::unordered_set<MappedItemType>& expectedMapped) {
      this->sourceSet = sourceSet;
      this->filterPredicate = filterPredicate;
      this->mapFunction = mapFunction;
      this->expectedFiltered = expectedFiltered;
      this->expectedMapped = expectedMapped;
   }
   
   virtual int Execute(std::ostream& testFeedback) override {
      using namespace std;
      
      // Print the source set first
      Print<unordered_set<T>, T>(
         testFeedback, sourceSet, ", ", "Set = {", "}\n");

      // Create the StaticSet object from the unordered_set source
      StaticSet<T> staticSet(sourceSet);
      
      // Create the filtered and mapped sets
      StaticSet<T> actualFiltered = staticSet.Filter(filterPredicate);
      StaticSet<MappedItemType> actualMapped = staticSet.Map(mapFunction);
      
      // Verify that performing operations didn't staticSetA's size
      if (staticSet.GetSize() != (int)sourceSet.size()) {
         testFeedback << "FAIL: Filtering and/or mapping StaticSet S changed ";
         testFeedback << "S's size from " << sourceSet.size();
         testFeedback << " to " << staticSet.GetSize() << std::endl;
         return 0.0;
      }
      
      // Compare actual vs. expected sets
      double totalPoints = 0.0;
      totalPoints += StaticSetTestCase::CompareSets<T>(testFeedback,
         actualFiltered, expectedFiltered, "Filter operation", 1.0);
      totalPoints += StaticSetTestCase::CompareSets<MappedItemType>(
         testFeedback, actualMapped, expectedMapped, "Map operation", 1.0);

      return (int) totalPoints;
   }
};

#endif

main.cpp

#include <iostream>
#include <string>
#include "StaticSetTestCases.h"
using namespace std;

int main(int argc, char *argv[]) {
   // First test case tests binary operations: union, intersection, and
   // difference
   BinaryOpsTestCase<int> binaryOpsTestCase(
      { 42, 63, 99, 32, 18, 77, 64, 50, 12 },
      { 64, 16, 32, 8, 4, 1, 2 },
      { 1, 2, 4, 8, 12, 16, 18, 32, 42, 50, 63, 64, 77, 99 }, // expected union
      { 32, 64 }, // expected intersection
      { 42, 63, 99, 18, 77, 50, 12 }, // expected A minus B
      { 1, 2, 4, 8, 16 } // expected B minus A
   );
   int binaryTestCasePoints = binaryOpsTestCase.Execute(cout);
   cout << endl;
   
   // Next test case tests unary operations: filter and map
   UnaryOpsTestCase<string, int> unaryOpsTestCase(
      { "zero", "one", "two", "three", "four", "five", "six", "seven", "eight",
        "nine", "ten" },
      [&](const string& str) {
         // Keep each string with a length <= 4
         return (str.length() <= 4);
      },
      [&](const string& str) {
         // Map from the string to the string's length
         return (int)str.length();
      },
      { "zero", "one", "two", "four", "five", "six", "nine", "ten" }, // expected filtered
      { 3, 4, 5 } // expected mapped
   );
   int unaryTestCasePoints = unaryOpsTestCase.Execute(cout);
   
   cout << endl;
   cout << "Binary operations score: " << binaryTestCasePoints << " out of 3";
   cout << endl;
   cout << "Unary operations score: " << unaryTestCasePoints << " out of 2";
   cout << endl;
   
   return 0;
}

Deliverable

Upload the following:

Full source code (.cpp files or .txt files)
Screenshot of the Console with the code executing

Programming 3 - Data Structures

Challange Lab- Sets