Метапрограммирование. Часть 1. Взгляд издалека.

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

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

Зачем нужны шаблоны - понятно, уже не раз они показывались (хоть и не описывались) в этом блоге, а описывать и не нужно, т.к. понятных описаний хватает - в той же, моей любимой книге ;)

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

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

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

И где же можно натоклнуться - на такое страшное (для новичка) дело. Да банально, на любом стандартном контейнере STL, в случае, конечно же, если интересно разобрать как он работает внутри, если не интересно, человек, в блаженном неведении, просто его использует, и тратит время на нечто более полезное, например изучение шаблонов проектирования :) Но мне кажется лучше медленно, но очень досконально изучать язык, и его свойства, чем научиться быстро писать на нём, не понимая как он работает внутри - т.к. если не изучать, тяжело писать эффективный код.

Возьмём дек (пожалуй, мой любимый последовательный контейнер :))

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

  1. template <class T> class Deque
  2. {
  3. private:
  4. T ** array;
  5. public:
  6. Deque ( unsigned, const T & = T() ); //1
  7. template <class Iterator> Deque (Iterator _first, Iterator _last); //2
  8. Deque ( );
  9. ~Deque();
  10. };

Первый конструктор служит для создания дека по указанному размеру (первый параметр), каждый элемент заполняется указанным значением.
А второй - получает полуинтервал другого контейнера через два итератора.

Например необходимо, для определенной задачи, создать дек из 25 элементов, равных -1.

  1. Deque<int> test1(25, -1);

Ожидаем вызов первого конструктора. Но вызовется второй - итераторный. И вот благодаря этому я и узнал что существует метапрограммирование и чем оно выгодно.

Ниже покажу как в подобной ситуации можно обойтись без развитого метапрограммирования (Си++98) и как с развитым (Си++11 и выше)

И так почему почему вызывается неправильный конструктор?

Для дальнейших рассуждений, лучше взять код std::deque:

  1. #if __cplusplus >= 201103L
  2. deque(size_type __n, const value_type& __value,
  3. const allocator_type& __a = allocator_type())
  4. : _Base(__a, __n)
  5. { _M_fill_initialize(__value); }
  6. #else
  7. explicit
  8. deque(size_type __n, const value_type& __value = value_type(),
  9. const allocator_type& __a = allocator_type())
  10. : _Base(__a, __n)
  11. { _M_fill_initialize(__value); } /*--------------- #1 */
  12. #endif
  13.  
  14.  
  15. #if __cplusplus >= 201103L
  16. template<typename _InputIterator,
  17. typename = std::_RequireInputIter<_InputIterator>>
  18. deque(_InputIterator __first, _InputIterator __last,
  19. const allocator_type& __a = allocator_type())
  20. : _Base(__a)
  21. { _M_initialize_dispatch(__first, __last, __false_type()); }
  22. #else
  23. template<typename _InputIterator>
  24. deque(_InputIterator __first, _InputIterator __last,
  25. const allocator_type& __a = allocator_type())
  26. : _Base(__a)
  27. {
  28. // Check whether it's an integral type. If so, it's not an iterator.
  29. typedef typename std::__is_integer<_InputIterator>::__type _Integral;
  30. _M_initialize_dispatch(__first, __last, _Integral());
  31. } /*--------------- #2 */
  32. #endif

Видно,что для решения поставленной задачи (предотвращение вызова 2-го конструктора) в Си++ начиная с 11 стандарта и выше, используется какая-то хитрая конструкция (обязательно опишу её ниже, и буду применять в своём деке её идеи). Очень коротко говоря - здесь используется подход метапрограммирования и шаблон _RequireInputIter, который определяет инстанцировать или нет, содержащую его ф-ю.

В 98м же Си++ используется вызов на прямую, без таких вот конструкций, типа _RequireInputIter, как я и пытался сделать изначально, следуя определению интерфейса дека.

Но наткнулся на то, что компилятор в общем случае воспринимает конструктор

  1. template<typename _InputIterator>deque(_InputIterator _first, _InputIterator __last, const allocator_type& __a = allocator_type())

как более предпочтительный (т.к. из за наличия шаблонов, в него можно передать std::deque<int> dq (10,-1) сразу, не задействуя преобразования типов) нежели конструктор

  1. deque(size_type __n, const value_type& __value = value_type(), const allocator_type& __a = allocator_type())

