Rust 100 Ex 🏃【26/37】 HashMap・順序・BTreeMap ～Rustの辞書型～

前の記事

• 【0】 準備 ← 初回
• ...
• 【25】 インデックス・可変インデックス ～インデックスもトレイト！～ ← 前回
• 【26】 HashMap・BTreeMap ～Rustの辞書型～ ← 今回

全記事一覧

• 【0】 準備
• 【1】 構文・整数・変数
• 【2】 if・パニック・演習
• 【3】 可変・ループ・オーバーフロー
• 【4】 キャスト・構造体 (たまにUFCS)
• 【5】 バリデーション・モジュールの公開範囲 ～ → カプセル化！～
• 【6】 カプセル化の続きと所有権とセッター ～そして不変参照と可変参照！～
• 【7】 スタック・ヒープと参照のサイズ ～メモリの話～
• 【8】 デストラクタ(変数の終わり)・トレイト ～終わりと始まり～
• 【9】 Orphan rule (孤児ルール)・演算子オーバーロード・derive ～Empowerment 💪 ～
• 【10】 トレイト境界・文字列・Derefトレイト ～トレイトのアレコレ～
• 【11】 Sized トレイト・From トレイト・関連型 ～おもしろトレイトと関連型～
• 【12】 Clone・Copy・Dropトレイト ～覚えるべき主要トレイトたち～
• 【13】 トレイトまとめ・列挙型・match式 ～最強のトレイトの次は、最強の列挙型～
• 【14】 フィールド付き列挙型とOption型 ～チョクワガタ～
• 【15】 Result型 ～Rust流エラーハンドリング術～
• 【16】 Errorトレイトと外部クレート ～依存はCargo.tomlに全部お任せ！～
• 【17】 thiserror・TryFrom ～トレイトもResultも自由自在！～
• 【18】 Errorのネスト・慣例的な書き方 ～Rustらしさの目醒め～
• 【19】 配列・動的配列 ～スタックが使われる配列と、ヒープに保存できる動的配列～
• 【20】 動的配列のリサイズ・イテレータ ～またまたトレイト登場！～
• 【21】 イテレータ・ライフタイム ～ライフタイム注釈ようやく登場！～
• 【22】 コンビネータ・RPIT ～ 「 Iterator トレイトを実装してるやつ」～
• 【23】 impl Trait ・スライス ～配列の欠片～
• 【24】 可変スライス・下書き構造体 ～構造体で状態表現～
• 【25】 インデックス・可変インデックス ～インデックスもトレイト！～
• 【26】 HashMap・順序・BTreeMap ～Rustの辞書型～
• 【27】 スレッド・'staticライフタイム ～並列処理に見るRustの恩恵～
• 【28】 リーク・スコープ付きスレッド ～ライフタイムに技あり！～
• 【29】 チャネル・参照の内部可変性 ～Rustの虎の子、mpscと Rc<RefCell<T>>～
• 【30】 双方向通信・リファクタリング ～返信用封筒を入れよう！～
• 【31】 上限付きチャネル・PATCH機能 ～パンクしないように制御！～
• 【32】 Send・排他的ロック(Mutex)・非対称排他的ロック(RwLock) ～真打 Arc<Mutex<T>> 登場～
• 【33】 チャネルなしで実装・Syncの話 ～考察回です～
• 【34】 async fn・非同期タスク生成 ～Rustの非同期入門～
• 【35】 非同期ランタイム・Futureトレイト ～非同期のお作法～
• 【36】 ブロッキング・非同期用の実装・キャンセル ～ラストスパート！～
• 【37】 Axumでクラサバ！ ～最終回～
• 【おまけ1】 Rustで勘違いしていたこと3選 🏄🌴 【100 Exercises To Learn Rust 🦀 完走記事 🏃】
• 【おまけ2】 【🙇 懺悔 🙇】Qiitanグッズ欲しさに1日に33記事投稿した話またはQiita CLIとcargo scriptを布教する的な何か

100 Exercise To Learn Rust 演習第26回になります。配列・イテレータ周りが多かった6章も今回が最後です！

今回の関連ページ

• 6.15. HashMap
• 6.16. BTreeMap

[06_ticket_management/15_hashmap] HashMap (いわゆる辞書型)

• 6.15. HashMap

問題はこちらです。

lib.rs (長いのでTODO周辺のみ抜粋)

// TODO: Replace `todo!()`s with the correct implementation.
//  Implement additional traits on `TicketId` if needed.

use std::collections::HashMap;
use std::ops::{Index, IndexMut};
use ticket_fields::{TicketDescription, TicketTitle};

#[derive(Clone)]
pub struct TicketStore {
    tickets: HashMap<TicketId, Ticket>,
    counter: u64,
}

