反復中にオブジェクトを変更する

Question

私はCusterで使用する単純なデータ構造を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; 
    } 
} 

錆コード：

/// 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のように不安定ですので、夜間コンパイラを使用する必要があります。