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

Question

我知道地图是实施红黑树。

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

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

std::map<int,MyObject>

Answer 1

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

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