有没有办法模拟Rust中的通用关联类型/关联类型构造函数？

Question

我正在Rust中制作一个图形处理模块.该模块的核心模型是拥有多个容器的想法,这些容器将数据保存在图表中.例如,我可能有一个内部结构是HashMap或可能AdjacencyMatrix等的图形.

这些容器必须实现一个特性:

trait GraphData<V> {
    fn has_edge(&self, v: &V, u: &V) -> bool;
    fn nodes(&self) -> Iterator<V>; // Here's the problem...
}

我不能只在我的特质定义中返回一个特征.我知道我必须使用特质对象,但我不想这样做Box.我想让容器提供自己的NodeIter结构.但是,我会遇到在Associated类型构造函数中解释的相同问题,第1部分:基本概念和介绍.该帖子解释了现在Rust中不存在的相关类型构造函数(ATC).我GraphData类似于Collection描述的通用.

是否有任何解决方法我可以用来"模拟"ATC或任何特定于Rust的模式我可以用于这种情况？

我不想依赖动态调度并使用Box或dyn关键字.

我想为NodeIter我在模块中创建的每种类型的图形容器定义一个结构,并在容器本身的实现中添加"节点".但是,我发现这是糟糕的代码重用.

Answer 1

您描述的问题通过普通关联类型解决.它不需要通用的关联类型,也就是相关的类型构造函数.这已经适用于稳定的Rust.

trait GraphData<V> {
    type Nodes: Iterator<Item = V>;
    fn has_edge(&self, v: &V, u: &V) -> bool;
    fn nodes(&self) -> Self::Nodes;
}

struct Graph<V> {
    nodes: Vec<V>,
    edges: Vec<(V, V)>,
}

impl<V: Clone + Eq> GraphData<V> for Graph<V> {
    type Nodes = vec::IntoIter<V>;
    fn has_edge(&self, u: &V, v: &V) -> bool {
        self.edges.iter().any(|(u1, v1)| u == u1 && v == v1)
    }
    fn nodes(&self) -> Self::Nodes {
        self.nodes.clone().into_iter()
    }
}

Nodes没有类型或生命周期参数(它不是Nodes<T>或Nodes<'a>),所以它不是通用的.

如果您希望Nodes类型能够保持对Self(以避免clone())的引用,则 Nodes需要使用life参数.但这并不是避免这种情况的唯一方法clone():你可以使用Rc.