Inapoi
Cuprins
Introducing
iterators
An iterator is an object that
moves through a container of other objects and selects them one at a time,
without providing direct access to the implementation of that container.
Iterators provide a standard way to access elements, whether or not a container
provides a way to access the elements directly. You will see iterators used most
often in association with container classes, and iterators are a fundamental
concept in the design and use of the Standard C++ containers, which are fully
described in Volume 2 of this book (downloadable from
www.BruceEckel.com). An iterator is also a kind of
design pattern, which is
the subject of a chapter in Volume 2.
In many ways, an iterator is a
“smart pointer,” and in fact you’ll notice that iterators
usually mimic most pointer operations. Unlike a pointer, however, the iterator
is designed to be safe, so you’re much less likely to do the equivalent of
walking off the end of an array (or if you do, you find out about it more
easily).
Consider the first example in this
chapter. Here it is with a simple iterator added:
//: C16:IterIntStack.cpp
// Simple integer stack with iterators
//{L} fibonacci
#include "fibonacci.h"
#include "../require.h"
#include <iostream>
using namespace std;
class IntStack {
enum { ssize = 100 };
int stack[ssize];
int top;
public:
IntStack() : top(0) {}
void push(int i) {
require(top < ssize, "Too many push()es");
stack[top++] = i;
}
int pop() {
require(top > 0, "Too many pop()s");
return stack[--top];
}
friend class IntStackIter;
};
// An iterator is like a "smart" pointer:
class IntStackIter {
IntStack& s;
int index;
public:
IntStackIter(IntStack& is) : s(is), index(0) {}
int operator++() { // Prefix
require(index < s.top,
"iterator moved out of range");
return s.stack[++index];
}
int operator++(int) { // Postfix
require(index < s.top,
"iterator moved out of range");
return s.stack[index++];
}
};
int main() {
IntStack is;
for(int i = 0; i < 20; i++)
is.push(fibonacci(i));
// Traverse with an iterator:
IntStackIter it(is);
for(int j = 0; j < 20; j++)
cout << it++ << endl;
} ///:~
The IntStackIter has been created
to work only with an IntStack. Notice that IntStackIter is a
friend of IntStack, which gives it access to all the
private elements of IntStack.
Like a pointer,
IntStackIter’s job is to move through an IntStack and
retrieve values. In this simple example, the IntStackIter can move only
forward (using both the pre- and postfix forms of the operator++).
However, there is no boundary to the way an iterator can be defined, other than
those imposed by the constraints of the container it works with. It is perfectly
acceptable (within the limits of the underlying container) for an iterator to
move around in any way within its associated container and to cause the
contained values to be modified.
It is customary that an iterator is
created with a constructor that attaches it to a single container object, and
that the iterator is not attached to a different container during its lifetime.
(Iterators are usually small and cheap, so you can easily make another
one.)
With the iterator, you can traverse the
elements of the stack without popping them, just as a pointer can move through
the elements of an array. However, the iterator knows the underlying structure
of the stack and how to traverse the elements, so even though you are moving
through them by pretending to “increment a pointer,” what’s
going on underneath is more involved. That’s the key to the iterator: It
is abstracting the complicated process of moving from one container element to
the next into something that looks like a pointer. The goal is for every
iterator in your program to have the same interface so that any code that uses
the iterator doesn’t care what it’s pointing to – it just
knows that it can reposition all iterators the same way, so the container that
the iterator points to is unimportant. In this way you can write more generic
code. All of the containers and algorithms in the Standard C++ Library are based
on this principle of iterators.
To aid in making things more generic, it
would be nice to be able to say “every container has an associated class
called iterator,” but this will typically cause naming problems.
The solution is to add a nested
iterator class to each container (notice that in this case,
“iterator” begins with a lowercase letter so that it conforms
to the style of the Standard C++ Library). Here is IterIntStack.cpp with
a nested iterator:
//: C16:NestedIterator.cpp
// Nesting an iterator inside the container
//{L} fibonacci
#include "fibonacci.h"
#include "../require.h"
#include <iostream>
#include <string>
using namespace std;
class IntStack {
enum { ssize = 100 };
int stack[ssize];
int top;
public:
IntStack() : top(0) {}
void push(int i) {
require(top < ssize, "Too many push()es");
stack[top++] = i;
}
int pop() {
require(top > 0, "Too many pop()s");
return stack[--top];
}
class iterator;
friend class iterator;
class iterator {
IntStack& s;
int index;
public:
iterator(IntStack& is) : s(is), index(0) {}
// To create the "end sentinel" iterator:
iterator(IntStack& is, bool)
: s(is), index(s.top) {}
int current() const { return s.stack[index]; }
int operator++() { // Prefix
require(index < s.top,
"iterator moved out of range");
return s.stack[++index];
}
int operator++(int) { // Postfix
require(index < s.top,
"iterator moved out of range");
return s.stack[index++];
}
// Jump an iterator forward
iterator& operator+=(int amount) {
require(index + amount < s.top,
"IntStack::iterator::operator+=() "
"tried to move out of bounds");
index += amount;
return *this;
}
// To see if you're at the end:
bool operator==(const iterator& rv) const {
return index == rv.index;
}
bool operator!=(const iterator& rv) const {
return index != rv.index;
}
friend ostream&
operator<<(ostream& os, const iterator& it) {
return os << it.current();
}
};
iterator begin() { return iterator(*this); }
// Create the "end sentinel":
iterator end() { return iterator(*this, true);}
};
int main() {
IntStack is;
for(int i = 0; i < 20; i++)
is.push(fibonacci(i));
cout << "Traverse the whole IntStack\n";
IntStack::iterator it = is.begin();
while(it != is.end())
cout << it++ << endl;
cout << "Traverse a portion of the IntStack\n";
IntStack::iterator
start = is.begin(), end = is.begin();
start += 5, end += 15;
cout << "start = " << start << endl;
cout << "end = " << end << endl;
while(start != end)
cout << start++ << endl;
} ///:~
When making a nested friend class,
you must go through the process of first declaring the name of the class, then
declaring it as a friend, then defining the class. Otherwise, the
compiler will get confused.
Some new twists have been added to the
iterator. The current( ) member function produces the element in the
container that the iterator is currently selecting. You can “jump”
an iterator forward by an arbitrary number of elements using operator+=.
Also, you’ll see two overloaded operators: == and != that
will compare one iterator with another. These can compare any two
IntStack::iterators, but they are primarily intended as a test to
see if the iterator is at the end of a sequence in the same way that the
“real” Standard C++ Library iterators do.
The idea is that two iterators define a range, including the first element
pointed to by the first iterator and up to but not including the last
element pointed to by the second iterator. So if you want to move through the
range defined by the two iterators, you say something like
this:
while(start != end)
cout << start++ << endl;
where start and end are the
two iterators in the range. Note that the end iterator, which we often
refer to as the end sentinel, is not dereferenced
and is there only to tell you that you’re at the end of the sequence. Thus
it represents “one past the end.”
Much of the time you’ll want to
move through the entire sequence in a container, so the container needs some way
to produce the iterators indicating the beginning of the sequence and the end
sentinel. Here, as in the Standard C++ Library, these iterators are produced by
the container member functions begin( ) and end( ).
begin( ) uses the first iterator constructor that defaults to
pointing at the beginning of the container (this is the first element pushed on
the stack). However, a second constructor, used by end( ), is
necessary to create the end sentinel iterator. Being “at the
end” means pointing to the top of the stack, because top always
indicates the next available – but unused – space on the stack. This
iterator constructor takes a second argument of type bool, which
is a dummy to distinguish the two constructors.
The Fibonacci
numbers are used again to fill the IntStack in main( ), and
iterators are used to move through the whole IntStack and also
within a narrowed range of the sequence.
The next step, of course, is to make the
code general by templatizing it on the type that it holds, so that instead of
being forced to hold only ints you can hold any type:
//: C16:IterStackTemplate.h
// Simple stack template with nested iterator
#ifndef ITERSTACKTEMPLATE_H
#define ITERSTACKTEMPLATE_H
#include "../require.h"
#include <iostream>
template<class T, int ssize = 100>
class StackTemplate {
T stack[ssize];
int top;
public:
StackTemplate() : top(0) {}
void push(const T& i) {
require(top < ssize, "Too many push()es");
stack[top++] = i;
}
T pop() {
require(top > 0, "Too many pop()s");
return stack[--top];
}
class iterator; // Declaration required
friend class iterator; // Make it a friend
class iterator { // Now define it
StackTemplate& s;
int index;
public:
iterator(StackTemplate& st): s(st),index(0){}
// To create the "end sentinel" iterator:
iterator(StackTemplate& st, bool)
: s(st), index(s.top) {}
T operator*() const { return s.stack[index];}
T operator++() { // Prefix form
require(index < s.top,
"iterator moved out of range");
return s.stack[++index];
}
T operator++(int) { // Postfix form
require(index < s.top,
"iterator moved out of range");
return s.stack[index++];
}
// Jump an iterator forward
iterator& operator+=(int amount) {
require(index + amount < s.top,
" StackTemplate::iterator::operator+=() "
"tried to move out of bounds");
index += amount;
return *this;
}
// To see if you're at the end:
bool operator==(const iterator& rv) const {
return index == rv.index;
}
bool operator!=(const iterator& rv) const {
return index != rv.index;
}
friend std::ostream& operator<<(
std::ostream& os, const iterator& it) {
return os << *it;
}
};
iterator begin() { return iterator(*this); }
// Create the "end sentinel":
iterator end() { return iterator(*this, true);}
};
#endif // ITERSTACKTEMPLATE_H ///:~
You can see that the transformation from
a regular class to a template is reasonably transparent. This approach of
first creating and debugging an ordinary class, then making it into a template,
is generally considered to be easier than creating the template from
scratch.
Notice that instead of just
saying:
friend iterator; // Make it a friend
friend class iterator; // Make it a friend
This is important because the name
“iterator” is already in scope, from an included
file.
Instead
of the current( ) member function, the iterator has an
operator* to select the current element, which makes the iterator
look more like a pointer and is a common practice.
Here’s the revised example to test
the template:
//: C16:IterStackTemplateTest.cpp
//{L} fibonacci
#include "fibonacci.h"
#include "IterStackTemplate.h"
#include <iostream>
#include <fstream>
#include <string>
using namespace std;
int main() {
StackTemplate<int> is;
for(int i = 0; i < 20; i++)
is.push(fibonacci(i));
// Traverse with an iterator:
cout << "Traverse the whole StackTemplate\n";
StackTemplate<int>::iterator it = is.begin();
while(it != is.end())
cout << it++ << endl;
cout << "Traverse a portion\n";
StackTemplate<int>::iterator
start = is.begin(), end = is.begin();
start += 5, end += 15;
cout << "start = " << start << endl;
cout << "end = " << end << endl;
while(start != end)
cout << start++ << endl;
ifstream in("IterStackTemplateTest.cpp");
assure(in, "IterStackTemplateTest.cpp");
string line;
StackTemplate<string> strings;
while(getline(in, line))
strings.push(line);
StackTemplate<string>::iterator
sb = strings.begin(), se = strings.end();
while(sb != se)
cout << sb++ << endl;
} ///:~
The
first use of the iterator just marches it from beginning to end (and shows that
the end sentinel works properly). In the second usage, you can see how iterators
allow you to easily specify a range of elements (the containers and iterators in
the Standard C++ Library use this concept of ranges almost everywhere). The
overloaded operator+= moves the start and end iterators to
positions in the middle of the range of the elements in is, and these
elements are printed out. Notice in the output that the end sentinel is
not included in the range, thus it can be one past the end of the range
to let you know you’ve passed the end – but you don’t
dereference the end sentinel, or else you can end up dereferencing a null
pointer. (I’ve put guarding in the StackTemplate::iterator, but in
the Standard C++ Library containers and iterators there is no such code –
for efficiency reasons – so you must pay attention.)
Lastly, to verify that the
StackTemplate works with class objects, one is instantiated for
string and filled with the lines from the source-code file, which are
then printed
out.
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.
PStash with iterators
For most container classes it makes sense
to have an iterator. Here’s an iterator added to the PStash
class:
//: C16:TPStash2.h
// Templatized PStash with nested iterator
#ifndef TPSTASH2_H
#define TPSTASH2_H
#include "../require.h"
#include <cstdlib>
template<class T, int incr = 20>
class PStash {
int quantity;
int next;
T** storage;
void inflate(int increase = incr);
public:
PStash() : quantity(0), storage(0), next(0) {}
~PStash();
int add(T* element);
T* operator[](int index) const;
T* remove(int index);
int count() const { return next; }
// Nested iterator class:
class iterator; // Declaration required
friend class iterator; // Make it a friend
class iterator { // Now define it
PStash& ps;
int index;
public:
iterator(PStash& pStash)
: ps(pStash), index(0) {}
// To create the end sentinel:
iterator(PStash& pStash, bool)
: ps(pStash), index(ps.next) {}
// Copy-constructor:
iterator(const iterator& rv)
: ps(rv.ps), index(rv.index) {}
iterator& operator=(const iterator& rv) {
ps = rv.ps;
index = rv.index;
return *this;
}
iterator& operator++() {
require(++index <= ps.next,
"PStash::iterator::operator++ "
"moves index out of bounds");
return *this;
}
iterator& operator++(int) {
return operator++();
}
iterator& operator--() {
require(--index >= 0,
"PStash::iterator::operator-- "
"moves index out of bounds");
return *this;
}
iterator& operator--(int) {
return operator--();
}
// Jump interator forward or backward:
iterator& operator+=(int amount) {
require(index + amount < ps.next &&
index + amount >= 0,
"PStash::iterator::operator+= "
"attempt to index out of bounds");
index += amount;
return *this;
}
iterator& operator-=(int amount) {
require(index - amount < ps.next &&
index - amount >= 0,
"PStash::iterator::operator-= "
"attempt to index out of bounds");
index -= amount;
return *this;
}
// Create a new iterator that's moved forward
iterator operator+(int amount) const {
iterator ret(*this);
ret += amount; // op+= does bounds check
return ret;
}
T* current() const {
return ps.storage[index];
}
T* operator*() const { return current(); }
T* operator->() const {
require(ps.storage[index] != 0,
"PStash::iterator::operator->returns 0");
return current();
}
// Remove the current element:
T* remove(){
return ps.remove(index);
}
// Comparison tests for end:
bool operator==(const iterator& rv) const {
return index == rv.index;
}
bool operator!=(const iterator& rv) const {
return index != rv.index;
}
};
iterator begin() { return iterator(*this); }
iterator end() { return iterator(*this, true);}
};
// Destruction of contained objects:
template<class T, int incr>
PStash<T, incr>::~PStash() {
for(int i = 0; i < next; i++) {
delete storage[i]; // Null pointers OK
storage[i] = 0; // Just to be safe
}
delete []storage;
}
template<class T, int incr>
int PStash<T, incr>::add(T* element) {
if(next >= quantity)
inflate();
storage[next++] = element;
return(next - 1); // Index number
}
template<class T, int incr> inline
T* PStash<T, incr>::operator[](int index) const {
require(index >= 0,
"PStash::operator[] index negative");
if(index >= next)
return 0; // To indicate the end
require(storage[index] != 0,
"PStash::operator[] returned null pointer");
return storage[index];
}
template<class T, int incr>
T* PStash<T, incr>::remove(int index) {
// operator[] performs validity checks:
T* v = operator[](index);
// "Remove" the pointer:
storage[index] = 0;
return v;
}
template<class T, int incr>
void PStash<T, incr>::inflate(int increase) {
const int tsz = sizeof(T*);
T** st = new T*[quantity + increase];
memset(st, 0, (quantity + increase) * tsz);
memcpy(st, storage, quantity * tsz);
quantity += increase;
delete []storage; // Old storage
storage = st; // Point to new memory
}
#endif // TPSTASH2_H ///:~
Most of this file is a fairly
straightforward translation of both the previous PStash and the nested
iterator into a template. This time, however, the operators return
references to the current iterator, which is the more typical and flexible
approach to take.
The destructor calls delete for
all contained pointers, and because the type is captured by the template,
proper destruction will take place. You should be aware that if the
container holds pointers to a base-class type, that type should have a
virtual destructor to
ensure proper cleanup of derived objects whose addresses have been upcast when
placing them in the container.
The PStash::iterator follows the
iterator model of bonding to a single container object for its lifetime. In
addition, the copy-constructor allows you to make a new iterator pointing at the
same location as the existing iterator that you create it from, effectively
making a bookmark into the container. The operator+= and
operator-= member functions allow you to move an iterator by a number of
spots, while respecting the boundaries of the container. The overloaded
increment and decrement operators move the iterator by one place. The
operator+ produces a new iterator that’s moved forward by the
amount of the addend. As in the previous example, the pointer dereference
operators are used to operate on the element the iterator is referring to, and
remove( ) destroys the current object by calling the
container’s remove( ).
The same kind of code as before (a
la the Standard C++ Library containers) is used for creating the
end sentinel: a second
constructor, the container’s end( ) member function, and
operator== and operator!= for comparison.
The following example creates and tests
two different kinds of Stash objects, one for a new class called
Int that announces its construction and destruction and one that holds
objects of the Standard library string class.
//: C16:TPStash2Test.cpp
#include "TPStash2.h"
#include "../require.h"
#include <iostream>
#include <vector>
#include <string>
using namespace std;
class Int {
int i;
public:
Int(int ii = 0) : i(ii) {
cout << ">" << i << ' ';
}
~Int() { cout << "~" << i << ' '; }
operator int() const { return i; }
friend ostream&
operator<<(ostream& os, const Int& x) {
return os << "Int: " << x.i;
}
friend ostream&
operator<<(ostream& os, const Int* x) {
return os << "Int: " << x->i;
}
};
int main() {
{ // To force destructor call
PStash<Int> ints;
for(int i = 0; i < 30; i++)
ints.add(new Int(i));
cout << endl;
PStash<Int>::iterator it = ints.begin();
it += 5;
PStash<Int>::iterator it2 = it + 10;
for(; it != it2; it++)
delete it.remove(); // Default removal
cout << endl;
for(it = ints.begin();it != ints.end();it++)
if(*it) // Remove() causes "holes"
cout << *it << endl;
} // "ints" destructor called here
cout << "\n-------------------\n";
ifstream in("TPStash2Test.cpp");
assure(in, "TPStash2Test.cpp");
// Instantiate for String:
PStash<string> strings;
string line;
while(getline(in, line))
strings.add(new string(line));
PStash<string>::iterator sit = strings.begin();
for(; sit != strings.end(); sit++)
cout << **sit << endl;
sit = strings.begin();
int n = 26;
sit += n;
for(; sit != strings.end(); sit++)
cout << n++ << ": " << **sit << endl;
} ///:~
For convenience, Int has an
associated ostream operator<< for both an Int& and an
Int*.
The first block of code in
main( ) is surrounded by braces to force the destruction of the
PStash<Int> and thus the automatic cleanup by that destructor. A
range of elements is removed and deleted by hand to show that the PStash
cleans up the rest.
For both instances of PStash,
an iterator is created and used to move through the container. Notice the
elegance produced by using these constructs; you aren’t assailed with the
implementation details of using an array. You tell the container and iterator
objects what to do, not how. This makes the solution easier to
conceptualize, to build, and to
modify.
 |
|
|
