Easy Rust

其他集合型別

Rust 還有很多集合型別。你可以在標準函式庫中的 https://doc.rust-lang.org/beta/std/collections/ 看到它們。那個頁面對為什麼要使用某種型別有很好的解釋，所以如果你不知道你想要什麼型別就去那裡。這些集合都在標準函式庫的 std::collections 裡面。使用它們最好的方法是使用 use 陳述式。就像我們對 enums 做的。我們將從非常常見的 HashMap 開始。

HashMap (和 BTreeMap)

HashMap 是由 鍵(key) 和 值(value) 組成的集合。你使用鍵來查詢與鍵匹配的值。你可以只用 HashMap::new() 建立一個新的HashMap，並使用.insert(key, value)來插入元素。

HashMap 是沒有順序的，所以如果你把 HashMap 中的每個鍵都一起印出來，可能每次會印出不同的結果。我們可以在範例中看到這一點：

use std::collections::HashMap; // 因此這是我們能只寫 HashMap 而不用每次都寫 std::collections::HashMap

struct City {
    name: String,
    population: HashMap<u32, u32>, // 這會記錄年度和該年度的人口數
}

fn main() {

    let mut tallinn = City {
        name: "Tallinn".to_string(),
        population: HashMap::new(), // 目前為止 HashMap 是空的
    };

    tallinn.population.insert(1372, 3_250); // 插入三筆年度資料
    tallinn.population.insert(1851, 24_000);
    tallinn.population.insert(2020, 437_619);


    for (year, population) in tallinn.population { // HashMap 型別是 HashMap<u32, u32> 所以它每次回傳有兩個元素的元組
        println!("In the year {} the city of {} had a population of {}.", year, tallinn.name, population);
    }
}

印出：

In the year 1372 the city of Tallinn had a population of 3250.
In the year 2020 the city of Tallinn had a population of 437619.
In the year 1851 the city of Tallinn had a population of 24000.

或者可能印出：

In the year 1851 the city of Tallinn had a population of 24000.
In the year 2020 the city of Tallinn had a population of 437619.
In the year 1372 the city of Tallinn had a population of 3250.

你可以看到它沒有按順序排列。

如果你想要一個可以排序的 HashMap，你可以用 BTreeMap。其實它們之間是非常相似的，所以我們可以快速的把我們的 HashMap 改成 BTreeMap 來看看。大家可以看到，這幾乎是一樣的程式碼。

use std::collections::BTreeMap; // HashMap 只改成 BTreeMap

struct City {
    name: String,
    population: BTreeMap<u32, u32>, // HashMap 只改成 BTreeMap
}

fn main() {

    let mut tallinn = City {
        name: "Tallinn".to_string(),
        population: BTreeMap::new(), // HashMap 只改成 BTreeMap
    };

    tallinn.population.insert(1372, 3_250);
    tallinn.population.insert(1851, 24_000);
    tallinn.population.insert(2020, 437_619);

    for (year, population) in tallinn.population {
        println!("In the year {} the city of {} had a population of {}.", year, tallinn.name, population);
    }
}

現在總是會印出：

In the year 1372 the city of Tallinn had a population of 3250.
In the year 1851 the city of Tallinn had a population of 24000.
In the year 2020 the city of Tallinn had a population of 437619.

現在我們再回來看看 HashMap。

只要把鍵放在 [] 的方括號裡，就可以得到 HashMap 的值。在接下來的這個範例中，我們將帶出 Bielefeld 這個鍵的值，也就是 Germany。但是要注意，因為如果沒有鍵，程式會崩潰(crash)。比如你寫了 println!("{:?}", city_hashmap["Bielefeldd"]);，那麼就會崩潰，因為 Bielefeldd 不存在。

如果你不確定會有鍵，你可以使用 .get()，它會回傳 Option。如果它存在就會是 Some(value)，如果不存在你將得到 None，而不是使程式崩潰。這就是為什麼 .get() 是從 HashMap 中取值較安全的方法。

use std::collections::HashMap;

fn main() {
    let canadian_cities = vec!["Calgary", "Vancouver", "Gimli"];
    let german_cities = vec!["Karlsruhe", "Bad Doberan", "Bielefeld"];

    let mut city_hashmap = HashMap::new();

    for city in canadian_cities {
        city_hashmap.insert(city, "Canada");
    }
    for city in german_cities {
        city_hashmap.insert(city, "Germany");
    }

    println!("{:?}", city_hashmap["Bielefeld"]);
    println!("{:?}", city_hashmap.get("Bielefeld"));
    println!("{:?}", city_hashmap.get("Bielefeldd"));
}

