Rust: how to use lifetimes when there are no references?

Question

I have this code:

use std::hash::Hash;
use std::rc::Rc;

struct Counter<V> {
    value: V,
}

struct LFUCache<K, V> {
    values: Vec<(Rc<K>, Counter<V>)>,
}

impl<K: Hash + Eq, V> IntoIterator for LFUCache<K, V> {
    type Item = (Rc<K>, V);
    type IntoIter = Box<dyn Iterator<Item=(Rc<K>, V)>>;

    fn into_iter(self) -> Self::IntoIter {
        return Box::new(self
            .values
            .into_iter()
            .map(|(key, value_counter)| (key, value_counter.value)));
    }
}

I get an error:

error[E0310]: the parameter type `K` may not live long enough
   --> src/lib.rs:167:16
    |
162 |   impl<K: Hash + Eq, V> IntoIterator for LFUCache<K, V> {
    |        -- help: consider adding an explicit lifetime bound `K: 'static`...
...
167 |           return Box::new(self
    |  ________________^
168 | |             .values
169 | |             .into_iter()
170 | |             .map(|(key, value_counter)| (key, value_counter.value)));
    | |____________________________________________________________________^
    |
note: ...so that the type `std::iter::Map<std::collections::hash_map::IntoIter<std::rc::Rc<K>, ValueCounter<V>>, [closure@src/lib.rs:170:18: 170:67]>` will meet its required lifetime bounds
   --> src/lib.rs:167:16
    |
167 |           return Box::new(self
    |  ________________^
168 | |             .values
169 | |             .into_iter()
170 | |             .map(|(key, value_counter)| (key, value_counter.value)));

I'd like to express that the intent that the boxed iterator should live as long as the LFU cache. However, since there are no references, I can't get any lifetimes.

How do I fix this?

_"Since there are no references, I can't get any lifetimes"_ Incorrect, you can still introduce new lifetime parameters and use them to apply a lifetime bound on the rest of the type parameters. It would go along something like this: `impl<'a, K: Hash + Eq + 'a, V: 'a> IntoIterator for LFUCache`, without forgetting the same bounds on the associated types (`type IntoIter = Box, V)> + 'a>`, etc) — E_net4, Jun 21 '20 at 13:57
It also helps in the future that you create a proper [mre] when asking a question. This one is missing the definition of `LFUCache`. — E_net4, Jun 21 '20 at 13:57
@E_net4likesdownvotes thanks for the pointers. `Rc` seems to be invalid, I get an error saying that it's "not a trait" — nz_21, Jun 21 '20 at 14:01
@E_net4likesdownvotes if I do that, I get an error saying that 'a' is an unconstrained lifetime parameter. — nz_21, Jun 21 '20 at 14:03
@nz_21 I strongly recommend you read [Common Rust Lifetime Misconceptions](https://github.com/pretzelhammer/rust-blog/blob/master/posts/common-rust-lifetime-misconceptions.md) since your confusion stems from a handful of common misconceptions that would be difficult to concisely address in a single answer. — pretzelhammer, Jun 21 '20 at 19:53

score 2 · Answer 1 · answered Jun 21 '20 at 17:37

This does not completely answer the question, but it may be worth noting that the lifetime difficulties arise from using a boxed trait object to hold the returned iterator. If you return the iterator directly, then there's no problem:

use std::hash::Hash;
use std::rc::Rc;
use std::{iter, vec};

struct Counter<V> {
    value: V,
}

struct LFUCache<K, V> {
    values: Vec<(Rc<K>, Counter<V>)>,
}

impl<K: Hash + Eq, V> IntoIterator for LFUCache<K, V> {
    type Item = (Rc<K>, V);
    type IntoIter =
        iter::Map<vec::IntoIter<(Rc<K>, Counter<V>)>, fn((Rc<K>, Counter<V>)) -> (Rc<K>, V)>;

    fn into_iter(self) -> Self::IntoIter {
        self.values
            .into_iter()
            .map(|(key, value_counter)| (key, value_counter.value))
    }
}

This also may have better performance, by avoiding the Box allocation and vtable lookups. The drawback here is that the iterator has a fairly complicated type that you have to write. Eventually, Rust's "impl Trait" functionality may be extended to cover this situation so that you don't have to write the type explicitly. In fact with nightly Rust you can already do it using an unstable feature:

#![feature(type_alias_impl_trait)]    

impl<K: Hash + Eq, V> IntoIterator for LFUCache<K, V> {
    type Item = (Rc<K>, V);
    type IntoIter = impl Iterator<Item = (Rc<K>, V)>;

    fn into_iter(self) -> Self::IntoIter {
        self.values
            .into_iter()
            .map(|(key, value_counter)| (key, value_counter.value))
    }
}

score 1 · Answer 2 · answered Jun 21 '20 at 14:30

1

I'd like to express that the intent that the boxed iterator should live as long as the LFU cache.

The method into_iter consumes self, so this doesn't make sense. The LFU cache is gone just by calling into_iter().

If you want to keep it around, then you can instead implement IntoIterator for &LFUCache. Now you have a reference—and so a lifetime—which the iterator can be tied to. Note that iterating will move values of type V, so you need to either constrain it to be Copy (or at least Clone), or else make the iterator item contain references to V instead. Here is the working example using references:

impl<'a, K: Hash + Eq, V> IntoIterator for &'a LFUCache<K, V> {
    type Item = (Rc<K>, &'a V);
    type IntoIter = Box<dyn Iterator<Item=(Rc<K>, &'a V)> + 'a>;

    fn into_iter(self) -> Self::IntoIter {
        return Box::new(self
            .values
            .iter()
            .map(|(key, value_counter)| (key.clone(), &value_counter.value)));
    }
}

answered Jun 21 '20 at 14:30

Peter Hall

53,120
14
139
204

> "The method into_iter consumes self, so this doesn't make sense. " Then how does it work for vectors? It's perfectly valid to do `for value in v.into_iter() {}` The vector is being consumed upon calling `into_iter()` but I can still get its underlying values – nz_21 Jun 21 '20 at 14:33
That too would consume the vector, @nz_21. – E_net4 Jun 21 '20 at 14:34
My end goal is to achieve this: `for (key, value) in lfu.into_iter() {}` where the lfu is consumed and the key and value are moved out. Key is of type `Rc` and value is `V` – nz_21 Jun 21 '20 at 14:35
Indeed it does. If `v` is a vector, then `v.into_iter()` will consume it, so you cannot use it afterwards: [playground example](https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=b4a1e5ba973c38e7cdbc90c7b60cc93b) – Peter Hall Jun 21 '20 at 14:36
That's a strange limitation. Why not just use `for value in &cache {}`? – Peter Hall Jun 21 '20 at 14:40
@PeterHall I am doing it as a learning exercise. I also already have a version of `Iterator` implemented that returns references. – nz_21 Jun 21 '20 at 14:42
_"My end goal is to achieve this...where the lfu is consumed and the key and value are moved out."_ — then what are the references for? If it's moved, there is nothing to reference. You have to move the values too and the iterator can live as long as needs to - it can't be constrained by the lifetime of something you have consumed. – Peter Hall Jun 21 '20 at 14:43
@PeterHall not sure I understand -- there are no references in the code I posted in my question – nz_21 Jun 21 '20 at 14:46
1

Maybe you need to re-read your question (including the title, and the part I quoted), and then possibly re-write it if it doesn't communicate what you actually wanted to ask. – Peter Hall Jun 21 '20 at 14:48

Rust: how to use lifetimes when there are no references?

2 Answers2