Rust中为Stack trait实现into_iter返回迭代器的正确方式

假设我有如下Stack trait，它仅定义了pop和push操作：

trait Stack<T> {
    fn push(&mut self, data: T);
    fn pop(&mut self) -> Option<T>;
}

我可以通过以下函数测试该trait的任意实现：

fn test(stack: &mut dyn Stack<i32>) {
    stack.push(1);
    stack.push(2);
    stack.push(3);

    assert_eq!(stack.pop(), Some(3));
    assert_eq!(stack.pop(), Some(2));
    assert_eq!(stack.pop(), Some(1));
    assert_eq!(stack.pop(), None);
}

例如，以下是一个基于vector的实现：

struct StackWithVec<T> {
    vec: Vec<T>,
}

impl<T> Stack<T> for StackWithVec<T> {
    fn push(&mut self, data: T) {
        self.vec.push(data);
    }

    fn pop(&mut self) -> Option<T> {
        self.vec.pop()
    }
}

我们可以通过test函数测试该实现：

fn main() {
    test(&mut StackWithVec {
        vec: Vec::<i32>::new(),
    })
}

这段代码可以正常运行。

现在我想为该trait添加一个新方法into_iter，它会消耗self并返回一个Iterator<Item = T>：

trait Stack<T> {
    fn push(&mut self, data: T);
    fn pop(&mut self) -> Option<T>;
    fn into_iter(self) -> dyn Iterator<Item = T>;
}

我尝试为StackWithVec实现该方法，代码如下：

struct StackWithVecIntoIter<T>(StackWithVec<T>);

impl<T> Iterator for StackWithVecIntoIter<T> {
    type Item = T;

    fn next(&mut self) -> Option<Self::Item> {
        self.0.pop()
    }
}

impl<T> Stack<T> for StackWithVec<T> {
    fn push(&mut self, data: T) {
        self.vec.push(data);
    }

    fn pop(&mut self) -> Option<T> {
        self.vec.pop()
    }

    fn into_iter(self) -> StackWithVecIntoIter<T> {
        StackWithVecIntoIter(self)
    }
}

但编译器报错：

error[E0053]: method `into_iter` has an incompatible type for trait
  --> src/main.rs:30:27
   |
30 |     fn into_iter(self) -> StackWithVecIntoIter<T> {
   |                           ^^^^^^^^^^^^^^^^^^^^^^^
   |                           |
   |                           expected trait object `dyn Iterator`, found struct `StackWithVecIntoIter`
   |                           help: change the output type to match the trait: `(dyn Iterator<Item = T> + 'static)`
   |
note: type in trait
  --> src/main.rs:4:27
   |
4  |     fn into_iter(self) -> dyn Iterator<Item = T>;
   |                           ^^^^^^^^^^^^^^^^^^^^^^
   = note: expected fn pointer `fn(StackWithVec<_>) -> (dyn Iterator<Item = T> + 'static)`
              found fn pointer `fn(StackWithVec<_>) -> StackWithVecIntoIter<T>`

方法一：使用关联类型（推荐） #

在trait中定义关联类型，让每个Stack实现可以指定自己的迭代器类型，既保留静态分发的性能，又满足trait约束：

修改trait定义：

trait Stack<T> {
    // 定义关联类型，代表当前Stack对应的迭代器类型
    type IntoIter: Iterator<Item = T>;
    
    fn push(&mut self, data: T);
    fn pop(&mut self) -> Option<T>;
    fn into_iter(self) -> Self::IntoIter;
}

修改StackWithVec的实现，指定关联类型：

struct StackWithVecIntoIter<T>(StackWithVec<T>);

impl<T> Iterator for StackWithVecIntoIter<T> {
    type Item = T;

    fn next(&mut self) -> Option<Self::Item> {
        self.0.pop()
    }
}

impl<T> Stack<T> for StackWithVec<T> {
    // 指定当前Stack对应的迭代器类型
    type IntoIter = StackWithVecIntoIter<T>;
    
    fn push(&mut self, data: T) {
        self.vec.push(data);
    }

    fn pop(&mut self) -> Option<T> {
        self.vec.pop()
    }

    fn into_iter(self) -> Self::IntoIter {
        StackWithVecIntoIter(self)
    }
}

这种设计和Rust标准库的IntoIterator trait思路一致，能最大化利用静态类型优势，避免动态分发开销。

方法二：返回装箱的trait object #

如果需要统一into_iter的返回类型，可以将具体迭代器装箱为trait object，修改trait和实现如下：

修改trait定义：

trait Stack<T> {
    fn push(&mut self, data: T);
    fn pop(&mut self) -> Option<T>;
    // 返回Box包裹的trait object，指定'static生命周期（因为迭代器持有被消耗的self）
    fn into_iter(self) -> Box<dyn Iterator<Item = T>>;
}

修改StackWithVec的实现：

struct StackWithVecIntoIter<T>(StackWithVec<T>);

impl<T> Iterator for StackWithVecIntoIter<T> {
    type Item = T;

    fn next(&mut self) -> Option<Self::Item> {
        self.0.pop()
    }
}

impl<T> Stack<T> for StackWithVec<T> {
    fn push(&mut self, data: T) {
        self.vec.push(data);
    }

    fn pop(&mut self) -> Option<T> {
        self.vec.pop()
    }

    fn into_iter(self) -> Box<dyn Iterator<Item = T>> {
        // 将具体迭代器类型装箱为trait object
        Box::new(StackWithVecIntoIter(self))
    }
}

这种方式会引入动态分发开销，但能实现类型擦除，让所有Stack实现的into_iter返回统一类型。

内容的提问来源于stack exchange，提问作者Jay Mody