矢量矢量有什麼問題？

Question

我讀過vector -of-vector由於固定的維數而給出了錯誤，但我找不到對http://www.stackoverflow.com上的問題的明確說明。

可能有人給爲什麼在單個vector使用二維索引優選的是使用vector -OF- vector S表示固定2 ^第二尺寸的說明？

另外，我假設一個vector -OF- vector s是具有可變2 ^第二尺寸的2D陣列的優選數據結構？如果有任何相反的證據，我很樂意看到這一點。

Answer 1

我會用一個簡單的比喻來回答。

這兩件事情總的來說「更好」是什麼？

1. 電話簿，其中每個條目是指，你必須找到並閱讀發現某人的電話號碼
2. 電話簿列出人的電話號碼

保持不同的書碼您的計算機緩存中的所有數據都會更簡單，更明智，更輕鬆。一個向量與N裏面的向量是更復雜的操作（記住，這些都需要動態分配和大小管理操作！）;一個向量就是一個向量。您尚未將工作量乘以N。

唯一的缺點是模擬二維數組訪問與一維底層數據存儲，你需要寫一個門面。幸運的是，這很容易。

現在的主觀部分：總體而言，我認爲這是值得的，除非你真的真的急於和你的代碼質量並不特別重要。

Answer 2

使用矢量的矢量：由於多個塊

1. 是在存儲器分配方面效率不高，被分配。
2. 模型鋸齒狀的右手邊，所以蟲子在蠕動。

使用單一的載體，在一般情況下，內存管理更簡單。但是如果你的矩陣很大，你可能會遇到問題，因爲它可能很難獲得一個大的連續塊。

如果你的數組可調整大小，那麼我仍然堅持一個向量：調整大小的複雜性可以孤立在一個單一的功能，你可以優化。

當然，最好的解決方案是使用像Boost中提供的線性代數庫（BLAS）。這也處理大稀疏矩陣美麗。

Answer 3

對於std::vector底層數組是從堆中動態分配的。如果你有例如std::vector<std::vector<double>>，那麼你的外載體看起來像

{v1, v2, v3, v4, ... vn} 

這看起來像每個內矢量將在連續的存儲器中，並且他們會，但它們的底層陣列將是不連續的。請參閱this post中的內存佈局圖。換句話說，你不能說

&(v1.back()) + 1 == &(v2.front()) // not necessarily true! 

相反，如果你使用一個單一的載體與striding，那麼你將獲得的數據局部性，並且它註定會更加cache friendly，因爲所有的數據是連續的。

爲了完整起見，我會用這些方法既不如果你的矩陣是稀疏的，因爲有more elegant and efficient storage schemes比直一維或二維陣列。雖然既然你提到你有一個「固定的第二維」，我會認爲這不是這種情況。