Метапрограммирование. Часть 2. Продвинутый уровень.

Базовые типы

В мире метапрограммирования 11-го стандарта "под капотом" все несколько сложнее, взамен простому объявлению __is_integer добавлен шаблон std::is_integral, А взамен объявления пустых структур, как типов истинности, появляется базовый класс std::integral_constant, содержащий несколько больше данных внутри себя, а соответственно и возможностей применения. Например - оператор преобразования к типу. И уже на базе него строятся типы истинности, хотя в общем идея абсолютно та же.

template<typename _Tp, _Tp __v>
  struct integral_constant
  {
    // Тут будет хранится переданный тип но в виде статического члена (статика
    // нужна чтобы иметь возможность что-то хранить, не создавая экземплра объета)
    static constexpr _Tp                  value = __v;
 
    // тут будет хранится описание переданного в шаблон типа
    typedef _Tp                           value_type;
    // Очень интересный подход - сохранение имени своего типа внутри себя
    // чем-то похоже на поле next в односвязном списке, только хранится не
    // объект а имя типа.
    typedef integral_constant<_Tp, __v>   type;
    // Операция приведения к типу (может быть использована во время выполнения
    // и во время компиляции, но в инстанцировании шаблонных параметров, а в
    // constexpr функцих.
    constexpr operator value_type() const { return value; } // #001
  };
// Инициализация статического элемента класса.
template<typename _Tp, _Tp __v>
  constexpr _Tp integral_constant<_Tp, __v>::value;

#001 -- обратите на внимание на шаблонную обертку и сравните с этим

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

/// The type used as a compile-time boolean with true value.
typedef integral_constant<bool, true>     true_type;
 
/// The type used as a compile-time boolean with false value.
typedef integral_constant<bool, false>    false_type;
 
template<bool __v>
  using __bool_constant = integral_constant<bool, __v>;

Кстати, здесь мы видим using. В таком исполнении это ключевое слово идентично typedef, и является псевдонимом (alias) семейства шаблонов, в данном случае используется для сокрытия первого шаблонного параметра integral_constant, делая как бы частичное специализацию integral_constant под новым именем. Подробнее:
здесь и тут.

И вот так объявлен, стандартизованный __is_integer (is_integral):

  template<typename>
    struct __is_integral_helper
    : public false_type { };
 
  template<>
    struct __is_integral_helper<bool>
    : public true_type { };
 
  template<>
    struct __is_integral_helper<char>
    : public true_type { };
 
 //.....
 //.....
 //.....
 
  template<>
    struct __is_integral_helper<unsigned long long>
    : public true_type { };
 
  template<typename _Tp>
    struct is_integral
    : public __is_integral_helper<typename remove_cv<_Tp>::type>::type
    { };

Сравните еще раз как это было в 98-м и в более новых стандартах - очень похоже. remove_cv - снимает константность и volatile спецификацию с типа, это нужно чтобы "очистить" имя типа, чтобы __is_integral_helper с ним правильно отработал.

constexpr

В Си++11 появилось новое ключевое слово constexpr - про его особенности есть длинная статья на Хабре, которую пока, увы не прочел.

Вкратце - этот спецификатор объявляет что выражение является константным, почти тоже самое что const, но классический const служит для указания константности объекта во время выполнения программы, а constexpr для описания константности во время компиляции. Разница между const и constexpr хорошо описана здесь.

Это очень важное ключевое слово, т.к. в матапрограммировании возможно оперировать только типами и константами времени компиляции. Поэтому если объявляется константа, или тем более некоторая что-то возвращающая функция, то нужно использовать constexpr, для возможности использования этих сущностей во всех выражениях времени компиляции.

Логические операции

В 11-м Си++ содержится весь необходимый набор логических операций (вероятно они не стандартизованы (т.к. их описания в интернете я не находил), но их замечательно можно использовать). Кстати 14-й стандарт, называют небольшим патчем к 11 (т.е. разница между 98 и 11 большая, а вот между 11 и 14 нет) =)

template<typename... _Bn> struct __or_;
template<typename... _Bn> struct __and_;
template<typename _Pp> struct __not_;
// данные структуры представляют собой тип true_type или false_type,
// преобразовываться к bool типу, и могут быть инстанцированны
// произвольным количеством параметров (кроме __not_), эмулируя стандартные логические операторы

Подробнее здесь.

Манипуляции с типами

//Удаление модификатора const
template<typename _Tp> struct remove_const
 
//Снятие константности и volatile спецификации с типа
template<typename _Tp> struct remove_cv
 
//Проверка на void тип
template<typename _Tp> struct is_void
 
//Определение на массив
template<typename _Tp> struct is_array
 
//Определение типа ссылки (rvalue/lvalue) 
template<typename _Tp> struct is_lvalue_reference
template<typename _Tp> struct is_rvalue_reference
 
//Определение является ли элемент ссылкой
template<typename _Tp> struct is_reference
 
//Определение является ли объект функцией/функциональным объектом или методом
template<typename _Res, typename... _ArgTypes> struct is_function
 
//Определение является ли объект ли этот тип
template<typename _Tp> struct is_object
 
//Определение  может ли объект передаваться по-ссылке
template<typename _Tp> struct __is_referenceable
 
//Добавление lvalue и rvalue ссылки к объекту
// add_lvalue_reference
template<typename _Tp> struct add_lvalue_reference
// add_rvalue_reference
template<typename _Tp> struct add_rvalue_reference

Подробнее здесь.

Проверка возможности преобразования одного типа в другой

template<typename _From, typename _To>
  struct is_convertible
  : public __is_convertible_helper<_From, _To>::type
  { };
  // Эта структура наследует свойства типа true_type или false_type

Определение базового класса для is_convertible

template<typename _From, typename _To,
  bool = __or_<is_void<_From>, is_function<_To>,
  is_array<_To>>::value> 
  struct __is_convertible_helper
  { typedef typename is_void<_To>::type type; };
 
template<typename _From, typename _To>
  class __is_convertible_helper<_From, _To, false>
  {
    template<typename _To1>
    static void __test_aux(_To1);
 
    template<typename _From1, typename _To1,
         typename = decltype(__test_aux<_To1>(std::declval<_From1>()))>
      static true_type
      __test(int);
 
    template<typename, typename>
      static false_type
      __test(...);
 
    public:
      typedef decltype(__test<_From, _To>(0)) type;
  };    

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

