Re: How to use std::sort() when my binary predicate is NOT transitive?



Chen Zhuo wrote:
Yes if I make IsChild() function recursive, then the problem will be
solved. However, that would require much code work, and need to handle
special cases like circular dependencies (node1 -> node2 -> node3 ->
node1), thus error-prone.

Ahem, if your design allows circular dependencies, you can't sort this
anyway.

Also, consider the case of two child-nodes. If you can't iterate from the
child to the parent (e.g. via a pointer), there is no way to say if they
are from the same parent or different parents and so you also can't tell
which way they are supposed to be sorted.

I suggest you try to write down in plain English by what criteria your nodes
are supposed to be sorted, we can then try to figure out a suitable
predicate.

Lastly, I noticed something in the code you gave: you are storing nodes by
element in the container and pointers in the nodes themselves. This is
fragile, I hope you are aware of that. In particular the fact that nodes
are copyable (i.e. value semantics, as required by the containers and the
sorting algorithm) will make it difficult to keep those pointers correct.

Maybe I could suggest something else if I knew what you are trying to do.

cheers

Uli


.