[解決済み] Javaによる配列のソートリスト

質問

これに対する迅速な回答が見つからず、困惑しています。 私は本質的に、Java で java.util.List インターフェイスを実装していますが、ソートされた順序でそのメンバーを保存する Java のデータ構造を探しています。 私は、通常の ArrayList を使用し Collections.sort() を使用していますが、私は時々メンバーを追加し、しばしばリストからメンバーを取り出すというシナリオがあり、新しいメンバーが追加された場合にメンバーを取り出すたびにソートする必要はありません。 JDKまたはサードパーティライブラリに存在するそのようなものに関して、誰かが私を指摘することができますか？

EDIT : データ構造は重複を保持する必要があります。

ANSWERの概要 : 私はこのすべてが非常に興味深く、多くを学びました。 特にAioobeは、私の上記の要件（主に重複をサポートするソートされたjava.util.Listの実装）を達成しようとする彼の忍耐力について言及するに値します。 彼の回答は、私が尋ねたことに対して最も正確であり、私が尋ねたものが私が必要とするものではなかったとしても、私が探していたものの意味合いについて最も示唆に富むものであったと受け止めています。

私が尋ねたことの問題は、リストインターフェイス自体と、インターフェイスのオプションメソッドの概念にあります。 javadoc を引用します。

このインターフェースのユーザーは、各要素がリスト内のどこに挿入されるかを正確に制御することができます。

ソートされたリストへの挿入は、挿入箇所を正確にコントロールできません。 それから、いくつかのメソッドをどのように処理するかを考えなければなりません。 テイク add を例にとってみましょう。

public boolean add(Object o)

 Appends the specified element to the end of this list (optional operation).

あなたは今、以下のどちらかの不快な状況に取り残されています。 1) 契約を破棄し、ソートされたバージョンのaddを実装する。 2) add に要素を追加させ、ソートされた順序を崩す。 3) add を投げ、(オプションとして) UnsupportedOperationException を投げ、ソートされた順序で項目を追加する別のメソッドを実装しています。

選択肢3がベストでしょうが、使えないaddメソッドとインターフェースにない別のsortedAddメソッドがあるのは不潔だと思います。

他の関連する解決策（順不同）。

• java.util.PriorityQueue これは、おそらく私が要求したものよりも、私が必要としていたものに最も近いものです。 キューは、私の場合、オブジェクトのコレクションの最も正確な定義ではありませんが、機能的には私が必要とするすべてを行います。
• net.sourceforge.nite.util.SortedList . しかし、この実装では、ソートを add(Object obj) メソッドでソートを実装し、奇妙なことにそのメソッドが add(int index, Object obj) . 一般的なコンセンサスでは throw new UnsupportedOperationException() はこのシナリオではより良い選択かもしれません。
• グアバのTreeMultiSet 重複をサポートするセットの実装
• ca.odell.glazedlists.SortedListの実装です。 このクラスは、javadocに注意事項が書かれています。 Warning: This class breaks the contract required by List

どのように解決するのですか？

最小限の解決策

ここでは、"minimal" ソリューションを紹介します。

class SortedArrayList<T> extends ArrayList<T> {

    @SuppressWarnings("unchecked")
    public void insertSorted(T value) {
        add(value);
        Comparable<T> cmp = (Comparable<T>) value;
        for (int i = size()-1; i > 0 && cmp.compareTo(get(i-1)) < 0; i--)
            Collections.swap(this, i, i-1);
    }
}

挿入は線形時間で実行されますが、これはとにかくArrayListを使用して得られるものでしょう（挿入された要素の右側にあるすべての要素は、いずれかの方法でシフトされなければならないでしょう）。

比較不可能なものを挿入すると、ClassCastExceptionが発生します。(これは PriorityQueue も同様です。 自然な順序付けに依存する優先度キューは、比較不可能なオブジェクトの挿入も許可しません (そうすると ClassCastException が発生する可能性があります)。 )

オーバーライド List.add

をオーバーライドすることに注意してください。 List.add (または List.addAll など) を使って、要素をソートして挿入することは インターフェース仕様の直接の違反となります。 . あなたが できること を投げるために、このメソッドをオーバーライドすることです。 UnsupportedOperationException .

のドキュメントから List.add :

boolean add(E e)

指定された要素をリストの末尾に追加します（オプションの操作）。

の両方のバージョンで同じ理屈が適用されます。 add の両方のバージョンに当てはまります。 addAll と set . (これらはすべてリストのインターフェースに従ったオプションの操作です)。

いくつかのテスト

SortedArrayList<String> test = new SortedArrayList<String>();

test.insertSorted("ddd");    System.out.println(test);
test.insertSorted("aaa");    System.out.println(test);
test.insertSorted("ccc");    System.out.println(test);
test.insertSorted("bbb");    System.out.println(test);
test.insertSorted("eee");    System.out.println(test);

...プリントします。

[ddd]
[aaa, ddd]
[aaa, ccc, ddd]
[aaa, bbb, ccc, ddd]
[aaa, bbb, ccc, ddd, eee]