C++11 way to index tuple at runtime without using switch

Question

I have a piece of c++11 code similar like below:

switch(var) {
   case 1: dosomething(std::get<1>(tuple));
   case 2: dosomething(std::get<2>(tuple));
   ...
}

Is there any way to remove this large switch ? Note that get<var> does not work because var is not constant, but I know var is in small range i.e. (0-20).

Note that the point here is to avoid using an array that causes an array lookup...

EDIT:

well on the issue of performance, there is a discussion Performance of array of functions over if and switch statements

For my own purpose, I do not argue which one is better.

Sw

Yes, use a vector. The title of your question is misleading. You don't know the value of var at compile time. – Farlie

You seem to be asking how to index a tuple at runtime. – Atomizer

Have you made any measurements suggesting this change in your code would be worthwhile? I'd think an array lookup is almost certainly faster than 256 separate branches where the CPU cannot accurately predict which branch will be taken. – Reinhold

This is what I've done before: stackoverflow.com/questions/2873802/… – Linkman

@DrewDormann yes, indeed, changed my title to make it clearer – Sw

Does your tuple contain different types? Is doSomething overloaded for all the types, or are implicit conversions expected? – Atomizer

@DrewDormann It can have different type, by just having them templated right ? So let's assume some implicit conversion. – Sw

@Sw I hardly doubt that this will improve your performance in any way. It takes the CPU the same amount of time to fetch the data from the touple and the array. – Lewison

Oh noes, an array lookup! It's only literally one of the fastest operations it's possible to perform. – Indevout

possible duplicate of (C++) Feed template function element from tuple at runtime? – Rinaldo

Use an array. The link you added refers to array of pointers to functions vs call a function depending on a switch. Here you want to call the same function with different values, there is no reason to not use an array. – Inhospitality

Possible duplicate of How to get the i-th element from an std::tuple when i isn't know at compile-time? – Penology

Answer 1

Here's a version that doesn't use an index sequence:

template <size_t I>
struct visit_impl
{
    template <typename T, typename F>
    static void visit(T& tup, size_t idx, F fun)
    {
        if (idx == I - 1) fun(std::get<I - 1>(tup));
        else visit_impl<I - 1>::visit(tup, idx, fun);
    }
};

template <>
struct visit_impl<0>
{
    template <typename T, typename F>
    static void visit(T& tup, size_t idx, F fun) { assert(false); }
};

template <typename F, typename... Ts>
void visit_at(std::tuple<Ts...> const& tup, size_t idx, F fun)
{
    visit_impl<sizeof...(Ts)>::visit(tup, idx, fun);
}

template <typename F, typename... Ts>
void visit_at(std::tuple<Ts...>& tup, size_t idx, F fun)
{
    visit_impl<sizeof...(Ts)>::visit(tup, idx, fun);
}

DEMO

Hob

Nice, it didn't occur to me to use the tuple size as the range of indices ... doh. – Ectoparasite

Nice but I think the demo is only working for c++14, something is wrong with c++11 ? – Sw

@Sw The generic lambda [](auto v) {...} is a C++14 feature. You could write a generic functor instead: struct F { template <class T> operator()(T v) const {...} }; F doSomething; – Hob

BTW, the DEMO provided with this answer can also work with an arbitrary integer got from stdin, for example (and therefore is not known at compile time). ideone.com/ExUbjK – Marielamariele

how does this work? how does the compiler know when to stop generating the struct at compile time? how does it know when idx == I-1 at compile time? – Dissolve

@Prith It stops generating when the recursive template instantiation reaches the visit_impl<0> specialization. And it doesn't know when idx == I-1 at compile time; that's the point. The question is about indexing a tuple at runtime. If I were known at compile time, we could just use std::get<I>. – Hob

@Hob oh I see, so it keeps generating till it gets to visit_impl<0>. I wasnt sure about that, thank you for clearing up the confusion. – Dissolve

Thanks for this answer. I'm using a modified version of your answer to access a parameter pack using a runtime index, and it's incredibly fast. – Greenhorn

Answer 2

Here's an unreadably over-generic implementation without recursion. I don't think I'd use this in production - it's a good example of write-only code - but it's interesting that it can be done. (DEMO):

