C++ - STL binary search
wizard
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?
Here is my dat structure. I'd like to search on id item.
class MyListTable
{
public:
int id;
string text;
};
Sam
> I am writing a program where I have a vector
> 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?
Subtract the iterator from vector.begin().
Bart van Ingen Schenau
> I am writing a program where I have a vector
> 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?
You can calculate the index from the iterator like this:
size_t index = std::distance(list.begin(), found_iterator);
For containers with random-access iterators, like std::vector, that is a
constant-time operation.
Bart v Ingen Schenau
--
a.c.l.l.c-c++ FAQ: http://www.comeaucomputing.com/learn/faq
c.l.c FAQ: http://c-faq.com/
c.l.c++ FAQ: http://www.parashift.com/c++-faq-lite/
wizard
class as below?
Bart van Ingen Schenau
It would be helpful if you quote some context to indicate what you are
replying to.
Here is a snippet of std::distance with a vector<MyListTable> (assuming
all relevant headers are included and overloaded operators are defined):
std::vector<MyListTable> list;
/*... populate and sort list ...*/
std::vector<MyListTable>::iterator it = std::binary_search(list.begin(),
list.end(), 42);
int index = std::distance(list.begin(), it);
assert(list[i] == *it);
wizard
wrote 42 You mean: id variable in MyListTable class)
How can I change binary search to search for variable text in MyListTable
class?
std::vector<MyListTable>::iterator it = std::binary_search(list.begin(),
list.end(), 42);
class MyListTable
{
public:
int id;
string text;
};
Regards
Greg
Joe Smith
"wizard" <gg...@wp.pl> wrote in message
news:h22qqu$qb2$1...@nemesis.news.neostrada.pl...
> Thanks for Your reply but How can I indicate variable in binary search
> (You wrote 42 You mean: id variable in MyListTable class)
> How can I change binary search to search for variable text in MyListTable
> class?
>
class MyListTable
{
public:
int id;
std::string text;
};
bool compfunc(MyListTable a, MyListTable b)
{
return a.text<b.text;
}
int main()
{
std::vector<MyListTable> list;
std::sort(list.begin(),list.end(),compfunc);
MyListTable valueToFind = {0,"Sometext"};
std::vector<MyListTable>::iterator it = std::binary_search(list.begin(),
list.end(), valueToFind, compfunc);
int index = std::distance(list.begin(),it);
}
peter koch
wrote:
> wizard wrote:
> > Could You give me a example how to use Your solution on my
> > class as below?
>
> > class MyListTable
> > {
> > public:
> > int id;
> > string text;
> > };
>
> It would be helpful if you quote some context to indicate what you are
> replying to.
>
> Here is a snippet of std::distance with a vector<MyListTable> (assuming
> all relevant headers are included and overloaded operators are defined):
>
> std::vector<MyListTable> list;
> /*... populate and sort list ...*/
>
> std::vector<MyListTable>::iterator it = std::binary_search(list.begin(),
returns a bool, indicating if the value if found or not. I agree: a
bad name.
> list.end(), 42);
> int index = std::distance(list.begin(), it);
/Peter
wizard
I 'll try Your solutiom
Greg
Uzytkownik "peter koch" <peter.ko...@gmail.com> napisal w wiadomosci
news:ed52574a-8234-4f53...@k26g2000vbp.googlegroups.com...
Juha Nieminen
>> std::vector<MyListTable>::iterator it = std::binary_search(list.begin(),
> That should be std::lower_bound (or std::upper_bound). binary_search
> returns a bool, indicating if the value if found or not. I agree: a
> bad name.
Not really. It's "lower_bound" because it doesn't tell you if the
searched element is there or not. It tells you the location where the
new element can be inserted so that after the insertion the vector will
still be sorted.
(The difference between lower_bound and upper_bound is that the former
tells you the *first* place where the insertion can be done while the
latter tells you the *last* place, which can make a difference if
there's more than one place where the new element can be inserted while
keeping the vector sorted. This is the case when at least one element
equal to the new element already exists in the vector.)
In other words, just calling std::lower_bound is not enough to know if
the element is there (unless you are certain that it is there because of
how the program works). You have to also check if the element pointed by
the returned iterator is equal to the searched element. (But remember to
check if the returned iterator points to end() first!)