c++ - 具有 lower_bound 函数的二分搜索

Question

我正在使用 lower_bound 函数，以便返回迭代器而不是 bool 值。

auto testPair = make_pair(0, 0);
auto it3 = std::lower_bound(vec[1].begin(), vec[1].end(), testPair, [](const std::pair<int, double> a, const std::pair<int, double> b)
{
    return a.first < b.first;
});
if (it3 != vec[1].end() && !(testPair.first < it3->first))
    vec[1].erase(it3);

我基本上采用了原始实现并对其进行了更改，以便它返回一个迭代器，以便我可以使用对。

我的问题在下面一行:

if (it3 != vec[1].end() && !(testPair.first < it3->first))

我的感觉是可以删除第二个逻辑语句，因为使用 lower_bound 意味着 testPair.first 永远不应大于 it3->first。但是，如果我删除 if 语句的那一部分，它在某些情况下将无法正常工作。

谁能告诉我这是为什么以及为什么需要它？

如果我传递一对

    auto testPair = make_pair(0, 0);

成对的 vector ，其中包含以下内容

std::push_back(std::make_pair(1,1.6));
std::push_back(std::make_pair(2,1.7));

它会在不应该删除的时候删除第二对。

Answer 1

算法 std::lower_bound 返回迭代器，在该迭代器之前可以将目标值插入到序列中，这样序列仍然是有序的。这并不意味着该算法总是返回指向具有相同目标值的元素的迭代器。

例如，如果你有一个像这样的序列

{ 0, 2, 4, 6 }

并使用值 3 的算法，然后它将返回指向 4 的迭代器。该序列没有值为 3 的元素。因此，您应该检查自己的迭代器是否指向具有相同值的元素。

对于您示例中的 int 类型的对象，您可以简单地编写

if ( it3 != vec[1].end() && testPair.first == it3->first )
                                           ^^^

但通常(例如，当使用 float 时)最好使用运算符 <，因为通常使用此运算符对序列进行排序。例如，无需在类中声明运算符 == 即可通过运算符 < 对类的对象序列进行排序，然后使用算法 std::lower_bound 查找目标元素

事实上对于你的代码片段这个声明

if (it3 != vec[1].end() && !(testPair.first < it3->first))

等同于上面的语句。 testPair.first 不能大于 it3->first。同时如果不小于it3->first则可以断定它们是相等的。