遞歸模板函數在初始化時導致負數組大小

我正在研究支持矩陣上各種數學運算的矩陣類。 Matrix類有三個模板參數：遞歸模板函數在初始化時導致負數組大小

template<typename T, int rows, int columns> 
class Matrix 
{ 
    ... 
};

這工作正常。然而，由於許多操作（例如顛倒矩陣並取其行列式）僅適用於矩形矩陣（其中行==列），因此我選擇使這些函數不是成員函數來控制模板參數，並且只允許這些操作在方塊矩陣：

template<typename T, int rc> 
const Matrix<T, rc, rc> inverse (const Matrix<T, rc, rc>& src) 
{ 
    ... 
}

我有幾個功能，以這種方式進行操作。

現在，我得到的錯誤信息非常複雜，因爲模板的使用已經將運行時堆棧跟蹤變成了編譯時堆棧跟蹤。以下是我認爲正在發生的事情：

我的矩陣類存儲它在三個方面的數據：指針的二維數組，行的一維數組，和列的一維數組（行和列是內部類在矩陣中聲明函數和函數作爲1d指針數組的包裝）。所有這些指針都指向Matrix數據。這允許在整個行和列上進行操作。
我得到的錯誤是這些數組的聲明，以及用於初始化行和列的構造函數中的一些其他臨時數組。錯誤消息是：

[錯誤]數組的大小爲負值。
堆棧跟蹤是巨大的，但它幾次通過功能subMatrix。許多這些函數以循環遞歸形式互相調用。
subMatrix採取與m行和n列的矩陣，並返回一個新的矩陣與m-1行和列n-1（一行和一列被移除以創建所述子矩陣）。
我已經確定這個函數從來沒有在我的代碼中小於2 x 2的矩陣上調用，但是我懷疑編譯器沒有檢測到這個。其他函數determinant計算方陣的行列式。此函數對於大於2 x 2的矩陣是遞歸的。在此函數的遞歸部分期間，它調用subMatrix，創建一個更小的矩陣，直到矩陣達到2 x 2的大小。
我懷疑我的問題出現從編譯器看到determinant中的遞歸併推斷subMatrix在逐漸變小的矩陣上被調用，並保持外推直到它達到-1的大小，這在聲明new =，更小矩陣的行和列時會導致錯誤（即使此代碼會從未被執行）。

我完全不知道如何解決這個問題，假設我已經準確地分析了情況。

這裏是我的代碼的相關位：

//matrix.h 
template <typename T, int rows, int columns> 

class Matrix 
{ 
public: 
    class Column; 

    class Row; 

private: 

    T* m_data[rows][columns]; //errors on these lines. 
    Row m_rows[rows]; 
    Column m_columns[columns]; 

// ... much more in class 

} 

//matrix.cpp 

template<typename T, int rows, int columns> 
const Matrix<T, rows - 1, columns - 1> Matrix<T, rows, columns>::subMatrix(int row, int column) const 
{ 
    Matrix<T, rows - 1, columns - 1> result; 

    if (row > rows || column > columns) 
    { 
     std::cout << "death: bad bounds\n"; 
     return result; 
    } 

    for (int m = 1, mr = 1; m <= rows; m ++) 
    { 
     if (m == row) 
     { 
      continue; 
     } 

     for (int n = 1, nr = 1; n <= columns; n ++) 
     { 
      if (n == column) 
      { 
       continue; 
      } 

      result.at(mr, nr) = *(m_data[m - 1][n - 1]); 

      nr ++; 
     } 

     mr ++; 
    } 

    return result; 
} 



template<typename T, int rc> 
T minor(const Matrix<T, rc, rc>& src, int m, int n) 
{ 
    return determinant(src.subMatrix(m, n)); 
} 


template<typename T, int rc> 
T cofactor(const Matrix<T, rc, rc>& src, int m, int n) 
{ 
    return pow(-1, m + n) * minor(src, m, n); 
} 



template<typename T, int rc> 
T determinant(const Matrix<T, rc, rc>& src) 
{ 
    T det; 

    if (rc == 2) 
    { 
     det = (src.get(1, 1) * src.get(2, 2)) - (src.get(1, 2) * src.get(2, 1)); 
     return det; 
    } 

    T temp; 

    for (int n = 1; n <= rc; n ++) 
    { 
     temp = src.get(1, n) * cofactor(src, 1, n); 
    } 

    return det; 
}

這一切都從這裏開始：

int main(void) 
{ 
    auto m1 = Matrix<int, 3, 3>().map(

    //lambda to fill the matrix with increasing values 
    [](int,int,int) { static int n = 0; return ++n; } 
    ); 

    int m2 = determinant(m1); //trace leads back to here 

    std::cout << m1 << '\n' << m2; 

    return 0; 
}

