 Jonathan Boccara's blog

Recent Posts

# Smart Output Iterators: A Symmetrical Approach to Range Adaptors

Published November 28, 2017 - 2 Comments Some of the algorithms of the STL have a structure in common: they take one or more ranges in input, do something more or less elaborate with them, and produce an output in a destination range.

For example, `std::copy` merely copies the inputs to the outputs, `std::transform` applies a function onto the inputs and sends the results as outputs, and `std::set_difference` takes two input ranges and outputs to a destination range the elements that are in the first one but not in the second.

There are several ways to express this kind of input-operation-output structure on ranges in C++. To illustrate them, let’s take the example of `std::transform` since it is such a central algorithm in the STL.

To make the code examples lighter, let’s suppose that we have some modified versions of STL algorithms that take an input range instead of two iterators, for instance:

and so on for other algorithms.

### Various places to put the logic

The standard way to apply a function to each element and have the results added to a collection is to combine the `std::transform` algorithm with an output iterator such as `std::back_inserter`:

A more modern way, which logic we saw in Ranges: the STL to the Next Level, is to use ranges and range adaptors:

We could even do away with the back_inserter here by using the `push_back` free function, but let’s keep it generic to take account of the case of sending outputs to a stream for example.

One interesting thing to note here is that the main action of the whole operation, which is applying the function `f`, has been transferred to the input range: `strings | ranges::view::transform`, taking this responsibility away from the algorithm. The algorithm then becomes simpler, becoming `copy` instead of `transform`.

When we see it from this perspective, we can see another way of structuring the operation. One that gets less publicity than the other ones, but that can have several advantages as we’ll see in just a moment: shifting the logic to the output iterator:

where `transform_f` is an output iterator that applies f and forwards this result to the `std::back_inserter`.

Note that with this approach the input range is simple (`strings`), the algorithm is simple too (`ranges::copy`) and the responsibility of applying `f` has been moved over to the output iterator.

Is this form helpful at all?

### The case for smart output iterators

Let’s take a case where standard algorithms aren’t practical to use: the case of “transform if” for example. This is a case where we’d like to apply a function to only the elements of a collection that satisfy a predicate. It is cumbersome to do with the STL because STL algorithms don’t chain up well:

So let’s say that the first way using STL algorithms is out. We’re left with two options:

• using ranges:
• using smart output iterators:

#### Smarter output iterators

Ranges are more and more the default solution in this case, and the direction that the STL is taking for the future. However, there are several reasons why it can be interesting to consider giving some responsibility to output iterators.

The first reason is that for the algorithms taking more than one range in input, for example `std::set_difference` and the other algorithms on sets, to my knowledge you can’t use traditional range adaptors to apply a transformation to the outputs of the algorithms. Indeed, ranges adaptors could modify either one or both of the input ranges:

But how could they apply a transformation on the outputs of the algorithms before sending them to the `outputIterator`, like a smart output iterator would do?

EDIT: in fact, the STL algorithms on sets are not such a good example of absolute necessity for smart output iterators, since range-v3 turns out to have view adaptors on sets algorithms. But there are still other cases where they are necessary, for instance algorithms that have several outputs. The STL only has `std::partition_copy`, but it’s very useful to extend the STL with more elaborate algorithms such as `set_segregate`, which has multiple outputs. In this case, smart output iterators become very handy.

A second reason is that smart output iterators could better express that some transformations are not semantically related to the algorithm, but rather to how the output collection stores its elements. To illustrate, let’s consider the case where the output container stores BigInts instead of ints. And this BigInt class doesn’t allow implicit conversion because its designer was wary of implicit conversions.

So our function `f` here would convert an int into a BigInt, simply by calling its constructor:

In this case, when reading the code we don’t really care about the fact that `f` is called. It has to be there, otherwise the code wouldn’t compile, but the meaningful part in the code is arguably the application of the predicate `isEven`. Shifting this application of `f` to the output iterator is a way to convey this message: this is just to make the outputs fit into the output container, much like `std::back_inserter` is.

So we could delegate the responsibility of the conversion to the output iterator side and mix both ranges and output iterators:

or we could just use the STL algorithm, here `copy_if`:

Another reason is a very practical one: smart output iterators are light-weight components that are relatively easy and quick to implement (much easier than ranges, I’ve tried to implement both) even in C++03. We see an example of that in the next section. So if you don’t have access to Boost Ranges or range-v3, they can be a practical way to make your code more concise. We’ll see an implementation in the next section of this article.

Finally, a last reason to consider smart output iterators is that they are a different way to go about structuring the call to an algorithm. And just for that reason, they can expand our view and give us more perspective on the topic of applying algorithms!

### Implementing smart output iterators

To follow up on the above example with BigInt, let’s make a generic output iterator that takes a function, applies it to the value it receives, and sends the result on to the iterator that it wraps (a `std::back_inserter` for example).

Here is a complete implementation, that we detail bit by bit just after:

Here is how this code works:

The generic elements of the smart iterator are:

• the function to apply,
• the iterator it wraps.

So let’s makes these two template parameters:

Let’s accept those two parameters in the constructor and store them in our smart iterator:

We need to implement the operators of an output iterator: `operator++` advances the underlying iterator. Advancing the underlying iterator is a no-op in `std::back_inserter`, but is necessary if the underlying output iterator is the `begin` of a container for example.

And like for `std::back_inserter` and `custom_inserter`, we use `operator*` to return the iterator itself and keep control of `operator=` to apply the function and pass the result to the underlying iterator:

That’s about it, except that the interface isn’t quite right: we would like an iterator that wraps over another iterator, and not one that also takes a function in its constructor:

Said differently, we’d like to partially apply the constructor with the transform function, here `make_bigint`, retrieve the object and give it an underlying iterator at a later time.

To simulate partial function application of a function in C++, we can use a function object:

Indeed, the parameters are applied in two phases: the first one in the constructor and the second one in the `operator()`.

Finally, to create a `transformer` we use a helper function to deduce the template parameter of the transform function:

This implementation is compatible with C++03 (and I didn’t see how to use lambdas to make it clearer anyway). Note though that in C++17 we wouldn’t need the `make_output_transformer` function thanks to the type deduction in class template constructors.

### Sweeping low-level operations under the rug

By using the smart output iterator we can now make the conversion to BigInt more discrete at the call site:

Will smart output iterators compete with ranges on all use cases? Certainly not. But to express that an operation is more closely related to the output container than to the algorithm itself, they can constitute an alternative worth having in our toolbox.

`output_transformer` and other smart output iterators are available in the smart-output-iterators GitHub repository.

Related articles:

Become a Patron!
Share this post!     Don't want to miss out ? Follow: