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

What is Rust's solution for a generic container?

The ideal solution for generic containers is not available yet. This would be covered by a feature currently in the implementation phase, generic associated types (GATs).

For the time being, there are ways to make your routines generic for certain use cases. In particular, it is common for a function to receiving an arbitrary sequence of data through a value that implements 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.)
}

For dictionary-like containers, the Index and IndexMut traits expose the specific functionality of obtaining a reference to a value in the receiver by a key with a known type. The methods in both cases return &Self::Output, leaving no room for recoverable errors or other kinds of outputs. As an alternative, you can create a new trait that suits the purpose while attempting to overcome the lack of higher-kinded types. In particular, the trait below cannot be implemented for a plain HashMap:

trait IMap<K> {
    type Value;

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

This is because we cannot specify Value as a &'a V where 'a is a lifetime that would be instantiated as the lifetime of self. However, it can be implemented for a reference to 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

A similar reasoning can be employed to a generic Set container.

Answer 2

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.