Rust: Borrowed value does not live long enough

Question

I am new to Rust and am working on a Rust solution to the leetcode question, "49. Group Anagrams" and ran into an issue with a borrowed value not living long enough error.

There are a few other related SOF threads but I had trouble understanding the content.

The error:

error[E0597]: `key` does not live long enough
  --> src/main.rs:14:18
   |
9  |     let key: String = sort_letters(&w);
   |         --- binding `key` declared here
10 |
11 |     if map.contains_key(&key as &str) {
   |        --- borrow later used here
...
14 |       map.insert(&key as &str, val);
   |                  ^^^^ borrowed value does not live long enough
...
20 |   }
   |   - `key` dropped here while still borrowed

fn main() {
    use std::any::type_name;
    use std::collections::HashMap;

    let words: Vec<&str> = vec!["eat", "tea", "tan", "ate", "nat", "bat"];
    let mut map: HashMap<&str, Vec<&str>> = HashMap::new();

    for w in words {
        let key: String = sort_letters(&w);

        if map.contains_key(&key as &str) {
            let mut val: Vec<&str> = map.get(&key as &str).unwrap().to_vec();
            val.push(w);
            map.insert(&key as &str, val);
        } else {
            let mut val = Vec::new();
            val.push(w);
            map.insert(&key as &str, val);
        }
    }
}

fn sort_letters(w: &str) -> String {
    let mut chars: Vec<char> = w.chars().collect();
    chars.sort();
    chars.into_iter().collect::<String>()
}

I tried cloning the key to give new ownership to the &key, but that gave me the same error.

Answer 1

    let mut map: HashMap<&str, Vec<&str>> = HashMap::new();

OK, so we're going to have a map, but this map won't own it's keys: the keys will be references to a string that is owned by something else.

    for w in words {
        let key: String = sort_letters(&w);
...
            map.insert(&key as &str, val);
...
    }

Now were are looping through some words, and on each iteration we create a string containing the letters of the word sorted. (BTW: no need to annotate key with the type String, rust is smart enough to figure that out).

That string value is owned by the variable key, which means when it goes out of scope (at the end of the loop iteration) that string is going to be dropped.

Then a few lines later, we add an entry to the map, with the key being a reference to that same string value (it actually happens in both branches of an if statement, I am only showing one for simplicity).

Then comes the end of the loop. The variable key goes out of scope, the value is dropped - but the map is still referring to it!

The solution is to make the map own the key, like this:

    let mut map: HashMap<String, Vec<&str>> = HashMap::new();

Then the loop looks like this:

    for w in words {
        let key: String = sort_letters(&w);

        if map.contains_key(&key) {
            let mut val: Vec<&str> = map.get(&key).unwrap().to_vec();
            val.push(w);
            map.insert(key, val);
        } else {
            let mut val = Vec::new();
            val.push(w);
            map.insert(key, val);
        }
    }

That will work, but it is pretty inefficient.

let mut val: Vec<&str> = map.get(&key).unwrap().to_vec();

to_vec creates a copy of the Vec in the map, and we then add the new word to the end of the Vec, and put this new Vec back into the map. We are constantly creating new Vecs and copying values from old to new.

There is a simpler and better way. HashMap has another method, entry, which allows you to very cleanly implement the "find or insert entry" pattern. Using entry your loop looks like this:

    for w in words {
        let key: String = sort_letters(&w);

        map.entry(key)
           .or_insert_with(Vec::new)
           .push(w);
    }

The entry method returns an Entry struct, which has various methods for populating the entry if it did not already exist. It also gives us mutable access to the new or existing entry, which we can just push our word straight onto.