STL binary search

A

Alex Gerdemann

Hello,

I am writing a program where I have a vector (std::vector<std:string> list)
that I need to search many times. To accomplish this efficiently, I plan to
sort the list using std::sort(list.begin(),list.end()), then run binary
searches. I need to get the indices of the elements found so I can
construct a matrix where I allocate a row of a matrix for each string in the
list (row one for the first item in the list, etc). However the binary
search algorithm in the STL returns an iterator that points to the object in
the vector rather than the index. Is there some way I can use STL to get
the index of an element without running a linear search?

Thanks,

Alex Gerdemann
University of Illinois at Urbana-Champaign
 
G

Gianni Mariani

Alex said:
Hello,

I am writing a program where I have a vector (std::vector<std:string> list)
that I need to search many times. To accomplish this efficiently, I plan to
sort the list using std::sort(list.begin(),list.end()), then run binary
searches. I need to get the indices of the elements found so I can
construct a matrix where I allocate a row of a matrix for each string in the
list (row one for the first item in the list, etc). However the binary
search algorithm in the STL returns an iterator that points to the object in
the vector rather than the index. Is there some way I can use STL to get
the index of an element without running a linear search?

I believe that std:vector guatentees contiguous elements hence the
follwoing holds true:

std::vector<T> arr;
std::vector<T>::iterator i1;
....
int indexof_i1 = &(*i1) - &(*arr.begin());

(iff i1 is an iterator of the arr vector and the vector is not empty)

You can often use pointers instead of iterators in many stl algorithms.

If you're going to be searching for elements very frequently, it may be
that you can use a hashing algorithm and that might be faster.

Hope this helps.
 
I

Ivan Vecerina

Alex Gerdemann said:
I am writing a program where I have a vector (std::vector<std:string>
list) that I need to search many times. To accomplish this efficiently, I
plan to sort the list using std::sort(list.begin(),list.end()), then run
binary searches. I need to get the indices of the elements found so I can
construct a matrix where I allocate a row of a matrix for each string in
the list (row one for the first item in the list, etc). However the
binary search algorithm in the STL returns an iterator that points to the
object in the vector rather than the index.
Actually, std::binary_search returns a bool telling whether the item
was found or not.
Is there some way I can use STL to get the index of an element without
running a linear search?
Yes, you can use std::lower_bound in <algorithm>.
This one returns an iterator, which can readily be converted to an index:
index = lower_bound( list.begin(), list.end(), valToBeFound ) -
list.begin();

Note that if you are not sure that the string to be found is in the list,
you need to (1) verify that the resut of lower_bound is not list.end()
and (2) verify that the result is actually equal to the searched string.


Cheers,
Ivan
 
A

Alf P. Steinbach

* Alex Gerdemann:
I am writing a program where I have a vector (std::vector<std:string> list)
that I need to search many times. To accomplish this efficiently, I plan to
sort the list using std::sort(list.begin(),list.end()),

This looks like a bit of confusion regarding choice of data structure.

Do you want a vector, a list, or an efficiently searchable structure?

Is there some way I can use STL to get
the index of an element without running a linear search?

Try a std::map, a std::multimap, a std::set or a std::multiset, depending on
what the requirements really are.
 
J

John Harrison

Alex Gerdemann said:
Hello,

I am writing a program where I have a vector (std::vector<std:string>
list) that I need to search many times. To accomplish this efficiently, I
plan to sort the list using std::sort(list.begin(),lis
t.end,thenrunbinary
searches. I need to get the indices of the elements found so I can
construct a matrix where I allocate a row of a matrix for each string in
the list (row one for the first item in the list, etc). However the
binary search algorithm in the STL returns an iterator

You must be thinking of lower_bound, binary_search returns a bool.
that points to the object in the vector rather than the index. Is there
some way I can use STL to get the index of an element without running a
linear search?

Of course

int index = iter - list.begin();

Just subtract the iterator pointing to the beginning of a vector from
another iterator pointing to the vector and you have the index.

john
 
I

Ivan Vecerina

Alf P. Steinbach said:
Try a std::map, a std::multimap, a std::set or a std::multiset, depending
on
what the requirements really are.

I remember from personal experiments that searching a sorted vector
is typically faster than using any of these containers.
This was also reported by Scott Meyers and others (Andrei) IIRC.
The associative containers only make sense if the list changes often.

Of course, a hash table will work best, and while non-standard, hash_set
is available in some form on most platforms. [if the list of words is
known at compile-time, a tool like GNU gperf is an ultimate solution]


Regards,
Ivan
 
?

=?ISO-8859-15?Q?Juli=E1n?= Albo

Alex said:
list (row one for the first item in the list, etc). However the binary
search algorithm in the STL returns an iterator that points to the object
in the vector rather than the index. Is there some way I can use STL to >
get the index of an element without running a linear search?

index= std::distance (container.begin (), found);
 

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

Forum statistics

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

Latest Threads

Top