Iterator categories

Let's revisit the count and count_if functions that we introduced in
Chapter 1, Classical Polymorphism and Generic Programming. Compare the function template definition in this next example to the similar code from that chapter; you'll see that it's identical except for the substitution of a pair of Iterators (that is, an implicitly defined range) for the Container& parameter--and except that I've changed the name of the first function from count to distance. That's because you can find this function, almost exactly as described here, in the Standard Template Library under the name std::distance and you can find the second function under the name std::count_if:

    template<typename Iterator>
    int distance(Iterator begin, Iterator end) 
    {
      int sum = 0;
      for (auto it = begin; it != end; ++it) {
        sum += 1;
      }
      return sum;
    }

    template<typename Iterator, typename Predicate>
    int count_if(Iterator begin, Iterator end, Predicate pred) 
    {
      int sum = 0;
      for (auto it = begin; it != end; ++it) {
        if (pred(*it)) {
            sum += 1;
        }
      }
      return sum; 
    }

    void test() 
    {
      std::vector<int> v = {3, 1, 4, 1, 5, 9, 2, 6};

      int number_above = count_if(v.begin(), v.end(), [](int e) { return e > 5; });
      int number_below = count_if(v.begin(), v.end(), [](int e) { return e < 5; });

      int total = distance(v.begin(), v.end()); // DUBIOUS 

      assert(number_above == 2);
      assert(number_below == 5);
      assert(total == 8);
    }

But let's consider the line marked DUBIOUS in that example. Here we're computing the distance between two Iterators by repeatedly incrementing the one until it reaches the other. How performant is this approach? For certain kinds of iterators--for example, list_of_ints::iterator--we're not going to be able to do better than this. But for vector::iterator or int*, which iterate over contiguous data, it's a little silly of us to be using a loop and an O(n) algorithm when we could accomplish the same thing in O(1) time by simple pointer subtraction. That is, we'd like the standard library version of std::distance to include a template specialization something like this:

    template<typename Iterator>
    int distance(Iterator begin, Iterator end)
    {
      int sum = 0;
      for (auto it = begin; it != end; ++it) {
        sum += 1;
      }
      return sum;
    }

    template<> 
    int distance(int *begin, int *end) 
    {
      return end - begin;
    }

But we don't want the specialization to exist only for int* and std::vector::iterator. We want the standard library's std::distance to be efficient for all the iterator types that support this particular operation. That is, we're starting to develop an intuition that there are (at least) two different kinds of iterators: there are those that are incrementable, comparable, and dereferenceable; and then there are those that are incrementable, comparable, dereferenceable, and also subtractable! It turns out that for any iterator type where the operation i = p - q makes sense, its inverse operation q = p + i also makes sense. Iterators that support subtraction and addition are called random-access iterators.

So, the standard library's std::distance ought to be efficient for both random-access iterators and other kinds of iterators. To make it easier to supply the partial specializations for these templates, the standard library introduced the idea of a hierarchy of iterator kinds. Iterators such as int*, which support addition and subtraction, are known as random-access iterators. We'll say that they satisfy the concept RandomAccessIterator.

Iterators slightly less powerful than random-access iterators might not support addition or subtraction of arbitrary distances, but they at least support incrementing and decrementing with ++p and --p. Iterators of this nature are called BidirectionalIterator. All RandomAccessIterator are BidirectionalIterator, but not necessarily vice versa. In some sense, we can imagine RandomAccessIterator to be a sub-class or sub-concept relative to BidirectionalIterator; and we can say that BidirectionalIterator is a weaker concept, imposing fewer requirements, than RandomAccessIterator.

An even weaker concept is the kind of iterators that don't even support decrementing. For example, our list_of_ints::iterator type doesn't support decrementing, because our linked list has no previous pointers; once you've got an iterator pointing at a given element of the list, you can only move forward to later elements, never backward to previous ones. Iterators that support ++p but not --p are called ForwardIterator. ForwardIterator is a weaker concept than BidirectionalIterator.