Question about lower_bound

[Allerdyce.John]

On page 181 of Effective STL, it said 'It 's knowning when equal_range
is a better way to search than lower_bound, knowing when lower bound is
preferable to find..."

My question is understand what situation is lower_bound is better than
find?
I think both algorithm stops when it find the first item which matches
the condition.
So they should be the same, right?

Thank you for any help.

[Thomas Tutone]

Al************@gmail.com wrote:

On page 181 of Effective STL, it said 'It 's knowning when equal_range
is a better way to search than lower_bound, knowing when lower bound is
preferable to find..."

My question is understand what situation is lower_bound is better than
find?
I think both algorithm stops when it find the first item which matches
the condition.
So they should be the same, right?

No. std::lower_bound requires that the range be sorted. std::find
does not. std::lower_bound searches in logarithmic time. std::find
searches in linear time. std::lower_bound returns an iterator to where
the object would be inserted in the sorted range, even if the object
doesn't exist in the range. std::find simply returns the end of the
range if it can't find the object.

I haven't read it in a while, but I imagine Effective STL explains all
this.

Best regards,

Tom

[Ben Pope]

Thomas Tutone wrote:

Al************@gmail.com wrote:

On page 181 of Effective STL, it said 'It 's knowning when equal_range
is a better way to search than lower_bound, knowing when lower bound is
preferable to find..."

My question is understand what situation is lower_bound is better than
find?
I think both algorithm stops when it find the first item which matches
the condition.
So they should be the same, right?

No. std::lower_bound requires that the range be sorted. std::find
does not. std::lower_bound searches in logarithmic time. std::find
searches in linear time. std::lower_bound returns an iterator to where
the object would be inserted in the sorted range, even if the object
doesn't exist in the range. std::find simply returns the end of the
range if it can't find the object.

I haven't read it in a while, but I imagine Effective STL explains all
this.

If nothing else, it's summarised in a table on the back of the front cover.

Ben Pope
--
I'm not just a number. To many, I'm known as a string...

[JE]

Thomas Tutone wrote:
<snip>

std::lower_bound searches in logarithmic time.

to clarify, logarithmic with random access iterators, linear otherwise.
Best regards, JE