Come si scrive un iteratore che restituisce riferimenti a se stesso?

Question

Ho difficoltà ad esprimere la durata del valore restituito di un'implementazione Iterator. Come posso compilare questo codice senza modificare il valore di ritorno dell'iteratore? Mi piacerebbe che restituisse un vettore di riferimenti.

È ovvio che non utilizzo correttamente il parametro della durata, ma dopo aver provato vari modi in cui ho rinunciato, non ho idea di cosa farne.

use std::iter::Iterator; 

struct PermutationIterator<T> { 
    vs: Vec<Vec<T>>, 
    is: Vec<usize>, 
} 

impl<T> PermutationIterator<T> { 
    fn new() -> PermutationIterator<T> { 
     PermutationIterator { 
      vs: vec![], 
      is: vec![], 
     } 
    } 

    fn add(&mut self, v: Vec<T>) { 
     self.vs.push(v); 
     self.is.push(0); 
    } 
} 

impl<T> Iterator for PermutationIterator<T> { 
    type Item = Vec<&'a T>; 
    fn next(&mut self) -> Option<Vec<&T>> { 
     'outer: loop { 
      for i in 0..self.vs.len() { 
       if self.is[i] >= self.vs[i].len() { 
        if i == 0 { 
         return None; // we are done 
        } 
        self.is[i] = 0; 
        self.is[i - 1] += 1; 
        continue 'outer; 
       } 
      } 

      let mut result = vec![]; 

      for i in 0..self.vs.len() { 
       let index = self.is[i]; 
       result.push(self.vs[i].get(index).unwrap()); 
      } 

      *self.is.last_mut().unwrap() += 1; 

      return Some(result); 
     } 
    } 
} 

fn main() { 
    let v1: Vec<_> = (1..3).collect(); 
    let v2: Vec<_> = (3..5).collect(); 
    let v3: Vec<_> = (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; 
      } 
     } 
    } 
} 

(Playground link)

error[E0261]: use of undeclared lifetime name `'a` 
    --> src/main.rs:23:22 
    | 
23 |  type Item = Vec<&'a T>; 
    |      ^^ undeclared lifetime 

Answer 1

Per quanto ho capito, volete vuole l'iteratore per restituire un vettore di riferimenti in se stesso, giusto? Sfortunatamente, non è possibile in Rust.

Questa è la assettato giù Iterator tratto:

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

noti che v'è alcuna connessione tra la vita&mut self e Option<Item>. Ciò significa che il metodo next() non può restituire riferimenti nell'iteratore stesso. Non puoi semplicemente esprimere una vita dei riferimenti restituiti. Questo è fondamentalmente il motivo per cui non si poteva trovare un modo per specificare la durata corretta - sarebbe già guardato come questo:

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

eccezione del fatto che questo non è un next() valido metodo per Iterator tratto.

Tali iteratori (quelli che possono restituire riferimenti in se stessi) sono chiamati iteratori di streaming. Puoi trovare altro here, here e here, se vuoi.

Aggiornamento . Tuttavia, è possibile restituire un riferimento ad un'altra struttura dal proprio iteratore: è così che funziona la maggior parte degli iteratori di raccolta. Potrebbe assomigliare a questo:

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>> { 
     ... 
    } 
} 

Si noti come la vita 'a è ormai dichiarata impl blocco. È OK farlo (richiesto, infatti) perché è necessario specificare il parametro lifetime sulla struttura. Quindi è possibile utilizzare lo stesso 'a entrambi in Item e nel tipo di ritorno next(). Di nuovo, è così che funziona la maggior parte degli iteratori di raccolta.

Answer 2

@VladimirMatveev's answer è corretto nel modo in cui si spiega il motivo per cui il codice non può compilare. In poche parole, afferma che un Iterator non può produrre valori presi in prestito da se stesso.

Tuttavia, può restituire valori presi in prestito da qualcos'altro. Questo è ciò che si ottiene con Vec e Iter: il Vec possiede i valori e lo Iter è solo un wrapper in grado di fornire riferimenti all'interno dello Vec.

Ecco un disegno che realizza ciò che desideri.L'iteratore è, come con Vec e Iter, solo un wrapper su altri contenitori che possiedono effettivamente i valori.

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;} 
     } 
    } 
} 

(Playground)

---

non collegati al problema iniziale. Se fossi solo io, farei in modo che tutti i vettori presi in prestito vengano presi immediatamente. L'idea è quella di rimuovere le chiamate ripetute per add e passare direttamente tutti i vettori in prestito a costruzione:

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); 
} 

(Playground)

(EDIT: Modificato disegno iteratore rimessa Vec<&'a [T]> piuttosto che un Vec<Vec<&'a T>>. È più facile prendere un contenitore ref che costruire un contenitore di ref.)