By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
454,137 Members | 1,024 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 454,137 IT Pros & Developers. It's quick & easy.

please help me on lower_bound && upper_bound

P: n/a
I have a class board, like this:
struct board
{
int x1, x2, h;
int time1, time2;
void calculate_time();
void assign(int x1__,int x2__,int h__);
};

And I have n boards stored in an array called boards__[n], and I have
got the array sorted by board.h ascendantly.

I have a pair<int,intt=pair<int,int>(x0,h0).

What I want to do is: to find the last board int boards__[n] which
satisfies this:
its h< h0,
and its x1<=t.first
and its x2>=t.second.

So, can I do it by upper_bound or lower_bound?
Which one do I have to use?
I tried for a moment and I couldn't find a way. Will you please help me
out?
Thanks!

Dec 26 '06 #1
Share this Question
Share on Google+
3 Replies


P: n/a

co*******@gmail.com wrote:
I have a class board, like this:
struct board
{
int x1, x2, h;
int time1, time2;
void calculate_time();
void assign(int x1__,int x2__,int h__);
};

And I have n boards stored in an array called boards__[n], and I have
got the array sorted by board.h ascendantly.

I have a pair<int,intt=pair<int,int>(x0,h0).

What I want to do is: to find the last board int boards__[n] which
satisfies this:
its h< h0,
and its x1<=t.first
and its x2>=t.second.

So, can I do it by upper_bound or lower_bound?
Which one do I have to use?
I tried for a moment and I couldn't find a way. Will you please help me
out?
Thanks!
Take a look at std::map. It inserts std::pair key/elements using a
programmeable order and already provides lower_bound and upper_bound
member functions.
http://www.sgi.com/tech/stl/Map.html
You also have std::multimap if you need duplicate pairs.

Dec 26 '06 #2

P: n/a
thank you,
but I'm not dealing with pair stuff.
I wrap the two numbers in a pair is just to pass is as a single param
into the algorithm.
It's also OK to put the two numbers in an arbitrary structure.

Salt_Peter wrote:
co*******@gmail.com wrote:
I have a class board, like this:
struct board
{
int x1, x2, h;
int time1, time2;
void calculate_time();
void assign(int x1__,int x2__,int h__);
};

And I have n boards stored in an array called boards__[n], and I have
got the array sorted by board.h ascendantly.

I have a pair<int,intt=pair<int,int>(x0,h0).

What I want to do is: to find the last board int boards__[n] which
satisfies this:
its h< h0,
and its x1<=t.first
and its x2>=t.second.

So, can I do it by upper_bound or lower_bound?
Which one do I have to use?
I tried for a moment and I couldn't find a way. Will you please help me
out?
Thanks!

Take a look at std::map. It inserts std::pair key/elements using a
programmeable order and already provides lower_bound and upper_bound
member functions.
http://www.sgi.com/tech/stl/Map.html
You also have std::multimap if you need duplicate pairs.
Dec 26 '06 #3

P: n/a
So, can I do it by upper_bound or lower_bound?
You can find range of elements satisfying first condition (h < h0)
using upper_bound(), but then you will need to iterate through this
range to check all conditions.

Though, you can check all elements of sorted array and stop scanning
when condition h < h0 becomes false.

Dec 26 '06 #4

This discussion thread is closed

Replies have been disabled for this discussion.