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