# sorting problem

Discussion in 'C++' started by Comp1597@yahoo.co.uk, Apr 2, 2009.

1. ### Guest

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.

, Apr 2, 2009

2. ### Guest

On Apr 2, 1:10 am, 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.

, Apr 2, 2009

3. ### Victor BazarovGuest

wrote:
> On Apr 2, 1:10 am, 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
--

Victor Bazarov, Apr 2, 2009
4. ### Guest

On Apr 2, 1:35 am, Victor Bazarov <> wrote:
> wrote:
> > On Apr 2, 1:10 am, 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
> --

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.

, Apr 2, 2009
5. ### Victor BazarovGuest

wrote:
> On Apr 2, 1:35 am, Victor Bazarov <> wrote:
>> wrote:
>>> On Apr 2, 1:10 am, 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
>> --

>
> 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:air<int,int> const& p1,
std:air<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:air<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
it's not what you expected, and we'll be happy to help you.

V
--

Victor Bazarov, Apr 2, 2009
6. ### Guest

On Apr 2, 1:56 am, Victor Bazarov <> wrote:
> wrote:
> > On Apr 2, 1:35 am, Victor Bazarov <> wrote:
> >> wrote:
> >>> On Apr 2, 1:10 am, 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
> >> --
> >> 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:air<int,int> const& p1,
>                       std:air<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:air<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
> --

Reading further, the definition (a,b) < (c,d) if [a,b] is strictly
included in [c,d] is not a strict weak ordering. Hence the predicate
version of sort can't be applied. The reason it's not a strict weak
ordering is that the relationship of incomparability is non-
transitive.
Hence my next question is: are there sorting algorithms in the STL
that handle partially ordered sets which aren't strictly weakly
would have thought it was a standard problem.

, Apr 2, 2009
7. ### Kai-Uwe BuxGuest

wrote:

[...]
> Hence my next question is: are there sorting algorithms in the STL
> that handle partially ordered sets which aren't strictly weakly
> ordered?

I don't think there is.

> would have thought it was a standard problem.

E.g., a standard problem in this context is topological sorting: embed a
partially ordered set into a totally ordered set so that the partial order
is preserved. As far as I know, the standard library has no algorithm for
that.

Best

Kai-Uwe Bux

Kai-Uwe Bux, Apr 2, 2009
8. ### Thomas WintschelGuest

wrote:
> On Apr 2, 1:56 am, Victor Bazarov <> wrote:
>> wrote:
>>> On Apr 2, 1:35 am, Victor Bazarov <> wrote:
>>>> wrote:
>>>>> On Apr 2, 1:10 am, 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
>>>> --

>>
>>> 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:air<int,int> const& p1,
>> std:air<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:air<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
>>
>> V
>> --

>
> Reading further, the definition (a,b) < (c,d) if [a,b] is strictly
> included in [c,d] is not a strict weak ordering. Hence the predicate
> version of sort can't be applied. The reason it's not a strict weak
> ordering is that the relationship of incomparability is non-
> transitive.
> Hence my next question is: are there sorting algorithms in the STL
> that handle partially ordered sets which aren't strictly weakly
> would have thought it was a standard problem.

Into the land of ambiguity I tread once again...

a) STL sorting mechanisms allow for user defined predicates in situations such
as this. This still requires the user to define the desired behaviour.
b) When you say 'standard problem' - partial orderings do arise but the
specifics of the elements being ordered and required levels of nesting (and, I
am sure, other issues) have perhaps prevented generic algorithms from arising.

For purposes of providing examples, look at set and multiset.

Execute:
set< int > bobo
bobo.insert(1);
bobo.insert(2);
bobo.insert(2);
bobo.insert(3);
bobo contains three elements with values 1, 2 and 3.

Execute:
multiset< int > bobo
bobo.insert(1);
bobo.insert(2);
bobo.insert(2);
bobo.insert(3);
bobo contains four elements with values 1, 2, 2 and 3.

