委托给HashMap迭代器时如何消除“预期的＆T，找到类型参数”错误？

Question

我正在尝试在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是边缘权重。客户会注意通过例如引用计数来确保拥有适当的所有权。

如何修改示例以消除错误并成功编译？

Answer 1

要编译代码，只需要删除几个额外的&。

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()
    }
}

(playground)

其原因归结为特征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())
    }
}

(playground)

这意味着您一直使用&'a N而不是N本身。

这里的关键是一致性，但是您还需要提前考虑如何使用这些类型和特征。您是否要HashGraph仅引用其键或拥有它们？如果它们是引用，实际上是它们的所有者？如果您使用拥有的钥匙，是否需要将它们移动很多？

最后一件事。您正在使用HashMap<N, ()>，但根据您要尝试执行的操作，HashSet<N>可能更惯用。两者在幕后完全相同，但是HashSet具有一组不同的方法，这些方法可能对您或更有用。