如何使用 std::lower_bound 检查向量中的元素？

Question

“Effective STL”一书（作者 Scott Meyers）建议在某些情况下使用排序向量而不是关联容器是有效的。它显示了在 std::vector 上使用 std::lower_bound 的示例。但是我发现其中的一些代码看起来不正确：

vector<Widget> vw;            // alternative to set<Widget>
 ......                       // Setup phase: lots of
                              // insertions, few lookups

sort(vw.begin(), vw.end());   // end of Setup phase.

Widget w;                     // object for value to look up
 ......                       // start Lookup phase

vector<Widget>::iterator i =
lower_bound(vw.begin(), vw.end(), w);  // lookup via lower_bound;

(1) Below is the weird part!
if (i != vw.end() && !(*i < w))...     // see Item 45 for an explana-
                                       // tion of the"!(*i < w)" test

...                                    // end Lookup phase, start

当您看到 (1) 时，它会检查从 lower_bound 返回的迭代器，以便它可以判断 w 是否在向量中。但我认为 !(w < *i) 是正确的，因为 std::lower_bound 会使用 less(w, iterating element)。 *i只有两个选择：要么等价于w（即w是向量的一个元素），要么大于w。因此，据我所知，要说明这两种情况，示例代码应该使用 !(w < *i).

我说的对吗？或者上面的示例代码还有其他原因吗？

Answer 1

!(*i < w) 显然是错误的（或者至少是多余的）因为，如果 std::lower_bound() 搜索不是 return vw.end()，那么那个测试的结果一定是真。来自 cppreference:

Returns an iterator pointing to the first element in the range [first, last) that is not less than (i.e. greater or equal to) value, or last if no such element is found.

这是一个简单的测试，表明它无法正确确定给定值是否在您的向量中：

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

int main()
{
    std::vector<int> vec = { 1,2,3,5,6,7,8,9,10 };
    std::vector<int>::iterator i1 = std::lower_bound(vec.begin(), vec.end(), 3); // Present
    if (i1 != vec.end() && !(*i1 < 3)) {
        std::cout << "3 is present\n";
    }
    else {
        std::cout << "3 is missing\n";
    }
    std::vector<int>::iterator i2 = std::lower_bound(vec.begin(), vec.end(), 4); // Missing
    if (i2 != vec.end() && !(*i2 < 4)) {
        std::cout << "4 is present\n";
    }
    else {
        std::cout << "4 is missing\n";
    }
    return 0;
}

输出（明显错误）：

3 is present
4 is present

但是，将上面的 !(*i < w) 形式的第二个测试更改为您的 !(w < *i) 形式，如以下修改后的代码所示：

int main()
{
    std::vector<int> vec = { 1,2,3,5,6,7,8,9,10 };
    std::vector<int>::iterator i1 = std::lower_bound(vec.begin(), vec.end(), 3); // Present
    if (i1 != vec.end() && !(3 < *i1)) {
        std::cout << "3 is present\n";
    }
    else {
        std::cout << "3 is missing\n";
    }
    std::vector<int>::iterator i2 = std::lower_bound(vec.begin(), vec.end(), 4); // Missing
    if (i2 != vec.end() && !(4 < *i2)) {
        std::cout << "4 is present\n";
    }
    else {
        std::cout << "4 is missing\n";
    }
    return 0;
}

输出（正确）：

3 is present
4 is missing

所以，除非你不知何故无意中歪曲了你引用的书中的代码（我 而不是 指责你这样做） , 那么应该联系它的作者指出他们的错误。

如何使用 std::lower_bound 检查向量中的元素？

How to check the element is in the vector using std::lower_bound?

c++

lower-bound