本文介绍了std :: lower_bound和std :: upper_bound的理由?的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

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的理由?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!

07-18 10:52
查看更多