rust Iterator

2022-06-18 本文已影响0人 liaozhiyuan

Rust Iterator设计：

定义:

#[doc(notable_trait)]
#[rustc_diagnostic_item = "Iterator"]
#[must_use = "iterators are lazy and do nothing unless consumed"]
pub trait Iterator { 
      /// The type of the elements being iterated over.
    #[stable(feature = "rust1", since = "1.0.0")]
    type Item;
    #[lang = "next"]
    #[stable(feature = "rust1", since = "1.0.0")]
    fn next(&mut self) -> Option<Self::Item>;
    fn size_hint(&self) -> (usize, Option<usize>)} { ... }
    fn count(self) -> usize  where Self: Sized, { ... }
    fn last(self) -> Option<Self::Item> where Self: Sized, { ... }
    fn nth(&mut self, n: usize) -> Option<Self::Item> { ... }
    fn step_by(self, step: usize) -> StepBy<Self> where Self: Sized, { ... }
    ...

对Iterator Trait的理解：

Rust的Iterator在大部分情况下并不是直接impl在一个类型上的。
在查阅Vec等可以迭代的对象时，可以明显发现它们的迭代器是通过调用iter(), iter_mut(), into_iter() 三个函数而返回来的结果。返回的类型是Iter<Item>。这里Iter是一个范型类型，Item是Vec中的具体类型。意思是，当调用iter()函数后，那么Vec中的内容，就被填充到Iter数据结构中，在Iter数据结构中实际上包含一个指针ptr, 一个end指针，和一个PhantomData。其中ptr就是用于维护当前遍历的元素地址。当ptr指向end时，则代表迭代器遍历结束。

这里我们以Vec为例：

#[stable(feature = "rust1", since = "1.0.0")]
#[cfg_attr(not(test), rustc_diagnostic_item = "Vec")]
#[rustc_insignificant_dtor]
pub struct Vec<T, #[unstable(feature = "allocator_api", issue = "32838")] A:       
    Allocator = Global> {
    buf: RawVec<T, A>,
    len: usize,
}
impl<T> [T]  {
    #[stable(feature = "rust1", since = "1.0.0")]
    #[inline]
    pub fn iter(&self) -> Iter<'_, T> {
         Iter::new(self)
    }
}

pub struct Iter<'a, T: 'a> {
  ptr: NonNull<T>,
  end: *const T, // If T is a ZST, this is actually ptr+len.  This encoding is picked so that
  // ptr == end is a quick test for the Iterator being empty, that works
  // for both ZST and non-ZST.
  _marker: PhantomData<&'a T>,
}

我们可以看到Vec实际上是一个包含指针和长度的结构体。这里RawVec是一个内部的结构体，仅在本模块中可见,包含一个指针，cap长度，alloc内存分配器范型。

pub(crate) struct RawVec<T, A: Allocator = Global> {
    ptr: Unique<T>,
    cap: usize,
    alloc: A,
}

通过阅读标准库源码，我们弄清楚了Vec是由一个大结构体内嵌小结构体的数据结构。这个结构体的最终指针会指向堆上的实际向量元素的起始位置。并且随着next函数的调用，会进一步指向后续的元素。这里用c语言的理解就是，当你有一个一维数组需要遍历时，构造一个临时数据结构，存放一个i=0，然后封装next函数，用于遍历使用，毎调用一次next函数后执行i += 1。

Iter的意义总结
在Vec的iter函数中可以看到，其实现仅仅是返回一个Iter::new(self).这里 impl<T> [T] 的意思是向一个数组的切片实现iter函数。所以我们需要一个Iter容器来存放需要需要遍历的内容。需要一个Iter中间数据结构的意义是需要引入一个index来记录当前遍历的进度。所以不能直白的对一个Vec进行遍历，因为它的内部没有维护一个index索引值。它并不能保存当前的遍历状态，也就不能称之为迭代器。
实现自己的一个迭代器。
这里我们构造一个自有的结构体，并对这个结构体实现其iter函数和Iterator Trait，来达到对这个结构体实现遍历的目的。这里要说明的是，iter函数返回的Iter<T>结构体和fn next() 函数实际上具体是返回什么内容，是由程序员自己拟定的。所以只要合乎Trait约束，实际上功能是否正确，完全依赖程序员对next函数的实现。如果你实现一个next函数一直返回同一个值，也是没有问题的，只是它背离了迭代器的初衷。但是编译器实际上找不到任何问题。编译器只能核对参数/返回值的类型是否满足约束，并不会对具体的实现逻辑进行保证。也无法依赖类型推断系统或者约束系统来保证一个正确的逻辑。

#![allow(unused_variables)]
use std::iter::Iterator;

#[derive(Clone, Debug)]
struct Person {
    name: String,
}

struct PersonArray(Vec<Person>);
struct IterPerson<'a> {
    it: &'a Vec<Person>,
    count: usize,
}

impl PersonArray {
    fn new() -> Self {
        PersonArray(vec![
            Person {
                name: "lilei".to_string(),
            },
            Person {
                name: "hanmeimei".to_string(),
            },
        ])
    }
    fn iter(&self) -> IterPerson {
        IterPerson {
            it: &self.0,
            count: 0,
        }
    }
}

impl<'a> Iterator for IterPerson<'a> {
    type Item = &'a Person;
    fn next(&mut self) -> Option<Self::Item> {
        if self.count < self.it.len() {
            self.count += 1;
            Some(&self.it[self.count - 1])
        } else {
            None
        }
    }
}

fn main() {
    let a = PersonArray::new();
    for i in a.iter() {
        println!("{}", i.name);
    }
}

这是一份自定义的迭代器样例代码，代码中除了PersonArray外，其余的结构体包括：struct IterPerson<'a> { ... } ，struct Person { ... }都不是必须暴露的结构体。可以封装起来，代码中对Vec中实际的String元素，进行了引用，所以引入了生命周期参数。可以看到Rust实际上强烈依赖类型系统，来实现对容器的封装和抽象。Iterator中的Item 类型可以和实际的Vec中的元素类型是没有约束关系的，因为Iterator Trait中重新定义了type Item = &'a Person; 当然也可以定位为任何你想返回的类型。意思是你可以构造一个迭代器，遍历这个迭代器，但是返回完全不相关的内容，返回的次数也没有约束条件。在自定义迭代器中我们使用self.it.len()作为结束的条件，返回None来终止迭代。实际上程序员具体选用什么条件逻辑来结束迭代，完全依赖具体的实现。也就是说你完全可以通过调用iter函数返回一个毫不相干的迭代器，它的结束条件，它的返回元素类型都可能与原类型好不相关。
通过阅读Rust标准库源码和自己实现一个迭代器。我们理清了迭代器数据结构与原数据结构的关系（它们可以说毫无关系）。这种抽象约束带来了一个想象不到的好处和自由。那就是在对String进行迭代时，我们发现字符串可以有多种的迭代方式，既可以根据字符进行迭代，也可以根据其他类型的编码进行迭代，甚至我想对字符串的hex数据进行迭代。在标准库的迭代器抽象中，我们可以通过实现多个“iter”函数来返回多种迭代器对象，从而实现对同一个数据结构拥有多种的解释能力。

rust Iterator

猜你喜欢

热点阅读