Подтвердить что ты не робот

Шаблоны Variadic и оператор switch?

У меня есть следующая функция, которая может принимать N аргументов разных типов и пересылает их к N функциям, шаблонным для каждого отдельного типа, таким образом (пример с двумя аргументами):

template <typename T1, typename T2>
bool func(int& counter, T1 x1, T2 x2) {
    switch (counter) {
        case 0:
            if (func2<T1>(x1)) {
                counter++;
                return true;
            } else {
                return false;
            }
        case 1:
            if (func2<T2>(x2)) {
                counter++;
                return true;
            } else {
                return false;
            }
        default:
            return true;
    }
}

Я хочу написать эту функцию с вариационными шаблонами, чтобы она могла обрабатывать любое количество аргументов безопасным способом. Я вижу решение, использующее рекурсивные функции, проходящее по счетчику и вариационный индекс и сравнивающее их для равенства, но это, казалось бы, дает гораздо менее эффективный код, чем оператор switch выше (последовательность if-проверок по сравнению с таблицей переходов).

Можно ли это сделать эффективно с использованием метапрограммирования шаблонов или мне нужно обеспечить перегрузки для каждой из них?

4b9b3361

ОТВЕТЫ

Ответ 1

Здесь решение, подобное макс, но оно: а) четко отделяет общие части от деталей, специфичных для решения, и б) я показываю, что clang полностью его оптимизирует. Основная идея состоит в том, чтобы построить случай переключения во время компиляции из непрерывной целочисленной последовательности. Мы делаем это следующим образом:

template <class T, T ... Is, class F>
auto compile_switch(T i, std::integer_sequence<T, Is...>, F f) {
  using return_type = std::common_type_t<decltype(f(std::integral_constant<T, Is>{}))...>;
  return_type ret;
  std::initializer_list<int> ({(i == Is ? (ret = f(std::integral_constant<T, Is>{})),0 : 0)...});
  return ret;
}

Идея состоит в том, что целое число передается в лямбда как целочисленный постоянный тип, поэтому его можно использовать в контекстах времени компиляции. Чтобы использовать это с текущей проблемой, все, что нам нужно сделать, это переложить пакет вариаций на кортеж и применить обычные трюки с индексной последовательностью:

template <class T, std::size_t ... Is>
bool func_impl(std::size_t& counter, T&& t, std::index_sequence<Is...> is) {
  auto b = compile_switch(counter, is, [&] (auto i) -> bool {
    return func2(std::get<i>(std::move(t)));
  });
  if (b) ++counter;
  return b;
}

template <class ... Ts>
bool func(std::size_t & counter, Ts&& ... ts) {
  return func_impl(counter,
      std::forward_as_tuple(std::forward<Ts>(ts)...),
      std::index_sequence_for<Ts...>{});
}

Мы будем использовать это определение func2 для просмотра некоторой сборки:

template <class T>
bool func2(const T& t) { std::cerr << t; return std::is_trivial<T>::value; }

Заглядывая здесь: https://godbolt.org/g/6idVPS, мы замечаем следующие инструкции:

