|
 |
|
| |
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.
|
|
|