印出：

"Germany"
Some("Germany")
None

這是因為 Bielefeld 存在，但 Bielefeldd 不存在。

如果 HashMap 已經有一個鍵，當你試圖把它放進去時，它的值將被覆蓋：

use std::collections::HashMap;

fn main() {
    let mut book_hashmap = HashMap::new();

    book_hashmap.insert(1, "L'Allemagne Moderne");
    book_hashmap.insert(1, "Le Petit Prince");
    book_hashmap.insert(1, "섀도우 오브 유어 스마일");
    book_hashmap.insert(1, "Eye of the World");

    println!("{:?}", book_hashmap.get(&1));
}

印出 Some("Eye of the World")，因為它是你最後用 .insert() 的值。

檢查項目存在很容易，因為你可以用會回傳 Option 的 .get() 檢查：

use std::collections::HashMap;

fn main() {
    let mut book_hashmap = HashMap::new();

    book_hashmap.insert(1, "L'Allemagne Moderne");

    if book_hashmap.get(&1).is_none() { // is_none()回傳布林值: true如果是None, false如果是Some
        book_hashmap.insert(1, "Le Petit Prince");
    }

    println!("{:?}", book_hashmap.get(&1));
}

印出 Some("L\'Allemagne Moderne") 是因為已經有個 key 為 1，所以我們沒有插入 Le Petit Prince。

HashMap 有個非常有趣的方法叫做 .entry()，你肯定想試試。有了它，你可以在沒有鍵的情況下，加入一筆項目 (entry) 並用像是 .or_insert() 這類方法來插入值。有趣的是，它還傳回了可變參考，所以如果你想的話你可以改變它。首先的範例是我們每次插入書名到 HashMap 時，我們就在值插入 true。

讓我們假裝我們有個圖書館，並希望跟蹤我們的書籍。

use std::collections::HashMap;

fn main() {
    let book_collection = vec!["L'Allemagne Moderne", "Le Petit Prince", "Eye of the World", "Eye of the World"]; // Eye of the World 出現兩次

    let mut book_hashmap = HashMap::new();

    for book in book_collection {
        book_hashmap.entry(book).or_insert(true);
    }
    for (book, true_or_false) in book_hashmap {
        println!("Do we have {}? {}", book, true_or_false);
    }
}

印出：

Do we have Eye of the World? true
Do we have Le Petit Prince? true
Do we have L'Allemagne Moderne? true

但這並不是我們想要的。也許最好數一下書的數量，這樣我們就知道 世界之眼 有兩本。首先讓我們看看 .entry() 做了什麼，以及 .or_insert() 做了什麼。.entry() 其實是回傳了名為 Entry 的 enum：

#![allow(unused)]
fn main() {
pub fn entry(&mut self, key: K) -> Entry<K, V> // 🚧
}

可以查看Entry 文件的網頁。下面是它的原始程式碼的簡化版。K 表示 key，V 表示 value。

#![allow(unused)]
fn main() {
// 🚧
use std::collections::hash_map::*;

enum Entry<K, V> {
    Occupied(OccupiedEntry<K, V>),
    Vacant(VacantEntry<K, V>),
}
}

然後當我們呼叫 .or_insert() 時，它就會檢視列舉，並決定該怎麼做。

#![allow(unused)]
fn main() {
fn or_insert(self, default: V) -> &mut V { // 🚧
    match self {
        Occupied(entry) => entry.into_mut(),
        Vacant(entry) => entry.insert(default),
    }
}
}

有趣的是，它回傳 mut 的引用：&mut V。這意味著你可以使用 let 將其附加到變數上，並藉由改變這個變數來改變 HashMap 中的值。所以對於每本書，如果沒有項目，我們就會插入 0。而如果有的話，我們將在參考上使用 += 1 來增加數字。現在它看起來像這樣：

use std::collections::HashMap;

fn main() {
    let book_collection = vec!["L'Allemagne Moderne", "Le Petit Prince", "Eye of the World", "Eye of the World"];

    let mut book_hashmap = HashMap::new();

    for book in book_collection {
        let return_value = book_hashmap.entry(book).or_insert(0); // return_value 是個可變參考。如果原先沒東西，它會是 0
        *return_value +=1; // 現在 return_value 至少是 1。 且如果已經有另一本書，它會往上加 1
    }

    for (book, number) in book_hashmap {
        println!("{}, {}", book, number);
    }
}

