c++ - 如何将数组索引存储在映射中

Question

我的程序经常使用 boost::unordered_map ，该映射有大约 4000 万个条目。该程序不经常执行插入或删除操作。它只是使用 key 随机访问条目。

我想知道如果我将条目值(每个大约 1 KB)存储在平面数组(可能是 std::vector)中，并且我使用boost::unordered_map 存储键到该数组索引的映射。

谢谢， 崔

Answer 1

是的，这可以大大加快速度。事实上，这就是 Boost flat_map 的用途:)

文档相关:Non-standard containers

Using sorted vectors instead of tree-based associative containers is a well-known technique in C++ world. Matt Austern's classic article Why You Shouldn't Use set, and What You Should Use Instead (C++ Report 12:4, April 2000, PDF) was enlightening:

...

这给了你比你要求的更多的东西，因为你甚至不需要无关的索引。这为您提供了更多的引用位置和更低的内存占用。最重要的是，它可以降低复杂性(-> 更少的错误)，并在接口(interface)方面直接替代 std::[unordered_]map。