Project 5: Containers and Iterators

Due: Thursday, May 5, 2016 by 9:00 pm


The objectives of this project are:

Secondarily, through implementation of the container and iterator classes, to gain additional experience with pointers.


The class my_array is a simple container class with a const_iterator. The code for the class and a simple driver are provided:

You can compile and run the driver program:

   g++ -g -Wall -ansi my_array_driver.cpp my_array.cpp -o my_array_driver

The functionality of my_array is very limited:

In addition, we'd like to be able to iterate over the container in a pseudo-random order (the pseudo-random order should be a permutation, meaning we visit each element exactly once). With these improvements the class could be used, say, to store songs in a playlist, and the random iterator would allow us to 'shuffle' the songs. Or I could use it to store a class roster, and the random iterator would allow me to call on students in a pseudo-random order.


Your assignment is to implement a templated class called sorted<T> that stores items in increasing order within a dynamically-allocated array. The elements of sorted<T> can be of any type that implements operator< and operator>. In addition, you must create two iterators: a constant iterator const_iterator that iterates over the elements in sorted order, and a pseudo-random iterator rand_iterator that iterates over the elements according to a pseudo-randomly generated permutation.

The container class sorted<T> and the iterator classes should be defined in the file sorted.h and implemented in sorted.cpp. You must also thoroughly test the classes and submit your tests in the main program mytest.cpp.

Although the my_array class and iterator are very basic, you should study them well as their structure is similar to the container and iterators that you will write.

sorted<T> Container Requirements

The container must be able to store elements of any type that implements operator> and operator<, and must store the items in ascending order.

