c++ - 谁能推荐一个 C++ std::map 替换容器？

Question

地图非常适合轻松完成任务，但它们会占用内存并且存在缓存问题。当你有一个关键循环中的地图时，这可能会很糟糕。

所以我想知道是否有人可以推荐另一个具有相同 API 但使用向量或哈希实现而不是树实现的容器。我的目标是交换容器，而不必重写所有依赖于地图的用户代码。

更新：性能方面最好的解决方案是在 std::vector 上测试地图外观

Answer 1

您可以使用 std::tr1::unordered_map，它已经存在于大多数 STL 实现中，并且是 C++0x 标准的一部分。

这是它的当前签名：

template <class Key,
          class T,
          class Hash = std::tr1::hash<Key>,
          class Pred = std::equal_to<Key>,
          class Alloc = std::allocator<std::pair<const Key, T> > >
class unordered_map;

Answer 2

也许Google SparseHash可以帮助你？

Answer 3

请参阅Loki::AssocVector和/或 hash_map（大多数 STL 实现都有这个）。

Answer 4

如果您的密钥是一种可以非常快速地比较的简单类型，并且您的条目不超过几千个，那么只需将您的配对放入 anstd::vector并迭代以找到您的值，您就可以获得更好的性能。