我如何在 Rust 中表达通用映射和设置容器？

Question

我正在学习来自 C++ 背景的 Rust，并且我正在编写拓扑排序。

输入是类型为 Map<Key, Set<Key>> 的依赖映射，其中每个节点（键）都映射到它的依赖（一组键）。 Map 和 Set 可以是任何 Map 和 Set 实现。输出是一个具有排序拓扑顺序的向量。

在 C++ 中，我会为 Map 和 Set 使用 "template template parameter"：

template<
    class K,
    template<class...> class Map,
    template<class...> class Set
>
std::vector<K>
topological_sort(Map<K, Set<K>> const &depmap);

此函数可应用于map<Key, set<Key>>或unordered_map<Key, set<Key>>或map<Key, unordered_set<Key>>等

在 Rust 中，似乎没有 "template template parameter"。我可以写下：

fn topological_sort<K: Eq + Ord + Hash + Clone>(depmp: &BTreeMap<K, HashSet<K>>) -> Option<Vec<K>> {
}

但是代码在容器选择方面并不通用，因为它不适用于 HashMap<K, HashSet<K>>，等等

我尝试了假设的语法：

fn topological_sort<Map, Set, K: Eq + Ord + Hash + Clone>(depmp: &Map::<K, Set::<K>>) -> Option<Vec<K>>

这不起作用。 Rust 对通用容器的解决方案是什么？

Answer 1

What is Rust's solution for a generic container?

通用容器的理想解决方案尚不可用。这将由当前处于实施阶段的功能涵盖，generic associated types (GATs)。

目前，有一些方法可以使您的例程对某些用例通用。特别是，函数通过实现 IntoIterator:

的值接收任意数据序列是很常见的

fn my_number_process<I>(stream: I) -> f32
where
    I: IntoIterator<Item = f32>,
{
    stream.into_iter().map(|x| x * 2. + 5.).sum().unwrap_or(0.)
}

对于类似字典的容器，Index and IndexMut 特征公开了通过已知类型的键获取对接收器中值的引用的特定功能。两种情况下的方法 return &Self::Output，没有为可恢复的错误或其他类型的输出留下空间。作为替代方案，您可以创建一个符合目的的新特征，同时尝试克服缺乏高等类型的问题。特别是，下面的特征不能为普通 HashMap:

实现

trait IMap<K> {
    type Value;

    fn get<B: Borrow<K>>(&self, key: B) -> Option<Self::Value>;
}

这是因为我们不能将 Value 指定为 &'a V，其中 'a 是将实例化为 self 的生命周期。但是对于引用HashMap:

可以实现

impl<'a, K, V> IMap<K> for &'a HashMap<K, V>
where
    K: Eq,
    K: Hash,
{
    type Value = &'a V;

    fn get<B: Borrow<K>>(&self, key: B) -> Option<Self::Value> {
        HashMap::get(self, key.borrow())
    }
}

Playground

可以对通用 Set 容器采用类似的推理。

Answer 2

这是我能得出的最接近的结果：

use std::collections::*;
use std::hash::Hash;
use std::ops::Index;

trait Set<K> {
    fn does_contain(&self, value: &K) -> bool;
}
impl<K: Eq + Hash> Set<K> for HashSet<K> {
    fn does_contain(&self, value: &K) -> bool {
        self.contains (value)
    }
}
impl<K: Eq + Ord> Set<K> for BTreeSet<K> {
    fn does_contain(&self, value: &K) -> bool {
        self.contains (value)
    }
}

fn topological_sort<K, S: Set<K>, M: Index<K, Output=S>> (depmp: &M) -> Option<Vec<K>> {
    unimplemented!()
}

它使用 std::ops::Index 对映射类型进行抽象，并使用自定义 Set 特征对集合类型进行抽象。

我如何在 Rust 中表达通用映射和设置容器？

How do I express generic map and set containers in Rust?

generic-programming

rust