当前位置：网站首页>[rust notes] 13 iterator (Part 2)

[rust notes] 13 iterator (Part 2)

2022-07-05 06:03:00 【phial03】

13.4 - Consumer iterators

13.4.1 - Simple accumulation

count Method ： Take values from an iterator , Until it returns None, Then tell you how many items this iterator contains .

use std::io::prelude::*;

fn main() {
      
    let stdin = std::io::stdin();
    println!("{}", stdin.lock().lines().count());
}

sum Method ： Used to calculate iterator items （ Must be an integer or floating point number ） And .

product Method ： Used to calculate iterator items （ Must be an integer or floating point number ） Product of .

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-`max` and `min`

Iterator Special max and min Method returns the maximum and minimum values of the items generated by the iterator . The item type of the iterator must implement std::cmp::Ord, In this way, items can be compared with each other .
```
assert_eq!([-2, 0, 1, 0, -2, -5].iter().max(), Some(&1));
assert_eq!([-2, 0, 1, 0, -2, -5].iter().min(), Some(&-5));
```
These two methods return Option<Self::Item>, Therefore, when the iterator does not produce an item, it returns None.
Floating point type f32 and f64 only std::cmp::PartialOrd, It didn't come true std::cmp::Ord, Therefore, the above two methods cannot be used .

13.4.3-`max_by` and `min_by`

max_by and min_by Method according to the custom comparison method provided , Returns the maximum and minimum values generated by the iterator .

use std::cmp::{
      PartialOrd, Ordering};

//  Compare the two f64 Value , If you include NAN Is surprised 
fn cmp(lhs: &&f64, rhs: &&f64) -> Ordering {
      
    lhs.partial_cmp(rhs).unwrap()
}

let numbers = [1.0, 4.0, 2.0];                 //  Sequence does not contain NAN Comparison 
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];  //  The sequence contains NAN Comparison 
assert_eq!(numbers.iter().max_by(cmp), Some(&4.0));  //  There will be surprise during the comparison

&&f64 Use double quotation , Because numbers.iter() Will generate a reference to the element , then max_by and min_by Pass the reference of iterator item to closure .

13.4.4-`max_by_key` and `min_by_key`

Iterator Of max_by_key and min_by_key Methods can be based on the closure applied to each item , Select the largest or smallest item .

///  Take each item as a parameter for a given , And return the ordered type B The closure of ,
///  They return to   The closure returns B Maximum or minimum   The item .
///  If no item is generated , Then return to 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;

Closures can select a field of an item , Or perform some calculations for each item .
Just care about the data associated with the largest or smallest item .

give an example ： From the hash table of a city, find the city with the largest and smallest population ：

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)));

Closure |&(_name, pop)| pop Will be applied to every item produced by the iterator , The returned value is used for comparison .
The population returned here . The returned value is the entire item , Instead of the value returned by the closure .

13.4.5 - Comparison item sequence

For strings 、 Vectors and slices , have access to >、< and == Operator comparison .
For iterators , have access to eq and lt And other methods to achieve the same function . Get the paired items from the iterator , And then compare them , Until a decision can be made ：
- eq and ne Method is used for equality comparison ;
- lt、le、gt and ge Method is used for order comparison .
- cmp and partial_cmp Method , And Ord and PartialOrd The corresponding method on the special type is similar .
```
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()));

//  return true, because  ' ' < 'o'
assert!(spaced < obscure);

//  return true,  because 'Troy' > 'Sandusky'
assert!(spaced.split_whitespace().gt(obscure.split_whitespace()));
```
- This is called split_whitespace() Method , You can return the iterator to generate the word obtained by dividing the string with spaces .
- Make the call eq and gt Method , Can perform word to word comparisons , Instead of comparing characters .
- because &str Realized PartialOrd and PartialEq Special type .

13.4.6-`any` and `all`

