Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationEventAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
7
Help us understand the problem. What are the problem?

More than 3 years have passed since last update.

@maueki

Rustと継承に関するメモ

はじめに

継承といっても#[derive(..)]のことではなくC++的な継承が欲しい場面でRustならどうするかという話。結論めいたものはない。アドバイスいただけると嬉しい。

発端

AtCoderの勉強にとRustでダイクストラ法の実装をおこなっていた。
いろいろ省略しているが以下の様なトレイトを作った。

mod dijkstra {

    #[derive(Copy, Clone, Eq, PartialEq)]
    pub struct State<T>
    {
        pub cost: usize,
        pub pos: T
    }

    pub trait Context<T>
    {
        fn cost(&self, pos: T) -> usize;
        fn update_cost(&mut self, s: &State<T>);
        fn neighbours(&self, s: &State<T>) -> Vec<State<T>>;

        fn run(&mut self, start: State<T>, end: T) -> Option<usize>
          where T: Copy+Ord {
            // 省略
        }
    }
}

あとは各問題に合わせてContextトレイトを実装すればよい(はず)。
ところで(全てではないが)多くの場合costはHashMapで管理すれば良さそうだ。
しかしトレイトにHashMapをメンバとして持たすことはできない、さてどうしようという話。

C++での実装

このときC++であればContextを継承してメンバと実装を持たせてしまうのが手っ取り早い。

// 疑似コード
class ContextWithHashMap : public Context {
    HashMap cost_table;

    size_t cost(T pos) {
        return cost_table[pos];
    }

    void update_cost(State<T>& s) {
        cost_table[s.pos] = s.cost;
    }
};

ユーザーはContextWithHashMapを継承してneighbours()の実装だけおこなえばよい。

Rustでの実装その1(差分をトレイトにする)

NeighbourトレイトとDefaultContextを新たに作る。
ユーザーはNeighbourトレイトを実装して、それを引数にDefaultContextを作ることになる。

    pub trait Neighbours<T>
    {
        fn neighbours(&self, s: &State<T>) -> Vec<State<T>>;
    }

    pub struct DefaultContext<'a, T, U>
    where U: 'a
    {
        pub cost_table: HashMap<T, usize>,
        pub data: &'a U
    }

    impl<'a, T, U> DefaultContext<'a, T, U>
    where T: Eq+Hash, U: Neighbours<T>
    {
        pub fn new(data: &'a U) -> Self {
            DefaultContext{ cost_table: HashMap::new(), data: data }
        }
    }

    impl<'a, T, U> Context<T> for DefaultContext<'a, T, U>
    where T: Copy+Clone+Eq+Hash, U: Neighbours<T>
    {
        fn cost(&self, pos: T) -> usize {
            self.cost_table.get(&pos).map_or(::std::usize::MAX, |c| *c)
        }

        fn update_cost(&mut self, s: &State<T>) {
            self.cost_table.insert(s.pos, s.cost);
        }

        fn neighbours(&self, s: &State<T>) -> Vec<State<T>> {
            self.data.neighbours(s)
        }
    }

むりやりC++っぽい実装を実現しようとするとこうなるだろうか。
DefaultContext::new()にNeighbourを渡すというのは回りくどいし、モジュール側のコードがC++より多いのもどうもいただけない。

Rustでの実装その2(ラムダ渡し)

DefaultContext作るところはその1と同じだが、neighbour()をラムダとして渡すようにしている。

    pub struct DefaultContext<'a, T: 'a>
    {
        pub table: HashMap<T, usize>,
        pub f: &'a Fn(&State<T>) -> Vec<State<T>>
    }


    impl<'a, T> Context<T> for DefaultContext<'a, T>
    where T: Copy+Clone+Eq+Hash
    {
        fn cost(&self, pos: T) -> usize {
            self.table.get(&pos).map_or(::std::usize::MAX, |c| *c)
        }

        fn update_cost(&mut self, s: &State<T>) {
            self.table.insert(s.pos, s.cost);
        }

        fn neighbours(&self, s: &State<T>) -> Vec<State<T>> {
            (self.f)(s)
        }
    }

    #[allow(dead_code)]
    pub fn create_default_context<'a, T, F>(f: &'a F) -> DefaultContext<'a, T>
    where T: Eq + Hash, F: Fn(&State<T>) -> Vec<State<T>> {
        DefaultContext{ table: HashMap::new(), f: f}
    }

その1よりはスマートな感じがするが、ユーザーが実装するメソッドが増えるとこの手は使えなさそう。

Rustでの実装その3(マクロ使用)

マクロを使ってみる

    macro_rules! cost_table {
        ($cost_table:ident, $t:ty) => (
            fn cost(&self, pos: $t) -> usize {
                self.$cost_table.get(&pos).map_or(::std::usize::MAX, |c| *c)
            }

            fn update_cost(&mut self, s: &State<$t>) {
                self.$cost_table.insert(s.pos, s.cost);
            }
        )
    }

ユーザーはこういう感じで使う

struct ContextImpl {
    cost_table: HashMap<(usize, usize), usize>
}

impl Context<(usize, usize)> for ContextImpl {
    cost_table!(cost_table, (usize, usize));

    fn neighbours(&self, s: &State<(usize, usize)>) -> Vec<State<(usize, usize)>> {
        // 省略
    }
}

モジュール側の実装は簡単だが、ユーザー側でHashMapを持ったり、マクロにStateの型パラメータを指定する必要があるのがかなりツライ。

まとめ

思いつく実装を3つほど挙げて見たもののどれもピンとこない。何かもっと良い実装はないだろうか。

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
7
Help us understand the problem. What are the problem?