当前位置:网站首页>【Rust 笔记】13-迭代器(下)

【Rust 笔记】13-迭代器(下)

2022-07-05 05:50:00 phial03

13.4 - 消费迭代器

13.4.1 - 简单累计

  • count 方法:从一个迭代器中取值,知道它返回 None,然后告诉你这个迭代器包含多少项。

    use std::io::prelude::*;
    
    fn main() {
          
        let stdin = std::io::stdin();
        println!("{}", stdin.lock().lines().count());
    }
    
  • sum 方法:用于计算迭代器项(必须是整数或浮点数)的和。

  • product 方法:用于计算迭代器项(必须是整数或浮点数)的积。

    use std::iter::{
          Sum, Product};
    
    fn triangle(n: u64) -> u64 {
          
        (1.. n+1).sum()
    }
    assert_eq!(triangle(20), 210);
    
    fn factorial(n: u64) -> u64 {
          
        (1.. n+1).product()
    }
    assert_eq!(factorial(20), 2432902008176640000);
    

13.4.2-maxmin

  • Iterator 特型的 maxmin 方法分别返回迭代器产生项的最大值和最小值。迭代器的项类型必须实现 std::cmp::Ord,这样项与项之间才能比较。

    assert_eq!([-2, 0, 1, 0, -2, -5].iter().max(), Some(&1));
    assert_eq!([-2, 0, 1, 0, -2, -5].iter().min(), Some(&-5));
    
  • 这两个方法返回 Option<Self::Item>,因此在迭代器没有产生项时返回 None

  • 浮点类型 f32f64 只实现了 std::cmp::PartialOrd,没有实现 std::cmp::Ord,因此不能使用上述两个方法。

13.4.3-max_bymin_by

  • max_bymin_by 方法根据提供的自定义比较方法,返回迭代器产生的最大值和最小值。

    use std::cmp::{
          PartialOrd, Ordering};
    
    // 比较两个f64的值,如果包含NAN则诧异
    fn cmp(lhs: &&f64, rhs: &&f64) -> Ordering {
          
        lhs.partial_cmp(rhs).unwrap()
    }
    
    let numbers = [1.0, 4.0, 2.0];                 // 序列中不包含NAN的比较
    assert_eq!(numbers.iter().max_by(cmp), Some(&4.0));
    assert_eq!(numbers.iter().min_by(cmp), Some(&1.0));
    
    let numbers = [1.0, 4.0, std::f64::NAN, 2.0];  // 序列中包含NAN的比较
    assert_eq!(numbers.iter().max_by(cmp), Some(&4.0));  // 比较过程中会产生诧异
    
  • &&f64 采用双重引用,是因为 numbers.iter() 会产生对元素的引用,然后 max_bymin_by 又把迭代器项的引用传给了闭包。

13.4.4-max_by_keymin_by_key

  • Iteratormax_by_keymin_by_key 方法可以根据应用到每一项的闭包,选择最大或最小的项。

    /// 对给定的以每一项作为参数,且返回有序类型B的闭包,
    /// 它们返回 闭包返回的B最大或最小 的项。
    /// 如果没有产生项,则返回None。
    fn max_by_key<B: Ord, F>(self, f: F) -> Option<Self:: Item>
        where Self: Sized, F: FnMut(&Self::Item) -> B;
    
    fn min_by_key<B: Ord, F>(self, f: F) -> Option<Self:: Item>
        where Self: Sized, F: FnMut(&Self::Item) -> B;
    
    • 闭包可以选择项的某个字段,或者对每一项执行某些计算。
    • 只需要关心与最大项或最小项关联的数据。
  • 举例:从一个城市的散列表中找到其中人口最多和最少的城市:

    use std::collections::HashMap;
    
    let mut populations = HashMap::new();
    populations.insert("Portland",  583_776);
    populations.insert("Fossil",        449);
    populations.insert("Greenhorn",       2);
    populations.insert("Boring",      7_762);
    populations.insert("The Dalles", 15_340);
    
    assert_eq!(populations.iter().max_by_key(|&(_name, pop)| pop), 
                                             Some((&"Portland", &583_776)));
    assert_eq!(populations.iter().min_by_key(|&(_name, pop)| pop), 
                                             Some((&"Greenhorn", &2)));
    
    • 闭包 |&(_name, pop)| pop 会应用于迭代器产生的每一项,返回的值则用于比较。
    • 此处返回的是人口。返回的值是整个项,而不是闭包返回的值。

