使用STL查找小于当前的最大元素

Find largest element smaller than current with STL

是否有一个单行代码可以找到排序容器中小于某个元素 x 的最大元素?我基本上对任何能给我一个指向小于 x 的最大元素的迭代器的代码感兴趣。

我知道如何自己编写代码,但希望有一个库函数...

编辑:也许我应该在这里说清楚,我想自己编写的版本是基于二进制搜索的,因此运行时间为 O(log n)。我需要为包含多达几百万个元素的列表计算此值。

由于您的容器已排序,您可以在以大于最大值的第一个元素结尾的范围内使用 std::max_element,使用带有 lambda 的 std::find_if,或 std::lower_bound 来获得这个范围:

int main()
{
    std::set<int> s{ 3, 1, -14, 1, 5, 9 }; 
    std::set<int>::iterator result;

    int max_value = 6;
    result = std::max_element(std::begin(s), std::find_if(std::begin(s), std::end(s), [&](int i) { return i >= max_value; } ) );
    std::cout << "max element is: " << *result;
}

输出:

max element is: 5

Live Demo

std::lower_bound :

int main()
{
    std::set<int> s{ 3, 1, -14, 1, 5, 9 }; 
    std::set<int>::iterator result;

    int max_value = 6;
    result = std::max_element(std::begin(s), std::lower_bound(std::begin(s), std::end(s), max_value)) ;
    std::cout << "max element is: " << *result;
}

Live Demo

你可以直接使用

lower_bound(container.begin(), container.end(), currentElement);

现在,如果它与 container.begin() 不同,那么有一个元素比您当前的元素小,只需减去一个即可。如果你确定总是有这样的元素就做

lower_bound(container.begin(), container.end(), currentElement) - 1;

编辑:当然我假设你的迭代器是双向的。

假设您的数据在一组 s 整数中,您可以找到小于 x 的最大元素,如下所示:

auto it = s.lower_bound( x ); // s.lower_bound has a complexity of O(logn)
if( it == s.begin() )
{
    std::cout << "No element found" << "\n";
}
else
{
    --it;
    std::cout << *it << "\n";
}

lower_bound 本质上 returns 你是一个指向最小元素 >= x 的迭代器 it。因此,它只是前一个指针 --it 会指向最大的元素,即 < x。这种方法的复杂性是 O(log n).

结合使用prev()lower_bound()

  • mycontainer.lower_bound(int_val) returns 等于或大于 int_val

  • 的迭代器
  • *prev(mycontainer.lower_bound(int_val)) returns容器中int_val之前的值

作为防御性检查,首先验证它不在容器的开头:

int result = -1, target = 15;
set<int> _container;
auto _iterator = _container.lower_bound(target);
if(_iterator != _container.begin())
   result = *std::prev(_iterator);