Summary

In this chapter, we've learned that traversal is one of the most fundamental things you can do with a data structure. However, raw pointers alone are insufficient for traversing complicated structures: applying ++ to a raw pointer often doesn't "go on to the next item" in the intended way.

The C++ Standard Template Library provides the concept of iterator as a generalization of raw pointers. Two iterators define a range of data. That range might be only part of the contents of a container; or it might be unbacked by any memory at all, as we saw with getc_iterator and putc_iterator. Some of the properties of an iterator type are encoded in its iterator category--input, output, forward, bidirectional, or random-access--for the benefit of function templates that can use faster algorithms on certain categories of iterators.

If you're defining your own container type, you'll need to define your own iterator types as well--both const and non-const versions. Templates are a handy way to do that. When implementing your own iterator types, avoid the deprecated std::iterator, but consider boost::iterator_facade.