☰

Java に SortedList がないのはなぜですか? 質問する

tag-icon • tag-icon java sorting collections
Java に SortedList がないのはなぜですか? 質問する

ジャワにはSortedSetそしてSortedMapインターフェース。どちらもJava コレクション フレームワーク要素にアクセスするための並べ替えられた方法を提供します。

しかし、私の理解ではJavaには存在しませんSortedList。java.util.Collections.sort()リストを並べ替えます。

なぜそのように設計されているのかご存知ですか?

ベストアンサー1

リスト反復子は、まず第一に、リストの要素をリストの内部順序 (挿入順序とも呼ばれます) で取得することを保証します。より具体的には、要素を挿入した順序、またはリストを操作した方法に従います。ソートはデータ構造の操作と見なすことができ、リストをソートする方法はいくつかあります。

個人的に便利だと思う順に並べます。

1.代わりにSetまたはBagコレクションの使用を検討する

注:このオプションを一番上に置いたのは、とにかくこれが通常実行したいことだからです。

ソートされたセットは、挿入時にコレクションを自動的にソートします。つまり、コレクションに要素を追加するときにソートが行われます。また、手動でソートする必要もありません。

さらに、重複する要素を気にする必要がない（または重複する要素がない）ことが確実な場合は、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"

比較演算子の使用

明らかな利点の1つは、ComparatorJavaでは、次のようなsort実装も提供しています。ComparatorCollatorこれはロケールに依存した文字列のソートに便利です。次に例を示します。

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

Collections.sort(strings, usCollator);

Java 8以降では、より単純にList#sort。

strings.sort( usCollator ) ;

並行環境でのソート

ただし、このsortメソッドの使用は、コレクションインスタンスが操作されるため、並行環境では使いにくいことに注意してください。代わりに不変コレクションの使用を検討する必要があります。これは、GuavaがOrderingクラスであり、シンプルなワンライナーです。

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

3. リストをまとめるjava.util.PriorityQueue

Javaにはソートされたリストはありませんが、ソートされたキューはあります。これはおそらく同じように機能します。java.util.PriorityQueueクラス。

ニコ・ハース氏はコメント欄にリンクを貼った。関連する質問これもこれに答えます。

ソートされたコレクションでは、内部データ構造を操作することはおそらく望ましくないため、PriorityQueue は List インターフェイスを実装しません (要素に直接アクセスできるため)。

PriorityQueueイテレータに関する注意点

クラスはおよびインターフェースPriorityQueueを実装しているため、通常どおり反復処理できます。ただし、反復子はソートされた順序で要素を返すことが保証されていません。代わりに (Alderath がコメントで指摘しているように)、空になるまでキューを実行する必要があります。Iterable<E>Collection<E>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クラスを作成する

注意:これを実行する必要はありません。

新しい要素を追加するたびにソートする独自の List クラスを作成できます。これは、実装によってはかなり計算量が多くなる可能性があり、演習として実行する場合を除いて無意味です。主な理由が 2 つあります。

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

ただし、練習として実行したい場合は、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。

おすすめ記事