直播錄影
Introduction
0:00:00
In this third Crust of Rust video, we cover iterators and trait bounds, by re-implementing the "flatten" Iterator method from the standard library. As part of that, we cover some of the weirder trait bounds that are required, including what's needed to extend the implementation to support backwards iteration.
The Iterator trait
0:01:45
Trait std::iter::Iterator
Iterator 在 Rust 是 trait,這個 trait 有兩個主要的東西你必須關注 :
- associated type
Item
: 由迭代器產生的 item。
next()
: 由驅動迭代器的事物呼叫。它會產生 Some(Item)
直到迭代器被耗盡,也就是產生 None
時,迭代器就會終止。
以下為 Iterator 函式庫部分程式碼 :
開始建置 Rust 專案 :
當你寫了以下的程式碼 :
在 Rust 本質上並沒有真正的 for 迴圈,它是個語法糖。Desugaring 前面我們寫的程式之後,實際上它會轉換成以下程式碼 :
into_iter()
給了我們一個迭代器,無論原本那個東西是什麼,假設那個東西可以被迭代。這時候 for 迴圈就可以改用 while let 迴圈取代,while let 迴圈持續呼叫 next()
函式回傳 Some(xxx)
,直到回傳 None
時,迭代器就會停下來。但語法糖轉換後並不完全是這樣,而是演變成一個帶有 break
的迴圈,這裡只是要提供背後到底發生了什麼事情。
The IntoIterator trait
0:04:25
Trait std::iter::IntoIterator
IntoIterator 是獨立的 trait,並不是包在 Iterator trait,但它有點像 Iterator 的 wrapper trait,它可以將任何東西變成迭代器。任何迭代器很明顯地可以變成迭代器,但其他東西也可以變成迭代器,像是 HashMap、HashSet …等等,它們實作的 slices、slices references to slices、mutable references to HashMap,如果你可以擁有他們實作的其中一個東西,你可以得到一個迭代器來迭代它們的一些相關部分,看到下面的例子 :
只要你每次迭代 mut HashMap,都會拿到包含 immutable 的 key 以及 mutable 的 value 的 tuple 結構,這些東西的可變性設定很有道理,因為當你在迭代的時候你不能去改變 key,因為 key 如果中途改變很有可能就移到其他的位置,但你可以改變 value。IntoIterator 還有 associated type IntoIter
,它將會回傳迭代器的型別 : IterMut
,它是 HashMap 的子模組,我們這邊不做探討。
Generic traits vs associated types
0:06:24
為什麼 Iterator 會有 associated types Item
? 以下兩個都可以運作,但差別在哪裡 ?
- Associated types
- Generic traits
當你使用 Associated types 的時候,你預期這個 trait 只會實作一個給定的型別。舉例來說 :
- 當你有一個 hash map,它只會有一個 Iterator 型別 : keys 和 values
- 當你有一個 vector,它只會有一個 Iterator 型別 : 某種儲存在 vector 內的型別。
如果多個實作對於任何給定類型都有意義的話,則可以用 Generic traits 。例如 :
因為你想要伺服器能夠支援多種不同型別,這時候用 Generic traits 就相當的合理,倘若這裡用 Associated types,反而被限制只能支援一種型別。這樣感覺用 Generic traits 對程式設計師很方便,但是如果使用 Associated types 的好處是,型別檢查器的工作會比較簡單,因為它知道現在只有一種型別被選擇,而且當你在編寫 impl blocks 的時候,函式簽章不需要有額外的泛型參數。
如果程式寫的例子是 SomethingIterable
,這時候我們會立刻知道你指的是哪一個實作的 Iterator,因為只有一個;但如果是 SomethingService
的話,你必須告訴編譯器你想要哪個 Request 型別的服務。