重點在 let return_value = book_hashmap.entry(book).or_insert(0);。如果去掉 let，你會得到 book_hashmap.entry(book).or_insert(0)。沒有 let 時它什麼也不做：它只插入了 0，也沒有取得指向 0 的可變參考。所以我們把它連結到 return_value 上，這樣我們就可以保留 0。然後我們把值增加 1，這樣 HashMap 中的每本書都至少有 1。接著當 .entry() 再拿到 世界之眼 時，它就不會插入任何東西，但它給我們一個可變的 1。然後我們把它增加到 2，這也是為什麼它會印出這樣的結果：

L'Allemagne Moderne, 1
Le Petit Prince, 1
Eye of the World, 2

你也可以用 .or_insert() 做一些事情，比如插入向量，然後往向量裡推入資料。讓我們假設我們問街上的男女他們對一個政治家的看法。他們給出的評分從 0 到 10。然後我們要把這些數字放在一起，看看這個政治家是更受男性還是女性的歡迎。它可以像這樣：

use std::collections::HashMap;

fn main() {
    let data = vec![ // 原始資料
        ("male", 9),
        ("female", 5),
        ("male", 0),
        ("female", 6),
        ("female", 5),
        ("male", 10),
    ];

    let mut survey_hash = HashMap::new();

    for item in data { // 給的型別是 (&str, i32) 的元組
        survey_hash.entry(item.0).or_insert(Vec::new()).push(item.1); // 推入數字到向量裡
    }

    for (male_or_female, numbers) in survey_hash {
        println!("{:?}: {:?}", male_or_female, numbers);
    }
}

印出：

"female", [5, 6, 5]
"male", [9, 0, 10]

重點行是：survey_hash.entry(item.0).or_insert(Vec::new()).push(item.1);，所以如果它看到 "female"，就會檢查 HashMap 中是否已經有 "female"。如果沒有，它就會插入 Vec::new()，然後把數字推入。如果它看到 "female" 已經在 HashMap 中，它將不會插入新的向量，而只是將數字推入其中。

HashSet 和 BTreeSet

HashSet 實際上是只有 key 的 HashMap。在 HashSet 文件的網頁上面有解釋：

A hash set implemented as a HashMap where the value is (). 所以它是有鍵無值的 HashMap。

如果你只是想知道某個鍵是不是存在，或者不存在，你經常會選擇用 HashSet。

想像一下，你有 100 個隨機數，每個數字介於 1 和 100 之間。如果你這樣做，有些數字會出現不止一次，而有些數字根本不會出現。如果你把它們放到 HashSet 中，那麼你就會有一個所有已出現的數字列表。

use std::collections::HashSet;

fn main() {
    let many_numbers = vec![
        94, 42, 59, 64, 32, 22, 38, 5, 59, 49, 15, 89, 74, 29, 14, 68, 82, 80, 56, 41, 36, 81, 66,
        51, 58, 34, 59, 44, 19, 93, 28, 33, 18, 46, 61, 76, 14, 87, 84, 73, 71, 29, 94, 10, 35, 20,
        35, 80, 8, 43, 79, 25, 60, 26, 11, 37, 94, 32, 90, 51, 11, 28, 76, 16, 63, 95, 13, 60, 59,
        96, 95, 55, 92, 28, 3, 17, 91, 36, 20, 24, 0, 86, 82, 58, 93, 68, 54, 80, 56, 22, 67, 82,
        58, 64, 80, 16, 61, 57, 14, 11];

    let mut number_hashset = HashSet::new();

    for number in many_numbers {
        number_hashset.insert(number);
    }

    let hashset_length = number_hashset.len(); // 長度會告訴我們有多少數字在裡面
    println!("There are {} unique numbers, so we are missing {}.", hashset_length, 100 - hashset_length);

    // 讓我們看看漏了什麼數字
    let mut missing_vec = vec![];
    for number in 0..100 {
        if number_hashset.get(&number).is_none() { // 如果 .get() 回傳 None,
            missing_vec.push(number);
        }
    }

    print!("It does not contain: ");
    for number in missing_vec {
        print!("{} ", number);
    }
}

印出：