template<typename _From, typename _To,
  bool = __or_<is_void<_From>, is_function<_To>,
  is_array<_To>>::value>
  // если первый void или второй ф-я или массив, то тут (в bool типе шаблона) будет истина
  // ( как мы видели выше эти классы преобразуемы к стандартному типу bool,
  // но тут ручное обращение к значению )
  //
  // Основная специализация будет инкапсулировать истину 
  // если второй парамерт тоже void (учтём что просто void переменных не существует)
  //
  // Cтоит понимать что is_void<T>, где T есть тип ф-ии (очищенной от указателя, не очищенная,
  // понятно что не подойдет тоже, т.к. буде являться указателем). Очищение, напомню делается
  // так decltype(/*имя void функции*/) – не подойдет для отработки is_void, т.к. в T будет тип ф-ии
  // (как говорилось выше это отдельный тип, существующий в шаблонах), проверять же тип
  // ф-ии (в том смысле тот, который она возвращает) можно таким способом
  // std::is_convertible<void,decltype(foo())>::value, или foo()(), если foo функтор. При этом стоит
  // помнить, что функторы не являюся ф-ями.
  // В общем говоря в этой основной версии шаблона на истину работает только
  // void->void ну и при некоторых внешних условиях void -> foo() | -> foo()()
  // – где foo() «вызвана» через decltype и является void ф-ей | функтором. Всё. 
  //
  //  Массивы же не могут быть void.
  //  Могут быть void* но данный случай - _From=void*, _To=void* array - обработается не
  //  в первой версии а в перегрузке шаблона, т.к. is_void не умеет работать с указателями 
  // на void* но успешно обработается ниже. 
  // Пруф для проверки: template <class A, class B>void foo2(A a, B b){  a = b; } 
  //  здесь оба элемента уже указатели, поэтому "возможно невозможное"
  // arr /*int arr[]*/ = ptr /*int *ptr*/ так же и с void за исключением того что void arr[]
  // невозможен, но возможен void * arr = new some_one[count] - что по сути будет
  // void arr[]. Т.е. (_From=void*, _To=void* array) == (_From=void*, _To=void array[])
  //
  // Understand? ) идем дальше, самое интересное впереди!
  //
  // во всех других случаях (преобразование к ф-ии или к массиву), внезависимости от
  // типа _From итоговый результат будет false_type, т.к. не существует преобразования
  // в указанные типы (не возможно что-то преобразовать в ф-ю* или массив**)
  // ** кроме случая показанного выше int[]=int* или void*/*==void[]*/=void*.
  // * is_convetible<decltype(foo),decltype(foo)> - будет false - т.к. тип ф-й не существует
  // вне шаблонов, и компилятор не умеет проверять возможность такого 
  // неявного преобразования
  struct __is_convertible_helper
  { typedef typename is_void<_To>::type type; };
 
// просто на память - void невозможно преобразовать ни во что, т.к. это пустой тип
// и ничто нельзя преобразовать в void (не путать с void*), к которому можно неявно
// преобразовать что угодно, но в чтолибо из void* преобразовать неявно нельзя.
 
// Посмотрим на специализацию:
template<typename _From, typename _To>
  class __is_convertible_helper<_From, _To, false>
  {
    // объявляем ф-ю, но она останется только объявленной, её определение не нужно
    // объявление будет служить для осуществления возможности передавать в неё
    // параметры...
    template<typename _To1>
    static void __test_aux(_To1);
 
    // т.к. она статическая, мы можем обращаться к ней не создавая реальные объекты...
 
    // через обращение к __test_aux объявляем шаблон для __test
 
    // далее, т.к. __test_aux должен быть актуализироан _To1 а в _To1 передается _From1
    // то такой путь компилятор выберет лишь в том случае когда такое преобразование
    // возможно. В случае если же оно не возможно, компилятор выберет версию ф-ии с
    // интерфейсом со множественной передачей параметров
    // ( изначально она не выбирается, т.к. предпочтитительнее именно с одиним
    // параметром )
 
    // зачем нужен 3-й параметр при инстанцировании? да потому что ф-ии не имеют тела,
    // и связать вызов одной ф-ии из другой (не имеющих тела) можно через
    // такую вот шаблонную связь. Хитро, хитро :)
 
 
    // также стоит понимать и помниь что в _From1 лежит описание типа, а не конкретная
    // переменная, например при вызове конструктора дека, в первый параметр попадет
    // vct1.begin(). 
    // _From1 же будет не результатом вызова vct1.begin(), а его типом, т.е.
    // std::vector<int>::iterator.
    template<typename _From1, typename _To1,
                    // #002              #004       #003
         typename = decltype( __test_aux<_To1>( std::declval<_From1>() ) )> // #004
      static true_type
      __test(int);
 
    template<typename, typename>
      static false_type
      __test(...);
 
    public:
      typedef decltype(__test<_From, _To>(0)) type;
  };

#002 - оператор (с++11) decltype объявляет тип по выражению. Чем-то похоже на typedef, но typedef - определяет синоним типа по имени типа, а decltype объявляет тип переданного в него объекта. Пример.

decltype в данном случае необходим чтобы в typename записать тип (void), вызвать без decltype сразу на прямую __test_aux - невозможно, т.к. в типовой параметр шаблона может передаваться только имя типа, а не объект типа (если бы стояло например не typename=, а _To1= (т.е. некоторое заранее известное имя типа, без слов class или typename - то это был бы уже не типовой, а назовём его объектный параметр шаблона (далее в статье он будет зваться "нетиповым"), в который уже можно передавать конкретные объекты.

#003 - почему бы не вызвать сразу __test_aux<_To1>(_From1()) и тем самым предоставить доступ к типу, который возвращает __test_aux. Такой вызов возможен, и в большинстве случаев отработает, но это не универсальное решение, т.к. _From1 возможно будет являться классом, не имеющим конструктора по-умолчанию.

/* Кто-то может подумать "а зачем вообще конструировать объект, ведь можно передать сразу имя типа - т.е. _From1" - нельзя - т.к. это лишь описание типа, а для анализа нам нужно указать компилятору что-то более вещественное и ощутимое чем просто описание типа - а это есть создание элемента данного типа. Это можно воспринять как инициализацию константного выражения (времени компиляции), по которому будет строиться дальнейший алгоритм анализа. */

Именно для этой цели используется std::declval.

Как это работает:

declval это создающая функция, которая говорит компилятору, что он, после её вызова, имеет дело с элементом типа std::add_rvalue_reference::type - т.е. правосторонней ссылкой на объект. Если тип представлен как правосторонне-ссылочный, то компилятор воспринимает его как некоторый уже существующий объект-константу. Так и происходит "обман", и возможность получать экземпляр класса, который фактически не может быть создан через _From1() - т.е. конструирование по-умолчанию. Если посмотреть на объявление declval- то это, грубо говоря, пустая ф-я, которая синтаксически "обманывает" компилятор в том вопросе, что ничего не создает, но в сигнатуре возвращаемого значения имеет правостороннюю ссылку на объект (т.е. компилятор такую ссылку воспринимает как то что объект уже создан), поэтому её применяют для определения типа класса (объекта класса), или для доступа к методам или полям класса, не имеющего конструктора по умолчанию, с целью получить из них тип, который они возвращают), при этом это только интроспективный доступ к типам полей и методов, использовать метод или поле объекта такого класса невозможно (на самом деле возможно, но от такого использования стоит защита). Подробнее про работу std::declval можно прочитать здесь.

/* Для понимания всей механики, нужно помнить, что это касается обычных методов в классе, что к ним невозможно получить доступ (и к их типам) не создав объект - это хорошо видно в примере тут, а вот к статическим методам и их типам, естественно, можно получить доступ, не создавая объект вообще, или не эмулируя его создание, как это делает std::declval */

таким образом std::declval<_From1>() гарантирует что объект, даже если он не имеет конструктора по-умолчанию будет "создан" - а точнее не создан, а описан, причем как созданный, и компилятор начнет пробовать передать этот элемент в __test_aux, с оценкой того возможно ли его передать (полное соответствие типов или возможность неявного преобразования) или же, в случае невозможности - будет выбрана вторая версия ф-ии __test.

#004 - в коде видно немного странное обращение к вызову шаблона функции __test_aux<_to1>(some value)

__test_aux<_To1>(some value)

Обычно во большинстве статей и учебников можно видеть только такое использование шаблонный ф-й

__test_aux(some value)

Но существует способ принудительного вызова нужной перегрузки (т..е перегрузка генерируетcя автоматически)

Например есть шаблон

template <class T> void foo (T v) { std::cout << "V1 " << v << std::endl; }

Если его использовать так

foo(13.5);

То выведется V1 13.5 как и должно быть. А если так:

foo<int>(13.5);

То автоматически создастся версия инстанцированная для типа int (и имеющая тело базовой версии), double значение неявно будет преобразовано к int, и на экран выведется V1 13.

Если интересно - можно поиграться с этим:

template <class T> void foo (T v) { std::cout << "V1 " << v << std::endl; }
template <> void foo<int> (int v) { std::cout << "V2 " << v << std::endl; }
...
foo<int>(13.5);                // V2 13
foo(static_cast<int>(13.5));   // V2 13
foo(13.5);                     // V1 13.5

Таким образом, здесь

__test_aux<_To1>(some value)

Создается специализация для конкретного типа _To1, для проверки возможности передачи в него some value.

Ещё возможно и такое :)

