Making C++ Pipes Compatible with STL Algorithms

Published August 16, 2019

As we saw in the previous post, the Smart output iterators are now called Pipes.

Pipes allow to write this kind of code:

A >>= funnel
  >>= transform(f)
  >>= filter(p)
  >>= unzip(back_inserter(B),
            demux(back_inserter(C),
                  filter(q) >>= back_inserter(D),
                  filter(r) >>= back_inserter(E));

Which has the plumbing equivalent of this:

pipeline

However, like we required of smart output iterators, we still want pipes to have the same integration with STL algorithms, as output iterators:

std::set_difference(begin(X), end(X),
                    begin(Y), end(Y),
  transform(f)
  >>= filter(p)
  >>= unzip(back_inserter(B),
            demux(back_inserter(C),
                  filter(q) >>= back_inserter(D),
                  filter(r) >>= back_inserter(E));

The equivalent in plumbing could look like this:

pipes STL algorithm

Let’s see how to express this in code.

Output iterators

In the above example, the first pipe that is connected to STL algorithm std::set_difference is the transform pipe.

Here is its interface:

template<typename TransformFunctionTuple, typename... Iterators>
class output_transform_iterator
{
public:
    using iterator_category = std::output_iterator_tag;
    using value_type = void;
    using difference_type = void;
    using pointer = void;
    using reference = void;
    
    explicit output_transform_iterator(TransformFunctionTuple transformFunctionTuple, Iterators... iterators);
    output_transform_iterator& operator++();
    output_transform_iterator& operator++(int);
    output_transform_iterator& operator*();
    template<typename T>
    output_transform_iterator& operator=(T const& value);

private:
    std::tuple<Iterators...> iterators_;
    TransformFunctionTuple transformFunctionTuple_;
};

This has the typical look of an STL-compatible iterator. It starts with the aliases that the iterator must define, then defines the operators that allows the STL algorithm to write this code:

*out = value;
++out;

Just in case you’re wondering, the reason why transform takes several functions and several iterators is because it allows to apply several functions to its input and send the results to various outputs:

auto const multiply = transform([](int i) { return i*2; },
                                [](int i) { return i*3; },
                                [](int i) { return i*4; });

std::copy(begin(input), end(input),
            multiply(std::back_inserter(results1),
                     std::back_inserter(results2),
                     std::back_inserter(results3)));

Let’s refactor this class so that its interface looks more like one of a pipe than an output iterator.

From output iterator to pipe

Ideally, we’d like our interface to look like this:

template<typename TransformFunctionTuple, typename... OutputPipes>
class transform_pipe
{
public:
    template<typename T>
    void onReceive(T&& value);

    explicit output_transform_iterator(TransformFunctionTuple transformFunctionTuple, OutputPipes... outputPipes);

private:
    std::tuple< OutputPipes...> outputPipes_;
    TransformFunctionTuple transformFunctionTuple_;
};

Or so I think. If you think otherwise, I’d love to hear your ideas. If you’d like to see another interface, let’s discuss this in the comment section.

Of course, we’re not going to reach this exact interface, because the class still has to expose the necessary aliases and operators in order to be usable as the output iterator of an STL algorithm.

Our goal is rather to encapsulate and present them as an extension of the class.

And how do we add a feature to a class, at compile time? With the CRTP!

The CRTP base class

Let’s design the CRTP base class that contains the necessary interface to be compatible with the STL algorithm:

template<typename Derived>
struct OutputIteratorBase : crtp<Derived, OutputIteratorBase>
{
    using iterator_category = std::output_iterator_tag;
    using value_type = void;
    using difference_type = void;
    using pointer = void;
    using reference = void;
    
    Derived& operator++() { return this->derived(); }
    Derived& operator++(int){ ++this->derived(); return this->derived(); }
    Derived& operator*() { return this->derived(); }
    
    template<typename T>
    Derived& operator=(T&& input)
    {
        this->derived().onReceive(std::forward<T>(input));
        return this->derived();
    }
};

The above code uses the crtp helper, a base class for CRTP base classes in order to provide the derived member function. It avoids having to write the ugly static_cast<Derived&>(*this) all over the class.

This class contains the interface of an output iterator, with the aliases and operators, and it also implements this interface to connect it with the onReceive member function that we wanted for our pipe.

Now let’s use this base class in our pipe:

template<typename TransformFunctionTuple, typename... OutputPipes>
class transform_pipe : public OutputIteratorBase<transform_pipe<TransformFunctionTuple, OutputPipes...>>
{
public:
    template<typename T>
    void onReceive(T&& value);

    explicit output_transform_iterator(TransformFunctionTuple transformFunctionTuple, OutputPipes... outputPipes);

private:
    std::tuple< OutputPipes...> outputPipes_;
    TransformFunctionTuple transformFunctionTuple_;
};

We should be finished then, right?

Yes, except that… it doesn’t compile.

`operator=` and the CRTP are not friends

An STL algorithm calls the operator= of its output iterator with the value on which is it operating, which can be of any type. This is why the base class of our CRTP has a template operator=:

    template<typename T>
    Derived& operator=(T&& input)
    {
        this->derived().onReceive(std::forward<T>(input));
        return this->derived();
    }

But the output iterator we pass to the algorithm is the derived class in the CRTP (so transform_pipe), and not the base class.

The code of the algorithm therefore invokes the operator= of the transform_pipe, not the one of its CRTP base class. It is not written in the code of the class, but the compiler generates it for us. It is equivalent to writing:

transform_pipe& operator=(transform_pipe const& other) = default;
transform_pipe& operator=(transform_pipe&& other) = default;

But those operator=s don’t accept anything else than other transform_pipes, or anything that can be converted to transform_pipe. And as explained in Effective C++ item 33, they hide the member functions names of the same name coming from the base class.

Note that although the operator= has a different prototype, which wouldn’t be ambiguous if it was in the same class as the generated operator=s, the fact that they have the same name (“operator=”) is enough for the derived class to hide the base class’s methods.

And even if the generated implementation of the operator= in transform_pipe calls operator= on the base class, it is the operator= that takes an OutputIteratorBase that gets called, not the template one.

This issue of CRTP conflicting with the code generated by the compiler wouldn’t have happened with any other member function. This problem is specific to operator=, because it is the only named member function that the compiler generates automatically.

Bringing down `operator=`

If you know how to fix this elegantly, please let me know in a comment below. As my solution is not elegant.

The classical solution in the context of name hiding is to bring the base class member function into the scope of the derived class by using using:

using OutputIteratorBase<transform_pipe<TransformFunctionTuple, OutputPipes...>>::operator=;

This is not pretty. What’s more, it has to be public, because it is called by STL algorithms, which is code external to the class.

To mitigate this, we can put this extra line at the very end of the class, because no one except the compiler is interested in reading it:

template<typename TransformFunctionTuple, typename... OutputPipes>
class transform_pipe : public OutputIteratorBase<transform_pipe<TransformFunctionTuple, OutputPipes...>>
{
public:
    template<typename T>
    void onReceive(T&& value);

    explicit output_transform_iterator(TransformFunctionTuple transformFunctionTuple, OutputPipes... outputPipes);

private:
    std::tuple< OutputPipes...> outputPipes_;
    TransformFunctionTuple transformFunctionTuple_;

public: // but technical
    using OutputIteratorBase<transform_pipe<TransformFunctionTuple, OutputPipes...>>::operator=;
};

If you can see a better solution, I’d be grateful if you let me know.

Sending data to a pipe

So far we have focused on how a pipe would receive data from an STL algorithm. But how should a pipe send data to the one(s) after it in the pipeline?

One way could be to use the same syntax as an STL algorithm:

*out = value;
++out;

That’s what smart output iterators were doing. But with the new perspective of pipes, it seems weird to use this syntax to send a piece of data down a pipe.

Let’s introduce a function to wrap this syntax and send data to a pipe:

template<typename OutputIterator, typename T>
void send(OutputIterator& outputIterator, T&& value)
{
    *outputIterator = std::forward<T>(value);
    ++outputIterator;
}

transform_pipe can therefore call it this way:

send(outputPipe, f(input));

We could also have used onReceive directly in the implementation of send. But the above way ensures via code that pipes and STL algorithms use the exact same code to send data to a pipe.

More pipes

All the above code is available in the Github repo.

Now that the library has taken the new orientation of pipes, some components that were clumsy before will fall into place nicely, like the demux pipe. And we’ll also add more pipes, like switch_, tee, and others. I will talk about some of them in future posts.

And if you have an idea for a new pipe to be added, I’ll be glad to read your comments or PRs.

Finally, the library needs user feedback to grow. Would you like to try it out?