やってみる

アウトプットすべく己を導くためのブログ。その試行錯誤すらたれ流す。

📌 ？
トップ > Rust > Rust自習（連結リスト6）

Rust自習（連結リスト6）

Rust

　nth_ref()メソッド実装。ふつうに書けた。

成果物

nth_ref()メソッド

　指定した位置のノードが持つitemの不変参照を返す。

　std::iter::Iterator.nth()というメソッドがある。これは指定した位置の要素を返す。だが、所有権をムーブしてしまう。リストから削除されてしまう。そこで、所有権をムーブせず参照を返すようにしたのが今回のnth_ref()メソッドである。

コード

while版

    fn nth_ref(&self, index: usize) -> &T {
        let mut count = 0;
        let mut ptr = &self.head;
        while count < index {
            if ptr.is_none() { panic!("Out of index. index値が大きすぎます。index: {}", index); }
            ptr = &ptr.as_ref().unwrap().next;
            count += 1;
        }
        if ptr.is_none() { panic!("Out of index. index値が大きすぎます。index: {}", index); }
        else { &((*ptr).as_ref().unwrap().item) }
    }

　if文のところが重複しているのが気になる。でも、while count <= indexにしてしまうと指定位置の要素がNoneのときptr = &ptr.as_ref().unwrap().next;のところでパニックする。Noneはunwrap()できないから。

　かといって以下のようにすると無駄にif文の実行を増やしてしまう。

        while count <= index {
            if ptr.is_none() { panic!("Out of index. index値が大きすぎます。index: {}", index); }
            if count < index {
                ptr = &ptr.as_ref().unwrap().next;
                count += 1;
            }
        }

再帰版

　再帰を使って書くと以下。

    fn nth_ref(&self, index: usize) -> &T {
        fn get_idx_ptr<T>(ptr: &Option<Box<Node<T>>>, index: usize, count: usize) -> &Option<Box<Node<T>>> {
            if count < index {
                if ptr.is_some() { return get_idx_ptr(&ptr.as_ref().unwrap().next, index, count+1); }
                else { return ptr; }
            } else { return ptr; }
        }
        let ptr = get_idx_ptr(&self.head, index, 0);
        if ptr.is_none() { panic!("Out of index. index値が大きすぎます。index: {}", index); }
        else { &((*ptr).as_ref().unwrap().item) }
    }

　get_idx_ptrは指定したインデックスにある要素への不変参照を返す。ただし、もしインデックスが最後の要素より大きいインデックスなら、最後の要素への不変参照を返す。

　インデックスがどこであれ、指し示した値がNoneなら要素が存在しないことを意味する。よってOut of indexとしてパニックさせる。

　意味付けとしては再帰版コードのほうがいい。

if let

before

        let ptr = get_idx_ptr(&self.head, index, 0);
        if ptr.is_none() { panic!("Out of index. index値が大きすぎます。index: {}", index); }
        else { &((*ptr).as_ref().unwrap().item) }

after

        if let Some(ref _n) = get_idx_ptr(&self.head, index, 0) { return &(_n.item) }
        else { panic!("Out of index. index値が大きすぎます。index: {}", index); }

完成版

    /// 指定位置の参照を得る
    fn nth_ref(&self, index: usize) -> &T {
        fn get_ptr_from_idx<T>(ptr: &Option<Box<Node<T>>>, index: usize, count: usize) -> &Option<Box<Node<T>>> {
            if count < index {
                if ptr.is_some() { return get_ptr_from_idx(&ptr.as_ref().unwrap().next, index, count+1); }
                else { return ptr; }
            } else { return ptr; }
        }
        if let Some(ref _n) = get_ptr_from_idx(&self.head, index, 0) { return &(_n.item) }
        else { panic!("Out of index. index値が大きすぎます。index: {}", index); }
    }

　再帰関数の名前を変えた。あとはそのまま。

  1. 指定位置もしくは末尾ノードへの不変参照を返す
  2. 1が存在すればそのノードがもつitemへの不変参照を返す
  3. 1が存在しなければパニックする

　やっていることは簡単。でも、1行あたりの字数が多すぎて読むのが嫌になる。かといって1行あたりの字数を短くすれば、インデントが深化しすぎて嫌。悩ましいが、これまで通り、できるだけ1行にぶちこんだ。

テストコード

異常系

    #[test]
    #[should_panic(expected = "Out of index. index値が大きすぎます。index: 0")]
    fn LinkedList_nth_ref_out_of_index_0() {
        let mut list: LinkedList<i32> = LinkedList::new();
        list.nth_ref(0);
        assert_eq!(list.next(), None);
        let a = list.next();
        assert_eq!(list.next(), None);

        list.push(0);
    }
    #[test]
    #[should_panic(expected = "Out of index. index値が大きすぎます。index: 1")]
    fn LinkedList_nth_ref_out_of_index_1() {
        let mut list: LinkedList<i32> = LinkedList::new();
        list.push(0);
        list.nth_ref(1);
    }

正常系

    #[test]
    fn LinkedList_nth_ref_1() {
        let mut list: LinkedList<i32> = LinkedList::new();
        list.push(10);
        assert_eq!(*list.nth_ref(0), 10);
    }
    #[test]
    fn LinkedList_nth_ref_3() {
        let mut list: LinkedList<i32> = LinkedList::new();
        list.push(10);
        list.push(11);
        list.push(12);
        let expecteds = vec![10, 11, 12];
        for (i, expected) in expecteds.iter().enumerate() {
            assert_eq!(*(list.nth_ref(i)), *expected);
        }
        for (i, expected) in expecteds.iter().enumerate() {
            assert_eq!(*(list.nth_ref(i)), *expected);
        }
    }

　ポイントは最後のテスト。2回目のfor文にて同じ位置の要素を参照している。所有権がムーブされず、参照を返しているため、1度nth_refした要素でもリストに保存されたまま。何度でも参照できる。

残念ポイント

  • 不変参照であるため、代入はできない
  • count()のようにリスト内の要素数を知ることができない
    • もし最大値を超過したインデックスを指定したらpanic!する
  • 低パフォーマンス
    • 毎回indexの値+1回だけnextを辿る　なんという無駄。でもこれが連結リストであり線形リスト。

　実用性はない。

疑問

スライス？

　これってlist[0]みたいにして参照するのと同じ処理だと思う。[index]の演算子をオーバーライドするのって、どうやるんだろう？　そもそも、できるのか？

　スライスはスライス型という別の型っぽいし、その挙動を真似するにはどうすればいいんだ？

ベクター？

　もしや、私が書いている連結リストはVecの実装を再現しているだけなのか？　じつは連結リストのメソッドなど書く必要はなく、最初からVecを隠蔽して実装すべきものなのだろうか？

linked-list

　crate.ioのサイトをみるとすでに連結リストがあった。

　このコードをみれば勉強できるかも。

　というか、今更ながら気づいたが標準モジュールに存在するのか？

　だが、コードが見当たらない。以下のコードは正式なものなのだろうか？　それとも個人が書いたもの？

対象環境

$ uname -a
Linux raspberrypi 4.19.42-v7+ #1219 SMP Tue May 14 21:20:58 BST 2019 armv7l GNU/Linux

前回まで