Need help sorting

[Brad Hagen]

I am trying to sort a vector of pointers to Foo, and my code looks something
like this:

vector<Foo*> *pNewVector

sort(pNewVector->begin(),
pNewVector->end(),
Foo::SortFuncti on
);

This was working for a while, but in one case it deadlocks in the sort
function (not Foo::SortFuncti on but somewhere else, in the standard library
code I guess, I don't know). Is it obvious that this won't work in general?
Thanks for any help.
Brad

[Ivan Vecerina]

Re: Need help sorting

Hi Brad,

"Brad Hagen" <100104.2061@co mpuserve.com> wrote in message
news:bj753c$n6d $1@ngspool-d02.news.aol.co m...
....
| sort(pNewVector->begin(),
| pNewVector->end(),
| Foo::SortFuncti on
| );
|
| This was working for a while, but in one case it deadlocks in the sort
| function (not Foo::SortFuncti on but somewhere else, in the standard
library
| code I guess, I don't know). Is it obvious that this won't work in
general?

You should post the body of your sorting function, this is probably where
the problem lies. The function must define a strict ordering, equivalent
to an operator < . In particular, you must never have (a<b) and (b<a).

For example, you should be able to assert:
assert( ! Foo::SortFuncti on(a,b) || ! Foo::SortFuncti on(b,a) );

Some implementations of std::sort may enter a deadlock when this condition
is not met (that is, the function returns true in both cases).


I hope this helps,
Ivan
--
http://www.post1.com/~ivec <> Ivan Vecerina
http://www.brainbench.com <> Brainbench MVP for C++

[Brad Hagen]

Re: Need help sorting

Hi Ivan,

Yes that certainly helped immensely. What I had for the sort function was
this (declared as static):

BOOL Foo::SortFuncti on(Foo*a, Foo *b)
{
return (a->m_iPriority> =b->m_iPriority) ;
};

And this didn't work, doubtless for the reason you mention. So now I have
just this:
return (a->m_iPriority > b->m_iPriority) ;

Which appears to work fine (I wanted descending order).

Thanks a million,
Brad

"Ivan Vecerina" <ivec@myrealbox .com> wrote in message
news:3f5725bc$1 @news.swissonli ne.ch...[color=blue]
> Hi Brad,
>
> "Brad Hagen" <100104.2061@co mpuserve.com> wrote in message
> news:bj753c$n6d $1@ngspool-d02.news.aol.co m...
> ...
> | sort(pNewVector->begin(),
> | pNewVector->end(),
> | Foo::SortFuncti on
> | );
> |
> | This was working for a while, but in one case it deadlocks in the sort
> | function (not Foo::SortFuncti on but somewhere else, in the standard
> library
> | code I guess, I don't know). Is it obvious that this won't work in
> general?
>
> You should post the body of your sorting function, this is probably where
> the problem lies. The function must define a strict ordering, equivalent
> to an operator < . In particular, you must never have (a<b) and (b<a).
>
> For example, you should be able to assert:
> assert( ! Foo::SortFuncti on(a,b) || ! Foo::SortFuncti on(b,a) );
>
> Some implementations of std::sort may enter a deadlock when this condition
> is not met (that is, the function returns true in both cases).
>
>
> I hope this helps,
> Ivan
> --
> http://www.post1.com/~ivec <> Ivan Vecerina
> http://www.brainbench.com <> Brainbench MVP for C++
>
>[/color]

[Stephen Howe]

Re: Need help sorting

> Yes that certainly helped immensely. What I had for the sort function was[color=blue]
> this (declared as static):
>
> BOOL Foo::SortFuncti on(Foo*a, Foo *b)
> {
> return (a->m_iPriority> =b->m_iPriority) ;
> };[/color]

It won't work when you have multiple m_iPriority that are the same value.
Your SortFunction will return true whichever way a, b are passed as
arguments - exactly what Ivan warned you about.
[color=blue]
> return (a->m_iPriority > b->m_iPriority) ;[/color]

Which is better. It return false for the same values which is what "less
than" should do.

Stephen Howe.