Iterators: A failure case

In my first post on iterators, I presented a case where they work well. In this post, I’ll present a clear failure and begin discussing why the deep structure of the design leads to this failure.

Consider the simple Python list comprehension:

res = [i*i for i in a if i > 0]

Given a list of numbers a, this constructs a numeric list res containing the squares of all positive values in a. Comparable facilities exist in Haskell and other languages.

At first glance, the C++ STL has all the facilities to do this in a slightly different way:

• iterators allow us to walk through a collection (the Python list is most closely matched by the STL vector)
• std::copy_if() allows us to copy only elements that satisfy a given criterion
• lambda expressions allow us to define on-the-fly callable objects to square a value and to implement the "greater-than-zero" criterion

And in fact these are sufficient to replicate the functionality of the Python expression. But Oh the syntax!

vector<int> a {10, 11, -1, 12};

vector<int> t1 {};
copy_if (a.cbegin(), a.cend(), back_inserter(t1),
              [](auto i) { return i > 0; });

vector<int> res {};
transform (t1.cbegin(), t1.cend(), back_inserter(res),
               [](auto i) { return i * i; });

There’s really no way to claim that this is close to the clarity and concision of its equivalent Python or Haskell expressions. And we’ll see in future posts that along the way, we have to make subtle decisions about storage allocation (the back_inserter() adaptors are only one of three contending approaches with different tradeoffs).

Furthermore, I wouldn’t expect anyone familiar with list comprehensions to be able to see that the C++ code implemented the same algorithm. There’s so much stuff idiosyncratic to the STL: cbegin()/cend(), back_inserter(), and the arcane syntax of C++ lambdas (you did recognize that [](auto i) { .... } is a lambda-expression, right?). Whereas a non-C++ programmer could likely recognize the gist of the ranged-for used in the last post, there is no way they could understand this algorithm without specific knowledge of C++ and the STL.

Most distracting of all is how the STL foregrounds the intermediate results. In the Python expression, the only names are the source, the sink, and the local scalar representing an element being processed, whereas the STL code forces us to define the intermediate vector t1 and constantly reference all three vectors (a, t1, res) in the expression.

The Python code focuses on the essential algorithm: The source and sink are each mentioned once, while the rest of the expression shows how a given element is transformed along the way. This focus is lost completely in the C++ version, with its constant restatement of the underlying vectors containing the values.

So from a notational standpoint, this approach isn’t up to contemporary standards. The code gcc 6.2 produces, on the other hand, is clean and tight. As with the example in the last post, the optimizer can recognize that the iterators are walking through contiguous blocks of memory and generate simple indirect references. It’s all inline, as well. The only function called in the sequence is a utility to construct values in the result vector, potentially expanding its allocation as necessary. Of particular note is that both lambda expressions have been completely inlined, generating two and one instruction each, respectively. Once again template specialization has allowed abstract source code to produce terse object code.

I can personally attest that this approach is learnable: I was able to write this example without consulting a single reference and compile it the first time. But rather than a testimony to the design, this may just indicate that I’ve fallen in love with my kidnappers.

In the next posts, I want to consider to what degree the notational flaws in this approach are readily correctable. In the last example, the syntactic sugar of ranged-for simplified the notation, bringing it closer to contemporary practice in other languages and making the code more robust. How much can this code be simplified by a few notational improvements and how much is inherent to the whole STL design? I’ll start by comparing C++ lambdas to their counterparts in other languages.