Both of these use the strict weak ordering. If a is NOT less than b and b is
NOT less a then a == b. 'set' excludes multiples and 'multiset' allows them.
The generic sorting routines require a predicate that makes this degree of
distinction - it must be unambiguous so that the correct slot may be found.

Given the following sets and the requirements you initially provided:

A = [1, 5]
B = [2, 4]
C = [3, 5]
D = [3, 4]

B, C and D are all <= A
D is <= B and C
B is NOT <= C and C is NOT <= B

so we get:

D <= B ???? C <= A
or
D <= C ???? B <= A

or some such thing.

Defining '????' is specific to the problem at hand. Can you clarify?

Tom

Thomas Wintschel, Apr 2, 2009
9. ### James KanzeGuest

On Apr 2, 1:42 am, wrote:
> On Apr 2, 1:35 am, Victor Bazarov <> wrote:
> > wrote:
> > > On Apr 2, 1:10 am, 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".)

--
James Kanze (GABI Software) email:
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34

James Kanze, Apr 2, 2009

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.

Why not use sort:
http://www.cplusplus.com/reference/algorithm/sort.html
?
Or sort_heap?

(not sure whats difference between two)

11. ### Guest

On Apr 2, 10:46 am, Vladimir Jovic <> wrote:
> 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.

>
> Why not use sort:http://www.cplusplus.com/reference/algorithm/sort.html
> ?
> Or sort_heap?
>
> (not sure whats difference between two)

Can't use sort because it's not a strict weak ordering.

, Apr 2, 2009
12. ### Guest

On Apr 2, 10:10 am, James Kanze <> wrote:
> On Apr 2, 1:42 am, wrote:
>
>
>
> > On Apr 2, 1:35 am, Victor Bazarov <> wrote:
> > > wrote:
> > > > On Apr 2, 1:10 am, 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".)
>
> --
> James Kanze (GABI Software)             email:
> Conseils en informatique orientée objet/
>                    Beratung in objektorientierter Datenverarbeitung
> 9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34

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.

, Apr 2, 2009
13. ### Guest

On Apr 2, 8:33 am, "Thomas Wintschel" <> wrote:
> wrote:
> > On Apr 2, 1:56 am, Victor Bazarov <> wrote:
> >> wrote:
> >>> On Apr 2, 1:35 am, Victor Bazarov <> wrote:
> >>>> wrote:
> >>>>> On Apr 2, 1:10 am, 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
> >>>> --
> >>>> 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:air<int,int> const& p1,
> >> std:air<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:air<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

>
> >> V
> >> --
> >> I do not respond to top-posted replies, please don't ask

>
> > Reading further, the definition (a,b) < (c,d) if [a,b] is strictly
> > included in [c,d] is not a strict weak ordering.  Hence the predicate
> > version of sort can't be applied.  The reason it's not a strict weak
> > ordering is that the relationship of incomparability is non-
> > transitive.
> > Hence my next question is: are there sorting algorithms in the STL
> > that handle partially ordered sets which aren't strictly weakly
> > would have thought it was a standard problem.

>
> Into the land of ambiguity I tread once again...
>
> a) STL sorting mechanisms allow for user defined predicates in situations such
> as this.  This still requires the user to define the desired behaviour.
> b) When you say 'standard problem' - partial orderings do arise but the
> specifics of the elements being ordered and required levels of nesting (and, I
> am sure, other issues) have perhaps prevented generic algorithms from arising.
>
> For purposes of providing examples, look at set and multiset.
>
> Execute:
> set< int > bobo
> bobo.insert(1);
> bobo.insert(2);
> bobo.insert(2);
> bobo.insert(3);
> bobo contains three elements with values 1, 2 and 3.
>
> Execute:
> multiset< int > bobo
> bobo.insert(1);
> bobo.insert(2);
> bobo.insert(2);
> bobo.insert(3);
> bobo contains four elements with values 1, 2, 2 and 3.
>
> Both of these use the strict weak ordering.  If a is NOT less than b and b is
> NOT less a then a == b.  'set' excludes multiples and 'multiset' allows them.
> The generic sorting routines require a predicate that makes this degree of
> distinction - it must be unambiguous so that the correct slot may be found.
>
> Given the following sets and the requirements you initially provided:
>
> A = [1, 5]
> B = [2, 4]
> C = [3, 5]
> D = [3, 4]
>
> B, C and D are all <= A
> D is <= B and C
> B is NOT <= C and C is NOT <= B
>
> so we get:
>
> D <= B ???? C <= A
> or
> D <= C ???? B <= A
>
> or some such thing.
>
> Defining '????' is specific to the problem at hand.  Can you clarify?
>
> Tom

