IterMut and lifetime conflict with HashMap

This toy data structure is intended to be a HashMap that remembers insertion order. I'd like to be able to call iter() on it and then iterate over the elements in order. 'iter()' works, but my implementation of IterMut does not. I know that mut references have stronger lifetime requirements, but I'm not sure how to fix this. Thank you for your help.

P.S. this is a very reduced example of the real code, trying to be minimally reproducible. In reality, my OrderedHashMap will have a type parameter so that it is not always String as the element. So it will be OrderedHashMap.

use core::slice;
use std::collections::HashMap;

pub struct OrderedHashMap {
    order: Vec<usize>,
    elements: HashMap<usize, String>,
}

impl OrderedHashMap {
    fn default() -> OrderedHashMap {
        let mut data = HashMap::new();
        data.insert(10, "ten".into());
        data.insert(20, "twenty".into());
        data.insert(30, "thirty".into());

        let ret = OrderedHashMap {
            order: vec![30, 10, 20],
            elements: data,
        };

        ret
    }

    fn iter(&self) -> Iter<'_> {
        Iter {
            inner_order: self.order.iter(),
            inner_hash: &self.elements,
        }
    }
}

pub struct Iter<'a> {
    inner_order: slice::Iter<'a, usize>,
    inner_hash: &'a HashMap<usize, String>,
}

impl<'a> Iterator for Iter<'a> {
    type Item = (usize, &'a String);

    fn next(&mut self) -> Option<Self::Item> {
        self.inner_order.next().map(|token| {
            let item = &self.inner_hash[token];
            (*token, item)
        })
    }
}

// Doesn't compile :(

pub struct IterMut<'a> {
    inner_order: slice::Iter<'a, usize>,
    inner_hash: &'a mut HashMap<usize, String>,
}

impl<'a> Iterator for IterMut<'a> {
    type Item = (usize, &'a mut String);

    fn next(&mut self) -> Option<Self::Item> {
        self.inner_order.next().map(|token| {
            let item = &mut self.inner_hash[token];
            (*token, item)
        })
    }
}

fn main() {
    let mut v = OrderedHashMap::default();

    for item in v.iter() {
        println!("{:?}", item);
    }
}

(Playground)

Errors:

   Compiling playground v0.0.1 (/playground)
error[E0495]: cannot infer an appropriate lifetime for lifetime parameter in function call due to conflicting requirements
  --> src/main.rs:60:29
   |
60 |             let item = &mut self.inner_hash[token];
   |                             ^^^^^^^^^^^^^^^^^^^^^^
   |
note: first, the lifetime cannot outlive the anonymous lifetime #1 defined on the method body at 58:5...
  --> src/main.rs:58:5
   |
58 |     fn next(&mut self) -> Option<Self::Item> {
   |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
note: ...so that reference does not outlive borrowed content
  --> src/main.rs:60:29
   |
60 |             let item = &mut self.inner_hash[token];
   |                             ^^^^^^^^^^^^^^^
note: but, the lifetime must be valid for the lifetime `'a` as defined on the impl at 55:6...
  --> src/main.rs:55:6
   |
55 | impl<'a> Iterator for IterMut<'a> {
   |      ^^
note: ...so that the types are compatible
  --> src/main.rs:58:46
   |
58 |       fn next(&mut self) -> Option<Self::Item> {
   |  ______________________________________________^
59 | |         self.inner_order.next().map(|token| {
60 | |             let item = &mut self.inner_hash[token];
61 | |             (*token, item)
62 | |         })
63 | |     }
   | |_____^
   = note: expected `Iterator`
              found `Iterator`

error: aborting due to previous error

For more information about this error, try `rustc --explain E0495`.
error: could not compile `playground`

To learn more, run the command again with --verbose.

Implementing a mutable iterator often requires a bit of unsafe code, because the compiler can't prove on its own that the iterator will never yield the same reference twice. (Mutable references must be unique.)

You can use raw pointers to create mutable references without the borrow checker complaining, but you must make sure that your iterator will never give out two references to the same item:

    fn next(&mut self) -> Option<Self::Item> {
        self.inner_order.next().map(|token| {
            let item = unsafe {
                &mut *(self.inner_hash.get_mut(token).unwrap() as *mut String)
            };
            (*token, item)
        })
    }
1 Like

I don't think you can get this with how it's structured currently, the reason being that nothing is telling the compiler that your Vec won't contain duplicates.

IMO the best way to model this is to store the String/other type in the Vec, and the indices in an HashSet. The problem with this approach is that you will have to borrow the Vec when hashing, because you don't want to hash just the usize, you want to hash with respect to vec[index]. This can be accomplished with hashbrown::raw::RawTable. It has a bunch of unsafe methods, however the safe ones should be enough for what you're trying to do.

1 Like

Thinking out loud here, please correct me if I'm wrong...

...because the compiler can't prove on its own that the iterator will never yield the same reference twice. (Mutable references must be unique.)

When I read this I initially thought: "but can't the compiler just look at the context in which the iterator is being used to conclude that no references are being stashed or abused?" e.g.:

let mut v = OrderedHashMap::default();

for mut ref item in v.iter_mut() {
    // Nothing fishy going on here!
    println!("{:?}", item);
}

...but then I realized that the compiler isn't trying to do the proof at this level. It wants to ensure that a non-unique reference never makes it out of next() in the first place. But because it can't statically prove that, it rejects the code.

So then what your code is doing is putting the mut ref creation behind an unsafe cloak so the compiler can't peek in. It's then up to me to ensure I don't do something stupid like this:

let mut v = OrderedHashMap::default();
        
let mut item0 = v.iter_mut().next();
println!("{:?}", item0);

// danger:
let mut also_item0 = v.iter_mut().next();
println!("{:?}", also_item0);

Is my understanding correct?

Yes, exactly.

1 Like

I was previously doing something similar. For the sake of simplicity I reduced my code, but here's what I used to use:

#[derive(Eq, PartialEq, Debug, Hash, Clone, Copy)]
pub struct Token {
    value: usize,
}

pub struct OrderedHashMap<T> {
    elements: Vec<(T, Token)>,
    token_to_elements: HashMap<Token, usize>,
    next_token: Token, // the next token to be given out when an item is added
}

My problem statement was also simplified - the actual data structure I am designing is like stable_vec (stable_vec - Rust) but that also maintains index validity in the face of arbitrary item insertions or removals. It does this by handing out opaque Tokens (just thin wrappers around a usize). Clients can only manipulate items via the tokens.

Some important methods signatures:

pub fn insert_after(&mut self, token: Token, data: T) -> Token;
pub fn insert_before(&mut self, token: Token, data: T) -> Token;
pub fn push(&mut self, data: T) -> Token;

As you can imagine it is not very performant, but it's not designed to be.

Anyway, with this design the iterators were quite simple since all I had to do was store the slice::Iter or slice::IterMut for the underlying elements Vec.

OK, cool! Thanks :slight_smile:

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.