Input and output iterators

We can imagine even weaker concepts than ForwardIterator! For example, one useful thing you can do with a ForwardIterator is to make a copy of it, save the copy, and use it to iterate twice over the same data. Manipulating the iterator (or copies of it) doesn't affect the underlying range of data at all. But we could invent an iterator like the one in the following snippet, where there is no underlying data at all, and it's not even meaningful to make a copy of the iterator:

    class getc_iterator {
      char ch;
    public:
      getc_iterator() : ch(getc(stdin)) {}
      char operator*() const { return ch; }
      auto& operator++() { ch = getc(stdin); return *this; }
      auto operator++(int) { auto result(*this); ++*this; return result; }
      bool operator==(const getc_iterator&) const { return false; }
      bool operator!=(const getc_iterator&) const { return true; }
    };

(In fact, the standard library contains some iterator types very similar to this one; we'll discuss one such type, std::istream_iterator, in Chapter 9, Iostreams.) Such iterators, which are not meaningfully copyable, and do not point to data elements in any meaningful sense, are called InputIterator types.

The mirror-image case is also possible. Consider the following invented iterator type:

    class putc_iterator {
      struct proxy {
        void operator= (char ch) { putc(ch, stdout); }
      };
    public:
      proxy operator*() const { return proxy{}; }
      auto& operator++() { return *this; }
      auto& operator++(int) { return *this; }
      bool operator==(const putc_iterator&) const { return false; }
      bool operator!=(const putc_iterator&) const { return true; }
    };

    void test()
    {
      putc_iterator it;
      for (char ch : {'h', 'e', 'l', 'l', 'o', '\n'}) {
        *it++ = ch;
      }
    }

(Again, the standard library contains some iterator types very similar to this one; we'll discuss std::back_insert_iterator in Chapter 3, The Iterator-Pair Algorithms, and std::ostream_iterator in Chapter 9, Iostreams.) Such iterators, which are not meaningfully copyable, and are writeable-into but not readable-out-of, are called OutputIterator types.

Every iterator type in C++ falls into at least one of the following five categories:

• InputIterator
• OutputIterator
• ForwardIterator
• BidirectionalIterator, and/or
• RandomAccessIterator

Notice that while it's easy to figure out at compile time whether a particular iterator type conforms to the BidirectionalIterator or RandomAccessIterator requirements, it's impossible to figure out (purely from the syntactic operations it supports) whether we're dealing with an InputIterator, an OutputIterator, or a ForwardIterator. In our examples just a moment ago, consider: getc_iterator, putc_iterator, and list_of_ints::iterator support exactly the same syntactic operations--dereferencing with *it, incrementing with ++it, and comparison with it != it. These three classes differ only at the semantic level. So how can the standard library distinguish between them?

It turns out that the standard library needs a bit of help from the implementor of each new iterator type. The standard library's algorithms will work only with iterator classes which define a member typedef named iterator_category. That is:

    class getc_iterator {
      char ch;
    public:
      using iterator_category = std::input_iterator_tag;

      // ...
    };

    class putc_iterator {
      struct proxy {
        void operator= (char ch) { putc(ch, stdout); }
      };
    public:
      using iterator_category = std::output_iterator_tag;

      // ...
    };

    template<bool Const>
    class list_of_ints_iterator {
      using node_pointer = std::conditional_t<Const, const list_node*,
       list_node*>;
      node_pointer ptr_;

    public:
      using iterator_category = std::forward_iterator_tag;

      // ...
    };

Then any standard (or heck, non-standard) algorithm that wants to customize its behavior based on the iterator categories of its template type parameters can do that customization simply by inspecting those types' iterator_category.

The iterator categories described in the preceding paragraph, correspond to the following five standard tag types defined in the <iterator> header:

    struct input_iterator_tag { };
    struct output_iterator_tag { };
    struct forward_iterator_tag : public input_iterator_tag { };
    struct bidirectional_iterator_tag : public forward_iterator_tag { };
    struct random_access_iterator_tag : public bidirectional_iterator_tag
    { };

Notice that random_access_iterator_tag actually derives (in the classical-OO, polymorphic-class-hierarchy sense) from bidirectional_iterator_tag, and so on: the conceptual hierarchy of iterator kinds is reflected in the class hierarchy of iterator_category tag classes. This turns out to be useful in template metaprogramming when you're doing tag dispatch; but all you need to know about it for the purposes of using the standard library is that if you ever want to pass an iterator_category to a function, a tag of type random_access_iterator_tag will be a match for a function expecting an argument of type bidirectional_iterator_tag:

    void foo(std::bidirectional_iterator_tag t [[maybe_unused]])
    {
      puts("std::vector's iterators are indeed bidirectional..."); 
    }

    void bar(std::random_access_iterator_tag)
    {
      puts("...and random-access, too!");
    }

    void bar(std::forward_iterator_tag)
    {
      puts("forward_iterator_tag is not as good a match");
    }

    void test()
    {
      using It = std::vector<int>::iterator;
      foo(It::iterator_category{});
      bar(It::iterator_category{});
    }

At this point I expect you're wondering: "But what about int*? How can we provide a member typedef to something that isn't a class type at all, but rather a primitive scalar type? Scalar types can't have member typedefs." Well, as with most problems in software engineering, this problem can be solved by adding a layer of indirection. Rather than referring directly to T::iterator_category, the standard algorithms are careful always to refer to std::iterator_traits<T>::iterator_category. The class template std::iterator_traits<T> is appropriately specialized for the case where T is a pointer type.

Furthermore, std::iterator_traits<T> proved to be a convenient place to hang other member typedefs. It provides the following five member typedefs, if and only if T itself provides all five of them (or if T is a pointer type): iterator_category, difference_type, value_type, pointer, and reference.