Combining Ranges and Smart Output Iterators

In our current stage of development of smart output iterators, we have:

• some iterators, such as filter, transform, unzip or demux,
• the possibility to combine them: filter(pred) >>= transform(f) >>= unzip(back_inserter(output1), back_inserter(output2))
• their usage as the output iterator of an STL algorithm:

std::copy(begin(inputs), end(inputs), transform(f) >>= back_inserter(outputs));

 

What we’re going to work on today is removing the call to std::copy to have a pipeline made of output iterators only. And once we get such a pipeline, we will plug it to ranges, in order to benefit from the expressiveness of both ranges and smart output iterators, in the same expression.

Note: it’s been a few posts that we’re exploring smart output iterators in detail. While this is a fascinating topic, I realize that some readers who may have joined us right in the middle of the adventure would appreciate a general overview on the topic. Just so you know, I’m planning to write such an overview in one of the next posts.

Hiding the call to std::copy

What would be great would be to pipe the contents of a collection directly into the first output iterator of the pipeline:

inputs >>= transform(f) >>= back_inserter(outputs));

Can you find a way to do this? If you can, please leave a comment below, because I couldn’t find how to implement operator>>= with the exact above syntax.

Indeed, the above expression implies that operator>>= has two meanings:

inputs >>= transform(f) >>= back_inserter(outputs));

• for the first >>= of the expression: send the data of inputs to transform(f) >>= back_inserter(outputs),
• for the second >>= of the expression: pass back_inserter(outputs) as the underlying of transform(f).

If you see how to achieve this, do leave a comment below!

In the meantime, I can think of two close syntaxes:

• use another right-associative operator for the connection of the inputs with the pipeline of output iterators:

inputs |= transform(f) >>= back_inserter(outputs)

• or add another level of indirection:

inputs >>= to_output >>= transform(f) >>= back_inserter(outputs)

 

I find the second option easier to remember. But I don’t have a strong opinion here. If you find that the first option looks better, please leave a comment below.

So let’s go and implement to_output.

Implementing to_output

Since operator>>= is right-associative, the >>= on the right of to_output will be called before the one on its left in the following expression:

inputs >>= to_output >>= transform(f) >>= back_inserter(outputs)
       ^^^           ^^^
       2nd           1st

This means that to_output starts by being associated to an output iterator. To implement this, we make to_output create a wrapper around the output iterator on its right.

Let’s first define a type for to_output itself:

struct to_output_t {};
const to_output_t to_output{};

We don’t need any data or behaviour for this type. We just need it to exist, in order to define an overload of operator>>= for it:

template<typename Iterator>
output_to_iterator<Iterator> operator>>=(to_output_t, Iterator iterator)
{
    return output_to_iterator<Iterator>(iterator);
}

output_to_iterator is the said wrapper type around the output iterator:

template<typename Iterator>
class output_to_iterator
{
public:
    explicit output_to_iterator(Iterator iterator) : iterator_(iterator) {}
    Iterator get() const { return iterator_; }
private:
    Iterator iterator_;
};

So to_output >>= transform(f) >>= back_inserter(outputs) returns an output_to_iterator.

We can now define the implementation of the second call to >>= (the one on the left): an overload of operator>>= that takes a range and a output_to_iterator:

template<typename Range, typename Iterator>
void operator>>=(Range&& range, output_to_iterator<Iterator> const& outputToIterator)
{
    std::copy(begin(range), end(range), outputToIterator.get());
}

This sends the data in the range to the wrapped output iterator.

With all this, the following two expressions are equivalent:

std::copy(begin(inputs), end(inputs), transform(f) >>= back_inserter(outputs));

and:

inputs >>= to_output >>= transform(f) >>= back_inserter(outputs)

Combining ranges and smart output iterators

Now to combine ranges, for example those in range-v3 as well as those coming in C++20 we need to do… nothing more!

Indeed, as we designed it, to_output can be combined with anything compatible with a begin and end functions. This can mean an STL container such as std::vector or std::map, a custom homemade collection, or any range created with range-v3 or presumably C++20 standard ranges.

Let’s illustrate this with an example: the fabulous biological phenomenon of the crossover. The crossover happens during the conception of a gamete, where the chromosomes coming from your dad mix up with their counterparts coming from your mom in order to create a unique combination of genes that define (half of) the DNA of your child (the other half comes from your partner’s crossover).

We’ll model the crossover the following way: each chromosome is a sequence of 25 genes, and a gene can have two values, or alleles: d for the allele of your dad’s chromosome and m for the allele of your mom’s. Our model selects for each gene the allele coming from Dad or Mom with a 50-50 probability, and assembles the results into two gametes. Those two gametes are therefore the recombination of the two initial chromosomes.

Here is how to code this by using ranges and smart output iterators:

auto const dadChromosome = Chromosome(25, Gene('d'));
auto const momChromosome = Chromosome(25, Gene('m'));

auto gameteChromosome1 = Chromosome{};
auto gameteChromosome2 = Chromosome{};

ranges::view::zip(dadChromosome, momChromosome) >>= to_output
                                                >>= output::transform(crossover)
                                                >>= output::unzip(back_inserter(gameteChromosome1),
                                                                  back_inserter(gameteChromosome2));

With crossover being defined like this:

std::pair<Gene, Gene> crossover(std::pair<Gene, Gene> const& parentsGenes)
{
    static auto generateRandomNumber = RandomNumberGenerator{0, 1};

    auto gametesGenes = parentsGenes;
    if (generateRandomNumber() == 1)
    {
        std::swap(gametesGenes.first, gametesGenes.second);
    }
    return gametesGenes;
}

We used:

• ranges to zip two collections together, because ranges are good for making several inputs enter a pipeline,
• the transform smart output iterator to perform the selection of alleles (we could just as well have used the transform range adaptor),
• the unzip smart output iterator to diverge into several directions, because smart output iterators are good for that.

If we print out the contents of the two gamete’s chromosomes we get (for one run):

dmmmdddddmdmmdmmmdmmddddd
mdddmmmmmdmddmdddmddmmmmm

The complete code example is here (the beginning of the code is a pull-in of library code, start by looking at the end of the snippet). And the smart output iterators library is available in its Github repo.

Ranges and smart output iterators are powerful libraries that have things in common (transform) and specificities (zip, unzip). Combining them allow to obtain even more expressive code than using them separately.

You will also like

• Unzipping a Collection of Tuples with the unzip Smart Output Iterator
• Introduction to the C++ Ranges Library
• The World Map of C++ STL Algorithms

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