template <class T> void bar () { std::cout << "B1\n"; }
template <> void bar<int> () { std::cout << "B2\n"; }
...
bar<int>();    // B2
bar<double>(); // B1

Но я отвлекся, продолжаем по-теме...

SFINAE

SFINAE - это свойство, доступное в Си++ довольно таки давно, в том числе и в стандарте 98.

Попросту говоря - это соглашение, при котором ошибки возникшие во время инстанцирования шаблона, связанные с отстутсвием неободимых данных (внутри других данных - т.е. например класс A не содержит поле B, хотя при инстанцировании идёт обращение к полю B) - не считаются ошибками, а шаблон, который невозможно инстанцировать по причине отсутствия необходимых данных просто исключается из списка кандидатов на перегрузку. SFINAE применяется только для перегруженных версий функций/методов, причем только шаблонов. /*т.е. если в ф-ии или методе foo применяется sfinae то эта ф-я/метод должна являться шаблоном, и при этом должна являться перегруженной версией такой же foo либо тоже являющейся шаблоном, либо не шаблонной версией. Иначе компилятор не сможет выбрать правильный путь и выдаст ошибку */ SFINAE использует автоматический вывод типа по входному аргументу функции компилятором. Поэтому SFINAE может применяться только при инстанцировании шаблонов функций или методов классов но не при специализации шаблонов самих классов. Но возможны трюки, когда можно выбирать на стадии компиляции по наличию или отсутствию полей основную или специализировнную версию шаблонного класса, для этого можно пользоваться создающими функциями, работающими с sfinae и создающие нужную версию шаблонного класса, или же определение наличие типа внести в параметр шаблона класса, как это сделано в iterator_traits

SFINAE работает только на "первом уровне" - т.е. может использоваться только среди параметров описания шаблона, или описания возвращаемого ф-ией значения, или среди параметров функции/метода, и проявляет себя только в процессе инстанцирования. Поэтому схожее обращение A::B в теле функции/класса, при условии что А не содержит B приведет к ошибке компиляции, т.к. тут уже никакого SFINAE не работает.

В Си++11 в стандарт был включен класс std::enable_if

template <bool C, typename T = void> struct enable_if{};
template <typename T> struct enable_if<true, T> { typedef T type; };

Который весьма удобно инкапсулирует в себе принципы SFINAE для определения стоит ли исключать данный объект из кандидатов на перегрузку.

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

#include <iostream>
#include <vector>
#include <utility>
 
template <class T> class deque
{
public:
    deque ( unsigned a, int b) { std::cout << "1\n"; } //1
 
    template
    <
        class _InIter, typename = 
            typename std::enable_if
            < 
                    std::is_convertible
                    < 
                        typename std::iterator_traits<_InIter>::iterator_category,
                        std::input_iterator_tag
                    >::value
            >::type
    >
    deque(_InIter _first, _InIter _last) { std::cout  << "2\n"; } //2
 
};
 
int main()
{
    deque<int> dq1 (10,-1); //1
 
    int arr[]={1,2,3,4};
    deque<int> dq2 (arr,arr+4); //2
 
    std::vector<int> vct1 (arr,arr+4);
    deque<int> dq3 (vct1.begin(), vct1.end()); //2
}

Всё очень красиво и понятно. Сначала std::is_convertible осуществляет проверку на возможность преобразования итератора к типу input_iterator_tag.

Т.к. итераторы состоят в иерархии - любой может быть неявно приведён к базовому типу, которым как раз и является input_iterator_tag. Это не всегда освящается в книжках, как правило в них лишь говорят о возможности передавать по ссылке или указателю на базовый класс - производный класс. Так как производный класс, это своего рода есть надстройка над базовым - то такое преобразование можно рассматривать как преобразование double -> float на машинах с остроконечным порядком байтов, когда надстройка ("лишние" поля) усекается. Обратное же преобразование - т.е. базового в производный, в отличие от float -> double невозможно.

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

Проверить возможность передачи просто:

struct iinput_iterator_tag {};
struct rrandom_access_iterator_tag : public iinput_iterator_tag  {};
void test (iinput_iterator_tag d) { std::cout << typeid(d).name() << '\n'; }
...
test (rrandom_access_iterator_tag()); // -- Ok, преобразование типа к базовому классу

А далее std::enable_if определит, включится ли или будет исключена данная инстанция шаблона их кандидатов на перегрузку.

Кстати, предварительно объявив такой шаблонный псевдоним к std::enable_if

template<typename _InIter>
  using _RequireInputIter = typename
    std::enable_if <
        std::is_convertible < 
            typename std::iterator_traits<_InIter>::iterator_category, std::input_iterator_tag
        >::value
    >::type;

2-й конструктор можно записать значительно красивее:

template<class _InIter, typename = _RequireInputIter<_InIter> >
deque(_InIter _first, _InIter _last) { std::cout  << "2\n"; }

И вот, благодаря SFINAE и шаблонам с параметрами по умолчанию для функций в Си++11 конструкторы дека будет исполнять именно свои роли, в отличии, от упомянутого из первой части статьи.

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

Так же, т.к. в шаблонах функций нет параметров по-умолчанию, то SFINAE не может работать на уровне описания параметров шаблонов, а только на уровне интерфейса ф-ий. При этом конечный параметр, играющий роль "определителя" включать или исключать из сборки - удобно объявить указателем, чтобы к нему можно было применить значение по-умолчанию, равное нулю.

Различие подхода к SFINAE в 98 и последующих стандартах хорошо описываются тут и тут (особенно видно на 19-й стр)

#include <iostream>
#include <iterator>
#include <vector>
// относительно длинный блок объявлений упомянутых выше структур,
// которых нет в 98-м стандарте.
//...
// т.к. у нас нет is_convertible (а её нет, из-за отсутстия decltype)
// то, чтобы не придумывать аналог, будем использовать перегрузку:
template <class X> struct convertible_to_input_iter:
public false_type {};
 
template <> struct convertible_to_input_iter
<std::input_iterator_tag>: public true_type {};
 
template <> struct convertible_to_input_iter
<std::random_access_iterator_tag>: public true_type {};
 
template <> struct convertible_to_input_iter
<int*>:public true_type {};
 
template <class T> class deque
{
public:
    deque ( unsigned a, int b) { std::cout << "1\n"; }
    template <class _InIter> deque ( _InIter a, _InIter b,
    typename enable_if<
        convertible_to_input_iter< typename std::iterator_traits<_InIter>::iterator_category>::value
        >::type* = 0 )
    { std::cout  << "2\n";};
};
 
int main()
{
 
    deque<int> dq1 (10,-1); //Error:
    // error: ‘int’ is not a class, struct, or union type
 
    int arr[]={1,2,3,4};
    deque<int> dq2 (arr,arr+4); //2
 
    std::vector<int> vct1 (arr,arr+4); //
    deque<int> dq3 (vct1.begin(), vct1.end()); //2
}

