我正在尝试创建一个简单的简单链表类型类，其中我有一个指向下一个节点的指针，但遇到了一些问题。 这样做的正确方法是什么？
我现在拥有的是：
trait Base {
fn connect<'a, 'b>(&'a self, next: &'b Base);
}
struct MyStruct<'b> {
next: Option<&'b Base>, // This should be swapped out with a reference to Base for the next node
}
impl<a', b'> Base for MyStruct<'b> {
pub fn new() -> MyStruct<'b'> {
MyStruct { next: None, }
}
pub fn connect<'a, 'b>(&'a self, layer: &'b Base) {
self.next = Some(layer);
}
}
我想象连接的struct / node的生命周期的方式应该与初始节点相同（即当我解除分配列表时应该完全这样做）所以它应该有一个生命周期。 但是，我相信当连接函数中存在自指针时，这会导致问题。
I'm trying to make a simple simple linked list type class where I have a pointer to the next node, but am running into some issues. What would be the proper way to do this?
What I currently have is this:
trait Base {
fn connect<'a, 'b>(&'a self, next: &'b Base);
}
struct MyStruct<'b> {
next: Option<&'b Base>, // This should be swapped out with a reference to Base for the next node
}
impl<a', b'> Base for MyStruct<'b> {
pub fn new() -> MyStruct<'b'> {
MyStruct { next: None, }
}
pub fn connect<'a, 'b>(&'a self, layer: &'b Base) {
self.next = Some(layer);
}
}
The way I picture this the lifetime for the struct/node that is connected should be the should be the same as the initial node (i.e. when I deallocate a list it should do so entirely) so it should have one lifetime. However, I believe this causes issues when there is a self pointer as in the connect function.
最满意答案
你说
我有一个指向下一个节点的指针
你的代码显示了一个引用，而不是一个指针，所以我认为你的意思是一个引用。 但你也说
当我解除分配列表时，它应该完全这样做
这两个概念是不相容的 。 唯一可以删除项目的是拥有该项目的东西。 这是通过放弃所有权而没有其他任何东西来完成的。 有了参考，你没有任何东西，你只是借用它。
现在，您可以拥有指向下一个项目的指针 。 那是一个Box ，代表一个堆分配的项目。 然后没有生命需要发挥作用，并在这个答案中涵盖。
这种类型的列表是通用的，因此您可以存储像String这样的拥有项，或者像&u32这样的引用。 删除列表或列表节点时，也会删除String 。 技术上删除了引用，但删除引用不会丢弃引用项。
创建仅包含对下一个节点的引用的链接列表是......至少可以说是棘手的，并且可能没用。
您的Node看起来像这样：
struct Node<'a> {
next: Option<&'a mut Node<'a>>,
}
您必须自己声明并分配每个Node ，因为无处可以从假设的“添加”方法中将Node存储在堆栈中。
对于下一个节点的引用和下一个节点的生命周期，您总是会遇到重叠生命周期的问题（对列表应用归纳并且它变得非常复杂。）
TL; DR目前尚不清楚为什么要这样做，但基本上它并不容易（或者我认为值得）。
You say
I have a pointer to the next node
your code shows a reference, not a pointer, so I take it you mean a reference. But you also say
when I deallocate a list it should do so entirely
These two concepts are incompatible. The only thing that can drop an item is the thing that owns the item. This is done by giving up ownership and nothing else taking the ownership. With a reference, you do not own anything, you are simply borrowing it.
Now, you could have an owned pointer to the next item. That's a Box, which represents a heap-allocated item. Then no lifetimes need to come into play, and is covered in this answer.
This type of list would be generic, so you could store an owned item like a String, or a reference to something like a &u32. When the list or list node is dropped, then the String would be dropped too. The references are technically dropped, but dropping a reference does not drop the referred-to item.
Creating a linked list with only references to the next node is... tricky to say the least, and probably not useful.
Your Node would look something like this:
struct Node<'a> {
next: Option<&'a mut Node<'a>>,
}
You'd have to declare and allocate each and every Node yourself, since there'd be nowhere you could store the Node on the stack from inside a hypothetical "add" method.
You are always going to run into an issue with overlapping lifetimes for the reference to the next node and the lifetime that the next node has (apply induction for a list and it gets really complicated.)
TL;DR It's not clear why want to do this, but basically it's not easy to do (or worth it, in my opinion).
更多推荐
发布评论