advertisement

Print

What Is an Iterator in C++, Part 1
Pages: 1, 2, 3, 4

Iterators in C++

The C++ standard library provides iterators for the standard containers (for example, list, vector, deque, and so on) and a few other noncontainer classes. You can use an iterator to print the contents of, for example, a vector like this:



vector<int> v;
// fill up v with data...
for (vector<int>::iterator it = v.begin();
     it != v.end(); ++it) {
   cout << *it << endl;
}

The variable it is the iterator. This use case illustrates how the iterator pattern requirements are implemented in C++. Obtain an iterator to the first element in a container by calling that container's begin member function. Advance an iterator to the next element with the pre- or post-increment operator, as in ++it or it++. Get the value it refers to with the pointer dereference operator *, as in *it. Finally, you can see if an iterator is at the end of a range by comparing it to the iterator returned by the container's end member function, which returns an iterator that refers to one past the end of the elements. This is why the continuation test for the for loop in the example above is it != v.end(). These one-past-the-end semantics are important in C++, so let's talk about that for a moment.

The iterator returned by a container's end member function represents a logical element that's one past the last element in a container, not the physical memory location that's just beyond the last element (which doesn't make sense for some kinds of data structures anyway). You should never dereference it, because it is just a marker and holds nothing of value. The point of such a construct is to provide a logical end marker for a range, regardless of the context in which that range is used. Standard algorithms and all member functions that work with a range of iterators use this convention. This is why you can use standard algorithms, such as sort in <algorithm>, like this:

sort(v.begin(), v.end());

sort sorts everything in the range up to, but not including, the iterator supplied as its second argument.

You can see that C++ iterators permit the same operations as the iterator pattern requires, but not literally. It's all there: move to the beginning, advance to the next element, get the referent, and test to see if you're at the end. In addition, different categories of iterators support additional operations, such as moving backward with the decrement operators (--it or it--), or advancing forward or backward by a specified number of elements. I will explain iterator categories a little later.

The above example won't work if you are working with a const container though (it won't even compile). In this case, you need to use a const_iterator, which works just like the iterator type in the example above, except that when you dereference it, you get back a const object. Therefore, a function to print the contents of a const container might look like this:

void printCont(const vector<int>& v) {
   for (vector<int>::const_iterator it = v.begin();
        it != v.end(); ++it) {
      cout << *it << endl;
   }
}

Incidentally, even if you aren't working with a const object, it is a good idea to use a const_iterator if you don't plan on modifying the elements in a container. This way, the compiler will keep you honest if you mistakenly try to modify an element.

There are a couple of important points to make here. First, note that the iterator and const_iterator types above are not part of the C++ language, they are just classes implemented in the standard library (just like the containers). Second, the exact type of an iterator is specific to the container (or other object) it is being used with, which is why you have to declare it using a name that includes the container name, such as vector<int>::iterator. Furthermore, each standard library implementation is free to choose the specific type of a container's iterator types, so long as it exposes it to the user of a container using the names iterator and const_iterator. This can be done with a public typedef. The actual type may be a pointer or a class whose structure and behavior are different from one standard library to another (though they must all support the specific behavior required by the standard).

Use Cases

If you use the standard containers, then you are probably using iterators in one of a few use cases. First of all, there is the simple task of iterating through elements, as I showed in the examples above. You will probably also want to use the standard algorithms with iterators, such as copy:

list<string> x;
x.push_back("peach");
x.push_back("apple");
x.push_back("banana");

// Make y the same size as x.  This creates
// empty strings in y's elements.
list<string> y(x.size());

// This is std::copy...
copy(x.begin(), x.end(), y.begin());

Or, you may want nest calls to standard algorithms. The following line copies elements from x to y starting at the element "apple," if it is found:

copy(find(x.begin(), x.end(), "apple"), x.end(), y.begin());

find returns an iterator that refers to the first element it finds that is equal to its argument. If no element is found, it returns its second argument, which is one past the end of the range.

You can also use the for_each algorithm to call a function for each element in the range:

template<typename T>
void print(const T& val) {
   cout << val << endl;
}
// ...
for_each(y.begin(), y.end(), print<string>);

for_each works with a function like my print function above, or with a function object. Each of these algorithms will work on any of the standard containers, because the algorithms use ranges of iterators and therefore make no assumptions about the type of container.

Pages: 1, 2, 3, 4

Next Pagearrow