rust - 如何消除委托(delegate)给HashMap迭代器时的 "expected &T, found type parameter"错误？

Question

我正在尝试用 Rust 构建一个小型图形库。 Graph特征将由所有图实现，并且HashGraph是一个具体的例子。 HashGraph本身将是 HashMap 的轻量级包装器.

特别是，我想要 HashGraph方法 nodes返回一个委托(delegate) 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应该拥有它的 key (在它的 HashMap 中的)。创建后，HashGraph将是只读的。

HashMap<N, ()>的使用主要是为了简化示例代码。它最终将使用 HashMap<N, HashMap<N, E>>其中 E是边权重。客户会注意确保对 HashMap 的适当所有权。例如，它们通过引用计数。

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

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 s 使一切保持一致。

另一个解决方案是添加一个额外的 &'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只引用其 key 或拥有它们？如果它们是引用，那么实际上拥有它们的是什么？如果您使用自有 key ，是否需要经常移动它们？

最后一件事。您正在使用 HashMap<N, ()>但是，取决于你到底想做什么，HashSet<N>可能更惯用。两者在引擎盖下完全相同，但是HashSet有一组不同的方法，这些方法可能对您更有用，也可能没有。