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 ./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.
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.
You must implement two iterators for the sorted<T> class:
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.
template <class T>
sorted<T>::const_iterator sorted<T>::begin() {
// Implementation goes here...
}
We want sorted<T>::const_iterator to be interpreted as a
type, but the compiler can't be sure that it isn't meant to be
a const_iterator variable, and so it produces an error:
sorted.cpp:76: error: expected constructor, destructor, or type conversion before ‘sorted’
We can fix this by telling the compiler explicitly that this is
meant to be a type by adding the typename keyword:
template <class T>
typename sorted<T>::const_iterator sorted<T>::begin() {
// Implementation goes here...
}
See the Wikipedia
Article for a concise description of the uses
of typename.
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.
The following public functions are required. You may implement additional constructors or other private or public functions.
//Default constructor sorted(); // Non-default constructor copies data from array to sorted sorted( T* data, int len ); // Copy constructor sorted( const sorted<T>& srtd ); // Destructor ~sorted(); // 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();
// Default constructor const_iterator(); // 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*();
// Default constructor rand_iterator(); // 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 ~rand_iterator(); // 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);
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 iterator_ex(); // Non-default constructor iterator_ex(const char* message); // Accessor function const char* what() const throw();