std :: lower_bound和std :: upper_bound的理由？ [英] rationale for std::lower_bound and std::upper_bound?

问题描述

STL提供二进制搜索函数std :: lower_bound和std :: upper_bound，
，但我不会使用它们，因为我不能记住他们做什么，
因为他们的合同似乎完全

只要看看名字，
我猜想lower_bound可能是last lower bound的缩写，

即排序列表中的最后一个元素是<=给定的val（如果有）。

同样，我猜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的理由？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！