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

Question

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

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.

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);

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

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

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

I tried the hypothetical syntax:

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

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

Answer 1

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

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