为二叉树实现IntoIterator [英] Implement IntoIterator for binary tree

问题描述

我正在尝试构建一个二叉树并编写一个迭代器以遍历树中的值. 在为我的树节点实现IntoIterator特性时，我遇到了生存期问题

I am trying to build a binary tree and write an iterator to traverse values in the tree. When implementing the IntoIterator trait for my tree nodes I ran into a problem with lifetimes

src\main.rs:43:6: 43:8 error: the lifetime parameter `'a` is not constrained by the impl trait, self type, or predicates [E0207]
src\main.rs:43 impl<'a, T: 'a> IntoIterator for Node<T> {

我知道我需要指定NodeIterator的生存时间与Node一样长，但是我不确定如何表达

I understand that I need to specify that NodeIterator will live as long as Node but I am unsure of how to express that

use std::cmp::PartialOrd;
use std::boxed::Box;

struct Node<T: PartialOrd> {
    value: T,
    left: Option<Box<Node<T>>>,
    right: Option<Box<Node<T>>>,
}

struct NodeIterator<'a, T: 'a + PartialOrd> {
    current: &'a Node<T>,
    parent: Option<&'a Node<T>>,
}

impl<T: PartialOrd> Node<T> {
    pub fn insert(&mut self, value: T) {
        ...
    }
}

impl<'a, T: 'a> IntoIterator for Node<T> { // line 43
     type Item = T;
     type IntoIter = NodeIterator<'a, T>;

     fn into_iter(&self) -> Self::IntoIter {
         NodeIterator::<'a> {
             current: Some(&self),
             parent: None
         }
     }
 }

推荐答案

您遇到的特定错误是'a应该出现在for的右侧.否则，编译器如何知道a是什么?

The particular error that you are getting is that 'a should appear on the right of for. Otherwise, how could the compiler know what a is?

在实现IntoIterator时，您必须决定迭代器是否会使用容器，或者是否只是在容器中产生引用.目前，您的设置不一致，并且错误消息指出了这一点.

When implementing IntoIterator you have to decide whether the iterator will consume the container, or whether it'll just produce references into it. At the moment, your setup is inconsistent, and the error message points it out.

对于二叉树，您还必须考虑要按哪个顺序生成值:传统顺序是深度优先(产生排序的序列)和宽度优先(暴露树的层") ).我将首先假定深度，因为它是最常见的深度.

In the case of a binary tree, you also have to think about which order you want to produce the values in: traditional orders are depth first (yielding a sorted sequence) and breadth first (exposing the "layers" of the tree). I'll assume depth first as it's the most common one.

让我们首先解决一个消耗迭代器的情况.从某种意义上讲，我们不必担心生命周期，这很简单.

Let's tackle the case of a consuming iterator first. It's simpler in the sense that we don't have to worry about lifetimes.

#![feature(box_patterns)]

struct Node<T: PartialOrd> {
    value: T,
    left: Option<Box<Node<T>>>,
    right: Option<Box<Node<T>>>,
}

struct NodeIterator<T: PartialOrd> {
    stack: Vec<Node<T>>,
    next: Option<T>,
}

impl<T: PartialOrd> IntoIterator for Node<T> {
    type Item = T;
    type IntoIter = NodeIterator<T>;

    fn into_iter(self) -> Self::IntoIter {
        let mut stack = Vec::new();

        let smallest = pop_smallest(self, &mut stack);

        NodeIterator { stack: stack, next: Some(smallest) }
    }
}

impl<T: PartialOrd> Iterator for NodeIterator<T> {
    type Item = T;

    fn next(&mut self) -> Option<T> {
        if let Some(next) = self.next.take() {
            return Some(next);
        }

        if let Some(Node { value, right, .. }) = self.stack.pop() {
            if let Some(right) = right {
                let box right = right;
                self.stack.push(right);
            }
            return Some(value);
        }

        None
    }
}

fn pop_smallest<T: PartialOrd>(node: Node<T>, stack: &mut Vec<Node<T>>) -> T {
    let Node { value, left, right } = node;

    if let Some(left) = left {
        stack.push(Node { value: value, left: None, right: right });
        let box left = left;
        return pop_smallest(left, stack);
    }

    if let Some(right) = right {
        let box right = right;
        stack.push(right);
    }

    value
}

fn main() {
    let root = Node {
        value: 3,
        left: Some(Box::new(Node { value: 2, left: None, right: None })),
        right: Some(Box::new(Node { value: 4, left: None, right: None }))
    };

    for t in root {
        println!("{}", t);
    }
}

---

现在，我们可以通过添加适当的引用来轻松地"使它适应非消耗性情况:

---

Now, we can "easily" adapt it to the non-consuming case by sprinkling in the appropriate references:

struct RefNodeIterator<'a, T: PartialOrd + 'a> {
    stack: Vec<&'a Node<T>>,
    next: Option<&'a T>,
}

impl<'a, T: PartialOrd + 'a> IntoIterator for &'a Node<T> {
    type Item = &'a T;
    type IntoIter = RefNodeIterator<'a, T>;

    fn into_iter(self) -> Self::IntoIter {
        let mut stack = Vec::new();

        let smallest = pop_smallest_ref(self, &mut stack);

        RefNodeIterator { stack: stack, next: Some(smallest) }
    }
}

impl<'a, T: PartialOrd + 'a> Iterator for RefNodeIterator<'a, T> {
    type Item = &'a T;

    fn next(&mut self) -> Option<&'a T> {
        if let Some(next) = self.next.take() {
            return Some(next);
        }

        if let Some(node) = self.stack.pop() {
            if let Some(ref right) = node.right {
                self.stack.push(right);
            }
            return Some(&node.value);
        }

        None
    }
}

fn pop_smallest_ref<'a, T>(node: &'a Node<T>, stack: &mut Vec<&'a Node<T>>) -> &'a T
    where
        T: PartialOrd + 'a
{
    if let Some(ref left) = node.left {
        stack.push(node);
        return pop_smallest_ref(left, stack);
    }

    if let Some(ref right) = node.right {
        stack.push(right);
    }

    &node.value
}

里面有很多东西可以打开.所以花些时间来消化它.具体来说:

There's a lot to unpack in there; so take your time to digest it. Specifically:

• 在Some(ref right) = node.right中使用ref是因为我不想消耗node.right，仅是为了获取Option内部的引用.编译器会抱怨没有它我无法移出借用的对象(所以我只是听从投诉)，
，right: &'a Box<Node<T>>和stack: Vec<&'a Node<T>>中的
• ;这是Deref的魔力:Box<T>实现了Deref<T>，因此编译器会根据需要自动转换引用.

• the use of ref in Some(ref right) = node.right is because I don't want to consume node.right, only to obtain a reference inside the Option; the compiler will complain that I cannot move out of a borrowed object without it (so I just follow the complaints),
• in stack.push(right), right: &'a Box<Node<T>> and yet stack: Vec<&'a Node<T>>; this is the magic of Deref: Box<T> implements Deref<T> so the compiler automatically transforms the reference as appropriate.

注意:我没有按原样编写此代码；相反，我只是将前几个引用放在希望的位置(例如Iterator的返回类型)，然后让编译器引导我.

Note: I didn't write this code as-is; instead I just put the first few references where I expect them to be (such as the return type of Iterator) and then let the compiler guide me.

这篇关于为二叉树实现IntoIterator的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！