Ch. 15: Iterators

# Ch. 15: Iterators ## Programming Rust 導讀 ###### tags: `Rust` `iterators` `Talk` `Programming Rust` ---  ## Iterators - Any type that implemnts `trait std::iter::Iterator`. ```rust trait Iterator { type Item; fn next(&mut self) -> Option<Self::Item>; //.... } ``` - 不斷呼叫 `next()`，就可以依續取得所有的 items。 ---  ## Iterable Types - Any type implements `trait std::iter::IntoIterator`, including collection types in `std::collections`. ```rust trait IntoIterator { type Item; type IntoIter: Iterator<Item = Self::Item>; fn into_iter(self) -> Self::IntoIter; // ^^^^會取走 self 的所有權 } ``` - To traverse all *items* in an iterable value, calls `value.into_iter()` to get the iterator, than get each item via `iterator.next()`. ---  ## Iteration Pipeline - 建立 iterator。 - 利用 **adapters** 「改造」（實際上是「取得新的」） iterator。 - 傳給 **consumers** 輸出實際的資料。   ### Lazy Evalutaion - 在 consumers「拉取」資料之前，iterator generator/adapters 不會有任何動作。 --- ## Creating Iterators ----  ### From Associated Functions - 標準資料集合：`iter()`, `iter_mut()` - 字串相關：`bytes()`, `chars()`, `lines()`, `split_whitespace()` - And many others... ----  ### `IntoIterator` Implementation - 型別 `T` 可以分別為 `&T`, `&mut T` 以及 `T` 實作 `IntoIterator`. - `&T`: item 的型別為 `&T::Item`。行為相當於 `iter()`。 - `&mut T`: item 的型別為 `&mut T::Item`。行為相當於 `iter_mut()`。 - `T`: item 的型別為 `T::Item`；而且呼叫過後，items 及容器本身的所有權都會被拿走。 - 不一定每個型別都會實作所有三個版本。 ----  ### `from_fn()` and `successors()` 利用 closure 來產生 items。 - `std::iter::from_fn()`: closure 不需要參數，但可以 capture 外部的 mutable 變數。 - `std::iter::successor()`: 以前一次的結果為輸入的參數。 ```rust fn successors<T, F>(first: Option<T>, succ: F) -> Successors<T, F> ⓘwhere F: FnMut(&T) -> Option<T>, ``` ----  ### `drain()` - 由某些 iterable type（而非 `trait Iterator`）提供的 method。 - 從 iterable 中移除某個範圍的 items，同時回傳被移除的 items 的 iterator。 --- ## Iterator Adapters ==Consume== one iterator and build a new one with ==useful behavior==. ----  `map()` : 將 `Item` 的 iterator，轉換成 `B` 的 iterator。 ```rust= fn map<B, F>(self, f: F) -> Map<Self, F> where Self: Sized, F: FnMut(Self::Item) -> B, ``` `filter()` : 僅留下 `predicate` 結果為 `true` 的 items。 ```rust= fn filter<P>(self, predicate: P) -> Filter<Self, P> where Self: Sized, P: FnMut(&Self::Item) -> bool, ``` ----  `filter_map()` : 僅留下 `f` 的執行結果為 `Some(b)` 的 items。 ```rust= fn filter_map<B, F>(self, f: F) -> FilterMap<Self, F> where Self: Sized, F: FnMut(Self::Item) -> Option<B>, ```` `flatten_map()` : `f` 會回傳 iterables。這些 iterables 的 items 就變成最後的 iterator 的 items。 ```rust fn flat_map<U, F>(self, f: F) -> FlatMap<Self, U, F> where Self: Sized, U: IntoIterator, // f 的回傳值，為 iterable F: FnMut(Self::Item) -> U, ``` ----  ### `map()`, `filter_map()` 和 `flatten_map()` ![](https://hackmd.io/_uploads/HkhSJnQ0s.png) ----  `flatten()` : 1. 把 iterator of iterators 變成 iterator。 2. 把 iterator of `Option<T>` 變成 iterator of T。（因為 `Option<T>` 實作了 `IntoIterator`） 3. 把 iterator of `Result<T, E>` 變成 iterator of T。 ```rust fn flatten(self) -> Flatten<Self> where Self: Sized, Self::Item: IntoIterator, ``` ----  `take()` : 取前 `n` 個 item。 ```rust= fn take(self, n: usize) -> Take<Self> where Self: Sized, ``` `take_while()` : 取到 `predicate` 的執行結果第一次為 `false` 為止。        ```rust= fn take_while<P>(self, predicate: P) -> TakeWhile<Self, P> where Self: Sized, P: FnMut(&Self::Item) -> bool, ``` ----  `skip()` : 跳過 n 個 `skip_while()` : `predicate` 為 `true` 的都跳過。 `rev()` : 從後面開始反著 iterate。但這是 `trait DoubleEndedIterator` 提供的方法。不是所有的 iterators 都支援。 ----  `enumerate()` : 變成 `(index, item)` 的 iterator。 ```rust= let items = ["Apple", "Banana", "Candy"]; let ol_result: Vec<_> = items .into_iter() .enumerate() .map(|(idx, item)| format!("{}. {}", idx + 1, item)) .collect(); println!("{:?}", ol_result); // ["1. Apple", "2. Banana", "3. Candy"] ``` ----  `zip()` : 將兩個 iterator 組合起來。只要有一邊空了，這個組合起來的 iterator 就會回傳 `None`。 ![](https://hackmd.io/_uploads/Sk2WOnQ0o.png) ----  `chain()` : 將兩個 Item 一樣的 iterator 串起來。如果兩個 iterator 都是 reversable 的話，那串起來的也是。 ![](https://hackmd.io/_uploads/rkoXthQAo.png) ----  `cycle()` : 無止盡地重覆元素。 ![](https://hackmd.io/_uploads/B1F3KhQRj.png) ----  `peekable()` : 建立 peekable（可以偷看下一個 item 的）iterator。 Peekable iterator 會多一個叫 `peek()` 的 method。 `fuse()` : 建立一個保證在「`next()` 第一次回傳 `None` 之後會持續回傳 `None`」的 iterator。 `inspect()` : 主要是用來 debug 的。不會影響 item 的內容，但可以透過傳入的 closure 把值印出來看。 ----  `by_ref()` : 以 `&mut` 方式使用 iterator。 `cloned()`, `copy()` : 用於產生 ref item 的 iterator，每一次都 clone 一份 item。 --- ## Consuming Iterators ----  `count()` : 計算個數。 `sum()` 和 `product()` : 總合和乘積。Item 必須為整數或浮點數，或是實作 `std::iter::Sum`/`std::iter::Product` 的型別。 ----  `max()` 和 `min()` : 取最大/最小值。Item 必須實作 `std::cmp::Ord`。無法處理浮點數（因為浮點數只有 `PartialOrd`）。 `max_by()` 和 `min_by()` : 用指定的比較 closure（回傳 `std::cmp::Ordering`）取最大/最小值。 `max_by_key()` 和 `min_by_key()` : 用 closure 回傳的值（實作 `std::cmp::Ord`）比較大小後，取最大/最小值。 ----  `lt()`, `eq()` 和 `gt()` : 回傳兩個 iterator 依序比較後的結果。 `any()` : 對所有的 items 執行 closure，其中一個的結果為 true 時就回傳 true。 `all()` : 對所有的 items 執行 closure，所有的結果為 true 時才回傳 true。 ----  `position()` : 從頭開始，對 items 執行 closure，回傳「第一個結果為 true 的 item」的 index 值。 `rposition()` : 從尾巴開始，對 items 執行 closure，回傳「第一個結果為 true 的 item」的 index 值。 - 必須實作 `DoubleEndedIterator`，才能從尾巴開始取 item。 - 必須實作 `ExactSizeIterator`，才能算出結果的 index。（像是 `str::chars` 就無法得知詳細的 size，因為 UTF-8 的每個 `char` 長度不固定。 ----  `fold()` 和 `rfold()` : 將 items 依續累積運算，最後算出一個結果。即一般 functional programming 常見的 reduce 函數。 ----  `try_fold()` 和 `try_rfold()` : - 和 `fold()`/`rfold()` 一樣，會累積運算。但依 closure 的回傳結果，可能會提前結束（不會走完所有的 items）。 - 回傳型別為 `Result<T,E>`：若回傳 `Err(e)`，則 `try_fold()` 直接回傳 `Err(e)`；若回傳 `Ok(a)`，則會把 `a` 當成 cloure 的 accu 繼續做下去，最後回傳 `Ok(v)`。 - 回傳型別為 `Option<T>`：若回傳 `None`，則 `try_fold()` 直接回傳 `None`；若回傳 `Some(a)`，則會把 `a` 當成 cloure 的 accu 繼續做下去，最後回傳 `Some(v)`。 - 回傳型別為 `std::ops::ControlFlow`：若回傳 `Break(b)`，則 `try_fold()` 直接回傳 `b`；若回傳 `Continue(c)`，則會把 `c` 當成 accu 繼續做下去，最後回傳 `v`。 - Iterator 中有很多 methods 會以 `try_fold()` 為基礎來實作，因此如果能自行實作更有效率的 `try_fold()`，可以顯著提升 iterator 的效率。 ----  `nth()` : 取得第 n 個 item。不會占用 iterator 的所有權，也不會改變 iterator 本身。 `nth_back()` : 取得倒數第 n 個 item。 `last()` : 取得最後一個 item。 ==會耗用 iterator 中所有的 items，就算是`DoubleEndedIterator`也一樣。== 因此，如果該 iterator 是 `DoubleEndedIterator` 的話，可以改用 `next_back()` 會比較好。 ----  `find()` 和 `rfind()` : 從 items 中找到第一個讓 closure 回傳 true 的 item，並回傳。 `find_map()` : 傳入的 closure 要依每一個 item 算出一個 `Option<B>`；`find_map()` 會回傳第一個 `Some(b)`。 `extend()` : - 這是 `trait Extend` 提供的方法，不是 `trait Iterator`。 - 把 iterable 的 items 附加到實作了 `Extend` 的集合上。 ----  `collection()` : - 只要是實作了 `trait FromIterator` 的型別（例如 `std::collections::*`），都可以利用 `iterator.collect()` 來建立。 - 建立 collection 的過程中，有時如果能知道 iterator 可能的長度，會更有效率（可以事先 allocate 需要的空間）。此時 iterator type 可以實作 `Iterator::size_hint()`，給 collection 使用。 ```rust // 利用 turbofish 語法指定要呼叫哪個版本的 collect() let args = std::env::args().collect::<Vec<String>>(); // 利用型別推斷幫你選擇對應的 collect() let args: Vec<String> = std::env::args().collect(); ``` ----  `partition()` : 依據 closure 回傳的 `true` or `false`，將 items 分成兩個不同的 group。 ----  `for_each()` : - 把每一個 item 都丟到 closure 去執行。 - 相當於 `for`-loop，只是不能用 `break` 和 `continue`。 - 如果 iterator 加了很多 adapters 變得很長，用 `for_each` 就比 `for`-loop 優雅。 - 某些情況下，`for_each()` 會比 `for`-loop 快。 `try_for_each()` : 和 `try_fold()` 很像，closure 可以回傳 `Option<_>`, `Result<_,_>` 或 `ControlFlow<_>`。一旦 `None`, `Err(_)`, `Break(_)` 的時候，就提前 return。 --- ## Iterators in Practice ----  ### Stand-alone Iterator (Generator) ```rust= impl Iterator for I32Range { type Item = i32; fn next(&mut self) -> Option<i32> { if self.start >= self.end { None } else { let result = Some(self.start); self.start += 1; result } } } ``` ----  ### Iterator from Iterables ```rust= enum BinaryTree<T> { Empty, NonEmpty(<Box<TreeNode<T>>), } struct TreeNode<T> { element T, left: BinaryTree<T>, right: BinaryTree<T>, } struct TreeIter<'a, T> { unvisited: Vec<&'a TreeNode<T>> } ``` ----  ```rust= impl<'a, T: 'a> TreeIter<'a, T> { fn push_left_edge(&mut self, mut tree: &'a BinaryTree<T>) { while let BinaryTree::NonEmpty(ref node) = tree { self.unvisited.push(node); tree = &node.left; } } } impl<T> BinaryTree<T> { fn iter(&self) -> TreeIter<T> { let mut iter = TreeIter { unvisited: Vec::new() }; iter.push_left_edge(self); iter } } ``` ----  ```rust= impl<'a, T> IntoIterator for &'a BinaryTree<T> { type Item = &'a T; type IntoIter = TreeIter<'a, T>; // IntoIter 必須實作 Iterator fn into_iter(self) -> Self::IntoIter { self.iter() } } impl<'a, T> Iterator for TreeIter<'a, T> { type Item = &'a T; fn next(&mut self) -> Option<Self::Item> { let node = self.unvisited.pop()?; self.push_left_edge(&node.right); Some(&node.element) } } ``` ---  ## Template title - List 1 - List 2 - List 3