Rust BTreeMap becomes invalid when key is mutated

In the BTreeMap values are sorted with the Ord trait. However, a key can change one of its attributes considered in the Ord trait implementation as shown in the example. This can lead to the BTreeMap containing values that can no longer be reached with the corresponding key because they are in the wrong place. Is it possible to work around this somehow and have such a value automatically moved to the right place when it is changed or is there perhaps another data structure that avoids the problem?

fn main() {
  use std::collections::BTreeMap;
  use std::cell::RefCell;

  #[derive(Ord, PartialOrd, PartialEq ,Eq, Debug)]
  struct Key {
    value: RefCell<usize>
  }
  impl Key {
    pub fn new(x: usize) -> Self {
      Self {
        value: RefCell::new(x)
      }
    }
  }

  //create a tree(bool value does not have any specific purpose)

  let mut a = BTreeMap::new();
  a.insert(Key::new(3), false);
  a.insert(Key::new(2), false);
  a.insert(Key::new(4), false);
  a.insert(Key::new(5), false);

  //tree looks like this:
  //        3
  //       / \
  //      2   4
  //           \
  //            5


  *a.get_key_value(&Key::new(5)).unwrap().0.value.borrow_mut() = 1;

  //mutated invalid tree:
  //        3
  //       / \
  //      2   4
  //           \
  //            1

  for x in a.keys() {
    println!("{:?}", x);
  }
  
  println!("{:?}", a.get(&Key::new(1)))
}

output:

Key { value: RefCell { value: 2 } }
Key { value: RefCell { value: 3 } }
Key { value: RefCell { value: 4 } }
Key { value: RefCell { value: 1 } }
None

As you can see here, the value 1 exists as a key in the BTreeMap, but cannot be found.

>Solution :

Rust BTreeMap becomes invalid when key is mutated

This is documented:

It is a logic error for a key to be modified in such a way that the key’s ordering relative to any other key, as determined by the Ord trait, changes while it is in the map.

Is it possible to work around this somehow and prevent such a value from being automatically moved to the right place when it is changed

It’s not moved at all, which is why you’re breaking the map when you do that.

Clippy has a lint which warns about such misuses.

Though it can not be perfect (it has both false positives and false negatives), here if you plug your code in the playground and select Tools > Clippy, you will see:

warning: mutable key type
  --> src/main.rs:19:3
   |
19 |   let mut a = BTreeMap::new();
   |   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^
   |
   = note: `#[warn(clippy::mutable_key_type)]` on by default
   = help: for further information visit https://rust-lang.github.io/rust-clippy/master/index.html#mutable_key_type

or is there perhaps another data structure that avoids the problem?

The map can not be aware that you’re mutating keys (despite being told not to do that). There is literally no way for the language to prevent this, short of only allowing a specific built-in immutable key type.