2020/04/06

rust08 Common Collections

Collection 可包含多個值。跟內建的 array 與 tuple 不同，collection 是儲存在 heap，資料的大小可隨時異動。以下討論三個最常用的 collection

  • vector: 可逐項儲存數量可變的值
  • string: 是 char 的集合，也就是先前用過的 String
  • hash map: key - value pair。這是 map 的一種特殊實作的版本。

std library 提供的其他 collection 的文件

Storing Lists of Values with Vectors

vector 可儲存多個值，在記憶體中是一個接著一個排列。只能儲存相同類別的值。例如，適合儲存文件的逐行文字資料，或是購物車裡的商品價格。

建立新的 Vector

注意要加上 <i32> 資料類別，因為 compiler 無法判斷沒有任何值的 Vector 的資料型別。

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

vec! 是 Macro，因為已經有初始的值，compiler 就能推測出 v 的類別是 Vec<i32>

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

更新 Vector

要能改變 v，必須宣告為 mut 可變

let mut v = Vec::new();

v.push(5);
v.push(6);
v.push(7);
v.push(8);

Dropping a Vector Drops Its Elements

當 vector 離開 scope 被丟棄時，裡面的內容也會被丟棄。

{
    let v = vec![1, 2, 3, 4];

    // 使用 v

} // v 離開 scope 並被丟棄

讀取 Vector 的 elements

用 index 或是 get method，index 的結果是 reference，get method 回傳的結果是 Option<&T>。

let v = vec![1, 2, 3, 4, 5];

// &v[2] 透過 index 取得第三個資料
let third: &i32 = &v[2];
println!("The third element is {}", third);

// 用 get method
match v.get(2) {
    Some(third) => println!("The third element is {}", third),
    None => println!("There is no third element."),
}

如果要取得超過長度的 index，就會在執行時發生 error，這部分錯誤無法在編譯時被發現。而 get 並不會 crash，而是回傳 None。

let v = vec![1, 2, 3, 4, 5];

// thread 'main' panicked at 'index out of bounds: the len is 5 but the index is 100'
let does_not_exist = &v[100];

// None
let does_not_exist = v.get(100);

當程式獲得一個有效的 reference，borrow checker 會處理 ownership 及 borrowing rules 確保 vector 的引用永遠有效。ex: 因為在相同作用域中同時存在可變和不可變引用的規則，無法在獲得了 vector 的第一個元素的不可變引用後，嘗試在 vector 末尾增加一個元素。

let mut v = vec![1, 2, 3, 4, 5];

let first = &v[0];

v.push(6);

println!("The first element is: {}", first);

編譯時會發生錯誤

error[E0502]: cannot borrow `v` as mutable because it is also borrowed as immutable

在 vector 的結尾增加新元素時，可能發生沒有足夠空間將所有所有元素依次相鄰存放，這時候會分配新記憶體並將舊的元素複製到新的空間中。這時，第一個元素的引用就指向了被釋放的記憶體。借用規則會阻止程式陷入這種狀況。

Iterating over the Values in a Vector

用 for

let v = vec![100, 32, 57];
for i in &v {
    println!("{}", i);
}

// 也可以取得可變引用，然後修改裡面的值
let mut v = vec![100, 32, 57];
for i in &mut v {
    *i += 50;
}

Using an Enum to Store Multiple Types

當需要在 vector 儲存不同類別的資料時，可以使用 enum。vector 裡面儲存的類別，就是相同的 enum

enum SpreadsheetCell {
    Int(i32),
    Float(f64),
    Text(String),
}

let row = vec![
    SpreadsheetCell::Int(3),
    SpreadsheetCell::Text(String::from("blue")),
    SpreadsheetCell::Float(10.12),
];

但如果一開始無法知道要儲存到 vector 的所有類別，就無法使用 enum，要改用 chap17 的 trait。

Storing UTF-8 Encoded Text with Strings

通常在 String 會遇到三個問題：rust 會確保找出所有可能的錯誤、String 資料結構比想像中複雜、UTF-8。

String 本身就是 collection of bytes，再外加一些 method 讓 bytes 可用 text 解譯。接下來會討論 String 跟其他 collections 的相異處，例如：因為人類跟機器解讀 String 方法不同，造成String 的 indexing 比較複雜。

What is a String?

rust 在核心中只有一種 string type: string slice str，通常會以引用的方式出現 &str。chap4 有討論過 string slices 就是 references 到某些存在別處的 UTF-8 encoded string data。例如 String literal，就是存在程式的 binary 中，因此也是 string slices。

