映射比稀疏向量更好嗎？

我有2個對象：映射比稀疏向量更好嗎？

vector<string> v(999999); 
map<int, string> m;

我需要存儲一些指數串對，雖然它是非常稀疏（說只有20對）。我想知道是否載體需要更多的內存比地圖？如果是這樣，矢量佔用多少內存？爲什麼在這種情況下使用矢量不好？

來源

2013-01-16 Stan

這不是一個稀疏矢量 –

是的，在實踐中該向量至少需要999999 * (sizeof(string) + C) + sizeof(vector)字節（其中C是由string自動執行的任何動態分配）。該map將有開銷，但它絕對不會是附近的999999

來源

2013-01-16 00:44:47

是的，v（999999）是非常不稀疏的，無論矢量的類型如何... – Eugene

您可能無法訪問該地圖的鍵元素依賴於它的元素實現。 –

@Peter Wooster如果這是一個需求，可以保持一個單獨的矢量與地圖迭代器按正確的順序。 – Eugene

我想你可以使用矢量如果查找時間絕對關鍵，訂單的任何地方，因爲它是在不斷載體，有效指針算術因爲你已經知道了索引，但是隨着地圖上的大小（O（log n））增長。儘管這種折衷的情況確實存在，但情況確實很糟糕。

來源

2013-01-16 00:53:32 Eugene

對於大約20個元素，創建具有10^6個元素的矢量沒有意義。地圖的使用將具有更好的內存佔用，甚至可能比矢量更快。你也可以考慮一個混合方法，使用std::pair<int,std::string>的矢量來保存鍵/值對，並對矢量進行線性搜索（20個元素是，很少有，可以將成本視爲常數，而且可能更簡單的算法補償額外的操作次數）。

來源

2013-01-16 05:10:20

映射比稀疏向量更好嗎？

回答

相關問題