如何实现对二叉搜索树右边缘值的可变引用的迭代器? [英] How to implement an iterator of mutable references to the values in the right edges of a Binary Search Tree?

问题描述

我在 Rust 中实现了一个简单的二叉搜索树(遵循 CIS 198，它很棒)，为了学习，我正在做只穿过右边缘的迭代器.

I implemented a simple Binary Search Tree in Rust (following CIS 198, it's great), and for learning I'm doing iterators that just run through the right edges.

我无法实现提供可变引用的迭代器.我尝试了很多方法，但没有一个被 Rust 编译器接受.我需要帮助的代码是下面的代码(虽然我在这里制作了完整代码的要点):

I could not implement an iterator that gives mutable references. I tried a lot of ways, but none were accepted by Rust compiler. The code I need help is the one below (while I made a gist with the complete code here):

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

#[derive(Debug)]
pub struct Node<T> {
    elem: T,
    left: Tree<T>,
    right: Tree<T>,
}

// MUTABLE BORROW STRUCT
pub struct IterMut<'a, T: 'a> {
    next: &'a mut Tree<T>,
}

// MUTABLE BORROW NEXT (I'M STUCK HERE, NOTHING WORKS)
impl<'a, T> Iterator for IterMut<'a, T> {
    type Item = &'a mut T;
    fn next(&mut self) -> Option<Self::Item> {
        // 1 try: cannot infer lifetime
        self.next.0.as_mut().map(|node| {
            self.next = &mut node.right;
            &mut node.elem
        })

        // 2 try: node.right, node.elem does not live long enough
        self.next.0.take().map(|node| {
            self.next = &mut node.right;
            &mut node.elem
        })
    }
}

推荐答案

您需要将字段IterMut::next的类型改为Option<&'a mut Node<T>>:

You need to change the type of the field IterMut::next to Option<&'a mut Node<T>>:

pub struct IterMut<'a, T: 'a> {
    next: Option<&'a mut Node<T>>,
}

impl<'a, T> Iterator for IterMut<'a, T> {
    type Item = &'a mut T;
    fn next(&mut self) -> Option<Self::Item> {
        self.next.take().map(|node| {
            self.next = node.right.0.as_mut().map(|node| &mut **node);
            &mut node.elem
        })

    }
}

您可以找到更多关于递归数据结构可变迭代器实现的有用信息在使用完全太多的链表学习 Rust 的 IterMut 章节中.

You can find more useful information about the implementation of the mutable iterator for recursive data structures in the IterMut chapter of Learning Rust With Entirely Too Many Linked Lists.

这篇关于如何实现对二叉搜索树右边缘值的可变引用的迭代器?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！