为什么这个链表中不需要显式引用？

Question

在这个可变链表实现中，没有Ref{ListNode{T}}：

mutable struct ListNode{T}
    data::T
    prev::ListNode{T}
    next::ListNode{T}
end

要编辑列表，它使用类似 的代码next.prev = prev。

我通常的理解是结构体被嵌入到位（就像 C 中的那样）。这不允许在不完全重新创建列表的情况下编辑列表。要拥有指向结构的引用/指针，可以使用Ref{ListNode{T}}.

从代码来看，这种理解显然是错误的：prev::ListNode{T}已经是一个可以轻易改变的指针了。但我不明白为什么会这样。Julia 中的结构默认嵌入为指针吗？可能只有它们是可变的？

我在文档中找不到该行为的具体描述。它讨论了堆/堆栈分配，但没有讨论直接分配与指针分配的更基本问题。

Answer 1

TL;DR：Julia 中的不可变结构像 C 中一样是“嵌入”的。mutable struct在内部进行堆分配并存储为指针。需要自引用初始化来避免不完整的初始化问题，并且您必须检查循环引用，而不是像在 C 中那样检查空指针。

\n

structJulia 中的 s 通常类似于 C 结构，即如您所描述的那样嵌入到位。此类类型在 Julia 中称为isbitstypes。当在函数内部时，此类类型的构造函数会导致“在堆栈上分配”，即类似于 C 中的结构。

\n

help?> isbitstype\nsearch: isbitstype\n\n  isbitstype(T)\n\n  Return true if type T is a "plain data" type, meaning it is immutable\n  and contains no references to other values, only primitive types and\n  other isbitstype types. Typical examples are numeric types such as\n  UInt8, Float64, and Complex{Float64}. This category of types is\n  significant since they are valid as type parameters, may not track\n  isdefined / isassigned status, and have a defined layout that is\n  compatible with C.\n\n  See also isbits, isprimitivetype, ismutable.\n\n  Examples\n  \xe2\x89\xa1\xe2\x89\xa1\xe2\x89\xa1\xe2\x89\xa1\xe2\x89\xa1\xe2\x89\xa1\xe2\x89\xa1\xe2\x89\xa1\xe2\x89\xa1\xe2\x89\xa1\n\n  julia> isbitstype(Complex{Float64})\n  true\n\n  julia> isbitstype(Complex)\n  false\n

\n

另一方面，可变结构是堆分配的。来自手册的复合类型部分。

\n

\n

为了支持突变，此类对象通常分配在堆上，并具有稳定的内存地址。可变对象就像一个小容器，随着时间的推移可能会保存不同的值，因此只能通过其地址来可靠地识别。相反，不可变类型的实例与特定字段值 \xe2\x80\x93 相关联 - 字段值本身就可以告诉您有关该对象的所有信息。在决定是否使类型可变时，请询问具有相同字段值的两个实例是否会被视为相同，或者它们是否可能需要随着时间的推移而独立更改。如果它们被认为是相同的，那么类型可能应该是不可变的。

\n

\n

因此，对它们进行堆分配的主要原因是，在最常见的情况下，即使结构成员的类型也可以更改，如示例所示。

\n

julia> mutable struct Bar\n           baz\n           qux::Float64\n       end\n\njulia> bar = Bar("Hello", 1.5);\n\njulia> bar.qux = 2.0\n2.0\n\njulia> bar.baz = 1//2\n1//2\n

\n

来到您定义的结构：

\n

julia> isbitstype(ListNode{Int64})\nfalse\n\njulia> sizeof(ListNode{Int64}) # 8 + 2*8 = 24 bytes\n24\n\njulia> sizeof(ListNode{Tuple{Int64,Int64}})  # 2*8 + 2*8 = 32 bytes\n32\n

\n

这是否意味着默认ListNode{T}构造函数在内部使用指针/引用？是的，但是值语义不允许您使用这些内部引用作为链接列表的指针。您不能只将空指针分配给它们。

