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:
int types are replaced with a type parameter
T. Test your code on doubles and
strings.
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.
~cs254/bin/TURN_IN.
Before class on Tuesday, December 6, send e-mail
to cs254 containing answers to the following questions:
friend
declaration in class oset::iter and try to recompile.
oset::iter::operator++(int) must return
an iter value rather than a reference.
Hint: think about the desired behavior for prefix and postfix increment.