13.4.5 - 比较项序列

  • 对于字符串、向量和切片,可以使用 ><== 操作符比较。

  • 对于迭代器,可以使用 eqlt 等方法实现同样的功能。从迭代器中取得成对的项,然后对它们进行比较,直到可以做出决定:

    • eqne 方法用于相等性比较;
    • ltlegtge 方法用于次序比较。
    • cmppartial_cmp 方法,与 OrdPartialOrd 特型上对应的方法类似。
    let packed = "Helen of Troy";
    let spaced = "Helen of Troy";
    let obscure = "Helen of Sandusky";
    
    assert_eq!(packed != spaced);
    assert_eq!(packed.split_whitespace().eq(spaced.split_whitespace()));
    
    // 返回true,因为 ' ' < 'o'
    assert!(spaced < obscure);
    
    // 返回true, 因为'Troy' > 'Sandusky'
    assert!(spaced.split_whitespace().gt(obscure.split_whitespace()));
    
    • 此处调用了 split_whitespace() 方法,可以返回迭代器产生以空格分割字符串得到的单词。
    • 使得调用 eqgt 方法,可以执行单词与单词的比较,而不是字符与字符的比较。
    • 因为 &str 实现了 PartialOrdPartialEq 特型。

13.4.6-anyall

  • any 方法:给迭代器产生的每一项应用闭包,如果闭包对其中一项返回 true,则方法才返回 true

  • all 方法:给迭代器产生的每一项应用闭包,如果闭包对全部项返回 true,则方法才返回 true

    let id = "Iterator";
    
    assert!(id.chars().any(char::is_uppercase));
    assert!(!id.chars().all(char::is_uppercase));
    

13.4.7-positionrpositionExactSizeIterator

  • position 方法:给迭代器产生的每一项应用闭包,返回值是一个 Option 类型的值:

    • 如果闭包对任何项都没有返回 true,则方法返回 None

    • 只要闭包返回 trueposition 就停止取值,并返回该项的索引。

      let text = "Xerxes";
      
      assert_eq!(text.chars().position(|c| c == 'e'), Some(1));
      assert_eq!(text.chars().position(|c| c == 'z'), None);
      
  • rposition 方法:功能与 position 相同,只不过是从右侧开始搜索。

    • 要求使用的迭代器为可逆迭代器,这样才能从迭代器右端取值。

    • 要求迭代器的大小固定,这样才能像 position 那样为索引赋值,同样以最左边的项为 0。

    • 不能对字符串使用 rposition。对字符串使用 b 标记,使得字符串转换为字节数组。

      let bytes = b"Xerxes";
      
      assert_eq!(bytes.iter().rposition(|&c| c == b'e'), Some(4));
      assert_eq!(bytes.iter().rposition(|&c| c == b'X'), Some(0));
      
  • 固定大小的迭代器,是指实现了 std::iter::ExactSizeIterator 特型的迭代器:

    pub trait ExactSizeIterator: Iterator {
          
        fn len(&self) -> usize {
           ... }
        fn is_empty(&self) -> bool {
           ... }
    }
    
    • len 方法返回剩余项数。
    • is_empty 方法在迭代完成时返回 true

13.4.8-fold

  • fold 方法:对迭代器产生的项的整个序列执行累计操作。

    • 接收一个累加器(accumulator)的初始值和一个闭包,
    • 然后对当前累加器和迭代器的下一项重复应用闭包。
    • 每次闭包的返回值都会成为累加器的新值,然后再和迭代器的下一项,一同传给闭包。
    • 返回值:累加器的最终值也是 fold 方法的返回值。如果序列为空,则 fold 返回累加器的初始值。
  • fold 方法的签名:

    fn fold<A, F>(self, init: A, f: F) -> A
        where Self: Sized, F: FnMut(A, Self::Item) -> A;
    
    • A 是累加器的类型。
    • init 参数是一个 A,即累加器。
    • 闭包的第一个参数及返回值都是 A
  • 迭代器的许多其他方法可以写成使用 fold 的形式:

    let a = [5, 6, 7, 8, 9, 10];
    
    assert_eq!(a.iter().fold(0, |n, _| n + 1),  6);       // 实现count
    assert_eq!(a.iter().fold(0, |n, i| n + i),  45);      // 实现sum
    assert_eq!(a.iter().fold(1, |n, i| n * i),  151200);  // 实现product
    assert_eq!(a.iter().fold(i32::min_value(), |m, &i| std::cmp::max(m, i)), 10);//实现max
    
  • 累加器的值会转移到闭包中,再转移出来。因此可以对非 Copy 类型的累加器使用 fold 方法:

    let a = ["Pack ", "my ", "box ", "with ",
             "five ", "dozen ", "liquor ", "jugs"];
    let pangram = a.iter().fold(String::new(), |mut s, &w| {
          s.push_str(w); s});
    
    assert_eq!(pangram, "Pach my box with five dozen liquor jugs");
    

