如何製作節省內存的網格類？

Question

大多數時候，你會作出對象的網格，C++的方式是這樣的：

class Grid { 
private: 
    GridObject[5][5]; 
}; 

但是，有沒有辦法來節省內存，而不是使用什麼都沒有在他們的瓷磚？假設你有一個棋盤。如果你不想在無人空間使用記憶怎麼辦？我正在想辦法做到這一點，但他們效率低下。

Answer 1

我想有這樣的結構：

class GridObjectWithIndex 
{ 
public: 
    size_t index; 
    GridObject obj; 
}; 

哪裏指數形式x + y * GRIDSIZE的值，以便您可以輕鬆地將x和它y解碼。

而在你Grid類有：

class Grid 
{ 
    std::vector<GridObjectWithIndex> grid_elements; 
}; 

Answer 2

這在我腦海的第一件事就是存儲指針GridObject *在網格中。它仍然會爲不存在的元素消耗sizeof（GridObject *）字節，但它可以讓您免受管理數據結構的噩夢。如果它不是絕對的關鍵 - 不要讓它比需要更復雜。這絕對不值得下棋（8x8）。

如果在廣泛的指數範圍內有少量元素，fritzone的解決方案將會很好。不過考慮讀寫性能。

如果要在通過網絡發送或保存文件時節省空間，您可能需要考慮歸檔算法。 Althogh只對大數據集有意義。

Answer 3

你所呼籲被稱爲稀疏數據結構中，最突出的例子是稀疏矩陣。

這個想法是交換CPU的內存：以更多操作爲代價使用更少的內存。通常這意味着：僅具有表示「不尋常」的值（與由座標快速接入）

保持「通常」的值一邊

作爲概念證明的結構

• ，您可以使用std::map< std::pair<size_t, size_t>, Object >作爲稀疏結構，並且只要中不存在Object即可。