any Method ： Give each application closure generated by the iterator , If the closure returns true, Then the method returns true.
all Method ： Give each application closure generated by the iterator , If the closure returns for all items true, Then the method returns true
```
let id = "Iterator";

assert!(id.chars().any(char::is_uppercase));
assert!(!id.chars().all(char::is_uppercase));
```

13.4.7-`position`、`rposition` and `ExactSizeIterator`

position Method ： Give each application closure generated by the iterator , The return value is one Option Type value ：
- If the closure does not return any items true, Then the method returns None.
- As long as the closure returns true,position Stop taking values , And return the index of the item .
```
let text = "Xerxes";

assert_eq!(text.chars().position(|c| c == 'e'), Some(1));
assert_eq!(text.chars().position(|c| c == 'z'), None);
```
rposition Method ： Function and position identical , Just search from the right .
- The iterator required is a reversible iterator , In this way, the value can be taken from the right end of the iterator .
- The iterator size is required to be fixed , In this way, it can be like position Then assign values to the index , Also take the leftmost item as 0.
- Cannot use... On a string rposition. Use... On strings b Mark , Make the string convert to byte array .
```
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));
```

Fixed size iterators , It means it's done std::iter::ExactSizeIterator Special iterators ：

pub trait ExactSizeIterator: Iterator {
      
    fn len(&self) -> usize {
       ... }
    fn is_empty(&self) -> bool {
       ... }
}

len Method returns the number of remaining items .
is_empty Method returns true.

13.4.8-`fold`

fold Method ： Perform a cumulative operation on the entire sequence of items generated by the iterator .
- Receive an accumulator （accumulator） And a closure ,
- Then apply the closure repeatedly to the next item of the current accumulator and iterator .
- The return value of each closure will become the new value of the accumulator , And then with the next item of the iterator , Pass it to the closure .
- Return value ： The final value of the accumulator is also fold Return value of method . If the sequence is empty , be fold Returns the initial value of the accumulator .
fold Method signature ：
```
fn fold<A, F>(self, init: A, f: F) -> A
    where Self: Sized, F: FnMut(A, Self::Item) -> A;
```
- A It's the type of accumulator .
- init The parameter is one A, I.e. accumulator .
- The first parameter and return value of the closure are A.

Many other methods of iterators can be written using fold In the form of ：

let a = [5, 6, 7, 8, 9, 10];

assert_eq!(a.iter().fold(0, |n, _| n + 1),  6);       //  Realization count
assert_eq!(a.iter().fold(0, |n, i| n + i),  45);      //  Realization sum
assert_eq!(a.iter().fold(1, |n, i| n * i),  151200);  //  Realization product
assert_eq!(a.iter().fold(i32::min_value(), |m, &i| std::cmp::max(m, i)), 10);// Realization max

The value of the accumulator will be transferred to the closure , Then transfer it out . Therefore, we can be right and wrong Copy Type accumulator uses fold Method ：

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 Method ： Receive an index value n, Then skip the corresponding item in the iterator , Return the item corresponding to the index .
- If the sequence ends before , Then return to None.
- call .nth(0) Equivalent to calling .next().
```
fn nth(&mut self, n: usize) -> Option<Self::Item> where Self: Sized;
```

nth Will not take ownership of the iterator , Therefore, you can call ：

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 Method ： Use closures to consume each item of the iterator , Until the closure returns None, Then return to the last item . If the iterator does not produce any items , be last Method will return None.
```
fn last(self) -> Option<Self::Item>;
```

give an example ：

let squares = (0..10).map(|i| i * i);
assert_eq!(squares.last(), Some(81));

If the iterator is reversible , It doesn't need to consume all its items , You can use iter.rev().next() Instead of realizing .

13.4.11-`find`

find Method ： Get the first return from the iterator true Value , Or if no suitable item is found, return None.

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

give an example ：

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 - Build collections

collect Method ： Build a collection that holds iterator items .

let args: Vec<String> = std::env::args().collect();  //  Construct vector 

use std::collections::{
      HashSet, BtreeSet, LinkedList, HashMap, BTreeMap};
