问llvm::DenseMap和std::map的异同

EN

llvm::DenseMap是std::unordered_map的替代品，所以它并不完全用于替换std::map (至少如果您已经根据有序属性和无序属性仔细选择了std::map)。

与std::unordered_map不同，std::map保证容器的迭代顺序与您的比较器定义的顺序相匹配(默认情况下是std::less)。在很多情况下，你不关心迭代顺序.但在少数重要的情况下，DenseMap不是一种选择。

现在，将DenseMap与std::unordered_map进行对比:与std容器不同，DenseMap将其所有数据保存在一个内存分配中，并且取消存储桶，以便将键和值保持在内存中。这两个特性对于数据局部性来说都是一个巨大的胜利，因此在几乎所有的情况下都是快速的。

此外，DenseMap默认分配大量的键/值对(实际上是64)，因此在小尺寸时，插入几乎是免费的。当然，这样做的缺点是，如果您创建了很多非常小的映射，或者您的类型本身很大，那么内存效率就很低；如果您的容器将永远增长到64个元素，那么您就是在浪费内存。根据您的用例，这可能会或不会对您造成实际伤害。

与std::unordered_map相比，最后一个不同之处可能会让一些人措手不及:每次插入后，DenseMap的迭代器都会失效(与std::map和std::unordered_map不同，后者只有当缓存重散时迭代器才失效)。我认为这主要是一个理论问题，因为您当然可以只存储密钥而不是迭代器。(与向量不同，找到保留映射迭代器的真正代码是相当罕见的。)

我已经收集了一些比较DenseMap和std容器的DenseMap，以及如果您想在自己的机器上运行基准测试的话GitHub回购。下面是四个选定的图表，显示不同尺寸的地图的插入和随机查找速度。

小地图中的插入速度

​

​

大地图中的插入速度

​

​

小地图中的随机查找

​

大型地图中的随机查找

​