الصدأ ينفذ مكررًا مصنفًا بالدمج

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() الاستخدام في الجسم match مباشرة مع mem::replace() يدعو، ولكن أعتقد أن فصل اختيار القيم و mem::replace() اتصل واجعل الكود أكثر نظافة.كما لم أتمكن من استخدامها Some(x) و Some(y) الأنماط في الأخير match الذراع لأنه يتم نقل المراجع نفسها إلى a_item و b_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);
}