矢量或地图,哪一个使用？

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

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

显然,map的查找性能不会比矢量的查找性能差(尽管可能是纳秒/微秒),那么它与内存使用情况有关吗？

在虚拟地址空间的分段中,矢量是否比映射更好/更差？

我正在使用随Visual Studio一起提供的STL库(即微软实现)与其他实现有什么不同？

1> Doug..：

---

我认为你正在map与之比较vector >.

首先,在一个非常小的向量中找到一个项目可能比在地图中的相同内容更快,因为向量中的所有内存总是连续的(因此与计算机的缓存和此类事物的关系更好)和数字在向量中找到某些东西所需的比较可能与地图大致相同.在非常大的容器的限制中,在地图中查找元素需要的操作更少.

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

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

---

@wmac:右:将Java的"HashMap"与C++"hash_map"或"unordered_map"以及Java的"SortedMap"与C++"map"进行比较更为准确.

---

当我进行基准测试时,我发现std :: map out std :: vector大约为8000,但在某些硬件上低至1000,我使用的代码可以在以下网址找到:https://github.com /BlackToppStudios/DAGFrameScheduler/blob/8bfaa295b76f8e58dd4fc21186e1c7f3dd3e323a/tests/dagsizestests.h

2> Crashworks..：

---

地图通常被实现为二叉搜索树,并且行走二叉树总是带来一点开销(执行比较,步行链接等).矢量基本上只是数组.对于非常少量的数据,可能是8或12个元素,有时在数组上进行线性搜索比在二进制搜索树中进行线性搜索更快.

您可以自己运行一些计时以查看盈亏平衡点的位置 - 搜索四个元素,然后搜索八个元素,然后搜索十六个元素,依此类推,找到特定STL实现的最佳位置.

映射确实往往在堆上有一堆小的分配,而向量是连续的,因此在从前到后迭代所有元素的情况下,向量的缓存命中率有时会更好一些.

---

您甚至不必进行线性搜索.std :: lower_bound为您提供任何已排序容器的二进制搜索.当有很多键插入时,Map很有用,改变了搜索树的结构.如果它是一个相当静态的集合,那么有序向量和lower_bound将轻松地匹配性能中的map而不仅仅是几个元素.当然还是值得在实践中进行比较!

3> Stefan Rådst..：

---

"默认情况下,在需要容器时使用矢量" - Bjarne Stroustrup.

否则,我发现这个小流程图非常有用:

http://homepages.e3.net.nz/~djm/cppcontainers.html

---

根据Herb Sutter(http://www.gotw.ca/gotw/054.htm),在deque和vector之间做出选择,通常最好选择deque.

---

deque很好,因为它几乎和矢量一样快,但因为deque的块是独立分配的,所以不需要为了增长而移动所有东西.