Stack with iterators
We can repeat the process with the dynamically-sized
Stack class that has been used as an example throughout the book. Here’s
the Stack class with a nested iterator folded into the mix:
//: C16:TStack2.h
// Templatized Stack with nested iterator
#ifndef TSTACK2_H
#define TSTACK2_H
template<class T> class Stack { struct Link { T* data;
Link* next;
Link(T* dat, Link* nxt)
: data(dat), next(nxt) {} }* head;
public:
Stack() : head(0) {} ~Stack();
void push(T* dat) { head = new Link(dat, head);
}
T* peek() const { return head ? head->data : 0;
}
T* pop();
// Nested iterator class:
class iterator; // Declaration required
friend class iterator; // Make it a friend
class iterator { // Now define it Stack::Link* p;
public:
iterator(const Stack<T>& tl) : p(tl.head) {} // Copy-constructor:
iterator(const iterator& tl) : p(tl.p) {} // The end sentinel iterator:
iterator() : p(0) {} // operator++ returns boolean indicating end:
bool operator++() { if(p->next)
p = p->next;
else p = 0; // Indicates end of list
return bool(p);
}
bool operator++(int) { return operator++(); } T* current() const { if(!p) return 0;
return p->data;
}
// Pointer dereference operator:
T* operator->() const { require(p != 0,
"PStack::iterator::operator->returns 0");
return current();
}
T* operator*() const { return current(); } // bool conversion for conditional test:
operator bool() const { return bool(p); } // Comparison to test for end:
bool operator==(const iterator&) const { return p == 0;
}
bool operator!=(const iterator&) const { return p != 0;
}
};
iterator begin() const { return iterator(*this);
}
iterator end() const { return iterator(); }};
template<class T> Stack<T>::~Stack() { while(head)
delete pop();
}
template<class T> T* Stack<T>::pop() { if(head == 0) return 0;
T* result = head->data;
Link* oldHead = head;
head = head->next;
delete oldHead;
return result;
}
#endif // TSTACK2_H ///:~
You’ll also notice
the class has been changed to support ownership, which works now because the
class knows the exact type (or at least the base type, which will work assuming
virtual destructors are used). The default is for the container to destroy its
objects but you are responsible for any pointers that you pop( ).
The iterator is
simple, and physically very small – the size of a single pointer. When you
create an iterator, it’s initialized to the head of the linked list, and
you can only increment it forward through the list. If you want to start over
at the beginning, you create a new iterator, and if you want to remember a spot
in the list, you create a new iterator from the existing iterator pointing at
that spot (using the iterator’s copy-constructor).
To call functions for the object referred
to by the iterator, you can use the current( ) function, the operator*, or the
pointer dereference operator-> (a common sight in iterators). The latter has an
implementation that looks identical to current( ) because it
returns a pointer to the current object, but is different because the pointer
dereference operator performs the extra levels of dereferencing (see Chapter
12).
The iterator class follows the form
you saw in the prior example. class iterator is nested inside the
container class, it contains constructors to create both an iterator pointing
at an element in the container and an “end sentinel” iterator, and the
container class has the begin( ) and end( ) methods to
produce these iterators. (When you learn the more about the Standard C++
Library, you’ll see that the names iterator, begin( ), and end( )
that are used here were clearly lifted standard container classes. At the end
of this chapter, you’ll see that this enables these container classes to be
used as if they were Standard C++ Library container classes.)
The entire implementation is contained in
the header file, so there’s no separate cpp file. Here’s a small test that
exercises the iterator:
//: C16:TStack2Test.cpp
#include "TStack2.h"
#include "../require.h"
#include <iostream>
#include <fstream>
#include <string>
using namespace std;
int main() { ifstream file("TStack2Test.cpp"); assure(file, "TStack2Test.cpp");
Stack<string> textlines;
// Read file and store lines in the Stack:
string line;
while(getline(file, line))
textlines.push(new string(line));
int i = 0;
// Use iterator to print lines from the list:
Stack<string>::iterator it = textlines.begin();
Stack<string>::iterator* it2 = 0;
while(it != textlines.end()) { cout << it->c_str() << endl;
it++;
if(++i == 10) // Remember 10th line
it2 = new Stack<string>::iterator(it);
}
cout << (*it2)->c_str() << endl;
delete it2;
} ///:~
A Stack is instantiated to hold string
objects and filled with lines from a file. Then an iterator is created and used
to move through the sequence. The tenth line is remembered by copy-constructing
a second iterator from the first; later this line is printed and the iterator –
created dynamically – is destroyed. Here, dynamic object creation is used to control the lifetime of the object.
