The genius insight behind iterators

The story so far:

1. List comprehensions and related techniques such as LINQ are a widely-used, well-adopted notation. They are part of the current consensus on programming language features.
2. C++ and the STL provide the basic mechanisms for implementing list comprehensions.
3. In the simple cases addressed by the C++ ranged for loop, C++/STL can be as concise as a list comprehension.
4. For more complex cases, the C++/STL patterns that address the same use cases as list comprehensions are far more verbose than their Python or Haskell equivalents, introducing many running details and requiring a different focus by the programmer.
5. The syntax of C++ lambdas is not the source of this syntactic complexity. Although the full syntax and semantics of lambdas is subtle, the idioms used in actual code (and the examples used to compare with Python list comprehensions) are simple.
6. We need to look at other components of the C++/STL design for sources of the complexity.

Several mechanisms are provided by C++/STL (I write it this way to emphasize that it is a combined design of features provided by the core C++ language and by the Standard Template Library) to support this sort of algorithm:

• STL containers hold data. Different containers support different patterns of efficient access.
• STL algorithms satisfy commonly-useful requirements for processing collections of data, assuming that the data can be accessed efficiently in one or more patterns.
• C++ ranged for loops provide a concise notation for the special case of single-pass sequential iteration through any STL container.
• C++ lambda expressions provide a concise notation for customizing algorithms with one-off provisions such as filters, accumulators, and so forth.
• C++ templates provide a mechanism for using the access patterns of a collection to select the most appropriate implementation of an algorithm to use with that collection.
• STL iterators provide specified patterns of efficient access.

That last component, iterators, are the STL’s genius contribution to computing. Whether or not you find the C++/STL combination comfortable to use, it is worth learning the approach because it provides a uniquely visible mechanism for a principle connecting data structures and algorithms in any language:

Data structures support patterns of efficient access. Algorithms depend upon specific patterns of efficient access. STL iterators are an explicit representation of the access patterns connecting a data structure (container) and an algorithm.

To illustrate this connection, consider the classic binary search algorithm over a collection. As typically presented, this algorithm presupposes constant-time access to a random element with the collection from any other element. In principle, you can run a binary search on a singly-linked list, but the classical performance guarantees of binary search will not be met: The number of element accesses would increase linearly with the size of the array, rather than the predicted logarithmic increase. You might even get fewer element accesses with linear search. The poor performance arises because a singly-linked list does not support efficient constant-time access from any one element to any other. A container that stores its elements contiguously, such as array or vector, is required for the binary search algorithm to achieve its classical guarantees.

The STL binary search algorithm takes advantage of iterators to run on both linked lists and vectors. It uses the most efficient access pattern supported by the container. I’ll return to this below.

In discussions of data structures and algorithms, as well as most implementations of them, the access patterns linking the two are left implicit. Making that link explicit was a brilliant insight and a contribution to the computing field from the STL design.

The common iterator access patterns

Iterators are categorized according to the efficient access patterns they support. The full set of categories is complex and their distinctions are subtle; I’ll just list three common ones and summarize each informally.

ForwardIterator

Given an element, access to its immediate successor. If you make a copy of the iterator, the copy will generate the same sequence of accesses as the original. (This last point is a rephrasing of the "multi-pass" requirement.)

BidirectionalIterator

Given an element, access to its immediate predecessor and successor. A copy of the iterator will generate the same sequence of accesses as the original.

RandomAccessIterator

Given en element, constant-time access to any other element. A copy of the iterator will generate the same sequence of accesses as the original.

Note that ForwardIterator and BidirectionalIterator technically only specify which access patterns will be inefficient: Given an iterator that only supports successor (and predecessor in the bidirectional case), moving more than one element requires iterating through all intervening elements. The efficiency of the basic successor/predecessor operations is determined by the underlying data structure; in all the standard collections it is constant irrespective of the collection size.

The full list of categories is longer and the requirements more detailed. The above list captures the common distinctions.

Example: The STL Binary search algorithm

The performance of the STL binary search algorithm depends upon the category of iterators that it is passed. Its minimal requirement is a ForwardIterator, which only supports the basic successor operation and whose copies are guaranteed to produce an identical sequence. This last point is essential for the algorithm to work without access to a predecessor operation: Rather than iterating backward, it retains a copy of the iterator to the lowest point in the search range and iterates forward from there.

