c++ - std::map 中的内存分配

Question

我正在对各种 C++ 字典实现（地图、字典、向量等）进行报告。

使用 std::map 插入的结果表明性能为 O(log n)。性能也有持续的峰值。我不是 100% 确定是什么原因造成的；我认为它们是由内存分配引起的，但我未能找到任何文献/文档来证明这一点。

任何人都可以解决这个问题或指出我正确的方向吗？

干杯。

Answer 1

你是对的：它是 O(log n) 复杂度。但这是由于 map 的排序特性（通常基于二叉树）。

另请参阅http://www.sgi.com/tech/stl/UniqueSortedAssociativeContainer.html有关于插入的说明。如果您可以提示在哪里进行插入，最坏的情况是 O(log n) 和摊销 O(1)。

地图通常基于二叉树，需要平衡以保持良好的性能。您观察到的负载峰值可能与此平衡过程相对应

Answer 2

对于 STL，经验方法并不是绝对必要的。当标准明确规定诸如 std::map 插入之类的操作的最小复杂性时，进行试验是没有意义的。

我敦促您阅读该标准，以便在继续实验之前了解最低复杂性保证。当然，您碰巧测试的任何 STL 实现都可能存在错误。但是流行的 STL 是经过良好调试的生物并且使用非常广泛，所以我对此表示怀疑。

Answer 3

如果我没记错的话，std::map 是一棵平衡的红黑树。当 std::map 确定底层树需要平衡时，可能会导致一些尖峰。此外，当分配新节点时，操作系统可能会在分配部分造成一些峰值。