使用模板 class 专业化消除代码冗余的标准方法是什么？

Question

我有一个模板 class，它使用模板递归递归构建斐波那契数组，如下所示：

#include <iostream>
#include "C++ Helpers/static_check.hpp"
using namespace std;

template <typename T>
struct valid_type : std::integral_constant<bool, std::is_integral<T>::value  > {};

template <size_t N, typename = void>
struct fibonacci {
    static const int value = fibonacci<N - 1>::value + fibonacci<N - 2>::value;
};
template <size_t N>
struct fibonacci <N, typename std::enable_if<(N < 2)>::type > {
    static const int value = 1;
};
template <size_t N, typename T = int>
struct fibonacci_array {
    static_assert(valid_type<T>::value, "invalid storage type for fibonacci sequence");
// the base case specialization should has all general case code except for the next line
    fibonacci_array<N - 1, T> generate_sequence_here;
    int value;
    fibonacci_array() : value(fibonacci<N - 1>::value) {}
    int operator [] (size_t pos) {
        return *((int*)this + pos);
    }
};

template <typename T>
struct fibonacci_array<1, T> {
    static_assert(valid_type<T>::value, "invalid storage type for fibonacci sequence");
    int value;
    fibonacci_array() : value(fibonacci<0>::value) {}
    int operator [] (size_t pos) {
        return *((int*)this + pos);
    }
};

int main () {
    const size_t n = 10;
    fibonacci_array<n, int> arr;
    for(size_t i = 0; i < n; ++i)
        cout << arr[i] << endl;
    return 0;
}

我想做的是消除基本案例专业化中的代码冗余（当N == 1）注意：如果我将 class 成员划分为私有成员和 public 成员并使用直接继承，则效率不高，因为私有成员实际上被继承但无法访问它们。我正在考虑创建一个基础 class 来制作通用模板 class 并从中继承专业化，但我不知道它的确切语法，如果有更好的方法会更好.谢谢！

Answer 1

如何在 N=0 处终止递归？在这种情况下，您可以为 fibonacci_array<1, T> 丢弃整个 body 并替换为这个小家伙：

template <typename T>
struct fibonacci_array<0, T> 
{
};

一个陷阱是这个特化是空的，但是当你把它聚合到主 class 作为 generate_sequence_here 时，它会消耗 space 的 1 个字节，因为在 C++ 中每个 object 都应有一个唯一的地址。这将浪费你 1 个字节的 space（并且需要更新你的 operator[]）。不过不用担心，如果您将 fibonacci_array<N - 1, T> 的聚合更改为从中继承，则可以轻松解决。这要归功于名为 "empty base class optimization".

的功能

此外，如果您可以使用 C++14，请改用 constexpr 构造函数来完成此任务，代码会更简洁：

template <int N, typename T = int>
struct fibonacci_array 
{
    int values[N];
    constexpr fibonacci_array() : values()
    {
        if (N > 1)
            values[1] = 1;
        for (int i = 2; i < N; ++i)
            values[i] = values[i - 1] + values[i - 2];
    }
    constexpr int operator [] (size_t pos) const
    {
        return values[pos];
    }
};

参见demo。

另请参阅编译器如何在编译时计算它：https://godbolt.org/g/kJEFvN

Answer 2

抱歉...我不是标准专家...但我找到了您访问这些值的模式

    return *((int*)this + pos);

有点危险。

我建议避免 class 递归，使用简单的 constexpr 函数来计算值

template <typename T>
constexpr T fibonacci (T const & val)
 { return val < T{2} ? T{1} : (fibonacci(val-T{1})+fibonacci(val-T{2})); }

并且，使用委托构造函数，在一个简单的 class

中初始化一个 std::array

template <size_t N, typename T = std::size_t>
struct fibonacci_array
 {
   static_assert(std::is_integral<T>::value,
                 "invalid storage type for fibonacci sequence");

   std::array<T, N> values;

   template <T ... Is>
   constexpr fibonacci_array (std::integer_sequence<T, Is...> const &)
      : values{ { fibonacci(Is)... } }
    { }

   constexpr fibonacci_array ()
      : fibonacci_array{std::make_integer_sequence<T, N>{}}
    { }

   T operator [] (size_t pos) const
    { return values[pos]; }

   T & operator [] (size_t pos)
    { return values[pos]; }
 };

此解决方案使用 std::integer_sequence 和 std::make_integer_sequence，C++14 解决方案也是如此；但如果您需要 C++11 解决方案，用它们替代并不难。

完整的工作示例

#include <array>
#include <utility>
#include <iostream>
#include <type_traits>

template <typename T>
constexpr T fibonacci (T const & val)
 { return val < T{2} ? T{1} : (fibonacci(val-T{1})+fibonacci(val-T{2})); }

template <std::size_t N, typename T = std::size_t>
struct fibonacci_array
 {
   static_assert(std::is_integral<T>::value,
                 "invalid storage type for fibonacci sequence");

   std::array<T, N> values;

   template <T ... Is>
   constexpr fibonacci_array (std::integer_sequence<T, Is...> const &)
      : values{ { fibonacci(Is)... } }
    { }

   constexpr fibonacci_array ()
      : fibonacci_array{std::make_integer_sequence<T, N>{}}
    { }

   T operator [] (std::size_t pos) const
    { return values[pos]; }

   T & operator [] (std::size_t pos)
    { return values[pos]; }
 };

int main ()
 {
   constexpr std::size_t n { 10U };

   fibonacci_array<n, int> arr;

   for (auto i = 0U; i < n ; ++i )
      std::cout << arr[i] << std::endl;
 }

-- 编辑--

正如 Mikhail 所指出的，我的 fibonacci() 函数可以用指数复杂度进行计算。

使用相同的指数算法，但在结构中使用静态 constexpr 值，因此使用记忆（我希望），以下代码应避免指数复杂度。

#include <array>
#include <utility>
#include <iostream>
#include <type_traits>

template <typename T, T N, bool = (N < T{2})>
struct fibonacci;

template <typename T, T N>
struct fibonacci<T, N, false>
   : std::integral_constant<T,   fibonacci<T, N-1U>::value
                               + fibonacci<T, N-2U>::value>
 { };

template <typename T, T N>
struct fibonacci<T, N, true>
   : std::integral_constant<T, 1U>
 { };

template <std::size_t N, typename T = std::size_t>
struct fibonacci_array
 {
   static_assert(std::is_integral<T>::value,
                 "invalid storage type for fibonacci sequence");

   std::array<T, N> values;

   template <T ... Is>
   constexpr fibonacci_array (std::integer_sequence<T, Is...> const &)
      : values{ { fibonacci<T, Is>::value... } }
    { }

   constexpr fibonacci_array ()
      : fibonacci_array{std::make_integer_sequence<T, N>{}}
    { }

   T operator [] (std::size_t pos) const
    { return values[pos]; }

   T & operator [] (std::size_t pos)
    { return values[pos]; }
 };

int main ()
 {
   constexpr std::size_t n { 10U };

   constexpr fibonacci_array<n, int> const arr;

   for (auto i = 0U; i < n ; ++i )
      std::cout << arr[i] << std::endl;
 }

使用模板 class 专业化消除代码冗余的标准方法是什么？

what is the standard way to eliminate code redundancy with template class specialization?

c++

templates

template-specialization

template-meta-programming

c++11