Rustのデータ構造をナビゲート：ベクターからハッシュセットへ

Posted at 2025-03-09

Rust の標準ライブラリには、基本的なデータ構造として、ベクター（Vec）、ハッシュマップ（HashMap）、および集合（HashSet）が提供されています。これらの 3 つのデータ構造は、ほとんどのプログラミングシナリオで最も一般的で有用なものです。Rust の目標である「安全性」「並行性」「実用性」に適合する形で設計・提供されており、データの格納とアクセスのニーズを満たしながら、標準ライブラリの軽量性と効率性を維持しています。

ベクター（Vec）

ベクターは、Rust で最も一般的に使用される動的配列の実装です。高速なインデックスアクセス、動的なサイズ変更が可能であり、メモリ上で要素を連続的に格納するため、要素の走査が非常に効率的です。これは、現代の CPU のキャッシュ機構を活用することで実現されています。

fn main() {
    // 空のベクターを作成
    let mut numbers: Vec<i32> = Vec::new();

    // マクロを使用して初期化
    let mut names = vec!["Alice", "Bob", "Carol"];

    // ベクターに要素を追加
    numbers.push(1);
    numbers.push(2);
    numbers.push(3);

    // ベクターから要素を削除
    numbers.pop(); // 最後の要素を削除して返す

    // ベクター内の要素にアクセス
    if let Some(first_name) = names.get(0) {
        println!("The first name is: {}", first_name);
    }

    // ベクターを走査
    for name in &names {
        println!("{}", name);
    }

    // ベクターの要素を変更
    if let Some(first_name) = names.get_mut(0) {
        *first_name = "Dave";
    }

    // イテレータを使用して要素を処理
    let numbers_squared: Vec<i32> = numbers.iter().map(|&x| x * x).collect();
    println!("Squared numbers: {:?}", numbers_squared);

    // ベクターを拡張
    numbers.extend([4, 5, 6].iter().copied());

    // インデックスを直接指定してアクセス
    println!("Second name: {}", names[1]); // 注意：直接アクセスはpanicを引き起こす可能性がある
}

ベクターは、同じ型の要素のリストを扱う際に最適な選択肢です。文字列、整数、カスタム型を格納する場合でも、要素の追加、削除、ランダムアクセスを簡単に実現できます。

ハッシュマップ（HashMap）

ハッシュマップは、キーと値のペアでデータを格納するためのデータ構造で、ハッシュテーブルを内部的に使用しています。高速な検索、挿入、削除が可能であり、効率的なデータの取得や管理を実現する重要なデータ構造です。

use std::collections::HashMap;

fn main() {
    // 空のハッシュマップを作成
    let mut book_reviews: HashMap<String, String> = HashMap::new();

    // ハッシュマップに要素を追加
    book_reviews.insert("The Hobbit".to_string(), "Excellent fantasy book".to_string());
    book_reviews.insert("The Catcher in the Rye".to_string(), "Classic novel".to_string());

    // ハッシュマップの要素にアクセス
    if let Some(review) = book_reviews.get("The Hobbit") {
        println!("Review of The Hobbit: {}", review);
    }

    // ハッシュマップの要素を削除
    book_reviews.remove("The Catcher in the Rye");

    // ハッシュマップを走査
    for (book, review) in &book_reviews {
        println!("{}: {}", book, review);
    }

    // ハッシュマップの要素を更新
    book_reviews.entry("The Hobbit".to_string()).or_insert("No review found".to_string());
    book_reviews.entry("1984".to_string()).or_insert("Dystopian science fiction".to_string());

    let mut scores = HashMap::new();

    // insertを使用して直接挿入
    scores.insert("Blue", 10);
    scores.insert("Blue", 25); // 既存の値を上書き

    // entryを使用して更新または挿入
    scores.entry("Yellow").or_insert(50); // "Yellow"が存在しないため挿入
    scores.entry("Blue").or_insert(50); // "Blue"は既に存在するため何もしない

    // 結果: {"Blue": 25, "Yellow": 50}

    // キーの存在を確認
    if book_reviews.contains_key("1984") {
        println!("Review for 1984 is available.");
    }
}

ハッシュマップは、データをキーに基づいて素早く検索する必要がある場合に適しています。データベースのインデックス、キャッシュの実装などに使用され、柔軟なキーと値の関連付けを提供し、データの整理や取得をシンプルかつ効率的に行えます。

集合（HashSet）

集合（HashSet）は、重複しない要素を格納するためのデータ構造で、ハッシュテーブルを内部で利用しています。高速な検索、挿入、削除が可能です。

use std::collections::HashSet;

fn main() {
    // 空のセットを作成
    let mut numbers = HashSet::new();

    // セットに要素を追加
    numbers.insert(1);
    numbers.insert(2);
    numbers.insert(3);

    // セットから要素を削除
    numbers.remove(&3);

    // セットに要素が含まれているか確認
    if numbers.contains(&1) {
        println!("1 is in the set");
    }

    // セットを走査
    for number in &numbers {
        println!("{}", number);
    }

    // 集合演算：和集合、交差、差分、対称差

    // numbers は {1, 2} を含む
    let other_numbers = [2, 3, 4].iter().cloned().collect::<HashSet<_>>();
    // other_numbers は {2, 3, 4} を含む

    let union = numbers.union(&other_numbers).cloned().collect::<HashSet<_>>();
    println!("Union: {:?}", union);
    // 和集合： {1, 2} ∪ {2, 3, 4} = {1, 2, 3, 4}

    let intersection = numbers.intersection(&other_numbers).cloned().collect::<HashSet<_>>();
    println!("Intersection: {:?}", intersection);
    // 交差： {1, 2} ∩ {2, 3, 4} = {2}

    let difference = numbers.difference(&other_numbers).cloned().collect::<HashSet<_>>();
    println!("Difference: {:?}", difference);
    // 差集合： {1, 2} - {2, 3, 4} = {1}

    let symmetric_difference = numbers.symmetric_difference(&other_numbers).cloned().collect::<HashSet<_>>();
    println!("Symmetric Difference: {:?}", symmetric_difference);
    // 対称差： {1, 2} △ {2, 3, 4} = {1, 3, 4}
}

