ChainMap

chainmap

此库提供了一个带有内部可变性的HashMap链。HashMap是引用计数的，因此可以创建一个HashMap层的树，而不仅仅是单个链。

树中的更高映射（靠近叶子）具有更高的优先级。

一个可能的用例是用于嵌套作用域的管理。

来自书籍相应部分的示例：15.作用域规则 - RAII

fn create_box() {
    // CreateBoxScope
    let _box1 = Box::new(3i32);
}

fn main() {
    // MainScope
    let _box2 = Box::new(5i32);
    {
        // NestedScope
        let box3 = Box::new(4i32);
    }

    for i in 0u32..1_000 {
        // LoopScope<i>
        create_box();
    }
}

可以表示为

MainScope["_box2" => 5i32]
    ├── NestedScope["_box3" => 4i32]
    ├── LoopScope0[]
    │       └── CreateBoxScope["_box1" => 3i32]
    ├── LoopScope1[]
    │       └── CreateBoxScope["_box1" => 3i32]
    │   ...
    └── LoopScope999[]
            └── CreateBoxScope["_box1" => 3i32]

其中每个 [ $( $key => $value ),* ] 是基于前一个构建的 ChainMap 树的一个级别。

然后可以声明为

let mut main_scope = ChainMap::new();
main_scope.insert("_box2", 5i32);

let mut nested_scope = main_scope.extend();
nested_scope.insert("_box1", 5i32);

let mut loop_scope = Vec::new();
for _ in 0..1000 {
    let mut h = HashMap::new();
    h.insert("_box1", 3i32);
    loop_scope.push(main_scope.extend().extend_with(h));
}

从 ChainMap 树的某个级别访问映射条目的规则与相应作用域的规则完全相同。

问题

为什么还需要另一个链表映射？

已经有链表映射了

chain-map

hash-chain

然而，这两个链表映射的实现都不允许从单个根节点有多个分支，因为它们是围绕一个 Vec<HashMap<K, V>> 的包装器。

另一方面，这个crate允许从公共根中分叉出几个映射，以牺牲不太友好的内部表示形式为代价来节省内存使用：一个Vec<HashMap<K, V>>比一棵Option<Rc<(Mutex<HashMap<K, V>, Self)>>的树更容易处理。

为什么在存在内部可变性的情况下，还要在所有地方都要求mut呢？

《ChainMap》完全可以像要求&mut self一样，在所有地方都使用&self，它仍然可以正常工作。毕竟，即使其容器不可变，`Mutex`的内容也可以更改。

不要求所有方法都接受&self有两个原因

1. 尽管存在内部可变性，但在非mut结构中insert会感觉很不寻常。

   HashMap需要mut来insert，我希望ChainMap尽可能像HashMap，因此选择了相同的方法名称insert和get。

2. fork和fork_with方法确实需要&mut self，而且没有（安全的）方法可以绕过这一点。

   fork被声明为

   pub fn fork(&mut self) -> Self {
       let newlevel = self.extend();
       let oldlevel = self.extend_fallthrough();
       std::mem::replace(&mut *self, oldlevel);
       newlevel
   }
   

   当使用时

   let ch = ChainMap::new();
   let _ = ch.fork();
   

   ch0在调用fork前后不是同一个对象！

   之前在ch中包含的对象已经被移除，现在除了隐式地从其子对象中读取之外，没有其他方式可以访问原来的ch。

   也无法在其中插入新的键。