How to do recursion based on tuple elements?

Question

I'm not sure if this is possible, but I would like to be able to recursively call a function based on the elements of a tuple. So for example a tuple such as std::tuple<int,float,double> should call expand_nested 3 times, and in turn invoke it's callback function with a parameter of type either int, float or double.

#include <tuple>
#include <vector>
#include <functional>

template <typename T>
struct tree_item
{
    T param;
    std::function<void(T)> callback;
};

template <typename... Ts>
struct tuple_node
{
    std::tuple<Ts...> tupl;
};

// recursion base case
template <typename T>
void expand_nested(tree_item<T> ti)
{
    ti.callback(ti.param);
}

// recursive function
template <typename T>
void expand_nested(tree_item<T> ti, tree_item<T> rest...)
{
    ti.callback(ti.param);
    expand_nested(ti, rest...);
}

template <typename... Ts>
void expand_root(tuple_node<Ts...> nodes)
{
    auto current = std::get<1>(nodes.tupl);
    auto rest = std::get<...>(nodes.tupl); // Made up syntax that doesn't work
    // How can I fill the "rest" variable with the remaining elements of the "nodes.tupl" tuple?

    expand_nested(current, rest...);
}

int main()
{
    tuple_node<tree_item<int>, tree_item<float>> nodes;

    tree_item<int> tree_int;
    tree_item<float> tree_float;
    tree_item<double> tree_double;

    tuple_node<tree_item<int>, tree_item<float>, tree_item<double>> node;
    node.tupl = std::make_tuple(tree_int, tree_float, tree_double);

    expand_root(nodes);
}

maybe https://stackoverflow.com/questions/1198260/how-can-you-iterate-over-the-elements-of-an-stdtuple — sp2danny, Jun 20 '20 at 18:19

rafix07 · Accepted Answer · 2020-06-20T18:30:45.283

Syntax for parameters pack in expand_nested should be:

template <typename T, typename ... Rest>
void expand_nested(tree_item<T> ti, tree_item<Rest>... rest)

This

ti.callback(ti.param);
expand_nested(ti, rest...);

will give you infinite recursion (you are calling the same function with the same number of arguments of the first call), it should look like:

template <typename T, typename ... Rest>
void expand_nested(tree_item<T> ti, tree_item<Rest>... rest)
{
    ti.callback(ti.param);    // process ti
    expand_nested(rest...);   // don't pass ti, pass only the rest to further processing
}

Since C++17 there is easy way to extract all elements of tuple - use std::apply:

template <typename... Ts>
void expand_root(tuple_node<Ts...> nodes)
{
    std::apply([](auto&... tupleItems){ 
        expand_nested(tupleItems...); }, nodes.tupl);
}

Full demo

score 1 · Answer 2 · answered Jun 20 '20 at 18:29

This is fairly easy in C++20:

#include <iostream>
#include <tuple>


template<typename T>
void func(T t)
{
    std::cout << t << std::endl;
}

int main()
{
    std::tuple<int,float,double> f{1,2,3};

    std::apply([]<typename ...Args>(Args && ...args)
           {
               (func(args), ...);
           }, f);
}

This requires a little bit more work, to support only C++11, or higher:

#include <iostream>
#include <tuple>
#include <utility>

template<typename T>
void func(T t)
{
    std::cout << t << std::endl;
}

template<typename T, size_t s, size_t n=0>
struct call_func {

    static void doit(T &t)
    {
        func(std::get<n>(t));

        call_func<T, s, n+1>::doit(t);
    }
};

template<typename T, size_t s>
struct call_func<T, s, s> {

    static void doit(T &t)
    {
    }
};

template<typename ...Args>
void do_callfunc(std::tuple<Args...> &t)
{
    call_func<std::tuple<Args...>, sizeof...(Args), 0>::doit(t);
}

int main()
{
    std::tuple<int,float,double> f{1,2,3};

    do_callfunc(f);
}

Wouldn't the first example work with c++17 if you just use `auto&&`? — super, Jun 20 '20 at 18:34

score 1 · Answer 3 · answered Jun 20 '20 at 18:45

I'm not sure if you need your expand functions for anything else, but from c++17 you can do this in a one-liner with std::apply.

#include <tuple>
#include <vector>
#include <functional>

template <typename T>
struct tree_item
{
    T param;
    std::function<void(T)> callback;
};

template <typename... Ts>
struct tuple_node
{
    std::tuple<Ts...> tupl;
};

int main()
{
    tuple_node<tree_item<int>, tree_item<float>> nodes;

    tree_item<int> tree_int;
    tree_item<float> tree_float;
    tree_item<double> tree_double;

    tuple_node<tree_item<int>, tree_item<float>, tree_item<double>> node;
    node.tupl = std::make_tuple(tree_int, tree_float, tree_double);

    std::apply([](auto&&... args){
        (args.callback(args.param), ...);
    }, node.tupl);
}

This is probably the most direct answer to the question title, but in my case I do need the extra step of calling `expand_nested` — mbl, Jun 20 '20 at 18:54

score 0 · Answer 4 · answered Jun 20 '20 at 18:38

Are you sure you need recursion?

If you can use C++17, what about template folding ?

template <typename... Ts, std::size_t ... Is>
void expand_root_helper (tuple_node<Ts...> nodes, std::index_sequence<Is...>)
 { ((void)std::get<Is>(nodes.tupl).callback(
             std::get<Is>(nodes.tupl).param), ...); }

template <typename... Ts>
void expand_root (tuple_node<Ts...> nodes)
 { expand_root_helper(nodes, std::index_sequence_for<Ts...>{}); }

In C++11/C++14 is a little more complicated (no template folding) but your helper function can emulate it as follows

template <typename... Ts, std::size_t ... Is>
void expand_root_helper (tuple_node<Ts...> nodes, std::index_sequence<Is...>)
 {
   using unused = int[];

   (void)unused { 0, ((void)std::get<Is>(nodes.tupl).callback(
                               std::get<Is>(nodes.tupl).param), 0)... };
 }

How to do recursion based on tuple elements?

4 Answers4