使用查找选择具有运行时索引的可变参数类型 Table

Question

考虑一组可变类型。可以 select 并使用递归索引函数和带有 auto 参数的 lambda 来使用由运行时值索引的类型之一，如下所示：

#include <iostream>
#include <functional>
#include <variant>

template<typename T> 
struct identity { using type = T; };

template<typename ... Cs>
struct variadic
{  
    template<size_t N>
    using type = std::tuple_element_t<N, std::tuple<Cs ...>>;

    template<typename F, size_t I = 0>
    static void identify(size_t index, F action)
    {
        if (index == I)
        {
            std::invoke(action, identity<type<I>>());
            return;
        }

        if constexpr (I < (sizeof...(Cs) - 1))
        {
            identify<F, I + 1>(index, action);
            return;
        }

        throw std::runtime_error("failed to identify type");
    }
};

struct s_a { void speak() { std::cout << "s_a" << std::endl; } };
struct s_b { void speak() { std::cout << "s_b" << std::endl; } };
struct s_c { void speak() { std::cout << "s_c" << std::endl; } };
struct s_d { void speak() { std::cout << "s_d" << std::endl; } };
struct s_e { void speak() { std::cout << "s_e" << std::endl; } };
struct s_f { void speak() { std::cout << "s_f" << std::endl; } };

void speak(size_t index)
{
    variadic<s_a, s_b, s_c, s_d, s_e, s_f>::identify(index, [](auto id)
    {
        using state_type = typename decltype(id)::type;
        state_type().speak();
    });
}

这种方法在编译时生成一系列 if 语句，under the hood 解析为多个分支。我想在某一点之后这会退化为分支预测错误的障碍。

有没有一种方法可以在幕后生成查找 table（本质上是 vtable），类似于 std::visit 的工作方式，从而实现相同的行为？

Answer 1

"simple"方法是构建一个函数指针数组：

template<typename F>
static void identify(size_t index, F action) {
    // handle case when index > sizeof...(Cs)

    using FPtr = void(*)(F&);
    static constexpr FPtr table[] = {
        +[](F& action){ action(identity<type<Cs>>()) }...
    };
    table[index](action);
}

有些编译器可能不喜欢这样扩展 lambda，因此您可以创建一个真正的函数：

template <typename T, typename F>
static void _apply(F& action) {
    action(identity<type<T>>());
}

template<typename F>
static void identify(size_t index, F action) {
    // handle case when index > sizeof...(Cs)

    using FPtr = void(*)(F&);
    static constexpr FPtr table[] = { _apply<Cs, F>... };
    table[index](action);
}

但是优化器往往不太擅长像这样内联函数指针。 variant 实现过去看起来像上面的，但正在远离它。

如果你真的想全力以赴，你将不得不编写一个递归开关...Michael Park对此给出了很好的解释，它相当复杂。

Answer 2

作为参考，这里是 Michael Park 的展开开关方法的实现，由 Barry 链接。

#include <iostream>
#include <functional>
#include <variant>

template<typename T> 
struct identity { using type = T; };

template<size_t I, typename ... Cs>
using type = std::tuple_element_t<I, std::tuple<Cs ...>>;

template<bool Valid, typename ... Cs>
struct dispatcher;

template<typename ... Cs>
struct dispatcher<false, Cs ...> 
{
    template<size_t I, typename F>
    constexpr static void case_(F) 
    { 
        static_assert(I >= sizeof...(Cs));
        __builtin_unreachable(); 
    }

    template<size_t B, typename F>
    constexpr static void next_(size_t, F) 
    { 
        static_assert(B >= sizeof...(Cs));
        __builtin_unreachable(); 
    }
};

template<typename ... Cs>
struct dispatcher<true, Cs ...>
{
    template<size_t I, typename F>
    constexpr static void case_(F action) 
    { 
        static_assert(I < sizeof...(Cs));
        std::invoke(action, identity<type<I, Cs ...>>()); 
    }

