generics - 如何迭代实现 Index 和 IntoIterator 的通用集合的索引？

Question

我想为任何通用集合实现一个小的有向图特征 C实现 std::ops::Index和 std::iter::IntoIterator .我希望集合代表图形的节点。每个节点都由其在 C 中的索引表示，这可能是一个 usize索引到 Vec或 String键入 HashMap . 我不知道这是否是图形库的最佳方法，但我也想了解 Rust、泛型特征和 Rust 的标准库。

在我实现的某些点上，我需要遍历 C 的所有索引实例。我找到的唯一方法是 enumerate函数，但这只实现了一个 usize迭代器的计数器而不是我的通用类型，所以它适用于 Vec , 但不适用于 HashMap .

这是使用 enumerate 实现的样子. nodes和 children需要功能，children返回图的邻接信息。使用 parents 获取所有前辈函数，我需要迭代通用容器类型的索引。

pub trait SimpleGraph {
    /// type used as an index to refer to nodes.
    type I: Eq + std::hash::Hash;

    /// container type for the nodes
    type C: std::ops::Index<Self::I> + std::iter::IntoIterator<Item = Self::I>;

    /// returns a reference to the node container.
    fn nodes(&self) -> &Self::C;

    /// gets the indices of the children of a node with index `index`.
    fn children(&self, index: Self::I) -> Vec<Self::I>;

    /// gets all ancestors of a node (not very efficient...)
    fn parents(&self, i: Self::I) -> Vec<Self::I> {
        let mut res = Vec::<Self::I>::new();
        let nodes = self.nodes();
        for (idx, _) in nodes.into_iter().enumerate() {
            let children = self.children(idx);
            for child_idx in children {
                if child_idx == i {
                    res.push(idx);
                }
            }
        }
        return res;
    }
}

这给了我一个不太令人惊讶的编译器错误:

error[E0308]: mismatched types
  --> src/lib.rs:19:42
   |
19 |             let children = self.children(idx);
   |                                          ^^^ expected associated type, found usize
   |
   = note: expected type `<Self as SimpleGraph>::I`
              found type `usize`

一个丑陋的解决方案是添加另一个必需的方法indices它返回一个索引列表，然后遍历这个列表，但这对用户来说不是很友好，而且对于 std::collections 中的任何一个来说似乎都是不必要的步骤。实现了 std::ops::Index和 std::iter::IntoIterator .我宁愿覆盖 enumerate以通用方式发挥作用。

我如何以一种干净和通用的方式对此进行编码？

Answer 1

我找到了一种方法:

• Github Repo 中的最小示例
• Rust Playground 中的最小示例

说明

我意识到我希望 Index 提供一个 enumerate 方法来枚举索引和集合索引后面的项目。所以在接受的答案的帮助下 Using generic iterators instead of specific list types我实现了提供此方法的 Index 超特征。

第 1 步:定义一个新的 Enumerate 结构并为其实现 Iterator

pub struct Enumerate<IndexIter, ItemIter> {
    index: IndexIter,
    item: ItemIter,
}

/// implements the [`Iterator`] trait for the new struct
impl<IndexIter, ItemIter> Iterator for Enumerate<IndexIter, ItemIter>
where
    IndexIter: Iterator,
    ItemIter: Iterator,
{
    type Item = (IndexIter::Item, ItemIter::Item);

    /// returns the next iterator
    #[inline]
    fn next(&mut self) -> Option<(IndexIter::Item, ItemIter::Item)> {
        self.index.next().map(|idx| {
            // CAUTION! We need to make sure that the index and item iterators are ordered consistently.
            // We are really just incrementing two iterators simultaneously here...
            (idx, self.item.next().unwrap())
        })
    }
}

第 2 步:为添加 enumerate 方法的 Index 定义一个超特征

/// trait for implementing over the indices of collections that implement [`std::ops::Index`].
/// 
/// It adds the enumerate function that returns an `Enumerate<IndexIter,ItemIter>` as an iterator.
pub trait SuperIndex<'a, Idx>: std::ops::Index<Idx> {
    type IndexIter: Iterator<Item = Idx>;
    type ItemIter: Iterator;

    /// enumerates over the indices and items of a collection
    fn enumerate(&'a self) -> Enumerate<Self::IndexIter, Self::ItemIter>;
}

第 3 步:为我要使用的集合实现 super 特征

Vec的实现

/// implement the [`SuperIndex`] trait for [`Vec<T>`]
impl<'a, T: 'a> SuperIndex<'a, usize> for Vec<T> {
    type IndexIter = std::ops::Range<usize>;
    type ItemIter = std::slice::Iter<'a, T>;

    fn enumerate(&'a self) -> Enumerate<Self::IndexIter, Self::ItemIter> {
        Enumerate {
            index: 0..self.len(),
            item: self.iter(),
        }
    }
}

HashMap的实现

/// implement the [`SuperIndex`] trait for [`HashMap<K, V, S>`]
impl<'a, K: 'a, V: 'a, S> SuperIndex<'a, &'a K> for std::collections::HashMap<K, V, S>
where
    K: Eq + std::hash::Hash,
    S: std::hash::BuildHasher,
{
    type IndexIter = std::collections::hash_map::Keys<'a, K, V>;
    type ItemIter = std::collections::hash_map::Values<'a, K, V>;

    fn enumerate(&'a self) -> Enumerate<Self::IndexIter, Self::ItemIter> {
        Enumerate {
            index: self.keys(),
            item: self.values(),
        }
    }
}

讨论

现在我可以为实现 SuperIndex 的任何类型的集合枚举索引和值，并且 index 不必是 usize:

for (index, item) in c.enumerate() {
    assert_eq!(&c[index], item);
}

这个实现做了我想要的，我想不出任何替代方案，但它有一些小缺陷:

• SuperIndex 索引不能像 Index 那样通用，例如不允许切片。
• 我们需要为每个集合显式实现 SuperIndex。
• 在每个实现中，我们必须确保两个迭代器的顺序一致。

如果我的实现有任何问题，请告诉我!它似乎工作正常，但我只了解我在做什么。