Question about lower_bound

[Allerdyce.John@gmail.com]

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]

Re: Question about lower_bound


Allerdyce.John@ gmail.com wrote:[color=blue]
> 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?[/color]

No. std::lower_boun d requires that the range be sorted. std::find
does not. std::lower_boun d searches in logarithmic time. std::find
searches in linear time. std::lower_boun d 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]

Re: Question about lower_bound

Thomas Tutone wrote:[color=blue]
> Allerdyce.John@ gmail.com wrote:[color=green]
>> 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?[/color]
>
> No. std::lower_boun d requires that the range be sorted. std::find
> does not. std::lower_boun d searches in logarithmic time. std::find
> searches in linear time. std::lower_boun d 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.[/color]

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]

Re: Question about lower_bound


Thomas Tutone wrote:
<snip>[color=blue]
> std::lower_boun d searches in logarithmic time.[/color]

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