You are to implement some of the STL list class template, with an associated iterator class. Your class will perform more rigorous error checking, but will have fewer tangential operations and only a basic iterator. Almost all of these operations are described in the STL handout.
The list is implement as a doubly-link list, with a header and tail node. Each node in the list stores a pointer to the previous node, a pointer the next node, and the item itself.
The list class provides constructors, a destructor, operator=, begin, end, size, empty, insert, erase, push_back, push_front, pop_back, pop_front, front, and back.
Nested inside the list class is the iterator class. The iterator class supports operator* (two forms: one returns a constant reference, and the other returns a non-constant reference), operator++ and operator-- (to advance and retreat, also in two forms each), and operator== and operator!=, to compare two iterators. The iterator is implemented by storing a pointer to its current node and also a pointer the header node in the list that owns the iterator. The idea is that when a function such as begin returns an iterator, it will set the iterator's current position and store a pointer to the header node of the current list. This pointer is used so that operations such as insert and erase, which require an iterator can verify that the iterator is really attached to the list that is being operated on. (There is a two-parameter constructor for iterator that can be used by list for this purpose.)
Finally, you will need to implement a node class, either by nesting it inside the iterator class, or by making it a separate class in global scope.
A sketch of the list class interface is shown below (with the node nested). It illustrates all the operations that must be supported and the general organization of nesting the class, and providing friend declarations. I suggest that you take significant time to scrutinize it, as you can expect this to be on a quiz. This code DOES NOT have sufficient commenting for a submission and it is missing the usual stuff that would be in a .h file.
/**
* Sketch of list class that mimics STL; known to work on
* Visual C++ 5.0, Borland 5.0, and SunPro 4.0
*/
template <class Object>
class list
{
public:
// The basic node; should be private, but CC has a warning bug.
// Implement a doubly-linked node.
struct node
{
};
// The iterator class (nested inside of list).
// You must implement the member functions shown.
// You may do an inline implementation to avoid nested scope operators.
// Make sure you do error checks.
// Provide ample comments.
class iterator
{
public:
iterator( );
const Object & operator* ( ) const;
Object & operator* ( );
const iterator & operator++ ( );
iterator operator++ ( int );
const iterator & operator-- ( );
iterator operator-- ( int );
bool operator== ( const iterator & rhs ) const;
bool operator!= ( const iterator & rhs ) const;
private:
iterator( const list & source, node *p );
node *current; // The current position
node *header; // The header node in the list that owns the iterator
friend class list<Object>;
};
// Here are the remaining list operations.
// Provide a SEPARATE implementation for these.
// Non-separate implementations will incur a minor deduction.
// You must do considerable error checks to ensure integrity.
list( );
~list( );
list( const list & rhs );
const list & operator= ( const list & rhs );
iterator begin( ) const;
iterator end( ) const;
int size( ) const;
bool empty( ) const;
iterator insert( const iterator & pos, const Object & x );
void erase( const iterator & pos );
void push_back( const Object & x );
void push_front( const Object & x );
void pop_back( );
void pop_front( );
const Object & front( ) const;
const Object & back( ) const;
private:
node *head; // The header node
node *tail; // The tail node
int currentSize; // The current size
void makeEmpty( ); // A helper to perform makeEmpty
friend class iterator;
};