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

是否有一个使用二进制搜索的函数，如 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;

3 回答

7

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

因此，您可以调用 std::upper_bound ，并将返回的迭代器减一次 . （在递减之前，你当然必须检查它不是开始迭代器;如果是，那么没有任何元素小于或等于 x . ）

回复于 2024-04-20T17:33:05+08:00

这是一个围绕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 — Find last number less than or equal to a given element in an array or container

回复于 2024-04-20T17:33:05+08:00

我测试了你的反向迭代器解决方案，这是正确的 .

给定 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 版更好

回复于 2024-04-20T17:33:05+08:00

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

3 回答

相关问题