How to iterate through a Hashmap, print the key/value and remove the value in Rust?

Question

This should be a trivial task in any language. This isn't working in Rust.

use std::collections::HashMap;

fn do_it(map: &mut HashMap<String, String>) {
    for (key, value) in map {
        println!("{} / {}", key, value);
        map.remove(key);
    }
}

fn main() {}

Here's the compiler error:

error[E0382]: use of moved value: `*map`
 --> src/main.rs:6:9
  |
4 |     for (key, value) in map {
  |                         --- value moved here
5 |         println!("{} / {}", key, value);
6 |         map.remove(key);
  |         ^^^ value used here after move
  |
  = note: move occurs because `map` has type `&mut std::collections::HashMap<std::string::String, std::string::String>`, which does not implement the `Copy` trait

Why it is trying to move a reference? From the documentation, I didn't think moving/borrowing applied to references.

Solution 1

There are at least two reasons why this is disallowed:

1. You would need to have two concurrent mutable references to map — one held by the iterator used in the for loop and one in the variable map to call map.remove.

2. You have references to the key and the value within the map when trying to mutate the map. If you were allowed to modify the map in any way, these references could be invalidated, opening the door for memory unsafety.

A core Rust principle is Aliasing XOR Mutability. You can have multiple immutable references to a value or you can have a single mutable reference to it.

I didn't think moving/borrowing applied to references.

Every type is subject to Rust's rules of moving as well as mutable aliasing. Please let us know what part of the documentation says it isn't so we can address that.

Why it is trying to move a reference?

This is combined of two parts:

1. You can only have a single mutable reference, so mutable references don't implement the Copy trait
2. for loops take the value to iterate over by value

When you call for (k, v) in map {}, the ownership of map is transferred to the for loop and is now gone.

---

I'd perform an immutable borrow of the map (&*map) and iterate over that. At the end, I'd clear the whole thing:

fn do_it(map: &mut HashMap<String, String>) {
    for (key, value) in &*map {
        println!("{} / {}", key, value);
    }
    map.clear();
}

remove every value with a key that starts with the letter "A"

I'd use HashMap::retain:

fn do_it(map: &mut HashMap<String, String>) {
    map.retain(|key, value| {
        println!("{} / {}", key, value);

        !key.starts_with("a")
    })
}

This guarantees that key and value no longer exist when the map is actually modified, thus any borrow that they would have had is now gone.

Solution 2

This should be a trivial task in any language.

Rust is preventing you from mutating the map while you are iterating over it. In most languages this is allowed, but often the behaviour is not well-defined, and removal of the item can interfere with the iteration, compromising its correctness.

Why it is trying to move a reference?

HashMap implements IntoIterator, so your loop is equivalent to:

for (key, value) in map.into_iter() {
    println!("{} / {}", key, value);
    map.remove(key);
}

If you look at the definition of into_iter, you'll see that it takes self, not &self or &mut self. Your variable map is a mutable reference, and IntoIterator is implemented for &mut HashMap - the self in into_iter is the &mut HashMap, not the HashMap. Mutable references cannot be copied (since only one mutable reference to any data can exist at one time) so this mutable reference is moved.

The API is intentionally built that way so that you can't do anything dangerous while looping over a structure. Once the loop is complete, the ownership of the structure is relinquished and you can use it again.

One solution is to keep track of the items you intend to remove in a Vec and then remove them afterwards:

fn do_it(map: &mut HashMap<String, String>) {
    let mut to_remove = Vec::new();
    for (key, value) in &*map {
        if key.starts_with("A") {
            to_remove.push(key.to_owned());
        }
    }
    for key in to_remove.iter() {
        map.remove(key);
    }
}

You may also use an iterator to filter the map into a new one. Perhaps something like this:

fn do_it(map: &mut HashMap<String, String>) {
    *map = map.into_iter().filter_map(|(key, value)| {
        if key.starts_with("A") {
            None
        } else {
            Some((key.to_owned(), value.to_owned()))
        }
    }).collect();
}

But I just saw Shepmaster's edit - I had forgotten about retain, which is better. It's more concise and doesn't do unnecessary copying as I have done.

Solution 3

Rust actually supports a wide number of potential solutions to this problem, though I myself also found the situation to be a bit confusing at first, and again each time I need a more complicated treatment of my hashmaps.

• To iterate through items while removing them, use .drain(). .drain() has the advantage of taking/owning rather than borrowing the values.
• If you want to only conditionally remove some of them, use .drain_filter().
• If you need to mutate every item but only want to remove some of them, you may mutate them in .drain_filter()'s closure argument, but this will check for removal after the changes.
• If you need to check for removal before the changes, use a variable to store the result of the check, then return that variable at the end. A very slightly slower but maybe more clear alternative is just to mutate them in one for loop, then .drain_filter() them in another for loop or a map.
• You may also simply allow the hashmap to drop at the end of the function by not borrowing it in the function argument, and initialize a new one if you need it. This completely removes the hashmap, obviously. Obviously you might want to keep the hashmap around so you don't reinitialize it over and over.
• You may also call .clear() to remove all elements, after you're done iterating through them to print them.

Comments

[MaddTheSane]

I can get the same error with for (key, value) in map {}; for (key, value) in map {}, and I don't think this answer explains that.

[loganfsmyth]

One way to think about it is, what would happen if you called that map.clear() inside the loop? key and value are references, and they wouldn't be referencing anything anymore. clear and remove both use &mut self, from a borrow-checker standpoint they are the same.

[MaddTheSane]

This led me to an even odder issue, but I suspect that the method call syntax is obscuring the issue. play.rust-lang.org/…

[Shepmaster]

@JoshLee That's a non-obvious one! The magic keyword you are looking for will be "reborrowing", which is a special property of mutable references.

[MaddTheSane]

@Shepmaster So now I know why doc.rust-lang.org/std/iter/… writes IntoIterator::into_iter(values) instead of values.into_iter().

[don bright]

"often the behaviour is not well-defined, and removal of the item can interfere with the iteration, compromising its correctness." very well said. the bugs caused by this type of thing are extremely bizarre, have spent a few dozen hours tracking them down before in C++. especially inside nested loops. thanks.

[vasilakisfil]

how can I use retain when the predicate for retaining or not needs await (calls an async fn) ?

[Shepmaster]

@vasilakisfil you can't, easily. The brute force answer is to spin up an executor for each predicate (How do I synchronously return a value calculated in an asynchronous Future in stable Rust?). That's probably a non-performant idea. I'd instead maybe try converting the hashmap to an iterator, then to a stream, then filter the stream using StreamExt then convert it back to a hashmap. Benchmarking would be important.