在没有生命周期参数的类型上限制实现生命周期的问题

Question

我正在尝试在 Rust 中实现 BST（对于 Rust 的可爱介绍中的 HW3 ），并且我遇到了生命周期错误，以及如何约束与没有生命周期的类型相关的类型的生命周期。

#[derive(Debug)]
pub struct BST<T>
    where T: Ord
{
    root: Option<Box<Node<T>>>,
}

// A couple dozen lines of BST stuff

impl<'a, T> IntoIterator for BST<T>
    where T: Ord
{
    type Item = T;
    type IntoIter = BSTIter<'a, T>; // <- my intuition is that I should
                                        // be able to say "BSTIter lives as
                                        // long as BST."

    fn into_iter(&'a mut self) -> BSTIter<'a, T> {
        BSTIter::new(&mut self)
    }
}


pub struct BSTIter<'a, T: 'a>
    where T: Ord + 'a
{
    bst: &'a mut BST<T>,
    node_list: Vec<&'a Node<T>>, // this is where the need for a lifetime on
                                 // BSTIter comes from
}


impl<'a, T> BSTIter<'a, T>
    where T: Ord
{
    fn new(&mut bst: BST<T>) -> BSTIter<'a, T> {
        let traverse_stack = Vec::new();
        if let Some(ref x) = bst.root {
            traverse_stack.push(x);
        }
        BSTIter {
            bst: bst,
            node_list: traverse_stack,
        }
    }
}


impl<'a, T> Iterator for BSTIter<'a, T>
    where T: Ord
{
    type Item = T;

    fn next(&mut self) -> Option<T> {
        // BST iteration details
    }
}

就目前而言，这段代码会抛出错误

#[derive(Debug)]
pub struct BST<T>
    where T: Ord
{
    root: Option<Box<Node<T>>>,
}

// A couple dozen lines of BST stuff

impl<'a, T> IntoIterator for BST<T>
    where T: Ord
{
    type Item = T;
    type IntoIter = BSTIter<'a, T>; // <- my intuition is that I should
                                        // be able to say "BSTIter lives as
                                        // long as BST."

    fn into_iter(&'a mut self) -> BSTIter<'a, T> {
        BSTIter::new(&mut self)
    }
}


pub struct BSTIter<'a, T: 'a>
    where T: Ord + 'a
{
    bst: &'a mut BST<T>,
    node_list: Vec<&'a Node<T>>, // this is where the need for a lifetime on
                                 // BSTIter comes from
}


impl<'a, T> BSTIter<'a, T>
    where T: Ord
{
    fn new(&mut bst: BST<T>) -> BSTIter<'a, T> {
        let traverse_stack = Vec::new();
        if let Some(ref x) = bst.root {
            traverse_stack.push(x);
        }
        BSTIter {
            bst: bst,
            node_list: traverse_stack,
        }
    }
}


impl<'a, T> Iterator for BSTIter<'a, T>
    where T: Ord
{
    type Item = T;

    fn next(&mut self) -> Option<T> {
        // BST iteration details
    }
}

如果该IntoIterator特征不需要我指定type IntoIterator = BSTIter，则实现块可以只具有into_iter方法签名into_iter<'a>(&'a mut self) -> BSTIter<'a, T>。因为我需要指定生命周期BSTIter，因此似乎我需要指定整个 BST 类型的生存期。同样，我的直觉告诉我，我不必在 BST 上指定生命周期才能为其创建迭代器。

我意识到这两个解决方案可能是以下之一（或两者）

1. 有一个语言功能可以帮助我解决这个问题
2. 一路走来，我的代码变得非常不惯用 Rust

如果我能获得关于如何使上述代码片段工作，或者我应该如何处理这些生命周期和所有权细节的帮助，我将非常感激！

Answer 1

您误解了 的目的和用法IntoIterator。它将一个值转换为一个迭代器；消耗过程中的价值。但是，您的迭代器正在尝试返回对集合的引用。您无法将引用返回到 iterator 中，因此使用树并将所有权转移给迭代器是没有意义的。

事实上，你调用它BSTIter而不是BSTIntoIter显示了希望；因为这是返回引用的迭代器的惯用名称。

你想要实现的IntoIterator是&'a BST<T>，而不是BST<T>。您也可以将其实现为BST<T>，但随后您想要yield T，而不是&T。

修复该问题后，会出现很多编译器错误：整个代码中的类型不匹配，特征中的方法签名不正确（这fn into_iter(self)是您所允许的），由于某种原因，存在对树的可变引用，变量在应该可变时却不可变....

#[derive(Debug)]
struct Node<T>(Option<Box<T>>);

#[derive(Debug)]
pub struct BST<T>
    where T: Ord
{
    root: Option<Box<Node<T>>>,
}

impl<'a, T> IntoIterator for &'a BST<T>
    where T: Ord
{
    type Item = T;
    type IntoIter = BSTIter<'a, T>;
    fn into_iter(self) -> BSTIter<'a, T> {
        BSTIter::new(self)
    }
}

pub struct BSTIter<'a, T: 'a>
    where T: Ord + 'a
{
    bst: &'a BST<T>,
    node_list: Vec<&'a Node<T>>,
}

impl<'a, T> BSTIter<'a, T>
    where T: Ord
{
    fn new(bst: &'a BST<T>) -> BSTIter<'a, T> {
        let mut traverse_stack = Vec::new();
        if let Some(ref x) = bst.root {
            traverse_stack.push(&**x);
        }
        BSTIter {
            bst: bst,
            node_list: traverse_stack,
        }
    }
}

impl<'a, T> Iterator for BSTIter<'a, T>
    where T: Ord
{
    type Item = T;

    fn next(&mut self) -> Option<T> {
        None
    }
}

fn main() {}