13.4.9-nth

  • nth 方法:接收一个索引值 n,然后跳过迭代器中相应的项,返回索引对应的项。

    • 如果序列在此之前结束,则返回 None

    • 调用.nth(0) 等同于调用.next()

      fn nth(&mut self, n: usize) -> Option<Self::Item> where Self: Sized;
      
  • nth 不会取得迭代器的所有权,因此可以多次调用:

    let mut squares = (0..10).map(|i| i * i);
    
    assert_eq!(squares.nth(4), Some(16));
    assert_eq!(squares.nth(0), Some(25));
    assert_eq!(squares.nth(6), None);
    

13.4.10-last

  • last 方法:使用闭包消费迭代器每一项,直到闭包返回 None,然后返回最后一项。如果迭代器不产生任何项,则 last 方法会返回 None

    fn last(self) -> Option<Self::Item>;
    
  • 举例:

    let squares = (0..10).map(|i| i * i);
    assert_eq!(squares.last(), Some(81));
    
  • 如果迭代器是可逆的,又不需要消费其所有项,则可以用 iter.rev().next() 代替实现。

13.4.11-find

  • find 方法:从迭代器中取得第一个返回 true 的值,或者如果没有找到合适的项则返回 None

    fn find<P>(&mut self, predicate: P) -> Option<Self::Item>
        where Self: Sized, P: FnMut(&Self:: Item) -> bool;
    
  • 举例:

    assert_eq!(populations.iter().find(|&(_name, &pop)| pop > 1_000_000), None);
    assert_eq!(populations.iter().find(|&(_name, &pop)| pop > 500_000),
        Some((&"Portland", &583_776)));
    

13.4.12 - 构建集合

  • collect 方法:构建保存迭代器项的集合。

    let args: Vec<String> = std::env::args().collect();  // 构建向量
    
    use std::collections::{
          HashSet, BtreeSet, LinkedList, HashMap, BTreeMap};
    // 构建其他任何集合
    let args: HashSet<String> = std::env::args().collect();
    let args: BTreeSet<String> = std::env::args().collect();
    let args: LinkedList<String> = std::env::args().collect();
    
    // 汇集映射需要(key,value)对,因此对这个例子,可以用zip为字符串添加整数索引
    let args: HashMap<String, usize> = std::env::args().zip(0..).collect();
    let args: BTreeMap<String, usize> = std::env::args().zip(0..).collect();
    
    • collect 的返回类型是其类型参数,因此上述 VecHashSet 的调用相当于:

      let args = std::env::args().collect::<Vec<String>>();
      let args = std::env::args().collect::<HashSet<String>>();
      
  • FromIterator 方法:

    • collect 本身不知道如何构建上述集合类型。

    • 相反 VecHashMap 等集合类型知道如何基于迭代器构建自己,因为它们实现了 std::iter::FromIterator 特型。

      trait FromIterator<A>: Sized {
              
          fn from_iter<T: IntoIterator<Item=A>>(iter: T) -> Self
      }
      
    • 如果某个集合类型实现了 FromIterator<A>,那么其静态方法 from_iter 就可以基于产生类型 A 的可迭代类型构建该类型的值。

  • Iterator 特型的 size_hint 方法:返回迭代器产生项数的下限值和可选的上限值。

    • 默认定义返回 0 作为下限值,不给出上限值。
    • 可以让 VecFromIterator 的实现,为新向量缓冲区分配正确的大小提供必要的信息。
    • HashSetHashMap 也会使用 Iterator::size_hint 为自己的散列表创建适当的初始大小。
    trait Iterator{
          
        ...
        fn size_hint(&self) -> (usize, Option<usize>) {
          
            (0, None)
        }
    }
    

