¿Cuánto tiempo puede durar la compilación de plantillas?

Question

La metaprogramación de plantillas se puede usar para calcular cosas como factorial en tiempo de compilación en lugar de durante el tiempo de ejecución. He oído que algunos concursos de programación han introducido limitaciones en el tiempo de compilación exactamente para eliminar el abuso de la metaprogramación de plantillas.

¿Hay algún ejemplo inocente de usar plantillas que demore bastante tiempo (como varias horas) en compilarse?

Answer 1

He oído que la Olimpiada Internacional en Informática (un concurso de programación de este tipo) introdujo por primera vez los límites de tiempo de compilación después de que un concursante creó un vector de 7 dimensiones usando una técnica muy similar a this. Su código tuvo que ser compilado durante la noche, fue tan malo. Creo que esto ocurrió en algún momento a finales de los 90.

Answer 2

El mecanismo de plantilla es Turing-completo. Esto significa que, al menos en teoría, cualquier cálculo que se pueda hacer se puede hacer en tiempo de compilación de esta manera (en la práctica puede encontrarse con límites duros en profundidad de plantilla, etc. bastante rápido, pero esto depende del compilador).

Si desea hacer esto o no, es una pregunta separada. Puede combinar trivialmente su criterio de "horas para compilar" utilizando un algoritmo costoso. Pero también hay códigos más prácticos como this one implementing an FFT; dan que establecen una gran cantidad de datos suficientes y tardará un tiempo ...

Answer 3

Prueba esto (i utiliza Visual Studio 2005)

template <int M, int N> 
struct Ack 
{ 
    enum { value = Ack<M - 1, Ack<M, N - 1>::value >::value }; 
}; 

template <int M> 
struct Ack<M, 0> 
{ 
    enum { value = Ack<M - 1, 0>::value }; 
}; 

template <> 
struct Ack<0, 0> 
{ 
    enum { value = 1 }; 
}; 

template <int N> 
struct Ack<0, N> 
{ 
    enum { value = N + 1 }; 
}; 

void main() 
{ 
    printf("Result: %d\n", Ack<150, 150>::value); 
} 

Es tal vez parece horribble, he intentado escribir un equivalente a este función Lisp linda

(defun ack(m, n) 
cond ((= m 0) (+ n 1)) 
    ((= n 0) ack(- m 1) n) 
    (t (ack (- m 1) (ack m (-n 1)))) 
) 

Nuestro profesor dijo que es función de Ferma, pero no estoy seguro ...