如何在构建链表时保持对最后一个节点的可变引用? [英] How do I keep a mutable reference to the last node while building a linked list?

问题描述

我正在尝试从 Iterator 构建一个单链表，保持元素的顺序.

I'm trying to implement building a singly-linked list from an Iterator, keeping the order of elements.

结构定义为:

#[derive(Debug)]
struct List<T> {
    list: Node<T>,
}

type Node<T> = Option<Box<Link<T>>>;

#[derive(Debug)]
struct Link<T> {
    head: T,
    tail: Node<T>,
}

我想保持对列表末尾的可变引用并在迭代时扩展它.但是，我无法弄清楚如何做到这一点.(非工作)想法是:

I was thinking of keeping a mutable reference to the end of the list and expanding it while iterating. However, I couldn't figure out how this could be done. The (non-working) idea was:

impl<T> List<T> {
    pub fn from_iterator(i: &mut Iterator<Item = T>) -> Self {
        let mut list = List { list: None };
        {
            let mut last: &mut Node<T> = &mut list.list;
            for x in i {
                let singleton = Box::new(Link {
                    head: x,
                    tail: None,
                });
                *last = Some(singleton);
                // --> I aim for something like the line below. Of course
                // 'singleton' can't be accessed at this point, but even if I
                // match on *last to retrieve it, still I couldn't figure out how
                // to properly reference the new tail.
                // last = &mut singleton.tail;
            }
        }
        list
    }
}

可以只反向构建列表，然后以相同的时间复杂度将其反向，但我很好奇上述方法在 Rust 中是否可行.

It'd be possible to just build the list in reverse and then reverse it afterwards with the same time complexity, but I was curious if the above approach is ever possible in Rust.

推荐答案

如在迭代递归结构时无法获得可变引用中所述: 一次不能多次借用可变引用，您可以使用 {} 显式转移可变引用的所有权:

As described in Cannot obtain a mutable reference when iterating a recursive structure: cannot borrow as mutable more than once at a time, you can explicitly transfer ownership of the mutable reference using {}:

impl<T> List<T> {
    pub fn from_iterator<I>(i: I) -> Self
    where
        I: IntoIterator<Item = T>,
    {
        let mut list = List { list: None };
        {
            let mut last: &mut Node<T> = &mut list.list;

            for x in i {
                let singleton = Box::new(Link {
                    head: x,
                    tail: None,
                });
                *last = Some(singleton);

                last = &mut {last}.as_mut().unwrap().tail;
            }
        }
        list
    }
}

我还删除了 trait 对象(&mut Iterator)以支持泛型.这允许更优化的代码(尽管使用链表可能不值得).

I also removed the trait object (&mut Iterator) in favor of a generic. This allows for more optimized code (although with a linked list it's probably not worth it).

不幸的是需要 unwrap.即使 Link 放在堆上，使地址稳定，编译器也不会执行该级别的生命周期跟踪.基于这种外部知识，可以使用 unsafe 代码，但我不知道在这里是否值得.

It's unfortunate that the unwrap is needed. Even though the Link is placed on the heap, making the address stable, the compiler does not perform that level of lifetime tracking. One could use unsafe code based on this external knowledge, but I don't know that it's worth it here.

这篇关于如何在构建链表时保持对最后一个节点的可变引用?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！