戈朗 : Preferred way to tag a struct with aribtrary data

Question

tl;博士 我有一个由节点结构定义的任意有向图。 我现在希望能够提供一种方法来编写遍历此图的函数，并使用特定于该函数的元数据“标记”每个节点。

例如，考虑一个计算节点数的函数:

type Node struct {
    Nexts []*Node
}

func CountNodes(root *Node) int {
    m := make(map[*Node]bool)
    return countNodesHelper(root, m)
}

func countNodesHelper(root *Node, m map[*Node]bool) int {
    _, seen := m[root]
    if seen {
        return 0
    }
    m[root] = true
    c := 1
    for _, child := range root.Nexts {
        c += countNodesHelper(child, m)
    }
    return c
}

func main() {
    n1 := &Node{make([]*Node, 0, 1)}
    n2 := &Node{[]*Node{n1}}
    n1.Nexts = append(n1.Nexts, n2)
    fmt.Println(CountNodes(n1))
}

如果我在结构中添加一个“seen”标签，我可以重写它:

type NodeWithTag struct {
    Nexts []*NodeWithTag
    Seen  bool
}

func CountNodesWithTag(root *NodeWithTag) int {
    if root.Seen {
        return 0
    }
    root.Seen = true
    c := 1
    for _, child := range root.Nexts {
        c += CountNodesWithTag(child)
    }
    return c
}

func main() {
    n1 := &NodeWithTag{make([]*NodeWithTag, 0, 1), false}
    n2 := &NodeWithTag{[]*NodeWithTag{n1}, false}
    n1.Nexts = append(n1.Nexts, n2)
    fmt.Println(CountNodesWithTag(n1))
}

但 Seen 标签还不够，比如说，我还想找到向后边的树上的 DFS(你需要数到 2 -- 从未见过，见过，沿着单个树第二次见过小路)。所以，我想要一些方法来允许函数的实现使用它自己的类型来标记结构。大致相当于:

type Node struct {
  ...
  // Not valid golang
  void* tag
}

但比 void* 更安全——函数应该能够静态验证标签是否是它期望的当前类型。有没有办法做到这一点/替代方法。

我想将标签与节点相关联(而不是标签的单独映射/存储)的原因是允许使用此类标签的函数轻松并行化，将节点分配给不同的 goroutines。在第一种方法中， map 必须在 goroutine 之间共享，这很快就会成为瓶颈，因为它需要同步访问。

Answer 1

如果你需要支持任意数据类型，你需要使用一个空接口(interface):

type NodeWithTag struct {
    Nexts []*NodeWithTag
    Tag   interface{}
}

您可以为 Tag 字段分配任何值。如果你想验证值是某种类型，比如 MyType，你可以使用类型断言:

myVal, ok := node.Tag.(MyType)

如果值属于该类型，ok 将为真，myVal 将包含键入的值。