Làm cách nào để viết một trình lặp mà trả về các tham chiếu đến chính nó?

Question

Tôi gặp sự cố khi thể hiện tuổi thọ của giá trị trả lại của triển khai Iterator. Làm thế nào tôi có thể biên dịch mã này mà không thay đổi giá trị trả về của trình lặp? Tôi muốn nó trả về một vectơ tham chiếu.

Rõ ràng là tôi không sử dụng thông số trọn đời chính xác nhưng sau khi thử nhiều cách khác nhau mà tôi đã từ bỏ, tôi không biết phải làm gì với nó.

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

Theo như tôi hiểu, bạn muốn muốn iterator để trả về một vector của tài liệu tham khảo vào bản thân, phải không? Thật không may, nó không thể trong Rust.

Đây là tỉa xuống Iterator đặc điểm:

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

Lưu ý rằng không có kết nối đời giữa &mut self và Option<Item>. Điều này có nghĩa là phương thức next() không thể trả lại tham chiếu vào bản thân trình lặp. Bạn chỉ có thể không thể hiện một đời của các tài liệu tham khảo trả về. Đây là về cơ bản là lý do mà bạn không thể tìm thấy một cách để xác định tuổi thọ đúng - nó sẽ đã xem xét như thế này:

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

trừ rằng đây không phải là một phương pháp hợp lệ next() cho Iterator tính trạng.

Trình vòng lặp như vậy (các trình lặp có thể trả về tham chiếu vào chính chúng) được gọi là trình lặp trực tuyến. Bạn có thể tìm thấy thêm here, here và here, nếu bạn muốn.

Cập nhật. Tuy nhiên, bạn có thể trả lại tham chiếu đến một số cấu trúc khác từ trình lặp của bạn - đó là cách hầu hết các trình vòng lặp bộ sưu tập hoạt động. Nó có thể trông như thế này:

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

Lưu ý cách đời 'a hiện đang công bố trên impl khối. Nó là OK để làm như vậy (yêu cầu, trên thực tế) bởi vì bạn cần phải xác định tham số suốt đời trên cấu trúc. Sau đó, bạn có thể sử dụng cùng một số 'a cả trong Item và trong loại next() trả lại. Một lần nữa, đó là cách mà hầu hết các trình vòng lặp bộ sưu tập hoạt động.

Answer 2

@VladimirMatveev's answer là chính xác trong cách nó giải thích tại sao mã của bạn không thể biên dịch. Tóm lại, nó nói rằng một Iterator không thể mang lại giá trị vay mượn từ bên trong chính nó.

Tuy nhiên, nó có thể mang lại giá trị được mượn từ một thứ khác. Đây là những gì đạt được với Vec và Iter: các Vec sở hữu các giá trị, và các Iter chỉ là một wrapper có thể mang lại tài liệu tham khảo trong các Vec.

Đây là thiết kế đạt được những gì bạn muốn.Các iterator là, giống như với Vec và Iter, chỉ là một wrapper trên container khác, những người thực sự sở hữu các giá trị.

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)

---

Không liên quan đến vấn đề ban đầu của bạn. Nếu đây chỉ là tôi, tôi sẽ đảm bảo rằng tất cả các vectơ vay mượn được thực hiện cùng một lúc. Ý tưởng là để loại bỏ các cuộc gọi lặp đi lặp lại để add và để vượt qua trực tiếp tất cả các vectơ mượn ở xây dựng:

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: Thay đổi thiết kế các iterator để có một Vec<&'a [T]> chứ không phải là một Vec<Vec<&'a T>>. Việc lấy ref tới container dễ dàng hơn là xây dựng một thùng chứa refs.)