How do I use a &HashSet<&T> as an IntoIterator<Item = &T>?

Question

I have a function that takes a collection of &T (represented by IntoIterator) with the requirement that every element is unique.

fn foo<'a, 'b, T: std::fmt::Debug, I>(elements: &'b I)
where
    &'b I: IntoIterator<Item = &'a T>,
    T: 'a,
    'b: 'a,

I would like to also write a wrapper function which can work even if the elements are not unique, by using a HashSet to remove the duplicate elements first.

I tried the following implementation:

use std::collections::HashSet;

fn wrap<'a, 'b, T: std::fmt::Debug + Eq + std::hash::Hash, J>(elements: &'b J)
where
    &'b J: IntoIterator<Item = &'a T>,
    T: 'a,
    'b: 'a,
{
    let hashset: HashSet<&T> = elements.into_iter().into_iter().collect();
    foo(&hashset);
}

playground

However, the compiler doesn't seem happy with my assumption that HashSet<&T> implements IntoIterator<Item = &'a T>:

error[E0308]: mismatched types
  --> src/lib.rs:10:9
   |
10 |     foo(&hashset);
   |         ^^^^^^^^ expected type parameter, found struct `std::collections::HashSet`
   |
   = note: expected type `&J`
              found type `&std::collections::HashSet<&T>`
   = help: type parameters must be constrained to match other types
   = note: for more information, visit https://doc.rust-lang.org/book/ch10-02-traits.html#traits-as-parameters

I know I could use a HashSet<T> by cloning all the input elements, but I want to avoid unnecessary copying and memory use.

Answer 1

If you have a &HashSet<&T> and need an iterator of &T (not &&T) that you can process multiple times, then you can use Iterator::copied to convert the iterator's &&T to a &T:

use std::{collections::HashSet, fmt::Debug, hash::Hash, marker::PhantomData};

struct Collection<T> {
    item: PhantomData<T>,
}

impl<T> Collection<T>
where
    T: Debug,
{
    fn foo<'a, I>(elements: I) -> Self
    where
        I: IntoIterator<Item = &'a T> + Clone,
        T: 'a,
    {
        for element in elements.clone() {
            println!("{:?}", element);
        }
        for element in elements {
            println!("{:?}", element);
        }
        Self { item: PhantomData }
    }
}

impl<T> Collection<T>
where
    T: Debug + Eq + Hash,
{
    fn wrap<'a, I>(elements: I) -> Self
    where
        I: IntoIterator<Item = &'a T>,
        T: 'a,
    {
        let set: HashSet<_> = elements.into_iter().collect();
        Self::foo(set.iter().copied())
    }
}

#[derive(Debug, Hash, PartialEq, Eq)]
struct Foo(i32);

fn main() {
    let v = vec![Foo(1), Foo(2), Foo(4)];
    Collection::<Foo>::wrap(&v);
}

See also:

• Using the same iterator multiple times in Rust
• Does cloning an iterator copy the entire underlying vector?
• Why does cloning my custom type result in &T instead of T?

---

Note that the rest of this answer made the assumption that a struct named Collection<T> was a collection of values of type T. OP has clarified that this is not true.

That's not your problem, as shown by your later examples. That can be boiled down to this:

struct Collection<T>(T);

impl<T> Collection<T> {
    fn new(value: &T) -> Self {
        Collection(value)
    }
}

You are taking a reference to a type (&T) and trying to store it where a T is required; these are different types and will generate an error. You are using PhantomData for some reason and accepting references via the iterator, but the problem is the same.

In fact, PhantomData makes the problem harder to see as you can just make up values that don't work. For example, we never have any kind of string here but we "successfully" created the struct:

use std::marker::PhantomData;

struct Collection<T>(PhantomData<T>);

impl Collection<String> {
    fn new<T>(value: &T) -> Self {
        Collection(PhantomData)
    }
}

Ultimately, your wrap function doesn't make sense, either:

impl<T: Eq + Hash> Collection<T> {
    fn wrap<I>(elements: I) -> Self
    where
        I: IntoIterator<Item = T>,

This is equivalent to

impl<T: Eq + Hash> Collection<T> {
    fn wrap<I>(elements: I) -> Collection<T>
    where
        I: IntoIterator<Item = T>,

Which says that, given an iterator of elements T, you will return a collection of those elements. However, you put them in a HashMap and iterate on a reference to it, which yields &T. Thus this function signature cannot be right.

It seems most likely that you want to accept an iterator of owned values instead:

use std::{collections::HashSet, fmt::Debug, hash::Hash};

struct Collection<T> {
    item: T,
}

impl<T> Collection<T> {
    fn foo<I>(elements: I) -> Self
    where
        I: IntoIterator<Item = T>,
        for<'a> &'a I: IntoIterator<Item = &'a T>,
        T: Debug,
    {
        for element in &elements {
            println!("{:?}", element);
        }
        for element in &elements {
            println!("{:?}", element);
        }

        Self {
            item: elements.into_iter().next().unwrap(),
        }
    }
}

impl<T> Collection<T>
where
    T: Eq + Hash,
{
    fn wrap<I>(elements: I) -> Self
    where
        I: IntoIterator<Item = T>,
        T: Debug,
    {
        let s: HashSet<_> = elements.into_iter().collect();
        Self::foo(s)
    }
}

#[derive(Debug, Hash, PartialEq, Eq)]
struct Foo(i32);

fn main() {
    let v = vec![Foo(1), Foo(2), Foo(4)];
    let c = Collection::wrap(v);
    println!("{:?}", c.item)
}

Here we place a trait bound on the generic iterator type directly and a second higher-ranked trait bound on a reference to the iterator. This allows us to use a reference to the iterator as an iterator itself.

See also:

• How does one generically duplicate a value in Rust?
• Is there any way to return a reference to a variable created in a function?
• How do I write the lifetimes for references in a type constraint when one of them is a local reference?

Answer 2

There were a number of orthogonal issues with my code that Shepmaster pointed out, but to solve the issue of using a HashSet<&T> as an IntoIterator<Item=&T>, I found that one way to solve it is with a wrapper struct:

struct Helper<T, D: Deref<Target = T>>(HashSet<D>);

struct HelperIter<'a, T, D: Deref<Target = T>>(std::collections::hash_set::Iter<'a, D>);

impl<'a, T, D: Deref<Target = T>> Iterator for HelperIter<'a, T, D>
where
    T: 'a,
{
    type Item = &'a T;
    fn next(&mut self) -> Option<Self::Item> {
        self.0.next().map(|x| x.deref())
    }
}

impl<'a, T, D: Deref<Target = T>> IntoIterator for &'a Helper<T, D> {
    type Item = &'a T;
    type IntoIter = HelperIter<'a, T, D>;
    fn into_iter(self) -> Self::IntoIter {
        HelperIter((&self.0).into_iter())
    }
}

Which is used as follows:

struct Collection<T> {
    item: PhantomData<T>,
}

impl<T: Debug> Collection<T> {
    fn foo<I>(elements: I) -> Self
    where
        I: IntoIterator + Copy,
        I::Item: Deref<Target = T>,
    {
        for element in elements {
            println!("{:?}", *element);
        }
        for element in elements {
            println!("{:?}", *element);
        }
        return Self { item: PhantomData };
    }
}

impl<T: Debug + Eq + Hash> Collection<T> {
    fn wrap<I>(elements: I) -> Self
    where
        I: IntoIterator + Copy,
        I::Item: Deref<Target = T> + Eq + Hash,
    {
        let helper = Helper(elements.into_iter().collect());
        Self::foo(&helper);
        return Self { item: PhantomData };
    }
}

fn main() {
    let v = vec![Foo(1), Foo(2), Foo(4)];
    Collection::<Foo>::wrap(&v);
}

I'm guessing that some of this may be more complicated than it needs to be, but I'm not sure how.

full playground