Подтвердить что ты не робот

Возможно ли создать и инициализировать массив значений с помощью метапрограммирования шаблонов?

Я хочу, чтобы иметь возможность создавать массив вычисляемых значений (скажем, для простоты, что я хочу, чтобы каждое значение было квадратом его индекса) во время компиляции с использованием метапрограммирования шаблонов. Это возможно? Как инициализируется каждое местоположение в массиве?

(Да, есть более простые способы сделать это, не прибегая к метапрограммированию шаблонов, просто задаваясь вопросом, возможно ли это сделать с помощью массива.)

4b9b3361

ОТВЕТЫ

Ответ 1

Хотя вы не можете инициализировать массив таким образом, вы можете сделать почти то же самое, создав рекурсивный 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) {}
};

Затем в вашем коде вы можете объявить:

squared<5> s;

и компилятор действительно создаст struct, содержащий 5 int s: 0, 1, 4, 16, 25.

Несколько примечаний:

  • Моя интерпретация стандарта С++ заключается в том, что она не позволяет гарантировать, что этот struct будет выровнен идентично массиву. Хотя это тип POD, и типы POD гарантированно будут "соприкасаться" в памяти (1.8/5) с первым членом со смещением 0 (9.2/17) и более поздними членами с более высокими адресами (9.2/12), и массивы также выложены "смежно" (8.3.4/1), стандарт не говорит, что массивы совместимы с макетами с такими struct s. Однако любой здравомыслящий компилятор будет выставлять эти объекты одинаково. [EDIT: Как указывает ildjarn, наличие определяемого пользователем конструктора фактически делает этот класс неагрегатным и, следовательно, не-POD. Опять же, любой здравомыслящий компилятор не позволит этому повлиять на его компоновку.]
  • С++ требует, чтобы даже пустой struct был как минимум 1 байт. Если бы это не так, мы могли бы пойти с более чистым формулированием, в котором базовый случай рекурсии был I == 0, и мы не вычитали 1 из I для вычислений.

Было бы неплохо, если бы мы могли разместить этот struct внутри union с массивом соответствующего размера, чтобы упростить доступ к членам. К сожалению, С++ запрещает вам включать объект в union, если этот объект имеет нетривиальный конструктор. Таким образом, самый простой способ получить элемент I th - это хороший старомодный актер:

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

Если вы хотите, вы можете написать перегруженный шаблон функции operator[](), чтобы сделать это более красивым.

Ответ 2

Он вызвал Static Table Generation в метапрограммировании.

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

Мы используем явное создание экземпляра шаблона и фиктивную переменную, чтобы заставить компилятор заполнить массив квадратами индекса. Часть после я * я - это трюк, необходимый для рекурсивного назначения каждого элемента массива.

Ответ 3

В С++ 0x возможно использование вариационных шаблонов. Вот пример создания таблицы биномиальных коэффициентов:

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

Для доступа к элементам используется синтаксис типа binomial <N> :: value [k], где N - константа времени компиляции, а k - индекс от 0 до N включительно.

Ответ 4

Это может быть для массивов фиксированного размера:

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

Массивы произвольного размера, однако, не могут быть выполнены без метапрограмм препроцессора - Boost.Preprocessor может помочь здесь.

Еще одна вещь, которую вы, возможно, захотите изучить, - это последовательности времени компиляции интегральных констант, например. используя 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

(Обратите внимание, что это, вероятно, можно было бы более элегантно использовать с помощью алгоритмов MPL)

Если вам больше любопытно рассказать о предметах с компиляцией, стоит посмотреть на книги "Современный дизайн С++" (основы TMP) и "Метапрограммирование шаблонов С++" (в основном, MPL).

Ответ 5

Мне очень нравится ответ j_random_hackers - его красивый и короткий. С С++ 11 это можно расширить до

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

Этот код можно использовать как во время выполнения

  squared<10> s;

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

а также время компиляции

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

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

и обеспечивает хороший и читаемый синтаксис.

Ответ 6

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

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

И было доступно следующее:

CrcTab<index>::value

Преимущество этого заключается в том, что вы можете использовать результаты в метапрограмме, где вы не сможете получить доступ к массиву.

Для значения квадрата аргумента вам даже не нужно специализироваться. Предупреждение: компилятор не под рукой...

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

На самом деле это подчеркивает недостаток этого подхода, вы не можете индексировать переменную... только константу.

Ответ 7

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

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

Теперь попробуйте использовать этот зверь:

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

Примечание (признание): Это не вычисление времени компиляции. Чтобы мотивировать это, вы можете попытаться изменить четвертую строку от SqArr<N-1>::fill(arr); до SqArr<N>::fill(arr);, чтобы рекурсия была бесконечной, и вы увидите, что это компилируется отлично (когда компилятор должен на самом деле рекурсивно отчитываться или жаловаться на бесконечную рекурсию).