我正在尝试在Rust中建立一个小型图形库。所有图形都将实现Graph
特征,并且HashGraph
是一个具体示例。 HashGraph
本身将是HashMap
周围的轻量级包装。
特别是,我希望HashGraph
方法nodes
返回将next
委派给从HashGraph#keys
获得的基础迭代器的迭代器。
这是我的代码:
use std::collections::HashMap;
pub trait Graph<'a, N: 'a> {
type Nodes: Iterator<Item=&'a N>;
fn nodes(&'a self) -> Self::Nodes;
}
struct HashGraph<N> {
map: HashMap<N, ()>
}
impl<N> HashGraph<N> {
pub fn new(map: HashMap<N, ()>) -> Self {
HashGraph { map }
}
}
impl<'a, N: 'a> Graph<'a, &'a N> for HashGraph<N> {
type Nodes = NodeIterator<'a, &'a N>;
fn nodes(&'a self) -> Self::Nodes {
NodeIterator::new(self.map.keys())
}
}
struct NodeIterator<'a, N> {
nodes: std::collections::hash_map::Keys<'a, N, ()>
}
impl<'a, N> NodeIterator<'a, N> {
pub fn new(nodes: std::collections::hash_map::Keys<'a, N, ()>) -> Self {
NodeIterator { nodes: nodes }
}
}
impl<'a, N> Iterator for NodeIterator<'a, N> {
type Item = &'a N;
fn next(&mut self) -> Option<Self::Item> {
self.nodes.next()
}
}
我正在尝试使用avoid Boxing iterators进行the technique described in the answers here。
此代码由于单个错误而无法编译:
|
23 | NodeIterator::new(self.map.keys())
| ^^^^^^^^^^^^^^^ expected &N, found type parameter
|
= note: expected type `std::collections::hash_map::Keys<'_, &N, _>`
found type `std::collections::hash_map::Keys<'_, N, _>`
HashMap
键迭代器似乎没有返回项目的预期形式,但是我真的不清楚如何解决此错误。我对NodeIterator
的目标是继续传递HashMap
迭代器为next
返回的任何内容。
HashGraph
应该拥有其键(HashMap
中的键)。创建后,HashGraph
将为只读。
HashMap<N, ()>
的使用主要是为了简化示例代码。最终将使用HashMap<N, HashMap<N, E>>
,其中E
是边缘权重。客户会注意通过例如引用计数来确保拥有适当的所有权。
如何修改示例以消除错误并成功编译?
要编译代码,只需要删除几个额外的&
。
use std::collections::HashMap;
pub trait Graph<'a, N: 'a> {
type Nodes: Iterator<Item = &'a N>;
fn nodes(&'a self) -> Self::Nodes;
}
struct HashGraph<N> {
map: HashMap<N, ()>,
}
impl<N> HashGraph<N> {
pub fn new(map: HashMap<N, ()>) -> Self {
HashGraph { map }
}
}
impl<'a, N: 'a> Graph<'a, N> for HashGraph<N> {
// ^^^ this one
type Nodes = NodeIterator<'a, N>;
// ^^^ and this one
fn nodes(&'a self) -> Self::Nodes {
NodeIterator::new(self.map.keys())
}
}
struct NodeIterator<'a, N> {
nodes: std::collections::hash_map::Keys<'a, N, ()>,
}
impl<'a, N> NodeIterator<'a, N> {
pub fn new(nodes: std::collections::hash_map::Keys<'a, N, ()>) -> Self {
NodeIterator { nodes }
}
}
impl<'a, N> Iterator for NodeIterator<'a, N> {
type Item = &'a N;
fn next(&mut self) -> Option<Self::Item> {
self.nodes.next()
}
}
其原因归结为特征Graph
和结构NodeIterator
上的签名。当送入Keys<'a, N, ()>
时,NodeIterator::new
返回NodeIterator<'a, N>
。但是,对于Graph
的实现,您希望它返回Nodes
类型的内容,即NodeIterator<'a, &'a N>
类型。注意额外的&'a
。此外,它需要返回一个项目类型为&'a N
的迭代器。删除某些&'a
使所有内容保持一致。
另一个解决方案是添加extra &'a
。
impl<'a, N: 'a> Graph<'a, &'a N> for HashGraph<&'a N> {
// ^^^ right here
type Nodes = NodeIterator<'a, &'a N>;
fn nodes(&'a self) -> Self::Nodes {
NodeIterator::new(self.map.keys())
}
}
这意味着您一直使用&'a N
而不是N
本身。
这里的关键是一致性,但是您还需要提前考虑如何使用这些类型和特征。您是否要HashGraph
仅引用其键或拥有它们?如果它们是引用,实际上是它们的所有者?如果您使用拥有的钥匙,是否需要将它们移动很多?
最后一件事。您正在使用HashMap<N, ()>
,但根据您要尝试执行的操作,HashSet<N>
可能更惯用。两者在幕后完全相同,但是HashSet
具有一组不同的方法,这些方法可能对您或更有用。