//  Build any other collection 
let args: HashSet<String> = std::env::args().collect();
let args: BTreeSet<String> = std::env::args().collect();
let args: LinkedList<String> = std::env::args().collect();

//  Aggregation mapping requires （key,value） Yes , So for this example , It can be used zip Add an integer index to the string 
let args: HashMap<String, usize> = std::env::args().zip(0..).collect();
let args: BTreeMap<String, usize> = std::env::args().zip(0..).collect();

collect The return type of is its type parameter , So the above Vec and HashSet The call of is equivalent to ：

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

FromIterator Method ：
- collect I don't know how to build the above set type .
- contrary Vec or HashMap And other collection types know how to build themselves based on iterators , Because they achieve std::iter::FromIterator Special type .
```
trait FromIterator<A>: Sized {
        
    fn from_iter<T: IntoIterator<Item=A>>(iter: T) -> Self
}
```
- If a collection type implements FromIterator<A>, Then its static method from_iter Based on the generation type A The iteratable type of builds the value of that type .
Iterator Special size_hint Method ： Returns the lower limit and optional upper limit of the number of items generated by the iterator .
- The default definition returns 0 As the lower limit , No upper limit is given .
- It can make Vec Yes FromIterator The implementation of the , Provide the necessary information for allocating the correct size of the new vector buffer .
- HashSet and HashMap You can also use Iterator::size_hint Create an appropriate initial size for your hash table .
```
trait Iterator{
      
    ...
    fn size_hint(&self) -> (usize, Option<usize>) {
      
        (0, None)
    }
}
```

13.4.13-`Extend` Special type

All standard library collections are implemented std::iter::Extend Special type ：

trait Extend<A> {
      
    fn extend<T>(&mut self, iter: T) where T: IntoIterator<Item=A>;
}

extend() Method can add the item of an iterator to the collection ：

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]);

Fixed length arrays and slices do not support this method .

FromIterator Used to create a new set , and Extend Used to extend existing collections .
- Some in the standard library FromIterator Realization , Is to create an empty set first , And then use extend Method to populate this collection .
- for example std::collections::LinkedList The implementation of the ：
```
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 Method ： Divide the items of an iterator into two sets , Then use closures to decide which item belongs to which set .
- partition You can generate any two collections of the same type .
- partition Return type... Must be specified , Let type inference choose to call the correct type parameters .
```
fn partition<B, F>(self, f: F) -> (B, B) 
    where Self: Sized,
          B: Default + Extend<Self::Item>,
          F: FnMut(&Self::Item) -> bool;