#[derive(Clone, Copy, Debug, PartialEq)]
pub struct TicketId(u64);

#[derive(Clone, Debug, PartialEq)]
pub struct Ticket {
    pub id: TicketId,
    pub title: TicketTitle,
    pub description: TicketDescription,
    pub status: Status,
}

// ...省略...

impl TicketStore {
    pub fn new() -> Self {
        Self {
            tickets: todo!(),
            counter: 0,
        }
    }

    pub fn add_ticket(&mut self, ticket: TicketDraft) -> TicketId {
        let id = TicketId(self.counter);
        self.counter += 1;
        let ticket = Ticket {
            id,
            title: ticket.title,
            description: ticket.description,
            status: Status::ToDo,
        };
        todo!();
        id
    }

    // Index<TicketId> for TicketStore に関わる
    pub fn get(&self, id: TicketId) -> Option<&Ticket> {
        todo!()
    }

    // IndexMut<TicketId> for TicketStore に関わる
    pub fn get_mut(&mut self, id: TicketId) -> Option<&mut Ticket> {
        todo!()
    }
}

テストを含めた全体

lib.rs

// TODO: Replace `todo!()`s with the correct implementation.
//  Implement additional traits on `TicketId` if needed.

use std::collections::HashMap;
use std::ops::{Index, IndexMut};
use ticket_fields::{TicketDescription, TicketTitle};

#[derive(Clone)]
pub struct TicketStore {
    tickets: HashMap<TicketId, Ticket>,
    counter: u64,
}

#[derive(Clone, Copy, Debug, PartialEq)]
pub struct TicketId(u64);

#[derive(Clone, Debug, PartialEq)]
pub struct Ticket {
    pub id: TicketId,
    pub title: TicketTitle,
    pub description: TicketDescription,
    pub status: Status,
}

#[derive(Clone, Debug, PartialEq, Eq)]
pub struct TicketDraft {
    pub title: TicketTitle,
    pub description: TicketDescription,
}

#[derive(Clone, Debug, Copy, PartialEq, Eq)]
pub enum Status {
    ToDo,
    InProgress,
    Done,
}

impl TicketStore {
    pub fn new() -> Self {
        Self {
            tickets: todo!(),
            counter: 0,
        }
    }

    pub fn add_ticket(&mut self, ticket: TicketDraft) -> TicketId {
        let id = TicketId(self.counter);
        self.counter += 1;
        let ticket = Ticket {
            id,
            title: ticket.title,
            description: ticket.description,
            status: Status::ToDo,
        };
        todo!();
        id
    }

    pub fn get(&self, id: TicketId) -> Option<&Ticket> {
        todo!()
    }

    pub fn get_mut(&mut self, id: TicketId) -> Option<&mut Ticket> {
        todo!()
    }
}

impl Index<TicketId> for TicketStore {
    type Output = Ticket;

    fn index(&self, index: TicketId) -> &Self::Output {
        self.get(index).unwrap()
    }
}

impl Index<&TicketId> for TicketStore {
    type Output = Ticket;

    fn index(&self, index: &TicketId) -> &Self::Output {
        &self[*index]
    }
}

impl IndexMut<TicketId> for TicketStore {
    fn index_mut(&mut self, index: TicketId) -> &mut Self::Output {
        self.get_mut(index).unwrap()
    }
}

impl IndexMut<&TicketId> for TicketStore {
    fn index_mut(&mut self, index: &TicketId) -> &mut Self::Output {
        &mut self[*index]
    }
}

#[cfg(test)]
mod tests {
    use crate::{Status, TicketDraft, TicketStore};
    use ticket_fields::test_helpers::{ticket_description, ticket_title};

    #[test]
    fn works() {
        let mut store = TicketStore::new();

        let draft = TicketDraft {
            title: ticket_title(),
            description: ticket_description(),
        };
        let id = store.add_ticket(draft.clone());
        let ticket = &store[id];
        assert_eq!(draft.title, ticket.title);
        assert_eq!(draft.description, ticket.description);
        assert_eq!(ticket.status, Status::ToDo);

        let ticket = &mut store[id];
        ticket.status = Status::InProgress;

        let ticket = &store[id];
        assert_eq!(ticket.status, Status::InProgress);
    }
}

TicketStore の定義部に今回の問題要旨が詰まっています。

Rust

#[derive(Clone)]
pub struct TicketStore {
    tickets: HashMap<TicketId, Ticket>,
    counter: u64,
}

Ticket を保存しておくフィールド tickets が Vec<Ticket> から HashMap<TicketId, Ticket> に変わっています！