0:10:05
Q : Why do some types have "iter()" (e.g. slice) and others use "into_iter()"?
A : Jon 認為沒有充分的理由用有 iter()
方法 :
實際上,slice 是有實作 into_iter()
方法,不過實際上沒有必要。您不需要完全符合 IntoIterator trait 要求的方法簽章,這在某些情況下使生命週期推理變得更容易。
Q : Couldn't hashmap also have seperate iterators for just keys or just values?
A : 它可以,而且它也有,一個叫做 .keys()
,一個叫做 .values()
。不過 hash map 本身沒有實作 Iterator,而是實作 IntoIterator。當你跟 hash map 說給我一個迭代器,你只會得到一種答案,因為它並沒有接收任何其它的參數。
Q : So, if using a for loop we don't need to explicitly call my_collection.iter() or are there exceptions?
A : 沒錯。不過要記住下面兩個 for 迴圈有很大的差別 :
Provided Iterator methods
0:13:37
標準函式庫只要該函式有 {...}
表示已經有預設的實作了,像是 count()
的話,就是實際走訪所有元素,但你也可以替換它們的實作,例如 ,Vector 就是直接回傳它的 size,而不用實際走訪整個 Vector 來提升效率。
Iterator::flatten
0:14:42
函式簽章如下,它要求 Item
要實作 IntoIterator trait :
觀察 flatten
方法 :
- 存取外部迭代器的第 n 個元素
- 呼叫
into_iter()
將外部迭代器的第 n 個元素轉成迭代器
- 轉完之後接著走訪內部迭代器的全部元素
- n++
- 如果走訪完外部迭代器的元素即終止,否則回到步驟 1

Q : does it flatten infinitely?
A : 只要外部迭代器的元素還有,就會一直繼續下去。
Q : Does these nested iterator need to have the same item type?
A : 是的。這本來就是迭代器要求的,外部迭代器的元素之間都會是相同型別,所以內部迭代器之間也自然而然跟著是相同型別。
flatten 的遞迴深度只會有一層,而不是你有很多層它就會遞迴到最底層。
開始實作 flatten 功能 :
Associated items of generics in bounds
0:20:07
繼續實作 flatten 功能, 要將部份的 I
換成 O
:
並且為 Flatten 實作 Iterator 原型:
Why must O as Trait be bracketed?
0:23:10
Q : Why <O::Item as IntoIterator> required?
A : Jon 不知道為什麼編譯器會認為是引發奇異的錯誤,Jon 猜測這可能是斷詞歧異,因為 AAA::BBB::CCC
可能是路徑 :
If a type has multiple associated types by the same name, such as if the trait that provides the associated type is itself generic (and therefore there are many implementations), you can disambiguate with the syntax <Type as Trait>::AssocType
. Using this, you can write bounds not only for the outer iterator type but also for the item type of that outer iterator.
- 歧義性:
在某些情況下,I::Item::Item
可能會導致歧義。如果 I::Item
實現了多個 trait,而這些 trait 都有一個名為 Item
的關聯類型,Rust 編譯器就無法確定您指的是哪個 Item
。
明確性:
<I::Item as Container<i32>>::Item
明確指出我們要使用的是 Container<i32>
trait 中定義的 Item
關聯類型。這種寫法消除了任何可能的歧義。
範例程式碼
目前程式碼
測試出現以下錯誤 :
Flattening more than two levels
0:24:28
可以,再宣告一層即可,大概是這樣:
要注意到,這樣你要 flatten 的東西必須有三層,兩層現在反而是不能接受的。
First attempt at Flatten::next
0:25:24
回到兩層的實作,接著繼續實作 next()
:
再實作兩個 test case :
std::iter::empty::<Vec<()>>()
解析
std::iter::empty
是 Rust 標準函式庫的函式,其定義如下:
所以我們可以知道 <Vec()>
是泛型的參數,而第二個 ()
則是呼叫該函式。
empty
與 <Vec<()>>()
之間的 ::
若省略會出現以下錯誤 :
什麼時候要加 ::
,什麼時候不用加 ::
?
- 當函式需要傳入值,而這個傳入的值有定義是泛型,就不用加
::
範例
- 當函式沒有傳入值,就要加
::
來呼叫函式。empty
用法即是這種例子。
Q : Would it be possible to write a macro that accepts n nested levels?
A : 程序式巨集是你的選項。
Q : Alternately, instead of doing this explicitly to one-level-deep, could we not write fn flatten() to all itself recursively?
A : 可以,flat_map
是個好選項。
完整程式碼
Two elements in inner iterator
0:29:59
再加一個 test case 並測試 :
測試失敗,左邊的結果只得到 1。
為了驗證到底哪裡出了問題,再加一個 test case :
Two elements in outer iterator
0:31:05
再加一個 test case 並測試:
這次測試成功了,表示外部迭代器的走訪應該是沒問題的,問題應該出在內部的迭代器現在只能迭代一次。
為了確認外部迭代器是正確的,再加一個 test case :
完整程式碼
測試結果如下:
Simplifying with ?
0:33:29
將程式碼實作的更有可讀性 :
Storing the inner iterator
0:35:05
我們有 struct 可以記錄 inner_iter 的位置 :
並為 impl block 加上 bound,以及先給 inner 初值 :
flatten
函式也要加上 bound :
我們現在的目標是,如果 inner 迭代器還沒走訪完,我們希望能繼續走訪下去,等到迭代器被耗盡之後,outer 迭代器再接著往下一個元素前進 :
備註
- 說明錯誤原因
- Some(ref mut x) = Option(y) 參照這裡
回到 struct 修好備註 1 的問題 :
目前程式碼
Trait bound syntax
0:39:10
到這裡才知道到 bound 的用途是透過限制型態來保證函式內部相關值一定會有那個方法可已用。
Finishing corrected next
0:40:07
到現在還沒完成,我們還沒實作完成 flatten 函式,接著繼續修改
Q : do you normally include bounds on the struct definition as well, or just the impl block?
A : 通常只加在 impl block,但這裡比較特別的原因是我們的 struct 也要有 bound 才能確保可以呼叫函式。
經歷了一些語法疼痛之後,終於實作完了。
目前程式碼
Ergonomics with IntoIterator
0:42:50
將 into_iter 移到 flatten 函式內部,並做一些微調,可以精簡 test case :
目前程式碼
Q : would while let Some(inner) = self.inner
work here?
A : 不行,next()
函式第一次被呼叫,我們必須要確保 Line 17, 18 被執行。
DoubleEndedIterator
0:44:15
Trait std::iter::DoubleEndedIterator
DoubleEndedIterator 讓你可以從左邊迭代到右邊。看到從標準函式庫看到它有一個方法,可以讓你從右邊迭代到左邊 :