Видем ошибку, кстати, которой нет в С++11 - все потому что в 11-м iterator_traits дружелюбен к SFINAE :)

Решением данной проблемы может послужить обертка, с необходимым набором перегрузок для указания типа итератора.
И соответственно итоговый код второго конструктора, при котором в Си++98 будут вызваны именно те конструкторы, которые предполагает интерфейс.

template <class _InIter> deque ( _InIter a, _InIter b,
    typename enable_if<
        convertible_to_input_iter<
        typename iterator_traits_proxy<_InIter>::iterator_category>::value
    >::type* = 0 )
{ std::cout  << "2\n";}

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

/* Кстати, изучая данную темку обнаружил что: в предыдущем стандарте в константных выражениях можно было использовать переменные только целого типа или типа перечисления а в Си++11 это ограничение снято (ссылка на вики). Имеется в виду та проблема, с которой столкнулся человек здесь - т.е. статические константы, которые _определяются_ прямо в классе, а не за его пределами. Но, во всех моих версиях компиляторов - даже для стандарта 98 года такие статические константы могут быть иметь любые типы, но кроме константных массивов, в 11-м же все можно, с constexpr. Подробнее тут.*/

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

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

Итоги

На примере STL мы подробно разобрали SFINAE, и служащаю для sfine технику применения шаблонов и специализаций для определения типов и рассмотрели как на основе шаблонов можно определить логические операции &&, ||, и !.

Стоит запомнить:

• В метапрограммировани оперируют типами и константами времени компиляции.
• Техника определения типа состоит в определении общего шаблона для всего, что не этот тип и в специализации шаблона, которая соответствует этому типу.

С помощью этой же техники реализованы преобразования типов, например std::remove_pointer и все другие, подобные задачи.

• Шаблоны для своей актуализации могут вызывать другие шаблоны, а иногда и сами себя (см. __or_) в таком случае образуется рекурсивный вызов шаблоном самого себя. Условием выхода из рекурсии в метапрограммировании является специализация шаблона, которая останавливает рекурсию.
• В вычислениях во время компиляции (о них пойдет речь ниже) так же часто применяется рекурсия.
• В си++98 в качестве констант времени компиляции могли быть только целочисленные типы (существующие в классе как static), или как перечисляемый тип (который по определению константен). В последующих стандартах константами времени компиляции могут быть любые величины.
• В 98-м невозможно было в вычислениях времени компиляции использовать вызов ф-й, которые что либо возвращают, в новых стандартах возможно, если ф-я объявлена как constexpr.

Типичный для 98-го стандарта способ определения итератор ли объект (использующий SFINAE):

template<typename T>
struct is_iterator
{
private:
    typedef char                      yes;
    typedef struct { char array[2]; } no;
 
    template<typename C> static yes test(typename C::pointer);
    template<typename C> static no  test(...);
public:
    static const bool value = sizeof(test<T>(0)) == sizeof(yes);
};
template <typename T> bool iterator_type(T)
{
    // т.к. компилятор умеет выводить из переменной её тип и автоматически
    //  подставлять выведенный тип в типовые параметры шаблона  только для
    // функций, то единственный способ передать тип существующего объекта
    // в инстанцирование шаблона - это обернуть создание объекта в
    // "создающую" ф-ю.
    return is_iterator<T>::value;
}

Кстати - виднен вызов ф-ии sizeof, а мы помним, что в 98-м нельзя использовать ф-ии в константных выражениях времени компиляции. И будь бы на месте sizeof какая-нибудь ф-я, возвращающая некий параметр - во время компиляции была бы ошибка (но, повторюсь, в новом стандарте её бы не было, если ф-я объявлена как constexpr). Дело в том что sizeof это не ф-я, а оператор языка, и при этом оператор времени компиляции:
Т.е. данный код выведет только число 4 (размер типа ф-ии)

int x(int a){
    std::cout << a;
    return a;
}
...
std::cout << sizeof ( x ( 20 ) );

Типичный для новых стандартов способ:

template<typename T>
struct is_iterator
{
private:
    template<typename C> static true_type test(typename C::pointer);
    template<typename C> static false_type  test(...);
public:
    typedef  decltype(test<T>(0)) type;
};
template <typename T> bool iterator_type(T)
{
    return is_iterator<T>::type::value;
}

От SFINAE к вычислениям во время компиляции

Всё что мы рассмативали выше - это рассматрение того, как "под капотом" работает sfinae. Естественно, метапрограммирование не ограничивается только преобразованиями типов. Уже на том что мы рассмотрели выше, можно увидеть ещё одну область метапрограммирования - а именно расчетов на этапе компиляции.

Мы видили это в этой строке. В ней вычисляется значение value.

static const bool value = sizeof(test<T>(0)) == sizeof(yes);

После компиляции, в программе, все строки

is_iterator<T>::value;

будут заменены вычисленным значением true или false.

Можно пойти дальше... Все что будет описано ниже, применимо и в 98 стандарте.

Классический пример - вычисление факториала, которое как правило значительно проще реализовать рекурсивно:

int64_t factorial (int64_t n) 
{ return (n==0) ? 1: n*factorial(n-1); }

Но это крайне нехорошее решение. Почему рекурсия времени выполнения это плохо - описывалось тут.

Вот решение получше:

template <typename T> int64_t factorial(T N)
{
    if (N < 0)
        return 0;
    if (N == 0)
        return 1;
 
    int64_t result = 1ll; //long long == int64_t
    for (unsigned i = 1; i <= N; i++) {
        result *= i;
    }
    return result;
}

Но, можно сделать решение, работающее ещё быстрее, чем итеративное вычисление факториала - а именно вычислять его на этапе компиляции:

// шаблон для вычисления
template <int n> 
struct factorial_c
{
  enum { value = factorial_c<n-1>::value * n }; 
};
 
// условие выхода из рекурсии
template < > 
struct factorial_c<0>
{
  enum { value = 1 }; 
}; 

Можно сделать ещё лучше ( позволит вычислять бОльшие значения факториала) Кстати видно, можно подумать - как статическая константа (которая существует в единственном экземпляре среди объектов класса) - используется со многими значениями в рекурсии. Дело в том что она одна и есть, просто специализация шаблона - это уже совершенно другой класс, и соответственно другой объект, со своей статической константой, но с тем же именем.

template <int n> 
struct factorial_c
{ 
    static const int64_t value = factorial_c<n-1>::value * n;
};
 
template < > 
struct factorial_c<0>
{
    static const int64_t value = 1 ; 
}; 

Теперь, на стадии выполнения программы вычислений не будет, т.к. в коде теперь везде вместо factorial_c<5>::value - будет результат вычислений.

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

Важные отличия между вычислениями на этапе выполения и вычислениями на этапе компиляции:

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

Вычисление выражений

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

/* Если далее если не очень понятен текст - то можно спустить ниже и посмотреть код, потом прочитать что было выше. =) */

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

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

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

Скалярное произведение — можно рассматривать как частный случай паттерна проектирования, называемого «Компоновщик» (composite). Данный паттерн представляет отношение «часть-целое» так, что клиент может игнорировать различия между отдельным объектами или композицией этих объектов. Ключевыми объектами являются leaf (лист, примитивный объект) и composite (композиция, составной объект).

• Leaf — определяет поведение примитивных объектов.
• Composite — определяет поведение компонентов, состоящих из листьев.

Примерами данного паттерна можно считать рекурсивные алгоритмы, рекурсивные структуры данных и синтаксические деревья.

