C++ 中 Set STL 的下限

Question

我知道 set 在 c++ 内部是作为树结构实现的。那么，lower_bound 是如何执行的呢？我的意思是我理解向量，你使用开始和结束索引选择中间元素并执行二进制搜索，但是它如何实现树状结构？

Answer 1

在 set 中查找 lower_bound 与在集合中查找元素几乎相同。在搜索结束时（在树中导航），您要么找到了元素所在的节点，要么找到了一个大于您要查找的元素的元素，但没有任何节点具有更低的元素其子树中的值（因此，如果您要添加该值，则这是您要插入该值的位置，作为该节点的左子节点）。

无论哪种方式，您都找到了元素的下限。