Thanks Tom,

In the example you provide, I would like the result of the sort to be
that B, C, and D are all <= A, D<= B, D <= C
The result of the sort might be that B <= C or it might be that C <=
B (I have no preference either way).
In other words the sort preserves my relationship of <= but possibly
The fact that such a <= exists mathematically speaking is a theorem
known as the order-extension principle.

But this all needs a correction. I should have said at the outset
that the relation is < and it's defined by (a,b) < (c,d) if the
interval (a,b) is strictly contained in (c,d) (it's non-reflexive in
other words).

Any idea how to get such a sort efficiently? Karl-Uwe Bux had the
good suggestion of topological sorting but that's very slow in general
-- order (n^2).

, Apr 2, 2009
14. ### Guest

On Apr 2, 3:13 am, Kai-Uwe Bux <> wrote:
> wrote:
>
> [...]
>
> > Hence my next question is: are there sorting algorithms in the STL
> > that handle partially ordered sets which aren't strictly weakly
> > ordered?

>
> I don't think there is.
>
> > would have thought it was a standard problem.

>
> E.g., a standard problem in this context is topological sorting: embed a
> partially ordered set into a totally ordered set so that the partial order
> is preserved. As far as I know, the standard library has no algorithm for
> that.
>
> Best
>
> Kai-Uwe Bux

Thanks Kai-Uwe. I'm looking for something a bit faster than the
topological sort algorithm which is order n^2.
And please accept my apologies for referring to you as "Karl-Uwe"

, Apr 2, 2009

wrote:
> On Apr 2, 10:46 am, Vladimir Jovic <> wrote:
>> 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.

>> Why not use sort:http://www.cplusplus.com/reference/algorithm/sort.html
>> ?
>> Or sort_heap?
>>
>> (not sure whats difference between two)

>
> Can't use sort because it's not a strict weak ordering.

Why can't you use it with a custom function to compare?

16. ### Guest

On Apr 2, 1:26 pm, Vladimir Jovic <> wrote:
> wrote:
> > On Apr 2, 10:46 am, Vladimir Jovic <> wrote:
> >> 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.
> >> Why not use sort:http://www.cplusplus.com/reference/algorithm/sort.html
> >> ?
> >> Or sort_heap?

>
> >> (not sure whats difference between two)

>
> > Can't use sort because it's not a strict weak ordering.

>
> Why can't you use it with a custom function to compare?

Well, the link you posted stated that compare needs to be a strict
weak ordering. My compare function < (strict set inclusion) is not a
strict weak ordering. As Kai-Uwe pointed out, there is a topological
sort algorithm to create a strict weak ordering from < but that is O
(n^2) and I'm hoping for something faster.

, Apr 2, 2009
17. ### Guest

On 4æœˆ2æ—¥, ä¸‹åˆ6æ™‚50åˆ†, wrote:
> On Apr 2, 10:10Â am, James Kanze <> wrote:
>
>
>
> > On Apr 2, 1:42 am, wrote:

>
> > > On Apr 2, 1:35 am, Victor Bazarov <> wrote:
> > > > wrote:
> > > > > On Apr 2, 1:10 am, 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".)

