借用チェッカを念頭に置いてデータ構造を設計しよう
しかし、データ構造の内部で 木構造 よりも複雑な グラフ構造 を形成している場合、単純な単一の所有者モデルは不可能 e.g. 到着順 + 辞書順にゲストを効率的に検索 + 登録するシステム
効率的にする（線形探索 となるのを避ける）ために 2 つのデータ構造が必要になるが、一方しか所有できない 回避策①: （データが イミュータブル かつサイズが小さい場合）クローンする code:rs
/// ゲストの登録を管理する
pub struct GuestRegister {
by_arrival: Vec<Guest>, // 到着順に並べたデータ
by_name: std::collections::BTreeMap<String, Guest>, // 辞書順に並べたデータ
}
impl GuestRegister {
/// 実際の登録処理を行う
fn register(&mut self, guest: Guest) {
self.by_arrival.push(guest.clone());
self.by_name.insert(guest.name.clone(), guest);
}
pub fn named(&self, name: &str) -> Option<&Guest> {
self.by_name.get(name)
}
pub fn nth(&self, idx: usize) -> Option<&Guest> {
self.by_arrival.get(idx)
}
}
① の問題点: データを更新する際に、両方のデータ構造から見つけて 整合するように更新する 必要がある
Vec<Guest> を所有者とし、名前の検索にはベクタへのインデックスを用いる
code:rs
pub struct GuestRegister {
by_arrival: Vec<Guest>,
by_name: std::collections::BTreeMap<String, usize>,
}
impl GuestRegister {
pub fn register(&mut self, guest: Guest) {
self.by_name.insert(guest.name.clone(), self.by_arrival.len());
self.by_arrival.push(guest)
}
pub fn named(&self, name: &str) -> Option<&Guest> {
let idx = *self.by_name.get(name)?;
self.nth(idx)
}
pub fn named_mut(&mut self, name: &str) -> Option<&mut Guest> {
let idx = *self.by_name.get(name)?;
self.nth_mut(idx)
}
pub fn nth(&self, idx: usize) -> Option<&Guest> {
self.by_arrival.get(idx)
}
pub fn nth_mut(&mut self, idx: usize) -> Option<&mut Guest> {
self.by_arrival.get_mut(idx)
}
}
これにより by_arrival と by_name の両方が同じ値を指すため、可変参照 を用いて保持している Guest のフィールドを変更できる code:rs
let new_address = "123 Bigger House St";
ledger.named_mut("Bob").unwrap().address = new_address.to_string();
assert_eq!(ledger.named("Bob").unwrap().address, new_address);
② の問題点: データを削除する際に、以下のような不注意で整合しなくなる危険性がある
code:rs
pub fn deregister(&mut self, idx: usize) -> Result<(), Error> {
if idx >= self.by_arrival.len() {
return Err(Error::new("out of bounds"));
}
self.by_arrival.remove(idx);
// self.by_name.remove(idx); を忘れた
Ok(())
}
code:_
Register starts as: {
by_name: {"Alice": 0, "Bob": 1, "Charlie": 2}
}
Register after deregister(0): {
// Alice だけ削除されている
by_name: {"Alice": 0, "Bob": 1, "Charlie": 2}
}
// データの不整合も起きている
Alice is Some(Guest { name: "Bob", address: "234 Bobton" })
Bob is Some(Guest { name: "Charlie", address: "345 Charlieland" })
Charlie is None
また、deregister を修正したとしても、呼び出し側のコードでインデックス値を保持して、nth を呼び出すと、不正なデータを取得する可能性がある
code:rs
register.register(alice);
register.register(bob);
register.register(charlie);
let idx = 1;
let guest_before = register.nth(idx); // Bob を取得
register.deregister(0); // Alice を削除
let guest_after = register.nth(idx); // ここでは Charlie を取得してしまう
② の解決策: この問題の中核は 2 つのデータ（by_arrival と by_name）が整合しなければならない点 にある
これは Rc と RefCell を組み合わせる（スマートポインタ）を用いることで回避できる code:rs
pub struct GuestRegister {
by_arrival: Vec<Rc<RefCell<Guest>>>,
by_name: std::collections::BTreeMap<String, Rc<RefCell<Guest>>>,
}
impl GuestRegister {
pub fn register(&mut self, guest: Guest) {
let name = guest.name.clone();
let guest = Rc::new(RefCell::new(guest));
self.by_arrival.push(guest.clone());
self.by_name.insert(name, guest);
}
pub fn deregister(&mut self, idx: usize) -> Result<(), Error> {
if idx >= self.by_arrival.len() {
return Err(Error::new("out of bounds"));
}
self.by_arrival.remove(idx);
// また self.by_name.remove(idx); を忘れた
Ok(())
}
}
code:_
Register starts as: {
by_name: [("Alice", {n: 'Alice', ...}), ("Bob", {n: 'Bob', ...}),
("Charlie", {n: 'Charlie', ...})]
}
Register after deregister(0): {
// Alice はまだ残っているが…
by_name: [("Alice", {n: 'Alice', ...}), ("Bob", {n: 'Bob', ...}),
("Charlie", {n: 'Charlie', ...})]
}
// データの不整合は解消されている
Alice is Some(RefCell { value: Guest { name: "Alice",
address: "123 Aliceville" } })
Bob is Some(RefCell { value: Guest { name: "Bob",
address: "234 Bobton" } })
Charlie is Some(RefCell { value: Guest { name: "Charlie",
address: "345 Charlieland" } })