如何避免 C++ 中的无限递归 类模板

Question

我有一个矩阵类，其大小由模板参数确定。

template <unsigned cRows, unsigned cCols>
class Matrix {
    ...
};

我的程序使用几种大小的矩阵，通常为 2x2、3x3 和 4x4。 通过使用模板参数而不是运行时参数设置矩阵大小，允许编译器进行大量内联和优化。

但现在我需要一个成员函数，它返回一个少一行和一列的新矩阵。

Matrix<cRows - 1, cCols - 1> Reduced(unsigned row, unsigned col) const { ... }

这个想法是，它将返回一个删除了指定行和列的矩阵。 实际上，只有使用至少具有三行三列的矩阵才能调用此函数，并且最小返回 2x2。

编译器看不到下限，因此它陷入无限递归，试图实例化尺寸不断减小的模板。 我尝试在函数本身中添加两条线索，表明这些较小的大小不会发生：

Matrix<cRows - 1, cCols - 1> Reduced(unsigned row, unsigned col) const {
    static_assert(cRows > 1 && cCols > 1);
    if (cRows <= 1 || cCols <= 1) throw std::domain_error();
    Matrix<cRows - 1, cCols - 1> r;
    // ... initialize r ...
    return r;
}

static_assert 和 if 语句似乎都不是编译器足够有力的线索，表明0x0 矩阵永远不会生成。 （讽刺的是，它确实抱怨 if 语句具有恒定的编译时条件。）

有人对如何避免这种编译时无限递归有任何建议吗？

Answer 1

您需要为没有行或没有列的矩阵提供专门化。

例如，

template<unsigned cRows>
class Matrix< cRows, 0 >
{
    Matrix<cRows - 1, 0> Reduced() { return Matrix<cRows - 1, 0>(); }
};


template<unsigned cCols>
class Matrix< 0, cCols >
{
    Matrix<0, cCols - 1> Reduced() { return Matrix<0, cCols - 1>(); }
};


template<>
class Matrix< 0, 0 >
{
    Matrix<0, 0> Reduced() { return Matrix<0, 0>(); }
};

您遇到的问题是，尝试使用一组特定的模板参数实例化矩阵缩减函数始终需要为另一组参数实例化矩阵模板（cRows - 1，cCols -1）。 这个递归必须在某个地方停止。 如果您只处理方阵，那么您可以采用较少的专业化。

另外，如果您永远不会使用 1x1 矩阵（例如 2x2 矩阵上的 reduce 的结果），则可以使用完全空的类来停止递归。

template<>
class Matrix< 1, 1 > {};

Answer 2

您可以为不包含该方法的 cRows 或 cCols 小值指定模板特化。

Answer 3

您似乎对编译时和运行时行为有点困惑，我对您的代码也有点困惑，但我认为您想要的是值 0, 0 的模板的专门化，它终止递归。

如果您还没有读过，我建议您阅读
C++ 模板：完整指南 作者：Vandervoorde & Josuttis，其中详细介绍了此类事情。

Answer 4

您需要显式指定希望递归结束的情况的行为。 请参阅这篇 DDJ 文章了解更多详细信息。 这是文章中的一个简单示例：

template<int n>
class META_FACTORIAL
{
public:
  enum{
    RET = n * META_FACTORIAL<n-1>::RET
  };
};

template<>
class META_FACTORIAL<0>
{
public:
  enum{ RET = 1 };
};

Answer 5

另一种选择可能是在函数上使用 boost::enable_if ，使其仅在矩阵大小高于 2x2 时可用，而不是专门使用整个类来终止递归。