在迭代期间修改对象 [英] Modifying an object during iteration

问题描述

我正在尝试将我在C ++中使用的一些简单数据结构转换为Rust，从区间树开始，但我不明白如何修改我的基础数据结构（这里是 std :: collections :: BTreeSet ）在迭代期间 - 基本上我可以合并重叠的条目。

I'm trying to translate some simple data structures I use in C++ over to Rust, starting with an interval tree, but I don't understand how to modify my underlying data structure (here an std::collections::BTreeSet) during iteration - essentially so I can merge overlapping entries as they appear.

如果我使用标准成语迭代一个集合，我得到以下消息，它是不可变的不能借用 self.storage 作为可变因为它也被借用为不可变的，并且没有出现获得一个我可以看到的可变迭代器的选项...我缺少什么？

If I use the standard idiom for iterating over a collection, I get the following message about it being immutable "cannot borrow self.storage as mutable because it is also borrowed as immutable", and there doesn't appear to be an option to get a mutable iterator that I can see ... what am I missing?

C ++代码：

inline void Insert(const Interval& interval)
{
    auto it = storage.insert(interval);

    // check to see if we overlap the previous element,
    // if we do, start our merge loop from there
    if (it != begin()) {
        const_iterator prev = std::prev(it);

        if (prev->Overlaps(*it)) it = prev;
    }

    while (it != end()) {
        const_iterator nx = std::next(it);

        if (nx != end() && it->Overlaps(*nx)) {
            const Interval u = it->Union(*nx);
            it = storage.erase(it);
            it = storage.erase(it);
            it = storage.insert(it, u);
        } else
            break;
    }
}

Rust代码：

/// Add a new interval into the tree
pub fn insert(&mut self, other: Interval) -> () {
    self.storage.insert(other);

    for int in self.storage.iter() {
        if other <= *int {
            break
        } else if other.overlaps(int) {
            self.storage.remove(&other);
            self.storage.remove(int);
            self.storage.insert(other.union(int).unwrap());
        }
    }
}

推荐答案

当你在迭代它时，你不能改变 BTreeSet –这会使迭代器失效。不幸的是，与C ++不同，Rust没有 insert 或 remove 返回更新迭代器的方法（如果有的话，它们必须是迭代器本身的方法。）

You cannot mutate a BTreeSet while you're iterating on it – that would invalidate the iterator. Unfortunately, unlike C++, Rust doesn't have insert or remove methods that return updated iterators (and if it did, they would have to be methods on the iterator itself).

BTreeSet 不提供可变迭代器，因为您可以做的唯一额外操作是获取对集合中元素的可变引用。但是，这样做可能会破坏集合的排序，因此它不可用。

BTreeSet doesn't offer a mutable iterator, because the only additional operation you could do is obtain a mutable reference to the elements in the set. However, doing this could potentially screw up the set's ordering, so it's not available.

最直接的解决方案是构建迭代期间要执行的操作列表，然后迭代完成后执行它们。但是，对于此算法，这不会很有效，因为您可能需要合并作为上一次合并结果的间隔。因此，一旦找到要合并的一对间隔，就需要跟踪相关值，突破迭代，执行合并，然后重新开始迭代。 BTreeSet 提供 range 方法，允许您迭代集合的值的子集，因此您可能希望使用它而不是 iter ，它总是遍历所有值。但是，从Rust 1.8开始， range 是不稳定的，所以你需要一个夜间编译器才能使用它。

The most straightforward solution is to build a list of operations to perform during the iteration, then perform them once the iteration is complete. However, for this algorithm, this won't quite work, since you might need to merge an interval that is the result of a previous merge. So, once you've found a pair of intervals to merge, you need to keep track of the relevant values, break out of the iteration, perform the merge, then restart the iteration. BTreeSet provides a range method that lets you iterate over a subset of the set's values, so you might want to use that instead of iter, which always iterates over all the values. However, range is unstable as of Rust 1.8, so you'll need a nightly compiler to be able to use it.

这篇关于在迭代期间修改对象的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！