is STL Find method for vector the fastest?

[tonnot]

I have a ordered vector. STL finder use internally bubble search ?
( I'd want to know if have I to implement a custom method to do a faster find)
Thanks

[coder777]

'std::find()' doesn't change anything. Look at this http://www.cplusplus.com/reference/algorithm/find/

You can expect that stl functions are highly optimized since they're around for such a long time.

[kev82]

http://www.sgi.com/tech/stl/lower_bound.html

[Galik]

I would imagine std::binary_search() is pretty efficient:
http://cplusplus.com/reference/algorithm/binary_search/

If you want to know the actual position of the element then lower_bound() also uses a binary search:
http://cplusplus.com/reference/algorithm/lower_bound/

[tonnot]

mmm. I dont know if I didn't explain well.
( I dont want to change nothing, netiher sort something)

I have a already ordered vector of custom class. In example, I have 100000 elements.
This class has a 'id' prop. I use it to do the properly sort.

My questión is, the find method use internally some 'bubble search' or it analyzes every item of the vector until the value was found ?

For what I have seen, I think that find looks every item from first to last ?
Thanks

[coder777]

For what I have seen, I think that find looks every item from first to last ?

From first to last only when none is found otherwise until one is found

[1vRz3TCk]

I have a ordered vector. STL finder use internally bubble search ?

It would be pretty hard to say. The standard does not specify what algorithm to use just what it has to do. As std::find is able to handle unsorted data, it must be implemented as a linear search but more than that I could not say.

[tonnot]

I dont know you zare111 -----

Thanks Coder777.
What means otherwise ?

If I have 10 elements : 1,2,33,50,52,53,90,91,98,100 .
And I want to find if I have 92 , I'd look into the range 1- 53 / and 53 -100 . Then into the 53-91 / 91 -100, then 91-98/ 98-100. Finally I know that there is no 92 and I'd have to insert it behind item 9 (98 ). This was my old method when I programmed with VB6....
So my question is , STL find method uses something like this , isn't it ?

Thanks

[1vRz3TCk]

std::find does not know anything about the ordering of your std::vector so it will search each element for 92.

[Galik]

tonnot wrote:

For what I have seen, I think that find looks every item from first to last ?

Yes, std::find() searches sequentially. That is why I mentioned std::binary_search() and std::lower_bound(). I think one of them is probably what you are looking for.

[1vRz3TCk]

Finally I know that there is no 92 and I'd have to insert it behind item 9

std:: vector is good at is good at inserting at the ends but not in the middle, it may be worth looking at std::list.

This provides the following advantages to list containers:
Efficient insertion and removal of elements anywhere in the container (constant time).
Efficient moving elements and block of elements within the container or even between different containers (constant time).
Iterating over the elements in forward or reverse order (linear time).

http://www.cplusplus.com/reference/stl/list/

Vectors are good at:
Accessing individual elements by their position index (constant time).
Iterating over the elements in any order (linear time).
Add and remove elements from its end (constant amortized time).

http://www.cplusplus.com/reference/stl/vector/

[coder777]

tonnot wrote:

What means otherwise ?

Um, you mean what the word 'otherwise' means?

Galik is right in an preordered container binary_search()/lower_bound() are pretty more effective than find().

if you want to insert an item it's better to use std::list and lower_bound() because the latter tells you where to insert.

tonnot wrote:

And I want to find if I have 92 , I'd look into the range 1- 53 / and 53 -100 . Then into the 53-91 / 91 -100, then 91-98/ 98-100. Finally I know that there is no 92 and I'd have to insert it behind item 9 (98 ). This was my old method when I programmed with VB6....

That's what binary_search()/lower_bound() does

[ne555]

If you want a set, then use a set. (binary_search takes advantage of random access)

[moorecm]

This definitely sounds like it should be std::set. 100000 contiguous elements (in a vector) sounds like a real memory hog.

[moorecm]

BTW, binary searches are logarithmic or O(log n). That's pretty fast but there are (amortized?) constant-time look-ups for hash tables (not in the STL) if you need a faster data structure.