rust实战系列 - 使用Iterator 迭代器实现斐波那契数列(Fibonacci )

为什么是斐波那契数列

斐波那契数列十分适合用来实战rust的迭代器,算法也很简单,一目了然。这个例子可以用来学习Iterator的使用,十分适合刚学习了rust的迭代器章节后用来练练手。

代码实战

don't bb, show me the code

struct Fib(usize, usize);

impl Fib {
    fn new() -> Fib {
        Fib(0, 1)
    }
}

impl Iterator for Fib {
    type Item = usize;
    fn next(&mut self) -> Option<usize> {
        *self = Fib(self.1, self.0 + self.1);
        Some(self.0)
    }
}

fn main() {
    let last = 20;
    println!("fib({}) result: {:?}", last, Fib::new().take(last).collect::<Vec<usize>>());
}

分解知识点

  1. 代码定义了一个名字为Fib的元组结构体(tuple structs)。因为我们的实现封装了实现细节,没必要定义一个具名结构体。
    网上有给出其他定义了名称的结构体,个人觉得有点多余了。比如这样
struct Fibonacci {
    a: u64,
    b: u64,
}
  1. 第二点就是如何实现Iterator,关键就两点,定义关联类型和实现next方法
impl Iterator for Fib {
    // 1. 定义关联类型为usize
    type Item = usize;
    // 2. 实现next方法,这里也是主要的逻辑
    fn next(&mut self) -> Option<usize> {
        *self = Fib(self.1, self.0 + self.1);
        Some(self.0)
    }
}
  1. 第三点是*self = Fib(self.1, self.0 + self.1);; self被定义为了可变引用(&mut), 这里*self 解引用为Fib类型。
    另外一种写法
self = &mut Fib(self.1, self.0 + self.1);

上面定义了一个可变引用 &mut Fib 赋值给self,rust编译器直接提示

   |
12 |         self = &mut Fib(self.1, self.0 + self.1);
   |         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ cannot assign to immutable argument

error[E0716]: temporary value dropped while borrowed
  --> src\main.rs:12:21
   |
11 |     fn next(&mut self) -> Option<usize> {
   |             - let's call the lifetime of this reference `'1`
12 |         self = &mut Fib(self.1, self.0 + self.1);
   |         ------------^^^^^^^^^^^^^^^^^^^^^^^^^^^^- temporary value is freed at the end of this statement
   |         |           |
   |         |           creates a temporary which is freed while still in use
   |         assignment requires that borrow lasts for `'1`

提示借用了临时变量,临时变量会被丢弃掉。其实就是&mut Fib 只是一个可变借用,在被借用给self后就会马上失效了,self就会指向一个悬垂指针, rust编译器肯定不会让这种情况发生的(强行解释一波,欢迎打脸)。
所以正确的做法是直接让self获取新创建的Fib的所有权就行了。也就是*self = Fib(self.1, self.0 + self.1);

  1. 第四点是Fib::new().take(last).collect::<Vec<usize>>()。 这里直接在println宏里打印结果,编译器推断不出需要collect的类型,需要使用collect::标注。
    除非是下面这种写法,编译器能自动推断出来
let result: Vec<usize> = Fib::new().take(last).collect();
println!("fib({}) result: {:?}", last, result);

总结

本文通过rust iterator来实现斐波那契数列,需要掌握一下要点

  • 元组结构体写法
  • 如何实现iterator trait
  • collect::<B> 帮助编译器推断类型
上一篇:递归求解斐波那契数列


下一篇:Css 使div标签下沉到页面最低部