我听很多人说，如果容器中期望的元素数量比较少，最好使用 std::vector 而不是 std::map即使您仅使用容器进行查找而不进行迭代。
这背后的真正原因是什么？
显然，std::map的查找性能不可能比std::vector差（尽管可能以纳秒/微秒为单位有所不同），那么它与内存有关系吗？用法？
在虚拟地址空间碎片方面，std::vector 比 std::map 更好/更差吗？
我使用的是Visual Studio 附带的STL 库（即Microsoft 的实现）。 与其他实现相比，这有什么区别吗？
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?
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?
Does std::vector fare any better/worse than std::map in fragmenting the virtual address space?
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?
发布评论
评论（7）
我假设您正在将
map与vector进行比较 >。首先，在一个非常小的向量中查找一个项目很容易比在地图中查找相同的项目更快，因为向量中的所有内存总是连续的（因此与计算机的缓存和此类事物配合得更好），并且数量在向量中查找某些内容所需的比较次数可能与在地图中查找内容所需的比较次数大致相同。 在非常大的容器的限制下，在映射中查找元素需要更少的操作。
映射比向量更快的点取决于实现、处理器、映射中的数据以及诸如处理器缓存中的内存之类的微妙因素。 通常，地图变得更快的点是大约 5-30 个元素。
另一种方法是使用哈希容器。 它们通常被命名为
hash_map或unordered_map。 名为hash_map的类不是官方标准的一部分（并且有一些变体）；std::tr1::unordered_map是。 哈希映射通常比普通映射更快，无论其中有多少元素，但它实际上是否更快取决于键是什么，它是如何哈希的，您必须处理什么值以及如何处理密钥在 std::map 中进行比较。 它不会像 std::map 一样将事物保持在特定的顺序，但你已经说过你不关心这一点。 我建议使用哈希映射，特别是当键是整数或指针时，因为这些哈希非常快。I presume you're comparing
map<A, B>withvector<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.
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.
An alternative is to use a hash container. They are often named
hash_maporunordered_map. Classes namedhash_mapare not part of the official standard (and there are a few variants out there);std::tr1::unordered_mapis. 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.“默认情况下，当您需要容器时，请使用矢量”- Bjarne Stroustrup。
否则，我发现这个小流程图非常有帮助（编辑 - 可能是一个有效的实时新链接）：
https://ngoduyhoa.blogspot.com/2015/06/summary-of- Different-containers.html
"By default, use vector when you need a container" - Bjarne Stroustrup.
Otherwise, I find this little flow chart to be of very good help (edited - probably a valid live new link):
https://ngoduyhoa.blogspot.com/2015/06/summary-of-different-containers.html
映射通常以二叉搜索树的形式实现，而遍历二叉树总是会带来一些开销（执行比较、遍历链接等）。向量基本上只是数组。 对于非常少量的数据，可能是 8 或 12 个元素，有时对数组进行线性搜索比遍历二叉搜索树更快。
您可以自己运行一些计时来查看收支平衡点在哪里——对四个元素进行计时，然后是八个，然后是十六个，依此类推，以找到 STL 的特定实现的最佳点。
映射确实往往在整个堆上有一堆小分配，而向量是连续的，因此在从前到后迭代所有元素的情况下，向量的缓存命中率有时会更好一些。
Maps are usually implemented as binary search trees, and walking a binary tree always comes with a little overhead (performing comparisons, walking links, etc.) Vectors are basically just arrays. For very small amounts of data, maybe 8 or 12 elements, sometimes it's faster just to do a linear search over an array than to walk a binary search tree.
You can run some timings yourself to see where the break-even point is -- time a search over four elements, then eight, then sixteen, and so on to find the sweet spot for your particular implementation of the STL.
Maps do tend to have a bunch of small allocations all over the heap, whereas vectors are contiguous so the cache-hit rate of vectors can sometimes be a little better in cases where you're iterating over all the elements from front to back.
如果您一次执行所有插入操作，然后进行大量查找，则可以使用向量并在插入完成后对其进行排序； 然后使用 lower_bound 进行快速查找。 即使对于大量项目，它也可能比使用地图更快。
If you're doing all your insertions at once then doing lots of lookups, you can use a vector and sort it when you're through inserting; then use lower_bound to do a quick lookup. It might be faster than using a map, even for large numbers of items.
我认为你应该首先使用适合数据的容器。 std::vector 用于在 C 或 STL 之前的 C++ 中使用数组的情况：您想要一个连续的内存块来存储具有快速恒定时间查找的值。 std::map 应用于将键映射到值。 这里的主要重叠是向量与以 size_t 作为键的映射。 在这种情况下，有两个问题：索引是否连续？ 如果没有，您可能会浪费向量的内存。 其次，你想要什么查找时间？ 向量具有恒定的查找时间，而 std::map 通常实现为 RB 树，其查找时间为 O(log n)，甚至哈希映射（例如 TR1 unordered_map）通常也具有更差的复杂度，因为索引（或其散列）将被映射到可以包含多个值的桶。
如果我们的目标是一个包含对的向量：您可以使用向量的元素并使用 find 来查找元素。 但这是二分搜索，实际上与 std::map 一样快。
不管怎样，尝试以明显的方式对数据进行建模。 过早的优化通常没有多大帮助。
I think you should use the container that fits the data first and foremost. std::vector is used in situations where you would use an array in C or pre-STL C++: you want a contiguous block of memory to store values with fast constant time look-up. std::map should be used to map keys to values. The primary overlap here is a vector vs a map with a size_t as the key. In that case there are two concerns: are the indexes continuous? If not, you will probably be wasting memory with a vector. Second, what look-up time do you want? A vector has constant time lookup, while std::map is usually implemented as a RB tree, which has a O(log n) look-up time, and even a hash map (such as TR1 unordered_map) usually has a worse complexity, because the index (or a hash thereof) will be mapped to a bucket that can contain multiple values.
If were aiming at a vector with pairs: you could the elements of the vector and use find to find elements. But this is a binary search, and will practically be as fast as a std::map.
Anyway, try to model the data in the obvious manner. Premature optimization often doesn't help much.
另一种看待这个问题的方式是，如果我们谈论的是小型容器，那么它们都不会花费很长时间来查找。 除非您在非常紧密的循环中搜索此容器，否则时间差异可能可以忽略不计。
在这种情况下，我会寻找哪个容器更符合您想要做的事情。 如果您正在寻找特定值，map 的内置 find() 方法将比创建 for 循环和迭代向量更容易（并且使用起来更简单）。
你自己的时间可能比这里那里的几纳秒更有价值。
Another way to look at this, is if we're talking about small containers, then neither one is going to take very long to look up. Unless you're searching through this container on a very tight loop, the difference in time will probably be negligible.
In that case, I would look for which container more closely matches what you want to do. If you're looking for a particular value, map's built-in find() method will be a lot easier (and less complex to use) than creating a for loop and iterating over a vector.
Your own time is probably worth a lot more than a few nano-seconds here and there.
基本上，地图用于查找。
但是，有时甚至可以使用
std::vector代替std::map进行查找。如果键值对中的元素非常少，那么即使在
std::vector> 中，您也可以使用 key 进行迭代搜索 。这是因为散列需要时间，特别是对于散列字符串和映射中的其他操作（例如在堆中存储数据）。
如果您有更多必须查找的元素，并且当您想在拥有的元素列表中进行频繁查找时，您只会在 std::map 中看到更好的差异。
Basically, maps are used for lookup.
But, sometimes
std::vectorcan be used instead ofstd::mapeven for look up.If there are going to be very less elements in your key-value pairs, then you can go for an iterative search using key even in
std::vector<std::pair<x,y>>.This is because of the fact that hashing takes time, especially for hashing strings and for other operations in map like storing data in heap.
You would only see a better difference in std::map, if you have more elements in which you have to lookup and also when you want to do frequent lookup in the list of elements that you have.