英文:
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 "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) // prints: <root><a></a></root>
fmt.Println(a) // prints: <a><b></b></a>
// 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 < 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 "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
}
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 "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
}
Output:
<head><tier-1><tier-2></tier-2><tier-2></tier-2></tier-1><tier-1><tier-2></tier-2></tier-1></head>
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论