searching a sorted list

[kasthurirangan.balaji@gmail.com]

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]

Re: searching a sorted list

kasthurirangan. balaji@gmail.co m wrote:

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]

Re: searching a sorted list

kasthurirangan. balaji@gmail.co m 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@gmail.com]

Re: searching a sorted list

On Aug 23, 12:02 am, Kai-Uwe Bux <jkherci...@gmx .netwrote:

kasthurirangan. bal...@gmail.co m 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@gmail.com]

Re: searching a sorted list

On Aug 22, 11:08 pm, red floyd <no.spam.h...@e xample.comwrote :

kasthurirangan. bal...@gmail.co m wrote:

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.- 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.programmin g but didn't want to cross/double post in the beginning
itself.

Thanks,
Balaji.

[Joe Greer]

Re: searching a sorted list

kasthurirangan. balaji@gmail.co m wrote in news:9dc89336-659c-4aed-89f8-
345b3d8b67af@56 g2000hsm.google groups.com:

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_boun d() which has a predicate version. This will do a binary
search on the data.

Hope that helps,
joe

[stan]

Re: searching a sorted list

kasthurirangan. balaji@gmail.co m wrote:

On Aug 23, 12:02 am, Kai-Uwe Bux <jkherci...@gmx .netwrote:

>kasthurirangan .bal...@gmail.c om 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.

It's really starting to look like the prof found a problem with no
answer posted. Sorry.