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

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

19 голосов
/ 21 июня 2010

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

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 ++ я упускал?

Спасибо!

Ответы [ 5 ]

23 голосов
/ 21 июня 2010
  • Что это за странный шаблон, который занимает <int N>?

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

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

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

  • Для чего нужны перечисления?

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

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

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

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

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

6 голосов
/ 21 июня 2010

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

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

Является ли "этим" вы относитесь к рекурсивному вычислению константы?Если да, то не часто.

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

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

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

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

4 голосов
/ 21 июня 2010

Я нашел этот ответ от Йоханнес Шауб - 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
};
3 голосов
/ 21 июня 2010

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

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

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

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

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

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

2 голосов
/ 21 июня 2010

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

template <>
struct Factorial<0>
{
}

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

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

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

...