<algorithm>函数用于查找小于或等于的最后一项,如lower_bound

Question

有没有在使用二进制搜索,像函数lower_bound,但返回的最后一个项目低于或相等,以根据给定的断言？

lower_bound 定义为:

查找具有大于或等于指定值的有序范围中的第一个元素的位置,其中排序标准可以由二元谓词指定.

并且upper_bound:

查找具有大于指定值的有序范围中第一个元素的位置,其中排序条件可以由二元谓词指定.

具体来说,我有一个时间排序事件的容器,在给定的时间内,我想找到之前或之前的最后一个项目.我可以通过上/下限,反向迭代器和使用std::greater或std::greater_equal？的某种组合来实现这一点.

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

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;

Answer 1

在已排序的容器中,小于或等于的最后一个元素x是第一个元素之前大于的元素x.

因此,您可以调用std::upper_bound并递减返回的迭代器一次.(在递减之前,您当然必须检查它不是开始迭代器;如果是,则没有小于或等于的元素x.)

Answer 2

这是一个围绕upper_bound的包装函数,它返回容器或数组中小于或等于给定值的最大数字:

template <class ForwardIterator, class T>
  ForwardIterator largest_less_than_or_equal_to ( ForwardIterator first, 
                                                  ForwardIterator last,
                                                  const T& value)
{
  ForwardIterator upperb = upper_bound(first, last, value);

  // First element is >, so none are <=
  if(upperb == first)
    return NULL;

  // All elements are <=, so return the largest.
  if(upperb == last)
    return --upperb;

  return upperb - 1;
}

为了更好地解释这是做什么以及如何使用此功能,请查看:

C++ STL - 查找小于或等于数组或容器中给定元素的最后一个数字

Answer 3

我已经测试了您的反向迭代器解决方案，这是正确的。

给出v的按'<'排序

查找小于x的最后一个元素：

auto iter = std::upper_bound(v.rbegin(), v.rend(), x, std::greater<int>());
if(iter == v.rend())
    std::cout<<"no found";
else
    std::cout<<*iter;

查找小于x的最后一个元素：

auto iter = std::lower_bound(v.rbegin(), v.rend(), x, std::greater<int>());
if(iter == v.rend())
    std::cout<<"no found";
else
    std::cout<<*iter;

这比iter -= 1版本更好