集合は、重複を許さないデータを扱う場合に適しています。例えば、ユーザー ID リストや特定の条件を満たすレコードの集合などに利用できます。また、和集合・交差・差分といった操作が可能なため、データの集合演算を効率的に行うのに役立ちます。

双方向リスト（LinkedList）

LinkedList<T> は Rust の標準ライブラリで提供される双方向リストの実装です。
Vec<T> に比べて、特にリストの先頭や末尾に要素を追加・削除する操作が効率的ですが、ランダムアクセスのパフォーマンスは劣ります。

use std::collections::LinkedList;

fn main() {
    // 空の双方向リストを作成
    let mut list: LinkedList<i32> = LinkedList::new();

    // リストの末尾に要素を追加
    list.push_back(1);
    list.push_back(2);

    // リストの先頭に要素を追加
    list.push_front(0);

    // リストの先頭と末尾の要素を削除
    assert_eq!(list.pop_front(), Some(0));
    assert_eq!(list.pop_back(), Some(2));

    // リストを走査
    for elem in list.iter() {
        println!("{}", elem);
    }

    // イテレータを使用してリストの要素を変更
    let mut iter_mut = list.iter_mut();
    if let Some(first_elem) = iter_mut.next() {
        *first_elem = 3;
    }

    // 変更後のリストを表示
    println!("Modified list: {:?}", list);
}

頻繁にリストの先頭や末尾に要素を追加・削除する必要がある場合、LinkedList は良い選択肢です。
ただし、要素のランダムアクセスが頻繁に行われる場合は、Vec<T> の方が適しています。

B 木マップ（BTreeMap）

BTreeMap<K, V> は B 木を基盤としたキーと値のペアを管理するデータ構造です。
HashMap<K, V> と異なり、キーが自動的にソートされるため、範囲検索や順序付きデータの管理に向いています。

use std::collections::BTreeMap;

fn main() {
    // 空の BTreeMap を作成
    let mut map: BTreeMap<String, i32> = BTreeMap::new();

    // BTreeMap に要素を追加
    map.insert("apple".to_string(), 3);
    map.insert("banana".to_string(), 2);
    map.insert("pear".to_string(), 4);

    // キーに対応する値を取得
    if let Some(v) = map.get("apple") {
        println!("apple: {}", v);
    }

    // キーと値のペアを削除
    map.remove("banana");

    // BTreeMap を走査（キーの順序でソートされている）
    for (key, value) in &map {
        println!("{}: {}", key, value);
    }

    // 範囲検索：apple 以上 pear 以下のキーを取得
    let range = map.range("apple".to_string()..="pear".to_string());
    for (key, value) in range {
        println!("Range query: {}: {}", key, value);
    }
}

データの順序が必要な場合、例えば範囲検索を頻繁に行う場合、BTreeMap は HashMap より適しています。
検索や挿入・削除操作の頻度が高く、キーの順序を保つ必要がある場合に有効です。

B 木セット（BTreeSet）

BTreeSet<T> は B 木を基盤にした集合で、要素を一意に管理し、常にソートされた状態を保持します。
HashSet<T> とは異なり、順序付きの要素管理や範囲検索をサポートします。

use std::collections::BTreeSet;

fn main() {
    // 空の BTreeSet を作成
    let mut set: BTreeSet<i32> = BTreeSet::new();

    // 要素を追加
    set.insert(12);
    set.insert(5);
    set.insert(18);

    // 要素の存在を確認
    if set.contains(&12) {
        println!("Set contains 12");
    }

    // 要素を削除
    set.remove(&5);

    // 集合を走査（ソートされた順序で表示）
    for num in &set {
        println!("{}", num);
    }

    // 範囲検索：10 以上 20 未満の要素を取得
    for num in set.range(10..20) {
        println!("Range query: {}", num);
    }
}

BTreeSet は、順序を保つ必要がある集合データを扱う場合に便利です。
範囲検索やソートが必要な場面では HashSet<T> より適しています。

二分ヒープ（BinaryHeap）

BinaryHeap<T> は、優先度付きキューを提供するデータ構造で、内部的には二分ヒープを使用しています。
標準の BinaryHeap<T> は最大ヒープ（最大値が優先される）として機能します。

use std::collections::BinaryHeap;

fn main() {
    // 空の BinaryHeap を作成
    let mut heap = BinaryHeap::new();

    // ヒープに要素を追加
    heap.push(1);
    heap.push(5);
    heap.push(2);

    // 最大値を取得（削除せず）
    if let Some(max) = heap.peek() {
        println!("Max element: {}", max);
    }

    // 最大値を削除して取得
    println!("Removed max element: {}", heap.pop().unwrap());

    // ヒープを走査（順序は保証されない）
    for num in &heap {
        println!("{}", num);
    }
}