STL binary search

[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

[Gianni Mariani]

Alex Gerdemann wrote:

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.

[Ivan Vecerina]

"Alex Gerdemann" <nu*******@hotmail.com> wrote in message
news:_wK9d.358075$Fg5.220754@attbi_s53...

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
--
http://ivan.vecerina.com/contact/?subject=NG_POST <- email contact form

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

--
A: Because it messes up the order in which people normally read text.
Q: Why is it such a bad thing?
A: Top-posting.
Q: What is the most annoying thing on usenet and in e-mail?

[John Harrison]

"Alex Gerdemann" <nu*******@hotmail.com> wrote in message
news:_wK9d.358075$Fg5.220754@attbi_s53...

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

[Ivan Vecerina]

"Alf P. Steinbach" <al***@start.no> wrote in message
news:41****************@news.individual.net...

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.

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
--
http://ivan.vecerina.com/contact/?subject=NG_POST <- email contact form

[Julián Albo]

Alex Gerdemann wrote:

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);

--
Salu2