关于rust:Rust之美迭代器在算法中的应用

前言

在本文中咱们将从一个简略的算法题引出 Rust 语言中迭代器相干的几个办法，帮忙大家了解 chars,all ,try_fold,enumerate,try_for_each,char_indices 的用法。

题目如下

咱们定义，在以下状况时，单词的大写用法是正确的：
援用
全副字母都是大写，比方 “USA”。
单词中所有字母都不是大写，比方 “leetcode”。
如果单词不只含有一个字母，只有首字母大写，比方 “Google”。
给你一个字符串 word。如果大写用法正确，返回 true；否则，返回 false。
援用
起源：力扣（LeetCode）
链接：https://leetcode-cn.com/probl…
著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。

剖析
依据题意，满足条件的字符串就是

要么字符串中的字符都是小写；
要么都是大写；
要么第一个是大写，剩下的是小写。

原始的解法
依据下面的剖析，咱们只须要做上面三个判断就能够了

word 中字符如果都是大写，返回 true
word 中字符是否都是小写，返回 true
word 中首字符大写且残余字符小写，返回 true
其它状况返回 false

pub fn detect_capital_use(word: String) -> bool {if word.len() < 2 {return true;}

    // 判断都是大写
    let mut res = true;
    for c in word.as_bytes() {if c.is_ascii_lowercase() {
            res = false;
            break;
        }
    }
    if res {return res;}

    // 判断都是小写
    let mut res = true;
    for c in word.as_bytes() {if c.is_ascii_uppercase() {
            res = false;
            break;
        }
    }
    if res {return res;}

    // 判断首字母大写，残余小写
    if word.as_bytes()[0].is_ascii_lowercase() {return false;}
    let mut res = true;
    for c in &word.as_bytes()[1..] {if c.is_ascii_uppercase() {
            res = false;
            break;
        }
    }
    if res {return res;}

    false
}

应用迭代器
下面的代码中应用了三次遍历，如果应用 Rust 中的迭代器，能够十分简洁，对应代码如下：

pub fn detect_capital_use(word: String) -> bool {if word.len() ==0{return true}
    if word.len() ==1{return true}

    let mut word1 = word.chars(); // 返回 word 中字符的迭代器
    if word1.all(|x|x.is_lowercase()){ // 都是小写
        return true 
    }

    let mut word1 = word.chars();
    if word1.all(|x|x.is_uppercase()){ // 都是大写
        return true 
    }

    let mut word1 = word.chars();
    let first_word = word1.next().unwrap();// 获取第一个字符
    if first_word.is_lowercase(){  // 首字符大写
        return false
    }
    if word1.all(|x|x.is_lowercase()){ // 剩下的小写
        return true 
    }

    false

}

代码剖析
下面代码中咱们应用.chars()办法失去 String 的字符迭代器，而后利用了 rust 中迭代器的 all 办法实现了该性能，整个代码逻辑十分贴合人类的自然语言，可读性十分强。上面咱们先介绍下 all 办法：迭代器的 all 办法用来判断迭代器所遍历的所有项是否满足闭包的条件

Tests if every element of the iterator matches a predicate.
all() takes a closure that returns true or false. It applies this closure to each element of the iterator, and if they all return true, then so does all(). If any of them return false, it returns false.
all() is short-circuiting; in other words, it will stop processing as soon as it finds a false, given that no matter what else happens, the result will also be false.
An empty iterator returns true.

翻译过去就是

判断迭代器中的每一个元素是否满足断言（也就是传入的闭包函数）。
all() 承受一个闭包作为参数，这个闭包返回 true 或 false。all() 在迭代器遍历过程中，把每一个元素传入闭包，如果所有的元素传入闭包中都返回 true，那么 all() 就返回 true，否则 all() 返回 false。
all() 是短路；换句话说，在遍历的过程中，一旦某个元素传入闭包后返回 false，就会立即进行遍历，无论前面元素的后果是什么，最终 all() 的后果是 false
一个空的迭代器的 all() 永远返回 true

