Go – 递归结构体与数组丢失值

huangapple go评论82阅读模式
英文:

Go - recursive struct with array and losing values

问题

我创建了一个Element结构体,它有一个父节点和子节点,创建了一个名为SubElement的辅助函数,以及一个String方法,用于遍历所有子节点进行打印:

package main

import "fmt"

type Element struct {
  parent *Element
  children []Element
  tag string
}

func SubElement(parent *Element, tag string) Element {
  el := Element{}
  el.parent = parent
  el.tag = tag
  parent.children = append(parent.children, el)
  return el
}

func (el Element) String() string {
  s := "<" + el.tag + ">"
  for _, child := range el.children {
    s += child.String()
  }
  s += "</" + el.tag + ">"
  return s
}

func main() {
  root := Element{}
  root.tag = "root"
  
  a := SubElement(&root, "a")
  b := SubElement(&a, "b")
  SubElement(&b, "c")
  
  fmt.Println(root) // 打印结果: <root><a></a></root>
  fmt.Println(a) // 打印结果: <a><b></b></a>
  // 以此类推
}

我遇到的问题是,我选择打印的根节点只能获取到第一层子节点。我确定这与在parent.children上使用append有关,但我不知道如何正确解决这个问题。

为了解决这个问题,我将children更改为map[int]Element。然后在我的SubElement函数中,我使用parent.children[len(parent.children)] = el来“添加”。然后为了按正确的顺序进行迭代,String方法的for循环是for i:= 0; i < len(el.children); i++,访问el.children[i]

不过,我仍然想知道如何使用数组来正确解决这个问题。谢谢。

英文:

I created an Element struct that has a parent and children, created a helper func called SubElement, and a String method that iterates through all children for print:

package main

import &quot;fmt&quot;

type Element struct {
  parent *Element
  children []Element
  tag string
}

func SubElement(parent *Element, tag string) Element {
  el := Element{}
  el.parent = parent
  el.tag = tag
  parent.children = append(parent.children, el)
  return el
}

func (el Element) String() string {
  s := &quot;&lt;&quot; + el.tag + &quot;&gt;&quot;
  for _, child := range el.children {
    s += child.String()
  }
  s += &quot;&lt;/&quot; + el.tag + &quot;&gt;&quot;
  return s
}

func main() {
  root := Element{}
  root.tag = &quot;root&quot;
  
  a := SubElement(&amp;root, &quot;a&quot;)
  b := SubElement(&amp;a, &quot;b&quot;)
  SubElement(&amp;b, &quot;c&quot;)
  
  fmt.Println(root) // prints: &lt;root&gt;&lt;a&gt;&lt;/a&gt;&lt;/root&gt;
  fmt.Println(a) // prints: &lt;a&gt;&lt;b&gt;&lt;/b&gt;&lt;/a&gt;
  // and so on
}

The problem I'm experiencing is, only the first tier of children are available from the root node I choose to print. I'm sure it's related to the use of append on parent.children, but lack the understanding of how to resolve this correctly.

To work around the issue, I changed children to map[int]Element. Then in my SubElement func, I "append" with parent.children[len(parent.children)] = el. Then to iterate in the correct order, the String method for-loop is for i:= 0; i &lt; len(el.children); i++, accessing el.children[i].

Still, I'd like to know how to do this correctly with an array. Thanks

答案1

得分: 5

解释为什么 []Element 版本不起作用。

结构体是按值复制的。在 SubElement 中,你创建了一个 Element 结构体,然后当你追加它时,实际上是追加了一个完整的结构体副本。当你将 el 返回并赋值给 a 时,又进行了一次复制。a 的地址不是追加的 Element 的地址。

所以,你可以巧妙地获取实际在切片中的元素的地址,这在测试用例中可能看起来像是起作用了,但是在将其存储回 Element.parent 中时,会出现一个问题,即后续的追加可能会重新分配切片,现在你保留的指针指向的是一些被废弃的内存,而不是当前有效的切片。

如果 []*Element 版本解决了其他问题,那么它们很可能是存储了随后被废弃的指针的问题。

可以使用结构体切片来实现树,但是需要清楚地理解,保留指向切片的指针通常是一个错误。由于存储父指针是不安全的,最好将其从结构体中删除。

package main

import "fmt"

func main() {
    tree := Element{tag: "head"}
    tree.SubElement("tier-1")
    tree.children[0].SubElement("tier-2")
    tree.children[0].SubElement("tier-2")
    tree.SubElement("tier-1")
    tree.children[1].SubElement("tier-2")
    fmt.Println(tree)
}

type Element struct {
    children []Element
    tag      string
}

func (parent *Element) SubElement(tag string) {
    parent.children = append(parent.children, Element{tag: tag})
}

func (el Element) String() string {
    s := "<" + el.tag + ">"
    for _, child := range el.children {
        s += child.String()
    }
    s += "</" + el.tag + ">"
    return s
}

