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

Ответ 1

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

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

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

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

• Что такое перечисления для?

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

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

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

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

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

Ответ 2

Что это за странный шаблон, который принимает <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 > ::. В скомпилированном коде они являются константами. Если вы должны были рассчитать факторный код, зависящий от производительности, и вы знали, во время компиляции это значение, вы должны либо сделать это, либо рассчитать его в автономном режиме, либо определить константу с предварительно рассчитанным значением в вашем коде.

Как часто вы это используете?

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

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

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

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

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

Ответ 3

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

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

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

• Введите параметры.
  • Типы
  • Шаблоны (только классы, без функций)
• Неигровые параметры
  • Указатели
  • Ссылки
  • Интегральные константные выражения

У вас есть последний вид. Это константа времени компиляции (так называемое постоянное выражение) и имеет тип 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
};

Ответ 4

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

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

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

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

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

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

Ответ 5

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

template <>
struct Factorial<0>
{
}

- точка выхода рекурсии.

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

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