Рис.1 Типичная структура составного объекта.

В GoF описана объектно-ориентированная версия патерна Composite c абстрактным базовым классом, который определяет общую для leaf и composite операцию и два производных класса, определяющих leaf и composite.

Рис.2. Uml-диаграмма классов паттерна Composite.

Для скалярного произведения leaf — это скалярное произведение двух векторов размерности 1. А composite — скалярное произведение двух векторов размерности N-1.

Рис.3. Структура паттерна Composite для скалярного произведения.

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

Рис.4. Uml-диаграмма классов скалярного произведения на базе паттерна Composite.

// Базовый класс
template <class T> 
class DotProduct
{ 
public: 
    virtual ~DotProduct ( ) { } 
    virtual T eval( ) = 0; 
};
 
// класс выдающий произведение двух точек (примитивный объект)
template <class T> 
class SimpleDotProduct : public DotProduct <T>
{ 
public: 
    SimpleDotProduct ( T * a, T * b ) : v1(a), v2(b) { } 
    virtual T eval( ) { return (*v1)*(*v2); } 
private: 
    T* v1; T* v2; 
};
 
// Класс связывающий произведения точек (составной объект)
template <class T> 
class CompositeDotProduct: public DotProduct <T>
{ 
public: 
    CompositeDotProduct ( T* a, T* b, size_t dim ):
    s(new SimpleDotProduct<T>(a,b)),
    c ( dim==1 ? 0 : new CompositeDotProduct <T> ( a+1,b+1,dim-1 ) )
    { } 
    virtual ~CompositeDotProduct ( ) { delete c; delete s; } 
    virtual T eval ( ) { return ( s->eval( ) + ( (c) ? c->eval( ) : 0 ) ); } 
protected: 
    SimpleDotProduct    <T> * s; 
    CompositeDotProduct <T> * c; 
};
 
// вспомогательная функция
template <class T> T dot ( T * a, T * b, size_t dim )  
{
    return (dim==1)
         ? SimpleDotProduct<T>(a,b).eval() 
         : CompositeDotProduct<T>(a,b,dim).eval(); 
}

Кстати, очень интересный подход - класс поражает сам себя рекурсивно в конструкторе!

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

template <class T> 
class DotProduct
{ 
public:
    virtual ~DotProduct ( ) { }
    virtual T eval( T *, T *, size_t ) = 0;
};
 
template <class T> 
class SimpleDotProduct: public DotProduct <T> { 
public:
    virtual T eval(T* a, T* b, size_t)  { return (*a)*(*b); } 
};
 
template <class T> 
class CompositeDotProduct: public DotProduct <T>
{ 
public:
    inline virtual T eval ( T *, T *, size_t );
};
 
template <class T> T CompositeDotProduct<T>::eval ( T * a, T * b, size_t dim )
{
   return
   SimpleDotProduct<T>().eval(a,b,dim)
   + ( dim == 1 ? 0 : CompositeDotProduct<T>( ).eval ( a+1,b+1,dim-1 ) );
}
 
// вспомогательная функция
template <class T> T dot ( T* a, T* b, size_t dim )  
{
    return CompositeDotProduct<T>().eval(a,b,dim);
}
 
// пример использования
int a[4] = {1,100,0,-1}; 
int b[4] = {2,2,2,2}; 
std::cout << dot(a,b,4); 

Рис.5. Uml-диаграмма классов упрощенной версии вычисления скалярного произведения.

Два класса, представляющие leaf и composite имеют общий базовый класс, который определяет их операции. Это хорошо известная объектно-ориентированная техника: общности (общие методы для потомков) выражается с помощью общего базового класса.

В шаблонном программировании общности выражаются только через одинаковые имена и сигнатуры шаблонов.

Важные отличия между вычислениями на этапе выполения и вычислениями на этапе компиляции, касающиеся иерархии

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

В отличии от рекурсивной специализации для вычисления факториала ( передавалось лишь одно значение и результат вычисления складывался во вложенную константу класса ) здесь будет передаваться три значение, одно так же будет "нетиповым" параметром шаблона, указывающим его размер, а два других значения - суть вектора, которые будут передаваться в статический шаблонный вычислительный метод, т.к. это наиболее удобный способ передатать типонезависимо конкретные переменные в шаблонный объект:
DotProduct<N,T>::eval(a,b) где:
N - "нетиповой" параметр
T - типовой параметр, для абстрагирования указателей a и b от конкретного типа.

Во время рекурсивной конкретизации будет происходить именно то, что и должно происходить при самой банальной конкретизации шаблонного класса, правда при банальной обычно не происходит рекурсии и создается именно экземпляр класса, здесь же, т.к. конкретизация класса происходит внутри шаблонного метода и при конкретизации идет обращение к статическому методу класса - то в результате создается не конкретизированный экземпляр класса а конкретизированный результат вызова метода, и т.к. он встроен в вызывающую шаблонную функцию, то та тоже конкретизируется до некоторого конечного итеративного выражения, которое и подставляет компилятор в место инстанцирования (конкретизации) этой функции.
/* GCC встраивает функции с ключом -O2, без него на выходе будет 7-м итеративных вызовов ф-й. */

Рис.6. Uml-диаграмма классов реализации скалярного произведения, вычисляемого на этапе компиляции.

Реализация:

// базовый класс
template <size_t N, class T> 
class DotProduct
{ 
public: 
    inline static T eval ( T * , T * );
};
 
template <size_t N, class T> T DotProduct<N,T>::eval ( T * a, T * b )
{
    return  DotProduct<1,T>::eval ( a, b )
    + DotProduct<N-1,T>::eval ( a+1, b+1 );  
}
 
// специализация
template <class T> 
class DotProduct<1,T>
{ 
public: 
    static T eval(T* a, T* b) { return (*a)*(*b); }
};
 
// вспомогательная функция
template <size_t N, class T> inline T dot(T* a, T* b)
{
    return DotProduct<N,T>::eval(a,b);
}
 
// использование
int a[4] = {1,100,0,-1}; 
int b[4] = {2,2,2,2}; 
std::cout << dot<4>(a,b);

Посмотрим что происходит при вычислении на этапе выполнения:
dot(a,b,4); сводится к вычислению

CompositeDotProduct<size_t>().eval(a,b,4)

что приводит к следующим рекурсивным вызовам на стадии исполнения:

SimpleDotProduct    <size_t>().eval(a,b,1)
CompositeDotProduct <size_t>().eval(a+1,b+1,3)
SimpleDotProduct    <size_t>().eval(a+1,b+1,1)
CompositeDotProduct <size_t>().eval(a+2,b+2,2)
SimpleDotProduct    <size_t>().eval(a+2,b+2,1)
CompositeDotProduct <size_t>().eval(a+3,b+3,1)
SimpleDotProduct    <size_t>().eval(a+3,b+3,1)

что приводит в итоге к 7 вызовам виртуальных функций.

При вычислении выражения на этапе компиляции происходит:
Вызов dot<4>(a,b) сводится к вычислению

DotProduct<4,size_t>::eval(a,b);

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

DotProduct<4,size_t>::eval(a,b) 
 
// приводит к
 
DotProduct<1,size_t>::eval(a,b) + DotProduct<3,size_t>::eval(a+1,b+1)
 
// что приводит к вычислению
 
(*a)*(*b) + DotProduct<1,size_t>::eval(a+1,b+1) + 
DotProduct<2,size_t>::eval(a+2,b+2)
 
// что приводит к вычислению
 
