優化存儲動態大小的向量的向量

我在做某些工作時遇到了這個問題模式多次，而且我想知道是否存在已知的解決方案。優化存儲動態大小的向量的向量

很簡單：我有一個元素向量，它又是一些動態大小的向量。我知道內部向量的大小會相對較小（即平均情況下大約10個項目的順序），但其中會有很多。

我天真地解決這個問題：

vector<vector<item>> vss;

在內矢量使用這種方法的內存分配將是所有的地方。迭代vss中的所有元素將會導致緩存崩潰，這可能會導致性能問題。

我在想，這可以通過在同一塊內存中使用某種具有多個頭的鏈接列表結構來解決。

假設內部向量的大小不能預先確定，是否有一種方法來構造和填充vss，使得遍歷元素不會成爲緩存災難？

謝謝。

如果你認爲這個內存分配「遍佈全球」，我可以向你保證傳統的鏈表不會更好，很可能會更糟糕。現在你已經有了一個指向動態行的指針表。如果整體池大小通常相同，你可能會放棄管理自己的分配器*，但大多數標準庫已經爲你分配，並且效率很高，所以我沒有看到那裏有巨大的勝利。 – WhozCraig

WhozCraig，我意識到使用傳統的鏈表會更糟糕。我想到的是分配一大塊內存並在該塊內保留鏈接列表** s **（並在必要時重新分配和移動）。 –

準確地說，這是我建議你可以使用自定義* allocator *並保持你的佈局，而是使用'std :: vector >'來完成那裏你的分配器從你自己管理的內存池中抽取。 *你可能不需要重新發明輪子。 – WhozCraig

我只是想添加我目前的，但希望是暫時的解決方案。而不是直接填充vss的，我使用對臨時矢量：

vector<pair<size_t, item>> temporaries;

，其表示某些項目應在特定索引被插入。從這裏我計算每個索引的條目數量，分配一塊內存來保存這些項目，並移動數據。一些額外的矢量用於簿記（即，每個索引的項目數量和它們的起始位置）。

2015-02-05 06:26:10

回答