c++ - vector 或 map ，使用哪一个？

Question

我听很多人说，如果容器中预期元素的数量比较少，最好使用std::vector而不是std::map 即使您将容器仅用于查找而不是迭代。

这背后的真正原因是什么？

显然 std::map 的查找性能不能比 std::vector 差(尽管它可能以纳秒/微秒为单位不同)所以它有什么需要与内存使用有关吗？

std::vector 在分割虚拟地址空间方面是否比 std::map 更好/更差？

我正在使用 Visual Studio 附带的 STL 库(即 Microsoft 的实现)。与其他实现相比，这有什么不同吗？

Answer 1

我猜你是在比较 map<A, B>与 vector<pair<A, B> > .

首先，在一个非常小的 vector 中找到一个项目很容易比在 map 中找到相同的项目更快，因为 vector 中的所有内存始终是连续的(因此可以更好地与计算机的缓存和类似的东西一起使用)，并且在 vector 中查找某些内容所需的比较次数可能与在 map 中的相同。在非常大的容器的限制下，在 map 中查找元素需要较少的操作。

map 比 vector 快的点取决于实现、处理器、map 中的数据以及处理器缓存中的内存等微妙因素。通常， map 变得更快的点大约是 5-30 个元素。

另一种方法是使用散列容器。它们通常被命名为 hash_map或 unordered_map .名为 hash_map 的类不是官方标准的一部分(并且有一些变体)； std::tr1::unordered_map是。 HashMap 通常比普通映射更快，无论其中有多少元素，但它是否真的更快取决于键是什么，它是如何散列的，你必须处理什么值，以及如何 key 在 std::map 中进行比较。它不会像 std::map 那样将事物保持在特定的顺序中，但是您已经说过您不在乎这一点。我推荐 HashMap ，特别是如果键是整数或指针，因为这些哈希非常快。