STL Algorithms on Tuples

When you manipulate a collection of objects in C++–which is quite a common thing to do when programming in C++–STL algorithms are your loyal companions to perform operations with expressive code.

But the STL algorithms, shipped in the standard library with C++, only apply to collections that are filled at runtime, during the execution of a program (or in C++20, during the execution of constepxr code during compilation). This include the ubiquitous std::vector and std::map.

But STL algorithms don’t operate on std::tuples.

However, it could be useful to iterate over the elements of a tuple, at runtime, and perform transformations or extract information, like STL algorithms do. We will see in detail a situation where this is useful with the demux output iterator, in a future post.

Can we design algorithms that are do what STL algorithms do, but on the contents of std::tuples instead of std::vectors and std::maps?

It turns out we can.

for_each: applying a function on each element of a std::tuple

The most basic algorithm consists in applying a given function (or function object) to each element of the collection successively. This is std::for_each.

To perform the equivalent of a std::for_each on a tuple, the most direct solution is probably to use Boost Hana, that provides boost::hana::for_each.

For example, to multiply by 2 each element of a tuple of ints containing 1, 2 and 3 we’d write:

auto myTuple = std::make_tuple(1, 2, 3);

boost::hana::for_each(myTuple, [](int& n) { n *= 2; });

If we print what the tuple contains, for example with the following code:

boost::hana::for_each(myTuple, [](int n) { std::cout << n << '\n'; });

We get the following output:

2
4
6

See the complete code example here.

Heterogeneous containers

Note that one of the forces of a tuple is that it can contain various types at the same time, for example:

auto myTuple = std::make_tuple(1, std::string("2"), std::string("3"));

This tuple is of type std::tuple<int, std::string, std::string>. In order to operate on each type of elements, we can pass a function object that covers the different cases:

struct Times2
{
    void operator()(int& n)
    {
        n *= 2;
    }
    void operator()(std::string& s)
    {
        s = std::to_string(2 * std::stoi(s));
    }
};

boost::hana::for_each(myTuple, Times2{});

Printing the contents of the tuple then still gives:

2
4
6

See the complete code example here.

If you don’t have Boost Hana

Boost Hana is a pretty cool library, but it has a pre-requisite: having access to Boost. While this is not problem for some projects, some codebases out there don’t have access to Boost.

Luckily, it turns out that we can code up an equivalent of Hana’s for_each that only relies on standard components and without too much difficulty.

The easiest solution to code would be to rely on compile time recursion: for_each (or rather, a intermediary function) would take an integral template parameter I, call the function on the I-th element of the tuple (accessible with std::get<I>) and recurse by calling the same code with I-1.

But using compile-time recursion on tuples is generally a bad practice, because it is inefficient in terms of compilation time.

A trick to avoid recursion is to use the comma operator. In fact, this is exactly the same mechanism that we saw in for_each_arg, that applies a function to each of the argument we pass to it:

template<class F, class...Args>
constexpr F for_each_arg(F f, Args&&...args) {
  std::initializer_list<int>{((void)f(std::forward<Args>(args)), 0)...};
  return f;
}

If the above code looks like a magical incantation to you, get a little refresher on for_each_arg.

To perform the same type of treatment on a tuple, we need to adapt the iteration over the pack of arguments into an iteration over the pack of elements inside the tuple.

As with many operations on tuples, this works in two phases:

• create a variadic pack of consecutive integrals: 0, 1, 2, 3, … This relies on std::make_index_sequence
• use this pack to fetch the consecutive data of the tuple

The first step can be implemented like this:

template <class Tuple, class F>
constexpr F for_each(Tuple&& t, F&& f)
{
    return for_each_impl(std::forward<Tuple>(t), std::forward<F>(f),
                         std::make_index_sequence<std::tuple_size<std::remove_reference_t<Tuple>>::value>{});
}

(Note that we use a template type for the tuple in order to be generic and allow for std::pair and std::array on the top of std::tuple, and in tuple_size we remove the reference on the tuple, because there is no such thing as a tuple_size on a reference of a tuple.)

The second phase consists in implementing the for_each_impl that the above code is calling:

