È possibile creare e inizializzare una matrice di valori usando la metaprogrammazione del modello?

Question

Voglio essere in grado di creare una matrice di valori calcolati (diciamo per semplicità che voglio che ogni valore sia il quadrato del suo indice) in fase di compilazione usando la metaprogrammazione del modello. È possibile? Come viene inizializzata ogni posizione nell'array?

(sì, ci sono modi più semplici per fare questo senza ricorrere a template metaprogrammazione, chiedo solo se è possibile farlo con un array.)

Answer 1

Anche se non è possibile inizializzare una matrice sul posto come quello, si può fare quasi la stessa cosa con la creazione di un ricorsiva 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) {} 
}; 

Poi più avanti nel codice è possibile dichiarare:

squared<5> s; 

e il compilatore effettivamente creare un struct contenente 5 int s: 0, 1, 4, 16, 25.

Un paio di note:

1. La mia interpretazione dello standard C++ è che si ferma a corto di garantendo che questo struct saranno disposte in modo identico a un array. Mentre è un tipo POD, i tipi POD sono garantiti per essere disposti "contigui" in memoria (1.8/5) con il primo membro all'offset 0 (9.2/17) e i membri successivi agli indirizzi più alti (9.2/12), e gli array sono disposti "contiguously" (8.3.4/1), lo standard non dice che gli array sono compatibili con il layout con tali struct s. Comunque, qualsiasi compilatore sano deporrà questi oggetti in modo identico. [EDIT: come osserva ildjarn, la presenza di un costruttore definito dall'utente rende in effetti questa classe non aggregata e quindi non POD. Ancora una volta, qualsiasi compilatore sensato non permetterà a questo di influenzare il suo layout.]
2. C++ richiede che anche un struct vuoto sia lungo almeno 1 byte. Se così non fosse, potremmo optare per una formulazione leggermente più pulita in cui il caso base della ricorsione era I == 0 e non abbiamo sottratto 1 da I per i calcoli.

Sarebbe bello poter collocare questo struct all'interno di una union con una serie di dimensioni appropriate, per rendere più facile l'accesso membri. Sfortunatamente, C++ vieta di includere un oggetto in un union se quell'oggetto ha un costruttore non banale. Quindi il modo più semplice per ottenere al esimo elemento i è con un buon cast vecchio stile:

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

Se si volesse, si potrebbe scrivere un modello operator[]() funzione sovraccaricata per rendere questo più bella.

Answer 2

Si può avere che per gli array a dimensione fissa:

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

Gli array di dimensioni arbitrarie tuttavia non possono essere eseguiti senza la meta-programmazione del preprocessore - Boost.Preprocessor può essere d'aiuto.

Un'altra cosa che potresti voler esaminare sono le sequenze in fase di compilazione delle costanti integrali, ad es. utilizzando 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 

(Si noti che questo potrebbe essere fatto probabilmente più elegante utilizzando algoritmi MPL)

Se siete più curiosi di sapere il tempo di compilazione soggetto dei libri "moderna C++ Design" (Nozioni di base su TMP) e "C++ Template Metaprogramming" (principalmente MPL spiegato in dettaglio) vale la pena esaminare.

Answer 3

Potrebbe essere più sensato utilizzare specializzazioni rispetto a un array reale. Tuttavia diventa complicato ... l'ho fatto per un algoritmo di hashing delle stringhe che ho fatto con la metaprogrammazione dei modelli. Parte dell'algoritmo utilizzato una grande tabella di ricerca, che ha finito per assomigliare:

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

E stata letta in questo modo:

CrcTab<index>::value 

Il vantaggio di questo è che è possibile utilizzare i risultati nella metaprogramma , dove non saresti in grado di accedere all'array.

Per il valore del quadrato dell'argomento non è nemmeno necessario specializzarsi. Attenzione: compilatore non a portata di mano ...

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

In realtà questo mette in evidenza lo svantaggio di questo approccio, non è possibile indice con una variabile ... solo una costante.

Answer 4

Non sono sicuro se vuoi vederlo fatto o trovare una libreria che lo farà solo per te. Presumo il primo.

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[]) { } 
}; 

Ora cerchiamo di utilizzare questa 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 (confessione): Questo non è compilare-tempo di calcolo. Per motivare puoi provare a cambiare la quarta riga da SqArr<N-1>::fill(arr); a SqArr<N>::fill(arr); in modo che la ricorsione sia infinita, e vedrai che questo si compila bene (quando il compilatore dovrebbe infatti recedere indefinitamente o lamentarsi della ricorsione infinita).

Answer 5

Si chiama Static Table Generation in metaprogrammazione.

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

Usiamo esplicito modello di istanza e una variabile dummy per forzare il compilatore a riempire l'array con quadrati di indice. La parte dopo I * I è il trucco necessario per assegnare in modo ricorsivo ogni elemento dell'array.

Answer 6

È possibile in C++ 0x utilizzando modelli variadic. Ecco come creare una tabella di coefficienti binomiali:

//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> {}; 

per accedere agli elementi usa una sintassi del tipo binomiale <N> :: valore [k], dove N è compilazione costante di tempo e k è indice che varia da 0 a N inclusivo.

Answer 7

Mi piace molto la risposta di j_random_hackers - è bella e corta.Con C++ 11, si può estendere a questo

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

Questo codice è utilizzabile sia in fase di esecuzione

squared<10> s; 

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

nonché compilazione

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

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

e fornisce un piacevole e sintassi leggibile