35

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.

Community
  • 1
  • 1
w00d
  • 5,416
  • 12
  • 53
  • 85
  • Yes, use a vector. The title of your question is misleading. You don't know the value of `var` at compile time. – n. m. could be an AI Mar 11 '15 at 21:02
  • 16
    You seem to be asking how to index a tuple at **runtime**. – Drew Dormann Mar 11 '15 at 21:09
  • 9
    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. –  Mar 11 '15 at 21:10
  • This is what I've done before: http://stackoverflow.com/questions/2873802/specify-template-parameters-at-runtime/2873883#2873883 – Bill Lynch Mar 11 '15 at 21:11
  • @DrewDormann yes, indeed, changed my title to make it clearer – w00d Mar 11 '15 at 21:12
  • 2
    Does your tuple contain different types? Is `doSomething` overloaded for all the types, or are implicit conversions expected? – Drew Dormann Mar 11 '15 at 21:14
  • @DrewDormann It can have different type, by just having them templated right ? So let's assume some implicit conversion. – w00d Mar 11 '15 at 21:16
  • @w00d 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. – Otomo Mar 11 '15 at 21:27
  • 5
    Oh noes, an array lookup! It's only literally one of the fastest operations it's possible to perform. – Puppy Mar 11 '15 at 21:30
  • possible duplicate of [(C++) Feed template function element from tuple at runtime?](http://stackoverflow.com/questions/27790038/c-feed-template-function-element-from-tuple-at-runtime) – Quentin Mar 11 '15 at 22:37
  • 3
    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. – sbabbi Mar 11 '15 at 23:38
  • Possible duplicate of [How to get the i-th element from an std::tuple when i isn't know at compile-time?](https://stackoverflow.com/questions/8194227/how-to-get-the-i-th-element-from-an-stdtuple-when-i-isnt-know-at-compile-time) – xskxzr Jan 16 '19 at 17:01

9 Answers9

38

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

Oktalist
  • 14,336
  • 3
  • 43
  • 63
  • 1
    Nice, it didn't occur to me to use the tuple size as the range of indices ... doh. – Jonathan Wakely Mar 11 '15 at 21:48
  • Nice but I think the demo is only working for c++14, something is wrong with c++11 ? – w00d Mar 12 '15 at 00:53
  • 1
    @w00d The generic lambda `[](auto v) {...}` is a C++14 feature. You could write a generic functor instead: `struct F { template operator()(T v) const {...} }; F doSomething;` – Oktalist Mar 12 '15 at 01:12
  • 1
    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). http://ideone.com/ExUbjK – ASten Sep 25 '16 at 16:06
  • 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? – PYA Oct 19 '17 at 01:23
  • @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`. – Oktalist Oct 19 '17 at 01:38
  • @Oktalist 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. – PYA Oct 19 '17 at 02:13
  • Thanks for this answer. I'm using a [modified version](https://stackoverflow.com/a/47385405/1136311) of your answer to access a parameter pack using a runtime index, and it's incredibly fast. – monkey0506 Nov 20 '17 at 05:32
16

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);
    }
  }
}
Casey
  • 41,449
  • 7
  • 95
  • 125
  • 2
    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. – Oktalist Mar 11 '15 at 23:19
  • Very nice! But don't you want a cast-to-void for the comma operator issue? – Vaughn Cato Mar 11 '15 at 23:36
  • @w00d 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. – Casey Mar 12 '15 at 01:19
14

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);
    }
}
scx
  • 3,221
  • 1
  • 19
  • 37
  • 1
    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. – fuzzyTew Jun 30 '20 at 13:46
10

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!

Jonathan Wakely
  • 166,810
  • 27
  • 341
  • 521
  • 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. – w00d Mar 11 '15 at 21:19
  • 1
    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... – T.C. Mar 11 '15 at 21:38
  • @T.C. 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. – Jonathan Wakely Mar 11 '15 at 21:45
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)

Dmitry Katkevich
  • 883
  • 7
  • 26
3

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.

MechaTheo
  • 123
  • 1
  • 9
2

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)

monkey0506
  • 2,489
  • 1
  • 21
  • 27
  • Should that be `&&` instead of `||` in the `noexcept` specifiers? – Oktalist Nov 20 '17 at 14:49
  • 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. – monkey0506 Jan 06 '18 at 13:32
1

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

X-Ray
  • 11
  • 2
0

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);
}
fuzzyTew
  • 3,511
  • 29
  • 24