There are 66 unique numbers, so we are missing 34.
It does not contain: 1 2 4 6 7 9 12 21 23 27 30 31 39 40 45 47 48 50 52 53 62 65 69 70 72 75 77 78 83 85 88 97 98 99

BTreeSet 與 HashSet 相似，就像 BTreeMap 與 HashMap 相似一樣。如果把 HashSet 中的每一項都印出來，我們就不知道順序會是什麼了：

#![allow(unused)]
fn main() {
for entry in number_hashset { // 🚧
    print!("{} ", entry);
}
}

也許它會印出這樣：67 28 42 25 95 59 87 11 5 81 64 34 8 15 13 86 10 89 63 93 49 41 46 57 60 29 17 22 74 43 32 38 36 76 71 18 14 84 61 16 35 90 56 54 91 19 94 44 3 0 68 80 51 92 24 20 82 26 58 33 55 96 37 66 79 73。但它幾乎不會再以同樣的方式印出。

在這裡也一樣，如果你決定需要有序印出的話，把你的 HashSet 改成 BTreeSet 也很容易。在我們的程式碼中，我們只需要做兩處改動，就可以從 HashSet 切換到 BTreeSet。

use std::collections::BTreeSet; // 把 HashSet 改成 BTreeSet

fn main() {
    let many_numbers = vec![
        94, 42, 59, 64, 32, 22, 38, 5, 59, 49, 15, 89, 74, 29, 14, 68, 82, 80, 56, 41, 36, 81, 66,
        51, 58, 34, 59, 44, 19, 93, 28, 33, 18, 46, 61, 76, 14, 87, 84, 73, 71, 29, 94, 10, 35, 20,
        35, 80, 8, 43, 79, 25, 60, 26, 11, 37, 94, 32, 90, 51, 11, 28, 76, 16, 63, 95, 13, 60, 59,
        96, 95, 55, 92, 28, 3, 17, 91, 36, 20, 24, 0, 86, 82, 58, 93, 68, 54, 80, 56, 22, 67, 82,
        58, 64, 80, 16, 61, 57, 14, 11];

    let mut number_btreeset = BTreeSet::new(); // 把 HashSet 改成 BTreeSet

    for number in many_numbers {
        number_btreeset.insert(number);
    }
    for entry in number_btreeset {
        print!("{} ", entry);
    }
}

現在會依照順序印出： 0 3 5 8 10 11 13 14 15 16 17 18 19 20 22 24 25 26 28 29 32 33 34 35 36 37 38 41 42 43 44 46 49 51 54 55 56 57 58 59 60 61 63 64 66 67 68 71 73 74 76 79 80 81 82 84 86 87 89 90 91 92 93 94 95 96。

BinaryHeap

BinaryHeap 是種有趣的集合型別，因為它大部分是無序的，但也有一點有序性。它把最大的元素放前面，但其他元素是以任意順序排列的。

我們將用另一個列表來舉例，但這次資料少一些。

use std::collections::BinaryHeap;

fn show_remainder(input: &BinaryHeap<i32>) -> Vec<i32> { // 這個函式呈現BinaryHeap中剩餘部分。實際上
                                                         // 疊代器會比函式快- 我們會在之後學到。
    let mut remainder_vec = vec![];
    for number in input {
        remainder_vec.push(*number)
    }
    remainder_vec
}

fn main() {
    let many_numbers = vec![0, 5, 10, 15, 20, 25, 30]; // 這些數字是有序的

    let mut my_heap = BinaryHeap::new();

    for number in many_numbers {
        my_heap.push(number);
    }

    while let Some(number) = my_heap.pop() { // 如果有數字 .pop() 回傳 Some(number)，否則 None。且從前面 pop
        println!("Popped off {}. Remaining numbers are: {:?}", number, show_remainder(&my_heap));
    }
}

印出：

Popped off 30. Remaining numbers are: [25, 15, 20, 0, 10, 5]
Popped off 25. Remaining numbers are: [20, 15, 5, 0, 10]
Popped off 20. Remaining numbers are: [15, 10, 5, 0]
Popped off 15. Remaining numbers are: [10, 0, 5]
Popped off 10. Remaining numbers are: [5, 0]
Popped off 5. Remaining numbers are: [0]
Popped off 0. Remaining numbers are: []

你可以看到索引 0 的數字總是最大的25、20、15、10、5 然後是 0。但其它都不一樣。

