用C++實現二維數組的最省時的方法？

Question

在C++中實現二維數組的最省時的方法是什麼？我很關心：插入，刪除和查找。

我看了一下這兩種方法：

1. vector<vector<int>> - 嵌套向量
2. vector<vector<int>*> - 矢量與指向其他載體

我發現的第一個選項是很容易實現，但是還有另一種更省時的方法嗎？

Answer 1

我的建議：

1. 創建一個類，Matrix。
2. 仔細定義接口，以便不公開內部數據結構詳細信息。
3. 從使用捕獲數據的方法之一開始。我建議從std::vector開始 - 一個1D數組。
4. 如果遇到任何性能或維護問題，請更改內部數據以使用其他策略。

Answer 2

以初始化矩陣大小MxN，所有你需要做的是：

std::vector<std::vector<dataType>> MyMat = std::vector<std::vector<dataType>>(M,std::vector<dataType>(N,0)); 

然而，我不得不提，這就是創建一個矩陣可怕的方式。通過這種方式編寫矩陣可以使性能下降。這是因爲當您執行矩陣乘法時，您的處理器使用稱爲vectorization的東西在一條指令中將多個數字相乘，並且在執行此操作時使處理器變得更加困難。此外，這將殺死緩存局部性，因爲不同的行（或列）不會在內存中連續存在，從而使所有內容都可能放慢幾百倍。

如果您有興趣，請考慮閱讀this和this。

做到這一點，正確的方法是用矢量創建一個類（大概）：

std::vector<dataType> MyMat(M*N,0); 

然後創建將由元素訪問元素的訪問：

dataType& getElement(int i, int j) 
{ 
    return MyMat[M*i+j]; 
} 

這樣你獲得最佳表現。當然，還有更多關於性能的細節，但這足以回答你的問題。

順便說一下，你不應該自己做矩陣操作。在最好的情況下，如果你是一個專業的高性能開發者，你應該使用一些LAPACK實現爲你做矩陣操作（就像Armadillo那樣的人）。