vector或地图，哪一个使用？
我听到很多人说，如果在容器中预期的元素数量相对较less，最好使用std::vector而不是std::map eventhough我只使用容器来查找而不是迭代。
这背后的真正原因是什么？
显然，map的查找性能不会比vector小（尽pipe可能是纳秒/微秒），这与内存使用情况有关系吗？
在虚拟地址空间的碎片化过程中，vector比地图更好还是更差？
我正在使用与Visual Studio（即微软实施）一起的STL库这是否与其他实现有什么不同？
我假定你正在比较map<A, B>与vector<pair<A, B> > 。
首先，在一个非常小的vector中find一个项目可能比地图中的同一个东西容易得多，因为vector中的所有内存都是连续的（所以和计算机的caching以及类似的东西玩的更好），数量需要在vector中find某种东西的比较可能与地图大致相同。 在地图中查找元素需要在非常大的容器范围内进行更less的操作。
地图变得比vector更快的点取决于实现，处理器，地图中的数据以及处理器caching中的内存等微妙的东西。 通常情况下，地图变得更快的点大概是5-30个元素。
另一种方法是使用散列容器。 它们通常被命名为hash_map或unordered_map 。 名为hash_map类不是官方标准的一部分（并且有几个变种）; std::tr1::unordered_map是。 哈希映射通常比查找的普通映射更快，而不pipe其中包含多less个元素，但实际上是否更快取决于关键是什么，如何进行散列，需要处理什么值以及如何处理密钥在std :: map中进行比较。 它不会像std :: map那样按照特定的顺序来保存东西，但是你已经说过你不关心这个。 我build议散列映射，特别是如果键是整数或指针，因为这些散列非常快。
地图通常以二叉search树的forms实现，而漫步二叉树总会带来一点开销（执行比较，走路链接等）。vector基本上只是数组。 对于非常less量的数据，可能是8或12个元素，有时对数组进行线性search比对二叉search树进行search要快。
你可以自己运行一些时间表，看看盈亏平衡点在哪里 – search四个元素，然后search八个，然后十六个，等等，为您的特定STL实现find最佳位置。
地图确实倾向于在整个堆中有一堆小的分配，而向量是连续的，所以在从前到后遍历所有元素的情况下，向量的caching命中率有时会更好一些。
“默认情况下，当你需要一个容器时使用向量” – Bjarne Stroustrup。
否则，我觉得这个小stream程图非常有帮助：
如果你一次做了所有的插入，然后做了很多的查找，你可以使用一个vector，并在插入时进行sorting; 然后使用lower_bound快速查找。 这可能比使用地图更快，即使是大量的项目。
我认为你应该首先使用适合数据的容器。 std :: vector用于在C或pre-STL C ++中使用数组的情况：需要连续的内存块以快速恒定时间查找来存储值。 应该使用std :: map将键映射到值。 这里的主要重叠是一个vector与一个size_t作为键的映射。 在这种情况下，有两个问题：索引是否连续？ 如果没有，你可能会浪费记忆与载体。 其次，你想要什么查找时间？ 一个向量具有恒定的时间查询，而std :: map通常被实现为一个RB树，它具有O（log n）查找时间，甚至一个哈希映射（比如TR1 unordered_map）通常具有更差的复杂度，因为索引（或其散列）将被映射到可以包含多个值的存储桶。
如果瞄准一个有成对的vector：你可以find这个vector的元素并使用find来find元素。 但是这是一个二进制search，几乎和std :: map一样快。
无论如何，尝试以明显的方式对数据进行build模。 过早优化往往没有多大帮助。
另一种看待这个问题的方法是，如果我们谈论的是小容器，那么没有人会花很长时间来查找。 除非你在一个非常紧密的循环中search这个容器，否则时间上的差别可能是微不足道的。
在这种情况下，我会寻找哪个容器更符合你想要做的。 如果你正在寻找一个特定的值，map的内buildfind（）方法比创build一个for循环和遍历一个vector要容易得多（而且使用起来也不那么复杂）。
你的时间可能比这里和那里的几个纳秒更有价值。
基本上，地图用于查找。
但是，有时std::vector也可以用来代替std::map甚至查找。
如果键值对中的元素less得多，那么即使在std::vector<std::pair<x,y>>也可以使用键进行迭代search。
这是因为散列花费时间，特别是对于散列string和其他像在堆中存储数据那样的映射操作。
如果你有更多的元素需要查找，并且当你想要在你有的元素列表中进行频繁的查找，你只会在std :: map中看到更好的区别。
