8

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.

dangerousdave
  • 6,331
  • 8
  • 45
  • 62
  • 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? – Justin Jan 22 '18 at 06:33

1 Answers1

9

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.

Benoit
  • 76,634
  • 23
  • 210
  • 236
  • +1: But as Meyers says in that book, comparing for equality won't always work (because `lower_bound` uses `<`, not `==`). – Oliver Charlesworth Jan 05 '12 at 10:43
  • @Oli Charlesworth: If you override `<` you should probably override `==` as well. Adapted answer. – Benoit Jan 05 '12 at 10:44
  • 3
    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. – Oliver Charlesworth Jan 05 '12 at 10:48
  • 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`. – James Kanze Jan 05 '12 at 11:23