В метапрограмме на шаблонах: каким образом базовая специализация прекращает рекурсивное вычисление типа?
Базовая специализация задаёт точный случай, для которого рекурсивное правило больше не применяется. При инстанцировании шаблона компилятор выбирает эту специализацию вместо рекурсивной, поэтому цепочка вычислений завершается.
Важно, что это не рекурсия во время выполнения: компилятор последовательно создаёт специализации шаблона и вычисляет их на этапе компиляции.
Шаблонное метапрограммирование использует систему шаблонов как средство вычислений во время компиляции. Такой подход позволяет получать типы и константные значения до запуска программы, в том числе в ситуациях, где обычные средства языка не подходят для формирования типов.
Рекурсивная обработка особенно естественна для списков типов, иерархий политик и других структур, которые можно разбирать на первый элемент и остаток. Для завершения такого разбора необходим отдельный базовый случай.
Рекурсивный шаблон обычно уменьшает задачу: например, заменяет список типов из нескольких элементов списком на один элемент короче. Если для пустого списка нет отдельной специализации, компилятор продолжит искать следующий уровень рекурсии.
Это приводит к ошибке превышения глубины инстанцирования или к другой диагностике, зависящей от конкретного компилятора. Неверный базовый случай также может дать неправильный результат, например сумму без корректного начального значения.
У шаблона обычно есть основное рекурсивное правило и специализация для минимального состояния. Для непустого списка частичная специализация отделяет первый тип, рекурсивно обрабатывает хвост и добавляет единицу. Для пустого списка полная специализация возвращает нулевой результат.
Здесь type_list предполагается простым шаблоном-контейнером для типов. Для непустого списка выбирается частичная специализация: она уменьшает пакет Tail... и снова обращается к length. Когда список становится пустым, выбирается полная специализация length<type_list<>>, а выражение 1 + ... больше не формируется.
Ключевой механизм — выбор специализации до дальнейшего инстанцирования её содержимого. Базовая специализация не вызывает саму себя и тем самым разрывает цепочку. Если базовый случай объявлен слишком поздно, компилятор может уже начать неявное инстанцирование первичного шаблона; специализацию следует объявлять до первого использования, которое приводит к такому инстанцированию.
Рекурсивный шаблон не обязан вычислять только число. Его результатом может быть вложенный тип, преобразованный список типов или объект политики. Однако каждый уровень создаёт дополнительные инстанцирования, поэтому глубокая рекурсия увеличивает время компиляции и может упереться в ограничение глубины.
В библиотеке нужно получить количество типов в compile-time-списке, чтобы выбрать перегрузку или размер статической структуры. Рассматривались три варианта: рекурсивные специализации, свёртка параметр-пака и вычисление через constexpr-функцию.
Свёртка параметр-пака короче и обычно удобнее для простого числового результата, но хуже подходит, когда на каждом шаге нужно формировать новый тип или выбирать разные ветви по структуре элемента. constexpr-функция хорошо решает задачи со значениями, однако сама по себе не заменяет специализации, когда результатом является тип.
Для обобщённого type-level-списка выбраны рекурсивные специализации: непустой список обрабатывается общим правилом, пустой — базовой специализацией. В результате размер доступен как константное выражение, а алгоритм можно расширить до построения нового списка типов. Компромисс — более сложные сообщения об ошибках и потенциально большая глубина инстанцирования.
Почему базовый случай обычно оформляют полной специализацией, а не отдельной перегрузкой?
У класса-шаблона нет перегрузок в смысле функций. Для точного типа type_list<> объявляют полную специализацию, которая фиксирует все параметры и полностью заменяет основное определение. Перегрузка функции могла бы выбирать другую реализацию по параметрам, но она не является механизмом выбора определения класса-шаблона.
Что произойдёт, если базовая специализация объявлена после первого использования шаблона?
Если использование уже вызвало неявное инстанцирование первичного шаблона, последующее объявление специализации для того же случая недопустимо. Компилятор не обязан откладывать уже начатое инстанцирование в ожидании будущей специализации, поэтому специализации и необходимые объявления размещают до точки первого использования.
Почему замена рекурсии на свёртку не всегда эквивалентна?
Свёртка эффективно агрегирует значения пакета, но не является универсальным механизмом рекурсивного преобразования типов. Если задача требует на каждом шаге получить новый тип, проверить структуру остатка или выбрать разные типовые ветви, специализация может выразить это напрямую. Свёртка предпочтительнее для простого ассоциативного вычисления, а рекурсивные специализации — когда важна структура и результатом является тип.