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

问题描述

我听说很多人说，如果容器中预期的元素数量相对较小，最好使用 std :: vector 而不是 std :: map eventhough我使用容器只进行查找而不是迭代。

I've heard many people saying that if the number of elements expected in the container is relatively small it is better to use std::vector instead of std::map eventhough I use the container for only lookup and not for iterating.

这是什么真正的原因？

What is the real reason behind this?

显然，map的查找性能不能比向量的查找性能更好（尽管它可能是以纳秒/微秒为单位），因此它与内存有关使用？

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

向量在虚拟地址空间碎片化中比地图更好/更差吗？

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

使用与Visual Studio（即微软实现）一起使用的STL库与其他实现有什么区别？

I am using STL library that comes along with Visual Studio (i.e. microsoft implementation) does that make any difference from other implementations?

推荐答案

假设您正在比较地图< A，B> 与向量< 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屋！