lower_bound() 在 C++ 中

Question

从网上了解到，C++中的lower_bound()方法是用来return一个指向范围[first,last)中第一个有值的元素的迭代器不低于价值。这意味着函数 return 是下一个刚好大于该数字的最小数字的索引。

所以，对于下面给定的代码，我知道输出是 3。但是，因为有 6 的重复。我如何使用 lower_bound() 获得最后 6 个的索引。我可以为此实现自己的 binary_search()，但我想知道如何通过 lower_bound() 来实现。

#include <iostream> 
#include <algorithm>
#include <vector> 

using namespace std; 

int main () 
{ 
    int array[] = {5,6,7,7,6,5,5,6}; 

    vector<int> v(array,array+8); // 5 6 7 7 6 5 5 6 

    sort (v.begin(), v.end()); // 5 5 5 6 6 6 7 7 

    vector<int>::iterator lower,upper; 
    lower = lower_bound (v.begin(), v.end(), 6); 
    upper = upper_bound (v.begin(), v.end(), 6); 

    cout << "lower_bound for 6 at position " << (lower- v.begin()) << '\n'; 
    return 0; 
}

Answer 1

使用 lower_bound 和 upper_bound 对。或者一个 equal_range -- 那会更好。

upper_bound 和 equal_range 的高部分都将过去最后一个“6”。同理end不是最后一个，是过去最后一个

Answer 2

您可以在向量中使用反向迭代器，但是为了满足 std::lower_bound 的排序要求，您需要反转比较，因此您需要使用 std::greater 而不是默认的 std::less。然而，这也意味着现在您并不是真正在寻找下限，而是在寻找与该比较函数相关的上限，因此：

auto upper = std::upper_bound(v.rbegin(), v.rend(), 6, std::greater{});

Answer 3

如果数组已排序，在 lower_bound 和 upper_bound 之间迭代，您将获得所有等于枢轴点的元素：

lower = lower_bound(v.begin(), v.end(), 6);
upper = upper_bound(v.begin(), v.end(), 6);

for (auto it = lower; it != upper; it++) {
    assert(6 == *it);
}

你问的问题，即最后一个 6 的索引是什么，在标准库中没有相应的函数，因为在范围不存在的情况下定义不正确包含任何 6。在所有其他情况下，因为你有一个随机访问容器，你可以通过从 upper_bound （代码中的 upper - 1 ）中删除一个迭代器来获得最后一个 6 的迭代器，就像你得到的一样通过从长度中删除 1 来获取数组的最后一个索引。但是，我建议您在设计算法时避免依赖最后一个元素的位置相等。另请注意，如果您需要下限和上限，您可以使用 equal_range 同时获得两者，这甚至可能表现更好，因为它可能被优化为仅遍历数据结构一次：

std::tie(lower,upper) = equal_range(v.begin(), v.end(), 6);

for (auto it = lower; it != upper; it++) {
    assert(6 == *it);
}

Answer 4

您可以再次使用 lower_bound，更新开始和值：

auto lower = std::lower_bound (v.cbegin(), v.cend(), 6); 
auto upper = std::lower_bound (lower, v.cend(), 6 + 1);

std::cout << "Number of values found: " << std::distance(lower, upper) << '\n';

lower_bound() 在 C++ 中

lower_bound() in C++

c++

algorithm

vector

binary-search