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?
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.