#include <array>
#include <cstddef>
#include <initializer_list>
#include <tuple>
#include <iostream>
#include <type_traits>
#include <utility>

template <std::size_t...Is> struct index_sequence {};

template <std::size_t N, std::size_t...Is>
struct build : public build<N - 1, N - 1, Is...> {};

template <std::size_t...Is>
struct build<0, Is...> {
    using type = index_sequence<Is...>;
};

template <std::size_t N>
using make_index_sequence = typename build<N>::type;

template <typename T>
using remove_reference_t = typename std::remove_reference<T>::type;

namespace detail {
template <class Tuple, class F, std::size_t...Is>
void tuple_switch(const std::size_t i, Tuple&& t, F&& f, index_sequence<Is...>) {
  [](...){}(
    (i == Is && (
       (void)std::forward<F>(f)(std::get<Is>(std::forward<Tuple>(t))), false))...
  );
}
} // namespace detail

template <class Tuple, class F>
void tuple_switch(const std::size_t i, Tuple&& t, F&& f) {
  static constexpr auto N =
    std::tuple_size<remove_reference_t<Tuple>>::value;

  detail::tuple_switch(i, std::forward<Tuple>(t), std::forward<F>(f),
                       make_index_sequence<N>{});
}

constexpr struct {
  template <typename T>
  void operator()(const T& t) const {
      std::cout << t << '\n';
  }
} print{};

int main() {

  {
    auto const t = std::make_tuple(42, 'z', 3.14, 13, 0, "Hello, World!");

    for (std::size_t i = 0; i < std::tuple_size<decltype(t)>::value; ++i) {
      tuple_switch(i, t, print);
    }
  }

  std::cout << '\n';

  {
    auto const t = std::array<int, 4>{{0,1,2,3}};
    for (std::size_t i = 0; i < t.size(); ++i) {
      tuple_switch(i, t, print);
    }
  }
}

Mishandle

Nice use of the… let's call it the empty variadic lambda pack expansion idiom. Not so hard to read I think; perfect forwarding exacts the greatest cost on readability. – Hob

Very nice! But don't you want a cast-to-void for the comma operator issue? – Paulita

@Sw Sorry, I was lazy. I used C++14's integer_sequence and remove_reference_t in the implementation, and a generic lambda in the demo code. There it is in just C++11. – Mishandle

Answer 3

No need to get all cray cray in c++17.

// Calls your func with tuple element.
template <class Func, class Tuple, size_t N = 0>
void runtime_get(Func func, Tuple& tup, size_t idx) {
    if (N == idx) {
        std::invoke(func, std::get<N>(tup));
        return;
    }

    if constexpr (N + 1 < std::tuple_size_v<Tuple>) {
        return runtime_get<Func, Tuple, N + 1>(func, tup, idx);
    }
}

And runtime tuple_element for fun.

// Calls your func with a pointer to the type.
// Uses a pointer so the element is not initialized.
template <class Tuple, class Func, size_t N = 0>
void runtime_tuple_element(Func func, size_t idx) {
    if (N == idx) {
        std::tuple_element_t<N, Tuple>* ptr = nullptr;
        std::invoke(func, ptr);
        return;
    }

    if constexpr (N + 1 < std::tuple_size_v<Tuple>) {
        return runtime_tuple_element<Tuple, Func, N + 1>(func, idx);
    }
}

Carleecarleen

slick. i didn't know about these features yet. btw if you put the constexpr condition at the start of the function you can throw an error for out of range indices. – Hone

Answer 4

It's possible but it's pretty ugly:

#include <tuple>
#include <iostream>

template<typename T>
void doSomething(T t) { std::cout << t << '\n';}

template<int... N>
struct Switch;

template<int N, int... Ns>
struct Switch<N, Ns...>
{
  template<typename... T>
    void operator()(int n, std::tuple<T...>& t)
    {
      if (n == N)
        doSomething(std::get<N>(t));
      else
        Switch<Ns...>()(n, t);
    }
};

// default
template<>
struct Switch<>
{
  template<typename... T>
    void operator()(int n, std::tuple<T...>& t) { }
};