這裏是完整的「堆棧跟蹤」。我懷疑這會有幫助。

C:\Users\noah dove\Documents\Devcpp\matrix.h: In instantiation of 'class Matrix<int, -1, -1>': 
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:411:40: required from 'T minor(const Matrix<T, rc, rc>&, int, int) [with T = int; int rc = 0]' 
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:419:41: required from 'T cofactor(const Matrix<T, rc, rc>&, int, int) [with T = int; int rc = 0]' 

C:\Users\noah dove\Documents\Devcpp\matrix.cpp:439:3: required from 'T determinant(const Matrix<T, rc, rc>&) [with T = int; int rc = 0]' 
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:411:40: required from 'T minor(const Matrix<T, rc, rc>&, int, int) [with T = int; int rc = 1]' 
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:419:41: required from 'T cofactor(const Matrix<T, rc, rc>&, int, int) [with T = int; int rc = 1]' 
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:439:3: [ skipping 2 instantiation contexts ] 

C:\Users\noah dove\Documents\Devcpp\matrix.cpp:419:41: required from 'T cofactor(const Matrix<T, rc, rc>&, int, int) [with T = int; int rc = 2]' 
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:439:3: required from 'T determinant(const Matrix<T, rc, rc>&) [with T = int; int rc = 2]' 

C:\Users\noah dove\Documents\Devcpp\matrix.cpp:411:40: required from 'T minor(const Matrix<T, rc, rc>&, int, int) [with T = int; int rc = 3]' 
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:419:41: required from 'T cofactor(const Matrix<T, rc, rc>&, int, int) [with T = int; int rc = 3]' 
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:439:3: required from 'T determinant(const Matrix<T, rc, rc>&) [with T = int; int rc = 3]' 
C:\Users\noah dove\Documents\Devcpp\matrix_driver.cpp:9:26: required from here 
C:\Users\noah dove\Documents\Devcpp\matrix.h:21:25: error: size of array is negative 
C:\Users\noah dove\Documents\Devcpp\matrix.h:21:25: error: size of array is negative 
C:\Users\noah dove\Documents\Devcpp\matrix.h:22:17: error: size of array is negative 
C:\Users\noah dove\Documents\Devcpp\matrix.h: In instantiation of 'class Matrix<int, -1, -1>::Row': 
C:\Users\noah dove\Documents\Devcpp\matrix.h:22:17: required from 'class Matrix<int, -1, -1>' 
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:411:40: required from 'T minor(const Matrix<T, rc, rc>&, int, int) [with T = int; int rc = 0]' 
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:419:41: required from 'T cofactor(const Matrix<T, rc, rc>&, int, int) [with T = int; int rc = 0]' 

C:\Users\noah dove\Documents\Devcpp\matrix.cpp:439:3: required from 'T determinant(const Matrix<T, rc, rc>&) [with T = int; int rc = 0]' 
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:411:40: required from 'T minor(const Matrix<T, rc, rc>&, int, int) [with T = int; int rc = 1]' 
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:419:41: [ skipping 3 instantiation contexts ] 
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:419:41: required from 'T cofactor(const Matrix<T, rc, rc>&, int, int) [with T = int; int rc = 2]' 
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:439:3: required from 'T determinant(const Matrix<T, rc, rc>&) [with T = int; int rc = 2]' 
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:411:40: required from 'T minor(const Matrix<T, rc, rc>&, int, int) [with T = int; int rc = 3]' 
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:419:41: required from 'T cofactor(const Matrix<T, rc, rc>&, int, int) [with T = int; int rc = 3]' 
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:439:3: required from 'T determinant(const Matrix<T, rc, rc>&) [with T = int; int rc = 3]' 
C:\Users\noah dove\Documents\Devcpp\matrix_driver.cpp:9:26: required from here 

C:\Users\noah dove\Documents\Devcpp\matrix.h:105:20: error: size of array is negative 
C:\Users\noah dove\Documents\Devcpp\matrix.h: In instantiation of 'class Matrix<int, -1, -1>': 
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:411:40: required from 'T minor(const Matrix<T, rc, rc>&, int, int) [with T = int; int rc = 0]' 
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:419:41: required from 'T cofactor(const Matrix<T, rc, rc>&, int, int) [with T = int; int rc = 0]' 
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:439:3: required from 'T determinant(const Matrix<T, rc, rc>&) [with T = int; int rc = 0]' 
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:411:40: required from 'T minor(const Matrix<T, rc, rc>&, int, int) [with T = int; int rc = 1]' 
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:419:41: required from 'T cofactor(const Matrix<T, rc, rc>&, int, int) [with T = int; int rc = 1]' 
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:439:3: [ skipping 2 instantiation contexts ] 
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:419:41: required from 'T cofactor(const Matrix<T, rc, rc>&, int, int) [with T = int; int rc = 2]' 

