c++ stl map.find() 使用什么算法？

Question

我知道地图是实现了红黑树。

所以我认为map.find()是实现了二分搜索算法

确定吗？我用这样的地图：

std::map<int,MyObject>

Answer 1

库标准没有指定任何特定的实现，只是对行为和性能特征的要求。特别是，find()必须花费对数时间，这在实践中需要像二进制搜索这样的东西。

红黑树或其他平衡搜索树是一种常见的实现方式。