stl binary_search with linked list

[Sno Kart]

I have a class associated with a linked list and would like to implement the binary_search algorithm. How?


long s;
cout<<"Enter item to serach"<<endl;
cin>>s;

for(iter2 = form2List.begin();iter2 != form2List.end(); iter2++)
{
binary_search(form2List.front(),form2List.end(),(*iter2).var1,s);
}

thanks..

[jfaust]

binary_search works with random access iterators, which list does not have. You cannot do this.


Jeff

[Yves M]

Well, you can't, or at the least it would not make sense.

If you are using a linked list, random access to an element is O(n). Now binary search relies on the fact that random access is much faster than cycling through all the elements (typically random access is O(1) for arrays).

Can't you use std::list or std::vector or maybe even std::set ?

[Sno Kart]

Thank you. I will look at alternatives..

[Yves M]

If your list is always sorted, and you need to insert / delete elements dynamically, I would definitely recommend using std::set. Internally it is implemented most of the time as a red-black tree (so that it is guaranteed to be balanced to some degree). Random access, insertion and deletion are all O(log n) and the nice thing is that it always remains sorted ;)

[Sno Kart]

Thanks, I will check out std::set, as the requirements do not depend on linked list. I was only going for something quick, that would not require me to write my own structure for the porject.

std::set sounds good...