问题描述
STL提供二进制搜索函数std :: lower_bound和std :: upper_bound,
,但我不会使用它们,因为我不能记住他们做什么,
因为他们的合同似乎完全
只要看看名字,
我猜想lower_bound可能是last lower bound的缩写,
即排序列表中的最后一个元素是
同样,我猜upper_bound可能是first upper bound ,
即排序列表中的第一个元素,即> =给定的val(如果有)。
但文档说一些与之不同的东西 -
似乎是向后和随机的混合物,对我来说。
解释文档:
- lower_bound查找> = val的第一个元素
- upper_bound找到> val
所以lower_bound没有找到一个下界;它找到第一个上边界!
和upper_bound找到第一个上限。
这是否有意义?
如果您在范围内有多个元素[]
第一个,最后),其值等于您正在搜索的值 val 范围[ l , u )其中l = std :: lower_bound(first,last,val)
u = std :: upper_bound(first,last,val)
正好是 val 范围内的元素范围[ code>, last )。因此 l 和 u 是相等范围的下限和上限。
(请注意 std :: equal_range 将在一次调用中返回一个对的下限和上限。)
STL provides binary search functions std::lower_bound and std::upper_bound,but I tend not to use them because I've been unable to remember what they do,because their contracts seem completely mystifying to me.
Just from looking at the names,I'd guess that "lower_bound" might be short for "last lower bound",
i.e. the last element in the sorted list that is <= the given val (if any).
And similarly I'd guess "upper_bound" might be short for "first upper bound",
i.e. the first element in the sorted list that is >= the given val (if any).
But the documentation says they do something rather different from that--something that seems to be a mixture of backwards and random, to me.To paraphrase the doc:
- lower_bound finds the first element that's >= val
- upper_bound finds the first element that's > val
So lower_bound doesn't find a lower bound at all; it finds the first upper bound!?And upper_bound finds the first strict upper bound.
Does this make any sense??How do you remember it?
If you have multiple elements in the range [first, last) whose value equals the value val you are searching for, then the range [l, u) where
l = std::lower_bound(first, last, val) u = std::upper_bound(first, last, val)
is precisely the range of elements equal to val within the range [first, last). So l and u are the "lower bound" and "upper bound" for the equal range. It makes sense if you're accustomed to thinking in terms of half-open intervals.
(Note that std::equal_range will return both the lower and upper bound in a pair, in a single call.)
这篇关于std :: lower_bound和std :: upper_bound的理由?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!