This chapter is from the book
This chapter is from the book
This chapter is from the book
Making Sense of Iterators
The obvious question is, how do we implement this layer of abstraction? We need a collection of objects that support the same set of operators as the built-in pointer (++, *, ==, !=) but allow us to provide a unique implementation of those operators. We can do exactly this with the C++ class mechanism. We'll design a set of iterator classes that are programmed using the same syntax as that of a pointer. For example, if first and last are list class iterators, we can write
// first and last are iterator class objects
while ( first != last )
{
cout << *first << ' ';
++first;
}
the same as if first and last are actual pointers. The difference is that the dereference operator (*), the inequality operator (!=), and the increment operator (++) represent inline function calls associated with the iterator classes. For the list class iterator, for example, the associated increment function advances to the next element by following the list pointer. For the vector class iterator, the increment function advances to the next element by adding the size of one element to the current address.
In Chapter 4, we look at how to implement an iterator class, including how to provide function instances of particular operators. In this section, we look at how to define and use the iterators associated with the standard library container classes.
Where do we get iterators? Each container class provides a begin() operation that returns an iterator that addresses the first element of the container and an end() operation that returns an iterator that addresses 1 past the last element of the container. For example, disregarding how we define an iterator object for the moment, we assign, compare, increment, and dereference an iterator as follows:
for ( iter = svec.begin();
iter != svec.end(); ++iter )
cout << *iter << ' ';
Before we look at how to define an iterator, let's think for a moment about the information its definition must provide: the type of the container over which it iterates, which determines how it accesses the next element; and the type of the element being addressed, which determines the value returned from a dereference of the iterator.
One possible syntax for an iterator definition might be to pass these two types as parameters to an iterator class:
// one possible iterator syntax // note: not actually used in the STL iterator< vector, string > iter;
The actual syntax looks considerably more complicated, at least at first sight. It also provides a more elegant solution, although that may not be apparent, at least not until we implement and use an iterator class in Chapter 4.
vector<string> svec; // the standard library iterator syntax // iter addresses vector elements of type string // it is initialized to the first element of svec vector<string>::iterator iter = svec.begin();
iter is defined to be an iterator for vectors of string elements. It is initialized to address the first element of svec. (The double colon [::] indicates that iterator is a type nested within the string vector definition. This will make more sense when you read Chapter 4 and we implement our own iterator class. For now, we'll just use the iterator.) For a const vector, such as
const vector<string> cs_vec;
we traverse the elements using a const_iterator:
vector<string>::const_iterator = cs_vec.begin();
A const_iterator allows us to read the vector elements but not write to them.
To access the element through the iterator, we dereference it just as we do a built-in pointer:
cout << "string value of element: " << *iter;
Similarly, to invoke an operation of the underlying string element through iter, we use the member selection arrow syntax:
cout << "( " << iter->size() << " ): " << *iter << endl;
Here is a reimplementation of display() as a function template using iterators rather than the subscript operator:
template <typename elemType>
void display( const vector<elemType> &vec, ostream &os )
{
vector<elemType>::const_iterator iter = vec.begin();
vector<elemType>::const_iterator end_it = vec.end();
// if vec is empty, iter and end_it are equal
// and the for-loop never executes
for ( ; iter != end_it; ++iter )
os << *iter << ' ';
os << endl;
}
Our reimplementation of find() supports either a pair of built-in pointers or a pair of iterators to a container of a particular type:
template <typename IteratorType, typename elemType >
IteratorType
find( IteratorType first, IteratorType last,
const elemType &value )
{
for ( ; first != last; ++first )
if ( value == *first )
return first;
return last;
}
Let's see how we might use this reimplementation of find() with a built-in array, a vector, and a list:
const int asize = 8;
int ia[ asize ] = { 1, 1, 2, 3, 5, 8, 13, 21 };
// initialize the list and vector with the 8 elements of ia
vector<int> ivec( ia, ia+asize );
list<int> ilist( ia, ia+asize );
int *pia = find( ia, ia+asize, 1024 );
if ( pia != ia+asize )
// found ...
vector< int >::iterator it;
it = find( ivec.begin(), ivec.end(), 1024 );
if ( it != ivec.end() )
// found ...
list< int >::iterator iter;
iter = find( ilist.begin(), ilist.end(), 1024 );
if ( iter != ilist.end() )
// found ...
Not bad. We've carried the generality of find() pretty far—a lot farther than we imagined we could when we began the preceding section. This is not the end of the story, however, although it is pretty much the end of this section.
find()'s implementation uses the equality operator of the underlying element type. If the underlying element type does not provide an equality operator, or if the user wants to define element equality differently, this instance of find() proves too inflexible. How can we add that flexibility? One solution is to replace the use of the equality operator with a function passed in as a pointer to function. A second solution is something called a function object, a special class implementation. In Chapter 4, we look at how to design a function object.
What we've accomplished in our successive iterations of find() is to evolve it into the generic find() algorithm. (find_if() provides the additional flexibility of passing in a pointer to a function or function object in place of using the equality operator of the underlying element.)
There are more than 60 generic algorithms. The following represents a partial listing (the full listing and an example of using each one can be found in Appendix B).
Search algorithms—find(), count(), adjacent_find(), find_if(), count_if(), binary_search(), and find_first_of()
Sorting and general ordering algorithms—merge(), partial_sort(), partition(), random_shuffle(), reverse(), rotate(), and sort()
Copy, deletion, and substitution algorithms—copy(), remove(), remove_if(), replace(), replace_if(), swap(), and unique()
Relational algorithms—equal(), includes(), and mismatch()
Generation and mutation algorithms—fill(), for_each(), generate(), and transform()
Numeric algorithms—accumulate(), adjacent_difference(), partial_sum(), and inner_product()
Set algorithms—set_union() and set_difference()
The algorithms ending with the _if suffix take either a pointer to function or a function object to determine equality. In addition, algorithms that modify the container, such as replace() and unique(), come in two versions: an in-place version that changes the original container and a version that returns a copy of the modified container. There are, for example, both a replace() and a replace_copy() algorithm.