使用 BinaryHeap<(u8, &str)> 的好方法是用在待處理事物的集合。這裡我們建立 BinaryHeap<(u8, &str)>，其中 u8 是任務重要性的數字。&str 是對要處理什麼的描述。

use std::collections::BinaryHeap;

fn main() {
    let mut jobs = BinaryHeap::new();

    // 加入一整天要做的工作
    jobs.push((100, "Write back to email from the CEO"));
    jobs.push((80, "Finish the report today"));
    jobs.push((5, "Watch some YouTube"));
    jobs.push((70, "Tell your team members thanks for always working hard"));
    jobs.push((30, "Plan who to hire next for the team"));

    while let Some(job) = jobs.pop() {
        println!("You need to: {}", job.1);
    }
}

總是會印出：

You need to: Write back to email from the CEO
You need to: Finish the report today
You need to: Tell your team members thanks for always working hard
You need to: Plan who to hire next for the team
You need to: Watch some YouTube

VecDeque

VecDeque 是一種既能從前面彈出元素，又能從後面彈出元素的 Vec。Rust 有 VecDeque 是因為 Vec 適合從後面(最後一個元素)彈出，但從前面彈出就不那麼好了。當你在 Vec 上使用 .pop() 的時候，它只是把右邊最後一個元素取出，其他的都不會動。但是如果你從其他地方取出元素，它右邊的所有元素都會被向左搬移一個位置。你可以在 .remove() 的文件描述中看到這一點：

Removes and returns the element at position index within the vector, shifting all elements after it to the left.

所以如果你這樣做：

fn main() {
    let mut my_vec = vec![9, 8, 7, 6, 5];
    my_vec.remove(0);
}

它將會刪除 9。索引 1 中的 8 將移到索引 0，索引 2 中的 7 將移到索引 1，以此類推。想像一個大停車場，每當有一輛車離開時，右邊所有的車都要移過來。

舉例來說這對電腦是很大的工作量。事實上，如果你在 Playground 上執行時，它很可能會因為工作量太大而直接放棄。

fn main() {
    let mut my_vec = vec![0; 600_000];
    for i in 0..600000 {
        my_vec.remove(0);
    }
}

這是有 60 萬個零的 Vec。每次你用 remove(0) 時，它就會把每個零向左搬移一個空間。並且它要做上 60 萬次。

用 VecDeque 就不用擔心這個問題了。它通常比 Vec 慢一點，但如果你要在資料兩端都做事情，那麼它就快多了。你可以直接從 Vec 用 VecDeque::from 做出來。那麼上面我們的程式碼就會像這樣：

use std::collections::VecDeque;

fn main() {
    let mut my_vec = VecDeque::from(vec![0; 600000]);
    for i in 0..600000 {
        my_vec.pop_front(); // pop_front 就像 .pop 但是從前面處理
    }
}

現在速度快了很多，在 Playground 上它不到一秒就結束，而不是放棄。

在接下來的這個範例中，我們有個記錄待處理事物的 Vec。接著我們做出 VecDeque，用 .push_front() 把它們放到前面，使得我們新增的第一個元素會是在右邊。但是我們推送的每個元素型別是 (&str, bool)：&str 是描述，false 表示還沒完成。我們用 done() 函式從後面彈出一個元素，但是我們不想刪除它。我們反而是把 false 改成 true，然後把它推到前面，使得我們可以保留它。

它看起來像這樣：

use std::collections::VecDeque;

fn check_remaining(input: &VecDeque<(&str, bool)>) { // 每個元素是 (&str, bool)
    for item in input {
        if item.1 == false {
            println!("You must: {}", item.0);
        }
    }
}

fn done(input: &mut VecDeque<(&str, bool)>) {
    let mut task_done = input.pop_back().unwrap(); // 後面彈出
    task_done.1 = true;                            // 它完成了 - 標記為 true
    input.push_front(task_done);                   // 現在把它放到前面
}

fn main() {
    let mut my_vecdeque = VecDeque::new();
    let things_to_do = vec!["send email to customer", "add new product to list", "phone Loki back"];

    for thing in things_to_do {
        my_vecdeque.push_front((thing, false));
    }

    done(&mut my_vecdeque);
    done(&mut my_vecdeque);

    check_remaining(&my_vecdeque);

    for task in my_vecdeque {
        print!("{:?} ", task);
    }
}

印出：

You must: phone Loki back
("add new product to list", true) ("send email to customer", true) ("phone Loki back", false)