(*a)*(*b) + (*a+1)*(*b+1) + DotProduct<1,size_t>::eval(a+2,b+2) + 
DotProduct<1,size_t>::eval(a+3,b+3) 
 
// что приводит к вычислению
(*a)*(*b) + (*a+1)*(*b+1) + (*a+2)*(*b+2) + (*a+3)*(*b+3)

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

(*a)*(*b) + (*a+1)*(*b+1) + (*a+2)*(*b+2) + (*a+3)*(*b+3)

Т.к. рекурсивная конкретизация шаблонов уже была выполнена во время компиляции.

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

Рекурсивная шаблонная конкретизация занимает больше времени и неудивительно, что требуемое время компиляции возрастает, для шаблонного решения по сравнению с объектно-ориентированным решением, которое компилируется быстрее, но работает медленнее.

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

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

template <int N> int64_t foo_n ()
{
    return  foo_n<N-1>() * N;
}
 
template <> int64_t foo_n<1> ()
{
    return 1;
}

В код подставится итеративный вызов конкретизаций этой функции, т.е. например foo<15>()...*foo<1>() - т.е. рекурсивная специализация метафункций основанных не на шаблонах классов а на основе шаблонов обычных ф-й (или нешаблонных ф-й вообще) может оказаться крайне неэффективным решением, но может и оказаться равноэффективным вычислениям в метаклассах. А почему так откроет эта короткая заметка, которая раскрывает подробности работы метафункций на основе обычных функций.

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

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

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

Конечно, в примере будут рассмотрены простые выражения, над встроенными типами, из которых в итоге построится очень простое выражение для времени выполнения. Но ведь формула расчетов в итоге может быть очень большой, и её рекурсивный анализ во время выполнения займет значительно больше времени, чем итеративный аналог выражения, полученный во время компиляции. Так же стоит учитывать, что кроме стандартных типов в арифметический интерпретатор могут быть переданы сложные пользовательские типы, те же вектора или многомерные матрицы ( с определенными в них или над ними арифметическими операциями ) - в таком случае синтаксический анализ на этапе компиляции и построение итеративного выражения — являются ещё более стоящим действием.

Арифметические выражения состоят из унарных и бинарных операций, переменных и констант. Арифметические выражения описывает паттерн Interpreter, описанный в GoF, являющийся частным случаям паттерна Composite.

Отношение “часть-целое” паттерна Composite соответствует отношению выражения и подвыражения в паттерне Intepreter.

• Leaf будет терминальным выражением (т. е. прерывающим дальнейший синтаксический анализ) — это константы и переменные
• Composite — это все то что не Leaf — т. е. унарные и бинарные операции.
• Вычисление компонентов является интерпретацией синтаксического дерева и его выражений.

Синтаксическое дерево представляется такими арифметическими выражениями как (a+1)*c или log(abs(х-N)). Переменные могут меняться между вызовами сгенерированного выражения. Литералы (константы) — нет.

Будем рассматривать конкретный пример выражения — (x+2)*3

Составная структура данного выражения, или другими словами, синтаксическое дерево данного выражения представлена следующим образом:

Рис. 7. Пример синтаксического дерева для арифметического выражения.

Классическая объектно-ориентированная реализация Interpreter включает следующие классы:

Рис. 8. Uml-диаграмма классов объектно-ориентированной реализации интерпретатора арифметических выражений

Реализация:

#include <iostream>
 
struct AbstractExpr
{ 
    virtual double eval() const = 0;
    virtual ~AbstractExpr(){}
};
 
// данный класс (структура) автоматом наследует чисто виртуальный
//  метод eval поэтому опеределять/переопределять его не нужно.
struct TerminalExpr : public AbstractExpr
{ 
};
 
struct NonTerminalExpr : public AbstractExpr
{
};
 
class Literal : public TerminalExpr
{
public:
   Literal (double v) : _val(v) {}
   double eval() const { return _val; }
private:
   const double _val;
}; 
 
class Variable : public TerminalExpr
{ 
public: 
   Variable(double & v) : _val(v) {}
   double eval() const { return _val; }
private:
   double& _val; 
};
 
class BinaryExpr : public NonTerminalExpr
{
protected:
   BinaryExpr ( const AbstractExpr * e1, const AbstractExpr * e2 )
     : _expr1(e1),_expr2(e2) {}
   virtual ~BinaryExpr ()
   { delete const_cast<AbstractExpr*>(_expr1);
     delete const_cast<AbstractExpr*>(_expr2);
   }
   const AbstractExpr* _expr1;
   const AbstractExpr* _expr2;
};
 
class Sum : public BinaryExpr
{
public:
   // напомню что только через указатели или ссылки на базовый
   // возможна передача производного класса в тип базового.
   Sum ( const AbstractExpr* e1, const AbstractExpr* e2 )
     : BinaryExpr(e1,e2) {}
   double eval( ) const
   { return _expr1->eval() + _expr2->eval(); }
};
 
class Product : public BinaryExpr
{
public:
   Product ( const AbstractExpr* e1, const AbstractExpr* e2 )
     : BinaryExpr(e1,e2) {}
   double eval( ) const
   { return _expr1->eval() * _expr2->eval(); }
};
 
void someFunction(double x) 
{
    // демонстрация смысла передачи в Variable параметра по ссылке
    std::cout << "start value: " << x;
    Product expr(new Sum(new Variable(x),new Literal(2)), new Literal(3));
    std::cout << "\n#01: " << expr.eval();
    x += .002d;
    std::cout << "\nchanged value: " << x;
    std::cout << "\n#02: " << expr.eval();
    std::cout << std::endl;
}
 
int main()
{
    // (x+2)*3 where PI = π
    someFunction(3.14d);
    return 0;
}

Сначала создается объект выражения expr, который представляет выражение (x+2)*3 и затем вычисляется объект выражения. При этом, x между обращениями к объекту выражения можно менять, т. к. он передан по ссылке.

Это не самое эффективное решение, но на основе него можно построить очень эффективное решение времени компиляции.

Как говорилось ранее — шаблонные решение основаны на общности имён и специализациях шаблонов — поэтому в базовых классах нет нужды.

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

Для описания классов литералов и переменных достаточно сходства имен и сигнатур их методов. Нетерминальные выражения такие как сумма, произведение и прочие будут определяться через конкретизации шаблонных классов BinaryExpr и UnaryExpr, которые конкретизируются структурной информацией — т. е. тем, что было нарисовано на рисунке 7. (будет понятно ниже). Эти шаблоны классов будут принимать типы их подвыражений как ”типовые” шаблонные аргументы. В последствии вычислительные методы классов нетерминальных выражений будут заменены на одноименные операции, что предоставит клиентам данного арифметического интерпретатора значительно более удобный интерфейс.

Рекурсия с этапа выполнения (вложенность (new Sum(new Variable(x),new Literal(2)), new Literal(3)) ) перейдет в рекурсию времени компиляции по инстанцированию шаблонов, правда рекурсия не будет похожа на ту, что мы рассматривали в этой статье, т. е. условие выхода не специализация шаблона — а дискретная структура синтаксического дерева — см рисунок 7 и код ниже.

Рис. 9. UML-диаграмма классов шаблонной реализации интерпретатора арифметических выражений.

Реализация:

Классы примитивных объектов (терминированных)

class Literal
{
public:
    Literal ( const double v ) : _val(v) {}
    double eval() const { return _val; }
private:
    const double _val; 
};
 
class Variable
{
public:
    Variable( double & v ) : _val(v) {}
    double eval() const { return _val; }
private:
    double & _val; 
};