template <class Tuple, class F, std::size_t... I>
constexpr F for_each_impl(Tuple&& t, F&& f, std::index_sequence<I...>)
{
    return (void)std::initializer_list<int>{(std::forward<F>(f)(std::get<I>(std::forward<Tuple>(t))),0)...}, f;
}

It relies exactly on the same trick as for_each_arg.

for_each2

for_each2 is an extended version of for_each, that takes two tuples in input, and a function that takes two elements:

auto tuple1 = std::make_tuple(1, std::string{"two"});
auto tuple2 = std::make_tuple(std::string{"one"}, 2);

for_each2(tuple1, tuple2, [](auto&& i, auto&& s){ std::cout << i << '-' << s << '\n'; });

Here is its implementation:

template <class Tuple1, class Tuple2, class F, std::size_t... I>
F for_each2_impl(Tuple1&& t1, Tuple2&& t2, F&& f, std::index_sequence<I...>)
{
    return (void)std::initializer_list<int>{(std::forward<F>(f)(std::get<I>(std::forward<Tuple1>(t1)), std::get<I>(std::forward<Tuple2>(t2))),0)...}, f;
}

template <class Tuple1, class Tuple2, class F>
constexpr decltype(auto) for_each2(Tuple1&& t1, Tuple2&& t2, F&& f)
{
    returnfor_each2_impl(std::forward<Tuple1>(t1), std::forward<Tuple2>(t2), std::forward<F>(f),
                         std::make_index_sequence<std::tuple_size<std::remove_reference_t<Tuple1>>::value>{});
}

transform: applying a function and output new elements

std::transform is a central STL algorithm that applies a function to each element of a collection and outputs the results of those applications into an output collection.

Let’s code up the equivalent for tuples: a function that takes a tuple and a function, and returns another tuple, containing the results of applying the function to the elements of the first tuple:

template<typename...Ts, typename Function, size_t... Is>
auto transform_impl(std::tuple<Ts...> const& inputs, Function function, std::index_sequence<Is...>)
{
    return std::tuple<std::result_of_t<Function(Ts)>...>{function(std::get<Is>(inputs))...};
}

template<typename... Ts, typename Function>
auto transform(std::tuple<Ts...> const& inputs, Function function)
{
    return transform_impl(inputs, function, std::make_index_sequence<sizeof...(Ts)>{});
}

Note how we used C++11’s std::result_of to create the type of the result tuple.

find_if: locating an element in a std::tuple

A classical operation that comes up all the time when manipulating collections is searching something in them. For std::vector, the STL offers amongst other things std::find that searches for a value, and the more generic std::find_if that searches for the first element that satisfies a predicate.

Let’s implement a find_if on a std::tuple. For example, let’s locate the first element of the tuple that is even.

First off, let’s note that this is in general not possible with Boost Hana because, as far as I understand, Boost Hana not made for this. To understand what Boost Hana is made for, have a look at the note on “C++ computational quadrants” in the introduction of Boost Hana.

So for this–as far as I’m aware of–we’re on our own.

In order to design a find_if on tuple, let’s first decide on the interface, like we usually do. The main question resides on the return type of find_if. In the STL, std::find_if returns an iterator. But for our case, there is no such thing as an iterator on tuples.

To go for a simple solution, let’s just return the index of the first element that satisfies the predicate. And if no element satisfies the predicate, we’ll return the size of the tuple. This is in the same spirit as the STL’s std::find_if that returns the end iterator if no element of the searched collection satisfies the predicate.

Implementation

To implement find_if on a tuple, we can reuse the for_each on tuples from above:

template<typename Tuple, typename Predicate>
constexpr size_t find_if(Tuple&& tuple, Predicate pred)
{
    size_t index = std::tuple_size<std::remove_reference_t<Tuple>>::value;
    size_t currentIndex = 0;
    bool found = false;
    for_each(tuple, [&](auto&& value)
                    {
                        if (!found && pred(value))
                        {
                            index = currentIndex;
                            found = true;
                        }
                        ++currentIndex;
                    });
    return index;
}

