課題15: スマートポインタ (Smart Pointers)

マンダトリー要件

問題1: 二分探索木の実装（30点）

Boxを使って二分探索木を実装しなさい。

type Link = Option<Box<Node>>;

#[derive(Debug)]
struct Node {
    value: i32,
    left: Link,
    right: Link,
}

struct BST {
    root: Link,
}

impl BST {
    fn new() -> Self {
        // TODO: 実装 (5点)
    }

    fn insert(&mut self, value: i32) {
        // TODO: 実装 (10点)
    }

    fn contains(&self, value: i32) -> bool {
        // TODO: 実装 (10点)
    }

    fn inorder(&self) -> Vec<i32> {
        // TODO: 実装 (5点)
        // 中順走査（左→根→右）の結果を返す
    }
}

fn main() {
    let mut bst = BST::new();

    bst.insert(5);
    bst.insert(3);
    bst.insert(7);
    bst.insert(1);
    bst.insert(9);

    assert!(bst.contains(5));
    assert!(bst.contains(7));
    assert!(!bst.contains(10));

    let sorted = bst.inorder();
    assert_eq!(sorted, vec![1, 3, 5, 7, 9]);

    println!("Problem 1 passed!");
}

評価基準:

  • newの実装: 5点
  • insertの実装: 10点
  • containsの実装: 10点
  • inorderの実装: 5点

---

問題2: グラフ構造の実装（30点）

RcとRefCellを使って無向グラフを実装しなさい。

use std::cell::RefCell;
use std::rc::Rc;

type NodeRef = Rc<RefCell<GraphNode>>;

#[derive(Debug)]
struct GraphNode {
    id: usize,
    neighbors: Vec<NodeRef>,
}

struct Graph {
    nodes: Vec<NodeRef>,
}

impl Graph {
    fn new() -> Self {
        // TODO: 実装 (5点)
    }

    fn add_node(&mut self, id: usize) -> NodeRef {
        // TODO: 実装 (5点)
    }

    fn add_edge(&mut self, from: usize, to: usize) {
        // TODO: 実装 (10点)
        // 無向グラフなので両方向に追加
    }

    fn get_neighbors(&self, id: usize) -> Vec<usize> {
        // TODO: 実装 (10点)
        // 指定されたノードの隣接ノードのIDリストを返す
    }
}

fn main() {
    let mut graph = Graph::new();

    let n0 = graph.add_node(0);
    let n1 = graph.add_node(1);
    let n2 = graph.add_node(2);
    let n3 = graph.add_node(3);

    graph.add_edge(0, 1);
    graph.add_edge(0, 2);
    graph.add_edge(1, 2);
    graph.add_edge(2, 3);

    let neighbors_0 = graph.get_neighbors(0);
    assert_eq!(neighbors_0.len(), 2);
    assert!(neighbors_0.contains(&1));
    assert!(neighbors_0.contains(&2));

    let neighbors_2 = graph.get_neighbors(2);
    assert_eq!(neighbors_2.len(), 3);

    println!("Problem 2 passed!");
}

評価基準:

  • newの実装: 5点
  • add_nodeの実装: 5点
  • add_edgeの実装: 10点
  • get_neighborsの実装: 10点

---

問題3: スレッドセーフなカウンタ（20点）

ArcとMutexを使ってスレッドセーフなカウンタを実装しなさい。

use std::sync::{Arc, Mutex};
use std::thread;

struct Counter {
    count: Arc<Mutex<i32>>,
}

impl Counter {
    fn new() -> Self {
        // TODO: 実装 (5点)
    }

    fn increment(&self) {
        // TODO: 実装 (5点)
    }

    fn get(&self) -> i32 {
        // TODO: 実装 (5点)
    }

    fn clone_counter(&self) -> Counter {
        // TODO: 実装 (5点)
        // Arcをクローンして新しいCounterを返す
    }
}

