需要帮助理解迭代器的生命周期

Question

考虑以下代码：

#[derive(Clone)]
pub struct Stride<'a, I: Index<uint> + 'a> {
    items: I,
    len: uint,
    current_idx: uint,
    stride: uint,
}

impl<'a, I> Iterator for Stride<'a, I> where I: Index<uint> {
    type Item = &'a <I as Index<uint>>::Output;

    #[inline]
    fn next(&mut self) -> Option<&'a <I as Index<uint>>::Output> {
        if (self.current_idx >= self.len) {
            None
        } else {
            let idx = self.current_idx;
            self.current_idx += self.stride;
            Some(self.items.index(&idx))
        }
    }
}

当前出现错误，表示编译器无法为 Some(self.items.index(&idx)) 行推断出合适的生命周期。 return 值的生命周期应该是多少？我相信它应该与 self.items 具有相同的生命周期，因为 Index 特征方法 return 是一个与 Index 实现者具有相同生命周期的引用。

Answer 1

Index的definition是：

pub trait Index<Index: ?Sized> {
    type Output: ?Sized;
    /// The method for the indexing (`Foo[Bar]`) operation
    fn index<'a>(&'a self, index: &Index) -> &'a Self::Output;
}

具体来说，index return 是对元素的引用，该引用的生命周期与 self 相同。也就是借用了self.

在你的例子中，index 调用的 self（顺便说一句，可能是 &self.items[idx]）是 self.items，因此编译器认为 return 值必须限制从 self.items 借用，但是 items 属于 next 的 self，所以从 self.items 借用是从 self 本身借用。

也就是说，编译器只能保证index的return值在self存活期间一直有效（以及各种变异的顾虑），所以&mut self 和 returned &... 的生命周期必须关联起来。

如果有人编译它，看到错误，编译器建议链接引用：

<anon>:23:29: 23:40 error: cannot infer an appropriate lifetime for autoref due to conflicting requirements
<anon>:23             Some(self.items.index(&idx))
                                      ^~~~~~~~~~~
<anon>:17:5: 25:6 help: consider using an explicit lifetime parameter as shown: fn next(&'a mut self) -> Option<&'a <I as Index<uint>>::Output>
<anon>:17     fn next(&mut self) -> Option<&'a <I as Index<uint>>::Output> {
<anon>:18         if (self.current_idx >= self.len) {
<anon>:19             None
<anon>:20         } else {
<anon>:21             let idx = self.current_idx;
<anon>:22             self.current_idx += self.stride;
          ...

然而，建议的签名 fn next(&'a mut self) -> Option<&'a <I as Index<uint>>::Output> 比 Iterator 特征的签名更严格，因此是非法的。（具有这种生命周期安排的迭代器可能很有用，但它们不适用于许多普通消费者，例如 .collect。）

编译器正在防止的问题由如下类型证明：

struct IndexablePair<T>  {
    x: T, y: T
}

impl Index<uint> for IndexablePair<T> {
    type Output = T;
    fn index(&self, index: &uint) -> &T {
        match *index {
            0 => &self.x,
            1 => &self.y,
            _ => panic!("out of bounds")
        }
    }
}

这存储两个 T 内联（例如直接在堆栈上）并允许索引它们 pair[0] 和 pair[1]。 index 方法 return 是一个直接指向该内存（例如堆栈）的指针，因此如果 IndexablePair 值在内存中移动，这些指针将变得无效，例如（假设 Stride::new(items: I, len: uint, stride: uint)）：

let pair = IndexablePair { x: "foo".to_string(), y: "bar".to_string() };

let mut stride = Stride::new(pair, 2, 1);

let value = stride.next();

// allocate some memory and move stride into, changing its address
let mut moved = box stride;

println!("value is {}", value);

倒数第二行写错了！它使 value 无效，因为 stride 和它的字段 items （一对）在内存中移动，因此 value 中的引用然后指向移动的数据；这是非常不安全和非常糟糕的。

建议的生命周期通过借用 stride 并禁止移动来阻止这个问题（以及其他几个有问题的问题），但是，正如我们在上面看到的那样，我们不能使用它。

解决这个问题的一种技术是将存储元素的内存与迭代器本身分开，即将Stride的定义更改为：

pub struct Stride<'a, I: Index<uint> + 'a> {
    items: &'a I,
    len: uint,
    current_idx: uint,
    stride: uint,
}

（添加对 items 的引用。）

然后编译器保证存储元素的内存独立于 Stride 值（也就是说，在内存中移动 Stride 不会使旧元素无效），因为有将它们分开的非拥有指针。这个版本编译正常：

use std::ops::Index;

#[derive(Clone)]
pub struct Stride<'a, I: Index<uint> + 'a> {
    items: &'a I,
    len: uint,
    current_idx: uint,
    stride: uint,
}

impl<'a, I> Iterator for Stride<'a, I> where I: Index<uint> {
    type Item = &'a <I as Index<uint>>::Output;

    #[inline]
    fn next(&mut self) -> Option<&'a <I as Index<uint>>::Output> {
        if (self.current_idx >= self.len) {
            None
        } else {
            let idx = self.current_idx;
            self.current_idx += self.stride;
            Some(self.items.index(&idx))
        }
    }
}

（理论上可以在其中添加一个 ?Sized 绑定，可能是通过手动实现 Clone 而不是 deriveing 它，以便可以直接使用 Stride使用 &[T]，即 Stride::new(items: &I, ...) Stride::new(&[1, 2, 3], ...) 会起作用，而不是像默认 Sized 绑定要求的那样必须有双层 Stride::new(&&[1, 2, 3], ...)。）

playpen

需要帮助理解迭代器的生命周期

Need help understanding Iterator lifetimes

rust