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

Question

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

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

编辑：也许我应该在这里说清楚，我想到的版本我将自己编码是基于二进制搜索，因此在O（log n）时间运行。我需要为最多几百万个元素的列表计算这个。

Answer 1

由于您的容器已排序，您可以在以大于最大值的第一个元素结尾的范围内使用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;
}

输出：

最大元素是：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

Answer 2

你可以使用

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

现在，如果这与container.begin()不同，则有一个小于当前元素的元素，只需减去一个就可以得到它。如果你确定总会有这样一个元素

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

编辑：当然我假设您的迭代器是双向的。

Answer 3

假设您的数据集合在整数s中，您可以找到小于x的最大元素，如下所示：

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

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