Rust迭代器深入與集合型別應用

Rust 的迭代器提供強大的資料處理能力，允許開發者以更簡潔、高效的方式遍歷和操作資料集合。理解迭代器的運作機制對於編寫高效能的 Rust 程式至關重要。標準函式庫提供的 Vec、Slice 等集合型別也與迭代器緊密結合，提供豐富的迭代方法和操作函式。對於自定義資料結構，例如二元樹，可以透過實作 Iterator 和 IntoIterator 特徵來支援迭代，進一步提升程式碼的可讀性和可維護性。深入瞭解迭代器的特性和使用方法，可以更好地利用 Rust 的語言特性，編寫出更具表現力的程式碼。

自定義迭代器實作與應用

在 Rust 程式語言中，迭代器是一種強大且靈活的工具，用於遍歷資料結構中的元素。除了使用標準函式庫提供的迭代器之外，開發者也可以為自己的資料結構實作自定義迭代器。本章節將探討如何為自定義資料結構實作 IntoIterator 和 Iterator 特徵（trait），並介紹相關的實作細節和應用案例。

實作簡單的迭代器：I32Range

首先，考慮一個簡化的範圍型別 I32Range，它表示一個從 start 到 end 的整數範圍。為了使 I32Range 可迭代，需要為其實作 Iterator 特徵。

struct I32Range {
    start: i32,
    end: i32,
}

impl Iterator for I32Range {
    type Item = i32;

    fn next(&mut self) -> Option<i32> {
        if self.start >= self.end {
            return None;
        }
        let result = Some(self.start);
        self.start += 1;
        result
    }
}

內容解密：

1. type Item = i32;：指定迭代器產生的元素型別為 i32。
2. fn next(&mut self) -> Option<i32>：實作 next 方法，用於產生下一個元素。如果 start 大於等於 end，傳回 None 表示迭代結束；否則，傳回當前的 start 值，並將其遞增。

由於 Rust 提供了對所有實作 Iterator 的型別的 IntoIterator 空泛實作，因此 I32Range 自動支援 into_iter 方法，可以直接在 for 迴圈中使用。

for k in (I32Range { start: 0, end: 14 }) {
    // ...
}

為二元樹實作迭代器

接下來，考慮一個更複雜的資料結構——二元樹。二元樹的定義如下：

enum BinaryTree<T> {
    Empty,
    NonEmpty(Box<TreeNode<T>>),
}

struct TreeNode<T> {
    element: T,
    left: BinaryTree<T>,
    right: BinaryTree<T>,
}

為了遍歷二元樹中的元素，需要實作一個迭代器。二元樹迭代器的實作比 I32Range 更為複雜，因為它需要維護遍歷的狀態。

內容解密：

1. 狀態管理：二元樹迭代器需要管理當前節點以及待存取的子樹。
2. 遍歷策略：常見的遍歷策略包括前序遍歷、中序遍歷和後序遍歷。

impl<T> IntoIterator for BinaryTree<T> {
    type Item = T;
    type IntoIter = BinaryTreeIter<T>;

    fn into_iter(self) -> Self::IntoIter {
        BinaryTreeIter::new(self)
    }
}

struct BinaryTreeIter<T> {
    stack: Vec<BinaryTree<T>>,
}

impl<T> BinaryTreeIter<T> {
    fn new(tree: BinaryTree<T>) -> Self {
        BinaryTreeIter { stack: vec![tree] }
    }
}

impl<T: Clone> Iterator for BinaryTreeIter<T> {
    type Item = T;

    fn next(&mut self) -> Option<T> {
        while let Some(tree) = self.stack.pop() {
            match tree {
                BinaryTree::Empty => continue,
                BinaryTree::NonEmpty(node) => {
                    self.stack.push(node.right);
                    self.stack.push(BinaryTree::NonEmpty(node.left));
                    return Some(node.element);
                }
            }
        }
        None
    }
}

內容解密：

1. into_iter 方法：將二元樹轉換為迭代器。
2. BinaryTreeIter 結構體：使用一個堆積疊來儲存待存取的節點。
3. next 方法：彈出堆積疊頂端的節點，並根據遍歷策略（此處為前序遍歷）將其子節點推入堆積疊。

Rust中的迭代器實作與集合型別

在Rust中，迭代器是一種用於遍歷資料結構的重要工具。本章節將探討如何為自定義資料結構實作迭代器，以及Rust標準函式庫中的集合型別。

為二元樹實作迭代器

實作迭代器的關鍵在於維護一個內部狀態，以便在每次呼叫next方法時傳回正確的元素。對於二元樹來說，這意味著要維護一個未存取節點的堆積疊。

// 定義二元樹的迭代器狀態
struct TreeIter<'a, T: 'a> {
    unvisited: Vec<&'a TreeNode<T>>,
}

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<T> BinaryTree<T> {
    fn iter(&self) -> TreeIter<T> {
        let mut iter = TreeIter { unvisited: Vec::new() };
        iter.push_left_edge(self);
        iter
    }
}