all() 对应的源码如下：

#[inline]
    #[stable(feature = "rust1", since = "1.0.0")]
    fn all<F>(&mut self, f: F) -> bool
    where
        Self: Sized,
        F: FnMut(Self::Item) -> bool,
    {#[inline]
        fn check<T>(mut f: impl FnMut(T) -> bool) -> impl FnMut((), T) -> ControlFlow<()> {move |(), x| {if f(x) {ControlFlow::CONTINUE} else {ControlFlow::BREAK}
            }
        }
        self.try_fold((), check(f)) == ControlFlow::CONTINUE
    }

能够看到 all 办法外部起始是应用了 try_fold() 来实现。下面咱们提到 all() 是短路的，就是应用了 try_fold 的个性。

首先 all 办法将传入的闭包 f 封装成 impl FnMut((), T) -> ControlFlow<()> 类型的新闭包，这个新闭包在 f(x) 为 true 的时候返回 ControlFlow::CONTINUE，在为 false 的时候返回 ControlFlow::BREAK，而 try_fold() 在闭包函数返回 ControlFlow::BREAK 的时候就会提前退出，实现短路的性质。
try_fold() 如果最终返回 ControlFlow::CONTINUE，示意所有的元素执行 f(x)返回 true，如果返回 ControlFlow::BREAK 示意两头遇到了一个元素执行 f(x)返回 false.

接下来咱们再认真看下 try_fold 这个办法：

An iterator method that applies a function as long as it returns successfully, producing a single, final value.
try_fold() takes two arguments: an initial value, and a closure with two arguments: an‘accumulator’, and an element. The closure either returns successfully, with the value that the accumulator should have for the next iteration, or it returns failure, with an error value that is propagated back to the caller immediately (short-circuiting).
The initial value is the value the accumulator will have on the first call. If applying the closure succeeded against every element of the iterator, try_fold() returns the final accumulator as success.
Folding is useful whenever you have a collection of something, and want to produce a single value from it.

翻译过去就是

try_fold 这个办法在迭代器上利用一个函数，如果这个函数统一返回胜利，就继续执行直到返回一个最终的值，如果失败就提前退出。
try_fold 承受两个参数，第一个参数是初始值，第二个参数是一个闭包，而这个闭包须要传入两个参数：一个累加值，一个元素值。这个闭包如果返回胜利的话，就会返回下次运算所需的累加值，如果返回失败，就会立即将谬误的值间接返回到调用者中（短路）
初始值是第一次闭包调用时候应用的累加值。如果迭代器中每一个元素利用到闭包上后就胜利，那么 try_fold()执行完结后就会返回最总的累加值。
当你有一个元素的机制，须要从这个汇合中失去单个值的时候，Fold 就会很有用。

try_fold 的源码如下，也比较简单

#[inline]
    #[stable(feature = "iterator_try_fold", since = "1.27.0")]
    fn try_fold<B, F, R>(&mut self, init: B, mut f: F) -> R
    where
        Self: Sized,
        F: FnMut(B, Self::Item) -> R,
        R: Try<Output = B>,
    {
        let mut accum = init;
        while let Some(x) = self.next() {accum = f(accum, x)?;
        }
        try {accum}
    }

能够看到 try_fold 外部通过迭代器的 next 办法一直获取迭代器中的每一个元素，执行函数 f，accum = f(accum, x)?;，其中？是 rust 中的一个特殊符号，示意如果 f(accum,x) 返回 ControlFlow::BREAK 就退出以后循环并且将 ControlFlow::BREAK 作为 try_fold 的返回值。

简化全小写，全大写判断

下面代码中，判断 word 是否都是小写的逻辑判断，分为了两行，先通过 chars 获取迭代器，而后调用 all 办法判断是否都是小写，这块代码能够间接用一行代码代替 word.chars().all(|x|x.is_lowercase()), 判断 word 都是大写的判断同理，如下：

