我听到很多人说，如果容器中预期的元素数量相对较少，最好使用std::vector而不是std::map，尽管我仅将容器用于查找而不用于迭代。矢量或地图，哪一个使用？
这背后的真正原因是什么？
很明显，map的查找性能不会比矢量的查找性能差（尽管可能是纳秒/微秒），它与内存使用情况有关吗？
在虚拟地址空间的分片中，向量的性能是否比map更好/更差？
我正在使用与Visual Studio（即微软实现）一起提供的STL库吗？它与其他实现有什么不同？
我推测你正在比较map<A, B>和vector<pair<A, B> >。
首先，在一个非常小的矢量中找到一个项目可能比在地图中同样的东西更快，因为矢量中的所有内存都是连续的（因此可以更好地播放计算机的缓存等等） ，并且在向量中查找某些内容所需的比较次数可能与地图大致相同。在地图中查找元素需要在非常大的容器范围内执行更少的操作。
映射变得比矢量更快的点取决于实现，处理器上，映射中的数据以及处理器缓存中的内存等细微内容。通常情况下，地图变得更快的点大概是5-30个元素。
另一种方法是使用散列容器。他们通常被命名为hash_map或unordered_map。名为hash_map的类不是官方标准的一部分（并且在那里有一些变体）; std::tr1::unordered_map是。哈希映射通常比查找的普通映射更快，无论它有多少个元素，但它是否更快取决于关键是什么，它如何被散列，你必须处理什么值以及如何处理密钥在std :: map中进行比较。它不会像std :: map那样按照特定的顺序来保存东西，但是你说过你并不关心它。如果键是整数或指针，我会推荐哈希映射，因为这些哈希映射非常快。
地图通常以二叉搜索树的形式实现，而漫步二叉树总会带来一点开销（执行比较，走路链接等）。矢量基本上只是数组。对于非常少量的数据，可能是8或12个元素，有时候对数组进行线性搜索比对二叉搜索树进行搜索要快。
您可以自己运行一些计时以查看盈亏平衡点的位置 - 搜索四个元素，然后搜索八个，然后十六个等等，为您的特定STL实现找到最佳位置。
地图确实倾向于在整个堆中有一堆小的分配，而向量是连续的，因此在迭代所有来自前面的元素的情况下，向量的缓存命中率有时会更好一些回来。
你甚至不需要做线性搜索。 std :: lower_bound在任何已排序的容器上为您提供二分搜索。当有很多密钥插入，改变搜索树的结构时，Map很有用。如果它是一个相当静态的集合，那么排序后的向量和lower_bound将很容易地匹配地图的性能，而不仅仅是几个元素。当然在实践中还是值得比较的！ – Zoomulator 2012-11-07 12:14:05
如果您一次完成所有插入操作，然后进行大量查找，则可以在插入时使用矢量并对其进行排序;然后使用lower_bound快速查找。它可能比使用地图更快，即使是大量的项目。
我想你应该首先使用适合数据的容器。 std :: vector用于在C或pre-STL C++中使用数组的情况：您希望连续的内存块以快速恒定时间查找来存储值。应该使用std :: map将键映射到值。这里的主要重叠是一个矢量与以size_t为关键字的映射。在这种情况下，有两个问题：索引是否连续？如果没有，你可能会用矢量来浪费记忆。其次，你想要什么查找时间？一个向量具有恒定的时间查询，而std :: map通常被实现为一个RB树，它具有O（log n）查找时间，甚至一个哈希映射（例如TR1 unordered_map）通常具有更差的复杂度，因为索引（或其散列）将映射到可以包含多个值的存储区。
如果是针对带有成对的矢量：可以使用矢量的元素并使用find来查找元素。但这是一个二分搜索，实际上和std :: map一样快。
无论如何，尝试以明显的方式对数据建模。过早优化往往没有多大帮助。
“默认情况下，在需要容器时使用向量” - Bjarne Stroustrup。
否则，我觉得这一点流程图是很好的帮助：
另一种方式来看待这个，如果是我们谈论的小容器，那么没有人会需要很长时间才能查找。除非你在非常紧密的循环中搜索这个容器，否则时间上的差异可能可以忽略不计。
在这种情况下，我会寻找哪个容器更符合你想要做的。如果你正在寻找一个特定的值，map的内建find（）方法比创建一个for循环和迭代一个vector更容易（而且使用起来更简单）。
你的时间可能比几个纳秒更有价值。
基本上，地图用于查找。
但是，有时可以使用std::vector而不是std::map甚至查找。
如果键值对中的元素数量非常少，那么即使在std::vector<std::pair<x,y>>中，也可以使用键进行迭代搜索。
这是因为散列需要时间，尤其是对于散列字符串和其他像map中的数据操作等操作。
如果你有更多的元素需要查找，并且你想在你有的元素列表中进行频繁的查找，你只会在std :: map中看到更好的区别。
奇怪的是我发现Java的HashMap比C++ Map快得多。您帖子的最后一段可能描述了原因。 – wmac 2013-05-26 03:44:41
@wmac：对：将Java的`HashMap`与C++`hash_map`或`unordered_map`以及Java的`SortedMap`与C++`map`进行比较会更准确。 – 2015-12-02 23:05:14
当我进行基准测试时，我发现std :: map out的std :: map大约在8000左右，但在某些硬件上低至1000，我使用的代码可在https：// github上获得。 com/BlackToppStudios/DAGFrameScheduler/blob/8bfaa295b76f8e58dd4fc21186e1c7f3dd3e323a/tests/dagsizestests.h – Sqeaky 2015-12-24 17:46:45