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

Hi all,

It seems that std::sort() is using algorithm like quick sort to do the
comparison, that means, the items to be sorted are not pair-wisely
compared. Thus, if the binary predicate is NOT transitive, then the
std::sort() may not work well.

For example, I have a list of nodes, each node has a list of node
references to its immediate children. I want to sort the list so that a
child must appear before its parent.

Since in my data structure, I only know the immediate children of each
node, thus my predicate can only tell whether node1 is an immediate
child of node2.
    bool IsChild(const Node& n1, const Node& n2)
    {
        return std::find(n2.children.begin(), n2.children.end(), &n1) !=
               n2.children.end();
    }

    std::sort(nodes.begin(), nodes.end(), IsChild);

Its possible that node1 is child of node2, node2 is child of node3, so
the expected sorting result should be: {node1, node2, node3}. However,
if it happens that std::sort() calls IsChild() to compare node1 and
node3, it cannot find immediate relationship thus returns "not a child",
and that lead to wrong sorting result. Some prototyped testing proved
such wrong result.

I'm thinking about this problem but I could not find an easy solution
with minimal change on the Node data structure. Does anyone have any
idea about how to solve this problem? Any suggestions are greatly
appreciated!