impl<'a, T: 'a> IntoIterator for &'a BinaryTree<T> {
    type Item = &'a T;
    type IntoIter = TreeIter<'a, T>;
    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<&'a T> {
        let node = match self.unvisited.pop() {
            None => return None,
            Some(n) => n,
        };
        self.push_left_edge(&node.right);
        Some(&node.element)
    }
}

內容解密：

1. TreeIter結構體用於維護二元樹迭代器的內部狀態，包括一個未存取節點的堆積疊unvisited。
2. push_left_edge方法將左子樹的節點推入堆積疊，以便進行中序遍歷。
3. iter方法傳回一個TreeIter例項，用於遍歷二元樹。
4. IntoIterator特徵的實作使得可以對二元樹的參照進行迭代。
5. Iterator特徵的實作定義了next方法的行為，用於傳回下一個元素。

使用迭代器遍歷二元樹

// 建立一個小型的二元樹
let subtree_l = make_node(Empty, "mecha", Empty);
let subtree_rl = make_node(Empty, "droid", Empty);
let subtree_r = make_node(subtree_rl, "robot", Empty);
let tree = make_node(subtree_l, "Jaeger", subtree_r);

// 使用for迴圈遍歷二元樹
let mut v = Vec::new();
for kind in &tree {
    v.push(*kind);
}
assert_eq!(v, ["mecha", "Jaeger", "droid", "robot"]);

內容解密：

1. 使用make_node函式建立一個二元樹。
2. 使用for迴圈遍歷二元樹，並將元素收集到一個向量中。
3. 驗證遍歷結果是否正確。

Rust標準函式庫中的集合型別

Rust標準函式庫提供了多種集合型別，包括Vec、HashMap等。這些集合型別具有以下特點：

• 移動語義：Rust使用移動語義來避免深複製值。
• 借用檢查：Rust的借用檢查器可以防止無效錯誤（invalidation errors）的發生。
• 無空值：Rust不使用空值，而是使用Option來表示可能不存在的值。

Rust 標準集合型別總覽

Rust 提供了一套豐富的標準集合型別，用於處理各種資料結構和演算法。這些集合型別都是泛型，可以根據不同的需求進行定製。

集合型別一覽

Rust 的標準集合型別包括以下八種：

1. Vec<T>：可增長的陣列，類別似於 C++ 的 vector 或 Python 的 list。
2. VecDeque<T>：雙端佇列，適合用作先進先出（FIFO）佇列。
3. LinkedList<T>：雙向鏈結串列，支援快速存取前端和後端元素。
4. BinaryHeap<T>：最大堆積，適合實作優先佇列。
5. HashMap<K, V>：鍵值對雜湊表，快速查詢特定鍵對應的值。
6. BTreeMap<K, V>：有序鍵值對表，保持鍵的有序性。
7. HashSet<T>：雜湊集合，快速新增、移除和檢查元素是否存在。
8. BTreeSet<T>：有序集合，保持元素有序。

Vec 詳細介紹

Vec<T> 是最常用的集合型別之一，是一種可增長的堆積疊分配陣列。

建立 Vec

可以使用 vec! 巨集來建立 Vec<T>：

let mut numbers: Vec<i32> = vec![];
let words = vec!["step", "on", "no", "pets"];
let mut buffer = vec![0u8; 1024]; // 1024 個零位元組

存取元素

可以使用索引來存取 Vec<T> 的元素：

let first_line = &lines[0];
let fifth_number = numbers[4]; // 需要實作 Copy 特性
let second_line = lines[1].clone(); // 需要實作 Clone 特性
let my_ref = &buffer[4..12];
let my_copy = buffer[4..12].to_vec(); // 需要實作 Clone 特性

安全存取元素

Rust 提供了多種方法來安全地存取元素：

• slice.first()：傳回第一個元素的參考。
• slice.last()：傳回最後一個元素的參考。
• slice.get(index)：傳回索引對應元素的參考，若索引超出範圍則傳回 None。

if let Some(item) = v.first() {
    println!("We got one! {}", item);
}

改變元素

可以使用可變參考來修改元素：

let mut slice = [0, 1, 2, 3];
{
    let last = slice.last_mut().unwrap(); // last 的型別是 &mut i32
    assert_eq!(*last, 3);
    *last = 100;
}
assert_eq!(slice, [0, 1, 2, 100]);

複製 Slice

可以使用 to_vec() 方法來複製整個 slice：

let v = [1, 2, 3, 4, 5, 6, 7, 8, 9];
assert_eq!(v.to_vec(), vec![1, 2, 3, 4, 5, 6, 7, 8, 9]);
assert_eq!(v[0..6].to_vec(), vec![1, 2, 3, 4, 5, 6]);

這個方法需要元素實作 Clone 特性。

其他集合型別的特點

