2

フェイルファストではない反復子を提供する赤黒木とリンク リストの実装を備えたライブラリを探しています。STL を使用して C++ で行っているのと同じ機能を持ちたいのですが、それは次のとおりです。

  • ツリー/リストへの挿入はイテレータを無効にしません
  • 削除は、削除される要素を指すイテレータのみを無効にします
  • イテレータの「位置」を何らかの方法で保存し、それが指している値を参照することが可能です

この実装は、その一部を使用しながらリスト/ツリーを変更する機能を提供するため、優れています。ここではいくつかの例を示します。

  • リンクされたリスト/赤黒ツリーの隣接要素をO(1)に格納された値に取得する
  • 一括挿入/削除 (位置の増分ごとに 1 つの削除などの制約なし)
  • イテレータの位置を介して O(1) でリンクされたリストを分割する
  • イテレータの位置を保存している場合のより効率的な削除 (たとえば、イテレータをリンクされたリスト内の位置に保持することにより、削除は O(N) ではなく O(1) になります)

また、そのライブラリ/ソース コード/実装に Apache/GPL に適したライセンスがあり、かなり拡張可能であることも望んでいます (上の例のような操作を実装するために独自の変更を加えることができます)。

そのようなライブラリが存在しない場合、これらの 2 つのデータ構造を自分で実装するのに役立つ他のライブラリはありますか?

4

1 に答える 1

0

これらはどちらも自分で実装するのは非常に簡単です。イテレータは次の3つのことを行う必要があります。

  1. 2つの参照のみを保存します。1つは「current」要素への参照で、もう1つは外部コンテナオブジェクト（ルート参照（ツリー）またはヘッド/テール参照（リスト）を保存するblob）への参照です。

  2. 参照される要素が有効かどうかを判断できます（簡単に、親ポインターがnull（ツリー）またはprev / nextポインターがnull（リスト）の場合、これはツリールートまたはリストの先頭/末尾になります）。無効なイテレータで操作が試行された場合は、何かをスローします。

  3. 前/次の要素を見つけることができます。

いくつかの落とし穴があります。リストの場合、java.util.ListIteratorのnextIndex（）とprevIndex（）を効率的にサポートするのは面倒です。もちろん、同時変更を処理するという問題があります。事態が悪化する可能性のある例を次に示します。

while (it.hasNext()) {
    potentially_delete_the_last_element()
    it.next() // oops, may throw NoSuchElementException.
}

これを回避する方法は、リストにnext / prevがあるかどうかを確認してから、実際にnext / prevを取得するまでの間に、リストを変更しないことです。

于 2011-02-06T22:50:36.647 に答える