We iterate on the tuple by testing for the predicate and incrementing a currentIndex, until we encounter an element that does satisfy the predicate. Then we set the found flag and stop testing for the predicate.

If no element satisfy the predicate, we return  the tuple_size of the tuple (of which we’ve remove the potential references because, as mentioned above, there is no such thing as the tuple_size of a reference of a tuple).

Note that when using the STL a good practice is to avoid storing state in function objects (because with the STL, stateless is stressless), but this is what we do here, because we don’t have iterators on tuples. If you see other ways to implement find_if on tuples, please let me know in the comment section!

Accessing a tuple element at runtime

After performing our find_if on tuple, we get an index representing the position of an element:

auto firstEvenIndex = find_if(myTuple, [](int n){ return n % 2 == 0; });

If all you need is to use firstEvenIndex, then this is enough.

But a natural thing to do would be to access the corresponding element in the tuple. However we can’t just use std::get:

std::cout << std::get<i>(myTuple) << '\n';

Indeed, std::get takes a template parameter, so it has to be known at compile-time.

One solution is to declare myTuple and firstEvenIndex  constexpr:

constexpr auto myTuple = std::make_tuple(1, 2, 3);

constexpr auto firstEvenIndex = find_if(myTuple, [](int n){ return n % 2 == 0; });

std::cout << std::get<firstEvenIndex>(myTuple) << '\n';

This compiles, runs, and prints:

2

But if the data in the tuple is determined at runtime you can’t declare it constexpr. So we need a way to access the i-th element of a tuple at runtime.

Accessing a tuple element at runtime

To access the i-th element of a tuple at runtime we can once more rely on for_each:

template<typename Tuple, typename Action>
void perform(Tuple&& tuple, size_t index, Action action)
{
    size_t currentIndex = 0;
    for_each(tuple, [action = std::move(action), index, &currentIndex](auto&& value)
                    {
                        if (currentIndex == index)
                        {
                            action(std::forward<decltype(value)>(value));
                        }
                        ++currentIndex;
                    });
}

This function uses for_each to iterate over the tuple while incrementing a currentIndex, and performs the desired action when it reaches the desired index. This action could consist in simply retrieving the data, or doing something else with it.

all_of, any_of, none_of: checking the tuple with a predicate

In the STL, it is easy to implement all_of, any_of and none_of by using std::find_if: just check if the returned value is the end of the passed range:

template<class InputIt, class UnaryPredicate>
bool all_of( InputIt first, InputIt last, UnaryPredicate p )
{
    return std::find_if(first, last, std::not_fn(p)) == last;
}

template<class InputIt, class UnaryPredicate>
bool none_of( InputIt first, InputIt last, UnaryPredicate p )
{
    return std::find_if(first, last, p) == last;
}

template<class InputIt, class UnaryPredicate>
bool none_of( InputIt first, InputIt last, UnaryPredicate p )
{
    return !std::none_of(first, last, p);
}

Similarly, we can implement an any_of algorithm for tuples based on the above find_if:

template<typename Tuple, typename Predicate>
bool all_of(Tuple&& tuple, Predicate pred)
{
    return find_if(tuple, std::not_fn(pred)) == std::tuple_size<std::decay_t<Tuple>>::value;
}

template<typename Tuple, typename Predicate>
bool none_of(Tuple&& tuple, Predicate pred)
{
    return find_if(tuple, pred) == std::tuple_size<std::decay_t<Tuple>>::value;
}

template<typename Tuple, typename Predicate>
bool any_of(Tuple&& tuple, Predicate pred)
{
    return !none_of(tuple, pred);
}

There are a ton more of STL-like algorithms on tuples that we could design, and perhaps we’ll dig more into this subject in the future. For the time being we have everything we need to implement the demux output iterator, which we’ll explore soon in a future post.

In the meantime, all your comments and suggestions are welcome!

You will also like

• for_each_arg: Applying a Function to Each Argument of a Function in C++
• The Demultiplexer Iterator: Routing Data to Any Numbers of Outputs
• The World Map of C++ STL Algorithms
• STL Function objects: Stateless is Stressless

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