Binding for associated type `Item` references lifetime `'a`, which does not appear in the trait input types

pub(crate) struct ConcurrentHashSet<E> 
{
    _map: HashMap<E, bool>,

}

impl<E> ConcurrentHashSet<E> 
where
    E: PartialEq + Eq + Hash,
{
    pub(crate) fn contains_all<C>(&self, mut c: C) -> bool
    where
        C: for<'a> Iterator<Item=&'a E>,
    {
        let map:&HashMap<E, bool> = &self._map;
        c.all(|e| map.contains_key(e))
    }
}

Error:

error[E0582]: binding for associated type `Item` references lifetime `'a`, which does not appear in the trait input types
  --> src/collection/ConcurrentHashSet.rs:50:29
   |
50 |         C: for<'a> Iterator<Item=&'a E>,
   |                             ^^^^^^^^^^

How could I solve this?
Is this related to Lifetime does not appear in the trait input types ?

I think this should express what you are trying to achieve with your API:

use std::collections::HashMap;
use std::hash::Hash;

pub(crate) struct ConcurrentHashSet<E> {
    _map: HashMap<E, bool>,
}

impl<'a, E> ConcurrentHashSet<E>
where
    E: PartialEq + Eq + Hash + 'a,
{
    pub(crate) fn contains_all<'b, C>(&self, mut c: C) -> bool
    where
        'a: 'b,
        C: Iterator<Item = &'b E>,
    {
        let map: &HashMap<E, bool> = &self._map;
        c.all(|e| map.contains_key(e))
    }
}

Playground.

3 Likes

Could you explain why 'a: 'b is needed?

fn test() {
    let cs = ConcurrentHashSet { _map: HashMap::from([(1, true), (2, true)]) };
    
    let b = [1,2,3];
    cs.contains_all(b.iter());
}

I'm a noob here so I'm not sure but
In the above example, I can't understand why it is needed.

In your example it is not really needed, because you use integers as keys. Integers have the 'static lifetime. But imagine you store some key type E that is a reference, like &'a str. Given your type definition it is completely possible to construct a ConcurrentHashSet<&'a str>, so we have to cater for that. We do so by first adding the 'a lifetime bound to E. This is how we tell the compiler, E will live for at least 'a. This subsequently allows us to use E's lifetime in our other generic type bounds, namely in C. What we can't allow is to pass some type &'b E<'a> where 'b may outlive 'a. If that'd be the case, E (or one of its fields) could potentially dangle, pointing to memory that has been freed. To avoid that, we explicitly tell the compiler: "hey, E lives at least as long as 'a (E: 'a) and 'a definitely outlives 'b ('a: 'b)," so passing an iterator with elements of &'b E<'a> is okay.

3 Likes

Thank you very much

1 Like