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.

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.