6.1. Algorithms, Idioms, Reuse, and Abstraction

Abstraction can be defined as generalization away from specific instances or implementations, and toward the "essence" of an object or process. Some abstractions, like that of an STL iterator, become so familiar that they can be called idiomatic. In software design, the idea reuse achieved through idiomatic abstractions can be just as important as code reuse. The best libraries provide both reusable code components and reusable idioms.

Because most of them operate at the relatively low level of sequence traversal, it's easy to miss the fact that the STL algorithms represent powerful abstractions. In fact, it's commonly arguednot entirely without causethat for trivial tasks, the algorithms are inferior to handwritten loops. For example:^[1]

^[1] In all fairness to the STL algorithms, this example was deliberately chosen to make the case for writing loops by hand.

    // "abstraction"


    std::transform(


        v.begin(), v.end(), v.begin()


      , std::bind2nd(std::plus<int>(),42)


    );


    // handwritten loop


    typedef std::vector<int>::iterator v_iter;


    for (v_iter i = v.begin(), last = v.end(); i != last; ++i)


       *i += 42;

So, what's wrong with the use of transform above?

• The user needs to handle iterators even if she wants to operate on the whole sequence.

• The mechanism for creating function objects is cumbersome and ugly, and brings in at least as many low-level details as it hides.

• Unless the person reading the code eats and breathes the STL components every day, the "abstraction" actually seems to obfuscate what's going on instead of clarifying it.

These weaknesses, however, can be overcome quite easily. For example, we can use the Boost Lambda library, which inspired MPL's compile time lambda expressions, to simplify and clarify the runtime function object:^[2]

^[2] In these examples, _1 refers to a placeholder object from the Boost Lambda library (in namespace boost::lambda). MPL's placeholder types were inspired by the Lambda library's placeholder objects.

    std::transform(v.begin(), v.end(), v.begin(), _1 + 42);

or even:

    std::for_each(v.begin(), v.end(), _1 += 42);

Both statements do exactly the same thing as the raw loop we saw earlier, yet once you are familiar with the idioms of the Lambda library, iterators, and for_each, the use of algorithms is far clearer.

We could raise the abstraction level a bit further by rewriting STL algorithms to operate on whole sequences (like the MPL algorithms do), but let's stop here for now. From the simplification above, you can already see that many of the problems with our example weren't the fault of the algorithm at all. The real culprit was the STL function object framework used to generate the algorithm's function argument. Setting aside those problems, we can see that these "trivial" algorithms abstract away several deceptively simple low-level details:

• Creation of temporary iterators.

• Correct declaration of the iterator type, even in generic code.

• Avoiding known inefficiencies^[3]

  ^[3] When efficiency counts, it's best to avoid post-incrementing most iterators (iter++), since the operator++ implementation must make a copy of the iterator before it is incremented, in order to return its original value. Standard library implementators know about this pitfall and go out of their way to use pre-increment (++iter) instead wherever possible.

• Taking advantage of known optimizations (e.g., loop unrolling)

• And correct generic loop termination: for_each uses pos != finish instead of pos < finish, which would lock it into random access iterators

These all seem easy enough to get right when you consider a single loop, but when that pattern is repeated throughout a large project the chance of errors grows rapidly. The optimizations mentioned above only tend to increase that risk, as they generally introduce even more low-level detail.

More importantly, the use of for_each achieves separation of concerns: the common pattern of traversing and modifying all the elements of a sequence is neatly captured in the name of the algorithm, leaving us only to specify the details of the modification. In the compile time world, this division of labor can be especially important, because as you can see from the binary template we covered in Chapter 1, coding even the simplest repeated processes is not so simple. It's a great advantage to be able to use the library's pre-written algorithms, adding only the details that pertain to the problem you're actually trying to solve.

When you consider the complexity hidden behind algorithms such as std::lower_bound, which implements a customized binary search, or std::stable_sort, which gracefully degrades performance under low memory conditions, it's much easier to see the value of reusing the STL algorithms. Even if we haven't convinced you to call std::for_each whenever you have to operate on all elements of a sequence, we hope you'll agree that even simple sequence algorithms provide a useful level of abstraction.