rust - How to implement HashMap with two keys? -
hashmap
implements get
, insert
methods take single immutable borrow , single move of value respectively.
i want trait takes 2 keys instead of one. uses map inside, it's detail of implementation.
pub struct table<a: eq + hash, b: eq + hash> { map: hashmap<(a, b), f64>, } impl<a: eq + hash, b: eq + hash> memory<a, b> table<a, b> { fn get(&self, a: &a, b: &b) -> f64 { let key: &(a, b) = ??; *self.map.get(key).unwrap() } fn set(&mut self, a: a, b: b, v: f64) { self.map.insert((a, b), v); } }
this possible. signature of get
is
fn get<q: ?sized>(&self, k: &q) -> option<&v> k: borrow<q>, q: hash + eq,
the problem here implement &q
type such (1) (a, b): borrow<q>
, , (2) q
implements hash + eq
.
to satisfy condition (1), need think of how write
fn borrow(self: &(a, b)) -> &q
the trick &q
does not need simple pointer, can trait object! idea create trait q
, have 2 implementations:
impl q (a, b) impl q (&a, &b)
so borrow
implementation return self
, meanwhile construct &q
trait object 2 elements separately.
the full implementation this:
use std::collections::hashmap; use std::hash::{hash, hasher}; use std::borrow::borrow; // see explanation (1). #[derive(partialeq, eq, hash)] struct pair<a, b>(a, b); #[derive(partialeq, eq, hash)] struct borrowedpair<'a, 'b, a: 'a, b: 'b>(&'a a, &'b b); // see explanation (2). trait keypair<a, b> { /// obtains first element of pair. fn a(&self) -> &a; /// obtains second element of pair. fn b(&self) -> &b; /// checks if pair equal pair elementwise. fn eq_pair(&self, a: &a, b: &b) -> bool; /// computes hash of pair. fn erased_hash(&self, state: erasedhasher); } // see explanation (3). impl<'a, a, b> borrow<keypair<a, b> + 'a> pair<a, b> a: eq + hash + 'a, b: eq + hash + 'a, { fn borrow(&self) -> &(keypair<a, b> + 'a) { self } } // see explanation (4). impl<'a, a: hash, b: hash> hash (keypair<a, b> + 'a) { fn hash<h: hasher>(&self, state: &mut h) { self.erased_hash(erasedhasher(state)); } } impl<'a, a: eq, b: eq> partialeq (keypair<a, b> + 'a) { fn eq(&self, other: &self) -> bool { self.eq_pair(other.a(), other.b()) } } impl<'a, a: eq, b: eq> eq (keypair<a, b> + 'a) {} pub struct table<a: eq + hash, b: eq + hash> { map: hashmap<pair<a, b>, f64>, } impl<a: eq + hash, b: eq + hash> table<a, b> { fn new() -> self { table { map: hashmap::new() } } fn get(&self, a: &a, b: &b) -> f64 { *self.map.get(&borrowedpair(a, b) &keypair<a, b>).unwrap() } fn set(&mut self, a: a, b: b, v: f64) { self.map.insert(pair(a, b), v); } } // boring stuff below. impl<a, b> keypair<a, b> pair<a, b> a: eq + hash, b: eq + hash, { fn a(&self) -> &a { &self.0 } fn b(&self) -> &b { &self.1 } fn eq_pair(&self, a: &a, b: &b) -> bool { &self.0 == && &self.1 == b } fn erased_hash(&self, mut state: erasedhasher) { self.0.hash(&mut state); self.1.hash(&mut state); } } impl<'a, 'b, a, b> keypair<a, b> borrowedpair<'a, 'b, a, b> a: eq + hash + 'a, b: eq + hash + 'a, { fn a(&self) -> &a { self.0 } fn b(&self) -> &b { self.1 } fn eq_pair(&self, a: &a, b: &b) -> bool { self.0 == && self.1 == b } fn erased_hash(&self, mut state: erasedhasher) { self.0.hash(&mut state); self.1.hash(&mut state); } } // needed because `&mut hasher` not `hasher`, // , `hash<h: hasher>(&self, &mut h)` means need sized `hasher`. struct erasedhasher<'a>(&'a mut hasher); impl<'a> hasher erasedhasher<'a> { fn finish(&self) -> u64 { self.0.finish() } fn write(&mut self, bytes: &[u8]) { self.0.write(bytes) } fn write_u8(&mut self, i: u8) { self.0.write_u8(i) } fn write_u16(&mut self, i: u16) { self.0.write_u16(i) } fn write_u32(&mut self, i: u32) { self.0.write_u32(i) } fn write_u64(&mut self, i: u64) { self.0.write_u64(i) } fn write_usize(&mut self, i: usize) { self.0.write_usize(i) } fn write_i8(&mut self, i: i8) { self.0.write_i8(i) } fn write_i16(&mut self, i: i16) { self.0.write_i16(i) } fn write_i32(&mut self, i: i32) { self.0.write_i32(i) } fn write_i64(&mut self, i: i64) { self.0.write_i64(i) } fn write_isize(&mut self, i: isize) { self.0.write_isize(i) } }
explanation:
we introduced
pair
,borrowedpair
types. can't use(a, b)
directly due the orphan rule e0210. fine since map implementation detail.the
keypair
trait takes role ofq
mentioned above. we'd needimpl eq + hash keypair
,eq
,hash
both not object safe. addeda()
,b()
,eq_pair()
,erased_hash()
methods implementing them manually.now implement
borrow
traitpair<a, b>
keypair + 'a
. note'a
— subtle bit needed maketable::get
work. arbitrary'a
allows say,pair<a, b>
can borrowed trait object any lifetime. if don't specify'a
, unsized trait object default'static
, meaningborrow
trait can applied when implementationborrowedpair
outlives'static
, not case.finally implement
eq
,hash
. above, implementkeypair + 'a
instead ofkeypair
(which meanskeypair + 'static
in context).
using trait objects incur indirection cost when computing hash , checking equality in get()
. cost can eliminated if optimizer able devirtualize that, whether llvm unknown.
an alternative store map hashmap<(cow<a>, cow<b>), f64>
. using requires less "clever code", there memory cost store owned/borrowed flag, runtime cost in both get()
, set()
.
so, unfortunately, unless fork standard hashmap , adds method entry via hash + eq
alone, there no guaranteed-zero-cost solution.
Comments
Post a Comment