前々回 にて「 O(N) アクセスになっている件は次回以降の話題」と話しましたが、今回がその話題になります。ハッシュテーブル を用いることで、 tickets へのアクセス(理想)時間計算量を O(1) にしましょう！

解説

改変するところが多いですが、難しい部分はないです。 TicketId には Eq トレイト及び Hash トレイトを実装する必要があるため、その記述の追加と、その他は HashMap に存在するメソッドに既存の実装を差し替える形になります。

lib.rs (超抜粋)

+ use std::hash::Hash;

- #[derive(Clone, Copy, Debug, PartialEq)]
+ #[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
pub struct TicketId(u64);

// 以降は todo!() 埋め

impl TicketStore {
    pub fn new() -> Self {
        Self {
            tickets: HashMap::new(),
            counter: 0,
        }
    }

    pub fn add_ticket(&mut self, ticket: TicketDraft) -> TicketId {
        let id = TicketId(self.counter);
        self.counter += 1;
        let ticket = Ticket {
            id,
            title: ticket.title,
            description: ticket.description,
            status: Status::ToDo,
        };
        self.tickets.insert(id, ticket);
        id
    }

    pub fn get(&self, id: TicketId) -> Option<&Ticket> {
        self.tickets.get(&id)
    }

    pub fn get_mut(&mut self, id: TicketId) -> Option<&mut Ticket> {
        self.tickets.get_mut(&id)
    }
}

Eq トレイトは、語弊を恐れずに言うと(マサカリ要素)、「 a == b なら b == a が成り立つ」、みたいな、 PartialEq の実装が直感に反しないものになっていること¹を保証するよ、というマーカートレイトです。 Hash トレイト は今回の場合 TicketId を何かしらのハッシュ関数に掛けられることを示します。この両トレイトを実装していないと、ハッシュテーブルのキーとなる型になる資格はありません！ハッシュテーブルの仕組みを考えると当然に見えますね。

そしてこの両トレイトを意図通り実装していても多分抜ける HashMap のキーの必要条件に「要素が『等しい』なら、ハッシュ同士を比較しても『等し』くなければならない」というものがあります²。まぁ Eq トレイトを要求している時点で「変な実装はするなよ」という牽制になっているでしょうから気にする必要はないかもしれませんが、例えば「比較に際して構造体が持つ特定のフィールドを無視する」といったことをすると(それでも対称律等は守られるはずです。)、ハッシュの実装にて全フィールドを見るようにしてしまっている場合結果に不整合が出ることになります。こういったヘンテコな実装が必要な場合、 PartialEq の手動実装と Hash の手動実装は不整合が起きないように気を配る必要がありそうです。

[06_ticket_management/16_btreemap] 順序・BTreeMap (順序付き辞書型)

• 6.16. BTreeMap

問題はこちらです。

lib.rs (重要な部分のみ抜粋)

// TODO: Replace `todo!()`s with the correct implementation.
//  Implement `IntoIterator` for `&TicketStore`. The iterator should yield immutable
//  references to the tickets, ordered by their `TicketId`.
//  Implement additional traits on `TicketId` if needed.

use std::collections::BTreeMap;
use std::ops::{Index, IndexMut};
use ticket_fields::{TicketDescription, TicketTitle};

#[derive(Clone)]
pub struct TicketStore {
    tickets: BTreeMap<TicketId, Ticket>,
    counter: u64,
}

// ...省略...

#[cfg(test)]
mod tests {
    use crate::{Status, TicketDraft, TicketId, TicketStore};
    use ticket_fields::test_helpers::{ticket_description, ticket_title};

    #[test]
    fn works() {
        // ...省略...

        let ids: Vec<TicketId> = (&store).into_iter().map(|t| t.id).collect();
        let sorted_ids = {
            let mut v = ids.clone();
            v.sort();
            v
        };
        assert_eq!(ids, sorted_ids);
    }
}

問題ソースコード全体

lib.rs

// TODO: Replace `todo!()`s with the correct implementation.
//  Implement `IntoIterator` for `&TicketStore`. The iterator should yield immutable
//  references to the tickets, ordered by their `TicketId`.
//  Implement additional traits on `TicketId` if needed.

use std::collections::BTreeMap;
use std::ops::{Index, IndexMut};
use ticket_fields::{TicketDescription, TicketTitle};

#[derive(Clone)]
pub struct TicketStore {
    tickets: BTreeMap<TicketId, Ticket>,
    counter: u64,
}

#[derive(Clone, Copy, Debug, PartialEq)]
pub struct TicketId(u64);

#[derive(Clone, Debug, PartialEq)]
pub struct Ticket {
    pub id: TicketId,
    pub title: TicketTitle,
    pub description: TicketDescription,
    pub status: Status,
}

