rust - 如何修改/部分删除 BTreeMap 中的范围？

Question

我正在尝试从 BTreeMap 构建一个 RangeSet(其中键是下限，值是上限)。只要我只是在查找东西，这就很好用。然而，第一个变异方法让我难住了:

如果我想插入一个范围到我的集合，我需要检查我的BTreeMap的Range从尾部到头部的范围，直到所讨论的值低于插入范围的下限，所有包含的范围都应删除并重叠范围合并。然而，即使使用目前不稳定的.range_mut(..)，我也找不到删除条目的方法(因为 map 仍然被范围借用) .

我是否使用了错误的工具来完成这项工作？我能让它正常工作吗？如果可以，怎么做？我当前的伪代码解决方案(我也使用自己的 Cut 类型，因为 Bound 不是 Ord):

fn insert(&mut self, range: &Range) {
    for entry in self.map.range_mut(Cut::Unbounded, range.upper).rev() {
         if entry.1 < range.lower {
             break;
         } else if entry.0 > range.lower {
             delete entry
         } else {
             merge entry with range
         }
     }
}

Answer 1

您需要分两次执行此操作，收集要删除的键，然后遍历那个列表并调用 remove。

请注意，因为在遍历树时您会获得引用，所以您必须克隆/复制键，因为您将拥有对映射内键的引用，这意味着您不能借用映射作为可变的。

这主要是因为在迭代中间删除条目时，内存和排序语义变得有点不稳定。在遍历树时很难删除树中的条目。由于它是一张 map ，这加剧了这种情况，这意味着键在树中以某种方式排序，这意味着节点可能最终会轮换他们的 child ，所以你可能以前访问过你的左 child ，现在突然那是你的当前节点，或者对的 child 。很难跟踪自己的位置。

此外，B-Tree 节点是子节点的列表，当节点需要合并和拆分时具有动态性，在迭代过程中进行合并和拆分更令人头疼。

部分原因是手动内存语义。键和值存储在节点内，而不是堆上，因此内存将到处跳动，确保它不会失效是非常重要的。尤其是当用户在循环的其他地方收集对树中条目的引用时。

编辑:而且，无论可能性如何，事实是迭代器借用了 Map，这意味着您不能再次借用它来删除内容。如果迭代器返回类似 Entry 的东西，这可能会有所不同，但据我所知，不存在这样做的迭代器。