13.4.13-Extend 特型

  • 所有标准库集合都实现了 std::iter::Extend 特型:

    trait Extend<A> {
          
        fn extend<T>(&mut self, iter: T) where T: IntoIterator<Item=A>;
    }
    
    • extend() 方法可以将一个迭代器的项添加到集合中:

      let mut v: Vec<i32> = (0..5).map(|i| 1 << i).collect();
      v.extend(&[31, 57, 99, 163]);
      assert_eq!(v, &[1, 2, 4, 8, 16, 31, 57, 99, 163]);
      
    • 固定长度的数组和切片不支持这个方法

  • FromIterator 用于创建一个新集合,而 Extend 用于实现扩展现有集合。

    • 标准库中的一些 FromIterator 实现,就是先创建一个空集合,然后用 extend 方法填充这个集合。

    • 例如 std::collections::LinkedList 的实现:

      impl<T> FromIterator<T> for LinkedList<T> {
              
          fn from_iter<I: IntoIterator<Item=T>>(iter: I) -> Self {
              
              let mut list = Self::new();
              list.extend(iter);
              list
          }
      }
      

13.4.14-partition

  • partition 方法:把一个迭代器的项分成两个集合,然后使用闭包决定哪一项属于哪个集合。

    • partition 可以生成任何两个相同类型的集合。

    • partition 必须指定返回类型,让类型推断可以选择调用正确的类型参数。

      fn partition<B, F>(self, f: F) -> (B, B) 
          where Self: Sized,
                B: Default + Extend<Self::Item>,
                F: FnMut(&Self::Item) -> bool;
      
    • collect 要求其结果类型实现 FromIterator

    • partition 要求其结果类型实现 std::default::Defaultstd::default::Extend

    • 所有 Rust 集合的 std::default::Default 实现都是返回一个空集合。

  • 举例:

    let things = ["doorknob", "mushroom", "noodle", "giraffe", "grapefruit"];
    
    // 找出首字母是第n个字母,n为奇数。
    let (living, nonliving): (Vec<&str>, Vec<&str>) = 
        things.iter().partition(|name| name.as_bytes()[0] & 1 != 0);
    
    assert_eq!(living, vec!["mushroom", "giraffe", "grapefruit"]);
    assert_eq!(nonliving, vec!["doorknob", "noodle"]);
    
  • 把一个迭代器切分成两个,需要两部分共享同一个底层迭代器,而迭代器必须可以修改才能使用。底层迭代器必须共享且可修改,这对 Rust 来说是违背安全准则的。

    • 所以,partition 方法把迭代器分成两个集合,而不是两个迭代器。
    • 从底层迭代器中取出(但还没有从切分后的迭代器中取出)的值,需要先缓存在集合中。

