我有一个基本的 LinkedList 实现，我想在其中迭代我的节点，并将这些节点添加到 HashSet。但是，我无法做到这一点，因为我的节点被包裹在一个 中Rc<RefCell<Node<T>>>，并且我在std::hash::Hash为我的std::cell::Ref<'_, Node<T>>类型实现特征时遇到了麻烦。
我怎样才能实现Hash这个例子的特征？还是我错过了什么？
这是一个失败的测试用例的示例，它尝试将一些节点添加到 a HashSet：
这是 Rust 操场上的源代码： https ://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=d79329dcb70ba54ff803dbcd93bd47d0
这是来源：
use std::cell::{RefCell, Ref};
use std::fmt;
use std::fmt::Display;
use std::ptr;
use std::rc::Rc;
use std::hash::{Hash, Hasher};
use std::collections::HashSet;
pub type NodeRef<T> = Rc<RefCell<Node<T>>>;
#[derive(Debug)]
pub struct LinkedList<T> {
pub head: Option<NodeRef<T>>,
}
// #[derive(Hash)]
pub struct Node<T> {
pub data: T,
pub next: Option<NodeRef<T>>,
}
impl<T: fmt::Debug> fmt::Debug for Node<T> {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
write!(f, "Node {{ data: {:?}, next: {:?} }}", self.data, self.next)
}
}
impl<T> LinkedList<T>
where
T: std::cmp::Eq
+ std::hash::Hash
+ std::clone::Clone
+ std::cmp::PartialOrd
+ std::cmp::PartialOrd
+ std::fmt::Debug,
{
pub fn new() -> Self {
Self { head: None }
}
pub fn append(&mut self, new_value: T) {
if let Some(tail) = self.tail() {
tail.borrow_mut().next = Some(Rc::new(RefCell::new(Node {
data: new_value,
next: None,
})));
} else {
self.head = Some(Rc::new(RefCell::new(Node {
data: new_value,
next: None,
})));
}
}
pub fn tail(&self) -> Option<NodeRef<T>> {
for node in self.iter() {
if let None = node.clone().borrow().next {
return Some(node);
}
}
None
}
pub fn iter(&self) -> Iter<T> {
Iter {
next: self.head.clone(),
}
}
}
#[derive(Debug)]
pub struct Iter<T> {
next: Option<NodeRef<T>>,
}
impl<'a, T> Iterator for Iter<T> {
type Item = NodeRef<T>;
fn next(&mut self) -> Option<Self::Item> {
if let Some(next) = self.next.clone() {
// Set the new self.next:
if let Some(new_next) = next.borrow().next.clone() {
self.next = Some(new_next);
} else {
self.next = None;
}
return Some(next);
} else {
None
}
}
}
impl<T: Display> Display for LinkedList<T> {
fn fmt(&self, w: &mut std::fmt::Formatter) -> std::result::Result<(), std::fmt::Error> {
write!(w, "[")?;
let mut node = self.head.clone();
while let Some(n) = node {
write!(w, "{}", n.borrow().data)?;
node = n.borrow().next.clone();
if node.is_some() {
write!(w, ", ")?;
}
}
write!(w, "]")
}
}
impl<T: PartialEq> PartialEq for Node<T> {
fn eq(&self, other: &Self) -> bool {
if ptr::eq(self, other) {
// For loop detection - if the nodes share the same
// reference, they are equal.
return true;
}
self.data == other.data && self.next == other.next
}
fn ne(&self, other: &Self) -> bool {
if !ptr::eq(self, other) {
return true;
}
self.data != other.data && self.next == other.next
}
}
// By implementing Eq, we are making the promise that our
// implementation of PartialEq is reflexive.
impl<T: Eq> Eq for Node<T> {
}
impl<T: Hash> std::hash::Hash for Node<T> {
fn hash<H>(&self, state: &mut H)
where H: std::marker::Sized + Hasher
{
self.data.hash(state);
if let Some(next) = self.next.clone() {
next.borrow().hash(state);
}
}
}
// // TODO: HELP!!!
// // Trying to implement Hash trait for Ref<'_, Node<T>>:
// impl<Node: Hash> std::hash::Hash for Ref<'_, Node> {
// fn hash<H: Hasher>(&self, state: &mut H) {
// self.data.hash(state);
// if let Some(next) = self.next.clone() {
// next.borrow().hash(state);
// }
// }
// }
impl<T: PartialEq> PartialEq for LinkedList<T> {
fn eq(&self, other: &Self) -> bool {
self.head == other.head
}
fn ne(&self, other: &Self) -> bool {
self.head != other.head
}
}
impl<T: Eq + std::fmt::Debug> Eq for LinkedList<T> {}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn eq() {
let mut list = LinkedList::new();
list.append(1);
list.append(2);
list.append(3);
let mut list2 = LinkedList::new();
list2.append(1);
list2.append(2);
list2.append(3);
assert_eq!(list, list2);
list2 = LinkedList::new();
list2.append(3);
assert_ne!(list, list2);
list = LinkedList::new();
list.append(3);
assert_eq!(list, list2);
}
#[test]
fn append() {
let mut list = LinkedList::new();
list.append(1);
list.append(2);
list.append(3);
let mut list2 = LinkedList::new();
list2.append(1);
list2.append(2);
list2.append(3);
assert_eq!(list, list2);
list2.append(1);
assert_ne!(list, list2);
list.append(1);
assert_eq!(list, list2);
}
// TODO: fix this test case!
#[test]
fn hashset_iter_nodes() {
let mut list = LinkedList::new();
list.append(1);
list.append(2);
list.append(3);
// the trait bound `std::cell::Ref<'_, Node<{integer}>>:
// std::hash::Hash` is not satisfied (the trait `std::hash::Hash` is
// not implemented for `std::cell::Ref<'_, Node<{integer}>>`)
// [E0277]
// the trait bound `std::cell::Ref<'_, Node<{integer}>>:
// std::cmp::Eq` is not satisfied (the trait `std::cmp::Eq` is
// not implemented for `std::cell::Ref<'_, Node<{integer}>>`)
// [E0277]
let mut set = HashSet::new();
// iterate over nodes, adding each node to our hashset:
for node in list.iter() {
println!("iterating over node: {:?}", node);
set.insert(&node.borrow());
}
assert_eq!(set.len(), 3);
}
}