如何在地圖中存儲數組索引

我的程序使用boost :: unordered_map很多，而且地圖有大約4000萬個條目。這個程序不會經常插入或刪除。它只是使用密鑰隨機訪問條目。如何在地圖中存儲數組索引

我想知道如果我在一個平面數組（也許是一個std :: vector）中存儲我的輸入值（每個大約1 KB），它會提高性能（就訪問條目的速度而言），而我使用boost :: unordered_map存儲索引到這個數組的映射關係。

感謝，崔

2014-02-10 user2100910

也許吧。你會使用unordered_map_every_時間來尋找索引嗎？因爲如果是這樣的話，那會比單獨使用'unordered_map'慢。如果沒有，則使用迭代器到unordered_map而不是索引。 –

是的，這可能會嚴重加速的東西。事實上，這就是升壓flat_map是:)

使用排序的載體，而不是基於樹的關聯容器是C++世界知名的技術。馬特Austern的經典文章Why You Shouldn't Use set, and What You Should Use Instead (C++ Report 12:4, April 2000, PDF)是啓發：

...

這給你超過你要求的，因爲你甚至不需要外來指標。這爲您提供了更多的參考位置和更低的內存佔用。最重要的是，它爲您提供了更低的複雜性（ - >更少的錯誤），並在接口方面可以替代std::[unordered_]map。

來源

2014-02-10 22:15:34 sehe

有沒有boost :: flat_unordered_map？而... OP不使用樹... –

@MooingDuck沒有。 OP不想使用樹或者...... :)當然，你提出了一個有效的觀點，儘管這樣路徑會導致Boost Intrusive（也可能是'multi_index_container <..，indexed_by ，unordered_unique <...>>'） – sehe

將值存儲在像std :: vector提供的連續內存中將會增加緩存局部性。這可能會在性能上造成相當大的差異，但取決於訪問模式。

如果你的狩獵表現，記住黃金法則： 總是測量！

來源

2014-02-10 22:16:40 DaBrain

如何在地圖中存儲數組索引

回答

相關問題