iterator - 如何向 Iterator 添加新方法？

Question

我想在迭代器上定义一个 .unique() 方法，使我能够在没有重复的情况下进行迭代。

use std::collections::HashSet;

struct UniqueState<'a> {
    seen: HashSet<String>,
    underlying: &'a mut Iterator<Item = String>,
}

trait Unique {
    fn unique(&mut self) -> UniqueState;
}

impl Unique for Iterator<Item = String> {
    fn unique(&mut self) -> UniqueState {
        UniqueState {
            seen: HashSet::new(),
            underlying: self,
        }
    }
}

impl<'a> Iterator for UniqueState<'a> {
    type Item = String;
    fn next(&mut self) -> Option<String> {
        while let Some(x) = self.underlying.next() {
            if !self.seen.contains(&x) {
                self.seen.insert(x.clone());
                return Some(x);
            }
        }
        None
    }
}

这编译。但是，当我尝试在同一个文件中使用时:

fn main() {
    let foo = vec!["a", "b", "a", "cc", "cc", "d"];

    for s in foo.iter().unique() {
        println!("{}", s);
    }
}

我收到以下错误:

error[E0599]: no method named `unique` found for type `std::slice::Iter<'_, &str>` in the current scope
  --> src/main.rs:37:25
   |
37 |     for s in foo.iter().unique() {
   |                         ^^^^^^
   |
   = help: items from traits can only be used if the trait is implemented and in scope
   = note: the following trait defines an item `unique`, perhaps you need to implement it:
           candidate #1: `Unique`

我做错了什么？我将如何扩展这种任意的可哈希类型？

Answer 1

在您的特定情况下，这是因为您已经为 String 的迭代器实现了特征，但是您的向量提供了 &str 的迭代器。这是一个更通用的版本:

use std::collections::HashSet;
use std::hash::Hash;

struct Unique<I>
where
    I: Iterator,
{
    seen: HashSet<I::Item>,
    underlying: I,
}

impl<I> Iterator for Unique<I>
where
    I: Iterator,
    I::Item: Hash + Eq + Clone,
{
    type Item = I::Item;

    fn next(&mut self) -> Option<Self::Item> {
        while let Some(x) = self.underlying.next() {
            if !self.seen.contains(&x) {
                self.seen.insert(x.clone());
                return Some(x);
            }
        }
        None
    }
}

trait UniqueExt: Iterator {
    fn unique(self) -> Unique<Self>
    where
        Self::Item: Hash + Eq + Clone,
        Self: Sized,
    {
        Unique {
            seen: HashSet::new(),
            underlying: self,
        }
    }
}

impl<I: Iterator> UniqueExt for I {}

fn main() {
    let foo = vec!["a", "b", "a", "cc", "cc", "d"];

    for s in foo.iter().unique() {
        println!("{}", s);
    }
}

大体上，我们创建了一个名为 UniqueExt 的新扩展特征，它具有 Iterator 作为超特征。当 Iterator 是超特征时，我们将可以访问关联类型 Iterator::Item。

这个trait定义了unique方法，只有当迭代项可以是:

1. 散列
2. 比较完全平等
3. 克隆

此外，它要求实现 Iterator 的项在编译时具有已知大小。这样做是为了让 Unique 迭代器适配器使用迭代器。

另一个重要部分是一揽子实现任何类型的特性，也实现Iterator:

impl<I: Iterator> UniqueExt for I {}