llvm :: DenseMap和std :: map之间的差异/相似之处

Question

最近我遇到了在llvm中广泛使用的DenseMap数据结构.我认为它是某种优化版本std::map(?).谁能帮我理解它们之间的区别或相似之处？

Answer 1

llvm::DenseMap是 的替代品std::unordered_map，因此它并不完全是要替代的std::map（至少如果您根据有序与无序属性仔细选择的话不会）。

与 不同std::unordered_map，std::map保证容器的迭代顺序与比较器定义的顺序相匹配（默认情况下为std::less）。在许多情况下，您并不关心迭代顺序……但在少数重要的情况下，这DenseMap不是一种选择。

现在，对比DenseMap一下std::unordered_map：与std容器不同DenseMap，它将所有数据保存在一个内存分配中，并且它取消了存储桶，而是将键和值彼此相邻地保存在内存中。这两个功能都是数据局部性的一大胜利，因此几乎在所有情况下都可以提高速度。

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

与 相比的最后一个区别std::unordered_map可能会让一些人措手不及： aDenseMap的迭代器在每次插入后都会失效（与std::map和不同std::unordered_map，只有在缓存重新散列发生时迭代器才会失效）。这在我看来主要是一个理论问题，因为您当然可以只存储键而不是迭代器。（与向量不同，找到保留映射迭代器的真实代码是相当罕见的。）

如果您想在自己的机器上运行基准测试，我已经汇总了一些与容器相比的基准测试，以及一个 GitHub 存储库。下面是四个选定的图表，显示了各种尺寸地图的插入和随机查找速度。DenseMapstd

小地图中的插入速度

大地图中的插入速度

在小地图中随机查找

大地图中的随机查找