Removing items from a BTreeMap or BTreeSet found through iteration

by

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:

More Related Contents:

  1. Traits and Rust
  2. Why do try!() and ? not compile when used in a function that doesn’t return Option or Result?
  3. Why does linking lifetimes matter only with mutable references?
  4. How do I collect into an array?
  5. Can I do type introspection with trait objects and then downcast it?
  6. Cannot borrow as mutable more than once at a time in one code – but can in another very similar
  7. How can I perform parallel asynchronous HTTP GET requests with reqwest?
  8. Is it considered a bad practice to implement Deref for newtypes?
  9. Implementing a trait for multiple types at once
  10. How do I get an owned value out of a `Box`?
  11. How can I store a Chars iterator in the same struct as the String it is iterating on?
  12. Converting from Option to Option
  13. How to disable unused code warnings in Rust?
  14. Why doesn’t println! work in Rust unit tests?
  15. How do you use parent module imports in Rust?
  16. Why is the `Sized` bound necessary in this trait?
  17. How do I overcome match arms with incompatible types for structs implementing same trait?
  18. Example of how to use Conditional Compilation Macros in Rust
  19. How to take ownership of T from Arc?
  20. Is there any trait that specifies numeric functionality?
  21. Why do I get “type annotations needed” when using Iterator::collect?
  22. Why would I use divergent functions?
  23. When is it necessary to circumvent Rust’s borrow checker?
  24. Expected closure, found a different closure
  25. How can I iterate on an Option?
  26. How does the Rust compiler know `Cell` has internal mutability?
  27. Comparing every element in a vector with the next one
  28. How to repeat a static string at compile time
  29. Is there a good way to convert a Vec to an array?
  30. How to concatenate static strings in Rust

Leave a Comment