矢量或地图，使用哪一个? [英] vector or map, which one to use?

问题描述

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

I've heard many people say that if the number of expected elements in the container is relatively small, it is better to use std::vector instead of std::map even if you were to use the container for lookups only and not iterating.

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

What is the real reason behind this?

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

Obviously the lookup performance of std::map cannot be worse than std::vector (although it may differ in nanoseconds/microseconds) so does it have something to do with memory usage?

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

Does std::vector fare any better/worse than std::map in fragmenting the virtual address space?

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

I am using the STL library that comes along with Visual Studio (i.e. Microsoft's implementation). Does that make any difference compared to other implementations?

推荐答案

我猜你在比较 map 和 vector>.

I presume you're comparing map<A, B> with vector<pair<A, B> >.

首先，在一个非常小的向量中查找一个项目很容易比在地图中查找相同的东西要快，因为一个向量中的所有内存总是连续的(因此与计算机的缓存和诸如此类的东西一起玩得更好)，并且在向量中查找某些内容所需的比较次数可能与地图大致相同.在非常大的容器的限制下，在地图中查找元素需要较少的操作.

Firstly, finding an item in a very small vector can easily be faster than the same thing in a map, because all the memory in a vector is always contiguous (and so plays more nicely with computers' caches and such things), and the number of comparisons needed to find something in a vector might be about the same as for a map. Finding an element in a map needs fewer operations in the limit of very large containers.

映射变得比向量更快的点取决于实现、处理器、映射中的数据以及处理器缓存中的内存等细微的事情.通常，地图变得更快的点大约是 5-30 个元素.

The point where maps become faster than vectors depends on the implementation, on your processor, what data is in the map, and subtle things like what memory is in the processor's cache. Typically, the point where map becomes faster would be about 5-30 elements.

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

An alternative is to use a hash container. They are often named hash_map or unordered_map. Classes named hash_map are not part of the official standard (and there are a few variants out there); std::tr1::unordered_map is. A hash map is often faster than a normal map for lookups, regardless of how many elements are in it, but whether it is actually faster depends on what the key is, how it is hashed, what values you have to deal with, and how the key is compared in std::map. It doesn't keep things in a specific order like std::map, but you've said that you don't care about that. I'd recommend hash maps particularly if the keys are integers or pointers, because these hash very quickly.

这篇关于矢量或地图，使用哪一个?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！