C:\Users\noah dove\Documents\Devcpp\matrix.cpp:439:3: required from 'T determinant(const Matrix<T, rc, rc>&) [with T = int; int rc = 2]' 
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:411:40: required from 'T minor(const Matrix<T, rc, rc>&, int, int) [with T = int; int rc = 3]' 
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:419:41: required from 'T cofactor(const Matrix<T, rc, rc>&, int, int) [with T = int; int rc = 3]' 
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:439:3: required from 'T determinant(const Matrix<T, rc, rc>&) [with T = int; int rc = 3]' 
C:\Users\noah dove\Documents\Devcpp\matrix_driver.cpp:9:26: required from here 
C:\Users\noah dove\Documents\Devcpp\matrix.h:23:26: error: size of array is negative 
C:\Users\noah dove\Documents\Devcpp\matrix.h: In instantiation of 'class Matrix<int, -1, -1>::Column': 
C:\Users\noah dove\Documents\Devcpp\matrix.h:23:26: required from 'class Matrix<int, -1, -1>' 
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:411:40: required from 'T minor(const Matrix<T, rc, rc>&, int, int) [with T = int; int rc = 0]' 
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:419:41: required from 'T cofactor(const Matrix<T, rc, rc>&, int, int) [with T = int; int rc = 0]' 
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:439:3: required from 'T determinant(const Matrix<T, rc, rc>&) [with T = int; int rc = 0]' 
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:411:40: required from 'T minor(const Matrix<T, rc, rc>&, int, int) [with T = int; int rc = 1]' 

C:\Users\noah dove\Documents\Devcpp\matrix.cpp:419:41: [ skipping 3 instantiation contexts ] 

C:\Users\noah dove\Documents\Devcpp\matrix.cpp:419:41: required from 'T cofactor(const Matrix<T, rc, rc>&, int, int) [with T = int; int rc = 2]' 
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:439:3: required from 'T determinant(const Matrix<T, rc, rc>&) [with T = int; int rc = 2]' 

C:\Users\noah dove\Documents\Devcpp\matrix.cpp:411:40: required from 'T minor(const Matrix<T, rc, rc>&, int, int) [with T = int; int rc = 3]' 
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:419:41: required from 'T cofactor(const Matrix<T, rc, rc>&, int, int) [with T = int; int rc = 3]' 
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:439:3: required from 'T determinant(const Matrix<T, rc, rc>&) [with T = int; int rc = 3]' 
C:\Users\noah dove\Documents\Devcpp\matrix_driver.cpp:9:26: required from here 
C:\Users\noah dove\Documents\Devcpp\matrix.h:134:17: error: size of array is negative 
In file included from C:\Users\noah dove\Documents\Devcpp\matrix_driver.cpp:1:0: 
C:\Users\noah dove\Documents\Devcpp\matrix.cpp: In instantiation of 'Matrix<T, rows, columns>::Matrix(T) [with T = int; int rows = -1; int columns = -1]': 
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:365:35: required from 'const Matrix<T, (rows - 1), (columns - 1)> Matrix<T, rows, columns>::subMatrix(int, int) const [with T = int; int rows = 0; int columns = 0]' 
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:411:40: required from 'T minor(const Matrix<T, rc, rc>&, int, int) [with T = int; int rc = 0]' 

C:\Users\noah dove\Documents\Devcpp\matrix.cpp:419:41: required from 'T cofactor(const Matrix<T, rc, rc>&, int, int) [with T = int; int rc = 0]' 
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:439:3: required from 'T determinant(const Matrix<T, rc, rc>&) [with T = int; int rc = 0]' 