13.5 - 给自定义类型实现迭代器

  • 自定义类型也可以实现 IntoIteratorIterator 特型:

    • 支持上述所有适配器和消费者。
    • 同时也可以支持使用标准迭代器接口的第三方库。
  • 举例 1:基于一个范围类型实现简单的迭代器。

    • 定义一个范围类型(std::ops::Range<T> 类型的简化版):

      // 迭代I32Range需要两个状态:
      // ===> 当前值:使用start作为下一个值。
      // ===> 结束迭代的限制条件:使用end作为限制条件。
      struct I32Range {
              
          start: i32,
          end: i32
      }
      
    • 实现 Iterator 特型:

      impl Iterator for I32Range {
              
          type Item = i32;
          fn next(&mut self) -> Option<i32> {
              
              if self.start >= self.end {
              
                  return None; // 结束条件
              }
              let result = Some(self.start);
              self.start += 1;
              result  // 返回值
          }
      }
      
    • 标准库为每个实现了 Iterator 的类型,都提供了对应的 IntoIterator 的通用实现,因此 I32Range 可以直接被使用:

      let mut pi = 0.0;
      mit mut numerator = 1.0;
      
      for k in (I32Range {
               start: 0, end: 14 }) {
              
          pi += numerator / (2*k + 1) as f64;
          numerator /= -3.0
      }
      pi *= f64::sqrt(12.0);
      
      // IEEE 754明确定义了PI
      assert_eq!(pi as f32, std::f32::consts::PI);
      
    • I32Range 的可迭代类型和迭代器都是同一种类型。

  • 举例 2:基于一个二叉树类型实现较复杂的迭代器。

    • 创建一个二叉树类型:

      enum BinaryTree<T> {
              
          Empty,
          NonEmpty(Box<TreeNode<T>>)
      }
      
      struct TreeBode<T> {
              
          element: T,
          left: BinaryTree<T>,
          right: BinaryTree<T>
      }
      
    • 遍历二叉树的经典方式是使用递归:通过函数调用栈,跟踪数中的位置和还未访问的节点。

    • 在为 BinaryTree<T> 实现 Iterator 时,每次调用 next 必须实现产生并返回一个值。为跟踪还未产生的树节点,迭代器必须维护自己的栈。

    • 针对 BinaryTree 实现一个迭代器类型:

      use self::BinaryTree::*;
      
      // 对BinaryTree执行按序迭代
      struct TreeIter<'a, T: 'a> {
              
          // 树节点应用的栈。
          // 因为使用Vec的push和pop方法,所以栈顶是向量的末尾。
          //
          // 节点迭代器将从栈顶取得下一个值,未访问的祖先节点在下面。
          // 如果栈空了,则迭代结束
          unvisited: Vec<&'a TreeNode<T>>
      }
      
    • 常见的操作是定义一个辅助方法:将子树左边的节点推到栈里:

      impl<'a, T: 'a> TreeIter<'a, T> {
              
          fn push_left_edge(&mut self, mut tree: &'a BinaryTree<T>) {
              
              while let NonEmpty(ref node) = *tree {
              
                  self.unvisited.push(node);
                  tree = &node.left;
              }
          }
      }
      
    • 接下来可以为 BinaryTree 定义 iter 方法,返回树的迭代器:

      impl<T> BinaryTree<T> {
              
          // 构建一个空TreeIter,然后调用push_left_edge来填充初始的栈。
          // 按照unvisited栈的规则,最左边的节点在上面。
          fn iter(&self) -> TreeIter<T> {
              
              let mut iter = TreeIter {
               unvisited: Vec::new() };
              iter.push_left_edge(self);
              iter
          }
      }
      
    • 参考标准库的实现,在树的一个共享引用上实现 IntoIterator,可以调用 BinaryTree::iter,返回一个迭代器:

      impl<'a, T: 'a>  IntoIterator for &'a BinaryTree<T> {
              
          type Item = &'a T;
          type IntoIter = TreeIter<'a, T>; // 将TreeIter作为&BinaryTree的迭代器类型
          fn into_iter(self) -> Self::IntoIter {
              
              self.iter()
          }
      }
      
    • 迭代器的 next 方法同样按照栈的规则行事:

      impl<'a, T> Iterator for TreeIter<'a, T> {
              
          type Item = &'a T;
          fn next(&mut self) -> Option<&'a T> {
              
              // 查找迭代必须产生的节点,或者结束迭代。
              let node = match self.unvisited.pop() {
              
                  None => return None;
                  Some(n) => n
              };
      
              // 如果节点有右子树,当前节点后面的下一个节点,是当前节点右子节点的最左子节点
              // 把它推进栈里
              self.push_left_edge(&node.right);
      
              // 产生对节点值的引用
              Some(&node.element)
              // 如果栈空了,则迭代结束。
              // 否则,node就是对当前节点的引用,而调用会返回对其element字段的引用。
          }
      }
      
    • 接下来就可以使用 for 循环按引用迭代 BinaryTree

      fn make_node<T>(left: BinaryTree<T>, element: T, right: BinaryTree<T>)
          -> BinaryTree<T>
      {
              
          NonExpty(Box::new(TreeNode {
               left, element, right }))
      }
      
      fn main() {
              
          // 构建一棵树
          let subtree_l = make_node(Empty, "mecha", Empty);
          let subtree_rl = make_node(Empty, "droid", Empty);
          let subtree_r = make_node(subtree_l, "robot", Empty);
          let tree = make_node(subtree_l, "Jaeger", subtree_r);
      
          // 迭代树
          let mut v = Vec::new();
          for kind in &tree {
              
              v.push(*kind);
          }
          assert_eq!(v, ["mecha", "Jaeger", "droid", "robot"]);
      }
      
    • 所有常用的迭代器适配器和消费者,都可以在这个树上使用:

      assert_eq!(
          tree.iter()
          .map(|name| format!("mega-{}", name))
          .collect::<Vec<_>>(),
          vec!["mega-mecha", "mega-Jaeger", "mega-droid", "mega-robot"]
      );
      

详见《Rust 程序设计》(吉姆 - 布兰迪、贾森 - 奥伦多夫著,李松峰译)第十五章
原文地址

原网站

版权声明
本文为[phial03]所创,转载请带上原文链接,感谢
https://blog.csdn.net/feiyanaffection/article/details/125574968