Most implemetations of linked lists in c++ use iterators to access the internal nodes. The reasons for iterator use are presented in Gamma's chapter on Iterators:
An aggregate object such as a list should give you a way to access its elements without exposing its internal structure. Moreover, you might want to traverse the list in different ways, depending on what you want to accomplish. But you probably don't want to bloat the List interface with operations for different traversals, even if you could anticipate the ones you will need. You might also need to have more than one traversal pending on the same list.
The Iterator pattern lets you do all this. The key idea in this pattern is to take the responsibility for access and traversal out of the list object and put it into an iterator object. The Iterator class defines an interface for accessing the list's elements. An iterator object is responsible for keeping track of the current element; that is, it knows which elements have been traversed already
When you create a listbox from an array, you keep the entries in the listbox in the same order as the items in the array, to maintain the correspondence between the strings in the listbox and the items in your array. You will see how to use a new type of iterator to sort an array, yet maintain the connection of items in the sorted array with items in the original array.
This new iterator will use two old techniques to achieve our goal. First the sort used is a very simple bubble sort. While you may substitute a different type of sort, for the number of items usually stored in the type of array displayed in a listbox, the bubble sort is fast enough. The second old-time device is to store the subscripts of items in the original array in an array of integers. When you sort the array, you interchange the integers in the second array. This sort is shown here. The array of data is called _array and the array of int is called _sorted.
template < class Type>
void SortedIterator< Type>::sort(RcPointer< Compare < Type> > c)
{
int size = _array.numberInArray();
// create an array of integers where _sorted[n] = n
// this array will hold subscripts for _array
for(int i = 0;i< size;i++)
_sorted.insertItemAt(i,i);
// sort the subscripts so _sorted[0] contains the
// subscript of the item in _array to be listed first
for (int i = 0;i< size-1;i++)
for(int j = 0;j< size-1;j++)
if (c->greaterThan(_array[_sorted[j]],_array[_sorted[j+1]]))
swap(_sorted[j],_sorted[j+1]);
init(); // Set the iterator back to the beginning
}
Comparisions are made using a pointer to an object in a Compare class. This class is an abstract base class. Actual subclasses are made for each type of search. Here is the abstract base class.
template < class Type>
class Compare
{
public:
virtual int equal(const Type &, const Type&)const=0;
virtual int greaterThan(const Type &, const Type&)const = 0;
};
The swap function is a template function.
template <class Type>
void swap(Type &x, Type &y)
{
Type temp = x;
x = y;
y = temp;
}
This iterator has most of the same functions that ArrayIterator has. With the exception of the () operators the functions shared by the two types of iterators are identical. The () functions return the array subscripted by the value in the sorted array. This results in the array being displayed in the desired order. The new [] operators return the item that would appears in the sorted position. Finally the sort is as described above.
template < class Type>
class SortedIterator
{
public:
SortedIterator(Array< Type> &a)
:_array(a){init();} // Reference variables must be initialized in the initialization section
void sort(RcPointer< Compare < Type> > c);
void init(){_loc = 0;}
int operator++(){return _loc++;}
int operator ++(int){return _loc++;}
Type operator ()()const{return _array[_sorted[_loc]];}
Type& operator()(){return _array[_sorted[_loc]];}
Type operator [](int i)const{return _array[_sorted[i]];}
Type& operator [](int i){return _array[_sorted[i]];}
// the next function returns the actual position of an item in _array for interger where which is the location in the listbox
int loc(where)const {return _sorted[where];}
operator int(){return _loc < _array.numberInArray();}
private:
Array< Type> &_array; // This is a reference to the orginal. Changes made here
// also appear in the original array.
int _loc;
Array< int> _sorted;
};
For a detail example of the application of this iterator click here .
This lab will give you experience with the sort you have just seen and with factories you saw this week and last.
This week you will learn how to create a linked list using counted pointers . Most of this construction is similar to what you have seen before, except accessing interal nodes will be by iterator only. An industrial strength linked list will be covered next week .
Recall that counted pointers contain an integer that keeps track of the number of variables that are currently assigned to the pointer. Everytime a pointer variable is assigned to or is created with a (as in a value parameter) given counted pointer, that count is incremented by one. Everytime a pointer variable that is set to a counted pointer is destroyed or assigned a different pointer, the count is decremented. If the count ever gets to zero, then the counted pointer is no longer accessable and the memory it uses is deleted.
The list itself is a simple linked list that only allows insert and delete at the beginning of the list. This will change when you add an iterator . All implementations of linked lists require that nodes in the list contain the address of the next node in addition to the data stored at a given location. Your node class will have functions that are needed for simple insert and delete operations. The Node class will also needs a getNext function to allow the list class to scroll to the next node.. This reference can be used as a left-size of an assignment expression. Here is the first definition of Node. In the deleteItem function, you must hold onto the address of the node following the node that will be deleted. If you don't do this, the node is deleted before the next address is assigned to _next.
template < class Type>
class Node
{
public:
Node(){} // notice that the default constructor for an RcPointer
// sets the pointer to NULL. _next is NULL in this case.
Node(const Type& data, const RcPointer< Node < Type> > next)
:_data(data),_next(next)
{}
void print()const{cout<<_data;}
RcPointer< Node < Type> > getNext()const{return _next;}
void insert(const Type &data){_next = new Node< Type>(data,_next);}
void deleteNext(){RcPointer >temp = _next->_next; _next = temp;}
private:
RcPointer< Node < Type> > _next;
Type _data;
};
template < class Type>
class List
{
public:
List(){_head = new Node< Type>;}
void insert(const Type& data){_head->insert(data);}
void deleteItem(){_head->deleteNext();}
void print()const;
protected :
RcPointer< Node < Type> > _head;
};
template < class Type>
void List< Type>::print()const
{
RcPointer< Node< Type> > current = _head->getNext();
while(current)
{
current->print();
cout << endl;
current = current->getNext();
}
}
As is always the case in c++, you must worry about reclaiming memory when you can no longer access a node. The example included here shows that if you delete an item, set a list equal to another list or just leave the scope of a list all memory is returned. The printouts from the destructor of the counted pointer have been added so you can see that each node is destroyed. To get the destructor to print, uncomment the line "#define TRACE_MODE" in the file RcPointe.h. The example code is can be downloaded by clicking here .
Iterator's primary purpose is to travers all or part of the list in the order. Functions and operators used to do this are the main messages of the iterator. In this case the traversal messages are:
In addition there are functions that set the position of an iterator:
The messagesmoveTo, * and ++ can be used to print a list. Notice that the post operator is best because when you move to 1, the first item is already in position to print. If you use the prefix ++ the second item is the first to print. Also with the prefix ++ operator, you cannot check to see if you are at the end of the list before printing.
next.moveTo(1);
while(next)
cout<< *next++<< endl;
cout<<"Using the preoperator "<< endl;
next.moveTo(1);
for(int i = 1;i<= l.getSize()-1;i++)
cout<< *++next<< endl;
The two increment operators are given here:
template < class Type>
RcPointer< Node< Type> > ListIterator< Type>::operator ++()
{
if(_position<= _size)
{
_prior = _current;
++_position;
_current = _current->getNext();
return _current;
}
return NULL;
}
template < class Type>
RcPointer< Node< Type> > ListIterator< Type>::operator ++(int)
{
if(_position<= _size)
{
_prior = _current;
++_position;
RcPointer< Node< Type> > temp = _current;
_current = _current->getNext();
return temp;
}
return NULL;
}
Other standard messages are those that initialize, test for the end, and retrieve the data at the current position.
Finally there are some messages that have been frequently used with lists. Namely the insert and deleteItem functions use for insertions and deletions other than at the begining of the list. The iterator keeps track of its current position in the list with the pointers _current (the current node), _prior (the node preceding _current), and _position (the cardinal position of _current). The pointer _head marks the begining of the list in case you need to go backward and the size of the list is given as _size. The functions are fairly straight forward and you can look at the whole project by clicking here .
template < class Type>
class ListIterator
{
public:
ListIterator(const List< Type> *l);
virtual int find(const Type &data);
virtual int findAfter(const Type &data,int where);
void moveTo(int);
Type operator *()const;
void insert(const Type &data);// inserts data after _prior
void deleteItem();//deletes _current
RcPointer< Node< Type> > operator ++();//next item in list prefix operator
RcPointer< Node< Type> >operator ++(int); //postfix get next item in list
operator int(){return _position <= _size;}
protected:
void init();
RcPointer< Node < Type> > _head;
RcPointer< Node< Type> > _prior;
RcPointer< Node< Type> > _current;
int _position;
int _size;
};
This implementation changes the insert and delete functions to insert at the end of the list if the new item isn't in the list. DeleteItem finds the item and deletes it. Both depend heavily on the iterator function find. Notice that the iterators are actually implemented as pointers. This is to allow different types of iterators to be used. The function getIterator creates a pointer an iterator specific to the type of list. There is a simple example of an ordered list in the full implementation .
template < class Type>
void List< Type>::insert(const Type& data)
{
RcPointer< ListIterator< Type> >next = getIterator();
int where = next->find(data);
if (where == 0)
{
next->insert(data);
_size++;
}
}
template< class Type>
void List< Type>::deleteItem(const Type data)
{
RcPointer< ListIterator< Type> > next = getIterator();
int where = next->find(data);
if (where > 0)
{
next->deleteItem();
_size--;
}
}