至少这段代码是可以工作的;但是如果你有其他使用指针的代码,或者使用了父指针的代码,那么就需要重新思考了。

英文:

An answer to explain why the []Element version didn't work.

Structs are copied as values. In SubElement, you create one Element struct, then when you append it, that actually appends a whole new copy of the struct. When you return el and assign it to a, that makes yet another copy. The address of a is not the address of the Element that was appended.

So, you could get tricky and take the address of the element that's actually in the slice, and that might even look like it's working in a test case, but there's a problem with retaining one these pointers such as you do when you store it back in Element.parent. The problem is that a subsequent append can reallocate the slice, and now your retained pointer points into some orphaned memory rather than the currently valid slice.

If the []*Element version solved some other issues, it's likely that they were issues of storing pointers that were subseqently orphaned.

It is possible to implement a tree with slices of structs, but it takes a clear understanding that retaining pointers into slices is usually a mistake. Since storing the parent pointer is not safe, it's best to just remove it from the struct.

package main

import &quot;fmt&quot;

func main() {
    tree := Element{tag: &quot;head&quot;}
    tree.SubElement(&quot;tier-1&quot;)
    tree.children[0].SubElement(&quot;tier-2&quot;)
    tree.children[0].SubElement(&quot;tier-2&quot;)
    tree.SubElement(&quot;tier-1&quot;)
    tree.children[1].SubElement(&quot;tier-2&quot;)
    fmt.Println(tree)
}

type Element struct {
    children []Element
    tag      string
}

func (parent *Element) SubElement(tag string) {
    parent.children = append(parent.children, Element{tag: tag})
}

func (el Element) String() string {
    s := &quot;&lt;&quot; + el.tag + &quot;&gt;&quot;
    for _, child := range el.children {
        s += child.String()
    }
    s += &quot;&lt;/&quot; + el.tag + &quot;&gt;&quot;
    return s
}

This code, at least, works; but if you had other code that was working with pointers, or that used the parent pointer, it would have to be rethought.

答案2

得分: 2

第一个线索是,SubElement在你的代码中无法编译通过(编辑:原本是这样的)。你可以尝试让它工作,但我建议你将Element.children更改为[]*Element而不是[]Element。这是一个可工作的示例:

package main

import "fmt"

func main() {
    tree := &Element{tag: "head"}
    t1 := SubElement(tree, "tier-1")
    SubElement(t1, "tier-2")
    SubElement(t1, "tier-2")
    t1 = SubElement(tree, "tier-1")
    SubElement(t1, "tier-2")
    fmt.Println(tree)
}

type Element struct {
    parent   *Element
    children []*Element
    tag      string
}

func SubElement(parent *Element, tag string) *Element {
    el := &Element{parent: parent, tag: tag}
    parent.children = append(parent.children, el)
    return el
}

func (el *Element) String() string {
    s := "<" + el.tag + ">"
    for _, child := range el.children {
        s += child.String()
    }
    s += "</" + el.tag + ">"
    return s
}

输出:

<head><tier-1><tier-2></tier-2><tier-2></tier-2></tier-1><tier-1><tier-2></tier-2></tier-1></head>
英文:

The first clue is that SubElement doesn't compile as you have it (edit: had it) there (originally.) You could experiment with making it work, but I recommend you change the Element.children to be []*Element rather than []Element. Here's a working example:

package main

import &quot;fmt&quot;

func main() {
    tree := &amp;Element{tag: &quot;head&quot;}
    t1 := SubElement(tree, &quot;tier-1&quot;)
    SubElement(t1, &quot;tier-2&quot;)
    SubElement(t1, &quot;tier-2&quot;)
    t1 = SubElement(tree, &quot;tier-1&quot;)
    SubElement(t1, &quot;tier-2&quot;)
    fmt.Println(tree)
}

type Element struct {
    parent   *Element
    children []*Element
    tag      string
}

func SubElement(parent *Element, tag string) *Element {
    el := &amp;Element{parent: parent, tag: tag}
    parent.children = append(parent.children, el)
    return el
}

func (el *Element) String() string {
    s := &quot;&lt;&quot; + el.tag + &quot;&gt;&quot;
    for _, child := range el.children {
        s += child.String()
    }
    s += &quot;&lt;/&quot; + el.tag + &quot;&gt;&quot;
    return s
}

Output:

&lt;head&gt;&lt;tier-1&gt;&lt;tier-2&gt;&lt;/tier-2&gt;&lt;tier-2&gt;&lt;/tier-2&gt;&lt;/tier-1&gt;&lt;tier-1&gt;&lt;tier-2&gt;&lt;/tier-2&gt;&lt;/tier-1&gt;&lt;/head&gt;

huangapple
  • 本文由 发表于 2012年4月26日 05:01:16
  • 转载请务必保留本文链接:https://go.coder-hub.com/10323731.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定