疊代器(iterators)是遍歷序列中每個元素的一種抽象。
for
循環中),不會觸發任何操作。在 Rust 中疊代器是透過 Iterator
特徵來實現的,該特徵最低限度要求實作 next
方法,透過這個方法疊代器可以訪問下一個元素。呼叫 next
方法之後可能會有兩種結果:有值與沒有值,對應到 Option<T>
的 Some<T>
以及 None
,序列結束時回傳 None
。
最基本的疊代器用法如下:
fn main() {
let v1 = vec![1, 2, 3];
let v1_iter = v1.iter();
for val in v1_iter {
println!("{}", val);
}
}
因為疊代器惰性初始化的特性,創建疊代器 v1_iter
時還不會有額外的性能消耗或動作,要等到疊代器被使用的時候元素才會被消耗,操作才會被執行。
實際上,即使我們不特別把向量用 iter
方法轉成疊代器, for
迴圈也可以正常運行:
fn main() {
let v1 = vec![1, 2, 3];
for val in v1 {
println!("{}", val);
}
}
這是因為 Rust 的設計中,許多常見的數據結構,如向量、陣列等,都隱含地實現了 Iterator
特徵,所以編譯器自動幫我們把向量轉換成疊代器再去操作了。
Iterator
特徵看一下Iterator
特徵,這邊只列出next
方法,後面還有很多其他方法是有預設實作的,所以大部分情況只需要實作 next
方法就可以用其他方法的預設實作。
pub trait Iterator {
/// The type of the elements being iterated over.
type Item;
fn next(&mut self) -> Option<Self::Item>;
}
要實作 Iterator
特徵的話,還需要定義 Item
關聯型別,它會是被包在 Option
的 next
的回傳型別。
因為 Rust 的標準庫已經為包含向量在內的各種集合類型提供了高效的疊代器實作,所以我們甚至也不用實作 next
方法,可以呼叫 next
:
fn main() {
let v1 = vec![1, 2, 3];
let mut v1_iter = v1.iter(); // 這裡要使用 mut,因為後續操作會改變疊代器
match v1_iter.next() {
Some(value) => println!("{}", value),
None => println!("End of iterator"),
}
match v1_iter.next() {
Some(value) => println!("{}", value),
None => println!("End of iterator"),
}
}
可以想像成一開始的 v1_iter
是虛擬的頭,要等到第一次呼叫 next
的時候我們才會真正移動到第一個元素的位置,之後每次呼叫 next
都會移往下一個元素。這種寫法要記得在疊代器變數前面加上 mut
告訴編譯器我們後續會改變它,前面 for
迴圈的版本不需要是因為沒有直接呼叫 next
方法,而是讓 for
自動管理疊代器,它會在內部隱式地處理了疊代器的可變性,自動獲取疊代器並在每次迴圈迭代中呼叫 next
。這些細節由 for
自動管理,因此不需要顯式將疊代器標記為可變。
實際上在 Rust for element in collection
這種寫法是一種語法糖,編譯器會把這個語法糖展開成大概是下面這樣,底層其實就是疊代器。:
fn main() {
let v1 = vec![1, 2, 3];
// for number in v1 { // 編譯器會展開成呼叫疊代器的方式
// println!("{}", number);
// }
let mut v1_iter = v1.iter();
while let Some(number) = v1_iter.next() {
println!("{}", number);
}
}
我們設計一個簡易版的 Node
結構,有另外一個 LinkedList
會包含多個 Node
,並實作 Iterator
這樣我們就能用疊代器的方式來操作 LinkedList
。
為了簡化,Node
我們只用 Box<T>
處理,不考慮共享所有權和內部可變性,然後 LinkedList
增加 Node
的方式限定往前端加,這樣把新增的 Node
的 next
指向現有的 LinkedList
前端就好。
struct Node<T> {
value: T,
next: Option<Box<Node<T>>>,
}
impl<T> Node<T> {
fn new(value: T) -> Self {
Node { value, next: None }
}
}
struct LinkedList<T> {
head: Option<Box<Node<T>>>,
}
impl<T> LinkedList<T> {
fn new() -> Self {
LinkedList { head: None }
}
fn prepend(&mut self, value: T) {
let mut new_node = Box::new(Node::new(value));
// 將新節點的 next 指向當前的 head
new_node.next = self.head.take();
// 將 head 指向新的節點
self.head = Some(new_node);
}
}
impl<T: Clone> Iterator for LinkedList<T> {
type Item = T;
fn next(&mut self) -> Option<Self::Item> {
let current = self.head.take()?;
self.head = current.next; // 移到下一個節點
Some(current.value.clone()) // 回傳當前節點的值
}
}
fn main() {
let mut list = LinkedList::new();
list.prepend(3);
list.prepend(2);
list.prepend(1);
for value in list {
println!("{}", value);
}
}
實作 Iterator
可以思考呼叫第一次 next
之後希望取得的值是什麼,不然可能會和預想有落差,例如我中間調整好幾次要嘛只印出 2 和 3 或 1 和 2,要嘛印 3 陷入無限迴圈無法結束。以向量來說第一次呼叫 next
才會取得第一個索引的值,比照辦理的話可能疊代器設計上要有虛擬的頭, next
的邏輯會比較單純 。
相對 iter
方法內含的元素是不可變參考,還有 iter_mut
和 into_iter
分別對應可變參考和取得所有權的版本。
例如我想要修改原本向量上的元素就可以改用 iter_mut
取得可變參考來操作:
fn main() {
let mut v1 = vec![1, 2, 3];
let v1_iter = v1.iter_mut();
for val in v1_iter {
*val += 1
}
println!("{:?}", v1); // [2, 3, 4]
}
Iterator
其他方法定義在 Iterator
特徵的方法除了 next
還有其他很多好用的方法,可以根據會不會消耗疊代器分為兩類:消費適配器和疊代適配器。
消費適配器(consuming adaptors)是指會呼叫 next
的方法,例如呼叫 sum
:取得疊代器的所有權並重複呼叫 next
來遍歷所有項目把所有項目的數值加到總計,在遍歷結束時回傳總計。
fn main() {
let v1 = vec![1, 2, 3];
let v1_iter = v1.iter();
let total: i32 = v1_iter.sum(); // v1_iter 被消耗,無法再次使用
println!("{}", total); // 6
}
疊代配接器(iterator adaptors)則是消費適配器以外的方法,它們不會消耗原有的疊代器,而是在原有的疊代器上加一些屬性,例如 map
,用一個閉包當作參數,每次疊代器被消耗的時候對應的值會傳給這個閉包進行操作。
fn main() {
let v1 = vec![1, 2, 3];
let v1_iter = v1.iter();
let v2_total: i32 = v1_iter.map(|x| x + 1).sum(); // 方法可以串在一起直到把疊代器消耗掉
println!("v2_total: {}", v2_total); // 9
}
如果是呼叫疊代配接器可以串接多個,因為它們的過程都不會消耗原有的疊代器。而這也呼應到疊代器的惰性初始化,也就是說,在這個過程不會有額外的動作觸發,一直等到疊代器被消耗才會真的執行。
v2_total
編譯器會要求加上型別詮釋,原因是 sum
方法不足以判斷我們想要的實際型別是什麼。
collect
是另外一個常見的消費適配器,用來將疊代器中的元素收集到一個新的集合中。
我們把疊代配接器(map
)和消費適配器(collect
)拆成兩行來寫:
use std::slice::Iter;
use std::iter::Map;
fn main() {
let v1 = vec![1, 2, 3];
let v1_iter: Iter<'_, i32> = v1.iter();
let v2_iter: Map<Iter<'_, i32>, _> = v1_iter.map(|x| x + 1); // 可以分開寫
let v2: Vec<i32> = v2_iter.collect(); // 等到需要時再消耗疊代器
println!("{:?}", v2); // [2, 3, 4]
}
同樣的這邊呼叫 collect
的那行也必須加上型別詮釋。
為了方便解析,特別把 v1_iter
和 v2_iter
也加上型別詮釋。
Iter
是 Rust 標準庫中的一個具體類型,而 Iterator
是一個特徵。兩者的關係在於 Iter
型別實現了 Iterator
特徵,使得 Iter
能夠作為疊代器來使用。
可以觀察到v2_iter
和 v1_iter
的型別是不一樣的,因為呼叫 map
的關係多包了一層邏輯,代表經過 map
轉換的疊代器,它在每次遍歷時會應用轉換邏輯(閉包)並回傳結果。如果再呼叫一次 map
或其他疊代配接器就會再多一層。不過原始的疊代器都還是沒有被消耗。
即使如此,我們在 v1_iter.map
操作後還是無法再使用 v1_iter
,原因不是因為疊代器被消耗,而是因為 map
是會取得所有權的操作,這句代表所有權跑到 v2_iter
上了,如果要保有原有的向量,需要複製一份,不過就會多耗資源,必須看情況斟酌。
看 map
的源碼,可以看到是少見的用 self
不是 &self
。
fn map<B, F>(self, f: F) -> Map<Self, F>
where
Self: Sized,
F: FnMut(Self::Item) -> B,
{
Map::new(self, f)
}
filter
搭配獲取環境數值的閉包再舉一個情況是過濾原有的向量元素,只留下限制內的數值:
fn main() {
let limit = 2;
let v1 = vec![1, 2, 3];
let v1_iter = v1.iter();
let filter_result: Vec<&i32> = v1_iter.filter(|&&x| x <= limit).collect();
println!("{:?}", filter_result); // [1, 2]
}
如果不用閉包不用疊代器和 for
語法糖,大概要寫成下面這樣:
fn filter(v: &[i32], limit: i32) -> Vec<&i32> {
let mut result: Vec<&i32> = Vec::new();
for i in 0..v.len() {
if v[i] <= limit {
result.push(&v[i]);
}
}
result
}
fn main() {
let limit = 2;
let v1 = vec![1, 2, 3];
let filtered_result = filter(&v1, limit);
println!("{:?}", filtered_result); // [1, 2]
}
要建立新的向量、要用索引操作 for
迴圈,而整個 filter
函數用疊代器和閉包只要一行。
從這個例子就可以看出閉包和疊代器搭配之後精簡又清晰表達意圖的優勢。
結論是,疊代器雖然是高階抽象,但經過編譯器優化之後編譯出來的程式碼和用索引迴圈效能相比也毫不遜色,甚至有些情況效能是更好的。
可以試著執行以下的程式碼看看,就算把順序調換結果也差不多,這個情況幾乎都是疊代器比較快,除了編譯器有針對疊代器做優化外,還有一個主要原因是疊代器版本不用檢查界限。
use std::time::Instant;
fn main() {
let numbers: Vec<i64> = (0..100000000).collect();
// 手寫迴圈版本
let start = Instant::now();
let mut sum_for = 0;
for i in 0..numbers.len() {
sum_for += numbers[i];
}
let duration = start.elapsed();
println!("Sum using for loop: {}, took: {:?}", sum_for, duration);
// 疊代器版本
let start = Instant::now();
let sum_iter: i64 = numbers.iter().sum();
let duration = start.elapsed();
println!("Sum using iterator: {}, took: {:?}", sum_iter, duration);
}
另外可以比較看看用 cargo run
和 cargo run --release
的差別,--release
如以前提到的,是正式的編譯,才會做完整優化,差異十分巨大。
cargo run
Sum using for loop: 4999999950000000, took: 1.054879417s
Sum using iterator: 4999999950000000, took: 339.45675ms
cargo run --release
Sum using for loop: 4999999950000000, took: 30.10825ms
Sum using iterator: 4999999950000000, took: 13.721792ms
不過這邊不是完整的測試,不同電腦、不同次的執行結果可能會不太一樣,上面結果也只是我自己電腦執行幾次的結果而已,僅供參考,只能說疊代器至少效能不劣於手寫迴圈的版本。
和閉包一樣,疊代器也是 Rust 其中一種零成本抽象。這代表的是我們可以用高階概念來撰寫程式碼但又同時享有低階程式碼的效能,這是 Rust 的核心精神。
既具有可讀性、彈性等優勢,效能又不會打折,這讓疊代器成為 Rust 裡面十分重要而且最常使用的工具,在各種處理資料的場合可以讓我們用高階的概念寫出精簡易懂的程式碼。疊代器還有許多沒有介紹到的方法,未來值得花時間自己另外探索!