searching a sorted list

[kasthurirangan.balaji]

Hello,

I have a string list of the format

rangeA rangeB 001
rangeA rangeB1002
rangeA rangeC 003
rangeB rangeC 004

This list is sorted according to the ranges in column 1. Now i have a
value rangeA1B. What is the efficient way to search this value? I need
to select all the three rangeA in the search. Using std::search or
std::find is a best choice here? Or if i need to write any algorithm,
what is that?

Though this seems like a programming question, i have posted here
because i need to write the solution in c++.

Thanks,
Balaji.

 

[red floyd]

Hello,

I have a string list of the format

rangeA rangeB 001
rangeA rangeB1002
rangeA rangeC 003
rangeB rangeC 004

This list is sorted according to the ranges in column 1. Now i have a
value rangeA1B. What is the efficient way to search this value? I need
to select all the three rangeA in the search. Using std::search or
std::find is a best choice here? Or if i need to write any algorithm,
what is that?

Though this seems like a programming question, i have posted here
because i need to write the solution in c++.

Well, then your answer can be found in the FAQ:

http://www.parashift.com/c++-faq-lite/how-to-post.html#faq-5.2

and

http://www.parashift.com/c++-faq-lite/how-to-post.html#faq-5.9

Because the solution is independent of the language.

 

[Kai-Uwe Bux]

(e-mail address removed) wrote:

[snip]

I have a string list of the format

rangeA rangeB 001
rangeA rangeB1002
rangeA rangeC 003
rangeB rangeC 004

This list is sorted according to the ranges in column 1. Now i have a
value rangeA1B. What is the efficient way to search this value? I need
to select all the three rangeA in the search. Using std::search or
std::find is a best choice here? Or if i need to write any algorithm,
what is that?

[snip]


You might consider storing your data as a std::multimap. The first column
would be the key_type and the second and third need to be combined into the
mapped_type. Then, you could use lower_bound() and upper_bound().


Best

Kai-Uwe Bux

 

[kasthurirangan.balaji]

(e-mail address removed) wrote:

[snip]> I have a string list of the format

rangeA rangeB 001
rangeA rangeB1002
rangeA rangeC 003
rangeB rangeC 004

This list is sorted according to the ranges in column 1. Now i have a
value rangeA1B. What is the efficient way to search this value? I need
to select all the three rangeA in the search. Using std::search or
std::find is a best choice here? Or if i need to write any algorithm,
what is that?

[snip]

You might consider storing your data as a std::multimap. The first column
would be the key_type and the second and third need to be combined into the
mapped_type. Then, you could use lower_bound() and upper_bound().

Best

Kai-Uwe Bux

Hello Kai,

Thanks. Your answer seems to be an apt fit. Actually, i was planning
to use multimap, but the key being a pair of the ranges and was
looking for already available algorithms where i can pass a predicate,
rather than reinvent. Once again, thanks to you.

Thanks,
Balaji.

 

[kasthurirangan.balaji]

Well, then your answer can be found in the FAQ:

http://www.parashift.com/c++-faq-lite/how-to-post.html#faq-5.2

and

http://www.parashift.com/c++-faq-lite/how-to-post.html#faq-5.9

Because the solution is independent of the language.- Hide quoted text -

- Show quoted text -

Hello Red,

Special thanks to you for pointing me that. Re-read again.

Actually i was looking for solution in c++(something already
available, rather than reinvent). I was also planning to post in
comp.programming but didn't want to cross/double post in the beginning
itself.

Thanks,
Balaji.

 

[Joe Greer]

(e-mail address removed) wrote in (e-mail address removed):

Hello,

I have a string list of the format

rangeA rangeB 001
rangeA rangeB1002
rangeA rangeC 003
rangeB rangeC 004

This list is sorted according to the ranges in column 1. Now i have a
value rangeA1B. What is the efficient way to search this value? I need
to select all the three rangeA in the search. Using std::search or
std::find is a best choice here? Or if i need to write any algorithm,
what is that?

Though this seems like a programming question, i have posted here
because i need to write the solution in c++.

Thanks,
Balaji.

If you are sorted by all three fields, then you should be able to use
std::lower_bound() which has a predicate version. This will do a binary
search on the data.

Hope that helps,
joe