有什么方法可以在Rust中模拟泛型关联类型/关联类型构造函数? [英] Is there any way to simulate Generic Associated Types / Associated Type Constructors in Rust?

问题描述

我正在Rust中制作一个图形处理模块.该模块的核心对具有多个容器的想法进行了建模，这些容器将数据保存在图中.例如，我可能有一个内部结构为HashMap或AdjacencyMatrix等的图.

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...
}

我不能只在我的特征定义中返回一个特征.我知道我必须使用trait对象，但是我不想Box它.我想使容器提供自己的NodeIter结构.但是，我会陷入

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.

是否可以使用任何变通办法来模拟" ATC或可以在这种情况下使用的特定于Rust的任何模式?

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

我不想依靠动态调度，而不得不使用Box或dyn关键字.

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

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

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.

推荐答案

作为 Anders Kaseorg的答案已经说明:如果可以克隆包含顶点的Vec，则可能不需要此处的GAT.但是，这可能不是您想要的.取而代之的是，您通常希望有一个引用原始数据的迭代器.

As the answer by Anders Kaseorg already explains: you might not need GATs here, if you can live with cloning your Vec containing the vertices. However, that's probably not what you want. Instead, you usually want to have an iterator that references the original data.

要实现这一目标，实际上，您实际上希望使用GAT.但是，由于它们还不是该语言的一部分，因此让我们解决您的主要问题:是否有任何方法可以模拟泛型关联类型?我实际上写了一篇有关该主题的非常广泛的博客文章: 解决广义流没有GAT的迭代器问题" .

To achieve that, you in fact ideally want to use GATs. But since they are not part of the language yet, let's tackle your main question: Is there any way to simulate Generic Associated Types? I actually wrote a very extensive blog post about this topic: "Solving the Generalized Streaming Iterator Problem without GATs".

文章摘要:

• 最简单的方法是将迭代器装箱并将其作为特征对象返回:

• The easiest way for you is to box the iterator and return it as trait object:

fn nodes(&self) -> Box<dyn Iterator<&'_ V> + '_>

正如您所说，您不想要那样，所以就出来了.

As you said, you don't want that, so that's out.

您可以向特征添加一个生命周期参数，并在关联的类型和&self接收器中使用该生命周期:

You can add a lifetime parameter to your trait and use that lifetime in your associated type and the &self receiver:

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()
    }
}

这有效！但是，现在您的特征中有一个烦人的生命周期参数.在您的情况下，这可能很好(除了烦人)，但实际上在某些情况下可能是一个关键问题，因此这可能对您不起作用.

This works! However, now you have an annoying lifetime parameter in your trait. That might be fine (apart from annoyance) in your case, but it can actually be a critical problem in some situations, so this might or might not work for you.

您可以通过具有一个辅助特性，将生命周期参数推到更深的层次，该特性在生命周期到类型之间都充当类型级别函数.这使情况变得不那么令人讨厌，因为lifetime参数不再是您的主要特征，但是它受到与先前解决方法相同的局限性的困扰.

You can push the lifetime parameter a level deeper by having a helper trait which works as type level function from lifetime to type. This makes the situation a little less annoying, because the lifetime parameter is not in your main trait anymore, but it suffers from the same limitation as the prior workaround.

您还可以走完全不同的路径，并编写包含对图形的引用的迭代器包装器.

You can also go a completely different path and write an iterator wrapper that contains a reference to your graph.

这只是一个粗略的草图，但是基本思想有效:您的实际内部迭代器不包含对图形的任何引用(因此其类型不需要self寿命).而是将图形引用存储在特定的类型Wrap中，并在每次next调用时传递给内部迭代器.

This is just a rough sketch, but the basic idea works: your actual inner iterator doesn't contain any reference to the graph (so its type does not need the self lifetime). The graph reference is instead stored in a specific type Wrap and passed to the inner iterator for each next call.

赞:

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中定义接口.

Then you can implement Iterator for Wrap. You just need some interface to the inner iterator, which you can pass the reference to the graph. Something like fn next(&mut self, graph: &Graph) -> Option<...>. You need to define the interface in InnerNodesIter.

这当然很冗长.而且它可能还会变慢一些，具体取决于迭代器的工作方式.

This of course suffers from being very verbose. And it also might be a bit slower, depending on how your iterator works.

简短而可悲的总结是:没有一种令人满意的解决方法可以在每种情况下使用.

The short and sad summary is: there is no satisfying workaround that works in every situation.

在这种情况下，我的观点:我从事的项目确实多次发生这种情况.就我而言，我只使用了Box解决方案，因为它非常简单并且可以正常工作.唯一的缺点是速度(分配和动态分配)，但是分配不会在紧密的循环中发生(除非您有大量的图，每个图只有很少的节点-不太可能)，并且优化器可能能够大多数情况下取消动态调用虚拟化的方式(毕竟，实型信息仅在一个函数边界之内).

My opinion in this case: I work on a project where this exact situation occurred multiple times. In my case, I just used the Box solution as it's very easy and works fine. The only downside is speed (allocation and dynamic dispatch), but the allocation doesn't happen in a tight loop (except if you have a large number of graphs, each with only very few nodes -- unlikely) and the optimizer is probably capable of devirtualizing the dynamic calls in most cases (after all, the real type information is only one function boundary away).

这篇关于有什么方法可以在Rust中模拟泛型关联类型/关联类型构造函数?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！