std::map 中的内存分配
我正在做一份关于各种 C++ 字典实现（地图、字典、向量等）的报告。
使用 std::map 插入的结果表明性能为 O(log n)。 性能也有持续的峰值。 我不能 100% 确定是什么原因造成的； 我认为它们是由内存分配引起的，但我未能成功找到任何文献/文档来证明这一点。
任何人都可以澄清这个问题或指出我正确的方向吗？
干杯。
I am doing a report on the various C++ dictionary implementations (map, dictionary, vectors etc).
The results for insertions using a std::map illustrate that that the performance is O(log n). There are also consistent spikes in the performance. I am not 100% sure what's causing this; I think they are caused by memory allocation but I have been unsuccessful in finding any literature / documentation to prove this.
Can anyone clear this matter up or point me in the right direction?
Cheers.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
你是对的：它的复杂度是 O(log n)。 但这是由于映射的排序性质（通常基于二叉树）。
另请参阅http://www.sgi.com/tech/stl/UniqueSortedAssociativeContainer.html< /a> 有一个关于插入的注释。 如果您可以提示在哪里进行插入，最坏的情况是 O(log n) 和摊销 O(1)。
映射通常基于二叉树，需要平衡以保持良好的性能。 您观察到的负载峰值可能与此平衡过程相对应
You are right: it is O(log n) complexity. But this is due to the sorted nature of map (normally binary tree based).
Also see http://www.sgi.com/tech/stl/UniqueSortedAssociativeContainer.html there is a note on insert. It’s worst case is O(log n) and amortized O(1) if you can hint where to do the insert.
Maps are normally based on binary trees and need to be balanced to keep good performance. The load spikes you are observing probably correspond to this balancing process
当涉及到 STL 时，经验方法并不是绝对必要的。 当标准明确规定了 std::map 插入等操作的最低复杂度时，进行实验是没有意义的。
我强烈建议您阅读该标准，以便在继续实验之前了解最低复杂性保证。 当然，无论您正在测试什么 STL 实现，都可能存在错误； 但是流行的 STL 是经过良好调试的并且使用非常广泛，所以我对此表示怀疑。
The empirical approach isn't strictly necessary when it comes to STL. There's no point in experimenting when the standard clearly dictates the minimal complexity of operations such as std::map insertion.
I urge you to read the standard so you're aware of the minimal complexity guarantees before continuing with experiments. Of course, there might be bugs in whatever STL implementation you happen to be testing; but the popular STLs are pretty well-debugged creatures and very widely used, so I'd doubt it.
如果我没记错的话，std::map 是一个平衡的红黑树。 当 std::map 确定底层树需要平衡时，可能会导致一些峰值。 此外，当分配新节点时，操作系统可能会在分配部分期间造成一些峰值。
If I remember correctly, std::map is a balanced red-black tree. Some of the spikes could be caused when the std::map determines that the underlying tree needs balancing. Also, when a new node is allocated, the OS could contribute to some spikes during the allocation portion.