Rust实现merge-sorted迭代器

Question

我正在尝试实现一个合并两个已排序迭代器的迭代器.我正在运行从结构中发布借用字段.

如何避免此错误？我尝试使用借来的引用,但似乎没有帮助,因为最终我需要移动a_item和b_item的值.

use std::num::Saturating;

pub struct MergeSorted<A, T> {
    a: T,
    b: T,
    a_item: Option<A>,
    b_item: Option<A>,
}

impl<A: Ord, T: Iterator<A>> Iterator<A> for MergeSorted<A, T> {
    #[inline]
    fn next(&mut self) -> Option<A> {

        match (self.a_item, self.b_item) {
            (None, None) => None,

            (None, Some(y)) => {
                let result = self.b_item;
                self.b_item = None;
                return result;
            }

            (Some(x), None) => {
                let result = self.a_item;
                self.a_item = self.a.next();
                result
            }

            (Some(x), Some(y)) => {
                if x < y {
                    let result = self.a_item;
                    self.a_item = self.a.next();
                    result
                } else {
                    let result = self.b_item;
                    self.b_item = self.b.next();
                    result
                }
            }
        }
    }

    #[inline]
    fn size_hint(&self) -> (uint, Option<uint>) {
        // stub
        (10, Some(100))
    }
}

这是特定错误,对于self.a_item和self.b_item的所有用法都会重复此错误.

error: cannot move out of dereference of `&mut`-pointer
       match (self.a_item, self.b_item) {
              ^~~~~~~~~~~

Answer 1

第一个问题是这种模式:

let result = self.b_item;
self.b_item = None;
return result;

在第一行之后,第二行self.b_item被移出之前,制作一个"洞" self(即使我们忘记了这self是一个借来的指针,你也无法移出它).这是不允许的.为了表达这种模式,有一个特殊的功能std::mem,叫做replace.

第二个主要问题是A不能隐式复制,因此当您尝试匹配类型的值时Option<A>,这些值会被移出,但&/&mut禁止从指针内部移出.解决这个问题的唯一方法是匹配引用.但是那时你应该小心,因为借用规则只允许你一次有单一的可变借款.所以,你必须组织一个样引用的"流"到self.a_item,并self.b_item通过匹配语句,使用模式绑定.

以下代码编译.您还可以直接用调用替换正文中的result变量和Some()用法,但我认为分离值选择和调用使代码更清晰.此外,我无法在最后一个手臂中使用和模式,因为引用本身被移入和.matchmem::replace()mem::replace()Some(x)Some(y)matcha_itemb_item

use std::mem;

pub struct MergeSorted<A, T> {
    a: T,
    b: T,
    a_item: Option<A>,
    b_item: Option<A>,
}

impl<A: Ord, T: Iterator<A>> Iterator<A> for MergeSorted<A, T> {
    #[inline]
    fn next(&mut self) -> Option<A> {
        let result = match (&mut self.a_item, &mut self.b_item) {
            (&None, &None) => None,
            (&None, b_item @ &Some(_)) => Some((b_item, None)),
            (a_item @ &Some(_), &None) => Some((a_item, self.a.next())),
            (a_item @ &Some(_), b_item @ &Some(_)) => Some(
                if a_item.get_ref() < b_item.get_ref() {
                    (a_item, self.a.next())
                } else {
                    (b_item, self.b.next())
                }
            )
        };

        result.and_then(|(dest, value)| mem::replace(dest, value))
    }

    #[inline]
    fn size_hint(&self) -> (uint, Option<uint>) {
        // stub
        (10, Some(100))
    }
}

Answer 2

这个解决方案适用于Rust 1.2和可能和Rust 1.x.

Option我没有保留自己的项目,而是选择使用peekable迭代器适配器.这使我们可以向前看一个项目而不会丢失它.

我还将Iterator::next方法分解为两个部分 - 一个确定从哪一侧拉,另一个实际推进迭代器.

现在还有关于如何使用关联类型定义迭代器的一般更新.

use std::iter::Peekable;
use std::cmp::Ordering;

struct MergeAscending<L, R>
where
    L: Iterator<Item = R::Item>,
    R: Iterator,
{
    left: Peekable<L>,
    right: Peekable<R>,
}

impl<L, R> MergeAscending<L, R>
where
    L: Iterator<Item = R::Item>,
    R: Iterator,
{
    fn new(left: L, right: R) -> Self {
        MergeAscending {
            left: left.peekable(),
            right: right.peekable(),
        }
    }
}

impl<L, R> Iterator for MergeAscending<L, R>
where
    L: Iterator<Item = R::Item>,
    R: Iterator,
    L::Item: Ord,
{
    type Item = L::Item;

    fn next(&mut self) -> Option<L::Item> {
        let which = match (self.left.peek(), self.right.peek()) {
            (Some(l), Some(r)) => Some(l.cmp(r)),
            (Some(_), None) => Some(Ordering::Less),
            (None, Some(_)) => Some(Ordering::Greater),
            (None, None) => None,
        };

        match which {
            Some(Ordering::Less) => self.left.next(),
            Some(Ordering::Equal) => self.left.next(),
            Some(Ordering::Greater) => self.right.next(),
            None => None,
        }
    }
}

fn main() {
    let left = [1, 3, 5, 7, 9];
    let right = [3, 4, 5, 6, 7];

    let result: Vec<_> = MergeAscending::new(left.iter(), right.iter()).collect();
    println!("{:?}", result);
}