Question about lower_bound

A

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.
 
T

Thomas Tutone

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
 
B

Ben Pope

Thomas said:
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
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,483
Members
44,901
Latest member
Noble71S45

Latest Threads

Top