Spring 2005 Final Exam, open book, open notes.  Name ______________________

1. A SafeVector<T> is like a vector<T> except that it has an additional
member type SafeIterator, which is like iterator except that it throws
an exception of type out_of_range if it is dereferenced by the *, ->,
or [] operators while it is not pointing to a valid element.  SafeVector
also has members safeBegin() and safeEnd() that work like begin() and end()
except that they return SafeIterator instead of iterator.  A partial
implementation is shown.  Add the 5 typedefs to SafeIterator needed to work
with the standard library (10 pts).  Add operators [], -, ==, and -> to
SafeIterator (10 pts each).  List (but don't write) the remaining operators
(10 pts).  Add a constructor to SafeVector taking an int, which defaults
to 0, which specifies the number of elements, and does not allow implicit
conversion from int (10 pts).  (Use back of page if you need more space).

  template <class T> class SafeVector: public vector<T> {
  public:
    SafeIterator safeBegin() {return SafeIterator(begin(), end(), begin());}
    SafeIterator safeEnd()   {return SafeIterator(begin(), end(), end());}
    class SafeIterator {
      friend class vector<T>;  // for safeBegin(), safeEnd()
      iterator b, e, p;  // points to *p such that b <= p < e
      SafeIterator(iterator b_, iterator e_, iterator p_): b(b_), e(e_), p(p_) {}
    public:
      SafeIterator(): b(0), e(0), p(0) {}
      reference operator*() const {
        if (p<b || p>=e)
          throw out_of_range();
        return *p;
      }
  
      // ANSWER
      typedef random_access_iterator_tag iterator_category;
      typedef T value_type;
      typedef T* pointer;
      typedef T& reference;
      typedef ptrdiff_t difference_type;  // or int

      reference operator[](int i) {
        if (p+i < b || p+i >= e)
          throw out_of_range();
        return p[i];  // or return *(p+i);
      }

      difference_type operator-(SafeIterator q) const {
        return q.p - p;
      }
      // or (both are needed, but I only asked you to write one)
      SafeIterator operator-(int i) const {
        return SafeIterator(b, e, p-i);
      }

      bool operator==(SafeIterator q) const {
        return p == q.p;
      }

      pointer operator->() const {
        if (p < b || p >= e)
          throw out_of_range();
        return p;
      }

      // Also ++ (pre and post), -- (pre and post), !=, <, <=, >, >=, +, +=, -=
    };

    explicit SafeVector(int i=0): vector<T>(i) {}  // Constructor
  };


2. Circle true or false.  Statements are executed in sequence (3 pts each).

ANSWERS
  F  vector<T> is an abstract base class of SafeVector<T>
  F  This throws an exception: SafeVector<int>::SafeIterator i, j=i;
T    This throws an exception: SafeVector<int> sv; cout << *sv.begin();
  F  This throws an exception: sv[-2] = 100;
  F  If vector has no virtual members, then this leaks memory:
       vector<int> *pv = new SafeVector<int>(10); delete pv;
  F  SafeVector needs a destructor, copy constructor and assignment operator.
  F  This is legal: i = &sv;
T    This is legal and throws an exception: *i = *i;
T    This is legal: const int *pci = &sv[5];
  F  This is legal: int *pi = pci;

Notes to answers:

  sv[-2] does not throw an exception because sv is a SafeVector, not
  a SafeIterator.  sv.begin()[-2] would throw an exception.

  *sv.begin() throws because sv is empty.

  There is no memory leak even though the wrong destructor is called,
  because the derived destructor is the default and doesn't do anything extra.

  No destructor, etc. is needed because vector<T> handles all the memory.

  i = &sv is illegal because there is no conversion from pointer to SafeIterator.

  int *pi = pci is illegal because *pi = ... would modify a const.