Modifying an object during iteration [duplicate]

Question

This question already has an answer here:

• How to modify/partially remove a range from a BTreeMap? 1 answer

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.

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++ code:

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 code:

/// 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());
        }
    }
}

Answer 1

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 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.

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.