Jak napisać iterator, który zwraca do siebie odwołania?

Question

Mam problem z wyrażeniem czasu życia zwracanej wartości implementacji Iterator. Jak mogę skompilować ten kod bez zmiany zwracanej wartości iteratora? Chciałbym, żeby zwrócił wektor referencji.

Jest oczywiste, że nie używam parametru "lifetime" poprawnie, ale po wypróbowaniu różnych sposobów po prostu się poddałem, nie mam pojęcia, co z nim zrobić.

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

O ile dobrze rozumiem, chcesz chcesz iterator zwraca wektor odniesień do siebie, prawda? Niestety nie jest to możliwe w Rust.

Jest to okrojone Iterator cecha:

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

Zauważ, że nie ma połączenia między &mut self życia i Option<Item>. Oznacza to, że metoda next() nie może zwrócić odwołań do samego iteratora. Po prostu nie możesz wyrazić życia zwróconych referencji. Jest to po prostu dlatego, że nie można znaleźć sposób, aby określić odpowiedni czas życia - to już wyglądało tak:

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

wyjątkiem, że to nie jest ważne next() metoda Iterator cechy.

Takie iteratory (te, które mogą zwracać odniesienia do siebie) nazywane są streaming iterators. Możesz znaleźć więcej here, here i here, jeśli chcesz.

Aktualizacja. Możesz jednak zwrócić referencję do innej struktury z iteratora - tak działa większość iteratorów kolekcji. To może wyglądać następująco:

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

Uwaga jak żywotność 'a jest teraz zadeklarował impl bloku. Można to zrobić (jest to wymagane), ponieważ trzeba podać parametr czasu życia w strukturze. Następnie możesz użyć tego samego 'a zarówno w typie zwracanym Item jak i next(). Ponownie, tak działa większość iteratorów kolekcji.

Answer 2

@VladimirMatveev's answer ma rację, jak to wyjaśnia dlaczegokod nie może skompilować. Mówiąc w skrócie, mówi się, że Iterator nie może uzyskać pożyczonych wartości z siebie.

Może jednak dostarczyć pożyczone wartości z czegoś innego. Osiąga się to za pomocą Vec i Iter: wartość Vec jest właścicielem, a Iter jest po prostu otoką zdolną do uzyskania odniesień w zakresie Vec.

Oto projekt, który pozwala osiągnąć to, czego oczekujesz.Iterator to, podobnie jak w przypadku Vec i Iter, tylko opakowanie innych kontenerów, które w rzeczywistości są właścicielami wartości.

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)

---

niezwiązane z początkowego problemu. Gdybym to był tylko ja, upewniłbym się, że wszystkie pożyczone wektory są pobierane jednocześnie. Chodzi o to, aby usunąć powtarzające się apele do add i przejść bezpośrednio wszystkie pożyczone wektorów w budowie:

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: Zmieniono iterator konstrukcja wziąć Vec<&'a [T]> zamiast Vec<Vec<&'a T>>. Łatwiej jest wziąść ref do pojemnika niż zbudować kontener z ref.).