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


.



Relevant Pages

  • Re: parent pointers in AST nodes
    ... Is it common / useful to supply a pointer to the node's parent as ... * This can simplify some AST processing tasks, ... You can easily pass down a chain of parent link pointers during ... the visitor pattern pops out of a simple ...
    (comp.compilers)
  • Re: hacker challenge - traverse a list
    ... came from (a link to your parent) in the node. ... Fortunately the link holding the address of the child you are going to ... you can do a clever trick with moving pointers around that implicitly ... could do the trick, but again one needs to remember the "state" (number ...
    (comp.programming)
  • Re: parent pointers in AST nodes
    ... Is it common / useful to supply a pointer to the node's parent as ... I find the visitor pattern non-intuitive for AST processing. ... over the node type and calls recursively on children nodes is much more ... list of parent pointers). ...
    (comp.compilers)
  • Re: reiser4 plugins
    ... > parent pointers starting from A. If you ever reach B, ... /nothing/ can touch the filesystem to do any change... ... And that means walking down to /each/ ...
    (Linux-Kernel)
  • Re: parent pointers in AST nodes
    ... One compiler that keeps parent pointers in the tree is GNAT ... Wastes space ...
    (comp.compilers)