У шаблонного (мета) программирования всегда есть только один способ реализации? - PullRequest
Новая
       17

У шаблонного (мета) программирования всегда есть только один способ реализации?

0 голосов
/ 19 июня 2011

Изучив несколько template программ и особенно метапрограмм, которые выводят результат во время компиляции в константу, я узнал, что в общем случае существует только один способ для реализации чего-либо. например: так просто, как пример factorial или так же сложно, как is_base_of

Я никогда не могу думать о совершенной альтернативной реализации такого кода, который имеет совершенно другую логику. Это верное предположение?

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

[Примечание: я не упоминаю об общем template использовании, которое мы делаем с class и функциями. Но использование для вывода постоянной времени компиляции.]

Ответы [ 5 ]

5 голосов
/ 19 июня 2011

Причина, по которой вы склонны видеть только один способ что-то сделать, состоит в том, что вещи, для которых люди на самом деле используют шаблонное метапрограммирование, обычно являются тривиальными алгоритмически - они просто выглядят сложными, потому что они перепутаны с нагрузкой типа хакерства истранности синтаксиса шаблонов C ++.

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

В качестве другого примераВот два способа оценки pow(a,b) (для аргументов малого целого):

Очевидное: 

// ----- Simple Way -----

template <int A, int B>
struct PowA {
    typedef PowA<A,B-1> next;
    enum {
       value = A * next::value,
       recursion_count = 1 + next::recursion_count
    };
};
template <int A> struct PowA<A, 1> { enum { value = A, recursion_count = 0 }; };
template <int A> struct PowA<A, 0> { enum { value = 1, recursion_count = 0 }; };

Чуть менее очевидно : 

// ----- Less Simple Way -----

template <int A, int B, int IsOdd> struct PowHelper;

template <int A> struct PowHelper<A, 0, 0> { enum { value = 1, recursion_count = 0 }; };
template <int A> struct PowHelper<A, 1, 1> { enum { value = A, recursion_count = 0 }; };

template <int A, int B>
struct PowHelper<A, B, 1> {
    typedef PowHelper<A, B-1, 1> next;
    enum {
        value = A * next::value,
        recursion_count = 1 + next::recursion_count
    };
};
template <int A, int B>
struct PowHelper<A, B, 0> {
    typedef PowHelper<A, B/2, ((B/2)&1)> next;
    enum {
        x = next::value,
        value = x*x,
        recursion_count = 1 + next::recursion_count
    };
};

template <int A, int B>
struct PowB {
    typedef PowHelper<A,B,(B & 1)> helper;
    enum {
        value = helper::value,
        recursion_count = helper::recursion_count
    };
};

И некоторый код, чтобы вы могли проверить это: 

// ----- Test -----

#include <iostream>

int main(int argc, char* argv[]) {
#define CHECK(X,Y) \
    std::cout << ("PowA: " #X "**" #Y " = ") << \
        PowA<(X),(Y)>::value << " (recurses " << \
        PowA<(X),(Y)>::recursion_count << " times)" << std::endl; \
    std::cout << ("PowB: " #X "**" #Y " = ") << \
        PowB<(X),(Y)>::value << " (recurses " << \
        PowB<(X),(Y)>::recursion_count << " times)" << std::endl;

    CHECK(3,3)
    CHECK(2,8)
    CHECK(7,3)
    CHECK(3,18)

#undef CHECK

   return 0;
}
3 голосов
/ 19 июня 2011

В зависимости от того, что вы подразумеваете под «делать это по-другому». Вот две реализации TMP для вычисления числа треугольника: 

template<int N>
struct RecursiveTriangle {
    static const int value = RecursiveTriangle<N-1>::value + N;
};

template<>
struct RecursiveTriangle<0> {
    static const int value = 0;
};

template<int N>
struct Triangle {
    static const int value = (N*(N+1))/2;
};

Они точно аналогичны двум «различным» способам вычисления чисел треугольников обязательно - с помощью цикла или с той же формулой, что и Triangle. Их область определения отличается, хотя - Triangle обрабатывает отрицательные числа, а RecursiveTriangle - нет. Не то, чтобы результат Triangle для отрицательных чисел имел большой смысл.

Итак, что вы подразумеваете под "различными способами сделать это"?

1 голос
/ 19 июня 2011

Давайте возьмем код для factorial из Википедии : 

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

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

Вы можете реализовать это альтернативно как: 

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

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

Или альтернативно как: 

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

template <>
struct Factorial<1> 
{
    enum { value = 1 };
};

template <>
struct Factorial<0> 
{
    enum { value = 1 };
};
1 голос
/ 19 июня 2011

Вообще говоря, отсутствие функций, доступных в TMP, и относительная простота функциональности - если не так, как это должно быть выражено - означает, что очень редко бывает более одной реализации, которая значительно отличается от .

1 голос
/ 19 июня 2011

Нет, есть не только одна реализация. Вот пример двух способов выполнения факториала: 

#include <iostream>
using namespace std;

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

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

template <int N>
class FactorialC {
public:
  static const long value = N * Factorial<N - 1>::value;
};

template <>
class FactorialC<10> {
public:
  static const long value = 3628800;
};

template <>
class FactorialC<0> {
public:
  static const long value = 0;
};

int main() {
  cout << Factorial<4>::value << endl;
  cout << Factorial<12>::value << endl;
  cout << FactorialC<4>::value << endl;
  cout << FactorialC<12>::value << endl;
}

Выход: 

24
479001600
24
479001600
...