如何在Rust中表达通用地图并设置容器? [英] How do I express generic map and set containers in Rust?

问题描述

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

I'm learning Rust coming from a C++ background and I'm writing a topological sort.

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

The input is a dependency map with type Map<Key, Set<Key>>, where every node (key) is mapped to its dependency (a set of keys). Map and Set can be any Map and Set implementation. The output is a vector with sorted topological order.

在C ++中，我将同时为Map和Set使用模板模板参数":

In C++, I would use a "template template parameter" for both Map and Set:

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

This function can apply to map<Key, set<Key>> or unordered_map<Key, set<Key>> or map<Key, unordered_set<Key>>, etc.

在Rust中，似乎没有模板模板参数".我可以写以下内容:

In Rust, it seems there is no "template template parameter". I can write the following:

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

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

But then the code isn't generic in terms of the container choice, since it won't work for HashMap<K, HashSet<K>>, etc.

我尝试了假设的语法:

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

这不起作用. Rust对于通用容器的解决方案是什么?

This does not work. What is Rust's solution for a generic container?

推荐答案

这是我能找到的最接近的

This is the closest I could come:

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特征来抽象集合类型.

It uses std::ops::Index to abstract over the map type and a custom Set trait to abstract over the set type.

这篇关于如何在Rust中表达通用地图并设置容器?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！