linked-list - 没有 malloc 的 no_std 中的无堆链表

Question

我对无堆链表的尝试缺少什么？

我的目标是让下面的代码在堆栈上生成序列 [1, 2, 3]，然后在单独的行上打印这些值 ，而不使用 Box 或其他任何东西需要堆或 std 或 malloc。

我浏览了 https://rust-unofficial.github.io/too-many-lists但所有“好”列表似乎都依赖于 Rc、Box 等。

heapless crate很简洁，但需要事先知道列表的大小。

我的 Google 功能不够强大，无法找到太多帮助。任何指针将不胜感激。但这就是我的想法:

struct Node<'a, T> {
    value: T,
    next: Option<&'a Node<'a, T>>
}

struct List<'a, T> {
    head: Option<&'a Node<'a, T>>,
    tail: Option<&'a Node<'a, T>>
}

impl<'a, T> List<'a, T> {
    fn new() -> Self {
        Self {
            head: None,
            tail: None
        }
    }

    fn push(self, value: T) ->Self {
        unimplemented!(); // What's missing here?
    }
}

struct Iter<'a, T> {
    next: Option<&'a Node<'a, T>>
}

impl<'a, T> Iterator for Iter<'a, T> {
    type Item = &'a T;

    fn next(&mut self) -> Option<&'a T> {
        match self.next.take() {
            Some(next) => {
                self.next = next.next;
                Some(&next.value)
            },
            None => None
        }
    }
}

impl<'a, T> IntoIterator for List<'a, T> {
    type Item = &'a T;
    type IntoIter = Iter<'a, T>;

    fn into_iter(self) -> Self::IntoIter {
        Iter {
            next: self.head
        }
    }
}

fn main() {
    let list = List::new();
    let list = list.push(1);
    let list = list.push(2);
    let list = list.push(3);
    for item in list {
        println!("{}", item);
    }
}

如您所见，我一直在尝试实现 List.push。

Answer 1

在不知道大小(或至少是大小的上限)的情况下在堆栈上分配东西是对圆进行平方，并且不会起作用。您可以让编译器为您确定大小，但仅此而已。原因很简单:堆栈分配可能不会失败，编译器必须确保一切都适合。

如果您想继续并坚持使用 push(T) 签名，只需取一个值 Matt Thomas 的答案就是可行的方法。

这是我对这个问题的看法，它避免了构建嵌套类型:

struct Node<'a, T> {
    value: T,
    next: Option<&'a Node<'a, T>>,
}

impl<'a, T> Node<'a, T> {
    pub fn new(value: T, next: Option<&'a Self>) -> Self {
        Node { value, next }
    }

    pub fn iter(&'a self) -> Iter<'a, T> {
        Iter {
            current: Some(self),
        }
    }
}

struct Iter<'a, T> {
    current: Option<&'a Node<'a, T>>,
}

impl<'a, T> Iterator for Iter<'a, T> {
    type Item = &'a T;
    fn next(&mut self) -> Option<&'a T> {
        match self.current {
            Some(Node { value, next }) => {
                self.current = *next;
                Some(value)
            }
            None => None,
        }
    }
}

fn main() {
    // Allocation of the Nodes directly on the stack,
    // not inside a push method. <= Solves lifetime issues
    // Reversed order solves mutability issues.
    let three = Node::new(3, None);
    let two = Node::new(2, Some(&three));
    let one = Node::new(1, Some(&two));

    for item in one.iter() {
        println!("{}", item)
    }
}