pub fn detect_capital_use(word: String) -> bool {if word.len() ==0{return true}
    if word.len() ==1{return true}

    if word.chars().all(|x|x.is_lowercase()){ // 如果都是小写
        return true 
    }

    if word.chars().all(|x|x.is_uppercase()){ // 如果都是大写
        return true 
    }

    let mut word1 = word.chars();
    let first_word = word1.next().unwrap(); // 获取第一个字符
    if first_word.is_lowercase(){  // 如果第一个字符是小写，返回 false
        return false
    }
    if word1.all(|x|x.is_lowercase()){  // 剩下的都是小写，返回 true
        return true 
    }

    false

}

简化首字符大写，其它小写的判断

因为.chars 失去的迭代器在遍历中只会返回每一个元素，并不会返回在原先汇合中的索引值，所以咱们先调用 next 获取第一个字符判断是否是大写，而后再用 all 判断剩下的字符是否都是小写。如果咱们能够同时获取索引和元素值，那么就能够在 all 的闭包中同时判断首字符和其它字符了。为了获取蕴含索引的迭代器，咱们能够采纳 enumerate 对迭代器进行封装，代码如下：

pub fn detect_capital_use(word: String) -> bool {if word.len() == 0 {return true;}
    if word.len() == 1 {return true;}

    if word.chars().all(|x| x.is_lowercase()) {// 如果都是小写
        return true;
    }

    if word.chars().all(|x| x.is_uppercase()) {// 如果都是大写
        return true;
    }

    if word.chars().enumerate().all(|(id, x)| {
        if id == 0 {x.is_uppercase()  // 第一个字符是大写
        } else {x.is_lowercase()  // 剩下的都是小写
        }
    }) {return true;}

    false
}

能够看到 enumerate()每次迭代返回的元素是一个元组，元组的第一个元素就是索引值，咱们就能够依据索引值和元素值判断了。enumerate()的办法返回的 Enumerate 类型的新的迭代器，对应源码如下：

pub struct Enumerate<I> {
    iter: I,
    count: usize,
}
impl<I> Enumerate<I> {pub(in crate::iter) fn new(iter: I) -> Enumerate<I> {Enumerate { iter, count: 0}
    }
}

#[stable(feature = "rust1", since = "1.0.0")]
impl<I> Iterator for Enumerate<I>
where
    I: Iterator,
{type Item = (usize, <I as Iterator>::Item);

    /// # Overflow Behavior
    ///
    /// The method does no guarding against overflows, so enumerating more than
    /// `usize::MAX` elements either produces the wrong result or panics. If
    /// debug assertions are enabled, a panic is guaranteed.
    ///
    /// # Panics
    ///
    /// Might panic if the index of the element overflows a `usize`.
    #[inline]
    #[rustc_inherit_overflow_checks]
    fn next(&mut self) -> Option<(usize, <I as Iterator>::Item)> {let a = self.iter.next()?;
        let i = self.count;
        self.count += 1;
        Some((i, a))
    }

    ...
}

能够看到 Enumerate 次要是将之前的迭代器进行了封装，而后外部保护了一个 count 来记录索引，在每次 next 的时候更新并作为元组的第一个元素返回。将代码中三个逻辑判断合并失去：

pub fn detect_capital_use(word: String) -> bool {if word.len() == 0 {return true;}
    if word.len() == 1 {return true;}

    if word.chars().all(|x| x.is_lowercase()) // 如果都是小写
        || word.chars().all(|x| x.is_uppercase())// 如果都是小写
        || word.chars().enumerate().all(|(id, x)| {
            if id == 0 {x.is_uppercase() // 第一个字符是大写
            } else {x.is_lowercase() // 第二个字符是小写
            }
        })
    {return true;}

    false
}