Класс бинарного выражения. По его подобию делается класс унарного выражения, но в изложении он отсутствует.

template <class ExprT1, class ExprT2, class BinOp> class BinaryExpr
{
public:
    BinaryExpr ( ExprT1 e1, ExprT2 e2,BinOp op = BinOp() ) : // *#01
    _expr1(e1), _expr2(e2), _op(op) {}
    double eval() const
    { return _op ( _expr1.eval(),_expr2.eval() ); }
private:
    ExprT1 _expr1;
    ExprT2 _expr2;
    BinOp  _op;
};

/*  #01
    3-м параметром, создаём вызов конструктора по умолчанию
    это избавит нас от необходимости в клиентах этого класса констрировать его так:
    BinaryExpr<ExprT1, ExprT2, std::plus<double> >(e1,e2, std::plus<double>()); */

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

Чтобы упростить создание объектов выражений, и сделать возможным из переменных вывести имена их типов, будем использовать "создающую функцию" - довольно частый приём в том же STL.

// helpers (make functions)
 
template  <class ExprT1, class ExprT2> BinaryExpr < ExprT1, ExprT2, std::plus<double> > 
makeSum ( ExprT1 e1, ExprT2 e2 )
{
    return BinaryExpr<ExprT1, ExprT2, std::plus<double> >(e1,e2);
}
 
template  <class ExprT1, class ExprT2> BinaryExpr < ExprT1, ExprT2, std::multiplies<double> >
makeProd ( ExprT1 e1, ExprT2 e2 )
{
    return BinaryExpr<ExprT1, ExprT2, std::multiplies<double> >(e1,e2);
}

Использование шаблонного интерпретатора:

void someFunction ( double x )
{
    // объявление типа переменной expr
    BinaryExpr< BinaryExpr < Variable,Literal,std::plus<double> >,
              Literal,
              std::multiplies<double> >
    expr = makeProd ( makeSum ( Variable(x), Literal(2) ), Literal(3) ); 
    std::cout << expr.eval() << std::endl;
}

В теле данной функции создастся объект, представляющий выражение (x+2)*3, а затем рассчитается само выражение. Помните текст "будет понятно ниже" - вот, теперь понятно о чем там говорилось. Мы конкретизируем шаблон структурной информацией, описывающей синтаксическое дерево - т.е. тип объекта выражения отражает структуру синтаксического дерева.

Вот тут как раз даже очень заядлые любители эстетики шаблонов будут рады введенной в 11-м стандарте auto переменной :)

void someFunction ( double x )
{
    auto
    expr = makeProd ( makeSum ( Variable(x), Literal(2) ), Literal(3) ); 
    std::cout << expr.eval() << std::endl;
}

Что имеем?

Если компилятор встраивает все создающие функции, конструкторы и функции eval() (скорее всего так и будет, так как они тривиальныe (на моих тестах всраивает с ключом -O2) ) выражение

makeProd ( makeSum( Variable(x), Literal(2) ), Literal(3) ).eval()

сводится к

(x+2)*3

Это в разы эффективнее - чем решение, работающее во время выполнения программы:

Product expr( new Sum ( new Variable(x), new Literal(2) ), new Literal (3) ).eval()

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

Решение на основе шаблонов выполняется гораздо быстрее, чем объектно-ориентированная реализация.

Наше решение можно сделать намного удобнее для использования. Ведь не так удобно, пользователям нашего интерпретатора каждый раз расписывать подобное:

makeProd ( makeSum( Variable(x), Literal(2) ), Literal(3) ).eval()

Для этого потребуется шаблонные создающие функции makeSum и makeProd сделать перегруженными шаблонными операциями, т. е. Просто поменять их объявление с makeSum и makeProd на operator + и operator * соответственно.
Теперь в использующей функции можно

makeSum ( Variable(x), Literal(2)), Literal(3) ).eval()

заменить на

( Variable(x) + Literal(2) ) * Literal(3);

Удобнее. Идём далее. Хотелось бы, чтобы можно было писать нечто, максимально похожее на ((х+2)*3) — т. е. Цель устранить явное создание объектов переменных и объектов литералов, которые загромождают выражение.

Правда полностью отказаться от некоторого загромождения не получится, т. к. если использовать непосредственно ((х+2)*3), где x — double, компилятор вызовет операцию + над типом double и выражение приведется к этому типу, и соответственно не сможет вызвать наш шаблоный вычислительный метод eval() времени компиляции. Переменную придется обернуть в Variable тип, чтобы выражение привелось к типу BianaryExpr.

Для конкретизации BinaryExpr в шаблон передаются конкретные типы Variable и Literal.

Если вместо

( Variable(x) + Literal(2) ) * Literal(3);

писать

Variable v(x);
std::cout << ((v+2)*3.0).eval() << std::endl;

То операция + (являющаяся создающей функцией) заставит компилятор вывести тип второго аргумента шаблона как тип int, так же, если не использовать обращение к безымянному объекту а создавать именованный объект, для возможности его повторного использования, то придётся инстанцировать шаблон не пользовательскими типами Literal для констант а именно типами этих констант:

Variable v(x);
BinaryExpr< BinaryExpr < Variable, int, std::plus<double> >,
              double,
              std::multiplies<double> >
    expr = (v + 2) * 3.0;
    std::cout << expr.eval() << std::endl;

Таким образом оба варианта использования, для нашего выражения, в шаблоне BinaryExpr _expr2 будет иметь тип int. Но int не имеет метода eval().

Тут необходима техника traits — описанная в этом блоге на примере итераторов (когда обычный указатель через обертку, наделялся аттрибутами, которые он не имел), и статье первоисточнике на примере шаблона string.

Но задача в отличие от iterator_traits чуть-чуть в другом - не снабдить указатель полями — описателями типов, а создать отображение констант в тип литералов, а для всех других типов (переменные и нетерминалы) сделать отображение в себя же:

// Base Template of Traits:
template <class Expr> struct exprTraits
{ typedef Expr type; };
 
// Specializations:
template <> struct exprTraits <double>
{ typedef Literal type; };
 
template <> struct exprTraits <int>
{ typedef Literal type; };

Естественно нужно охватить все типы, мы же ограничимся только теми, которые используем в примере.

Поля в BinaryExpr с таких

ExprT1 _expr1;
ExprT2 _expr2;

Теперь станут такими

typename exprTraits<ExprT1>::type _expr1; 
typename exprTraits<ExprT2>::type _expr2; 

Теперь выражение, такое как (х+2)*3, будет вычисляться без лишних награмождений.

Если создать вспомогательную функцию

template <class ExprT> double eval(ExprT e) { return e.eval(); }

то можно будет избавиться, от выглядящего странным — обращения к методу сущности, которая выглядит как выражение.

Теперь, вместо

((v+2)*3).eval()

можно писать

eval( (v+2)*3 )

На рисунке показывается как выражение ((v+2)* 3).eval(), где v является Variable – оберткой double переменной x, постепенно разворачивается во время компиляции к выражению (x+2)*3.

Рис. 10. Вычисление объекта выражения (v+2)*3 на этапе компиляции.

Реализация:

#include <iostream>
 
// Literal and Variable Class
class Literal
{
public:
    Literal ( const double v ) : _val(v) {}
    double eval() const { return _val; }
private:
    const double _val; 
};
 
class Variable
{
public:
    Variable( double & v ) : _val(v) {}
    double eval() const { return _val; }
private:
    double & _val; 
};
 
// Base Template of Traits:
template <class Expr> struct exprTraits
{ typedef Expr type; };
 
