Как избежать бесконечной рекурсии в шаблонах классов 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

Требуется указать специализацию для матрицы, в которой нет строк или столбцов.

* 1003 Е.Г. *

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

Проблема, с которой вы столкнулись, заключается в том, что при попытке создать экземпляр функции Matrix Reduced с определенным набором параметров шаблона всегда требуется создание экземпляра шаблона Matrix для другого набора параметров (cRows - 1, cCols -1). Эта рекурсия должна быть где-то остановлена. Если вы когда-либо имели дело только с квадратными матрицами, то вам может понадобиться меньше специализаций.

Кроме того, вы можете остановить рекурсию с совершенно пустым классом, если вы никогда не собираетесь использовать, скажем, матрицу 1x1, результат сокращения на матрице 2x2.

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

Answer 2

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

Answer 3

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

Если у вас его еще нет, советую прочитать Шаблоны C ++: Полное руководство от Vandervoorde & Josuttis, которое подробно описывает подобные вещи.

Answer 4

Вместо того, чтобы специализировать весь класс для завершения рекурсии, другим вариантом может быть использование boost::enable_if в функции, чтобы сделать ее доступной только тогда, когда размер матрицы превышает 2x2.

Answer 5

Вам необходимо явно указать поведение для случая, когда вы хотите, чтобы рекурсия завершилась. См. эту статью 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 };
};