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::SortFunction
);

This was working for a while, but in one case it deadlocks in the sort
function (not Foo::SortFunction 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]

Hi Brad,

....
| sort(pNewVector->begin(),
| pNewVector->end(),
| Foo::SortFunction
| );
|
| This was working for a while, but in one case it deadlocks in the sort
| function (not Foo::SortFunction 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::SortFunction(a,b) || ! Foo::SortFunction(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

 

[Brad Hagen]

Hi Ivan,

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

BOOL Foo::SortFunction(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

 

[Stephen Howe]

Yes that certainly helped immensely. What I had for the sort function was

this (declared as static):

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

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.

return (a->m_iPriority > b->m_iPriority);

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

Stephen Howe.