>
> > --
> > James Kanze (GABI Software) Â  Â  Â  Â  Â  Â  email:
> > Conseils en informatique orientÃ©e objet/
> > Â  Â  Â  Â  Â  Â  Â  Â  Â  Â Beratung in objektorientierter Datenverarbeitung
> > 9 place SÃ©mard, 78210 St.-Cyr-l'Ã‰cole, France, +33 (0)1 30 23 00 34

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

This is formal. Semantics is irrelevant.
(a,b)<=(c,d) ==> !((a,b)>(c,d)) ==> !((c,d)<(a,b))

< is implied by <= if ! is meaningful. Is that correct?

, Apr 2, 2009
18. ### Guest

On Apr 2, 3:20Â pm, wrote:
> On 4æœˆ2æ—¥, ä¸‹åˆ6æ™‚50åˆ†, wrote:
>
>
>
> > On Apr 2, 10:10Â am, James Kanze <> wrote:

>
> > > On Apr 2, 1:42 am, wrote:

>
> > > > On Apr 2, 1:35 am, Victor Bazarov <> wrote:
> > > > > wrote:
> > > > > > On Apr 2, 1:10 am, 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".)

>
> > > --
> > > James Kanze (GABI Software) Â  Â  Â  Â  Â  Â  email:
> > > Conseils en informatique orientÃ©e objet/
> > > Â  Â  Â  Â  Â  Â  Â  Â  Â  Â Beratung in objektorientierter Datenverarbeitung
> > > 9 place SÃ©mard, 78210 St.-Cyr-l'Ã‰cole, France, +33 (0)1 30 23 00 34

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

>
> This is formal. Semantics is irrelevant.
> Â (a,b)<=(c,d) ==> !((a,b)>(c,d)) ==> !((c,d)<(a,b))
>
> < is implied by <= if ! is meaningful. Is that correct?

There are two problems that have been brought up by other posters -- a
shallow problem and a deep problem.
There is a shallow problem (the difference between <= and <) that's
easy to work around.
However, there's a deep problem: Even if you make the trivial change
to use the < form of my predicate, you still don't get a strict weak
ordering.
As Kai-Uwe pointed out, the problem that set inclusion is not a strict
weak ordering is a real obstacle and that's why Kai-Uwe suggested a
topological-sort. However topological-sorting is very slow.

I'm not sure what you mean by "that" when you ask "Is that correct?"
I suspect that if I knew what you meant by "that", my answer would be
"No, that is not correct?"

, Apr 2, 2009
19. ### Carlo MilanesiGuest

ha scritto:
> 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.

You may be interested in this research paper:

--

Carlo Milanesi
http://digilander.libero.it/carlmila

Carlo Milanesi, Apr 2, 2009
20. ### Kai-Uwe BuxGuest

wrote:

> On Apr 2, 3:13 am, Kai-Uwe Bux <> wrote:
>> wrote:
>>
>> [...]
>>
>> > Hence my next question is: are there sorting algorithms in the STL
>> > that handle partially ordered sets which aren't strictly weakly
>> > ordered?

>>
>> I don't think there is.
>>
>> > would have thought it was a standard problem.

>>
>> E.g., a standard problem in this context is topological sorting: embed a
>> partially ordered set into a totally ordered set so that the partial
>> order is preserved. As far as I know, the standard library has no
>> algorithm for that.

[...]
> Thanks Kai-Uwe. I'm looking for something a bit faster than the
> topological sort algorithm which is order n^2.

You are searching for an efficient solution. That is commendable. However,
it would be good if we knew what the problem is. From postings elsethread,
I figured that you want to somehow sort intervals according to inclusion.
But that is an ill-defined problem. What does count as sorted? And _why_ do
you want to sort the intervals? Is it to speed up searching for an interval
containing a given point? In that case, maybe it's easier to solve the
underlying problem. Can you clarify?

Best

Kai-Uwe Bux

Kai-Uwe Bux, Apr 3, 2009