auto compile_switch<unsigned long, 0ul, 1ul, 2ul, 3ul, 4ul, 5ul, bool func_impl<std::tuple<int&, double&, int&, unsigned long&, char const*&, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&>, 0ul, 1ul, 2ul, 3ul, 4ul, 5ul>(unsigned long&, std::tuple<int&, double&, int&, unsigned long&, char const*&, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&>&&, std::integer_sequence<unsigned long, 0ul, 1ul, 2ul, 3ul, 4ul, 5ul>)::{lambda(auto:1)#1}>(unsigned long, std::integer_sequence<unsigned long, 0ul, 1ul, 2ul, 3ul, 4ul, 5ul>, bool func_impl<std::tuple<int&, double&, int&, unsigned long&, char const*&, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&>, 0ul, 1ul, 2ul, 3ul, 4ul, 5ul>(unsigned long&, std::tuple<int&, double&, int&, unsigned long&, char const*&, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&>&&, std::integer_sequence<unsigned long, 0ul, 1ul, 2ul, 3ul, 4ul, 5ul>)::{lambda(auto:1)#1}): # @auto compile_switch<unsigned long, 0ul, 1ul, 2ul, 3ul, 4ul, 5ul, bool func_impl<std::tuple<int&, double&, int&, unsigned long&, char const*&, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&>, 0ul, 1ul, 2ul, 3ul, 4ul, 5ul>(unsigned long&, std::tuple<int&, double&, int&, unsigned long&, char const*&, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&>&&, std::integer_sequence<unsigned long, 0ul, 1ul, 2ul, 3ul, 4ul, 5ul>)::{lambda(auto:1)#1}>(unsigned long, std::integer_sequence<unsigned long, 0ul, 1ul, 2ul, 3ul, 4ul, 5ul>, bool func_impl<std::tuple<int&, double&, int&, unsigned long&, char const*&, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&>, 0ul, 1ul, 2ul, 3ul, 4ul, 5ul>(unsigned long&, std::tuple<int&, double&, int&, unsigned long&, char const*&, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&>&&, std::integer_sequence<unsigned long, 0ul, 1ul, 2ul, 3ul, 4ul, 5ul>)::{lambda(auto:1)#1})
        push    r14
        push    rbx
        push    rax
        mov     bl, 1
        cmp     rdi, 5
        ja      .LBB2_11
        jmp     qword ptr [8*rdi + .LJTI2_0]

Глядя на эту метку, мы находим:

.LJTI2_0:
        .quad   .LBB2_2
        .quad   .LBB2_4
        .quad   .LBB2_5
        .quad   .LBB2_6
        .quad   .LBB2_7
        .quad   .LBB2_10

Другими словами, clang превратил это в таблицу переходов и вложил все вызовы в func2. Это невозможно с помощью таблицы указателей функций, как некоторые предложили (по крайней мере, я никогда не видел, чтобы компилятор делал это), на самом деле единственным способом получить сборку это хорошо через случай переключения или с помощью этой техники + clang. К сожалению, gcc не будет генерировать сборку столь же хорошо, но все же прилично.

Ответ 2

Просто для удовольствия я предлагаю следующий путь

template <typename ... Ts>
bool func (int & cnt, Ts ... xs)
 {
   using unused = int[];

   int  i   { -1 };
   bool ret { true };

   (void)unused { 0, ((++i == cnt ? (ret = func<Ts>(xs)) : true), 0)... };

   if ( ret && (cnt <= i) )
      ++cnt;

   return ret;
 }

но я не думаю, что это эффективный способ переключения.

Ответ 3

Это решение может быть наиболее эффективным:

template<size_t I,class...Args>
bool func2_b(Args...arg)
  {
  if (func2(std::get<I>(std::tuple<Args...>{arg...})))
    return true;
  else
   return false;
  }

template<class...Args,size_t...Is>
bool func_(int& counter,std::index_sequence<Is...>,Args...args)
  {
  using ft = bool(*)(Args...);
  ft table[]={func2_b<Is,Args...>...};
  if (counter<0 || counter>=(int)sizeof...(Args))
    return false;
  return table[counter](args...);
  }

template<class...Args>
bool func(int& counter,Args...xs)
  {
  return func_(counter,std::make_index_sequence<sizeof...(Args)>{},xs...);
  }

Ответ 4

Также для удовольствия это может быть слишком запутанным

#include<type_traits>
#include<array>

template<typename T>
void g(T&& t)
{
    // This function gets called
}

template<typename T>
void entry(void* p)
{
    g(*(std::remove_reference_t<T>*)p);
}

template<size_t N>
using table_t = std::array<void (*)(void*), N>;

template<typename... Ts>
constexpr auto make_table()
{
    return table_t<sizeof...(Ts)>{
        entry<Ts>...
    };
}

template<size_t N>
void f_(const table_t<N>&, int)
{

}

template<size_t N, typename T, typename... Ts>
void f_(const table_t<N>& table, int select, T&& t, Ts&&... ts)
{
    if(select == N - sizeof...(Ts) - 1)
        table[select]((void*)&t);
    else
        f_(table, select, std::forward<Ts>(ts)...);
}

template<typename... Ts>
void f(int select, Ts&&... ts)
{
    static constexpr auto table = make_table<Ts...>();
    if(select < 0 || select >= int(sizeof...(Ts)))
        throw "out of bounds";
    f_(table, select, std::forward<Ts>(ts)...);
}

Что катит vtable в f и отправляет соответственно g.

Live

Ответ 5

Теоретически вы можете выполнить двоичный поиск индекса параметров самостоятельно:

#include <type_traits>
#include <tuple>
#include <typeinfo>
#include <iostream>
#include <algorithm>


template <std::size_t I>
using ic = std::integral_constant<std::size_t, I>;

template <class T>
bool func2(T) {
    std::cout<<typeid(T).name()<<std::endl;
    return true;
}

template <std::size_t N, class T>
bool func_impl(ic<0>, ic<N>, std::size_t &, T &&tup) {
    constexpr int index = std::min(N - 1, std::tuple_size<T>{} - 1);
    if (func2<std::tuple_element_t<index, std::decay_t<T>>>(std::get<index>(tup))) 
        return true;
    return false;
}

template <std::size_t K, std::size_t N, class T>
bool func_impl(ic<K>, ic<N> n, std::size_t &counter, T &&tup) {
    if (counter == N - 1) {
        return func_impl(ic<0>{}, n, counter, std::forward<T>(tup));
    }
    if (counter < N) {
        return func_impl(ic<K/2>{}, ic<N - K>{}, counter, std::forward<T>(tup));
    } else {
        return func_impl(ic<K/2>{}, ic<N + K>{}, counter, std::forward<T>(tup));
    }
}

template <class... Ts>
bool func(std::size_t& counter, Ts&&... xs) {
    return func_impl(ic<sizeof...(Ts)/2>{}, ic<sizeof...(Ts)/2>{}, counter, std::forward_as_tuple(xs...));
}

int main() {
   std::size_t i = 0;
   func<int, float, double, char>(i, 1, 2, 3, 4); 
}

[live demo]