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

    Доброго времени суток, Хабралюди!

    Гуру C++, а также люди смыслящие в шаблонном метапрограммировании могут смело пропускать этот топик, ничего нового для себя они здесь не найдут. Однако, если после прочтения заголовка, у вас в голове еще не возникло решение данной задачи (и даже если оно возникло, но не при помощи шаблонов), то милости просим под кат.


    Собственно, решение задачи:
    #include <iostream>
    
    template<int n>
    class Factorial {
    public:
        static const int f = Factorial<n - 1>::f * n;
    };
    
    template<>
    class Factorial<0> {
    public:        
        static const int f = 1;
    };
    
    int main() {
        std::cout << Factorial<5>::f << std::endl; // 120
    }
    


    Давайте разберемся, что к чему. Во-первых, некоторые могут спросить — а почему значение вычисляется на стадии компиляции? Ответ — это основа шаблонов в C++. Специализированный код генерируется на стадии компиляции, в зависимости от того каким типом реально был параметризован шаблон. Суть в том, что если вы используете, например, шаблон функции, которая возвращает минимум двух значений:
    template<class T> const T& min(const T& a, const T& b) {
        return (a < b) ? a : b;
    }
    

    То если использовать в программе, например:
    min(2, 3)
    

    То сгенерируется только специализация для типа int. А если написать, что-то вроде:
    min(2.0, 3.0)
    

    То сгенерируется специализация для double.

    Теперь, возвращаясь к нашему факториалу, можно понять, что для генерации шаблона Factorial<5> должен сгенерироваться шаблон Factorial<4> и так далее до нуля, где в Factorial<0>::f записывается просто единица (за счет явной специализации template<>). Этот последний шаг останавливает «рекурсивную» генерацию шаблонов, после чего вычисляется само значение факториала. Почему на стадии компиляции? Потому что константа static const int f является константой времени компиляции. Если кто-то не верит в это, можете задать какое-нибудь значение шаблона в качестве длины массива, и наблюдать спокойную компиляцию программы.

    В книге Брюса Эккеля Философия С++. Практическое программирование. Приводится следующее решение этой задачи (которое по сути ничем не отличается от вышеописанного):
    template<int n>
    struct {
        enum {val = Factorial<n - 1> * n};
    };
    
    template<>
    struct Factorial<0>{
        enum {val = 1};
    };
    


    Вообще, такое вычисление факториала является частным случаем шаблонного метапрограммирования. Например, возведение в степень q, целого числа p, можно было бы написать циклом:
    int power = 1;
    while (q--)
        power *= p;
    


    Но также можно и при помощи шаблонного метапрограммирования:
    template<int p, int q>
    class Power {
    public:
        static const int value = p * Power<p, q - 1>::value;
    };
    
    template<int p>
    class Power<p, 0> {
    public:
        static const int value = 1;
    }
    


    Более подробно об этом можно прочесть, например, у Эккеля, в книге Философия С++. Практическое программирование, или у Александреску в книге Современное проектирование на C++.

    Спасибо за внимание!
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More
    Ads

    Comments 64

      +2
      Да, это именно то, чего мне не хватало все эти года :-) Если бы каждый программист как-можно больше фич реализовывал с помощью шаблонов — мы жили бы в чудесном мире производительности и ослепительного света прогресса.
        +14
        Прошу прощение, при всем моем уважении к вам — либо у вас сперли аккаунт, либо вы написали бота ) Столько BarsMonster'a на Хабре и в таком формате Мир еще не видывал. Смайлик из прошлого, практически в каждом посте — первый же комментарий, комментарии уровня среднестатистического хабрапетросяна вместо адекватных ответов (с вашим то багажом знаний, блин), топики уровня «поправим пару строк в виндовом реестре на питоне» & etc. Где старый добрый профи с клевым доменом в одной руке и симпатичной сестрой в другой? Неужели ППА головного мозга? Или рейтинг?

        Сорри за выхлоп.
          +2
          Перенервничал? =))
          Noooooooo! My first place on Habr is gone!


          Барс, без обид))
            0
            Да ладно :-)
            Чем больше я там, тем больше хочется прибить акк (или сделать свой с блекджеком).
            Есть всего один топик, который я действительно хочу опубликовать.
              +2
              Чего? Рейтинг на Хабре ведь ни к чему не обязывает. Ну первый ты, ну тысячный, никакой разницы, имхо)
              Топики надо публиковать от души, имхо)
                0
                Вот, ты живешь в чудесном мире, и я рад за тебя :-)
                  0
                  Не, ну честно, а какая разница то?)
                    +1
                    Все банально — для одной из будущих статей нужно быть на первом месте. Ну и мне понравилось как сестра случайно обнаружила меня на первом месте и была в полном шоке :-) — впрочем, это уже не повториться…

                    Самолюбие это само собой не тешит — т.к. на хабре достаточно несложно выйти на первое место — нужно просто подарить много-много своего времени(даже уметь программировать совершенно не обязательно). А дороже времени для меня ничего нет.
                      0
                      Я имею ввиду другое
                      Чем больше я там, тем больше хочется прибить акк (или сделать свой с блекджеком).

                      Чего? Чем так плохо первое место? Оно что есть, что нету.
                        +1
                        Оно что есть, что нету если оно не нужно. А если нужно — тогда это как стоять в середине горной реки :-)
                          0
                          Ну тогда я поделаю тебе волны ;)
                            0
                            Weeeee…
                              0
                              Этот комент сведет мой сервер в могилу ) Я то думаю, откуда столько переходов на мой сайт отсюда… 900 за 2 часа… А как днем все начнут рефрешить коменты…
                              0
                              Черд, не тот урл:
                              PS. Когда уже будет редактирование комментов в течении 5 минут…
                  +3
                  Вот это мысль верная.
                0
                Да-да, сперли :-) Бота все хотел — но пока никак.
                ППА мне не светит, я по прежнему хочу от неё отказаться.

                Насчет уровня можно спорить, но не публично. В данном конкретном случае — вырвалось моя личная неприязнь к злоупотреблению языком — последствия тяжелого детства.
                  0
                  А чего буквы такие маленькие? Стесняетесь что-ли?
                    +1
                    Не хотелось совершенно оффтопный коммент делать на полстраницы, а выхлопнуться нужно было.
                +3
                Ну, все вроде бы супер! Только, в течении 10 минут пытался ответить себе на вопрос — «Где бы мне это понадобилось?». Или пятница-ночь, или я не дорос пока:)
                  +2
                  Александреску и другие замечательно показывают где и зачем. Boost и STL так же.
                    +1
                    Если Вы говорите про метапрограммирование, то оно должно сохранять принципы обобщенного программирования, а в приведенных примерах, я обобщенности не увидел. Но, это как в том бородатом анекдоте: "...-Видишь зайца? — Нет. -Вот и я не вижу, а он есть!":) Буду читать Александреску.
                      –2
                      Без осмысления тривиальных примеров не стоит даже открывать Александреску.

                      Пост является затравкой для привлечения народа к теме + возможный обмен опытом, но никак не best practices и им подобные. Для последнего лучше читать книги Александреску.
                        0
                        Очень даже стоит открывать Александреску. Просто придётся разок-другой перечитать, дабы достигнуть полного сатори от C++ных наблонов.
                          +1
                          Кстати, мне когда советовали Александреску, уточняли, что читать надо лежа на полу, чтобы не откуда падать.
                        • UFO just landed and posted this here
                          0
                          А с чего вы решили, что оно кому-то что-то должно? Оно есть, у него свои возможности, как их использовать — дело каждого.
                          Читайте, читайте, там много полезного.
                        0
                        Такие фокусы как правило используются в библиотеках типа boost для организации несвойственных языку вещей — делегатов, грамматик, кортежей и иже с ними. Грамотная реализация того же делегата требует достаточно сложной шаблонной магии O_O.
                        +13
                        шаблоны должны остаться шаблонами, а не задачкой для реализации машины Тьюринга ))
                          0
                          Как ещё предлагаете заниматься мета-программированием в C++? Ведь это банальное управление генерацией кода, которое рано или поздно понадобится в каком-нибудь сложном софте. C++ — не Lisp, AST-макросов там нет. Выкручиваемся, как можем.
                            +1
                            так где же это может пригодиться за рамками истинного предназначения шаблонов (коллекции, алгоритмы, итераторы и т.п.)? может стоит воспользоваться специализированными инструментами? например, ORM-генераторы классов, если таковые необходимы.
                              0
                              Истинное предназначение шаблонов — удобная и упрощающая разработку генерация кода.
                                –3
                                с чего вы взяли, что шаблоны C++ код генерят?
                                  +1
                                  Есть и те, что непосредственно не генерят. Но, в конечном счёте, они служат именно этой цели: шаблоны обобщают алгоритмы и структуры данных и служат для генерации специализированных версий этих алгоритмов и структур. А это, в свою очередь, позволяет выполнять некоторые вычисления на этапе компиляции, что есть неявная генерация кода. Похоже, вы воспринимаете термин «генерация кода» на слишком очевидном уровне: сгенерить из C++ машинный код.
                                    +2
                                    так всё же, какие вычисления на этапе компиляции необходимы, кроме вычисления типа? я уже второй раз прошу дать пример, имеющий смысл в реальном проекте, если он имеется. в теории все мне понятно. я тоже эту головоломку решал с факториалами, но практического значения в этих «выкрутасах» так и не увидел.
                                      +1
                                      пример: есть подсистема Property, поддерживает из коробки любые типы. Для того чтобы зарегестрировать в системе свойство нужно вызвать MakeProperty:

                                      class CMyObject: public CPropertyEnabled
                                      {
                                      int a;
                                      double x;
                                      std::vector v;

                                      DECLARE_META_CLASS();
                                      };



                                      IMPLEMENT_META_CLASS( CMyObject )
                                      {
                                      // Здесь мы задаем список свойст, поддерживаемых нашим классом
                                      RegisterProperty( MakeProperty( &CMyObject::a, «a» ).release() );
                                      RegisterProperty( MakeProperty( &CMyObject::x, «x» ).release() );
                                      RegisterProperty( MakeProperty( &CMyObject::v, «v» ).release() );
                                      }

                                      // а вот так свойствами можно пользоваться:

                                      CMyObject obj;

                                      MakeTransaction().MakeTrampoline( &obj )
                                      .SetPropertyValue( «a», 1 )
                                      .SetPropertyValue( «x», «1.0» )
                                      .SetPropertyValue( «v», "{1,2,3}" )
                                      .Close();

                                      assert( obj.a == 1 );
                                      assert( obj.x == 1.0 );
                                      assert( obj.v[0] == 1 );
                                      assert( obj.v[1] == 2 );
                                      assert( obj.v[1] == 3 );

                                      А теперь обратите внимание, на то, что
                                      1. RegisterProperty( MakeProperty(… ).release() ) выглядит абсолютно одинаково для свойств совершенно разных типов (у нас в с++ строгая типизация, напомню).
                                      2. Каким-то магическим образом SetProperty может принимать не только реальный тип свойства, но и что-то, что можно в него адекватно сконвертировать (например, строку «1.5» в число 1.5)
                                      3. Свойства контейнерных типов можно использовать так же как и сами контейнеры (но все обращения будут при этом идти через транзакцию, которую можно откатить):
                                      auto oTransaction = MakeTransaction();
                                      auto &rv = oTransaction.MakeTrampoline( &obj, «v» );
                                      std::for_each( rv->begin(), rv->end(), [](… &r ){ r = (int)r + 1; } );

                                      Так вот, это работает, потому как MakeProperty штука хитрая, при компиляции это:
                                      RegisterProperty( MakeProperty( &CMyObject::a, «a» ).release() );

                                      преобразуется приблизительно в следующее:
                                      RegisterProperty(
                                      MakeEmptyProperty( «a» )
                                      .SetSetter( []( CMyObject *p, int v ){ p->a = v; } ) // как устанавливать свойство
                                      .SetGetter( []( const CMyObject *p ){ return p->a; } ) // как читать свойство
                                      .RegisterConversionTrampoline< std::string, int >(… ) // преобразование string->int
                                      .RegisterConversionTrampoline< int, std::string >(… ) // преобразование string->int
                                      .release() );

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

                                      так вот MakeProperty работает на шаблонах: анализируя переданный ей тип она старается как можно более точно описать, как генерировать для него свойства:
                                      * если тип поддерживает сериализацию через стримы, зарегестрировать преобразователи из/в строковые типа
                                      * если тип является константным не регестрировать setter (тогда свойство будет ридонли)
                                      * если тип контейнер, зарегестрировать логику, специфичную для контейнеров и т.п.
                                    +2
                                    шаблоны — полный по тьюрингу чисто функциональный язык, оперирующий типами. с помощью шаблонов генерируются новые типы классов.
                                      0
                                      кроме вычисления типа и генерации классов (методов, функций) нужны ли еще какие-то возможности от шаблонов? я думаю, что нет. так как при технической возможности вычислять факториал на этапе компиляции, затраты на реализацию подобного простейшего алгоритма чудовищны. проще отдельный генератор написать, если так уж необходимо генерировать исходный код. свою же шаблонную роль шаблоны отлично выполняют ))
                                        +1
                                        Шаблоны позволяют определять такие штуки как:
                                        * наследуется ли А от B?
                                        * имеет ли А функцию-член f()
                                        * и т.п.

                                        Эти вещи очень сильно бывают нужны в обобщенном коде.

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

                            +7
                            Вот тут: www.oonumerics.org/blitz/examples/fft.html вычисляют Fast Fourier Transform на этапе компиляции.
                              0
                              Вот ещё подобный топик про CRC32:
                              habrahabr.ru/blogs/crazydev/38622/
                                +2
                                А смысл? Если мне нужно вычислить преобразование фурье некоего константного сигнала, я пишу простую и понятную программку (без всякой там шаблонной магии), с обычными циклами, а результат просто забиваю в Си-шный массив. Смысл мозг пудрить?
                                • UFO just landed and posted this here
                                    0
                                    Можно но не очень удобно когда нужно объявлять такие числа часто (например в разных исходных файлах) или они часто меняются по мере разработки.
                                    0
                                    Это такой чистый акт творчества. Как и вычисление факториала на этапе компиляции — практического применения не имеет.
                                    0
                                    Да и вообще, по ссылке не вычисляют FFT, а разворачивают в линейный код — это большая разница.
                                    0
                                    Если таки вы попробуете сказать
                                    min(2.0, 3)

                                    специализация для дабла не сгенерится, а сгенерится ошибка компиляции. В случае вашего шаблона придётся писать:
                                    min<double>(2.0, 3)

                                      0
                                      Полностью согласен, ошибка исправлена.
                                    • UFO just landed and posted this here
                                        0
                                        Ну дык, факториал на шаблонах и есть забава. Но вообще шаблонное мегапрограммирование попрошу не трогать!
                                        • UFO just landed and posted this here
                                            0
                                            Спасибо, посмеялся :-) Я его не то чтобы люблю, это просто как глоток свежего воздуха после повседневного мяса.
                                            0
                                            Пошли на мою работу сходим, подебажим и порефакторим твои любимые шаблоны ;-)
                                            Только нужно учитывать, что за рабочий день мы проект собрать сможем только 1 раз ;-)
                                              +1
                                              Извиняй, до тебя далеко добираться :-)
                                          +5
                                          Спасибо, Кэп! (простите, не сдержался)
                                            +1
                                            Как-то давно, узнав о такой возможности, написал вычисления определителя матрицы в compile-time.

                                            Кстати, интересно, что МП на шаблонах в Си++ — чистый функциональный язык.
                                              +2
                                              ага, только при оптимизациях и функция вычисляющая факториал редуцируется до своего значения, а вашу байду нельзя применить для переменных
                                              This is useless, sad but true
                                                0
                                                У Васи было два компьютера. Один он выбросил в окно. Сколько компьютеров осталось у Васи?

                                                Вроде всё правильно, но бессмыслица абсолютная. Присоединяюсь к мнению тех, кто считает, что демонстрационные задачи должны быть интересными и жизненными.
                                                +1
                                                Меня в свое время очень сильно впечатлило использование шаблонной магии применительно к микроконтроллерам для абстрагирования драйвера внешнего устройства от пинов, к которым оно подключено.
                                                easyelectronics.ru/rabota-s-portami-vvoda-vyvoda-mikrokontrollerov-na-si.html
                                                  0
                                                  Где же я видел эту идею? А, вот тут: Printing 1 to 1000 without loop or conditionals
                                                    0
                                                    Идее уже больше десяти лет вообще-то :-)
                                                    +1
                                                    В следующем стандарте будет интереснее (попробовать можно уже сейчас: gcc.gnu.org):
                                                    constexpr int fact(int n)
                                                    {
                                                    if (n > 0)
                                                    return fact(n - 1);
                                                    else
                                                    return 1;
                                                    }
                                                    double array[fact(5)];


                                                    Или даже ещё лучше:

                                                    struct CompileTimeMap {
                                                    size_t hash;
                                                    const char* val;
                                                    } ctmap[] = { hash("123"), "123" };

                                                    Плюс обобщить макросом вида "#define CTH(str) hash(str), str".
                                                      +1
                                                      В § 7.1.5 п. 3 говорится, что в теле constexpr функции может быть только один return и никаких if.
                                                      Т.е. хотя бы так:

                                                      constexpr int fact(int n) { return n > 0 ? fact(n - 1) : 1; }
                                                        0
                                                        Совершенно верно.

                                                    Only users with full accounts can post comments. Log in, please.