The container should not have any fixed limits on the number of items that it can hold; to achieve this, it must use a dynamically-allocated storage array. (Clearly, the number of items that can be stored is limited by the amount of memory in the computer, but we're not worried about that.) The storage array must be re-sized as elements are inserted or erased from the container, but it is inefficient to re-size the array every time an element is inserted or erased. One approach is to initialize the array to a small length n; once the number of elements in the array equals n, double the size of the array to 2n; if the number of elements increases to 2n, double the size again to 4n, etc. Similarly, if after erasing elements, at most one-quarter of the capacity of the array is used, it should be re-sized to half the current capacity, but never to less than n elements. The choice of n is up to you, but something like 10 (or 8 if you prefer powers of two) would be reasonable.

Note that you will have to keep track of both the capacity of the array, that is, it's allocated length, and it's size, the number of items stored in the array. In the remainder of the project description, the term 'capacity' will always refer to the allocated storage in the container and 'size' will refer to the number of items stored in the container.

Since the class must use dynamically allocated memory, you must implement a copy constructor and overload operator=.

See the Required Functions section below for a list of functions that must be implemented in the sorted<T> class; additional functions may implemented as needed.

const_iterator and rand_iterator Iterator Requirements

You must implement two iterators for the sorted<T> class:

  1. A constant iterator const_iterator that iterates over the elements of a sorted<T> object in sorted order. We use a const_iterator rather than a plain iterator because we do not want to be able to change a value by dereferencing the iterator since this would potentially store elements out of the proper order.
  2. A random iterator rand_iterator that iterates over the elements of a sorted<T> object in order of a pseudo-random permutation; that is, the iterator access each item of the object exactly once, but in a pseudo-random order.

For rand_iterator constructors that do not accept a seed for the random number generator as a parameter, you may use either a fixed seed or time(NULL).

The rand_iterator will need to construct a permutation, and since the size of the permutation depends on the container it is being used with, the permutation array will need to be allocated dynamically. Therefore, rand_iterator needs a copy constructor and overloaded operator=.

See the Required Functions section below for a list of functions that must be implemented for each of the iterator classes. You will probably need to implement additional functions, either helper functions or non-default constructors.

Implementation Issues

Submitting Your Program

A minimal test program sorted_driver.cpp is provided as an example. Your sorted<T> class should work with this program, but you should also implement more extensive tests in mytest.cpp.

You should submit the following files to the proj5 directory:

If you followed the directions in setting up shared directories, then you can copy your code to the submission directory with:

    cp sorted.h sorted.cpp mytest.cpp iterator_ex.h iterator_ex.cpp  ~/cs202proj/proj5/

You can check that your program compiles and runs in the proj5 directory, but please clean up any .o and executable files. Again, do not develop your code in this directory, and do not keep the only copy of your program here.

If you are submitting late, you need to copy to proj5-late1, or proj5-late2 instead of proj5. Make sure you understand the course late submission policy.

Required Functions

The following public functions are required. You may implement additional constructors or other private or public functions.

sorted<T> required functions

  //Default constructor

  // Non-default constructor copies data from array to sorted
  sorted( T* data, int len );

  // Copy constructor
  sorted( const sorted<T>& srtd );

  // Destructor

  // Overloaded assignment operator
  sorted<T> operator=(const sorted<T>& srtd);

  // Return the capacity of the storage array
  int capacity() const;

  // Return number of items stored
  int size() const;

  // Return the address of the storage array;
  // for use in grading programs
  T* getStorageArray() const;

  // Insert an item in sorted; return iterator to inserted item
  const_iterator insert(T data);

  // Remove an item from sorted; return iterator to next item
  // after the erased item
  const_iterator erase(const_iterator itr);

  // Get element at indx position                                                  
  const T& at(int indx);

  // Starting iterator value for const_iterator
  const_iterator begin();

  // Ending iterator value for const_iterator; typically,
  // one element beyond the last valid element in the array.
  const_iterator end();

  // Starting iterator value for rand_iterator.  Should use constant
  // value or time(NULL) as seed value for srand().
  rand_iterator rndbegin();

  // Starting iterator value for rand_iterator with seed for
  // srand() specified.  Given a sorted<T> object x, repeated 
  // use of rndbegin( unsigned seed ) with the same seed value
  // must produce the same permutation of the elements of x.
  rand_iterator rndbegin( unsigned seed );

  // Ending iterator value for rand_iterator
  rand_iterator rndend();

const_iterator required functions

  // Default constructor

  // Non-default constructor sets value to given address
  const_iterator(T* addr);

  // Pre-increment, e.g. ++itr
  const_iterator operator++();

  // Post-increment, e.g. itr++
  const_iterator operator++(int);

  // operator!= needed for loop control, e.g. itr != x.end()
  bool operator!=(const const_iterator& itr);

  // Unary dereference operator; returns element currently pointed
  // to by the const_iterator
  const T& operator*();

rand_iterator required functions

  // Default constructor

  // Non-default constructor; pointer to sorted<T> object passed 
  // as a parameter, which allows the rand_iterator to access 
  // variables of the associated sorted<T>> container
  rand_iterator( sorted<T>* srtdPtr );

  // Non-default constructor; pointer to sorted<T> passed as in
  // previous constructor, but also passes seed for random number
  // generator
  rand_iterator( sorted<T>* srtdPtr, unsigned seed );

  // Copy constructor
  rand_iterator( const rand_iterator& itr );

  // Destructor

  // pre-increment
  rand_iterator operator++();

  // post-increment
  rand_iterator operator++(int);

  // operator!= needed for loop control, e.g. itr != x.end()
  bool operator!=(const rand_iterator& itr);

  // Unary dereference operator
  const T& operator*();

  // Overloaded assignment operator
  rand_iterator operator=(const rand_iterator& itr);

Exception class required functions [added 4/27]

You may name your exception class whatever you like so long as you put the definition in iterator_ex.h, the implemenation in iterator_ex.cpp, and provide the required functionality; in the following, we use iterator_ex as an example.

  // Default constructor
  // Non-default constructor
  iterator_ex(const char* message);

  // Accessor function
  const char* what() const throw();