因为空的迭代器的 all 永远返回 true，下面的 word 长度的判断也能够省略，失去：

pub fn detect_capital_use(word: String) -> bool {if word.chars().all(|x| x.is_lowercase()) // 
        || word.chars().all(|x| x.is_uppercase())
        || word.chars().enumerate().all(|(id, x)| {
            if id == 0 {x.is_uppercase()
            } else {x.is_lowercase()
            }
        })
    {return true;}

    false
}

另外 word.chars().enumerate()也能够间接简写为 word.char_indices(), 所以下面代码进一步可写为

pub fn detect_capital_use(word: String) -> bool {if word.chars().all(|x| x.is_lowercase()) // 
        || word.chars().all(|x| x.is_uppercase())
        || word.char_indices().all(|(id, x)| {
            if id == 0 {x.is_uppercase()
            } else {x.is_lowercase()
            }
        })
    {return true;}

    false
}

三次遍历变为一次遍历
下面的算法对于首字母大写的状况会导致三次遍历，进一步能够优化

判断除首字母之外剩下的字母是否都是小写或都是大写，具体实现：判断和第二个字母的大小写是否统一
如果剩下的大小写不一样，间接返回 false
而后再依据第一个字母，第二个字母判断
如果第一个字母是大写，返回 true。对于都是大写，或首字母大写
如果如果第一个字母和第二个字母都是小写，返回 true。对应都是小写的请。
返回 false

代码如下：

pub fn detect_capital_use(word: String) -> bool {let mut word = word.chars();
    let first = word.next();
    if first.is_none(){return true}
    let first = first.unwrap();

    if let Some(second) = word.next(){
        let res = word.try_for_each(move |x|{if second.is_lowercase() && x.is_lowercase(){return Ok(())
            }

            if second.is_uppercase() && x.is_uppercase(){return Ok(())
            }

            Err(())
        });

        if res.is_err(){return false}
        if first.is_uppercase(){return true}

        if first.is_lowercase() && second.is_lowercase(){return true}

        false
    }else{true}

}

这里代码中应用了 try_for_each, 官网形容：
An iterator method that applies a fallible function to each item in the iterator, stopping at the first error and returning that error. 翻译过去就是对迭代器中的每一个元素执行一个可能会出错的函数，如果函数返回谬误就立即进行迭代并返回该谬误。其中 try_for_each 的源码如下，能够看到外部也是调用了 try_fold 实现

fn try_for_each<F, R>(&mut self, f: F) -> R
    where
        Self: Sized,
        F: FnMut(Self::Item) -> R,
        R: Try<Output = ()>,
    {#[inline]
        fn call<T, R>(mut f: impl FnMut(T) -> R) -> impl FnMut((), T) -> R {move |(), x| f(x)
        }

        self.try_fold((), call(f))
    }

所以下面代码也能够把 try_for_each 间接应用 try_fold 来写，如下：

pub fn detect_capital_use(word: String) -> bool {let mut word = word.chars();
    let first = word.next();
    if first.is_none() {return true;}
    let first = first.unwrap();

    if let Some(second) = word.next() {
        let res = word.try_fold(second, move |sd, x| {if sd.is_lowercase() && x.is_lowercase() {return Ok(sd);
            }

            if sd.is_uppercase() && x.is_uppercase() {return Ok(sd);
            }

            Err(())
        });

        if res.is_err() {return false;}
        if first.is_uppercase() {return true;}

        if first.is_lowercase() && second.is_lowercase() {return true;}

        false
    } else {true}
}

总结
在本文中能够看到尽管是一个简略的算法例子，利用 Rust 语言中迭代器以及相干的几个办法 chars,all,try_fold,enumerate,try_for_each,char_indices`，能够看到 Rust 语言的灵活性和弱小。

关于rust:Rust之美迭代器在算法中的应用

Just My Socks（注册教程 内含优惠码）

Just My Socks（注册教程内含优惠码）