Recopilación de tiempo de compilación y condicionales

Question

Estaba leyendo las respuestas a "Printing 1 to 1000 without loop or conditionals" y me pregunto por qué es necesario tener el caso especial para NumberGeneration < 1> en la respuesta superior.

Si elimino eso y agrego un cheque para N == 1 en la plantilla (código debajo), el código falla la compilación con "la profundidad de la instanciación de la plantilla excede el máximo" pero no estoy seguro por qué. ¿Los condicionales se manejan de manera diferente en tiempo de compilación?

#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

¡La generación y compilación de código no se bifurca dependiendo de los condicionales! Considere esto:

// don't declare bar()! 

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

Si nunca declara bar(), esto es un error de compilación a pesar de que el alcance interno nunca puede ser alcanzado. Por la misma razón, NumberGeneration<N-1> siempre se instancia, independientemente de si se puede llegar a esa rama o no, y tiene recursión infinita.

De hecho, el análogo estática de los condicionales es precisamente especialización de plantilla:

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

Answer 2

Es porque los números enteros pueden ser negativos y el código de tiempo de ejecución (el cheque if) no detendrán el compilador crear instancias de la plantilla con 0, -1, -2, etc. Un compilador podría ser capaz de obtener de distancia con lo que propone, pero ¿qué pasa si la creación de instancias de las otras plantillas (0, -1, ...) tiene efectos secundarios de los que depende? El compilador no puede dejar de crear instancias para usted en ese caso.

En resumen, al igual que todas las recursiones tiene que proporcionar su propio caso base.

Answer 3

Me pregunto por qué es necesario contar con el caso especial de NumberGeneration < 1> en la respuesta superior.

Porque esa es la condición final para recursivo! Sin eso, ¿cómo podría el final recursivo?

Answer 4

El condicional if no será manejada en tiempo de compilación. Se manejará en tiempo de ejecución.

Por lo tanto, incluso para N = 1, el compilador generará NumberGenerator < 0>, entonces NumberGenerator < -1> ... sin fin, hasta llegar a la profundidad plantilla instanciación.

Answer 5

En general, la condición N == 1 en su código se evalúa en tiempo de ejecución (aunque el compilador puede optimizar esto), no en tiempo de compilación. Por lo tanto, la recursión de instanciación de plantilla en la cláusula else nunca termina. NumberGeneration<1> por otro lado se evalúa en tiempo de compilación y por lo tanto actúa como un caso de terminación de esta plantilla recursiva.

Answer 6

Estoy bastante seguro de que esto es específico del compilador; algunos compiladores pueden intentar generar ambas ramas del if/else cualquiera que sea el valor de N, en cuyo caso la compilación fallará en cualquier caso. Otros compiladores pueden evaluar la condición en tiempo de compilación y solo generar código para la rama que se ejecuta, en cuyo caso la compilación tendrá éxito.

ACTUALIZACIÓN: O como dice Luc en los comentarios, es posible que el compilador genere ambas ramas, por lo que el código siempre fallará. No estoy seguro de cuál es el caso, pero de cualquier forma es una mala idea confiar en las condiciones de tiempo de ejecución para controlar la generación de código en tiempo de compilación.

Sería mejor utilizar la especializació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; 
} 

(o usted podría acortar este ligeramente en lugar especializado para N=0, con una función out que no hace nada).

Además, tenga en cuenta que algunos compiladores pueden no admitir plantillas profundamente resursivas; C++ 03 sugiere una profundidad mínima admitida de solo 17, que C++ 11 aumenta a 1024. Debe verificar cuál es el límite de su compilador.

Answer 7

Las plantillas se instancian en tiempo de compilación, el caso especial de la plantilla evita que el compilador recurra por debajo de 1 al compilar.

if-clauses se evalúan en tiempo de ejecución, por lo que el compilador ya no compiló su código cuando tendría algún efecto.

Answer 8

Ésta es la forma correcta de hacerlo:

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); 
} 

Eso se llama plantilla de especialización: usted, el programador, proporcionan una definición alternativa para una instanciación particular de una plantilla. Puedes especializar toda la plantilla, o solo una parte, como hice aquí (solo he especializado la función, no toda la estructura).