迭代器

Iterator和IntoIterator

trait Iterator {
    type Item;
    fn next(&mut self) -> Option<Self::Item>;
    ... // many default methods
}

迭代器都实现了Iterator，他的关联类型Item是迭代器输出的每个元素的类型。

如果一个类型有一个比较自然的变成迭代器的方法，那这个类型可以实现IntoIterator。

trait IntoIterator where Self::IntoIter: Iterator<Item=Self::Item> {
    type Item;
    type IntoIter: Iterator;
    fn into_iter(self) -> Self::IntoIter;
}

从定义可以看出，生成迭代器会获取本身的所有权。关联类型IntoIter是返回的迭代器，Item是这个迭代器元素的类型。实现了该trait的类型就是一个Iterable。

for循环就是调用了IntoIterator和Iterator的方法。如果调用的值本身就是个Iterator也没问题，因为Iterator本身也实现了IntoIterator。

创建迭代器

从集合创建

大多数集合类型都有iter和iter_mut方法。分别返回不变引用和可变引用的迭代器。
因为有些类型没有自然的成为迭代器的方法，需要有单独的逻辑来创建适合的迭代器。比如&str，可以使用bytes方法转成字节按字节迭代，也可以用chars方法，转成字符向量按字符迭代。

for循环里除了可以用值本身以外也可以用引用和可变引用，迭代生成的元素也分别是原集合中元素的引用和可变引用。这是因为被迭代的集合类型的三个类型&T，&mut T和T本身都实现了IntoIterator。但不是所有的类型都是这样。 HashSet, BTreeSet, 和BinaryHeap没有实现可变引用的IntoIterator。因为改变的元素可能会影响整个集合的结构。HashMap和BTreeMap可以生成可变的值但是不可变的键。

(&T).into_iter()和T.inter()是等价的，后者在不是for这种必须使用trait的情况下更简洁。
而IntoIterator用在泛型变成中更方便，
T: IntoIterator可以限制类型是能生成迭代器的，
T: IntoIterator<Item=U>规定生成的迭代的输出的元素的类型是U。

用函数创建

use rand::random; // In Cargo.toml dependencies: rand = "0.7"
use std::iter::from_fn;
// Generate the lengths of 1000 random line segments whose endpoints
// are uniformly distributed across the interval [0, 1]. (This isn't a
// distribution you're going to find in the `rand_distr` crate, but
// it's easy to make yourself.)
let lengths: Vec<f64> =
    from_fn(|| Some((random::<f64>() - random::<f64>()).abs()))
    .take(1000)
    .collect();

from_fn的参数是一个返回Option的函数，如果返回的Some则继续迭代，如果None则停止，上例中的函数一直是Some，所以用take函数只去1000个。collect从结果生成一个Vec。

successor函数可以利用前一个值来生成下一个值。他的参数是一个初始值，和一个函数，这个函数有一个参数是前一个值，返回是迭代的下一个值。

use num::Complex;
use std::iter::successors;
fn escape_time(c: Complex<f64>, limit: usize) -> Option<usize> {
    let zero = Complex { re: 0.0, im: 0.0 };
    successors(Some(zero), |&z| { Some(z * z + c) })
        .take(limit)
        .enumerate()
        .find(|(_i, z)| z.norm_sqr() > 4.0)
        .map(|(i, _z)| i)
}

find查找迭代中第一个出现的复合条件的值，返回Some(i, x)，i是序号，x是值。

from_fn和successor参数中的函数都是FnMut。

很多集合类型有drain方法，从值的可变引用生成迭代器，并消耗迭代器中涉及的元素，不管是不是用到了。

use std::iter::FromIterator;
let mut outer = "Earth".to_string();
let inner = String::from_iter(outer.drain(1..4));
assert_eq!(outer, "Eh");
assert_eq!(inner, "art");

标准库中的其他迭代器

迭代适配器

适配器都是从一个迭代器产生另一个迭代器。调用适配器的时候还没有开始迭代，只有在最后一个适配器调用next的时候才开始。也就是惰性的。
Rust的迭代适配器是没有overhead的，会用inline来让整个代码变成一个整体。就像是手写的循环一样。

map和filter

map从获取迭代的元素，产生一个新的。
filter获取的是引用。

flatten可以用来过滤Some和Ok

peek

就是让你用下一个元素，但不消耗它。

fuse

虽然大多数迭代器穷尽之后会返回None，但不是所有的都这样，所以不能依赖这个行为

zip

use std::iter::repeat;
let endings = vec!["once", "twice", "chicken soup with rice"];
let rhyme: Vec<_> = repeat("going")
    .zip(endings)
    .collect();
assert_eq!(rhyme, vec![("going", "once"),
                       ("going", "twice"),
                       ("going", "chicken soup with rice")]);

by_ref

一般的适配器会获取迭代器的所有权，执行结束之后，迭代器也被耗尽了。by_ref可以生成一个迭代器的可变引用给适配器，这样适配器在运行到某个地方停止后，原迭代器还是存在，迭代位置停留在了之前停止的地方。

cloned和copied

从元素是引用的迭代器，复制一个元素是值的迭代器。

cycle

将一个迭代器不断循环

消耗迭代器

count, sum, product

max, min

不能用于浮点数，因为浮点数只实现了PartialOrd。

max_by, min_by

用自定义的闭包确定原色的大小，来取最大或最小值，可以解决max，min不能比较浮点数的问题。
闭包的函数前面里，参数使用的是元素的引用。

max_by_key, min_by_key

用闭包生成一个可以比较值，用这个值来取结果

position, rposition, and ExactSizeIterator

position查找某个元素的位置，rposition也是，但是从右边开始找，因此rposition只有reversible的迭代器才能用，而且这个迭代器也需要实现：

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

len方法返回迭代器还剩下的原色个数。不是所有的迭代器都能确定剩下的个数，比如一些无限的迭代器，又比如str需要解析后面的元素那些字节是一个utf-8才能返回一个元素。

fold, rfold, try_fold, try_rfold

fold 就是reduce。
try版本的返回Result或Option，如果结果是Err或None，迭代停止，且不会消耗迭代器。

nth, nth_back

相当于一次执行n个next

last

消耗整个迭代器，去最后一个元素，即使是reversible的。

collect和size_hint

collect需要对应的类型实现FromIterator。一般的实现都是创建一个该类型的对象然后把迭代的值一个一个放进去，但这对于需要动态申请内存的类型（比如Vec）性能很差。因为有可能事先知道结果所需要的内存，所以Iterator有个方法size_hint，会返回预计该类型的size的范围。

实现迭代器

一个迭代一般都需要一个记录迭代状态的数据结构，像range这样的类型，start值可以记录状态，他的into_iter方法甚至可以用自己本身来实现，每迭代一个就加1。像二叉树就需要复杂一点的结构，需要实现IntoIterator，用into_iter方法生成一个专门的Iterator。书中的例子用树的左视图来记录未访问到 节点。

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

便利的时候更新该左视图

impl<'a, T> Iterator for TreeIter<'a, T> {
    type Item = &'a T;
    fn next(&mut self) -> Option<&'a T> {
        // Find the node this iteration must produce,
        // or finish the iteration. (Use the `?` operator
        // to return immediately if it's `None`.)
        let node = self.unvisited.pop()?;
        // After `node`, the next thing we produce must be the leftmost
        // child in `node`'s right subtree, so push the path from here
        // down. Our helper method turns out to be just what we need.
        self.push_left_edge(&node.right);
        // Produce a reference to this node's value.
        Some(&node.element)
    }
}