C:\Users\noah dove\Documents\Devcpp\matrix.cpp:411:40: required from 'T minor(const Matrix<T, rc, rc>&, int, int) [with T = int; int rc = 1]' 
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:419:41: [ skipping 3 instantiation contexts ] 
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:419:41: required from 'T cofactor(const Matrix<T, rc, rc>&, int, int) [with T = int; int rc = 2]' 
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:439:3: required from 'T determinant(const Matrix<T, rc, rc>&) [with T = int; int rc = 2]' 
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:411:40: required from 'T minor(const Matrix<T, rc, rc>&, int, int) [with T = int; int rc = 3]' 
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:419:41: required from 'T cofactor(const Matrix<T, rc, rc>&, int, int) [with T = int; int rc = 3]' 
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:439:3: required from 'T determinant(const Matrix<T, rc, rc>&) [with T = int; int rc = 3]' 
C:\Users\noah dove\Documents\Devcpp\matrix_driver.cpp:9:26: required from here 
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:11:25: error: size of array is negative 
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:12:28: error: size of array is negative 
C:\Users\noah dove\Documents\Devcpp\matrix.cpp: In instantiation of 'Matrix<T, rows, columns>::Matrix(const Matrix<T, rows, columns>&) [with T = int; int rows = -1; int columns = -1; Matrix<T, rows, columns> = Matrix<int, -1, -1>]': 
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:370:10: required from 'const Matrix<T, (rows - 1), (columns - 1)> Matrix<T, rows, columns>::subMatrix(int, int) const [with T = int; int rows = 0; int columns = 0]' 
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:411:40: required from 'T minor(const Matrix<T, rc, rc>&, int, int) [with T = int; int rc = 0]' 
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:419:41: required from 'T cofactor(const Matrix<T, rc, rc>&, int, int) [with T = int; int rc = 0]' 
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:439:3: required from 'T determinant(const Matrix<T, rc, rc>&) [with T = int; int rc = 0]' 
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:411:40: required from 'T minor(const Matrix<T, rc, rc>&, int, int) [with T = int; int rc = 1]' 
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:419:41: [ skipping 3 instantiation contexts ] 
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:419:41: required from 'T cofactor(const Matrix<T, rc, rc>&, int, int) [with T = int; int rc = 2]' 
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:439:3: required from 'T determinant(const Matrix<T, rc, rc>&) [with T = int; int rc = 2]' 
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:411:40: required from 'T minor(const Matrix<T, rc, rc>&, int, int) [with T = int; int rc = 3]' 
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:419:41: required from 'T cofactor(const Matrix<T, rc, rc>&, int, int) [with T = int; int rc = 3]' 
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:439:3: required from 'T determinant(const Matrix<T, rc, rc>&) [with T = int; int rc = 3]' 
C:\Users\noah dove\Documents\Devcpp\matrix_driver.cpp:9:26: required from here 
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:38:25: error: size of array is negative 
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:39:28: error: size of array is negative

如果有人能就此事提供任何協助，我將不勝感激。

來源

2013-08-30 ApproachingDarknessFish

你在哪裏實例化矩陣？顯然，第一行「Matrix Matrix 」顯示編譯器已經確定行==列== 0。你顯然不能創建一個負數大小的數組。 – nimrodm

@nimrodm如果你一路追溯，它首先調用'int main'中的3×3矩陣上的'determinant'。我現在將添加代碼。 – ApproachingDarknessFish

您的編譯日誌非常有針對性。您有一個遞歸擴展，最終會達到無效的數組維度。 'determinate（）'調用'cofactor（）'調用'minor（）'希望調用'determinate（）'和一個減小大小的子矩陣。重複此操作，直到大小對於使用它的基礎成員變量不再有效。最終由'minor（）'準備的子矩陣是無效的，因此是你的錯誤。這聽起來像你需要一個專門的'矩陣'，停止瘋狂。 – WhozCraig

rc == 2的特例不應該是代碼中的運行時檢查 - 它應該是部分特化，它會在編譯時終止遞歸。沿着這些線：

template <typename T, int rc> 
struct DeterminantHelper { 
    static T calculate(const Matrix<T, rc, rc>& src) { 
    T det; 
    for (int n = 1; n <= rc; n ++) 
    { 
     det = src.get(1, n) * cofactor(src, 1, n); 
    } 

    return det; 
    } 
}; 

template <typename T> 
struct DeterminantHelper<T, 2> { 
    static T calculate(const Matrix<T, 2, 2>& src) { 
    return (src.get(1, 1) * src.get(2, 2)) - (src.get(1, 2) * src.get(2, 1)); 
    } 
}; 

template<typename T, int rc> 
T determinant(const Matrix<T, rc, rc>& src) { 
    return DeterminantHelper<T, rc>::calculate(src); 
}

來源

2013-08-30 18:44:07

+1這絕對是一種方法來做到這一點（和更多的手術方法之一）。我沒有驗證代碼，但前提是正確的，無論如何。需要使用某種專業化來停止遞歸擴展。 – WhozCraig

非常感謝。我知道它必須是編譯時檢查，但我想不出如何實現它。是否有理由需要結構，並且您可以直接對函數進行專門化？ – ApproachingDarknessFish

函數模板的部分特化不存在。只有類模板可以部分專用。 –

遞歸模板函數在初始化時導致負數組大小

回答

相關問題