fn main() {
    let counter = Counter::new();
    let mut handles = vec![];

    for _ in 0..10 {
        let counter = counter.clone_counter();
        let handle = thread::spawn(move || {
            for _ in 0..1000 {
                counter.increment();
            }
        });
        handles.push(handle);
    }

    for handle in handles {
        handle.join().unwrap();
    }

    assert_eq!(counter.get(), 10000);
    println!("Problem 3 passed!");
}

評価基準:

  • newの実装: 5点
  • incrementの実装: 5点
  • getの実装: 5点
  • clone_counterの実装: 5点

---

ボーナス課題

ボーナス1: ツリー構造の実装（10点）

親子関係を持つツリー構造を実装しなさい（Weakを使用）。

use std::cell::RefCell;
use std::rc::{Rc, Weak};

type NodeRef = Rc<RefCell<TreeNode>>;
type ParentRef = Weak<RefCell<TreeNode>>;

#[derive(Debug)]
struct TreeNode {
    value: i32,
    parent: RefCell<ParentRef>,
    children: RefCell<Vec<NodeRef>>,
}

impl TreeNode {
    fn new(value: i32) -> NodeRef {
        // TODO: 実装
    }

    fn add_child(parent: &NodeRef, child: NodeRef) {
        // TODO: 実装
        // 親の子リストに追加 & 子の親を設定
    }

    fn get_parent(&self) -> Option<NodeRef> {
        // TODO: 実装
        // Weakをアップグレードして親を取得
    }

    fn print_tree(node: &NodeRef, depth: usize) {
        // TODO: 実装
        // ツリーを整形して出力
    }
}

fn main() {
    let root = TreeNode::new(1);
    let child1 = TreeNode::new(2);
    let child2 = TreeNode::new(3);
    let grandchild = TreeNode::new(4);

    TreeNode::add_child(&root, child1.clone());
    TreeNode::add_child(&root, child2.clone());
    TreeNode::add_child(&child1, grandchild.clone());

    // 親の取得
    let parent = grandchild.borrow().get_parent();
    assert!(parent.is_some());
    assert_eq!(parent.unwrap().borrow().value, 2);

    // ツリーの出力
    TreeNode::print_tree(&root, 0);
    // 期待される出力:
    // 1
    //   2
    //     4
    //   3

    println!("Bonus 1 passed!");
}

評価基準:

  • newとadd_childの実装: 5点
  • get_parentの実装: 3点
  • print_treeの実装: 2点

---

ボーナス2: LRUキャッシュ（10点）

HashMapとLinkedListを使ってLRU（Least Recently Used）キャッシュを実装しなさい。

use std::collections::HashMap;

struct LRUCache {
    capacity: usize,
    cache: HashMap<i32, i32>,
    access_order: Vec<i32>,  // 簡略版
}

impl LRUCache {
    fn new(capacity: usize) -> Self {
        // TODO: 実装
    }

    fn get(&mut self, key: i32) -> Option<i32> {
        // TODO: 実装
        // キーが存在すれば値を返し、アクセス順を更新
    }

    fn put(&mut self, key: i32, value: i32) {
        // TODO: 実装
        // キャパシティを超えたら最も古いエントリを削除
    }
}

fn main() {
    let mut cache = LRUCache::new(2);

    cache.put(1, 1);
    cache.put(2, 2);
    assert_eq!(cache.get(1), Some(1));

    cache.put(3, 3);  // 2が削除される
    assert_eq!(cache.get(2), None);

    cache.put(4, 4);  // 1が削除される
    assert_eq!(cache.get(1), None);
    assert_eq!(cache.get(3), Some(3));
    assert_eq!(cache.get(4), Some(4));

    println!("Bonus 2 passed!");
}

評価基準:

  • 基本的なget/putの実装: 5点
  • LRUロジックの正しい実装: 5点

---

ボーナス3: 参照カウント付きスマートポインタの自作（10点）

簡易版のRcを実装しなさい。

use std::cell::RefCell;
use std::ops::Deref;

