C++/C++11 - Switch statement for variadic templates?

Question

Let's say I have a few structs like this:

struct MyStruct1 {

    inline void DoSomething() {
        cout << "I'm number one!" << endl;
    }

};

struct MyStruct2 {

    static int DoSomething() {

        cout << "I'm the runner up." << endl;
        return 1;

    }

};

struct MyStruct3 {

    void (*DoSomething)();

    MyStruct3() {
        DoSomething = &InternalFunction;
    }

    static void InternalFunction() {
        cout << "I'm the tricky loser." << endl;
    }

};

As you can see, for all three structs, I can call DoSomething() on an object of that struct and have it work (though this is achieved differently for each struct):

MyStruct1 a;
MyStruct2 b;
MyStruct3 c;

a.DoSomething(); // works, calls Struct1's instance function
b.DoSomething(); // works, calls Struct2's static function, discards return value
c.DoSomething(); // works, calls Struct3's function pointer

Now, let's say I put an arbitrary selection of these structs into a tuple:

tuple<MyStruct2, MyStruct3, MyStruct2, MyStruct1> collection;

Let's also say that I want to take one of those elements and run its DoSomething() function based on an index that is determined at runtime. To achieve this, I could use a switch statement:

switch(index) {

case 0: get<0>(collection).DoSomething(); break;
case 1: get<1>(collection).DoSomething(); break;
case 2: get<2>(collection).DoSomething(); break;
case 3: get<3>(collection).DoSomething(); break;

}

This works fine and dandy, but gets very tedious, repetitive and error-prone when it needs to be done with multiple differently arranged (and potentially much longer than 4-element) tuples. It would be very handy if a switch statement could be automatically generated based on the number of elements in a variadic template. Pseudocode:

template <typename... T>
void DoSomethingByIndex(int index, tuple<T...>& collection) {

    switch(index) {

    STATIC_REPEAT(sizeof...(T), X) {
    case X: get<X>(collection).DoSomething(); break;
    }

    }

}

Is there any mechanism in C++11 that would allow me to achieve this? If not, I know I can undoubtedly hack together a solution with a list of function pointers within a template, but I'm just curious if something like this exists, since it would be better suited for my purposes. I'm sure a switch statement's compiler-generated jump list would be more efficient than my homemade function pointer solution as well.

I'm not sure I understand the need for a switch statement...why not just call get with the index and call `DoSomething()`? — Chad La Guardia, Sep 11 '11 at 23:00
Template arguments must be compile-time constants. Index is determined at runtime. — nonoitall, Sep 11 '11 at 23:02
I can conceive of other techniques using inheritance and a separate list of pointers to a base struct, but in this case I think their complexity and performance hit (although admittedly slight) would outweigh that of simply writing a template with a list of function pointers, which isn't too big of a deal. Mainly I'm just wondering if there's a silver bullet tucked away somewhere in C++11 that will offer awesome performance without me having to write anything. :-) — nonoitall, Sep 11 '11 at 23:23
have you thought of using `std::function` instead of raw function pointers? — Tony The Lion, Sep 11 '11 at 23:36

score 18 · Accepted Answer · answered Sep 12 '11 at 05:03

18

You can use an array to bridge compile-time and runtime: (ab)use variadic templates to statically initialize the array elements, and then index into the array with the runtime parameter. The tricky part is finding the right element type for the array. In addition since we need the template to be variadic on the tuple indices rather than on the tuple elements I'll be using my usual trick.

template<int... Indices>
struct indices {
    typedef indices<Indices..., sizeof...(Indices)> next;
};

template<int N>
struct build_indices {
    typedef typename build_indices<N - 1>::type::next type;
};

template<>
struct build_indices<0> {
    typedef indices<> type;
};

// No need to be variadic on the tuple elements as we don't care about them
// So I'm using perfect forwarding for the tuple
template<typename Tuple, int... Indices>
void
do_something_by_index(Tuple&& tuple, int index, indices<Indices...>)
{
    using std::get;

    typedef void (*element_type)(Tuple&&);
    static constexpr element_type table[] = {
        [](Tuple&& tuple)
        { get<Indices>(std::forward<Tuple>(tuple)).DoSomething(); }
        ...
    };

    table[index](std::forward<Tuple>(tuple));
}

