Rust 學習筆記：向量與雜湊表

October 10, 2023 · Chinese

前言

本系列文書寫我個人初探 Rust 的學習筆記，章節劃分主要基於著名的 The Book，The Rust Programming Language，程式碼部分通常是個人閱讀消化後以方便說明的方式撰寫，完整學習建議直接參見該書。

The Rust Programming Language

該書也有中文翻譯版，不過個人閱讀以英文原版為主以鞏固對 terminology 的一致認識，我認為對未來閱讀以及查找資料會較為順暢。

不論語言該書都是相當優秀的學習資源，選擇適合你的語言開始學習 Rust 吧。

Appendix F: Translations of the Book

向量 Vector

vector 是和 array 類似的資料結構，差別在於 array 會在 stack 上配置記憶體因此必須為固定大小長度，vector 則會向 heap 配置記憶體，可以提供動態大小的元素集合，在多數情況會比 array 來得實用。

創建

使用 new 函式建立一個空 vector，注意我們必須給予 type annotation 明確指出型別。

let v1: Vec<i32> = Vec::new();

vec! macro 提供建立初始值的快捷方式。這種做法 Rust 能夠自行推導型別。

let v2 = vec![1, 2, 3];

新增

使用 push 在 vector 最後新增元素。注意必須使用 mut 讓 v1 可變

let mut v1 = vec![1, 2, 3];
v1.push(4);
println!("{:?}", v1);       // [1, 2, 3, 4]

使用 append 可將一個 vector 接在後面 (move)，被移過去的 vector 則會清空。

let mut v1 = vec![1, 2, 3];
let mut v2 = vec![4, 5, 6];
v1.append(&mut v2);
println!("{:?}", v1);       // [1, 2, 3, 4, 5, 6]
println!("{:?}", v2);       // []

讀取

使用索引語法讀取元素。

let v1 = vec![1, 2, 3];
println!("{}", v1[1]);      // 2

索引語法讀取超出 vector 的索引時會造成 panic。

let v1 = vec![1, 2, 3];
println!("{}", v1[5]);      // index out of bounds: the len is 3 but the index is 5

不確定索引是否存在時，使用 get 可以取得 Option<&T> 回來做 pattern matching。

let v1 = vec![1, 2, 3];
    
if let Some(x) = v1.get(5) {
    println!("{}", x);
} else {
    println!("Not found");
}

// output: Not found

移除

使用 pop 移除最後一個元素，pop 會回傳一個 Option 帶有被移除的元素，若 vector 為空則為 None。

let mut v1 = vec![1, 2, 3, 4, 5];
    
match v1.pop() {
    Some(x) => println!("{} removed.", x),  // 5 removed.
    _ => ()
}

println!("{:?}", v1);                       // [1, 2, 3, 4]

remove 可以在特定位置移除元素。

let mut v1 = vec![1, 2, 3, 4, 5];
    
v1.remove(2);

println!("{:?}", v1);                       // [1, 2, 4, 5]

因為 remove 會在移除後將後續元素全部往前 shift，因此 worst case 時間複雜度為 O(n)，如果不關心順序只是想移除某個元素時可以使用 swap_remove ，它會將最後一個元素移到被移除的位置，雖然順序會亂掉但時間複雜度為常數 O(1)。

let mut v1 = vec![1, 2, 3, 4, 5];
    
v1.swap_remove(2);

println!("{:?}", v1);                       // [1, 2, 5, 4]

遍歷

使用 for 遍歷 vector。

let v1 = vec![1, 2, 3];
    
for i in v1 {
    println!("{}", i);
}

// output: 
// 1
// 2
// 3

利用 enum 儲存不同型別資料

我們可以利用 enum 達成存入不同型別的資料的效果。

enum VT {
    String(String),
    Number(i32)
}

