Как написать итератор, который возвращает ссылки на себя?

Ответ 1

Насколько я понимаю, вы хотите, чтобы итератор возвращал вектор ссылок в себя, правильно? К сожалению, это невозможно в Rust.

Это обрезанная черта Iterator:

trait Iterator {
    type Item;
    fn next(&mut self) -> Option<Item>;
}

Обратите внимание, что между &mut self и Option<Item> не существует соединения времени жизни. Это означает, что метод next() не может возвращать ссылки в сам итератор. Вы просто не можете выразить всю жизнь возвращенных ссылок. Это в основном причина, по которой вы не могли найти способ указать правильное время жизни - это выглядело бы так:

fn next<'a>(&'a mut self) -> Option<Vec<&'a T>>

за исключением того, что это недействительный метод next() для Iterator.

Такие итераторы (те, которые могут возвращать ссылки в себя) называются потоковыми итераторами. Здесь вы можете найти более , здесь и здесь, если вы хотите.

Обновить. Однако вы можете вернуть ссылку на какую-либо другую структуру из своего итератора - то, как работают большинство итераторов коллекции. Это может выглядеть так:

pub struct PermutationIterator<'a, T> {
    vs: &'a [Vec<T>],
    is: Vec<usize>
}

impl<'a, T> Iterator for PermutationIterator<'a, T> {
    type Item = Vec<&'a T>;

    fn next(&mut self) -> Option<Vec<&'a T>> {
        ...
    }
}

Обратите внимание на то, как срок службы 'a теперь объявляется в блоке impl. Это нормально (обязательно, на самом деле), потому что вам нужно указать параметр lifetime в структуре. Затем вы можете использовать тот же 'a как в Item, так и в next() возвращаемом типе. Опять же, как работает большинство итераторов коллекции.

Ответ 2

@Ответ VladimirMatveev является правильным в том, как он объясняет, почему ваш код не может скомпилироваться. В двух словах говорится, что Итератор не может давать заимствованные значения изнутри.

Однако он может давать заимствованные значения из чего-то другого. Это достигается с помощью Vec и Iter: Vec владеет значениями, а Iter - это просто оболочка, способная давать ссылки в Vec.

Вот дизайн, который позволяет вам что угодно. Итератор, как и Vec и Iter, представляет собой оболочку поверх других контейнеров, которые фактически владеют значениями.

use std::iter::Iterator;

struct PermutationIterator<'a, T: 'a> {
    vs : Vec<&'a [T]>,
    is : Vec<usize>
}

impl<'a, T> PermutationIterator<'a, T> {
    fn new() -> PermutationIterator<'a, T> { ... }

    fn add(&mut self, v : &'a [T]) { ... }
}

impl<'a, T> Iterator for PermutationIterator<'a, T> {
    type Item = Vec<&'a T>;
    fn next(&mut self) -> Option<Vec<&'a T>> { ... }
}

fn main() {
    let v1 : Vec<i32> = (1..3).collect();
    let v2 : Vec<i32> = (3..5).collect();
    let v3 : Vec<i32> = (1..6).collect();

    let mut i = PermutationIterator::new();
    i.add(&v1);
    i.add(&v2);
    i.add(&v3);

    loop {
        match i.next() {
            Some(v) => { println!("{:?}", v); }
            None => {break;}
        }
    }
}

(Игровая площадка)

Не связано с вашей первоначальной проблемой. Если бы это был только я, я бы гарантировал, что все заимствованные векторы будут приняты сразу. Идея состоит в том, чтобы удалить повторяющиеся вызовы add и передать непосредственно все заимствованные векторы при построении:

use std::iter::{Iterator, repeat};

struct PermutationIterator<'a, T: 'a> {
    ...
}

impl<'a, T> PermutationIterator<'a, T> {
    fn new(vs: Vec<&'a [T]>) -> PermutationIterator<'a, T> {
        let n = vs.len();
        PermutationIterator {
            vs: vs,
            is: repeat(0).take(n).collect(),
        }
    }
}

impl<'a, T> Iterator for PermutationIterator<'a, T> {
    ...
}

fn main() {
    let v1 : Vec<i32> = (1..3).collect();
    let v2 : Vec<i32> = (3..5).collect();
    let v3 : Vec<i32> = (1..6).collect();
    let vall: Vec<&[i32]> = vec![&v1, &v2, &v3];

    let mut i = PermutationIterator::new(vall);
}

(Игровая площадка)

( EDIT: изменил конструкцию итератора, чтобы взять Vec<&'a [T]>, а не Vec<Vec<&'a T>>. Легче взять ref в контейнер, чем построить контейнер refs.)

Ответ 3

Как упоминалось в других ответах, это называется потоковым итератором, и он требует разных гарантий от Rust Iterator. Один ящик, который обеспечивает такую функциональность, точно называется потоковым-итератором, и он обеспечивает свойство StreamingIterator.

Вот один пример реализации признака:

extern crate streaming_iterator;

use streaming_iterator::StreamingIterator;

struct Demonstration {
    scores: Vec<i32>,
    position: usize,
}

// Since 'StreamingIterator' requires that we be able to call
// 'advance' before 'get', we have to start "before" the first
// element. We assume that there will never be the maximum number of
// entries in the 'Vec', so we use 'usize::MAX' as our sentinel value.
impl Demonstration {
    fn new() -> Self {
        Demonstration {
            scores: vec![1, 2, 3],
            position: std::usize::MAX,
        }
    }

    fn reset(&mut self) {
        self.position = std::usize::MAX;
    }
}

impl StreamingIterator for Demonstration {
    type Item = i32;

    fn advance(&mut self) {
        self.position = self.position.wrapping_add(1);
    }

    fn get(&self) -> Option<&Self::Item> {
        self.scores.get(self.position)
    }
}

fn main() {
    let mut example = Demonstration::new();

    loop {
        example.advance();
        match example.get() {
            Some(v) => {
                println!("v: {}", v);
            }
            None => break,
        }
    }

    example.reset();

    loop {
        example.advance();
        match example.get() {
            Some(v) => {
                println!("v: {}", v);
            }
            None => break,
        }
    }
}

К сожалению, потоковые итераторы будут ограничены до тех пор, пока не будут реализованы общие связанные типы (ГАТ) из RFC 1598.