Templates Assignment

For this final, brief assignment, you are to implement a generic ordered set abstraction.  As a starting point, we are providing code for a set of integers (CLICK HERE to download).  The provided code implements the following operations:

    oset();         // default constructor -- empty set
    oset(int);      // constructor for singleton set
    oset(oset&);    // copy constructor

    bool operator[](const int)      // find:    if (S[3]) ...
    oset& operator+=(const int)     // insert:  S += 3
    oset& operator-=(const int)     // remove:  S -= 3

    oset& operator+=(oset&)         // union
    oset& operator-=(oset&)         // set difference
    oset& operator*=(oset&)         // intersection                 

The provided code also provides a simple iterator mechanism (still part of class oset):

    class oset::iter;               // type declaration
    iter begin()                    // returns "pointer" to first element of set
    iter end()                      // returns pointer beyond end of set   

Iterators themselves support the following methods:

    const int& operator*()          // "dereference" the iterator
    iter& operator++()              // prefix ++; point to next element
    iter& operator++(int)           // postfix ++; point to next element
        // NB: the int arg is unused; C++ uses it by convention to tell
        // the difference between prefix and postfix increment
    bool operator==(iter)           // do iterators point
    bool operator!=(iter)           //    at the same element?      
Note that the iter constructor in inaccessible to user code: the only way to get an iterator is by calling begin() or end().  For what it’s worth, oset::iter resembles what the C++ standard template library calls a “forward, constant” iterator: it can be incremented but not decremented, and the “pointed-at” elements are read-only. 

Your assignment is in four parts:

  1. The union, difference, and intersection operations, as written, are O(n2).  Rewrite them to be O(n)
  2. The set code should be generic.  Rewrite it as a template in which the existing int types are replaced with a type parameter T.  Test your code on doubles and strings. 
  3. The private find_prev method, called by operator[](), operator+=(T), and operator-=(T), where T is your element type, implicitly assumes the existence of a >= operator for T.  Rewrite it to make ordering of T explicit by passing a ccomparator function to (each of) the oset constructors.  Test your code on strings with both case-sensitive and case-insensitive lexicographic ordering. 
  4. Note that the linear-time routines you created for union, difference, and intersection won’t work correctly if the two sets have different comparators.  Modify your code to use the linear-time versions ony when the comparators are the same. 

Special Notes

  1. There will be no teams for this assignment; each student should write his or her own code. 
  2. For purposes of this assignment, you are not permitted to use any of the collection classes in the standard template library (STL). 
As usual, please follow all the rules on the Grading page, and use the turn-in script:  ~cs254/bin/TURN_IN

Trivia Assignment

Before class on Tuesday, December 6, send e-mail to cs254 containing answers to the following questions: 

  1. Explain the claim in the 4th part of the assignment above: why won’t linear-time union, difference, and intersection work for sets with the same element type but different comparators? 
  2. Explain what happens if you comment out the friend declaration in class oset::iter and try to recompile. 
  3. Explain why the code for oset::iter::operator++(int) must return an iter value rather than a reference.  Hint: think about the desired behavior for prefix and postfix increment. 

Extra Credit Suggestions

MAIN DUE DATE:

Friday, December 16, at 5:00 pm; no extensions. 
Last Change: 03 December 2011 / Michael Scott's email address