Изменение объекта во время итерации

Question

Я пытаюсь перевести некоторые простые структуры данных, которые я использую в C++ для Rust, начиная с дерева интервалов, но я не понимаю, как изменить мою базовую структуру данных (здесь std::collections::BTreeSet) во время итерации - по существу, я могу объединить перекрывающиеся записи по мере их появления.

Если я использую стандартную идиому для итерации по коллекции, я получаю следующее сообщение об ее неизменяемости: «не может брать self.storage в качестве изменчивого, потому что он также заимствован как неизменный», и, похоже, нет опции чтобы получить изменчивый итератор, который я вижу ... что мне не хватает?

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

Answer 1

Вы не можете мутировать BTreeSet в то время как вы итерацию на нем – что бы итератор недействительным. К сожалению, в отличие от C++, Rust не имеет методов insert или remove, которые возвращают обновленные итераторы (и если бы это было так, они должны были быть методами самого итератора).

BTreeSet не предлагает изменяемый итератор, так как единственная дополнительная операция, которую вы могли бы сделать, это получить изменяемую ссылку на элементы в наборе. Однако это может привести к зависанию заказа набора, поэтому он недоступен.

Наиболее простым решением является создание списка операций, выполняемых во время итерации, а затем их выполнение после завершения итерации. Однако для этого алгоритма это не будет работать, так как вам может понадобиться объединить интервал, являющийся результатом предыдущего слияния. Итак, как только вы нашли пару интервалов для слияния, вам нужно отслеживать соответствующие значения, выходить из итерации, выполнять слияние, а затем перезапускать итерацию. BTreeSet предоставляет метод range, который позволяет выполнять итерацию по подмножеству значений набора, поэтому вы можете использовать это вместо iter, который всегда выполняет итерацию по всем значениям. Однако range нестабилен по сравнению с Rust 1.8, поэтому вам понадобится ночной компилятор, чтобы использовать его.