Eliminate lifetime parameter from a trait whose implementation wraps a HashMap?

Question

I'd like to wrap a few methods of HashMap such as insert and keys. This attempt compiles, and the tests pass:

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

pub trait Map<'a, N: 'a> {
    type ItemIterator: Iterator<Item=&'a N>;

    fn items(&'a self) -> Self::ItemIterator;
    fn insert(&mut self, item: N);
}

struct MyMap<N> {
    map: HashMap<N, ()>
}

impl<N: Eq + Hash> MyMap<N> {
    fn new() -> Self {
        MyMap { map: HashMap::new() }
    }
}

impl<'a, N: 'a + Eq + Hash> Map<'a, N> for MyMap<N> {
    type ItemIterator = std::collections::hash_map::Keys<'a, N, ()>;

    fn items(&'a self) -> Self::ItemIterator {
        self.map.keys()
    }

    fn insert(&mut self, item: N) {
        self.map.insert(item, ());
    }
}

#[cfg(test)]
mod tests {
    use super::*;

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

    #[test]
    fn test() {
        let mut map = MyMap::new();
        let item = MyItem { };

        map.insert(&item);

        let foo = map.items().collect::<Vec<_>>();

        for it_item in map.items() {
            assert_eq!(it_item, &&item);
        }

        assert_eq!(foo, vec![&&item]);
    }
}

I'd like to eliminate the need for the lifetime parameter in Map if possible, but so far haven't found a way. The problem seems to result from the definition of std::collections::hash_map::Keys, which requires a lifetime parameter.

Attempts to redefine the Map trait work until it becomes necessary to supply the lifetime parameter on Keys:

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

pub trait Map<N> {
    type ItemIterator: Iterator<Item=N>;

    fn items(&self) -> Self::ItemIterator;
    fn insert(&mut self, item: N);
}

struct MyMap<N> {
    map: HashMap<N, ()>
}

impl<N: Eq + Hash> MyMap<N> {
    fn new() -> Self {
        MyMap { map: HashMap::new() }
    }
}

// ERROR: "unconstrained lifetime parameter"
impl<'a, N> Map<N> for MyMap<N> {
    type ItemIterator = std::collections::hash_map::Keys<'a, N, ()>;
}

The compiler issues an error about an unconstrained lifetime parameter that I haven't been able to fix without re-introducing the lifetime into the Map trait.

The main goal of this experiment was to see how I could also eliminate Box from previous attempts. As this question explains, that's another way to return an iterator. So I'm not interested in that approach at the moment.

How can I set up Map and an implementation without introducing a lifetime parameter or using Box?

Answer 1

Something to think about is that since hash_map::Keys has a generic lifetime parameter, it is probably necessary for some reason, so your trait to abstract over Keys will probably need it to.

In this case, in the definition of Map, you need some way to specify how long the ItemIterator's Item lives. (The Item is &'a N).

This was your definition:

type ItemIterator: Iterator<Item=&'a N>

You are trying to say that for any struct that implements Map, the struct's associated ItemIterator must be an iterator of references; however, this constraint alone is useless without any further information: we also need to know how long the reference lives for (hence why type ItemIterator: Iterator<Item=&N> throws an error: it is missing this information, and it cannot currently be elided AFAIK).

So, you choose 'a to name a generic lifetime that you guarantee each &'a N will be valid for. Now, in order to satisfy the borrow checker, prove that &'a N will be valid for 'a, and establish some useful promises about 'a, you specify that:

1. Any value for the reference &self given to items() must live at least as long as 'a. This ensures that for each of the returned items (&'a N), the &self reference must still be valid in order for the item reference to remain valid, in other words, the items must outlive self. This invariant allows you to reference &self in the return value of items(). You have specified this with fn items(&'a self). (Side note: my_map.items() is really shorthand for MyMap::items(&my_map)).
2. Each of the Ns themselves must also remain valid for as long as 'a. This is important if the objects contain any references that won't live forever (aka non-'static references); this ensures that all of the references that the item N contains live at least as long as 'a. You have specified this with the constraint N: 'a.

So, to recap, the definition of Map<'a, N> requires that an implementors' items() function must return an ItemIterator of references that are valid for 'a to items that are valid for 'a. Now, your implementation:

impl<'a, N: 'a + Eq + Hash> Map<'a, N> for MyMap<N> { ... }

As you can see, the 'a parameter is completely unconstrained, so you can use any 'a with the methods from Map on an instance of MyMap, as long as N fulfills its constraints of N: 'a + Eq + Hash. 'a should automatically become the longest lifetime for which both N and the map passed to items() are valid.

Anyway, what you're describing here is known as a streaming iterator, which has been a problem in years. For some relevant discussion, see the approved but currently unimplemented RFC 1598 (but prepare to be overwhelmed).

Finally, as some people have commented, it's possible that your Map trait might be a bad design from the start since it may be better expressed as a combination of the built-in IntoIterator<Item=&'a N> and a separate trait for insert(). This would mean that the default iterator used in for loops, etc. would be the items iterator, which is inconsistent with the built-in HashMap, but I am not totally clear on the purpose of your trait so I think your design likely makes sense.