First draft of DEI implementation
0:46:10
開始實作,新增程式碼 :
將 Flatten 的 Iterator 的程式碼直接貼到 Flatten 的 DoubleEndedIterator :
可以看到,光是要處理兩層的 flatten,bound 就要寫得這麼麻煩了,更多層的話,可想而知會更不好寫。
Q : what's the difference between + and , in trait bounds?
A : ,
是新規則,+
是該規則有多個 bound。
Testing double-ended iteration
0:50:57
新增 test case 來驗證剛剛實作的正不正確 :
rev
()
Reverses an iterator’s direction.
Usually, iterators iterate from left to right. After using rev(), an iterator will instead iterate from right to left.
This is only possible if the iterator has an end, so rev() only works on DoubleEndedIterators.
目前程式碼
測試順利通過 :
Iterating from both ends in parallel
0:53:58
但還是有問題,新增一個更複雜的 test case :
目前程式碼
新增的那個 test case 並未通過測試 :
因為外部迭代器的第一個元素的尚未耗盡,所以即使反轉了迭代方向還是會在第一個元素裡面走訪,下圖為圖解 :

將 test case 的元素稍微改一下,驗證猜想 :
出現了以下錯誤 :
證明前面圖解的推論是正確的。歸根究柢就是因為我們的 struct 的 inner 只能記錄單邊的游標所導致的,再多引入一個游標看看 :
接著修改 Flatten 的 impl block :

