The Demultiplexer Iterator: Routing Data to Any Numbers of Outputs
In a previous post, we explored the partition output iterator, that routes data into two directions according to a predicate: the elements that satisfy the predicate to one side, and those that don’t to another side:
auto const isEvenPartition = partition([](int n){ return n % 2 == 0; });
std::copy(begin(input), end(input), isEvenPartition(back_inserter(evenNumbers), back_inserter(oddNumbers)));
The above code sends the even numbers of inputs to evenNumbers and the odd ones to oddNumbers.
But what if we want to route data not just to two, but any number of outputs? This is a need that several developers expressed to me when using STL algorithms.
Let’s design an output iterator that can route data according to an arbitrary number of predicates: the demultiplexer output iterator.
Designing the interface
As usual when designing a component, we start by writing the desired code first, and then try to write an implementation behind that interface afterwards.
Our demux iterator needs to accommodate several predicates, as well as one destination output iterator for each one of the predicates. Here is one possibility of interface:
std::copy(begin(inputs), end(inputs),
demux(demux_if(predicate1).send_to(output1),
demux_if(predicate2).send_to(output2),
demux_if(predicate3).send_to(output3)));
If you can think of another interface that would look more natural, please leave a comment below.
Once we’ve implemented demux, it will be compatible with other smart output iterators to create combinations:
std::copy(begin(inputs), end(inputs),
demux(demux_if(predicate1).send_to(transform(f) >>= back_inserter(v1)),
demux_if(predicate2).send_to(filter(p) >>= back_inserter(v2)),
demux_if(predicate3).send_to(begin(v3))));
Now that we have several predicates, a new question arises, that didn’t exist for the partition iterator: what to do if a piece of data satisfies several predicates?
I can see two options to answer that question: 1) sending the data to all the corresponding outputs, or 2) sending it to the first one that matches, in their order of declaration in the demux iterator.
We’ll go for the second one, because it is arguably more natural to think that each piece of data goes into one direction. I’d love to hear your opinion on this question, so please leave a comment if you have one.
Another new question arises with this iterator: what should we do if a piece of data doesn’t satisfy any predicate? Let’s decide that in that case, we won’t send that data to any branch.
Now that we agreed on what the resulting usage should look like, let’s code it up!
Implementing the demux iterator
Like for all output iterators, our operator* and operator++ don’t do much:
output_demux_iterator& operator++() { return *this; }
output_demux_iterator& operator++(int){ ++*this; return *this; }
output_demux_iterator& operator*(){ return *this; }
Returning *this in operator* is the usual trick to keep control on what’s happening when an STL algorithm typically calls operator= afterwards.
The main logic lies in operator=. We want operator= to take a value and send it to the right output according to its predicate.
That previous sentence suggests that the demux iterator needs to have access to the outputs as well as their corresponding predicates.
To implement this, let’s first define an abstraction on the association of an output and a predicate, and call that a branch:
template<typename Predicate, typename Iterator>
struct demux_branch
{
Predicate predicate;
Iterator iterator;
demux_branch(Predicate predicate, Iterator iterator) : predicate(predicate), iterator(iterator) {}
};
In order for the demux iterator to have access to the branches, let’s store them as members:
template<typename... DemuxBranches>
class output_demux_iterator
{
public:
explicit output_demux_iterator(DemuxBranches const&... demuxBranches) : branches_(std::make_tuple(demuxBranches...)) {}
// ...
private:
std::tuple<DemuxBranches...> branches_;
};
Routing values
The complexity lies in how to implement the operator=, that is the routing of a given value into the right branch.
template<typename T>
output_demux_iterator& operator=(T&& value)
{
What we want to do is to test the predicate of each successive branch on the value, send it to the first one that returns true, and stop testing afterwards.
The branches are stored into a std::tuple. So we’d like to iterate over the tuple, find the first element satisfying the predicate, and perform the action of sending data to the corresponding underlying iterator.
Said differently, we’d like to perform a find_if on the tuple, and perform an action at the returned position (if it is indeed inside of the tuple).
This is exactly what we’ve explored in the STL-like algorithms on tuples. Let’s reuse find_if, that returns the index of the first element of the tuple that matches the predicate, and perform, that applies a function on the i-th element of the tuple, i being determined at runtime:
template<typename T>
output_demux_iterator& operator=(T&& value)
{
auto const firstSatisfyingBranchIndex = find_if(branches_, [&value](auto&& branch){ return branch.predicate(value); });
if (firstSatisfyingBranchIndex < sizeof...(DemuxBranches))
{
perform(branches_, firstSatisfyingBranchIndex, [&value](auto&& branch){ *branch.iterator = value; ++ branch.iterator; });
}
return *this;
}
As decided up above, if no element satisfies the predicate, we don’t send the data anywhere.
Matching the desired usage
Now that we have the iterator implemented, we need to put in place the machinery to instantiate it, with demux_if and send_to as in the desired usage at the opening of the post:
std::copy(begin(inputs), end(inputs),
demux(demux_if(predicate1).send_to(output1),
demux_if(predicate2).send_to(output2),
demux_if(predicate3).send_to(output3)));
The iterator can be constructed with a parameters pack of demux_branches. So demux_if needs to create an object that has a method send_to that takes an iterator and returns a demux_branch. Let’s call this intermediary object Demux_if:
template<typename Predicate>
class Demux_if
{
public:
explicit Demux_if(Predicate predicate) : predicate_(std::move(predicate)) {}
template<typename Iterator>
auto send_to(Iterator&& iterator) const
{
return demux_branch<Predicate, Iterator>(predicate_, std::forward<Iterator>(iterator));
}
private:
Predicate predicate_;
};
Before C++17 and its template type deduction for constructors, we need demux_if to be a separate function that instantiate the Demux_if with the right template parameter:
template<typename Predicate>
Demux_if<Predicate> demux_if(Predicate&& predicate)
{
return Demux_if<Predicate>(std::forward<Predicate>(predicate));
}
In C++17, demux_if can be the intermediary object itself that we called Demux_if (with a capital D).
Similarly, in C++17 demux can be the iterator that we called output_demux_iterator. Before C++17, it has to be a function that instantiates the iterator with the right template parameters:
template<typename... DemuxBranches>
output_demux_iterator<DemuxBranches...> demux(DemuxBranches const&... demuxBranches)
{
return output_demux_iterator<DemuxBranches...>(demuxBranches...);
}
Usage
Let’s try out our new demultiplexer iterator:
std::vector<int> numbers = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
std::vector<int> multiplesOf3;
std::vector<int> multiplesOf2Only;
std::vector<int> multiplesOf1Only;
std::copy(begin(numbers), end(numbers),
demux(demux_if( [](int n){ return n % 3 == 0; } ).send_to(back_inserter(multiplesOf3)),
demux_if( [](int n){ return n % 2 == 0; } ).send_to(back_inserter(multiplesOf2Only)),
demux_if( [](int n){ return n % 1 == 0; } ).send_to(back_inserter(multiplesOf1Only)) ));
If we print the contents of the output collections:
std::cout << "Muliples of 3:\n";
for (auto const& number : multiplesOf3)
std::cout << number << ' ';
std::cout << "\nMuliples of 2 only:\n";
for (auto const& number : multiplesOf2Only)
std::cout << number << ' ';
std::cout << "\nMuliples of 1 only:\n";
for (auto const& number : multiplesOf1Only)
std::cout << number << ' ';
We get the following output:
Muliples of 3: 3 6 9 Muliples of 2 only: 2 4 8 10 Muliples of 1 only: 1 5 7
Now that demux is part of the smart output iterators library, it can also be combined with all the other iterators: transform, filter, partition, etc.
The code is available on Github. If you see other output iterators that could be useful, please leave a comment below!
You will also like
- Algorithms on Tuples
- Partitioning Data with Output Iterators in C++
- Smart Output Iterators: A Symmetrical Approach to Range Adaptors
- Introduction to the C++ Ranges Library
Share this post!
