Re: sorting problem
Comp1597@yahoo.co.uk wrote:
On Apr 2, 1:35 am, Victor Bazarov <v.Abaza...@comAcast.net> wrote:
Comp1...@yahoo.co.uk wrote:
On Apr 2, 1:10 am, Comp1...@yahoo.co.uk wrote:
Suppose we have pairs of integers of the form (a,b). I want to define
(a,b) <= (c,d) as meaning a >=c and b<=d
(The motivation for this definition is that it means that the interval
(a,b) is a subset of (c,d) ).
Are there any STL functions that can be used for this type of sort? I
don't believe the standard sort (applied to the standard containers)
would work.
Thank you.
I should have said explicitly that I want to sort according to this
new definition of <=. Of course, there will be incomparable
elements. My aim is to transform the original set of pairs into
several sets of pairs where each set is totally ordered.
Standard sort applies predicate but the predicate should have the strict
weak ordering trait. I am not sure that the "less-or-equal" qualifies.
V
--
Please remove capital 'A's when replying by e-mail
I do not respond to top-posted replies, please don't ask
Yes, I've read that too. But unfortunately my sources are vague on
what "strict weak ordering" means.
Under my ordering, if P and Q are intervals such that neither P <= Q
or Q <= P, it could still hold that P <=Z is true but Q <= Z is
false. I think this property prevents the predicate being used in
sort.
Sources are vague? What sources are those? Ever tried Wikipedia.org?
First and foremost, to be able to sort, pred(x,x) should return 'false'.
If you write your predicate as "less than *or equal*", then this
simple rule of 'pred(x,x)' to be true is not going to be satisfied.
Then there is if pred(x,y) == true, then !pred(y,x) == true. Won't be
satisfied with '<=' semantics.
What you could do is to define the correct 'a < b' as the complete
inclusion of 'a' range into the 'b' range. That way when you sort, all
equivalent ranges will end up next to each other anyway.
Try it. Define
bool mypredicate(std::pair<int,int> const& p1,
std::pair<int,int> const& p2)
{
// if 'p1' is a complete subrange of 'p2', return true
// otherwise return false.
}
then sort an array (or a vector) of 'std::pair<int,int>' using std::sort
and that predicate. See what happens. Experiment with overlapping
ranges, equal ranges, fully enclosed ranges, etc. Mix them up, sort,
print out the results. See if it fits what you expected. If not, post
your code here, post your expectations, post the results, explain how
it's not what you expected, and we'll be happy to help you.
V
--
Please remove capital 'A's when replying by e-mail
I do not respond to top-posted replies, please don't ask