当键发生突变时，Rust BTreeMap 变得无效

Question

在 BTreeMap 中，值使用 Ord 特征进行排序。但是，键可以更改 Ord 特征实现中考虑的其中一个属性，如示例所示。这可能导致 BTreeMap 包含无法再使用相应键访问的值，因为它们位于错误的位置。是否有可能以某种方式解决这个问题并在更改时自动将这样的值移动到正确的位置，或者是否有另一种数据结构可以避免该问题？

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)))
}

输出：

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

正如你在这里所看到的，值 1 作为键存在于 BTreeMap 中，但无法找到。

Answer 1

Rust BTreeMap becomes invalid when key is mutated

记录在案：

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

它根本没有移动，这就是为什么你这样做会破坏地图。

Clippy has a lint which warns about such misuses.

虽然它不能完美（它既有误报也有漏报），在这里如果你plug your code in the playground和select工具> Clippy，你会看到：

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?

地图无法知道您正在改变键（尽管被告知不要那样做）。除了只允许特定的 built-in 不可变键类型之外，语言几乎没有办法阻止这种情况。

当键发生突变时，Rust BTreeMap 变得无效

Rust BTreeMap becomes invalid when key is mutated

binary-tree

rust

data-structures