有没有办法在 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...
}

我不能只 return 我的特质定义中的一个特质。我知道我必须使用特征对象，但我不想 Box 它。我想让容器提供自己的 NodeIter 结构。但是，我会遇到 Associated type constructors, part 1: basic concepts and introduction 中解释的相同问题。 post 解释了现在 Rust 中不存在的关联类型构造函数 (ATC)。我的 GraphData 类似于描述的通用 Collection。

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

我不想依赖动态调度并求助于使用 Box 或 dyn 关键字。

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

Answer 1

您描述的问题已通过 associated types. It does not require generic associated types、a.k.a 简单解决。关联的类型构造函数。这已经在稳定的 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 需要具有生命周期参数的通用性。不过，这不是避免 clone() 的唯一方法：您可以使用 Rc.

Answer 2

正如已经解释的那样：如果您可以忍受克隆包含顶点的 Vec，那么您可能不需要 GAT。但是，这可能不是您想要的。相反，您通常希望有一个引用原始数据的迭代器。

要实现这一点，您实际上最好使用 GAT。但由于它们还不是语言的一部分，让我们来解决您的主要问题：有什么方法可以模拟通用关联类型吗？ 实际上我写了一篇非常广泛的博客 post 关于本主题：“Solving the Generalized Streaming Iterator Problem without GATs”。

文章总结：

最简单的方法是将迭代器装箱并 return 它作为特征对象：
```
fn nodes(&self) -> Box<dyn Iterator<&'_ V> + '_>
```
正如你所说，你不想要那个，所以就这样了。
您可以将生命周期参数添加到特征中，并在关联类型和 &self 接收器中使用该生命周期：
```
trait GraphData<'s, V: 's> {
    type NodesIter: Iterator<Item = &'s V>;
    fn nodes(&'s self) -> Self::NodesIter;
}

struct MyGraph<V> {
    nodes: Vec<V>,
}

impl<'s, V: 's> GraphData<'s, V> for MyGraph<V> {
    type NodesIter = std::slice::Iter<'s, V>;
    fn nodes(&'s self) -> Self::NodesIter {
        self.nodes.iter()
    }
}
```
这有效！但是，现在您的特征中有一个恼人的生命周期参数。在你的情况下这可能没问题（除了烦人），但在某些情况下它实际上可能是一个严重的问题，所以这可能对你有用也可能不起作用。
您可以将生命周期参数推得更深，方法是拥有一个辅助特征，该特征从生命周期到类型都充当类型级别的函数。这使情况变得不那么烦人了，因为生命周期参数不再是您的主要特征，但它受到与先前解决方法相同的限制。
您也可以走一条完全不同的路，编写一个迭代器包装器，其中包含对您的图形的引用。

这只是一个粗略的草图，但基本思想是可行的：您的实际内部迭代器不包含对图的任何引用（因此它的类型不需要 self 生命周期）。图引用存储在特定类型 Wrap 中，并传递给每个 next 调用的内部迭代器。

像这样：
```
trait InnerNodesIter { /* ... */ }

struct Wrap<'graph, G: GraphData, I: InnerNodesIter> {
    graph: &'graph G,
    iter: I,
}

type NodesIterInner: InnerNodesIter;
fn nodes(&self) -> Wrap<'_, Self, Self::NodesIterInner>;
```
然后你可以为 Wrap 实现 Iterator。您只需要一些内部迭代器的接口，您可以将引用传递给图形。类似于 fn next(&mut self, graph: &Graph) -> Option<...>。您需要在 InnerNodesIter.
中定义接口
当然，这很冗长。它也可能有点慢，具体取决于您的迭代器的工作方式。

简短而悲伤的总结是：没有在所有情况下都适用的令人满意的解决方法。

我对这种情况的看法：我在一个项目中多次发生这种情况。就我而言，我只是使用了 Box 解决方案，因为它非常简单并且工作正常。唯一的缺点是速度（分配和动态调度），但分配不会在紧密循环中发生（除非你有大量图表，每个图表只有很少的节点 - 不太可能）并且优化器可能有能力在大多数情况下将动态调用去虚拟化（毕竟，真正的类型信息只有一个函数边界）。

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

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

generics

rust

associated-types