вычисления факториала с использованием шаблона метапрограммировании

Question

Я не понимаю, как этот кусок кода (from Wikipedia) работ:

template <int N> 
struct Factorial 
{ 
    enum { value = N * Factorial<N - 1>::value }; 
}; 

template <> 
struct Factorial<0> 
{ 
    enum { value = 1 }; 
}; 

// Factorial<4>::value == 24 
// Factorial<0>::value == 1 
void foo() 
{ 
    int x = Factorial<4>::value; // == 24 
    int y = Factorial<0>::value; // == 1 
} 

• Что это странно шаблон, который принимает <int N>?
• Что это за второй странный шаблон <>?
• Что такое enum аксессуаров для?
• В чем преимущество использования этого, а не нормального расчет времени выполнения?
• Как часто вы путешествуете? Я уже некоторое время использую C++, но никогда раньше этого не использовал. Насколько большой частью C++ я отсутствовал?

Спасибо!

Answer 1

• Что это странно шаблон, который принимает <int N>?

В C++, аргументы шаблона могут быть либо типа (с префиксом class или typename) или целых (с приставкой int или unsigned int). Здесь мы находимся во втором случае.

• Что это второй странно template <>?

template<> struct Factorial<0> полная специализация шаблона класса Факториал, что означает, что 0 считается особое значение, которое соответствует его собственной версии Факториал.

• Для чего предназначены перечисления?

перечислений являются способом вычисления значений в метапрограммирования C++

• Что такое преимущество использования этого вместо нормального выполнения факторного расчета?

Причина, почему этот код был создан в первую очередь создать доказательство концепции, что исчисление может быть сделано с помощью метапрограммирования. Преимущество заключается в том, что сгенерированный код является чрезвычайно эффективным (вызов Factorial<4>::value эквивалентно просто писать «24» в вашем коде.

• Как часто вы люди используют это? Я использую C++ на некоторое время теперь, но никогда не использовал это раньше. Как большую часть C++ был я пропускаю?

Такой функциональность редко достигаются с помощью этого метода, но метапрограммирование используется все больше и больше в настоящее время. См Boost meta-programming library, чтобы получить подсказку что можно сделать.

Answer 2

Это рекурсия выполняется компилятором, где

template <> 
struct Factorial<0> 
{ 
} 

является точкой выхода из рекурсии.

Сначала Factorial<4> разрешен. Для значения 4 нет специализации Factorial, поэтому используется первое определение Factorial<>. Затем вычисляется значение Factorial<3>::value, где повторен предыдущий шаг.

Это будет продолжаться до N == 1, затем для N-1 вступает в действие специализация Factorial<0>, где значение равно 1. Рекурсия останавливается здесь, и компилятор может идти вверх и вычисляет оставшиеся значения Factorial<N>.

Answer 3

В чем преимущество использования этого, а не обычного факториального расчета времени выполнения?

Это быстрее - теоретически компилятор расширит набор шаблонов во время компиляции, например, что Factorial<n>::value является просто одной константой. В некоторых исчезающе малых случаях это может иметь значение.

Недостатком этого является то, что он должен быть рассчитан во время компиляции, поэтому, если ваш n определяется во время выполнения, вы не можете использовать этот метод.

Как часто вы путешествуете? Я использовал C++ некоторое время, , но никогда не использовал это раньше. Насколько большой частью C++ я отсутствовал?

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

Но это полезный метод в C++, поскольку он позволяет языку делать множество мощных трюков, которые иначе были бы недоступны. Я бы рискнул, что гораздо чаще использовать метапрограммирование шаблонов, которые кто-то сделал для вас - например. Boost использует его довольно сильно и в результате может сделать очень умные вещи. Он мощный, но может также обфускать код, если он не сделан хорошо.

Answer 4

Что это за странный шаблон, который принимает <int N>?

Объявление типа может быть сделано для классов/типов, значений и указателей. Обычно вы не видите эту форму, так как определение шаблонов редко использует константы в параметрах шаблона.

Что это за второй странный шаблон <>?

Лучший способ думать о шаблоне - это сделать что-то похожее на то, что делает компилятор: рассмотрите шаблон как класс, где вы заменяете параметр шаблона фактическим значением этого типа.

То есть, для:

template <int N> 
struct Factorial 
{ 
    enum { value = N * Factorial<N - 1>::value }; 
}; 

Factorial<2>::value эквивалентно:

// generated by the compiler when Factorial<2>::value is encountered in code: 
struct Factorial2 { enum { value = 2 * Factorial1::value }; }; 
struct Factorial1 { enum { value = 1 * Factorial0::value }; }; 
// not generated by compiler, as it was explicitly defined in the code you ask about: 
template <> struct Factorial<0> { enum { value = 1 }; }; // defines Factorial<0> 

Каковы перечислений для?

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

Что такое преимущество использования этого вместо нормального выполнения факторного расчета?

Преимущество - эффективность. Поскольку вычисление значения расширяется при компиляции, стоимость исполнения Factorial<10>::value такая же, как Factorial < 1> :: значение. В скомпилированном коде они являются константами. Если вы должны были рассчитать факторный код, зависящий от производительности, и вы знали, что в момент компиляции это значение, вы должны либо сделать это, либо рассчитать его в автономном режиме, либо определить константу с предварительно рассчитанным значением в вашем коде.

Как часто вы путешествуете?

Является ли это «вы» ссылкой на рекурсивное вычисление константы? Если да, то не часто.

Является ли это «определение» констант в шаблонах? Очень часто :)

