< algorithm>函数，用于查找最后一个项小于或等于，如lower_bound [英] <algorithm> function for finding last item less-than-or-equal to, like lower_bound

问题描述

有一个函数使用二进制搜索，如 lower_bound 但返回最后项 less-than-or-

Is there a function in that uses binary search, like lower_bound but that returns the last item less-than-or-equal-to according to a given predicate?

lower_bound 定义为

查找元素在有序范围中的位置，其值小于或等于 em>指定值，其中排序标准可以由二元谓词指定。

Finds the position of the first element in an ordered range that has a value less than or equivalent to a specified value, where the ordering criterion may be specified by a binary predicate.

和 upper_bound ：

查找有序区域中元素的位置

Finds the position of the first element in an ordered range that has a value that is greater than a specified value, where the ordering criterion may be specified by a binary predicate.

>具体来说，我有一个时间有序事件的容器，在给定的时间，我想找到之前或之前的最后一个项目。我可以通过上下限，反向迭代器和使用 std :: greater 或 std :: greater_equal ？

Specifically, I have a container of time ordered events and for a given time I want to find the last item that came before or at that point. Can I achieve this with some combination of upper/lower bound, reverse iterators and using std::greater or std::greater_equal ?

编辑：
如果你在数组开始之前要求一个点，需要对user763305的建议进行调整：

A tweak was needed to user763305's suggestion to cope with if you ask for a point before the start of the array:

iterator it=upper_bound(begin(), end(), val, LessThanFunction());
if (it!=begin()) {
  it--; // not at end of array so rewind to previous item
} else {
  it=end(); // no items before this point, so return end()
}
return it;

推荐答案

大于 x 的 x 是第一个元素之前的元素。

In a sorted container, the last element that is less than or equivalent to x, is the element before the first element that is greater than x.

因此，您可以调用 std :: upper_bound ，并将返回的迭代器减少一次。
（递减之前，你必须确定它不是begin迭代器;如果是，那么没有小于或等价于 x 。）

Thus you can call std::upper_bound, and decrement the returned iterator once. (Before decrementing, you must of course check that it is not the begin iterator; if it is, then there are no elements that are less than or equivalent to x.)

这篇关于< algorithm>函数，用于查找最后一个项小于或等于，如lower_bound的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！