int main()
{
  std::tuple<int, char, double, int, int, const char*> t;
  Switch<1, 2, 4, 5>()(4, t);
}

Just list each constant that would have been a case label in the original switch in the template argument list for the Switch specialization.

For this to compile, doSomething(std::get<N>(t)) must be a valid expression for every N in the argument list of the Switch specialization ... but that's true of the switch statement too.

For a small number of cases it compiles to the same code as a switch, I didn't check if it scales to large numbers of cases.

If you don't want to type out every number in Switch<1, 2, 3, 4, ... 255> then you could create a std::integer_sequence and then use that to instantiate the Switch:

template<size_t... N>
Switch<N...>
make_switch(std::index_sequence<N...>)
{
  return {};
}

std::tuple<int, char, double, int, int, const char*> t;
make_switch(std::make_index_sequence<4>{})(3, t);

This creates a Switch<0,1,2,3> so if you don't want the 0 case you'd need to manipulate the index_sequence, e.g. this chops the zero off the front of the list:

template<size_t... N>
Switch<N...>
make_switch(std::index_sequence<0, N...>)
{
  return {};
}

Unfortunately GCC crashes when trying to compile make_index_sequence<255> as it involves too much recursion and uses too much memory, and Clang rejects it by default too (because it has a very low default for -ftemplate-instantiation-depth) so this isn't a very practical solution!

Ectoparasite

yeah.. pretty ugly, is there away to remove the need for specifying the number in the Switch ? since I know my value is within a range. – Sw

Heh, is the crash a sign of the solution not being practical or of QoI issues with libstdc++'s make_index_sequence? ;) IIRC there's a log N implementation... – Undergo

@Undergo heh, partly my naïve implementation in libstdc++ and partly limitations of G++ ... but it's a pretty bonkers template instantiation anyway. I think I'd probably just use a code generator to spam out the case statements if it was me. I'm still holding out for a compiler intrinsic that will make the log N implementation unnecessary. – Ectoparasite

Answer 5

Here is C++17 solution without compile-time recursion (which is bad because it degrades your compile time) and without switch-case:

template<typename TPred, typename ...Ts, size_t ...Is>
void invoke_at_impl(std::tuple<Ts...>& tpl, std::index_sequence<Is...>, size_t idx, TPred pred)
{
    ((void)(Is == idx && (pred(std::get<Is>(tpl)), true)), ...);
    // for example: std::tuple<int, float, bool> `transformations` (idx == 1):
    //
    // Is... expansion    -> ((void)(0 == idx && (pred(std::get<0>(tpl)), true)), (void)(1 == idx && (pred(std::get<1>(tpl)), true)), (void)(2 == idx && (pred(std::get<2>(tpl)), true)));
    //                    -> ((void)(false && (pred(std::get<0>(tpl)), true)), (void)(true && (pred(std::get<1>(tpl)), true)), (void)(false && (pred(std::get<2>(tpl)), true)));
    // '&&' short-circuit -> ((void)(false), (void)(true && (pred(std::get<1>(tpl)), true)), (void)(false), true)));
    //
    // i.e. pred(std::get<1>(tpl) will be executed ONLY for idx == 1
}

template<typename TPred, typename ...Ts>
void invoke_at(std::tuple<Ts...>& tpl, size_t idx, TPred pred)
{
    invoke_at_impl(tpl, std::make_index_sequence<sizeof...(Ts)>{}, idx, pred);
}

Several notes here:

1. You CAN achieve same result in C++11 but instead of using C++17 fold-expressions you should use well-known 'hack' with local array (by expanding a pack inside array's initialization list). Something like:

   std::array<bool, sizeof...(Ts)> arr = { ((Is == idx && (pred(std::get<Is>(tpl)), true)), ...) };

2. We are using comma-operator for both Is... pack-expansion AND pred execution, i.e all operands of the comma-operator will be executed and the result of the whole comma-expression is the result of the last operand.

3. We are casting each operand to void in order to silence compiler (unused expression value or something like this)

Sorghum

Can also get rid of index_requence and use a local counter incremented on each iteration. – Joeyjoffre

@Joeyjoffre I believe index_sequence cannot be avoided - the purpose on index_sequence here is to expand tuple<Ts...> during compile-time – Sorghum

Right. I was probably thinking about putting it in std::apply. – Joeyjoffre

Answer 6

I know this thread is quite old, but i stumbled across it in my attempt to replace a virtual dispatch through a static one in my code base.

In contrast to all solutions presented so far this one uses a binary search instead of a linear search, so in my understanding it should be O(log(n)) instead of O(n). Other than that it is just a modified version of the solution presented by Oktalist

#include <tuple>
#include <cassert>

template <std::size_t L, std::size_t U>
struct visit_impl
{
    template <typename T, typename F>
    static void visit(T& tup, std::size_t idx, F fun)
    {
        static constexpr std::size_t MEDIAN = (U - L) / 2 + L;
        if (idx > MEDIAN)
            visit_impl<MEDIAN, U>::visit(tup, idx, fun);
        else if (idx < MEDIAN)
            visit_impl<L, MEDIAN>::visit(tup, idx, fun);
        else
            fun(std::get<MEDIAN>(tup));
    }
};

template <typename F, typename... Ts>
void visit_at(const std::tuple<Ts...>& tup, std::size_t idx, F fun)
{
    assert(idx <= sizeof...(Ts));
    visit_impl<0, sizeof...(Ts)>::visit(tup, idx, fun);
}

template <typename F, typename... Ts>
void visit_at(std::tuple<Ts...>& tup, std::size_t idx, F fun)
{
    assert(idx <= sizeof...(Ts));
    visit_impl<0, sizeof...(Ts)>::visit(tup, idx, fun);
}

/* example code */

/* dummy template to generate different callbacks */
template <int N>
struct Callback
{
    int Call() const
    {
        return N;
    }
};

template <typename T>
struct CallbackTupleImpl;

template <std::size_t... Indx>
struct CallbackTupleImpl<std::index_sequence<Indx...>>
{
    using type = std::tuple<Callback<Indx>...>;
};

template <std::size_t N>
using CallbackTuple = typename CallbackTupleImpl<std::make_index_sequence<N>>::type;

int main()
{
    CallbackTuple<100> myTuple;
    int value{};
    visit_at(myTuple, 42, [&value](auto& pc) { value = pc.Call(); });
    assert(value == 42);
}

With this solution the number of calls to visit_impl is 7. With the linear search approach it would be 58 instead.

Another interesting solution presented here even manages to provide O(1) access. However at the cost of more storage, since a function map with the size O(n) is generated.

Oriana

Answer 7

I modified Oktalist's answer to make it slightly more robust:

• make visit_at method constexpr
• allow visitor to pass any number of arguments (visited tuple element is still required first parameter)
• allow visitor to return a value
• make visit_at method compatible with any std::get-compatible type (e.g., std::array)

For completeness sake, I made it noexcept as well, though that is a mess (where is noexcept(auto) already?).

namespace detail
{
    template<std::size_t I>
    struct visit_impl
    {
        template<typename Tuple, typename F, typename ...Args>
        inline static constexpr int visit(Tuple const &tuple, std::size_t idx, F fun, Args &&...args) noexcept(noexcept(fun(std::get<I - 1U>(tuple), std::forward<Args>(args)...)) && noexcept(visit_impl<I - 1U>::visit(tuple, idx, fun, std::forward<Args>(args)...)))
        {
            return (idx == (I - 1U) ? (fun(std::get<I - 1U>(tuple), std::forward<Args>(args)...), void(), 0) : visit_impl<I - 1U>::visit(tuple, idx, fun, std::forward<Args>(args)...));
        }

        template<typename R, typename Tuple, typename F, typename ...Args>
        inline static constexpr R visit(Tuple const &tuple, std::size_t idx, F fun, Args &&...args) noexcept(noexcept(fun(std::get<I - 1U>(tuple), std::forward<Args>(args)...)) && noexcept(visit_impl<I - 1U>::template visit<R>(tuple, idx, fun, std::forward<Args>(args)...)))
        {
            return (idx == (I - 1U) ? fun(std::get<I - 1U>(tuple), std::forward<Args>(args)...) : visit_impl<I - 1U>::template visit<R>(tuple, idx, fun, std::forward<Args>(args)...));
        }
    };

    template<>
    struct visit_impl<0U>
    {
        template<typename Tuple, typename F, typename ...Args>
        inline static constexpr int visit(Tuple const&, std::size_t, F, Args&&...) noexcept
        {
            return 0;
        }

        template<typename R, typename Tuple, typename F, typename ...Args>
        inline static constexpr R visit(Tuple const&, std::size_t, F, Args&&...) noexcept(noexcept(R{}))
        {
            static_assert(std::is_default_constructible<R>::value, "Explicit return type of visit_at method must be default-constructible");
            return R{};
        }
    };
}

template<typename Tuple, typename F, typename ...Args>
inline constexpr void visit_at(Tuple const &tuple, std::size_t idx, F fun, Args &&...args) noexcept(noexcept(detail::visit_impl<std::tuple_size<Tuple>::value>::visit(tuple, idx, fun, std::forward<Args>(args)...)))
{
    detail::visit_impl<std::tuple_size<Tuple>::value>::visit(tuple, idx, fun, std::forward<Args>(args)...);
}

template<typename R, typename Tuple, typename F, typename ...Args>
inline constexpr R visit_at(Tuple const &tuple, std::size_t idx, F fun, Args &&...args) noexcept(noexcept(detail::visit_impl<std::tuple_size<Tuple>::value>::template visit<R>(tuple, idx, fun, std::forward<Args>(args)...)))
{
    return detail::visit_impl<std::tuple_size<Tuple>::value>::template visit<R>(tuple, idx, fun, std::forward<Args>(args)...);
}

DEMO (demo is not C++11 (due to laziness), but the implementation above should be)

Greenhorn

Should that be && instead of || in the noexcept specifiers? – Hob

I realized that I had misunderstood how overloaded comma operators work, so I corrected the first implementation to not break in the presence of said overloaded comma operator. – Greenhorn

Answer 8

C++17 non-recursive

template <typename T>
inline constexpr size_t tuple_size_v = std::tuple_size<T>::value;

template <typename T, typename F, std::size_t... I>
constexpr void visit_impl(T& tup, const size_t idx, F fun, std::index_sequence<I...>)
{
    assert(idx < tuple_size_v<T>);
    ((I == idx ? fun(std::get<I>(tup)) : void()), ...);
}

template <typename F, typename... Ts, typename Indices = std::make_index_sequence<sizeof...(Ts)>>
constexpr void visit_at(std::tuple<Ts...>& tup, const size_t idx, F fun)
{
    visit_impl(tup, idx, fun, Indices {});
}

template <typename F, typename... Ts, typename Indices = std::make_index_sequence<sizeof...(Ts)>>
constexpr void visit_at(const std::tuple<Ts...>& tup, const size_t idx, F fun)
{
    visit_impl(tup, idx, fun, Indices {});
}

Using:

auto tuple = std::tuple { 1, 2.5, 3, 'Z' };
// print it to cout
for (size_t i = 0; i < tuple_size_v<decltype(tuple)>; ++i) {
    visit_at(tuple, i, [](auto&& arg) {
        using T = std::decay_t<decltype(arg)>;
        std::cout << *typeid(T).name() << arg << ' ';
    });
}

Output: i1 d2.5 i3 cZ

Vivyanne

Answer 9

For c++11 here is a concise approach that returns a pointer:

template <typename Tuple, long template_index = std::tuple_size<Tuple>::value>
struct tuple_address {
  static void * of(Tuple & tuple, long function_index) {
    if (template_index - 1 == function_index) {
      return &std::get<template_index - 1>(tuple);
    } else {
      return tuple_address<Tuple, template_index - 1>::of(tuple, function_index);
    }
  }
};
template <typename Tuple>
struct tuple_address<Tuple, 0> {
  static void * of(Tuple & tuple, long function_index) {
    return 0;
  }
};
template <typename Tuple>
void * tuple_address_of(Tuple & tuple, long index) {
  return tuple_address<Tuple>::of(tuple, index);
}

Hone