#[derive(Clone, Debug, PartialEq, Eq)]
pub struct TicketDraft {
    pub title: TicketTitle,
    pub description: TicketDescription,
}

#[derive(Clone, Debug, Copy, PartialEq, Eq)]
pub enum Status {
    ToDo,
    InProgress,
    Done,
}

impl TicketStore {
    pub fn new() -> Self {
        Self {
            tickets: todo!(),
            counter: 0,
        }
    }

    pub fn add_ticket(&mut self, ticket: TicketDraft) -> TicketId {
        let id = TicketId(self.counter);
        self.counter += 1;
        let ticket = Ticket {
            id,
            title: ticket.title,
            description: ticket.description,
            status: Status::ToDo,
        };
        todo!();
        id
    }

    pub fn get(&self, id: TicketId) -> Option<&Ticket> {
        todo!()
    }

    pub fn get_mut(&mut self, id: TicketId) -> Option<&mut Ticket> {
        todo!()
    }
}

impl Index<TicketId> for TicketStore {
    type Output = Ticket;

    fn index(&self, index: TicketId) -> &Self::Output {
        self.get(index).unwrap()
    }
}

impl Index<&TicketId> for TicketStore {
    type Output = Ticket;

    fn index(&self, index: &TicketId) -> &Self::Output {
        &self[*index]
    }
}

impl IndexMut<TicketId> for TicketStore {
    fn index_mut(&mut self, index: TicketId) -> &mut Self::Output {
        self.get_mut(index).unwrap()
    }
}

impl IndexMut<&TicketId> for TicketStore {
    fn index_mut(&mut self, index: &TicketId) -> &mut Self::Output {
        &mut self[*index]
    }
}

#[cfg(test)]
mod tests {
    use crate::{Status, TicketDraft, TicketId, TicketStore};
    use ticket_fields::test_helpers::{ticket_description, ticket_title};

    #[test]
    fn works() {
        let mut store = TicketStore::new();

        let n_tickets = 5;

        for i in 0..n_tickets {
            let draft = TicketDraft {
                title: ticket_title(),
                description: ticket_description(),
            };
            let id = store.add_ticket(draft.clone());
            let ticket = &store[id];
            assert_eq!(draft.title, ticket.title);
            assert_eq!(draft.description, ticket.description);
            assert_eq!(ticket.status, Status::ToDo);

            let ticket = &mut store[id];
            ticket.status = Status::InProgress;

            let ticket = &store[id];
            assert_eq!(ticket.status, Status::InProgress);
        }

        let ids: Vec<TicketId> = (&store).into_iter().map(|t| t.id).collect();
        let sorted_ids = {
            let mut v = ids.clone();
            v.sort();
            v
        };
        assert_eq!(ids, sorted_ids);
    }
}

先程は HashMap にしていた部分を BTreeMap (B木³式のマップ) に差し替えた問題となっています！

Rust

#[derive(Clone)]
pub struct TicketStore {
    tickets: BTreeMap<TicketId, Ticket>,
    counter: u64,
}

解説

先程の問題とほぼ同じです！ TicketId に対して Hash の代わりに PartialOrd, Ord を付ける点と、 IntoIterator トレイトを実装している点が異なります。

lib.rs

- #[derive(Clone, Copy, Debug, PartialEq)]
+ #[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord)]
pub struct TicketId(u64);

// HashMap のエクササイズと同様の改変を加えた上で、更にIntoIteratorについて

use std::array::IntoIter;

impl<'a> IntoIterator for &'a TicketStore {
    type Item = &'a Ticket;
    type IntoIter = Values<'a, TicketId, Ticket>;

    fn into_iter(self) -> Self::IntoIter {
        self.tickets.values()
    }
}

二分探索等で要素にアクセスするようになるがゆえに、ハッシュ値を取らないため Hash がなくなっています。平均アクセス時間計算量が O(1) からは離れましたが、順番を維持したまま要素を保存し、かつ高速にアクセスできるということで配列とハッシュテーブルの良いとこ取りになっていますね！ HashMap と合わせて使いこなせるようになりたいデータ構造です。

では次の問題に行きましょう！

次の記事: 【27】 スレッド・'staticライフタイム ～並列処理に見るRustの恩恵～

1. 本来なら数学の二項関係とかの話をするべきなのかもしれませんが、正直「数学的な関係を満たしている」というのもそれはそれで誤りな理解な気がしていて、あえて「直感に反しない」という表現にしました。マサカリはコメント欄へ ↩

2. 筆者はbookを誤読していましたが、逆(ハッシュが同一でも全体は等しくない)は別に問題ないようです。 ↩

3. 競プロ雑魚なので間違った理解をしているかもしれませんが、二分探索とかがしやすい木と認識していました。 ↩