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

Question

The book, "Effective STL," (by Scott Meyers), suggests that using sorted vectors instead of associative containers is efficient in some conditions. It shows the example of using std::lower_bound on std::vector. But I found some code in it that looks incorrect:

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 

When you see (1), it checks returned iterator from lower_bound so that it can tell if w is in the vector or not. But I think !(w < *i) is right because std::lower_bound would be using less(w, iterating element). The *i only has two choices: either it is equivalent with w (i.e. w is an element of vector) or it is greater than w. So, as far as I know, to tell these two cases the example code should have used !(w < *i).

Am I correct? Or is there any other reason for above example code?

Answer 1

The !(*i < w) is clearly wrong (or, at the very least, redundant) because, if the std::lower_bound() search does not return vw.end(), then the result of that test must be true. From 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.

Here's a trivial test that shows it does not correctly determine whether or not a given value is in your vector:

#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;
}

Output (clearly wrong):

3 is present
4 is present

However, changing the second test from the above !(*i < w) form, to your !(w < *i) works, as shown in the following modified code:

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;
}

Output (correct):

3 is present
4 is missing

---

So, unless you have somehow inadvertently misrepresented the code from the book you quote (which I am not accusing you of doing), then its author should be contacted to point out their error.