Re: sorting problem
On Apr 2, 12:50 pm, Comp1...@yahoo.co.uk wrote:
On Apr 2, 10:10 am, James Kanze <james.ka...@gmail.com> wrote:
On Apr 2, 1:42 am, Comp1...@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.
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.
The standard requires that pred(a,a) return false. This
definitely means that pred can't be <=.
Yes, I've read that too. But unfortunately my sources are
vague on what "strict weak ordering" means.
I'm not sure that it's an established concept, outside of
the standard. But even if it is, it doesn't really
matter---the standard explicitly defines what it means by
the term, and when the standard explicitly defines a term,
that's what it means in the standard, regardless of what it
might mean elsewhere. Basically, for a binary predicate
comp, if we define equiv(a,b) as !comp(a,b) && !comp(b,a),
then both comp and equiv must be transitive.
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.
The fact that P <= Q and Q <= P are both true also prevents
its use. (That's what the standard means by "strict".)
Thanks. My deeper problem is that if I define < on the pairs
to mean (a,b) < (c,d) if the interval (a,b) is _strictly_
contained in (c,d). Then the relation is non-reflexive but is
still not a strict weak ordering.
Correct, since the resulting equiv function isn't transitive.
In fact, if the conditions are met, equiv will define an
equivalent relationship. The problem with the ordering you are
concerned with is that it doesn't define a complete ordering,
there are pairs which are not ordered, but which are not
equivalent. (Another way of expressing the requirements, or at
least a condition that follows from the requirements, is that
for any given pair of elements, one must come before the other,
or they are members of the same equivalence class.)
--
James Kanze (GABI Software) email:james.kanze@gmail.com
Conseils en informatique orient=E9e objet/
Beratung in objektorientierter Datenverarbeitung
9 place S=E9mard, 78210 St.-Cyr-l'=C9cole, France, +33 (0)1 30 23 00 34