时间戳

首页 > 解决方案 > Is there any way to simulate Generic Associated Types / Associated Type Constructors in Rust?

generics - Is there any way to simulate Generic Associated Types / Associated Type Constructors in Rust?

问题描述

I'm making a graph processing module in Rust. The core of the module models the idea of having multiple containers which hold the data in the graph. For example, I may have a graph whose inner structure is an HashMap or maybe AdjacencyMatrix etc.

These containers must implement a trait:

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

I can't just return a trait in my trait definition. I know I must use trait object, but I don't want to Box it. I would like to make the container provide its own NodeIter struct. However, I would be stuck with the same problem explained in Associated type constructors, part 1: basic concepts and introduction. The post explains about associated type constructors (ATC) which do not exist in Rust now. My GraphData resembles the generic Collection described.

Is there any workaround I could use to "simulate" ATC or any pattern specific to Rust I could use for this situation?

I don't want to depend on dynamic dispatch and resort to using Box or the dyn keyword.

I thought to define a struct NodeIter for each type of graph container I created in my module and add "nodes" inside the implementation of the container itself. However, I find this to be poor code reuse.

标签： genericsrustassociated-types

解决方案

您描述的问题已通过普通关联类型解决。它不需要泛型关联类型，也就是关联类型构造函数。这已经在稳定的 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>or Nodes<'a>），所以它不是通用的。

如果您希望该Nodes类型能够持有对Self（以避免clone()）的引用，则 Nodes需要具有生命周期参数的泛型。不过，这不是避免 . 的唯一方法clone()：您可以使用Rc.

推荐阅读