¿Es posible crear e inicializar una matriz de valores utilizando la metaprogramación de plantillas?

Question

Quiero ser capaz de crear una matriz de valores calculados (supongamos, por simplicidad, que quiero que cada valor sea el cuadrado de su índice) en tiempo de compilación utilizando la metaprogramación de plantillas. es posible? ¿Cómo se inicializa cada ubicación en la matriz?

(Sí, hay maneras más fáciles de hacer esto sin tener que recurrir a metaprogramming plantilla, simplemente preguntando si es posible hacer esto con una matriz.)

Answer 1

Aunque no se puede inicializar una matriz en lugar de esa manera, se puede hacer casi lo mismo mediante la creación de un recursiva struct:

template <int I> 
struct squared { 
    squared<I - 1> rest; 
    int x; 
    squared() : x((I - 1) * (I - 1)) {} 
}; 

template <> 
struct squared<1> { 
    int x; 
    squared() : x(0) {} 
}; 

Entonces adelante en el código se puede declarar:

squared<5> s; 

y el compilador de hecho creará un struct contiene 5 int s: 0, 1, 4, 16, 25.

Un par de notas:

1. Mi interpretación de la norma C++ es que no llega a garantizando que este struct será colocado de forma idéntica a una matriz. Si bien es un tipo de POD, y los tipos de POD están garantizados para colocarse "contiguamente" en la memoria (1.8/5) con el primer miembro en el desplazamiento 0 (9.2/17) y los miembros posteriores en las direcciones más altas (9.2/12), y las matrices también se presentan "contiguamente" (8.3.4/1), la norma no dice que las matrices son compatible con la disposición con tales struct s. Sin embargo, cualquier compilador sano expondrá estos objetos de forma idéntica. [EDITAR: Como señala ildjarn, la presencia de un constructor definido por el usuario realmente hace que esta clase no sea agregada y, por lo tanto, que no sea POD. Una vez más, cualquier compilador sane no permitirá que esto afecte su diseño.]
2. C++ requiere que incluso un struct vacío tenga al menos 1 byte de longitud. Si no fuera así, podríamos ir con una formulación ligeramente más limpia en la que el caso base de la recursión fuera I == 0 y no restaramos 1 de I para los cálculos.

Sería bueno si pudiéramos colocar este struct dentro de un union con una matriz de tamaño apropiado, para hacer más fácil el acceso a los usuarios. Desafortunadamente, C++ le prohíbe incluir un objeto en un union si ese objeto tiene un constructor no trivial. Así que la forma más fácil de llegar a la ésimo elemento es i con un buen reparto pasada de moda:

squared<5> s; 
cout << "3 squared is " << reinterpret_cast<int*>(&s)[3] << endl; 

Si quisiera, podría escribir una plantilla de operator[]() función sobrecargada para hacer esta bonita.

Answer 2

Usted puede tener que para las matrices de tamaño fijo:

int a[] = { foo<0>::value, foo<1>::value, ... }; 

Arrays de tamaño arbitrario, sin embargo no se pueden hacer sin metaprogramación de preprocesador - Boost.Preprocessor puede ayudar aquí.

Otra cosa en la que puede que desee tener en cuenta son las secuencias en tiempo de compilación de las constantes integrales, p. utilizando Boost.MPL:

template<int n> 
struct squares { 
    typedef typename squares<n-1>::type seq; 
    typedef typename boost::mpl::integral_c<int, n*n>::type val;  
    typedef typename boost::mpl::push_back<seq, val>::type type; 
}; 

template<> 
struct squares<1> { 
    typedef boost::mpl::vector_c<int, 1>::type type; 
}; 

// ... 
typedef squares<3>::type sqr; 
std::cout << boost::mpl::at_c<sqr, 0>::type::value << std::endl; // 1 
std::cout << boost::mpl::at_c<sqr, 1>::type::value << std::endl; // 4 
std::cout << boost::mpl::at_c<sqr, 2>::type::value << std::endl; // 9 

(Tenga en cuenta que esto probablemente se podría hacer más elegante utilizando MPLS algoritmos)

Si usted es más curioso sobre el tiempo de compilación sujetos los libros "Modern C Diseño ++" (conceptos básicos de TMP) y "Metaprogramación de plantillas C++" (principalmente MPL explicado en profundidad).

Answer 3

Puede ser más sensato usar especializaciones que una matriz real. Sin embargo, se pone complicado ... Hice esto para un algoritmo hash de cadenas que hice con la metaprogramación de plantillas. Parte del algoritmo utiliza una tabla de consulta grande, que terminó pareciéndose a:

template <> struct CrcTab<0x00> { enum { value = 0x00000000 }; }; 
template <> struct CrcTab<0x01> { enum { value = 0x77073096 }; }; 
template <> struct CrcTab<0x02> { enum { value = 0xee0e612c }; }; 

Y se accedió así:

CrcTab<index>::value 

La ventaja de esto es que usted puede utilizar los resultados en el metaprograma , donde no podría acceder a la matriz.

Por el valor del cuadrado del argumento, ni siquiera necesita especializarse. Advertencia: compilador no práctico ...

