'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.



Sources

This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.

Source: Stack Overflow

Solution Source