並且修改 next 的邏輯 :
next_back 依樣畫葫蘆 :
目前程式碼
pub fn flatten<I>(iter: I) -> Flatten<I::IntoIter>
where
I: IntoIterator,
I::Item: IntoIterator,
{
Flatten::new(iter.into_iter())
}
pub struct Flatten<O>
where
O: Iterator,
O::Item: IntoIterator
{
outer : O,
front_iter : Option<<O::Item as IntoIterator>::IntoIter>,
back_iter : Option<<O::Item as IntoIterator>::IntoIter>,
}
impl<O> Flatten<O>
where
O: Iterator,
O::Item: IntoIterator,
{
fn new(iter: O) -> Self
{
Flatten {
outer : iter,
front_iter : None,
back_iter : None,
}
}
}
impl<O> Iterator for Flatten<O>
where
O: Iterator,
O::Item: IntoIterator,
{
type Item = <O::Item as IntoIterator>::Item;
fn next(&mut self) -> Option<Self::Item>
{
loop {
if let Some(ref mut front_iter) = self.front_iter {
if let Some(i) = front_iter.next() {
return Some(i);
}
self.front_iter = None;
}
if let Some(next_inner) = self.outer.next() {
self.front_iter = Some(next_inner.into_iter());
} else {
return self.back_iter.as_mut()?.next();
}
}
}
}
impl<O> DoubleEndedIterator for Flatten<O>
where
O: Iterator + DoubleEndedIterator,
O::Item: IntoIterator,
<O::Item as IntoIterator>::IntoIter: DoubleEndedIterator,
{
fn next_back(&mut self) -> Option<Self::Item>
{
loop {
if let Some(ref mut back_iter) = self.back_iter {
if let Some(i) = back_iter.next_back() {
return Some(i);
}
self.back_iter = None;
}
if let Some(next_back_inner) = self.outer.next_back() {
self.back_iter = Some(next_back_inner.into_iter());
} else {
return self.front_iter.as_mut()?.next_back();
}
}
}
}
#[cfg(test)]
mod tests
{
use super::*;
#[test]
fn empty()
{
assert_eq!(flatten(std::iter::empty::<Vec<()>>()).count(), 0);
}
#[test]
fn empty_wide()
{
assert_eq!(flatten(vec![Vec::<()>::new(), vec![], vec![]]).count(), 0);
}
#[test]
fn one()
{
assert_eq!(flatten(std::iter::once(vec!["a"])).count(), 1);
}
#[test]
fn two()
{
assert_eq!(flatten(std::iter::once(vec!["a", "b"])).count(), 2);
}
#[test]
fn two_wide()
{
assert_eq!(flatten(vec![vec!["a"], vec!["b"]]).count(), 2);
}
#[test]
fn reverse()
{
assert_eq!(
flatten(std::iter::once(vec!["a", "b"]))
.rev()
.collect::<Vec<_>>(),
vec!["b", "a"]
);
}
#[test]
fn reverse_wide()
{
assert_eq!(
flatten(vec![vec!["a"], vec!["b"]])
.rev()
.collect::<Vec<_>>(),
vec!["b", "a"]
);
}
#[test]
fn both_ends()
{
let mut iter = flatten(vec![vec!["a1", "a2", "a3"], vec!["b1", "b2", "b3"]]);
assert_eq!(iter.next(), Some("a1"));
assert_eq!(iter.next_back(), Some("b3"));
assert_eq!(iter.next(), Some("a2"));
assert_eq!(iter.next_back(), Some("b2"));
assert_eq!(iter.next(), Some("a3"));
assert_eq!(iter.next_back(), Some("b1"));
assert_eq!(iter.next(), None);
assert_eq!(iter.next_back(), None);
}
}
修改完畢之後,順利通過所有測試了 :
Q : the inner refs are being reset with each direction, so it gets "lost" what the new ends would be.
A : 沒錯。
The cost of two cursors
1:04:02
1:04:02
Q : is there a way to implement it in such a way that you don't have to pay the cost of two cursors when the iterator is only used in one way?
A : 有的,但這裡不講。不過你可能需要 specialization 才能讓這個技巧發揮作用,但想法是你要添加第二個泛型參數到 flatten,有些型別有實作 walk back。如果它沒有實作 walk back,你可以給它 zero slice 型別,這樣或許就能做到再沒有兩個游標情況下仍可以從兩端走訪。
Q : Why store back_iter even for types that aren't DoubleEndedIterator?
A : 原因如下 :
Iterators are like Futures
1:06:28
Q : This whole process gives me major future vibes. The whole stacking iters on iters.
A : 是的。
Calling next and next_back concurrently
1:07:14
Q : Can you call next and next_back concurrently?
A : 不行,可以看到函式簽章 :
兩者的傳入參數都必須要是 exclusive 的,所以你不能同時呼叫 next 和 next_back。
ref in patterns
1:07:55
Q : why do you need to use "ref mut" in Some(ref mut back_iter)?
A :
但我們可以做以下更換 :
Why not flatten first, then iterate
1:09:33
Q : what if instead of "live" walking you'll "flatten" entire data into flatten structure and then iter() over it from both ends?
A : 這樣你就需要記憶體配置,而我們的實作是,即便元素是無限的,我們的方法也仍可以運作,因為我們只配置了指標,並且去移動它而已,例如下面的 test case :
可以通過 inf 測試 :
目前程式碼
pub fn flatten<I>(iter: I) -> Flatten<I::IntoIter>
where
I: IntoIterator,
I::Item: IntoIterator,
{
Flatten::new(iter.into_iter())
}
pub struct Flatten<O>
where
O: Iterator,
O::Item: IntoIterator
{
outer : O,
front_iter : Option<<O::Item as IntoIterator>::IntoIter>,
back_iter : Option<<O::Item as IntoIterator>::IntoIter>,
}
impl<O> Flatten<O>
where
O: Iterator,
O::Item: IntoIterator,
{
fn new(iter: O) -> Self
{
Flatten {
outer : iter,
front_iter : None,
back_iter : None,
}
}
}
impl<O> Iterator for Flatten<O>
where
O: Iterator,
O::Item: IntoIterator,
{
type Item = <O::Item as IntoIterator>::Item;
fn next(&mut self) -> Option<Self::Item>
{
loop {
if let Some(ref mut front_iter) = self.front_iter {
if let Some(i) = front_iter.next() {
return Some(i);
}
self.front_iter = None;
}
if let Some(next_inner) = self.outer.next() {
self.front_iter = Some(next_inner.into_iter());
} else {
return self.back_iter.as_mut()?.next();
}
}
}
}
impl<O> DoubleEndedIterator for Flatten<O>
where
O: Iterator + DoubleEndedIterator,
O::Item: IntoIterator,
<O::Item as IntoIterator>::IntoIter: DoubleEndedIterator,
{
fn next_back(&mut self) -> Option<Self::Item>
{
loop {
if let Some(ref mut back_iter) = self.back_iter {
if let Some(i) = back_iter.next_back() {
return Some(i);
}
self.back_iter = None;
}
if let Some(next_back_inner) = self.outer.next_back() {
self.back_iter = Some(next_back_inner.into_iter());
} else {
return self.front_iter.as_mut()?.next_back();
}
}
}
}
#[cfg(test)]
mod tests
{
use super::*;
#[test]
fn empty()
{
assert_eq!(flatten(std::iter::empty::<Vec<()>>()).count(), 0);
}
#[test]
fn empty_wide()
{
assert_eq!(flatten(vec![Vec::<()>::new(), vec![], vec![]]).count(), 0);
}
#[test]
fn one()
{
assert_eq!(flatten(std::iter::once(vec!["a"])).count(), 1);
}
#[test]
fn two()
{
assert_eq!(flatten(std::iter::once(vec!["a", "b"])).count(), 2);
}
#[test]
fn two_wide()
{
assert_eq!(flatten(vec![vec!["a"], vec!["b"]]).count(), 2);
}
#[test]
fn reverse()
{
assert_eq!(
flatten(std::iter::once(vec!["a", "b"]))
.rev()
.collect::<Vec<_>>(),
vec!["b", "a"]
);
}
#[test]
fn reverse_wide()
{
assert_eq!(
flatten(vec![vec!["a"], vec!["b"]])
.rev()
.collect::<Vec<_>>(),
vec!["b", "a"]
);
}
#[test]
fn both_ends()
{
let mut iter = flatten(vec![vec!["a1", "a2", "a3"], vec!["b1", "b2", "b3"]]);
assert_eq!(iter.next(), Some("a1"));
assert_eq!(iter.next_back(), Some("b3"));
assert_eq!(iter.next(), Some("a2"));
assert_eq!(iter.next_back(), Some("b2"));
assert_eq!(iter.next(), Some("a3"));
assert_eq!(iter.next_back(), Some("b1"));
assert_eq!(iter.next(), None);
assert_eq!(iter.next_back(), None);
}
#[test]
fn inf()
{
let mut iter = flatten((0..).map(|i| 0..i));
assert_eq!(iter.next(), Some(0));
assert_eq!(iter.next(), Some(0));
assert_eq!(iter.next(), Some(1));
}
}
More ref in patterns
1:12:51
Q : ref mut should be inferred by the compiler now i believe
A : 並不是全部,這裡的用法就是例子。
當你有個模式,編譯器很聰明,它不會移動值,而是 mutably 借用 :
Q : then next_back() makes no sense… as next one will be rubbish if outer gets new item
A : 是的,我們的 inf test case 是不能呼叫 next_back 的,如果你常是呼叫,編譯器會回報以下的錯誤訊息給你 :
Deeper flattening
1:14:09
Q : Does this code work for arbitrary nested iterators? I see it addresses two levels with outer and inner. how would it work for a third level?
A : 前面就有說到了,並不行。你還需要額外在 stcut 添加額外的 front_front_iter
, front_back_iter
, back_front_iter
, back_back_iter
,你需要追蹤你正在走訪的游標樹。
你可以 flatten 你之前 flatten 的結果,或許可能比起實作支援多層的 flatten 還要是繼一點,新增一個 test case :
通過測試 :
pub fn flatten<I>(iter: I) -> Flatten<I::IntoIter>
where
I: IntoIterator,
I::Item: IntoIterator,
{
Flatten::new(iter.into_iter())
}
pub struct Flatten<O>
where
O: Iterator,
O::Item: IntoIterator
{
outer : O,
front_iter : Option<<O::Item as IntoIterator>::IntoIter>,
back_iter : Option<<O::Item as IntoIterator>::IntoIter>,
}
impl<O> Flatten<O>
where
O: Iterator,
O::Item: IntoIterator,
{
fn new(iter: O) -> Self
{
Flatten {
outer : iter,
front_iter : None,
back_iter : None,
}
}
}
impl<O> Iterator for Flatten<O>
where
O: Iterator,
O::Item: IntoIterator,
{
type Item = <O::Item as IntoIterator>::Item;
fn next(&mut self) -> Option<Self::Item>
{
loop {
if let Some(ref mut front_iter) = self.front_iter {
if let Some(i) = front_iter.next() {
return Some(i);
}
self.front_iter = None;
}
if let Some(next_inner) = self.outer.next() {
self.front_iter = Some(next_inner.into_iter());
} else {
return self.back_iter.as_mut()?.next();
}
}
}
}
impl<O> DoubleEndedIterator for Flatten<O>
where
O: Iterator + DoubleEndedIterator,
O::Item: IntoIterator,
<O::Item as IntoIterator>::IntoIter: DoubleEndedIterator,
{
fn next_back(&mut self) -> Option<Self::Item>
{
loop {
if let Some(ref mut back_iter) = self.back_iter {
if let Some(i) = back_iter.next_back() {
return Some(i);
}
self.back_iter = None;
}
if let Some(next_back_inner) = self.outer.next_back() {
self.back_iter = Some(next_back_inner.into_iter());
} else {
return self.front_iter.as_mut()?.next_back();
}
}
}
}
#[cfg(test)]
mod tests
{
use super::*;
#[test]
fn empty()
{
assert_eq!(flatten(std::iter::empty::<Vec<()>>()).count(), 0);
}
#[test]
fn empty_wide()
{
assert_eq!(flatten(vec![Vec::<()>::new(), vec![], vec![]]).count(), 0);
}
#[test]
fn one()
{
assert_eq!(flatten(std::iter::once(vec!["a"])).count(), 1);
}
#[test]
fn two()
{
assert_eq!(flatten(std::iter::once(vec!["a", "b"])).count(), 2);
}
#[test]
fn two_wide()
{
assert_eq!(flatten(vec![vec!["a"], vec!["b"]]).count(), 2);
}
#[test]
fn reverse()
{
assert_eq!(
flatten(std::iter::once(vec!["a", "b"]))
.rev()
.collect::<Vec<_>>(),
vec!["b", "a"]
);
}
#[test]
fn reverse_wide()
{
assert_eq!(
flatten(vec![vec!["a"], vec!["b"]])
.rev()
.collect::<Vec<_>>(),
vec!["b", "a"]
);
}
#[test]
fn both_ends()
{
let mut iter = flatten(vec![vec!["a1", "a2", "a3"], vec!["b1", "b2", "b3"]]);
assert_eq!(iter.next(), Some("a1"));
assert_eq!(iter.next_back(), Some("b3"));
assert_eq!(iter.next(), Some("a2"));
assert_eq!(iter.next_back(), Some("b2"));
assert_eq!(iter.next(), Some("a3"));
assert_eq!(iter.next_back(), Some("b1"));
assert_eq!(iter.next(), None);
assert_eq!(iter.next_back(), None);
}
#[test]
fn inf()
{
let mut iter = flatten((0..).map(|i| 0..i));
assert_eq!(iter.next(), Some(0));
assert_eq!(iter.next(), Some(0));
assert_eq!(iter.next(), Some(1));
}
#[test]
fn deep()
{
assert_eq!(flatten(flatten(vec![vec![vec![0, 1]]])).count(), 2);
}
}
Q : could you nest calls of flatten if it detects more than two levels?
A : 並不行,因為 flatten 是在編譯時期就被執行,所以你必須在呼叫 flatten 的時候就給它一個型別,這都發生在編譯時期。我們沒辦法在執行階段去檢查到底有幾層。
FlatMap
1:17:00
Struct std::iter::FlatMap
FlatMap 映射的是外部迭代器,而不是內部迭代器,FlatMap 的結構長得像這樣 :
如果你想驗證本主題的概念是否都掌握了,你可以自己試著實作 FlatMap 看看。
Ergonomics through extension traits
1:18:19
現在我們想要做的是,是改變呼叫的方式 (flatten(...)
-> .flatten()
),因為原本的 freestanding function 有點惱人。,你原本就可以這樣呼叫了,因為迭代器就有實作了,但是呼叫的時候就不是用到我們實作的那個 flatten 了。現在想像一下迭代器本身沒有實作 flatten,我們可以用 extension trait :
新增 test case 來驗證是否可以用 .flatten() 方式呼叫我們的 flatten :
嘗試編譯看看,得到了以下錯誤 :
Sized in traits
1:21:19
編譯不過的原因如下 :
回到編譯器的錯誤訊息就清楚知道 Flatten<Self>
要有 Sized 才可以,因為 Self 不是 Sized,所以要多加一個 bound :
為什麼我的編譯器版本不用 into_iter() 也可以編譯的過 ?
目前程式碼
pub trait IteratorExt: Iterator {
fn our_flatten(self) -> Flatten<Self>
where
Self: Sized,
Self::Item: IntoIterator;
}
impl<T> IteratorExt for T
where
T: Iterator
{
fn our_flatten(self) -> Flatten<Self>
where
Self::Item: IntoIterator
{
flatten(self)
}
}
pub fn flatten<I>(iter: I) -> Flatten<I::IntoIter>
where
I: IntoIterator,
I::Item: IntoIterator,
{
Flatten::new(iter.into_iter())
}
pub struct Flatten<O>
where
O: Iterator,
O::Item: IntoIterator
{
outer : O,
front_iter : Option<<O::Item as IntoIterator>::IntoIter>,
back_iter : Option<<O::Item as IntoIterator>::IntoIter>,
}
impl<O> Flatten<O>
where
O: Iterator,
O::Item: IntoIterator,
{
fn new(iter: O) -> Self
{
Flatten {
outer : iter,
front_iter : None,
back_iter : None,
}
}
}
impl<O> Iterator for Flatten<O>
where
O: Iterator,
O::Item: IntoIterator,
{
type Item = <O::Item as IntoIterator>::Item;
fn next(&mut self) -> Option<Self::Item>
{
loop {
if let Some(ref mut front_iter) = self.front_iter {
if let Some(i) = front_iter.next() {
return Some(i);
}
self.front_iter = None;
}
if let Some(next_inner) = self.outer.next() {
self.front_iter = Some(next_inner.into_iter());
} else {
return self.back_iter.as_mut()?.next();
}
}
}
}
impl<O> DoubleEndedIterator for Flatten<O>
where
O: Iterator + DoubleEndedIterator,
O::Item: IntoIterator,
<O::Item as IntoIterator>::IntoIter: DoubleEndedIterator,
{
fn next_back(&mut self) -> Option<Self::Item>
{
loop {
if let Some(ref mut back_iter) = self.back_iter {
if let Some(i) = back_iter.next_back() {
return Some(i);
}
self.back_iter = None;
}
if let Some(next_back_inner) = self.outer.next_back() {
self.back_iter = Some(next_back_inner.into_iter());
} else {
return self.front_iter.as_mut()?.next_back();
}
}
}
}
#[cfg(test)]
mod tests
{
use super::*;
#[test]
fn empty()
{
assert_eq!(flatten(std::iter::empty::<Vec<()>>()).count(), 0);
}
#[test]
fn empty_wide()
{
assert_eq!(flatten(vec![Vec::<()>::new(), vec![], vec![]]).count(), 0);
}
#[test]
fn one()
{
assert_eq!(flatten(std::iter::once(vec!["a"])).count(), 1);
}
#[test]
fn two()
{
assert_eq!(flatten(std::iter::once(vec!["a", "b"])).count(), 2);
}
#[test]
fn two_wide()
{
assert_eq!(flatten(vec![vec!["a"], vec!["b"]]).count(), 2);
}
#[test]
fn reverse()
{
assert_eq!(
flatten(std::iter::once(vec!["a", "b"]))
.rev()
.collect::<Vec<_>>(),
vec!["b", "a"]
);
}
#[test]
fn reverse_wide()
{
assert_eq!(
flatten(vec![vec!["a"], vec!["b"]])
.rev()
.collect::<Vec<_>>(),
vec!["b", "a"]
);
}
#[test]
fn both_ends()
{
let mut iter = flatten(vec![vec!["a1", "a2", "a3"], vec!["b1", "b2", "b3"]]);
assert_eq!(iter.next(), Some("a1"));
assert_eq!(iter.next_back(), Some("b3"));
assert_eq!(iter.next(), Some("a2"));
assert_eq!(iter.next_back(), Some("b2"));
assert_eq!(iter.next(), Some("a3"));
assert_eq!(iter.next_back(), Some("b1"));
assert_eq!(iter.next(), None);
assert_eq!(iter.next_back(), None);
}
#[test]
fn inf()
{
let mut iter = flatten((0..).map(|i| 0..i));
assert_eq!(iter.next(), Some(0));
assert_eq!(iter.next(), Some(0));
assert_eq!(iter.next(), Some(1));
}
#[test]
fn deep()
{
assert_eq!(flatten(flatten(vec![vec![vec![0, 1]]])).count(), 2);
}
#[test]
fn ext()
{
assert_eq!(flatten([vec![vec![0, 1]]]).into_iter().our_flatten().count(), 2);
}
}
Q : So you could implement flatten as outer.flat_map(|inner| inner)
A : 是的。
Q : why not implement monad laws? it would be a lot less confusing
A : 本次是要探討迭代器的觀念。
Q : why do I sometimes see a ?Sized
A : 請看下面程式碼說明 :
Q : could you put the bounds into the trait IteratorExt instead of the function our_flatten? Or is that not good?
A : 可以,如下 :