Rust Book 勉強会 #4 第8章「Common Collections」

## この資料について

この資料は「[Rust Book 勉強会 #4](https://rust-kansai.connpass.com/event/118536/)」用の発表資料です。

* 担当: Yuya Kato (Nayutaya Inc.)
* 範囲: 第8章「Common Collections」
* 原文: [Common Collections - The Rust Programming Language](https://doc.rust-lang.org/book/ch08-00-common-collections.html#common-collections)

---

## 「コレクション」について

* 一般的なデータ型は、単一の値を表現します。例: `i32`
* コレクションは、複数の値を表現します。例: `Vec<i32>`
* 組み込み型である「配列」や「タプル」と違いは:
    * データはスタックではなく、ヒープに置かれます。
    * コンパイル時にサイズを決定する必要がなく、実行時に伸縮できます。

---

## この章で紹介するデータ型

* Rustの標準ライブラリには、数々の使いやすいデータ構造が含まれています。
* この章で紹介するのは以下の3つ:
    * <ruby><rb>Vector</rb><rt>ベクタ</rt></ruby>
    * <ruby><rb>String</rb><rt>ストリング</rt></ruby>
    * <ruby><rb>Hash Map</rb><rt>ハッシュマップ</rt></ruby>

---

## Vector

---

### Vector: `Vec<T>`

* 最初に紹介するのは`Vec<T>`です。
* 同じ型`T`の値を0個以上格納するデータ構造です。
* 値はメモリの連続した領域に置かれます。

---

### Vector: 空のVector

`Vec::new`関数で空の`Vec`を作ることができます。

```rs
// Listing 8-1: Creating a new, empty vector to hold values of type i32
let v: Vec<i32> = Vec::new();
```

この例では、内容がない（具体的なデータがない）ため、コンパイラは型を推論することができません。そのため、型アノテーションが必要です。

`Vec`の実装にはGenericsが使われています。詳細については第10章を参照してください。

簡単に言えば、上記の例の`<i32>`の部分を別の型に書き換えることで、任意の型についての同じデータ構造を作ることができます。

---

### Vector: 初期値を持つVector

`vec!`マクロを使うことで、初期値を伴う`Vec`を作ることができます。

```rs
// Listing 8-2: Creating a new vector containing values
let v = vec![1, 2, 3];
```

この例では、コンパイラは型を推論することできるので、型アノテーションは省略することができます。（もちろん書くこともできます）

---

### Vector: `vec!`マクロ

`vec!`は単なるマクロなので、`[]`以外の括弧も使えます。ですが、`[]`が一般的なので、それを使いましょう。

```rs
let v1 = vec![1, 2, 3];
let v2 = vec!{1, 2, 3};
let v3 = vec!(1, 2, 3);
assert_eq!(v1, v2);
assert_eq!(v1, v3);
```

---

### Vector: 値の追加

`push`関数で末尾に値を追加することができます。

```rs
// Listing 8-3: Using the push method to add values to a vector
let mut v = Vec::new();
v.push(5);
v.push(6);
v.push(7);
v.push(8);
```

この例では、`Vec::new`関数で空のVectorを作っているものの、あとに続く`push`関数の引数から推論できるため、型アノテーションは不要です。

また、値を変更するため`mut`キーワードが必要です。詳しくは第3章を参照してください。

---

### Vector: 値のドロップ（解放）

構造体のデータなどと同様に、Vectorもスコープから外れるとドロップされます。

```rs
// Listing 8-4: Showing where the vector and its elements are dropped
{
    let v = vec![1, 2, 3, 4];
    // do stuff with v
} // <- v goes out of scope and is freed here
```

Vectorがドロップされる時、その内容についてもドロップされます。

参照（リファレンス）をVector内に保持すると、話が少しだけややこしくなります。

---

### Vector: 値の取得

インデックス表記`[]`、または`get`関数を使って、指定したインデックスの値を取得することができます。インデックスは`0`から始まり、それは1番目の要素を指します。

```rs
// Listing 8-5: Using indexing syntax or the get method to access an item in a vector
let v = vec![1, 2, 3, 4, 5];
let third: &i32 = &v[2];
println!("The third element is {}", third);

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

```text
The third element is 3
The third element is 3
```

`get`関数は`Option<&T>`を返します。

---

### Vector: 値の取得（範囲外）

範囲外のインデックスにアクセスした場合、`[]`と`get`で挙動が異なります。

```rs
// Listing 8-6: Attempting to access the element at index 100 in a vector containing five elements
let v = vec![1, 2, 3, 4, 5];

let does_not_exist = &v[100]; // panic
let does_not_exist = v.get(100); // None
```

範囲外のインデックスにアクセスした場合:

* `[]`はpanicを発生させます。確実に値が存在すると仮定できる場合に便利です。
* `get`は`None`を返します。確実に値が存在すると言えない場合に便利です。外部から入力される場合など。

`Option<&T>`の取り扱いについては第6章を参照してください。

---

### Vector: 所有権

第4章で説明した通り、同一のスコープで可変参照と不変参照を同時に持つことはできません。

```rs
// Listing 8-7: Attempting to add an element to a vector while holding a reference to an item
let mut v = vec![1, 2, 3, 4, 5];
let first = &v[0];
v.push(6);
println!("The first element is: {}", first);
```

上記のコードでは、以下のようなコンパイルエラーが発生します。

```text
error[E0502]: cannot borrow `v` as mutable because it is also borrowed as immutable
  --> src/main.rs:10:5
   |
8  |     let first = &v[0];
   |                  - immutable borrow occurs here
9  |
10 |     v.push(6);
   |     ^^^^^^^^^ mutable borrow occurs here
11 |
12 |     println!("The first element is: {}", first);
   |                                          ----- borrow later used here
```

`first`は最初の要素の不変参照を取得しており、`push`は末尾を操作しているだけなので、このコードは一見動作するように見えます。
実際には末尾への値の追加は領域の拡張（再確保とコピー）が生じる可能性があります。その場合、最初の要素への参照は妥当な領域を指さなくなり、安全ではありません。

---

### Vector: 値の列挙 (1/2)

Vectorのすべての値について処理したい場合は、`for`を使うことができます。

```rs
// Listing 8-8: Printing each element in a vector by iterating over the elements using a for loop
let v = vec![100, 32, 57];
for i in &v {
    println!("{}", i);
}
```

```text
100
32
57
```

---

### Vector: 値の列挙 (2/2)

可変参照を得ることもできます。

```rs
// Listing 8-9: Iterating over mutable references to elements in a vector
let mut v = vec![100, 32, 57];
for i in &mut v {
    *i += 50;
}
```

`*`（参照解決演算子、dereference operator）については第15章で詳しく扱います。

---

### Vector: 複数の型の保持

Vectorは1つのデータ型しか扱うことができませんが、`enum`を使うことで、間接的に複数の型を扱うことができます。

```rs
// Listing 8-10: Defining an enum to store values of different types in one vector
enum SpreadsheetCell {
    Int(i32),
    Float(f64),
    Text(String),
}

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

上記は、スプレッドシートのセルを扱う例です。整数`i32`、浮動小数点数`f64`、文字列`String`を1つのVectorに格納しています。

もし実行時にしか分からない複数の型を取り扱う必要がある場合、`enum`のテクニックは使えません。その場合、トレイトオブジェクトを使うことができます。詳しくは第17章を参照してください。

---

## String

---

### String

`String`については第4章で軽く触れましたが、文字列は多くのプログラマが考えるより複雑なデータ構造です。ここではより深く見ていきましょう。

Rustでは`String`はバイトのコレクション（バイト列）として実装されています。ただ、人とコンピュータとでは解釈が異なり、それによりどう複雑になるのかを説明します。

---

### String: Rustにおける文字列

* Rustのコア言語には1つの文字列型`str`（文字列スライス）しかありません。（第4章を参照してください）
    * 文字列スライスは、UTF-8形式でエンコードされ、どこかに格納された文字列です。（例えば、実行バイナリに含まれる文字列リテラルなど）
* `String`は（コア言語ではなく）標準ライブラリで提供される型の1つです。
    * `String`は変更可能で、所有可能なUTF-8形式でエンコードされた文字列型です。
* 標準ライブラリには、他にも`OsString`、`OsStr`、`CString`、`CStr`などのそれぞれの用途を持つ文字列型が存在します。
    * 詳しくはAPIドキュメントを参照してください。

---

### String: 空の文字列の作成

`Vec<T>`と同じように、`new`関数を用いて空の文字列を作ることができます。

```rs
// Listing 8-11: Creating a new, empty String
let mut s = String::new();
```

`Vec<T>`で利用可能な操作の多くは`String`でも利用可能です。

---

### String: リテラル文字列からの作成

リテラル文字列（`str`）から文字列（`String`）を作る場合、`to_string`関数を使うことができます。`str`に限らず`Display`トレイトを実装している型で利用できます。

```rs
// Listing 8-12: Using the to_string method to create a String from a string literal
let data = "initial contents";

let s = data.to_string();

// the method also works on a literal directly:
let s = "initial contents".to_string();
```

別の方法として、`String::from`関数から作ることもできます。どちらを使うかはお好みでどうぞ。

```rs
// Listing 8-13: Using the String::from function to create a String from a string literal
let s = String::from("initial contents");
```

---

### String: UTF-8

`String`は文字列をUTF-8形式で取り扱うため、Unicodeで表現できる任意の文字を含むことができます。

```rs
// Listing 8-14: Storing greetings in different languages in strings
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");
```

上記の文字列は、すべて有効な文字列です。

---

### String: 文字列の追加

`String`も`Vec<T>`と同様、伸縮可能です。`push_str`関数を使うことで、文字列の末尾に文字列を追加することができます。

```rs
// Listing 8-15: Appending a string slice to a String using the push_str method
let mut s = String::from("foo");
s.push_str("bar");
```

`push_str`は所有権を取りません。そのため以下の例のように`s2`を使うことができます。

```rs
// Listing 8-16: Using a string slice after appending its contents to a String
let mut s1 = String::from("foo");
let s2 = "bar";
s1.push_str(s2);
println!("s2 is {}", s2);
```

---

### String: 文字の追加

`push`関数は、単一の文字を文字列の末尾に追加することができます。

```rs
// Listing 8-17: Adding one character to a String value using push
let mut s = String::from("lo");
s.push('l');
```

---

### String: `+`演算子 (1/2)

2つの文字列を結合するのに`+`演算子を使うこともできます。

```rs
// Listing 8-18: Using the + operator to combine two String values into a new String value
let s1 = String::from("Hello, ");
let s2 = String::from("world!");
let s3 = s1 + &s2; // note s1 has been moved here and can no longer be used
```

上記の結果、`s3`は`Hello, world!`となります。ただし、`s1`はムーブされるため、以降使うことができません。

---

### String: `+`演算子 (2/2)

`+`演算子は以下のように定義されている`add`関数を使っています。（なお、標準ライブラリ内における正確な定義ではありません。実際にはGenericsです）

```rs
fn add(self, s: &str) -> String {
```

上記の通り`+`演算子の右辺にあたる`s`は`&str`であり、`&String`ではありません。なのになぜ前述のコード（8-18）はコンパイルできるのでしょう？

それは「deref coercion」という機構が働くからです。詳しくは第15章を参照してください。

`+`演算子の左辺にあたる`self`は所有権を必要としています。そのため前述のコード（8-18）において`s1`はムーブされ、以降使うことができません。

`let s3 = s1 + &s2;`という文は一見、`s1`と`s2`をコピーし、新たな`s3`を生成しているように見えます。しかし実際には、`s1`に`s2`をコピーして追加しています。

---

### String: `format!`マクロ

`+`演算子を使って複数の文字列を結合する場合、少々分かりづらいコードとなります。

```rs
let s1 = String::from("tic");
let s2 = String::from("tac");
let s3 = String::from("toe");
let s = s1 + "-" + &s2 + "-" + &s3;
```

こういった場合には`format!`マクロが便利です。

```rs
let s1 = String::from("tic");
let s2 = String::from("tac");
let s3 = String::from("toe");
let s = format!("{}-{}-{}", s1, s2, s3);
```

`format!`マクロは`println!`と同じように書式化しますが、結果を標準出力ではなく、文字列として出力します。

---

### String: インデックスによるアクセス

多くのプログラミング言語では、文字列に含まれるそれぞれの文字にインデックスでアクセスできます。しかしRustはそうではありません。

例えば以下のコードはエラーになります。

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

```
error[E0277]: the trait bound `std::string::String: std::ops::Index<{integer}>` is not satisfied
 -->
  |
3 |     let h = s1[0];
  |             ^^^^^ the type `std::string::String` cannot be indexed by `{integer}`
  |
  = help: the trait `std::ops::Index<{integer}>` is not implemented for `std::string::String`
```

このエラーを理解するには、Rustにおける文字列の内部表現について知る必要があります。

---

### String: 内部表現

`String`は`Vec<u8>`をラッピングしたものです。

```rs
let len = String::from("Hola").len();
```

上記の例では、`len`は`4`です。`Hola`のそれぞれの文字はUTF-8では1バイトでエンコードされるためです。では以下の例ではどうでしょう？

```rs
let len = String::from("Здравствуйте").len();
```

上記の文字列は12文字に見えますが、`len`は`24`となります。1文字は複数バイトで構成されており、インデックスで参照された位置にある`u8`が有効な文字であるとは限りません。

---

### String: Grapheme

（より複雑な、ヒンディー語の文字の例。割愛します）

Rustの`String`は効率を重視して`Vec<u8>`として実装されていますが、有効な文字列であることを保証するために、インデックスによる文字へのアクセスはできません。

---

### String: 文字列のスライス

文字列のスライスを得ることは、多くの場合悪いアイデアです。それは、バイト列を得たいのか、文字群を得たいのか、Grapheme群を得たいのか明かではないからです。

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

let s = &hello[0..4];
```

上記の例では、4バイトを含む`&str`が得られます。では`&hello[0..1]`だとどうでしょうか？結果はパニックです。

```text
thread 'main' panicked at 'byte index 1 is not a char boundary; it is inside 'З' (bytes 0..2) of `Здравствуйте`', src/libcore/str/mod.rs:2188:4
```

クラッシュしうるので、文字列のスライスを扱う場合は十分に注意しましょう。

---

### String: 文字列の列挙（文字単位）

幸い、Rustの文字列には何を列挙するのか明確な関数があります。`chars`関数を使えば、文字単位（正確にはUnicodeスカラ値単位）で列挙できます。

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

結果は以下の通りです。

```text
न
म
स
्
त
े
```

---

### String: 文字列の列挙（バイト単位）

`bytes`関数を使えば、バイト単位で列挙できます。

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

結果は以下の通りです。

```text
224
164
// --snip--
165
135
```

---

### String: 文字列の取り扱いは単純じゃない

要するに、文字列の取り扱いは難しいものです。それぞれのプログラミング言語は、それぞれ異なった方法で複雑な「文字列」という存在にアプローチしています。

Rustの場合、すべてのプログラマが安全にUTF-8を扱える道を選びました。これにはいくらかのトレードオフもありますが、文字列の取り扱いに関するエラーに比べたらはるかにマシです。

---

## Hash Map

---

### Hash Map: 「Hash Map」とは？

* 「キー」と、それに関連する「値」を格納するためのデータ構造です。
* Rustでは`HashMap<K, V>`と表現されます。
* 効率よくアクセスするために「ハッシュ関数」を用いて生成した「ハッシュ値」が用いられます。
* 他のプログラミング言語では「map」「object」「hash table」「dictionary」「associative array」などと呼ばれることがあります。
* Vectorとは異なり、任意の型をキーとして用いることができます。
* 使用例: チーム名（文字列）をキーとして、チームのスコア（数値）を格納するデータ構造。

---

### Hash Map: 作成と要素の追加

`new`関数で空のデータを作成し、`insert`で要素を追加することができます。

```rs
// Listing 8-20: Creating a new hash map and inserting some keys and values
use std::collections::HashMap;

let mut scores = HashMap::new();

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

`HashMap`を使うためには`use`する必要があります。他の2つのコレクション（Vector、String）は自動的に取り込まれる機能がありますが、`HashMap`はそうではありません。

Vectorと同様、Hash Mapのデータもヒープに置かれます。上記の例の場合、キーは`String`で、値は`i32`です。

Vectorと同じように、キー、値には任意の型を用いることができますが、すべてのキー、すべての値のそれぞれは同じ型である必要があります。

---

### Hash Map: `collect`による変換

別の方法として、キーのVector、値のVectorからHash Mapを作成する方法があります。

```rs
// Listing 8-21: Creating a hash map from a list of teams and a list of scores
use std::collections::HashMap;

let teams  = vec![String::from("Blue"), String::from("Yellow")];
let initial_scores = vec![10, 50];

let scores: HashMap<_, _> = teams.iter().zip(initial_scores.iter()).collect();
```

ここでは型アノテーション`HashMap<_, _>`が必要です。`collect`関数は様々なデータ構造を生成することができるため、型アノテーションを行わないと、生成するデータ構造を特定できません。
ここでの`_`は、Rustに型推論を行わせることを意味します。

---

### Hash Map: 所有権

`i32`のような`Copy`トレイトを実装している型の場合、その値はHash Mapにコピーされます。
一方、`String`のようなownedな値の場合、その値はHash Mapにムーブされます。

```rs
// Listing 8-22: Showing that keys and values are owned by the hash map once they’re inserted
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 and field_value are invalid at this point, try using them and
// see what compiler error you get!
```

`field_name`と`field_value`の値はムーブされるため、`insert`を呼び出したあとは使うことができません。

参照を`insert`した場合、値はHash Mapにムーブされません。その代わり、Hash Mapが有効である限り、参照先が有効である必要があります。
これらについては第10章の「Validating References with Lifetimes」で詳しく説明します。

---

### Hash Map: 値へのアクセス

`get`関数で値を取得することができます。

```rs
// Listing 8-23: Accessing the score for the Blue team stored in the hash map
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");
let score = scores.get(&team_name);
```

`get`関数は`Option<&V>`を返します。キーに関連付けられた値が存在する場合は`Some(&V)`が、存在しない場合は`None`が返されます。

---

### Hash Map: キーと値の列挙

キーと値の組について、Vectorなどと同じように列挙することができます。

```rs
use std::collections::HashMap;

let mut scores = HashMap::new();

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

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

実行結果は以下の通りです。なお、列挙の順序は一定ではありません。

```text
Yellow: 50
Blue: 10
```

---

### Hash Map: 更新

各キーには、1つの値だけを関連付けることができます。そのため、キーが既に存在する場合の挙動を決める必要があります。

例えば、キーが既に存在した場合:

* 古い値を新しい値で置き換え、古い値を削除する。
* 新しい値を無視し、古い値を維持する。ただし、キーが存在しない場合は新しい値を追加する。
* 古い値を新しい値を組み合わせる。

---

### Hash Map: 値を上書きする

既に存在するキーを追加した場合、古い値は新しい値で置き換えられます。

```rs
// Listing 8-24: Replacing a value stored with a particular key
use std::collections::HashMap;

let mut scores = HashMap::new();

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

println!("{:?}", scores);
```

実行結果は以下の通りです。

```text
{"Blue": 25}
```

---

### Hash Map: キーが存在しない場合に追加する

「特定のキーが存在するかどうか確認し、無い場合は値を追加する」というのは、Hash Mapにおいてよく用いられる操作です。

Hash Mapには`entry`関数というAPIがあり、`or_insert`関数を持つ`Entry`列挙型を返します。

```rs
// Listing 8-25: Using the entry method to only insert if the key does not already have a value
use std::collections::HashMap;

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

scores.entry(String::from("Yellow")).or_insert(50);
scores.entry(String::from("Blue")).or_insert(50);

println!("{:?}", scores);
```

実行結果は以下の通りです。

```text
{"Yellow": 50, "Blue": 10}
```

---

### Hash Map: 古い値と新しい値を組み合わせる

他のよくあるケースとして「古い値と新しい値を組み合わせる」というのがあります。具体例として「単語を数える」例を以下に示します。

```rs
use std::collections::HashMap;

let text = "hello world wonderful world";

let mut map = HashMap::new();

for word in text.split_whitespace() {
    let count = map.entry(word).or_insert(0);
    *count += 1;
}

println!("{:?}", map);
```

実行結果は以下の通りです。

```text
{"wonderful": 1, "hello": 1, "world": 2}
```

`or_insert`関数は値への可変参照（`&mut V`）を返します。そのため`*`を用いることで値を更新することができます。

---

### Hash Map: ハッシュ関数

デフォルトでは、`HashMap`は「暗号学的に強度のある」ハッシュ関数を用います。これはDoS（サービス不能攻撃）を防ぐためです。
ただし、このハッシュ関数は遅いというトレードオフがあります。

もしパフォーマンスを改善したい場合、他のハッシュ関数に切り替えることもできます。
crates.ioには多くのハッシュ関数が登録されているため、それらを利用できるかも知れません。

---

## まとめ

---

### まとめ

* Vector、String、そしてHash Mapという3つのコレクション（データ構造）について説明しました。
* これらはデータを操作（保存、読み込み、変更）するプログラムが必要とする多くの機能を提供します。
* 演習問題:
    * 複数の整数を渡し、その平均値、中央値、頻出値を返す関数を書きましょう。
    * 文字列を「pig latin」に変換する関数を書きましょう。（詳細は割愛）
    * Hash MapとVectorを使って、従業員名と部署名を管理するCLIを書きましょう。（詳細は割愛）