C++ 映射 lower_bound/upper_bound

Question

我了解到 C++ 中 map 的底层数据结构是一个自平衡的二叉搜索树。由于在这些数据结构中，查找键的下限和上限有很多用处，您会认为 map lower_bound 和 upper_bound 函数将为您提供这种能力。令人遗憾的是，这些功能无法实现。有谁知道为什么 lower_bound 的行为方式是这样的？ (它为您提供了不在给定 key 之前的 key )。

Answer 1

自从 SGI 甚至引入 STL 之前我就一直在使用 C++，并且出于某种原因仍然设法搞砸了使用这些方法，甚至在将它们呈现给类时让自己感到尴尬。我认为我的问题是:

1. 这些名字在数学上已经具有直观但不同的含义。鉴于数学含义，在大集合或 map 中似乎很奇怪，upper_bound和 lower_bound实际上是相同或相邻的元素。

2. 名称“upper_bound”和“lower_bound”听起来好像两者之间存在某种对称性，但实际上并非如此。如果名称类似于 least_ge，我会轻松得多(至少大于或等于)lower_bound 和 least_gt (最小大于)upper_bound。

如果有人有助记符或逻辑可以使这些易于内化，请分享。否则，感觉就像他们写了两个有用的函数，但使用了两个随机的数学术语来命名这些函数，无法从名称中推导出语义。到那时，为什么不使用像egptr这样的虚构名称呢？和 pbase ？我的意思是至少我没有任何预先存在的直觉来克服关于 streambuf 的名字。方法...

无论如何，我认为这是您必须记住的基本规则:

• lower_bound(X)返回最低元素 v这样 v >= X

• upper_bound(X)返回最低元素 v这样 v > X

• 要遍历半开区间 [L,H)，从 lower_bound(L) 开始并停止(不处理)lower_bound(H) . 这通常是您想要的，因为在 C++ 中遍历半开区间是最常见的——例如，[ buf , buf+nbytes ), 或 [ 0 , array_size ), 或 [ begin() , end() ).

• 要遍历闭区间 [L,H]，从 lower_bound(L) 开始并停在 upper_bound(H) .

• 要遍历开区间 (L,H)，从 upper_bound(L) 开始并停在 lower_bound(H) .

• 在非空容器中，lower_bound(X) 的镜像是std::prev(upper_bound(X))和upper_bound(X)的镜像是std::prev(lower_bound(X)) .当然，如果一个元素等于begin() , 那么你不能用 std::prev 向后退一步，所以你需要额外的逻辑来处理这个点不能用迭代器值表示的事实。

• 在多重集/多重映射中，第一个 v是lower_bound(v)如果该元素确实是 v .最后v是std::prev(upper_bound(v))如果容器不为空且该元素为 v ，但记得在尝试之前检查容器是否为空 prev在 end() .