// Proverbial layer of indirection to get the indices
template<typename Tuple>
void
do_something_by_index(Tuple&& tuple, int index)
{
    typedef typename std::decay<Tuple>::type decay_type;
    constexpr auto tuple_size = std::tuple_size<decay_type>::value;
    typedef typename build_indices<tuple_size>::type indices_type;

    do_something_by_index(std::forward<Tuple>(tuple), index, indices_type{});
}

answered Sep 12 '11 at 05:03

Luc Danton

34,649
6
70
114

4

Best use of pack expansion ever :-) – Kerrek SB Sep 12 '11 at 09:27
Interesting way to create a function pointer table! Uses a lot of features I wasn't aware of or wouldn't have thought of. G++ choked on using Indices with a lambda function ("parameter packs not expanded with '...'") but I got it working with a separate template function. (Any ideas on how to make it work with the lambda function?) I understand pretty much everything there, but I can't find any documentation on what std::decay does. What does it accomplish? – nonoitall Sep 13 '11 at 22:49
Dug through header files and have deduced that std::decay>::type basically just returns the 'naked' type, with no references, pointers, consts or volatiles attached. That right? – nonoitall Sep 14 '11 at 00:06
@nonoitall My snapshot of GCC 4.7 cannot deal with the expansion with the lambda either and I'm not too keen on checking whether I'm correct or the compiler is -- thankfully the workaround you found is acceptable to you. – Luc Danton Sep 14 '11 at 04:52
@nonoitall It's not true that `std::decay` removes everything (it doesn't remove pointers like you mention), what it does is 'mimic' value semantics in perfect forwarding contexts. Strictly speaking, I only needed `std::remove_reference` because `std::tuple_size` can deal with e.g. `const std::tuple`, but cannot deal with `std::tuple&` (but it's longer to type!). This is needed because the way perfect forwarding works, `Tuple` might end up as a reference type. – Luc Danton Sep 14 '11 at 04:53
@KhurshidNormuradov There is no `#include ` and no `main` function either -- the code is not meant to be run verbatim. – Luc Danton Sep 21 '13 at 10:48
@Luc Danton. Unpacking variadic templates out lambda expression is not allowed. – Khurshid Normuradov Sep 22 '13 at 18:04
1

In this case get<0>(collection).DoSomething() won't be inlined. I mean you store pointers to lambdas whereas switch statement allows compiler to inline everything. – 0x2207 Aug 26 '15 at 09:31

score 1 · Answer 2 · answered Sep 11 '11 at 23:50

1

Hmmm, I'm tempted to try something like this:

template<int N, typename ...Args>
struct call_N_helper
{
  static void call(const std::tuple<Args...> & t, int i)
  {
    if (i == N) std::get<N>(t).call();
    else call_N_helper<N-1, Args...>(t, i);
  }
};

template<typename ...Args>
struct call_N_helper<0, Args...>
{
  static void call(const std::tuple<Args...> & t, int i)
  {
    if (i == 0) std::get<0>(t).call();
  }
};

template<typename ...Args>
void call_N(const std::tuple<Args...> & t, int i)
{
  call_N_helper<sizeof...(Args), Args...>::call(t, i);
}

This is just an idea, untested and all.

answered Sep 11 '11 at 23:50

Kerrek SB

464,522
92
875
1,084

Would a compiler like g++ be likely to convert the if-else's into a switch statement and ultimately a jump table? – nonoitall Sep 12 '11 at 00:06
@nonoitall: Does it matter? Why do you care so much about the performance of this? A `std::vector>` would probably be virtually identical in speed. – Nicol Bolas Sep 12 '11 at 00:37
1

@nonoitall: Why not just test? Fire up the compiler and check the assembly output... – Kerrek SB Sep 12 '11 at 00:46
1

Doesn't look like it. Even with -O3 and over 30 elements in the tuple it still produces a series of compares proportionate to the number of elements. – nonoitall Sep 12 '11 at 05:44
1

@Nicol Bolas: It's more of curiosity than anything else. I just want to know if there's something both faster and more elegant than a hand-made function pointer table. Theoretically a switch statement should be, but does the syntax exist to create a variadic one? – nonoitall Sep 12 '11 at 05:48

C++/C++11 - Switch statement for variadic templates?

2 Answers2

Linked