Для передачи в который, параметров (25 и -1) требовалось бы преобразовать 25 к беззнаковому типу. (size_type == unsigned long). Дело в том что по умолчанию, типы, указанные руками в ф-ях, воспринимаются как знаковые. Компилятор выбирает более выгодную стратегию вызова (более соответствующий тип) - и выбирает тот конструктор, вызвать который проще (не нужно преобразовывать).

Выход один - указывать явно тип константы (25u), что не удобно, или же принудительно преобразовать (unsigned long)25 - что в добавок и не хорошо (лишние операции)

Так как же тогда работает дек с конструктором по итераторам в Си++ до 11 стандарта?

На самом деле работает просто:

Такой вызов пойдет конструктору ---- #1

  1. std::deque<int> dq (10u,-1)

А такой

  1. std::deque<int> dq (10,-1)

Как и ожидается, конструктору ----- #2

Т.е. можно говорить, что до появления стандартизованной std::enable_if (и кое чего ещё*) - конструктор ----- #1 почти не использовался, а лишь служил описанием интерфейса. Вот так вот :)

А его работу исполнял ----- #2, используя для своего «двойного» поведения метод

  1. template<typename _Integer>
  2. void
  3. _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type)
  4. {
  5. _M_initialize_map(static_cast<size_type>(__n));
  6. _M_fill_initialize(__x);
  7. }
  8.  
  9. // called by the range constructor to implement [23.1.1]/9
  10. template<typename _InputIterator>
  11. void
  12. _M_initialize_dispatch(_InputIterator __first, _InputIterator __last, __false_type)
  13. {
  14. typedef typename std::iterator_traits<_InputIterator>::
  15. iterator_category _IterCategory;
  16. _M_range_initialize(__first, __last, _IterCategory());
  17. }

Который в первичной своей форме выполняет выделение памяти по первому параметру, и заполняет её вторым.
А его перегруженный вариант оба параметра воспринимает как итераторы, и ведет работу по ним.

Для того чтобы определиться какую ф-ю вызвать используется шаблонный класс (да структура, но будем говорить что класс)

  1. typedef typename std::__is_integer<_InputIterator>::__type _Integral

Здесь проявляется метапрограммирование: идёт актуализация шаблонного класса __is_integer - но никакого объекта не создаётся, создается лишь связь к определенному внутри этого класса типу __type. Который, если _InputIterator попадает под одну из специализаций шаблона __is_integreal будет иметь тип __true_type, если же тип _InputIteraror не соответствует специализациям, то значение __type будет иметь тип __false_type.

/* подробный разбор этой техники, на которой можно увидеть некоторые особенности частичных специализаций. */

Далее, поскольку тип определен, то возможно и создавать объекты данного типа:

  1. _M_initialize_dispatch(__first, __last, _Integral());

И вот, в зависимости от того - какого типа (__true_type или __false_type) будет созданный временный объект после вызова _Integral() - компилятор и выберет нужную версию _M_initialize_dispatch. Объёмно - да, но и просто. Особо залипательно здесь то что - можно инстанцировать, но не с целью создания экземпляра класса, а именно для доступа к его свойствам. Фактически тоже самое используется и в iterator_traits, описанном ранее в этом блоге.

И вот, таким вот образом, один конструктор, (с другим интрефейсом и как бы созданный совсем для другого) эмулирует действия первого.

Убедиться в этом можно, заккоментив stl_deque.h пару строк:

  1. template<typename _Integer>
  2. void
  3. _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type)
  4. {
  5. //_M_initialize_map(static_cast<size_type>(__n));
  6. //_M_fill_initialize(__x);
  7. }

и выполнив код:

  1. std::deque<int> dq1 (10,-1);
  2. std::deque<int> dq2 (10u,-1);
  3. std::copy ( dq1.begin(), dq1.end(), std::ostream_iterator<int>(std::cout, " "));
  4. std::cout << std::endl;
  5. std::copy ( dq2.begin(), dq2.end(), std::ostream_iterator<int>(std::cout, " "));

собранный для -std=c++11 и -std=c++98.

Чуть менее подробно (и возможно более удобочитаемо) об этом я написал тут после "====================== UPDATE" стоит читать.

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

Метапрограммирование. Взгляд издалека. Часть 2. С++11.