// Specializations:
template <> struct exprTraits <double>
{ typedef Literal type; };
 
template <> struct exprTraits <int>
{ typedef Literal type; };
 
// Binary Expression Class
template <class ExprT1, class ExprT2, class BinOp> class BinaryExpr
{
public:
    BinaryExpr ( ExprT1 e1, ExprT2 e2,BinOp op=BinOp() ) :
    _expr1(e1), _expr2(e2), _op(op) {}
    double eval() const
    { return _op ( _expr1.eval(),_expr2.eval() ); }
private:
    typename exprTraits<ExprT1>::type _expr1; 
    typename exprTraits<ExprT2>::type _expr2; 
    BinOp  _op;
};
 
// Helpers (make functions)
template  <class ExprT1, class ExprT2> BinaryExpr < ExprT1, ExprT2, std::plus<double> > 
operator + ( ExprT1 e1, ExprT2 e2 )
{
    return BinaryExpr<ExprT1, ExprT2, std::plus<double> >(e1,e2);
}
 
template  <class ExprT1, class ExprT2> BinaryExpr < ExprT1, ExprT2, std::multiplies<double> >
operator * ( ExprT1 e1, ExprT2 e2 )
{
    return BinaryExpr<ExprT1, ExprT2, std::multiplies<double> >(e1,e2);
}
 
// Using tempates iterpreter ( с возможностью повторного использования выражения )
void someFunctionMultiple ( double x )
{
    Variable v = x; // #01
    BinaryExpr< BinaryExpr < Variable, int, std::plus<double> >,
              double,
              std::multiplies<double> >
    expr = (v + 2) * 3.0;
    std::cout << expr.eval() << std::endl;
}
 
// Using tempates iterpreter
void someFunctionSingle ( double x )
{
    Variable v = x;
    std::cout << ((v+2)*3.0).eval() << std::endl;
}
 
 
// User friendly variant:
template <class ExprT> double eval(ExprT e) { return e.eval(); }
 
void someSimplyFunction ( double x )
{
    Variable v = x;
    std::cout << eval( (v+2)*3.0 )<< std::endl; // #02
}
 
 
int main()
{
    // (x+2)*3 where PI = π
    someFunctionSingle(3.14d);
    someSimplyFunction(3.14d);
    return 0;
}

Комментарии к реализации:
#01 - работает конструктор преобразоания.
#02 - сначала вычисляется выражение (v+2), имеющее тип Variable,int,plus<double>, далее вычилится выражение BinaryExpr<BinaryExpr,double,multiplies<double>>, если полностью писать "разворот" - то он будет тем же, что и тот что под строкой #01, и именно к объекту выражения этого типа и обратится конструкция e.eval().

В том что мы сделали - каждый объект выражения представляет синтаксическую декомпозицию арифметического выражения. Это синтаксическое дерево знает, как интерпретировать себя для вычисления числового значения. Полученное выражение можно использовать неоднократно (меняя переменные, хранящиеся в Variable типах, по ссылке). Иногда же нужно создать объект выражения ещё до того как известна какая-то переменная, например для передачи его в другую функцию, в которой будет инициализирована эта переменная.

Например это нужно для вычисления интеграла с помощью следующей аппроксимирующей функции:

template <class ExprT> 
double integrate ( ExprT e, double from, double to, size_t n )
{
    double sum=0, step=(to-from)/n;
    for ( double i=from+step/2; i<to; i+=step )
	sum+=e.eval(i);
    return step*sum;
}

В которую передавалось бы такое выражение:

Variable<double> v; 
// Как видно Variable теперь является шаблоном, можно было реализовать и
// как обычный класс, но в первоисточнике реализовано в виде шаблонов.
// Поэтому и я делаю в шаблонах.
std::cout << integrate ( v/(1.0+v), 1.0, 5.0, 10) << std::endl;

Для реализации этого, решение выше требует небольших изменений. А именно - Variable теперь не будет иметь конструктора, его функционал можно реализовать как возвращение копии переменной переданной по значению в параметр. Т.к. методы должны иметь одинаковую сигнатуру - то и Literal должен иметь входящий параметр, но при этом возвращать сохраненную копию значения. Нетерминальные выражения будут передавать аргумент своим подвыражениям.

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

Код (с сокращением некоторых участков для краткости) :

class Literal
{
public:
    Literal ( const double v ) : _val(v) {}
    double eval(double) const { return _val; }
private:
    const double _val; 
};
 
template <class T> class Variable
{
public:
    double eval(T _val) const { return _val; }
};
 
template <class ExprT1, class ExprT2, class BinOp> class BinaryExpr
{
public:
    // ... тот же конструктор
    double eval(double d) const
    { return _op ( _expr1.eval(d),_expr2.eval(d) ); }
    typedef BinaryExpr<ExprT1,ExprT2,BinOp> type;
private:
    // ... те же поля
};
 
template <class ExprT> 
double integrate ( ExprT e, double from, double to, size_t n )
{
    Variable<double> _n;
    double sum=0, step=(to-from)/n;
    for ( double i=from+step/2; i<to; i+=step )
	sum+=e.eval(i);
    return step*sum;
}
 
void someIntegral (void)
{
    Variable<double> v; 
    std::cout << integrate ( v/(1.0+v), 1.0, 5.0, 10) << std::endl;
}
 
template <class T> void someFunctionSingle ( T x )
{
    Variable<T> v;
    std::cout << ((v+2)*3.0).eval(x) << std::endl;
}
 
template <class T> class Eval
{
public:
    Eval ( T & x ): _val(x) { }
    template <class ExprT> T operator () (ExprT e)  { return e.eval(_val); }
private:
    T & _val;
};
 
template <class T> void someSimplyFunction ( T x )
{
    Variable<T> v;
    Eval<T> eval(x);
    std::cout << eval( (v+2)*3.0 )<< std::endl;
}

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

Можно добавить такие унарные функции как: sqrt, sqr, exp, log, и тогда будет возможно даже вычисление распределения Гаусса:

double sigma=2.0, mean=5.0; 
const double Pi = 3.141593;
std::cout << integrate( 
 1.0/(sqrt(2*Pi)*sigma) * exp(sqr(x-mean)/(-2*sigma*sigma)), 
 2.0,10.0,100) << std::endl; 

Для выражений, представляющих числовые функции, можно использовать функции из стандартной библиотеки C. Все, что нужно сделать, это добавить создающие функции для унарных или бинарных выражений. Пример для квадратного корня:

template  < class ExprT > UnaryExpr < ExprT,double(*)(double) > sqrt ( ExprT e )
{ return UnaryExpr<ExprT,double(*)(double)>(e,::std::sqrt); } 

С этими дополнениями у нас появляется мощное и высокопроизводительные решение для расчета арифметических выражений. В которое так же можно добавить и шаблоны логических операций. Если же метод eval сделать оператором вызова функции - то из объектов выражений можно получить функциональные объекты, которые можно использовать в сочетании с "алгоритмами" STL

Variable<int> x;
std::cout << std::count_if ( vct.begin(), vct.end(), x >= 0 && x <= 25 ) << std::endl;

Этот пример хорошо иллюстрирует читабельность шаблонов выражений при нулевой вычислительной стоимости на этапе выполнения.

Код с полным листингом из этой статьи, в том числе с поддержкой логических операций - в архиве.

Заключение

В заключение порекомендую дополнительный матриал (прежде всего самому себе :))
SFINAE — это просто
А так же 48-е правило (на 231 старание) Эффективного Си++ Мейерса - крайне интересное чтиво.