Является ли это «особенностью» шаблона для определенного типа? Очень Очень Очень часто. Я понял, что std :: vector имеет полностью отдельную реализацию в некоторых реализациях STL (для std::vector<bool> с 8 элементами не требуется больше 1 байта для хранения значений).

Я использовал C++ какое-то время, , но никогда не использовал это раньше. Насколько большой часть C++ была упущена?

Не обязательно большая часть. Если вы используете boost, вероятно, что используемый вами код реализуется с помощью таких вещей.

Answer 5

Я нашел this answer от Johannes Schaub - litb по другому вопросу очень полезно.

[Я скопирую здесь ответ, предполагая, что Йоханнес в порядке.Я удалю пасту, если он не нравится]

---

Да, это параметр не типа. У вас может быть несколько видов параметров шаблона

• Параметры типа.
  • Типы
  • шаблоны (только классы, не функции)
• Параметры Non-типа
  • указки
  • Ссылки
  • Интегральные константные выражения

У вас есть последний вид. Это постоянная времени компиляции (так называемое постоянное выражение) и имеет тип integer или перечисление. После поиска в стандарте мне пришлось переместить классные шаблоны в раздел типов - хотя шаблоны не являются типами. Но они называются параметрами типа с целью описания тех видов. У вас могут быть указатели (а также указатели элементов) и ссылки на объекты/функции, которые имеют внешнюю привязку (те, которые могут быть связаны с другими объектными файлами и адрес которых уникален во всей программе). Примеры:

Шаблон параметров Тип:

template<typename T> 
struct Container { 
    T t; 
}; 

// pass type "long" as argument. 
Container<long> test; 

Шаблон целочисленный параметр:

template<unsigned int S> 
struct Vector { 
    unsigned char bytes[S]; 
}; 

// pass 3 as argument. 
Vector<3> test; 

Параметр указателя шаблона (передавая указатель на функцию)

template<void (*F)()> 
struct FunctionWrapper { 
    static void call_it() { F(); } 
}; 

// pass address of function do_it as argument. 
void do_it() { } 
FunctionWrapper<&do_it> test; 

ссылка Шаблон параметра (передача целого числа)

template<int &A> 
struct SillyExample { 
    static void do_it() { A = 10; } 
}; 

// pass flag as argument 
int flag; 
SillyExample<flag> test; 

Шаблон для шаблона.

template<template<typename T> class AllocatePolicy> 
struct Pool { 
    void allocate(size_t n) { 
     int *p = AllocatePolicy<int>::allocate(n); 
    } 
}; 

// pass the template "allocator" as argument. 
template<typename T> 
struct allocator { static T * allocate(size_t n) { return 0; } }; 
Pool<allocator> test; 

Шаблон без параметров невозможен. Но шаблон без явного аргумента возможно - он имеет аргументы по умолчанию:

template<unsigned int SIZE = 3> 
struct Vector { 
    unsigned char buffer[SIZE]; 
}; 

Vector<> test; 

синтаксический, template<> зарезервирован для обозначения явной специализации шаблона вместо шаблона без параметров:

template<> 
struct Vector<3> { 
    // alternative definition for SIZE == 3 
}; 

---