Рекурсия и условные условия компиляции

Question

Я читал ответы на "Printing 1 to 1000 without loop or conditionals", и мне интересно, зачем нужен специальный чехол для NumberGeneration < 1> в верхнем ответе.

Если я удалю это и добавлю чек для N == 1 в шаблоне (код ниже), код не завершится компиляцией, «глубина создания экземпляра превышает максимум», но я не уверен, почему. Условны обрабатываются по-разному во время компиляции?

#include <iostream> 

template<int N> 
struct NumberGeneration 
{ 
    static void out(std::ostream& os) 
    { 
     if (N == 1) 
     { 
      os << 1 << std::endl; 
     } 
     else 
     { 
      NumberGeneration<N-1>::out(os); 
      os << N << std::endl; 
     } 
    } 
}; 

int main() 
{ 
    NumberGeneration<1000>::out(std::cout); 
} 

Answer 1

Создание и сборка кода не зависит от условных обозначений! Рассмотрим это:

// don't declare bar()! 

void foo() 
{ 
    if (false) { bar(); } 
} 

Если вы никогда не объявлять bar(), это ошибка компиляции даже если внутренняя сфера никогда не может быть достигнута. По той же причине NumberGeneration<N-1> всегда создается, независимо от того, может быть достигнута эта ветка или нет, и у вас бесконечная рекурсия.

Действительно, статический аналог условных именно специализация шаблона:

template <> struct NumberGeneration<0> { /* no more recursion here */ }; 

Answer 2

Это потому, что целые числа могут быть отрицательными и код времени исполнения (if проверки) не остановит компилятор инстанцирования шаблона с 0, -1, -2 и т.д. компилятором может быть в состоянии получить с тем, что вы предлагаете, но что, если при создании экземпляров других шаблонов (0, -1, ...) есть побочные эффекты, от которых вы зависите? В этом случае компилятор не сможет создать экземпляр для вас.

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

Answer 3

Я задаюсь вопросом, почему это необходимо иметь специальный случай для NumberGeneration < 1> в верхнем ответе.

Потому что это конечное условие для рекурсивного! Без этого, как может рекурсивный конец?

Answer 4

Условный if не будет обрабатываться во время компиляции. Он будет обрабатываться во время выполнения.

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

Answer 5

В общем случае условие N == 1 в вашем коде оценивается во время выполнения (хотя компилятор может его оптимизировать), а не во время компиляции. Поэтому рекурсия экземпляра экземпляра в предложении else никогда не прерывается. NumberGeneration<1>, с другой стороны, оценивается во время компиляции и, следовательно, действует как пример завершения этого рекурсивного шаблона.

Answer 6

Я уверен, что это специфичный для компилятора; некоторые компиляторы могут попытаться сгенерировать обе ветви if/else независимо от значения N, и в этом случае компиляция завершится неудачно. Другие компиляторы могут оценить условие во время компиляции и только генерировать код для ветви, которая выполнена, и в этом случае компиляция будет успешной.

ОБНОВЛЕНИЕ: Или, как говорит Люк в комментариях, возможно, что компилятор должен сгенерировать обе ветви, чтобы код всегда терпел неудачу. Я не совсем уверен, что происходит, но в любом случае плохой идеей полагаться на условия времени выполнения для управления генерации кода компиляции.

Было бы лучше использовать специализацию:

template <int N> 
struct NumberGeneration 
{ 
    static void out(std::ostream & os) 
    { 
     NumberGeneration<N-1>::out(os); 
     os << N << std::endl; 
    } 
}; 

template <> 
void NumberGeneration<1>::out(std::ostream & os) 
{ 
    os << 1 << std::endl; 
} 

(или вы могли бы сократить это незначительно, а не специализирующаяся на N=0, с out функции, которая ничего не делает).

Также имейте в виду, что некоторые компиляторы могут не поддерживать глубоко resursive templates; C++ 03 предлагает минимальную поддерживаемую глубину только 17, что C++ 11 увеличивается до 1024. Вы должны проверить, что такое предел вашего компилятора.

Answer 7

Шаблоны создаются во время компиляции, особый случай шаблона предотвращает рекурсию компилятора ниже 1 при компиляции.

if-clauses оцениваются во время выполнения, поэтому компилятор уже сработал при компиляции вашего кода, когда это будет иметь какой-либо эффект.

Answer 8

Вот правильный способ сделать это:

template<int N> 
struct NumberGeneration 
{ 
    static void out(std::ostream& os); 
}; 

template<int N> 
void NumberGeneration<N>::out(std::ostream& os) 
{ 
    NumberGeneration<N-1>::out(os); 
    os << N << std::endl; 
} 

template<> 
void NumberGeneration<1>::out(std::ostream& os) 
{ 
    os << 1 << std::endl; 
} 

int main() 
{ 
    NumberGeneration<20>::out(std::cout); 
} 

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