\n

julia> ListNode{Int}(1, Ptr{ListNode{Int}}(), Ptr{ListNode{Int}}())\nERROR: MethodError: Cannot `convert` an object of type Ptr{ListNode{Int64}} to an object of type ListNode{Int64}\nClosest candidates are:\n  convert(::Type{T}, ::T) where T at Base.jl:61\n  ListNode{T}(::Any, ::Any, ::Any) where T at REPL[1]:2\nStacktrace:\n [1] ListNode{Int64}(data::Int64, prev::Ptr{ListNode{Int64}}, next::Ptr{ListNode{Int64}})\n   @ Main ./REPL[1]:2\n [2] top-level scope\n   @ REPL[26]:1\n

\n

在您的特定情况下，您将遇到不完整的初始化问题\n文档中有一个关于此问题的部分（不完整的初始化）。Julia 允许您new使用更少的值调用内部构造函数，以使递归成员保持未初始化。

\n

mutable struct ListNode{T}\n    data::T\n    prev::ListNode{T}\n    next::ListNode{T}\n    \n    # inner constructor\n    ListNode(data::T) where T = new{T}(data)\nend\n

\n

julia> head = ListNode(1)\nListNode{Int64}(1, #undef, #undef)\n\njulia> head.next = ListNode(2)\nListNode{Int64}(2, #undef, #undef)\n\njulia> head\nListNode{Int64}(1, #undef, ListNode{Int64}(2, #undef, #undef))\n

\n

所以，回答你的问题：

\n

\n

Julia 中的结构默认嵌入为指针吗？可能只有它们是可变的？

\n

\n

是的，只有当它们是可变的时，它们才会作为指针嵌入。尽管如此，您确实不应该使用此细节来将链表节点的指针组合在一起。

\n

julia> head.next.next === undef\nERROR: UndefRefError: access to undefined reference\nStacktrace:\n [1] getproperty(x::ListNode{Int64}, f::Symbol)\n   @ Base ./Base.jl:38\n [2] top-level scope\n   @ REPL[11]:1\n\njulia> typeof(head.prev)\nERROR: UndefRefError: access to undefined reference\nStacktrace:\n [1] getproperty(x::ListNode{Int64}, f::Symbol)\n   @ Base ./Base.jl:38\n [2] top-level scope\n   @ REPL[8]:1\n

\n

访问未定义的字段会尝试直接取消引用这些指针，因此您无法像在 C 中那样真正检查空指针。要么使用Refand Friends，要么您可以通过使用循环引用完全初始化而不是返回未完全初始化的对象来使此特定结构正常工作。

\n

mutable struct ListNode{T}\n    data::T\n    prev::ListNode{T}\n    next::ListNode{T}\n\n   ListNode(data::T) where T = (n = new{T}(data); n.prev = n; n.next=n)\nend\n\nistail(l::ListNode{T}) where T = l === l.next\n

\n

julia> head = ListNode(1)\nListNode{Int64}(1, ListNode{Int64}(#= circular reference @-1 =#), ListNode{Int64}(#= circular reference @-1 =#))\n\njulia> head.next = ListNode(2)\nListNode{Int64}(2, ListNode{Int64}(#= circular reference @-1 =#), ListNode{Int64}(#= circular reference @-1 =#))\n\njulia> head.next.next = ListNode(3)\nListNode{Int64}(3, ListNode{Int64}(#= circular reference @-1 =#), ListNode{Int64}(#= circular reference @-1 =#))\n\njulia> istail(head.next.next)\ntrue\n\njulia> istail(head.next)\nfalse\n

\n

事实证明，DataStructures.MutableLinkedList正是这样做的。如果您查看他们的迭代接口的实现（允许您for x in list为您的类型编写），就会发现终止条件是通过检查循环引用来实现的。

\n

Base.iterate(l::MutableLinkedList, n::ListNode) = n === l.node ? nothing : (n.data, n.next)\n

\n