2022/04/21
はじめに
ビルトインの hash table library を使わずに hash set を実装する問題．
Rust を使って，簡単な方法で解いてみる（この問題を解くためのベストの方法ではないのでご注意！！）．
コード全文
問題の条件では，keyが0 <= key <= 10^6となっていたので，「行けるだろ」ということで，フラグを格納する10^6+1の長さを持つブール配列を準備した．
main.rs
struct MyHashSet {
flags: Vec<bool>,
}
impl MyHashSet {
fn new() -> Self {
Self { flags: vec![false; 1000001] }
}
fn add(&mut self, key: i32) {
self.flags[key as usize] = true;
}
fn remove(&mut self, key: i32) {
self.flags[key as usize] = false;
}
fn contains(&self, key: i32) -> bool {
self.flags[key as usize]
}
}
解説
struct 準備
flagsのkey番目にはkeyが含まれているかどうかの状態をbool型で記録するような実装を行う．
struct MyHashSet {
flags: Vec<bool>,
}
コンストラクタ
MyHashSet::new()により，MyHashSetを初期化出来る．
初期化時は，長さ1000001のfalseを持つflagsを準備する．
impl MyHashSet {
fn new() -> Self {
Self { flags: vec![false; 1000001] }
}
add method
keyを追加するためのメソッド．
ミュータブルメソッドのため，&mut selfとし，key番目の値をtrueにする．
ここで，入力されるkeyの型はi32であり，直接Vecのキーとすることは出来ないため，key as usizeにより，型キャストを行い，要素にアクセスする．
fn add(&mut self, key: i32) {
self.flags[key as usize] = true;
}
remove method
keyを削除するためのメソッド．
key番目の値をtrueにする．
fn remove(&mut self, key: i32) {
self.flags[key as usize] = false;
}
contains method
要素が含まれるかを確認するメソッド．
例によって，型キャストを行って取得できる要素を戻り値とする．
fn contains(&self, key: i32) -> bool {
self.flags[key as usize]
}
}
おわりに
メンバ関数に関して，C++ではconstを付けることでイミュータブルに出来るのに対し，Rust ではmutを付けることでミュータブルにできるという点から，両者の違いが伝わってくる．