Рекурсивное объяснение шаблона C ++

Question

template<typename... ArgTypes>
int add(ArgTypes... args);

template<typename T, typename... ArgTypes>
int add(T t, ArgTypes... args)
{
    int sum = 0;
    return t + add(args...);
}
template<> int add() {
    return 0;
} 

Как добавить больше операций, таких как умножение и вычитание?Что означает template<> int add()?

Может ли кто-нибудь подробно объяснить, как работает этот рекурсивный шаблон?

UPD: Спасибо, ребята, за вычитание, да, вычитание не является коммутативным, поэтому оно не очень подходит для таких рекурсивных шаблонов.

UPD2: добавлен стек вызовов в качестве справки для сообщества

Answer 1

Вот моя попытка объяснения.

Во-первых:

template<typename... ArgTypes>
int add(ArgTypes... args);

Это отправная точка.В нем говорится «существует функция с именем add, которая принимает ноль или более общих аргументов».Он не содержит реализацию, поэтому сам по себе он представляет собой своего рода обещание компилятору, что такая функция будет существовать.

Тогда мы имеем:

template<typename T, typename... ArgTypes>
int add(T t, ArgTypes... args)
{
    int sum = 0; // This line isn't doing anything!
    return t + add(args...);
}

Это говоритmsgstr "здесь есть функция с именем add, которая принимает один или несколько общих аргументов".Это включает в себя реализацию.Часть этой реализации рекурсивно вызывает add(args...) со всеми аргументами, кроме первого (т. Е. Ноль или более).Нам сказали, что это существует в первом объявлении выше.

Если в args есть хотя бы один аргумент, то этот рекурсивный вызов снова вызовет ту же самую функцию.Но что происходит, когда args содержит ноль аргументов?Нам нужна версия (специализация) функции для обработки этого случая, которая является единственным случаем, не обработанным нашим вторым определением.Вот где появляется третье объявление:

template<> int add() {
    return 0;
} 

Это определяет функцию с именем add, которая принимает ноль аргументов.

Итак, в итоге:

1. Второе объявление определяет функцию, принимающую один или несколько аргументов
2. Третье объявление определяет функцию, принимающую ноль аргументов
3. вместеэто означает, что у нас есть функция, принимающая ноль или более аргументов, как объявлено в первом объявлении.

Answer 2

Это довольно распространенный рекурсивный шаблон переменной .Идея состоит в том, что мы используем рекурсию

f(x0, x1, ..., xn) = f(f(x0, x1, ..., xn-1), xn) (1),

в вашем образце

add(x0, x1, ..., xn) = add(x0, x1, ..., xn-1) + xn.

Шаблоны Variadic предоставляют простой и полезный способсоздайте такую ​​структуру.

Сначала определите общую сигнатуру шаблона (без реализации, потому что мы никогда не используем общую форму)

template<typename... ArgTypes>
int add(ArgTypes... args);

Теперь специализируйте функцию шаблона для случая с хотя бы однимпараметр.Мы используем рекурсию, которая извлекает первый аргумент и вызывает себя рекурсивно с уменьшенным на единицу количеством параметров.

template<typename T, typename... ArgTypes>
int add(T t, ArgTypes... args)
{
    int sum = 0;
    return t + add(args...); // recursive call without first arg
}

Чтобы остановить рекурсию, мы используем специализацию шаблона для пустого списка параметров шаблона (мы добавили 0 на последнем шаге).

template<> int add() {
    return 0;
} 

Для умножения вам нужно просто изменить + на *, потому что общая рекурсивная форма (1) идентична в обоих случаях, и изменить return 0 на return 1 (умножить на * 1029)* на последнем этапе).

В случае вычитания общая форма рекурсии (1) неприменима, поскольку возникает a-b != b-a, неопределенность.Также с делением и другими некоммутативными операциями.Вам нужно будет уточнить порядок операций.

Answer 3

Может ли кто-нибудь подробно объяснить, как работает этот рекурсивный шаблон?

Я могу попробовать.

Сначала у вас есть

template<typename... ArgTypes>
int add(ArgTypes... args);

Этообъявление функции шаблона переменной: вы объявляете, что существует add() функция, которая получает переменное (ноль или более) число аргументов.

Внимание: вы объявляете, но не определяете функцию.

Второе: вы объявляете и , определяющие

template<typename T, typename... ArgTypes>
int add(T t, ArgTypes... args)
{
    int sum = 0;
    return t + add(args...);
}

a различные функции шаблона add(), которые получают аргумент типа шаблона (t) и шаблон списка переменных аргументов (args...).

Строка

int sum = 0;

совершенно бесполезна, поскольку объявляет неиспользуемую переменную, но следующую строку

return t + add(args...);

выполняет работу, возвращая сумму между t и сумму (add(args...)) между следующими args....

То есть с add(args...) рекурсивно называется int add(T t, ArgTypes... args), когда args...(потому что это лучшее совпадение) не пусто и int add(ArgTypes... args), когда args... - пустой список.

Но помните, что int add(ArgTypes... args) объявлено, но не определено.

Последний пункт -

template<> int add() {
    return 0;
} 

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

Off Тема: вам не нужна первая шаблонная функция;Вы можете заменить его более простой функцией без шаблонов.

Вы можете переписать код следующим образом:

int add()
 { return 0; } 

template <typename T, typename... ArgTypes>
int add(T t, ArgTypes... args)
 { return t + add(args...); }

и, как рекомендует Jarod42, если вы можете использовать C ++ 17, выможно полностью избежать рекурсии, используя сгибание шаблона

template <typename... ArgTypes>
int add (ArgTypes... args)
 { return (... + args); }

или, возможно, использование auto для возврата типа.

Как добавить больше операций, таких как умножение и вычитание?

Нет представления о вычитании (как определяется вариативное вычитание?), Но для умножения вы можете использовать что-то подобное (но основной случай должен возвращать 1, а не 0)

int mult ()
 { return 1; } 

template <typename T, typename... ArgTypes>
int mult (T t, ArgTypes... args)
 { return t * mult(args...); }

или с использованием шаблона сворачивания, из C ++ 17,

template <typename... ArgTypes>
int mult (ArgTypes... args)
 { return (... * args); }

Answer 4

Рекурсия имеет базовый случай .Таким образом, вы можете думать о template<> int add() как о шаблонной специализации, охватывающей базовый случай, когда T является целым числом.Это будет вызвано, когда sizeof...(args) равно нулю.См. Демо Здесь .

Для умножения вы можете сделать это:

template<typename T, typename... ArgTypes>
int mult(T t, ArgTypes... args)
{
    return t * mult(args...);
}
template<> int mult() {
    return 1;
} 

Я не уверен, что вы намерены сделать для вычитания, хотя.Мы можем иметь сумму (сложение) чисел и произведение (умножение) чисел, но нет ничего похожего на ???(вычитание) чисел.