The binary search algorithm guarantees comparisons proportional to the log of the collection size for any collection supporting ForwardIterators or better but the number of element accesses depends upon the category of iterators provided by the collection. For collections supporting RandomAccessIterators, which permit computation of a midpoint iterator in constant time, the algorithm guarantees logarithmic number of element accesses. However for collections that only support ForwardIterators, such as a linked list, the algorithm guarantees accesses proportional linearly to the collection size. If comparisons are particularly expensive, this may still make binary_search() more efficient than simple linear search for a linked list, even though both algorithms are linear in number of accesses. (In many cases, the binary search algorithm will require more accesses than linear search, due to its initial scan over all elements, so binary search’s saving in comparison time will have to be particularly big to make it faster.)

This flexibility is enabled by the C++ template facility. The library selects a different implementation of binary search depending upon the category of iterator that it is passed. The iterator category in turn is determined by the collection, which exports the iterators representing the best access patterns that it supports.

This design allows the library to choose the best possible algorithm for a given collection, without the programmer explicitly choosing that algorithm:

int main () {
  vector<int> vals_v (10);
  generate(vals_v.begin(), vals_v.end(),
    [ind=0]() mutable {return ind++; });

  forward_list<int> vals_l {};
  copy (vals_v.cbegin(), vals_v.cend(),
    make_back_inserter_fl(vals_l));
  
  copy (vals_v.cbegin(), vals_v.cend(),
    make_ostream_joiner(cout, ", "));
  cout << '\n';

  copy (vals_l.cbegin(), vals_l.cend(),
    make_ostream_joiner(cout, ", "));
  cout << "\n\n";

  cout << binary_search(vals_v.cbegin(), vals_v.cend(), 5) << '\n';
  cout << binary_search(vals_l.cbegin(), vals_l.cend(), 5) << '\n';
}

The highlighted lines are the two calls to std::binary_search(). The first runs on std::vector vals_v, which provides RandomAccessIterator iterators, while the second runs on std::forward_list vals_l, which provides ForwardIterator iterators. Assuming the two containers have the same contents, both calls will perform comparable numbers of comparisons (logarithmic in the number of elements) but the call on the forward_list will perform far more element accesses (linear rather than logarithmic).

So why are iterators so tedious to use?

Iterators are a method for containers to explicitly represent their favoured access patterns, allowing algorithms to optimize their behaviour for those patterns. This is a genuinely novel idea and one that will change how you program once you have used it enough to be comfortable with it.

Yet the example failure case highlighted the tediousness of the iterator approach versus the simplicity of list comprehensions. What is the source of the problem? As with so many complexities of C++ code, it stems from the language’s insistence that you state where and how every value is stored. I’ll turn to that topic in the next post.

Appendix: class back_inserter_fl

The sample program uses a class back_inserter_fl I wrote, together with a convenience function for creating it, make_back_inserter_fl(). The STL std::back_inserter() adaptor requires that the underlying container have a push_back() member. The forward_list cannot support such a function because it has no tail pointer. Building a back inserter for a forward_list is tricky because assignment to the iterator also creates an iterator that will be the location of the next assignment.

I think the following code is pretty close to meeting all the formal requirements but I have neither checked it nor tested in exhaustively. I’m including it here for completeness—check carefully before using it in any production code.

template<typename _L>
class back_inserter_fl {
public:
  using iterator_category = std::forward_iterator_tag;
  using value_type = typename _L::value_type;
  using pointer = value_type*;
  using reference = value_type&;
  using difference_type = typename _L::iterator::difference_type;

  class proxy {
  public:
    proxy (_L& fl_i,
	   back_inserter_fl& bi_i) :
      fl {fl_i},
      bi {bi_i}
    {}

    value_type& operator=(value_type v) {
      auto next_it = fl.insert_after(bi.it, v);
      bi.it = next_it;
      return *next_it; }

  private:
    _L& fl;
    back_inserter_fl& bi;
  };

  back_inserter_fl (_L& fl_i) : fl {&fl_i},
                                it {fl_i.before_begin()} {}
  back_inserter_fl() = default;
  back_inserter_fl(const back_inserter_fl&) = default;
  back_inserter_fl& operator=(const back_inserter_fl&) = default;
  ~back_inserter_fl() = default;

  proxy operator*() { return proxy(*fl, *this); }
  back_inserter_fl& operator++() { return *this; }
  back_inserter_fl  operator++(int) { return *this; }
  back_inserter_fl* operator->() { return this; }

private:
  _L* const fl {nullptr};
  typename _L::iterator it {};
};

template<typename _T>
auto make_back_inserter_fl(forward_list<_T>& fl) {
  return back_inserter_fl<forward_list<_T>>(fl);
}