Add reverse iterators to the STL List class implementation. Define reverse_iterator and co...

In a STL List class, the begin function returns the pointer to the head node and end function returns the pointer to the tail node.

To reverse the list, function rbegin is defined, which returns the pointer to the tail node and function rend returns the pointer to the head node.

In normal STL List class, the begin function points to the head node of the list and the end function points to the tail of the list, whereas in the reverse iterator, the rbegin function points to the tail node of the list, and rend function points to the head node of the list.

The function of overloaded operators: operator++ and operator-- is also reversed. Now the operator++ moves to the previous node and operator-- moves to the next node.

List class with reverse_iterator and const_reverse_iterator having methods rbegin and rend as given below.

template

class List

{

private:

// The basic doubly linked list node.

// Nested inside of List, can be public

// because the Node is itself private

struct Node

{

Object data;

Node *prev;

Node *next;

Node( const Object & d = Object( ), Node * p = NULL, Node * n = NULL )

: data( d ), prev( p ), next( n ) { }

};

public:

// define class const_iterator_reverse

class const_iterator_reverse

{

public:

// Public constructor for const_iterator_replace.

const_iterator_reverse( ) : current( NULL )

{ }

// Return the object stored at the current position.

// For const_iterator_replace, this is an accessor with a

// const reference return type.

const Object & operator* ( ) const

{ return retrieve( ); }

// the increment operator points to the previous node in the list

const_iterator_reverse & operator++ ( )

{

current = current->prev;

return *this;

}

// the increment operator which moves the pointer this.

const_iterator_reverse operator++ ( int )

{

const_iterator_reverse old = *this;

++( *this );

return old;

}

// the decrement operator points to the next node in the list

const_iterator_reverse & operator-- ( )

{

current = current->next;

return *this;

}

// the decrement operator which moves the pointer this.

const_iterator_reverse operator-- ( int )

{

const_iterator_reverse old = *this;

--( *this );

return old;

}

bool operator== ( const const_iterator_replace & rhs ) const

{ return current == rhs.current; }

bool operator!= ( const const_iterator_replace & rhs ) const

{ return !( *this == rhs ); }

protected:

Node *current;

// Protected helper in const_iterator_replace that returns the object

// stored at the current position. Can be called by all

// three versions of operator* without any type conversions.

Object & retrieve( ) const

{ return current->data; }

// Protected constructor for const_iterator_replace.

// Expects a pointer that represents the current position.

const_iterator_replace( Node *p ) : current( p )

{ }

friend class List