template <uint32_t N> struct Square { enum { value = N*N }; }; 

En realidad esto pone de manifiesto la desventaja de este enfoque, que no pueden indexar con una variable ... solamente una constante.

Answer 4

No estoy seguro de si desea verlo o encontrar una biblioteca que lo haga por usted. Supongo que el primero.

template<int N> 
struct SqArr { 
    static inline void fill(int arr[]) { 
     arr[N-1] = (N-1)*(N-1); 
     SqArr<N-1>::fill(arr); 
    } 
}; 

template<> 
struct SqArr<0> { 
    static inline void fill(int arr[]) { } 
}; 

Ahora vamos a tratar de utilizar esta bestia:

#include <iostream> 
#include <algorithm> 
#include <iterator> 

using namespace std; 

int main(int argc, char* argv[]) 
{ 
    int arr[10]; 
    SqArr<10>::fill(arr); 
    cout << endl; 
    copy(arr, arr+10, ostream_iterator<int>(cout, "\t")); 
    cout << endl; 
    return 0; 
} 

Nota (confesión): Esto no es compilar-tiempo de cálculo. Para motivarlo, puede tratar de cambiar la cuarta línea de SqArr<N-1>::fill(arr); a SqArr<N>::fill(arr);, por lo que la recursión es infinita, y verá que esta compila muy bien (cuando el compilador debería de hecho recurrir indefinidamente, o quejarse de la recursión infinita).

Answer 5

Se llama Static Table Generation en metaprogramación.

#include <iostream> 

const int ARRAY_SIZE = 5; 

template <int N, int I=N-1> 
class Table : public Table<N, I-1> 
{ 
public: 
    static const int dummy; 
}; 

template <int N> 
class Table<N, 0> 
{ 
public: 
    static const int dummy; 
    static int array[N]; 
}; 

template <int N, int I> 
const int Table<N, I>::dummy = Table<N, 0>::array[I] = I*I + 0*Table<N, I-1>::dummy; 

template <int N> 
int Table<N, 0>::array[N]; 

template class Table<ARRAY_SIZE>; 

int main(int, char**) 
{ 
    const int *compilerFilledArray = Table<ARRAY_SIZE>::array; 
    for (int i=0; i < ARRAY_SIZE; ++i) 
     std::cout<<compilerFilledArray[i]<<std::endl; 
} 

Utilizamos instancias de plantilla explícita y una variable ficticia para forzar al compilador para llenar la matriz con cuadrados de índice. La parte posterior a I * I es el truco necesario para asignar recursivamente cada elemento de la matriz.

Answer 6

Es posible en C++ 0x utilizando plantillas variadic. Aquí es ejemplo cómo crear una tabla de coeficientes binomiales:

//typedefs used 
typedef short int    index_t; 
typedef unsigned long long int int_t; 

//standard recursive template for coefficient values, used as generator 
template <index_t n, index_t k> struct coeff {static int_t const value = coeff<n-1, k-1>::value + coeff<n-1, k>::value;}; 
template <index_t n>   struct coeff<n, 0> {static int_t const value = 1;}; 
template <index_t n>   struct coeff<n, n> {static int_t const value = 1;}; 

//helper template, just converts its variadic arguments to array initializer list 
template<int_t... values> struct int_ary {static int_t const value[sizeof...(values)];}; 
template<int_t... values> int_t const int_ary<values...>::value[] = {values...}; 

//decrement k, pile up variadic argument list using generator 
template<index_t n, index_t k, int_t... values> struct rec: rec<n, k-1, coeff<n, k-1>::value, values...> {}; 
//when done (k == 0), derive from int_ary 
template<index_t n,   int_t... values> struct rec<n, 0, values...>: int_ary<values...> {}; 

//initialise recursion 
template<index_t n> struct binomial: rec<n, n+1> {}; 

Para acceder a los elementos utilizan sintaxis como binomial <N> :: valor [k], donde N es compilar constante de tiempo y k es el índice varía de 0 a N inclusive.

Answer 7

Me gusta mucho j_random_hackers answer - es hermoso y corto.Con C++ 11, se puede extender esto a

template <int I> 
struct squared { 
    squared<I - 1> rest; 
    static const int x = I * I ; 
    constexpr int operator[](int const &i) const { return (i == I ? x : rest[i]); } 
    constexpr int size() const { return I; } 
}; 

template <> 
struct squared<0> { 
    static const int x = 0; 
    constexpr int operator[](int const &i) const { return x; } 
    constexpr int size() const { return 1; } 
}; 

Este código se puede utilizar tanto en tiempo de ejecución

squared<10> s; 

    for(int i =0; i < s.size() ; ++i) { 
    std::cout << "s[" << i << "]" << " = " << s[i] << std::endl; 
    } 

así como el tiempo de compilación

struct Foo { 
    static const squared<10> SquareIt; 
    enum { 
    X = 3, 
    Y = SquareIt[ X ] 
    }; 
}; 

int main() { 
    std::cout << "Foo::Y = " << Foo::Y << std::endl; 
} 

y proporciona una agradable y sintaxis legible