如何修改/部分删除 BTreeMap 中的范围?

问题描述

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

I'm trying to build a RangeSet out of a BTreeMap (where the keys are lower bounds and the values are upper bounds). This works quite well as long as I'm only looking up stuff. However, the first mutating method has me stumped:

如果我想插入一个范围到我的集合中，我需要从我的BTreeMap的上限检查一个Range从尾部到头部的范围，直到有问题的值低于插入范围的下限，所有包含的范围应该删除和重叠范围合并.但是，即使使用当前不稳定的 .range_mut(..)，我也找不到删除条目的方法(因为地图仍然被范围借用).

If I want to insert a range to my set, I need to check a Range of my BTreeMap from the upper bound of the range from tail to head until the value in question is below the inserted range's lower bound, all contained ranges should be removed and overlapping ranges merged. However, even using .range_mut(..) which is currently unstable, I cannot find a way to delete an entry (because the map is still borrowed from by the range).

我是否使用了错误的工具来完成这项工作?无论如何，我可以让它发挥作用吗——如果可以，怎么做?我目前的伪代码解决方案(我也使用自己的 Cut 类型，因为 Bound 不是 Ord):

Am I using the wrong tool for the job? Can I make it work anyway – and if so, how? My current solution in pseudocode (I also use my own Cut type because Bounds are not 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
         }
     }
}

推荐答案

你需要分两次完成，收集你要删除的键，然后遍历那个列表并调用remove.

You need to do this in two passes, collecting the keys you want to delete, and then iterate over that list and call remove.

请注意，由于在遍历树时会获得引用，因此您必须克隆/复制键，因为您将引用映射中的键，这意味着您不能将映射借用为可变的.

Note that since while iterating over a tree you get references, you'll have to clone/copy the key because you'll have a reference to a key inside the map, which means you cannot borrow the map as mutable.

这样做的原因主要是因为在迭代过程中删除条目时内存和排序语义变得有点不稳定.在遍历树时删除树中的条目非常困难.由于它是一个映射，这意味着键在树中以某种方式排序，这意味着节点可能最终会旋转它们的子节点，所以你可能之前访问过你的左子节点，现在突然这是你的当前节点，或者对的孩子.很难跟踪自己的位置.

The reason for this is largely because the memory and ordering semantics get a bit wonky while deleting entries in the middle of an iteration. It's pretty difficult to delete entries in a tree while iterating over it. This is exacerbated by it being a map, which means the keys are ordered in some way in the tree, meaning that nodes may end up rotating their children, so you may have previously visited your left child and now suddenly that's your current node, or right child. It's difficult to keep track of where you are.

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

In addition, B-Tree nodes are lists of subnodes that have dynamics for when nodes need to merge and split, it's even more of a headache to do that in the middle of an iteration.

部分原因是手动内存语义.键和值存储在节点中，而不是在堆上，因此内存将在整个地方弹跳并确保它没有失效是非常重要的.特别是如果用户正在收集对循环中其他位置的树中条目的引用.

Some of this is due to manual memory semanics. The keys and values are stored within the nodes, not on the heap, so memory is going to be bouncing all over the place and making sure it's not invalidated is non-trivial. Especially if the user was collecting references to entries in the tree elsewhere in the loop.

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

And, regardless of possibility, the fact of the matter is that an iterator borrows the Map, which means you can't borrow it again to delete things. This might be different if the iterator returned something like an Entry, but as far as I know no iterator that does this exists.

这篇关于如何修改/部分删除 BTreeMap 中的范围?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！