[解決済み] なぜJavaにはSortedListがないのですか？

質問

Javaでは SortedSet と SortedMap というインターフェイスがあります。どちらも Java Collections フレームワーク で、要素にアクセスするためのソートされた方法を提供します。

しかし、私の理解では SortedList をJavaで作成します。使用できるのは java.util.Collections.sort() でリストを並べ替えることができます。

なぜそのようなデザインになっているのか、何か思い当たることはありますか？

解決方法は？

リストのイテレータは、何よりもまず、リストの要素をリストの内部順序で取得することを保証します（別名. 挿入順 ). 具体的には、要素を挿入した順、あるいはリストをどのように操作したかによります。ソートはデータ構造の操作とみなすことができ、リストのソートにはいくつかの方法があります。

の順に方法を並べることにします。 有用性 個人的に見た場合

1. の使用を検討する。 Set または Bag コレクションに置き換えます。

NOTE このオプションを一番上に置いたのは、とにかく普通はこうしたいからです。

ソートされたセット 挿入時に自動的にコレクションをソートする つまり、コレクションに要素を追加している間に並べ替えが行われます。また、手動でソートする必要がないことも意味しています。

さらに、要素の重複を気にする必要がない（あるいはある）ことが確実な場合には TreeSet<T> 代わりに これは SortedSet と NavigableSet というインターフェイスを持ち、リストで期待されるような動作をします。

TreeSet<String> set = new TreeSet<String>();
set.add("lol");
set.add("cat");
// automatically sorts natural order when adding

for (String s : set) {
    System.out.println(s);
}
// Prints out "cat" and "lol"

もし自然な並び順を望まない場合は、コンストラクタのパラメータに Comparator<T> .

または マルチセット (として知られている）。 バッグ ) というのは Set は、代わりに要素の重複を許容するもので、サードパーティによる実装もあります。最も顕著なのは グアバライブラリ があります。 TreeMultiset と同じように動作します。 TreeSet .

2. でリストをソートします。 Collections.sort()

前述したように、ソートの List は、データ構造の操作になります。したがって、さまざまな方法でソートされる1つの真実のソースが必要な場合は、手動でソートするのがよいでしょう。

でリストをソートすることができます。 java.util.Collections.sort() メソッドを使用します。以下は、そのコード例です。

List<String> strings = new ArrayList<String>()
strings.add("lol");
strings.add("cat");

Collections.sort(strings);
for (String s : strings) {
    System.out.println(s);
}
// Prints out "cat" and "lol"

コンパレータの使用

明確な利点は Comparator の中に sort メソッドを使用します。また、Java では、このメソッドに対応するいくつかの実装が用意されています。 Comparator のような Collator これは、ロケールを考慮したソート文字列に有効です。以下はその一例である。

Collator usCollator = Collator.getInstance(Locale.US);
usCollator.setStrength(Collator.PRIMARY); // ignores casing

Collections.sort(strings, usCollator);

同時並行環境での並べ替え

ただし sort なぜなら、コレクションのインスタンスが操作されるからです。そして、代わりに不変のコレクションを使用することを考慮すべきです。これは、Guavaが Ordering クラスで、シンプルなワンライナーです。

List<string> sorted = Ordering.natural().sortedCopy(strings);

3. リストを java.util.PriorityQueue

Javaにはソートされたリストはありませんが、ソートされたキューがあり、おそらくあなたにとって同様に機能するでしょう。それは java.util.PriorityQueue クラスがあります。

Nico Haaseがコメントでリンクしているのは 関連質問 にも答えています。

ソートされたコレクションで を操作したいとは思わないでしょう。 PriorityQueue が List インターフェイスを実装しないのは、その要素に直接アクセスできるようになるためです。

の注意点 PriorityQueue イテレータ

は PriorityQueue クラスは Iterable<E> と Collection<E> インターフェイスを持つので、通常通り反復処理することができます。しかし、イテレータはソートされた順番に要素を返すことを保証していない。その代わり（Alderathがコメントで指摘しているように）、次のようなことが必要です。 poll() を空にするまで待ち行列に入れます。

なお、リストを優先キューに変換する場合は コンストラクタは、任意のコレクション :

List<String> strings = new ArrayList<String>()
strings.add("lol");
strings.add("cat");

PriorityQueue<String> sortedStrings = new PriorityQueue(strings);
while(!sortedStrings.isEmpty()) {
    System.out.println(sortedStrings.poll());
}
// Prints out "cat" and "lol"

4. 自分で書く SortedList クラス

NOTE こんなことしちゃダメだよ。

新しい要素を追加するたびにソートする独自の List クラスを書くことができます。これは、実装によってはかなり計算が重くなります。 であり、無意味である というのも、主に2つの理由があるからです。

1. という契約を破ることになります。 List<E> インターフェイスが持つ add メソッドは、ユーザーが指定したインデックスに要素が存在することを保証する必要があります。
2. なぜ車輪の再発明をするのか？上記の最初のポイントで指摘したように、代わりにTreeSetまたはMultisetsを使用すべきです。

しかし、練習としてやってみたいということであれば、以下のコードサンプルを参考にしてください。 AbstractList 抽象クラスです。

public class SortedList<E> extends AbstractList<E> {

    private ArrayList<E> internalList = new ArrayList<E>();

    // Note that add(E e) in AbstractList is calling this one
    @Override 
    public void add(int position, E e) {
        internalList.add(e);
        Collections.sort(internalList, null);
    }

    @Override
    public E get(int i) {
        return internalList.get(i);
    }

    @Override
    public int size() {
        return internalList.size();
    }

}

必要なメソッドをオーバーライドしていない場合、デフォルトの実装は AbstractList を投げます。 UnsupportedOperationException s.