struct MyRc<T> {
    ptr: *mut RcBox<T>,
}

struct RcBox<T> {
    value: T,
    ref_count: RefCell<usize>,
}

impl<T> MyRc<T> {
    fn new(value: T) -> Self {
        // TODO: 実装
        // ヒープにRcBoxを割り当て
    }

    fn clone(&self) -> Self {
        // TODO: 実装
        // 参照カウントをインクリメント
    }

    fn strong_count(&self) -> usize {
        // TODO: 実装
    }
}

impl<T> Deref for MyRc<T> {
    type Target = T;

    fn deref(&self) -> &Self::Target {
        // TODO: 実装
    }
}

impl<T> Drop for MyRc<T> {
    fn drop(&mut self) {
        // TODO: 実装
        // 参照カウントをデクリメント
        // カウントが0になったらメモリ解放
    }
}

fn main() {
    let a = MyRc::new(5);
    assert_eq!(a.strong_count(), 1);

    let b = a.clone();
    assert_eq!(a.strong_count(), 2);

    {
        let c = a.clone();
        assert_eq!(a.strong_count(), 3);
    }

    assert_eq!(a.strong_count(), 2);
    assert_eq!(*a, 5);

    println!("Bonus 3 passed!");
}

評価基準:

  • 基本的な実装: 5点
  • Drop実装（メモリリーク防止）: 5点

    • 注意: unsafeコードが必要です。

    ---

    評価基準

    マンダトリー部分（80点）

    項目 配点 評価ポイント
    問題1：二分探索木 30点 Boxの正しい使用
    問題2：グラフ構造 30点 Rc/RefCellの理解
    問題3：スレッドセーフカウンタ 20点 Arc/Mutexの使用

    ボーナス部分（20点）

    項目 配点 評価ポイント
    ボーナス1：ツリー構造 10点 Weakの理解
    ボーナス2：LRUキャッシュ 10点 実用的なデータ構造
    ボーナス3：自作Rc 10点 内部実装の理解

    注: ボーナスは最大20点まで加算されます。

    ---

    提出方法

    ファイル構成

    rust-foundations-15/
├── src/
│   ├── problem1.rs
│   ├── problem2.rs
│   ├── problem3.rs
│   ├── bonus1.rs       # オプション
│   ├── bonus2.rs       # オプション
│   └── bonus3.rs       # オプション
├── Cargo.toml
└── README.md

    テスト

    cargo test --release

    提出期限

  • マンダトリー：第15章学習後、1週間以内
  • ボーナス：第17章修了時まで

    • ---

    ヒント

    問題1のヒント

    fn insert_recursive(node: &mut Link, value: i32) {
    match node {
        Some(ref mut n) => {
            if value < n.value {
                insert_recursive(&mut n.left, value);
            } else {
                insert_recursive(&mut n.right, value);
            }
        }
        None => {
            *node = Some(Box::new(Node {
                value,
                left: None,
                right: None,
            }));
        }
    }
}

    問題2のヒント

    // エッジの追加
let from_node = &self.nodes[from];
let to_node = &self.nodes[to];

from_node.borrow_mut().neighbors.push(Rc::clone(to_node));
to_node.borrow_mut().neighbors.push(Rc::clone(from_node));

    問題3のヒント

    fn increment(&self) {
    let mut count = self.count.lock().unwrap();
    *count += 1;
}

    ---

    学習の確認

    この課題を通じて、以下を理解できたか確認してください：

  • [ ] Boxの使い方とユースケース
  • [ ] Rcによる複数所有権
  • [ ] RefCellによる内部可変性
  • [ ] Arcによるスレッドセーフな共有
  • [ ] Weakによる循環参照の解決
  • [ ] Rc>パターン
  • [ ] Arc>パターン

次の章では、並行処理について学びます。スレッド、Send/Syncトレイト、データ競合の防止方法を理解します。

Previous
第15章: イテレータ
Next
第16章: モジュールシステム