C++什麼是對象「樁」的二維數組的最佳數據結構？

網格的大小在開始時是已知的（但每次程序啓動時都會有所不同）。然而，每個單元的深度並不僅僅是一個值，而是一個在運行時期間會不斷變化的對象羣體。C++什麼是對象「樁」的二維數組的最佳數據結構？

問：什麼是最推薦的（高效且易於維護;不易發生用戶錯誤）的方式來實現這一點？

這是一種標準的二維矢量指針數組嗎？
它是3D矢量陣列嗎？
它是一個二維數組的鏈表或二叉樹（我認爲二叉樹會增加複雜性開銷，因爲連續刪除和插入節點 - 體操）
它是一些其他的自定義數據結構嗎？

enter image description here

2013-05-20 Thomas An

也許你可以描述你的實際應用。你需要迭代這些樁，還是隻需要計算每個樁的高度？如果您有一組固定的節點，您可以將網格位置存儲在節點中並更新深度直方圖。移動節點時，只需執行兩個直方圖更新並更改網格位置。不知道這是否有用。正如我所說，取決於你想達到的目標。 – paddy

這是一個碰撞網格表。每個單元格都包含對可變數量對象的引用。所以我們每毫秒處理數以千計的搜索，刪除和添加。但是，每個單元不應該有超過5或10個對象（我們寧願使網格更精細以減少每個單元的對象數量）。 –

好吧，試着在每個單元中存儲一個向量。在大多數情況下，矢量比列表好。聽起來有點像[這個答案]（http://stackoverflow.com/a/14615449/1553090）我回了一段時間。如果你需要更快，更骯髒，你可以記憶載體。也許甚至使用矢量作爲第二手段。您可能想試驗將小型本地數組以內聯方式存儲，然後將數據溢出到某個矢量上，以便將大部分內存訪問保留在本地。在這方面，將網格屏蔽成頁面也可能有助於改善局部性。 – paddy

使用最好緩存局部性一維數組。 A vector會很好。

std::vector<int> histdata(width * height);

如果快速行需要指數，然後進行扯上點進去：

std::vector<int*> histogram(height); 
histogram[0] = &histdata[0]; 
for(int i = 1; i < height; i++) { 
    histogram[i] = histogram[i-1] + width; 
}

現在，你必須存儲在一維向量2D直方圖。你可以像這樣訪問：

histogram[row][col]++;

如果你包裝這一切在一個簡單的類，你就不太可能做一些愚蠢的用指針。您也可以使用clear()函數來將直方圖數據設置爲零（它只是穿過histdata矢量並將其零）。

來源

2013-05-20 00:51:43 paddy

每個單元格的深度不僅僅是一個值。這是一個在運行時會不斷變化的對象羣體。 –

在這種情況下，我很難將其稱爲直方圖。無論如何，沒關係。在上面的例子中，只需'typedef std :: vector Objects'並用'Objects'代替'int'。然後，每個單元格都有一個可以填充項目的矢量。 – paddy

C++什麼是對象「樁」的二維數組的最佳數據結構？

回答

相關問題