Removing items from a BTreeMap or BTreeSet found through iteration

Question

I would like to remove items from a BTreeMap which have been found through iteration.

As it is not possible to remove items while iterating, I put the items to delete into a vector. The main issue is that it is not possible to use a vector of references, but only a vector of values. All the keys for which the entry has to be removed must then be cloned (assuming the key implements the Clone trait).

For instance, this short sample does not compile:

use std::collections::BTreeMap;

pub fn clean() {
    let mut map = BTreeMap::<String, i32>::new();

    let mut to_delete = Vec::new();

    {
        for (k, v) in map.iter() {
            if *v > 10 {
                to_delete.push(k);
            }
        }
    }

    for k in to_delete.drain(..) {
        map.remove(k);
    }
}

fn main() {}

It generates the following errors when it is compiled:

error[E0502]: cannot borrow `map` as mutable because it is also borrowed as immutable
  --> src/main.rs:17:9
   |
9  |         for (k, v) in map.iter() {
   |                       --- immutable borrow occurs here
...
17 |         map.remove(k);
   |         ^^^ mutable borrow occurs here
18 |     }
19 | }
   | - immutable borrow ends here

Changing to_delete.push(k) with to_delete.push(k.clone()) makes this snippet compile correctly but it is quite costly if each key to delete must be cloned.

Is there a better solution?

Answer 1

TL;DR: you cannot.

As far as the compiler is concerned, the implementation of BTreeMap::remove might do this:

pub fn remove<Q>(&mut self, key: &Q) -> Option<V>
where
    K: Borrow<Q>,
    Q: Ord + ?Sized,
{
    // actual deleting code, which destroys the value in the set
    // now what `value` pointed to is gone and `value` points to invalid memory

    // And now we access that memory, causing undefined behavior
    key.borrow();
}

The compiler thus has to prevent using the reference to the value when the collection will be mutated.

To do this, you'd need something like the hypothetical "cursor" API for collections. This would allow you to iterate over the collection, returning a special type that hold the mutable innards of the collection. This type could give you a reference to check against and then allow you to remove the item.

---

I'd probably look at the problem from a bit different direction. Instead of trying to keep the map, I'd just create a brand new one:

use std::collections::BTreeMap;

pub fn main() {
    let mut map = BTreeMap::new();

    map.insert("thief", 5);
    map.insert("troll", 52);
    map.insert("gnome", 7);

    let map: BTreeMap<_, _> =
        map.into_iter()
        .filter(|&(_, v)| v <= 10)
        .collect();

    println!("{:?}", map); // troll is gone
}

---

If your condition is equality on the field that makes the struct unique (a.k.a is the only field used in PartialEq and Hash), you can implement Borrow for your type and directly grab it / delete it:

use std::collections::BTreeMap;

#[derive(Debug, PartialEq, Eq, PartialOrd, Ord)]
struct Monster(String);

use std::borrow::Borrow;

impl Borrow<str> for Monster {
    fn borrow(&self) -> &str { &self.0 }
}

pub fn main() {
    let mut map = BTreeMap::new();

    map.insert(Monster("thief".into()), 5);
    map.insert(Monster("troll".into()), 52);
    map.insert(Monster("gnome".into()), 7);

    map.remove("troll");

    println!("{:?}", map); // troll is gone
}

See also:

• How to implement HashMap with two keys?
• How to avoid temporary allocations when using a complex key for a HashMap?

Answer 2

As of 1.53.0, there is a BTreeMap.retain method which allows to remove/retain items based on return value of a closure, while iterating:

map.retain(|_, v| *v<=10);