几个元素的map vs unordered_map

Question

我试图之间作出选择map,并unordered_map为下面的用例:

关键map是指针.最常见的用例是地图中将有一个元素.通常,地图中的最大元素数小于10.地图经常被访问,速度是最重要的因素.对地图的更改很少发生.

虽然测量速度显然是正确的方法,但这个代码将在几个平台上使用,所以我试图创建一个通用的经验法则,用于在a map和unordered_map基于元素的数量之间进行选择.我在这里看到一些帖子暗示std :: map对于少数元素可能更快,但没有给出"小"的定义.

是否有一个经验法则可以选择a map和unordered_map基于元素的数量？另一种数据结构(如通过线性搜索vector)更好吗？

Answer 1

在你总是需要测量以便找出在性能方面更合适的前提下,如果所有这些都是真的:

1. 地图的变化不常见;
2. 地图最多包含10个元素;
3. 查找会很频繁;
4. 你非常关心表现;

然后我会说你最好把你的元素放在一个std::vector并对所有元素执行一个简单的迭代,找到你正在寻找的元素.

一个std::vector将在连续的内存区域中分配它的元素,因此缓存局部性可能会为您提供更高的性能 - 在缓存未命中之后从主内存获取缓存行所需的时间至少比时间高一个数量级需要访问CPU缓存.

非常有趣的是,Boostflat_map似乎非常适合您的用例(由Praetorian提供):

flat_map类似于std::map它,但它实现像有序矢量.(来自在线文档)

因此,如果您使用Boost是一个选项,您可能想尝试这个.