rust std library 提供的 String type 是 growable, mutable, owned, UTF-8 encoded string type。當 Rustacean 談到 rust 的 "string" 時，通常是同時代表 String 以及 string slice &str 這兩個。雖然大部分都是關於 String，這兩個類別在 std 都被廣泛使用，同時他們都是 UTF-8 encoded。

std library 還有其他 string 類別，例如：OsString, OsStr, CString, CStr。還有其他 libray crate 提供更多 string。類別是以 String 或是 Str 結尾， 對應到 owned 及 borrowed variants。

Creating new String

    // 建立新的 String
    let mut s = String::new();

    let data = "initial contents";
    // to_string 可用在任何實現了 Display trait 的類別
    let s = data.to_string();

    // 用 string literal 的 to_string 產生 String
    let s = "initial contents".to_string();

    // 用 String::from 產生 String
    let s = String::from("initial contents");

    // 可以儲存 UTF-8 的字串
    let hello = String::from("السلام عليكم");
    let hello = String::from("Dobrý den");
    let hello = String::from("Hello");
    let hello = String::from("שָׁלוֹם");
    let hello = String::from("नमस्ते");
    let hello = String::from("こんにちは");
    let hello = String::from("안녕하세요");
    let hello = String::from("你好");
    let hello = String::from("Olá");
    let hello = String::from("Здравствуйте");
    let hello = String::from("Hola");

Updating a String

可使用 push_str, push 增加 string 內容

    // push_str 增加 string slice，但 push_str 不需要獲得該 string 的 ownership
    let mut s = String::from("foo");
    s.push_str("bar");

    // 如果 push_str 獲取了 s2 的 ownership，就會無法列印資料
    let mut s1 = String::from("foo");
    let s2 = "bar";
    s1.push_str(s2);
    println!("s2 is {}", s2);

    // 用 push 增加 char
    let mut s = String::from("lo");
    s.push('l');

使用 + 或 format! 連接字串

    let s1 = String::from("Hello, ");
    let s2 = String::from("world!");
    let s3 = s1 + &s2; // 注意 s1 被移動了，不能繼續使用， s2 還可以繼續使用

    // + 的 函數定義類似這樣
    // fn add(self, s: &str) -> String {
    // &s2 是引用, add 只能將 String 及 &s 相加，不能將兩個 String 相加
    // 上面的 s2 會由 String 強制轉型 coerced 為 &str

    let s1 = String::from("tic");
    let s2 = String::from("tac");
    let s3 = String::from("toe");

    //let s = s1 + "-" + &s2 + "-" + &s3;
    // 可改用 format!，跟 println! 類似，且不會獲取 s2, s3 的 ownership
    let s = format!("{}-{}-{}", s1, s2, s3);

    println!("{}, {}, {}", s, s2, s3);

Indexing into Strings

如果用 index 語法取得 String 的一部分會發生錯誤，也就是說 rust 的 string 不支援 indexing

    let s1 = String::from("hello");
    let h = s1[0];

編譯錯誤

error[E0277]: the type `std::string::String` cannot be indexed by `{integer}`
 --> src/main.rs:5:13
  |
5 |     let h = s1[0];
  |             ^^^^^ `std::string::String` cannot be indexed by `{integer}`
  |
  = help: the trait `std::ops::Index<{integer}>` is not implemented for `std::string::String`

String 的實作方法

String 是一個 Vec<u8> 的封裝

    let len1 = String::from("Hola").len();
    // len 為 4

    let len2 = String::from("Здравствуйте").len();
    // len 為 24 不是 12，因為 unicode 每個字元需要 2 bytes

    println!("{}, {}", len1, len2);

因此 char 的 index 並不一定能對應到有效的 unicode。

假設 rust 可以這樣寫

let hello = "Здравствуйте";
let answer = &hello[0];

З 的第一個byte 為 208, 第二個是 151， answer 應該為 208，但 208 不是一個正常的 unicode。為了避免發生這樣的問題，rust 直接拒絕這樣的寫法，而是給我們編譯錯誤的訊息。

Bytes and Scalar Values and Grapheme Clusters

rust 有三種方式理解 string: bytes, scalar values, grapheme clusters (字形集合)

例如 印度語單詞 “नमस्ते” 存在 Vector 為

[224, 164, 168, 224, 164, 174, 224, 164, 184, 224, 165, 141, 224, 164, 164,
224, 165, 135]

有 18 bytes，但從 unicode 來說，應該要是

['न', 'म', 'स', '्', 'त', 'े']

但第四與第六都不是字母，以 grapheme cluster 方式理解，應該為

["न", "म", "स्", "ते"]

另外因為 String 透過 index 取得 slice 的時間預期為 O(1)，但 String 每次都必須要從開頭開始，無法確保O(1) 這樣的效能。

因此 rust 的 string 不支援 indexing

