如何消除委托给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()
    }
}

我正在尝试使用避免装箱迭代器使用答案中描述的技巧。

由于一个错误，此代码无法编译：

   |
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是一个边缘权重。客户端将负责确保他们传递的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()
    }
}

(游乐场)

其原因可以归结为特征Graph和struct NodeIterator上的签名。当美联储Keys<'a, N, ()>时，NodeIterator::new返回NodeIterator<'a, N>。但是，对于Graph的实现，您希望它返回Nodes类型的东西，即NodeIterator<'a, &'a N>类型。注意额外的&'a。此外，它需要返回一个迭代器，其项具有&'a N类型。删除一些&'a使一切都保持一致。

另一个解决方案是添加一个额外的&'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有一组不同的方法，这些方法可能对您更有用，也可能不会对您更有用。