    template<size_t B, typename F>
    constexpr static void next_(size_t index, F action)
    {
        constexpr size_t size = sizeof...(Cs);

        switch (index) 
        {
        case B +  0: dispatcher<(B +  0 < size), Cs ...>::template case_<B +  0>(action); break;
        case B +  1: dispatcher<(B +  1 < size), Cs ...>::template case_<B +  1>(action); break;
        case B +  2: dispatcher<(B +  2 < size), Cs ...>::template case_<B +  2>(action); break;
        case B +  3: dispatcher<(B +  3 < size), Cs ...>::template case_<B +  3>(action); break;    
        case B +  4: dispatcher<(B +  4 < size), Cs ...>::template case_<B +  4>(action); break;
        case B +  5: dispatcher<(B +  5 < size), Cs ...>::template case_<B +  5>(action); break;
        case B +  6: dispatcher<(B +  6 < size), Cs ...>::template case_<B +  6>(action); break;
        case B +  7: dispatcher<(B +  7 < size), Cs ...>::template case_<B +  7>(action); break;    
        case B +  8: dispatcher<(B +  8 < size), Cs ...>::template case_<B +  8>(action); break;
        case B +  9: dispatcher<(B +  9 < size), Cs ...>::template case_<B +  9>(action); break;
        case B + 10: dispatcher<(B + 10 < size), Cs ...>::template case_<B + 10>(action); break;
        case B + 11: dispatcher<(B + 11 < size), Cs ...>::template case_<B + 11>(action); break;
        case B + 12: dispatcher<(B + 12 < size), Cs ...>::template case_<B + 12>(action); break;
        case B + 13: dispatcher<(B + 13 < size), Cs ...>::template case_<B + 13>(action); break;    
        case B + 14: dispatcher<(B + 14 < size), Cs ...>::template case_<B + 14>(action); break;
        case B + 15: dispatcher<(B + 15 < size), Cs ...>::template case_<B + 15>(action); break;
        case B + 16: dispatcher<(B + 16 < size), Cs ...>::template case_<B + 16>(action); break;
        case B + 17: dispatcher<(B + 17 < size), Cs ...>::template case_<B + 17>(action); break;    
        case B + 18: dispatcher<(B + 18 < size), Cs ...>::template case_<B + 18>(action); break;
        case B + 19: dispatcher<(B + 19 < size), Cs ...>::template case_<B + 19>(action); break;
        case B + 20: dispatcher<(B + 20 < size), Cs ...>::template case_<B + 20>(action); break;
        case B + 21: dispatcher<(B + 21 < size), Cs ...>::template case_<B + 21>(action); break;
        case B + 22: dispatcher<(B + 22 < size), Cs ...>::template case_<B + 22>(action); break;
        case B + 23: dispatcher<(B + 23 < size), Cs ...>::template case_<B + 23>(action); break;    
        case B + 24: dispatcher<(B + 24 < size), Cs ...>::template case_<B + 24>(action); break;
        case B + 25: dispatcher<(B + 25 < size), Cs ...>::template case_<B + 25>(action); break;
        case B + 26: dispatcher<(B + 26 < size), Cs ...>::template case_<B + 26>(action); break;
        case B + 27: dispatcher<(B + 27 < size), Cs ...>::template case_<B + 27>(action); break;    
        case B + 28: dispatcher<(B + 28 < size), Cs ...>::template case_<B + 28>(action); break;
        case B + 29: dispatcher<(B + 29 < size), Cs ...>::template case_<B + 29>(action); break;
        case B + 30: dispatcher<(B + 30 < size), Cs ...>::template case_<B + 30>(action); break;
        case B + 31: dispatcher<(B + 31 < size), Cs ...>::template case_<B + 31>(action); break;
        default:     dispatcher<(B + 32 < size), Cs ...>::template next_<B + 32>(index, action); break;
        }
    }
};

template<typename ... Cs>
struct variadic
{  
    template <typename F>
    constexpr static void identify(size_t index, F action) 
    {
        constexpr size_t size = sizeof...(Cs);
        if (index >= size)
            throw std::out_of_range("type index out of bounds");
        dispatcher<(0 < size), Cs ...>::template next_<0>(index, action);
    }
};

struct s_a { void operator()() { std::cout << "s_a" << std::endl; } };
struct s_b { void operator()() { std::cout << "s_b" << std::endl; } };
struct s_c { void operator()() { std::cout << "s_c" << std::endl; } };
struct s_d { void operator()() { std::cout << "s_d" << std::endl; } };
struct s_e { void operator()() { std::cout << "s_e" << std::endl; } };
struct s_f { void operator()() { std::cout << "s_f" << std::endl; } };

void speak(size_t index)
{
    variadic<s_a, s_b, s_c, s_d, s_e, s_f>::identify(index, [](auto id)
    {
        using state_type = typename decltype(id)::type;
        std::invoke(state_type());
    });
}

为了完整起见，这是函数指针方法的一个版本，正如所宣传的那样，它优化得不是很好。

#include <iostream>
#include <functional>
#include <variant>

template<typename T> 
struct identity { using type = T; };

template<size_t I, typename ... Cs>
using type = std::tuple_element_t<I, std::tuple<Cs ...>>;

template<typename ... Cs>
struct variadic
{  
    template <typename T, typename F>
    static void _apply(F& action) 
    {
        action(identity<T>());
    }

    template<typename F>
    static void identify(size_t index, F action) 
    {
        constexpr size_t size = sizeof...(Cs);
        if (index >= size)
            throw std::out_of_range("type index out of bounds");

        using func_ptr = void(*)(F&);
        static constexpr func_ptr table[] = { _apply<Cs, F>... };
        table[index](action);
    }
};

struct s_a { void operator()() { std::cout << "s_a" << std::endl; } };
struct s_b { void operator()() { std::cout << "s_b" << std::endl; } };
struct s_c { void operator()() { std::cout << "s_c" << std::endl; } };
struct s_d { void operator()() { std::cout << "s_d" << std::endl; } };
struct s_e { void operator()() { std::cout << "s_e" << std::endl; } };
struct s_f { void operator()() { std::cout << "s_f" << std::endl; } };

void speak(size_t index)
{
    variadic<s_a, s_b, s_c, s_d, s_e, s_f>::identify(index, [](auto id)
    {
        using state_type = typename decltype(id)::type;
        std::invoke(state_type());
    });
}

展开的开关方法在优化方面看起来很成功，我可能最终会使用它。

使用查找选择具有运行时索引的可变参数类型 Table

Selecting Variadic Type with Runtime Index using Lookup Table

c++

templates

template-meta-programming

variadic-templates

c++17