Как мне выразить общую карту и установить контейнеры в Rust?

Question

Я изучаю Rust из C ++ фона и пишу топологическую сортировку.

Входные данные представляют собой карту зависимостей с типом Map<Key, Set<Key>>, где каждый узел (ключ) сопоставлен с егозависимость (набор ключей).Map и Set может быть любой Map и Set реализацией.Выходными данными является вектор с отсортированным топологическим порядком.

В C ++ я бы использовал «параметр шаблона шаблона» как для Map, так и для 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>> и т. д.

В Rust, похоже, нет "параметра шаблона шаблона".Я могу написать следующее:

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

Но тогда код не является универсальным с точки зрения выбора контейнера, так как он не будет работать для HashMap<K, HashSet<K>> и т. Д.

Iпробовал гипотетический синтаксис:

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

Это не работает.Каково решение Rust для универсального контейнера?

Answer 1

Это самое близкое, что я мог бы получить:

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 для абстрагирования по установленному типу..

Answer 2

Что такое решение Rust для универсального контейнера?

Идеальное решение для универсальных контейнеров недоступно пока .Это будет охватываться функцией, которая в настоящее время находится на этапе реализации, универсальными ассоциированными типами (GAT) .

. В настоящее время существуют способы сделать ваши подпрограммы общими для определенных случаев использования.В частности, для функции характерно получение произвольной последовательности данных через значение, которое реализует 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и IndexMut черты раскрывают специфические функциональные возможности получения ссылки на значение в получателе по ключу с известным типом.Методы в обоих случаях возвращают &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.