• VecDeque<T>：適合用作 FIFO 佇列，支援在前端和後端快速新增和移除元素。
• LinkedList<T>：支援快速存取前端和後端元素，但通常比 Vec<T> 和 VecDeque<T> 慢。
• BinaryHeap<T>：最大堆積，適合實作優先佇列。
• HashMap<K, V> 和 BTreeMap<K, V>：鍵值對表，前者快速查詢特定鍵對應的值，後者保持鍵的有序性。
• HashSet<T> 和 BTreeSet<T>：集合，前者快速新增、移除和檢查元素是否存在，後者保持元素有序。

向量（Vec）與切片（Slice）的迭代與操作

向量（Vec）和切片（Slice）是 Rust 中常見的資料結構，它們支援多種迭代方式。根據「IntoIterator Implementations」一節的描述，向量和切片可以透過值或參照進行迭代。

迭代向量和切片

• 對 Vec<T> 進行迭代會產生型別為 T 的元素。這些元素會逐一移出向量，因此會消耗向量。
• 對 &[T; N]、&[T] 或 &Vec<T>（即陣列、切片或向量的參照）進行迭代，會產生型別為 &T 的元素，即對個別元素的參照，而不會移動這些元素。
• 對 &mut [T; N]、&mut [T] 或 &mut Vec<T> 進行迭代，則會產生型別為 &mut T 的元素。

此外，陣列、切片和向量還提供了 .iter() 和 .iter_mut() 方法，用於建立迭代器以產生對其元素的參照。

內容解密：

這段描述了 Rust 中向量和切片的迭代方式。透過不同的迭代方法，可以選擇是否移動元素或僅取得元素的參照。這對於處理資料集合時非常有用，因為它允許開發者根據需求選擇適當的迭代方式。

向量的增長與縮減

向量的長度是指它所包含的元素數量。相關方法包括：

• slice.len()：傳回切片的長度，型別為 usize。
• slice.is_empty()：如果切片不包含任何元素（即 slice.len() == 0），則傳回 true。

以下方法用於調整向量的大小，這些方法不適用於陣列和切片，因為它們一旦建立就無法調整大小。

• 向量中的所有元素都儲存在一個連續的、堆積分配的記憶體區塊中。向量的容量是指這個區塊可以容納的最大元素數量。
• Vec::with_capacity(n)：建立一個具有容量 n 的新空向量。
• vec.capacity()：傳回向量的容量，型別為 usize。總是滿足 vec.capacity() >= vec.len()。
• vec.reserve(n)：確保向量至少有足夠的剩餘容量來容納 n 個更多的元素，即 vec.capacity() 至少為 vec.len() + n。
• vec.reserve_exact(n)：與 vec.reserve(n) 類別似，但告訴向量不要為未來的增長分配額外的容量。
• vec.shrink_to_fit()：嘗試釋放向量容量大於長度時的多餘記憶體。

內容解密：

這部分介紹瞭如何管理向量的容量，包括建立具有特定容量的向量、預留容量以及縮減容量以釋放記憶體。這些操作對於最佳化記憶體使用和提高程式效能非常重要。

向量的元素操作

Vec<T> 提供了許多方法來新增或移除元素，從而改變向量的長度。這些方法通常透過可變參照來操作向量。

新增或移除單個元素

• vec.push(value)：將給定的值新增到向量的末尾。
• vec.pop()：移除並傳回向量的最後一個元素。傳回型別為 Option<T>，如果向量已空，則傳回 None。

在任意位置插入或移除元素

• vec.insert(index, value)：在 vec[index] 處插入給定的值，並將原有的元素向右移動。如果 index > vec.len()，則會 panic。
• vec.remove(index)：移除並傳回 vec[index]，並將後面的元素向左移動。如果 index >= vec.len()，則會 panic。

調整向量的長度

• vec.resize(new_len, value)：將向量的長度設定為 new_len。如果這增加了向量的長度，則會新增 value 的複製來填充新的空間。元素型別必須實作 Clone 特徵。
• vec.truncate(new_len)：將向量的長度減少到 new_len，丟棄範圍 vec[new_len..] 中的元素。
• vec.clear()：移除向量中的所有元素，等同於 vec.truncate(0)。

新增或移除多個元素

• vec.extend(iterable)：將給定可迭代物件中的所有元素按順序新增到向量的末尾。
• vec.split_off(index)：類別似於 vec.truncate(index)，但傳回一個包含從向量末尾移除的元素的新向量。
• vec.append(&mut vec2)：將另一個向量 vec2 中的所有元素移動到向量 vec 中，之後 vec2 將變為空。
• vec.drain(range)：移除向量中指定範圍的元素，並傳回一個對被移除元素的迭代器。

選擇性地移除元素

• vec.retain(test)：移除所有未透過給定測試的元素。測試函式或閉包的型別為 FnMut(&T) -> bool。
• vec.dedup()：刪除重複的元素。它掃描向量，發現相鄰元素相等時，刪除多餘的元素，只保留一個。

內容解密：

這部分詳細介紹了 Rust 向量提供的豐富操作方法，包括在末尾或任意位置新增或移除元素、調整向量大小、批次新增或移除元素，以及根據條件選擇性地移除元素。這些方法使得對向量的操作變得靈活高效。