Slicing Strings

這是可能會造成程式 crash 的 method。可以用 [] 及 range 取得 string slice

    let hello = "Здравствуйте";

    // 這些字元都是 2 bytes
    // s 將會是 “Зд”
    let s = &hello[0..4];

    // 如果獲取 &hello[0..1] ，會造成程式 panic
    let s2 = &hello[0..1];
thread 'main' panicked at 'byte index 1 is not a char boundary; it is inside 'З' (bytes 0..2) of `Здравствуйте`', src/libcore/str/mod.rs:2027:5

Iterating over Strings

for c in "नमस्ते".chars() {
    println!("{}", c);
}
न
म
स
्
त
े

也可以轉換為 bytes

for b in "नमस्ते".bytes() {
    println!("{}", b);
}

Storing Keys with Associated Values in Hash Maps

HashMap<K, V> 透過 hashing function 決定如何將 key, value 放入 memory

Creating a New Hash Map

    // HashMap 沒有倍 prelude 自動引用
    use std::collections::HashMap;

    // 類似 vector，HashMap 的 key 為 String, value 為 i32
    let mut scores = HashMap::new();
    scores.insert(String::from("Blue"), 10);
    scores.insert(String::from("Yellow"), 50);


    // 也可以用 vector 的 collect 產生 Hash Map
    let teams  = vec![String::from("Blue"), String::from("Yellow")];
    let initial_scores = vec![10, 50];

    // 先透過 zip 產生 tuple 的 vector，再呼叫 collect
    let scores: HashMap<_, _> = teams.iter().zip(initial_scores.iter()).collect();
    println!("{:?}", scores);
    // {"Yellow": 50, "Blue": 10}

Hash Maps and Ownership

對於像 i32 實現 Copy trait 的類別，值可以複製到 Hash Map，但對於 String 有 ownership 的值，其值會因為 move 而轉職給 Hash Map

    use std::collections::HashMap;

    let field_name = String::from("Favorite color");
    let field_value = String::from("Blue");

    let mut map = HashMap::new();
    map.insert(field_name, field_value);
    // 這裡 field_name 和 field_value 不再有效，不能再使用

如果是用 reference，這些引用指向的值，雖 ownership 不會移動給 Hash Map，但必須在 map 有效時同樣有效。

存取 Hash Map 的 Values

    use std::collections::HashMap;

    let mut scores = HashMap::new();

    scores.insert(String::from("Blue"), 10);
    scores.insert(String::from("Yellow"), 50);

    let team_name = String::from("Blue");
    // get 會回傳 Option<V>，如果不存在會回傳 None
    let score = scores.get(&team_name);
    println!("{:?}", score);
    // Some(10)


    // use std::collections::HashMap;

    let mut scores = HashMap::new();

    scores.insert(String::from("Blue"), 10);
    scores.insert(String::from("Yellow"), 50);

    // 用 for iterate Hash Map
    for (key, value) in &scores {
        println!("{}: {}", key, value);
    }
    //Yellow: 50
    //Blue: 10

更新 Hash Map

覆蓋舊的 value: insert

    use std::collections::HashMap;

    let mut scores = HashMap::new();

    scores.insert(String::from("Blue"), 10);
    scores.insert(String::from("Blue"), 25);

    println!("{:?}", scores);
    // {"Blue": 25}

只在沒有 value 時 insert: entry

    use std::collections::HashMap;

    let mut scores = HashMap::new();
    scores.insert(String::from("Blue"), 10);

    scores.entry(String::from("Yellow")).or_insert(50);
    // 不會改成 50
    scores.entry(String::from("Blue")).or_insert(50);

    println!("{:?}", scores);
    // {"Yellow": 50, "Blue": 10}

根據舊的值，更新新值

例如記錄某個單詞出現幾次

    use std::collections::HashMap;

    let text = "hello world wonderful world";

    let mut map = HashMap::new();

    // or_insert 會回傳 &mut V，可變引用
    for word in text.split_whitespace() {
        let count = map.entry(word).or_insert(0);
        *count += 1;
    }

    println!("{:?}", map);
    // {"wonderful": 1, "hello": 1, "world": 2}

Hashing Functions

HashMap 預設使用 "cryptographically strong" hashing function，可防止 Denial of Service (DoS) 攻擊。這不是最快的演算法，但犧牲性能提高安全性。可利用 hasher 切換使用其他 hashing function。hasher 是實作 BuildHasher trait 的類別。crates.io 可找到其他常用的 hasher hashing function。

References

The Rust Programming Language

中文版

中文版 2

張貼者： 於
標籤：

沒有留言:

張貼留言

訂閱： 張貼留言 (Atom)