fn main() {
    let v1 = vec![VT::String(String::from("Hello")), VT::Number(5)];
    
    for i in v1 {
        match i {
            VT::String(v) => println!("String: {}", v),
            VT::Number(v) => println!("Number: {}", v)
        }
    }
}

// output:
// String: Hello
// Number: 5

雜湊表 HashMap

Map 是常見的 key-value pair 集合，Rust 中常用的 HashMap 定義在 standard library 中。

創建

要使用 HashMap 必須先引入，然後一樣使用 new 建立。

這邊建立一個 key 為 String、value 為 i32 的 HashMap。HashMap 的 key 必須為同一型別、value 也必須為同一型別。

use std::collections::HashMap;

fn main() {
    let m:HashMap<String, i32> = HashMap::new();
}

不是所有情況都必須要明確給定 type annotation，我們在建立後馬上 insert 一筆資料，Rust 能夠推導出其型別。

let mut m = HashMap::new();
m.insert(String::from("k1"), 1);

新增、修改

要新增資料必須使用 mut 使其可變，使用 insert 進插入一筆資料。

let mut m = HashMap::new();
m.insert(String::from("k1"), 1);

如果我們對同樣的 key 重複 insert，會將值覆蓋。

let mut m = HashMap::new();
m.insert(String::from("k1"), 1);
m.insert(String::from("k1"), 100);
println!("{:?}", m);        // {"k1": 100}

讀取

和 vector 相同我們可以使用 get 取得對應值。回傳的一樣是 Option。

let mut m = HashMap::new();
m.insert(String::from("k1"), 1);
m.insert(String::from("k2"), 2);

if let Some(x) = m.get(&String::from("k2")){
    println!("{}", x);
} else {
    println!("Not found");
}

// output:
// 2

移除

remove 用於移除特定資料。

let mut m = HashMap::new();
m.insert(String::from("k1"), 1);
m.remove(&String::from("k1"));
println!("{:?}", m);        // {}

遍歷

使用 for 對雜湊進行遍歷，要注意的是順序是不定的，每次執行順序可能不同。

let mut m = HashMap::new();
m.insert(String::from("k1"), 1);
m.insert(String::from("k2"), 2);

for (key, value) in &m {
    println!("{}: {}", key, value);
}

// output:
// k2: 2
// k1: 1

entry

一個實用的方法 entry，回傳一個 Entry enum，Occupied 代表已經被占用(key已經存在)，Vacant 則是還不存在。

entry 很適合用於要對 key 存在與否做不同處理時，以下程式若 key 已存在則將值+1，不存在則插入 1。

let mut m = HashMap::new();
m.insert(String::from("k1"), 1);

match m.entry(String::from("k1")) {
    Entry::Occupied(mut e) => *e.get_mut() += 1,
    Entry::Vacant(e) => {
        e.insert(1);
    }
}

println!("{:?}", m);        // {"k1": 2}
let mut m = HashMap::new();
m.insert(String::from("k1"), 1);

match m.entry(String::from("k1100")) {
    Entry::Occupied(mut e) => *e.get_mut() += 1,
    Entry::Vacant(e) => {
        e.insert(1);
    }
}

println!("{:?}", m);        // {"k1": 1, "k1100": 1}

有一個常用的便利方法 or_insert，可以只在 key 不存在時插入，避免使用 insert 會直接覆蓋。

let mut m = HashMap::new();
m.insert(String::from("k1"), 1);
m.entry(String::from("k1")).or_insert(100);
println!("{:?}", m);        // {"k1": 1}

BTreeMap

BTreeMap

std library 中有另一種 Map BTreeMap，不同於雜湊其使用 B 樹實作，相對於 HashMap 增刪讀取都是常數時間，BTreeMap 都需要對數時間，但它有額外提供一些功能且是有序的。

雖然目前我多數情況使用 HashMap 即可，但多認識 BTreeMap 也不錯，當需要的時候也知道有這項工具能夠使用。

下一篇會進入應該是最常使用的集合，字串 String。