Компилировать циклы времени

Я хотел бы знать, возможно ли иметь какие-то промежутки времени компиляции.
Например, у меня есть следующий шаблонный класс:

template<class C, int T=10, int B=10>
class CountSketch
{
public:
    CountSketch()
    {   
         hashfuncs[0] = &CountSketch<C>::hash<0>;
         hashfuncs[1] = &CountSketch<C>::hash<1>;
         // ... for all i until i==T which is known at compile time
    };
private:
    template<int offset>
    size_t hash(C &c)
    {
        return (reinterpret_cast<int>(&c)+offset)%B;
    }
    size_t (CountSketch::*hashfuncs[T])(C &c);
};

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

Конечно, в этом конкретном примере я мог бы просто создать одну хеш-функцию с двумя параметрами (хотя это было бы менее эффективно, я думаю). Поэтому я не заинтересован в решении этой конкретной проблемы, а знаю, что для подобных случаев существовали "компиляции временных циклов".

Спасибо!

Ответ 1

Нет, это невозможно. Метапрограммирование шаблонов - это чисто функциональный язык. Каждое значение или тип, определенные через него, являются неизменными. В цикле по существу требуются изменяемые переменные (многократно проверяйте некоторое условие до тех пор, пока не произойдет X, а затем выйдите из цикла).

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

Однако это может решить все те же проблемы, что и цикл.

Редактирование: здесь быстрый пример, вычисляющий факториал N с использованием рекурсии во время компиляции:

template <int N>
struct fac {
  enum { value = N * fac<N-1>::value };
};

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

int main() {
  assert(fac<4>::value == 24);
}

Метапрограммирование шаблонов на С++ является языком Turing-complete, поэтому, пока вы не используете различные внутренние ограничения компилятора, вы можете решить в основном любую проблему с ним.

Однако для практических целей может быть целесообразным исследовать библиотеки, такие как Boost.MPL, который содержит большое количество структур данных и алгоритмов, которые упрощают множество задач метапрограммирования.

Ответ 2

Да. Возможно использование рекурсии времени компиляции.

Я пытался с вашим кодом, но поскольку он не был компилируемым, это модифицированная и компиляция exmaple:

template<class C, int T=10>
class CountSketch
{
  template<int N>
  void Init ()
  {
    Init<N-1>();
    hashfuncs[N] = &CountSketch<C>::template hash<N>;
    cout<<"Initializing "<<N<<"th element\n";
  }

public:
    CountSketch()
    {
      Init<T>();
    }
private:
   template<int offset>
   size_t hash(C &c)
   {
     return 0;
   }
   size_t (CountSketch::*hashfuncs[T])(C &c);
};

template<>
template<>
void CountSketch<int,10>::Init<0> ()
{
  hashfuncs[0] = &CountSketch<int,10>::hash<0>;
  cout<<"Initializing "<<0<<"th element\n";
}

Демо. Единственным ограничением этого решения является то, что вы должны предоставить окончательную специализированную версию как CountSketch<int,10>::Init<0> для любого типа и размера.

Ответ 3

Вам нужна комбинация boost:: mpl:: for_each и повышение:: MPL:: range_c.

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

Фактическая сложность заключается в том, чтобы построить структуру, которая была построена шаблоном по параметру int (mpl:: int_ в нашем случае), и которая выполняет назначение при вызове operator(), и нам также нужен функтор для фактического захвата этот указатель.

Это несколько сложнее, чем я ожидал, но это весело.

#include <boost/mpl/range_c.hpp>
#include <boost/mpl/vector.hpp>
#include <boost/mpl/for_each.hpp>
#include <boost/mpl/transform.hpp>
#include <boost/mpl/copy.hpp>

// aforementioned struct
template<class C, class I>
struct assign_hash;

// this actually evaluates the functor and captures the this pointer
// T is the argument for the functor U
template<typename T>
struct my_apply {
  T* t;
  template<typename U>
  void operator()(U u) {
    u(t);
  }
};

template<class C, int T=10, int B=10>
class CountSketch
{
public:
  CountSketch()
    {   
      using namespace boost::mpl;

      // we need to do this because range_c is not an ExtensibleSequence
      typedef typename copy< range_c<int, 0, T>,
                             back_inserter< vector<> > >::type r;
      // fiddle together a vector of the correct types
      typedef typename transform<r, typename lambda< assign_hash<C, _1 > >::type >
        ::type assignees;

      // now we need to unfold the type list into a run-time construct
      // capture this
      my_apply< CountSketch<C, T, B> > apply = { this };
      // this is a compile-time loop which actually does something at run-time
      for_each<assignees>(apply);
    };

  // no way around
  template<typename TT, typename I>
  friend struct assign_hash;

private:
  template<int offset>
  size_t hash(C& c)
    {
      return c;
      // return (reinterpret_cast<int>(&c)+offset)%B;
    }
  size_t (CountSketch::*hashfuncs[T])(C &c);
};

// mpl uses int_ so we don't use a non-type template parameter 
// but get a compile time value through the value member
template<class C, class I>
struct assign_hash {
  template<typename T>
  void operator()(T* t) {
    t->hashfuncs[I::value] = &CountSketch<C>::template hash<I::value>;
  }
};

int main() 
{
  CountSketch<int> a;
}

Ответ 4

Есть компиляторы, которые будут видеть цикл и разворачивать его. Но это не часть спецификации языка, что это должно быть сделано (и, по сути, спецификация языка бросает всевозможные препятствия на пути ее выполнения), и нет никакой гарантии, что в конкретном случае это будет сделано, даже в компиляторе, который "знает, как".

Есть несколько языков, которые явно делают это, но они очень специализированы.

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

Ответ 5

Вот, я думаю, лучшая версия решения, приведенная выше.
Вы можете видеть, что мы используем время компиляции в параметрах функции.
Это позволяет помещать всю логику внутри вашего класса, а базовый случай Init (int_ < -1 > ) очень ясен - просто ничего не делать:)
Только так вы не будете бояться штрафа за производительность, знаете, что оптимизатор выбросит эти неиспользуемые параметры.
По сути, все эти вызовы функций будут в любом случае встраиваться. что весь смысл здесь.

#include <iostream>
using namespace std;

template <class C, int N = 10>
class CountSketch {
 public:
  CountSketch() {
    memset(&hashfuncs, sizeof(hashfuncs), 0); // for safety
    // Notice: we start with (N-1) since we need a zero based index
    Init(int_<N - 1>());
  }

 private:
  template <int offset>
  size_t hash(C &c) {
    return 0;
  }

  size_t (CountSketch::*hashfuncs[N])(C &c);

 private: // implementation detail

  // Notice: better approach.
  // use parameters for compile-time recursive call.
  // you can just override for the base case, as seen for N-1 below
  template <int N>
  struct int_ {};

  template <int N>
  void Init(int_<N>) {
    Init(int_<N - 1>());
    hashfuncs[N] = &CountSketch<C>::template hash<N>;
    cout << "Initializing " << N << "th element\n";
  }

  void Init(int_<-1>)  // Notice: this gives you the N=0 case for free!
  {}
};

int main() {
  CountSketch<int, 10> cs;
  return 0;
}