Test lower_bound's return value against the end iterator

Question

In effective STL by Scott Meyers (page 195) there is the following line:

"The result of lower_bound must be tested to see if it's pointing to the value you're looking for. Unlike find, you can't just test lower_bound's return value against the end iterator."

Can anyone explain why you can't do this? seems to work fine for me.

Cloying

What is the context at that point in the book? It's confusing without knowing what the book is talking about. Is it saying for using lower_bound to see if a value is contained in the set? – Weighted

Answer 1

It works fine for you because your element is present.

lower_bound returns an iterator to the first element not less than the given value, and upper_bound returns an iterator to the first element greater than the given value.

Given the array 1, 2, 3, 3, 4, 6, 7, lower_bound(..., 5) will return an iterator pointing to 6.

Hence, two ways of checking whether the value is present:

• Use equal_range to also get the upper_bound (computing separately lower_bound and upper_bound will probably be suboptimal). If the std::distance between the bounds is greater than 0 then the element is present.

  1, 2, 3, 3, 4, 6, 7
  std::distance(std::lower_bound(v.begin(),v.end(),5), std::upper_bound(v.begin(),v.end(),5)) == 0 // 6 is absent
  std::distance(std::lower_bound(v.begin(),v.end(),3), std::upper_bound(v.begin(),v.end(),3)) == 2 // 3 is present
  

• Compare the element pointed by the iterator with your value (provided operators != and < are coherent), but you have to make sure it does not return the end iterator.

  *(std::lower_bound(v.begin(), v.end(), 5)) != 5
  

Additionally, since lower_bound is a binary search algorithms it would be inconsistent to return end if the element was not found. Actually, the iterators returned by this algorithm can be used as a hint for a subsequent insertion operation for example.

Autonomic

+1: But as Meyers says in that book, comparing for equality won't always work (because lower_bound uses <, not ==). – Impression

@Oli Charlesworth: If you override < you should probably override == as well. Adapted answer. – Autonomic

Even if you do, they won't necessarily correspond: == corresponds to "equality", < corresponds to "equivalence". See Item 19 of Effective STL for a discussion of this. – Impression

If you overload <, you should also overload == in a compatible fashion (and <=, >, >= and !=). The real issue is when you don't overload <, but pass a comparison operator to lower_bound. In such cases, you have to use the same comparison function when checking after the call to lower_bound. – Sororicide