```
- collect The result type is required to realize FromIterator;
- partition The result type is required to realize std::default::Default and std::default::Extend.
- all Rust A collection of std::default::Default All implementations return an empty set .

give an example ：

let things = ["doorknob", "mushroom", "noodle", "giraffe", "grapefruit"];

//  Find out that the first letter is n Letters ,n It's odd .
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"]);

Cut an iterator into two , Two parts need to share the same underlying iterator , Iterators must be modifiable to use . The underlying iterators must be shared and modifiable , This is right Rust It is against the safety rules .
- therefore ,partition Method divides the iterator into two sets , Instead of two iterators .
- Take it out of the underlying iterator （ But it has not been taken out of the segmented iterator ） Value , It needs to be cached in the set first .

13.5 - Implement iterators for custom types

Custom types can also be implemented IntoIterator and Iterator Special type ：
- Support all adapters and consumers mentioned above .
- It also supports third-party libraries that use standard iterator interfaces .

give an example 1： Implement a simple iterator based on a range type .

Define a scope type （std::ops::Range<T> Simplified version of type ）：

//  iteration I32Range Two states are required ：
// ===>  Current value ： Use start As the next value .
// ===>  Constraints for ending iterations ： Use end As a condition of limitation .
struct I32Range {
        
    start: i32,
    end: i32
}

Realization Iterator Special type ：

impl Iterator for I32Range {
        
    type Item = i32;
    fn next(&mut self) -> Option<i32> {
        
        if self.start >= self.end {
        
            return None; //  The end condition 
        }
        let result = Some(self.start);
        self.start += 1;
        result  //  Return value 
    }
}

The standard library implements Iterator The type of , All provide corresponding IntoIterator General implementation of , therefore I32Range Can be used directly ：

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 Clearly defined PI
assert_eq!(pi as f32, std::f32::consts::PI);

I32Range The iteratable type and iterator of are the same type .

give an example 2： Implement a more complex iterator based on a binary tree type .

Create a binary tree type ：

enum BinaryTree<T> {
        
    Empty,
    NonEmpty(Box<TreeNode<T>>)
}

struct TreeBode<T> {
        
    element: T,
    left: BinaryTree<T>,
    right: BinaryTree<T>
}

The classic way to traverse a binary tree is to use recursion ： Through the function call stack , Track the location in the number and the nodes that have not been visited .
For BinaryTree<T> Realization Iterator when , Every time you call next You must generate and return a value . For tracking tree nodes that have not yet been generated , Iterators must maintain their own stack .

in the light of BinaryTree Implement an iterator type ：

use self::BinaryTree::*;

//  Yes BinaryTree Perform sequential iterations 
struct TreeIter<'a, T: 'a> {
        
    //  Stack of tree node applications .
    //  Because use Vec Of push and pop Method , So the top of the stack is the end of the vector .
    //
    //  The node iterator will get the next value from the top of the stack , The unreached ancestor nodes are below .
    //  If the stack is empty , End of iteration 
    unvisited: Vec<&'a TreeNode<T>>
}

A common operation is to define an auxiliary method ： Push the node on the left of the subtree to the stack ：

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;
        }
    }
}

Next, you can BinaryTree Definition iter Method , Returns the iterator of the tree ：

impl<T> BinaryTree<T> {
        
    //  Build an empty TreeIter, And then call push_left_edge To fill the initial stack .
    //  according to unvisited The rules of the stack , The leftmost node is above .
    fn iter(&self) -> TreeIter<T> {
        
        let mut iter = TreeIter {
         unvisited: Vec::new() };
        iter.push_left_edge(self);
        iter
    }
}

Implementation of reference standard library , Implement on a shared reference of the tree IntoIterator, You can call BinaryTree::iter, Returns an iterator ：

impl<'a, T: 'a>  IntoIterator for &'a BinaryTree<T> {
        
    type Item = &'a T;
    type IntoIter = TreeIter<'a, T>; //  take TreeIter As &BinaryTree The iterator type of 
    fn into_iter(self) -> Self::IntoIter {
        
        self.iter()
    }
}

Iterator next Methods also act according to the rules of the stack ：

impl<'a, T> Iterator for TreeIter<'a, T> {
        
    type Item = &'a T;
    fn next(&mut self) -> Option<&'a T> {
        
        //  Find the nodes that the iteration must produce , Or end the iteration .
        let node = match self.unvisited.pop() {
        
            None => return None;
            Some(n) => n
        };

        //  If the node has a right subtree , The next node after the current node , It is the leftmost child node of the right child node of the current node 
        //  Push it into the stack 
        self.push_left_edge(&node.right);

        //  Generate a reference to the node value 
        Some(&node.element)
        //  If the stack is empty , End of iteration .
        //  otherwise ,node Is the reference to the current node , And the call will return to its element References to fields .
    }
}

You can use for Loop iterates by reference BinaryTree：

fn make_node<T>(left: BinaryTree<T>, element: T, right: BinaryTree<T>)
    -> BinaryTree<T>
{
        
    NonExpty(Box::new(TreeNode {
         left, element, right }))
}

fn main() {
        
    //  Build a tree 
    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);

    //  Iterative tree 
    let mut v = Vec::new();
    for kind in &tree {
        
        v.push(*kind);
    }
    assert_eq!(v, ["mecha", "Jaeger", "droid", "robot"]);
}

All commonly used iterator adapters and consumers , Can be used on this tree ：

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