Java は Collections.sort があるのに .NET は List
自身が Sort メソッドを持っているのはなぜ？

.NETではデータ構造アルゴリズムに合わせた効率的なソートアルゴリズム/実装を選択しやすいことを重視したのでは？(インタフェース上の話です。実装は知りません)

例えば、配列を利用したListでは(不安定で構わないならば)クイックソートが向いているでしょうし、連結リストを利用したListではマージソートが向くはずです。また、Javaの場合はCollections.sort()でリストの中身を配列に変換してからソートして書き戻すので無駄が多いです。

あしゅさん

.NETではデータ構造アルゴリズムに合わせた効率的なソートアルゴリズム/実装を選択しやすいことを重視したのでは？(インタフェース上の話です。実装は知りません)

なるほど、効率の面からということですね。リストの内部構造を良く知っている List 自身に Sort を任せるのは、たしかに一理あると思います。ただし、私はつぎの2つの点から、そこまで効率を重視する必要があるのか、という疑問が残ります。

まずひとつの点として、ソートはよほど特殊なソートアルゴリズムを使わない限り、基本的には2つの要素(や要素のレンジ)の swap を繰り返すことで実装します。リストの内部構造を知っていたからといって、swap がそれほど効率化できるかということが疑問です。逆に、swap のコストが高いリストの内部構造だと、どうせ配列などにコピーしてからソートしてそれをリストに戻すようなことをするわけで、それならそういう配列へのコピーは呼び元でやればよいことであり、List のメソッドの中でやらなくても良いような気がします。

もうひとつの点としては、ソートはたくさんあるデーター処理のひとつにすぎず、List に Sort メソッドを備えるならば、ほかにも最大値(Max)や逆順の並び替え(Reverse)や検索(Find/Search)なども備えるべきのような気がします。ソートだけが特別扱いというのもなんとなく違和感があります。

と、ここまで書いた後で List クラスのメソッド定義を見てみたら、Reverse や BinarySearch などのメソッドは持っていました。なるほど、持たせられるメソッドはあらかた持たせようという設計思想なのかもしれません。Sort に限らずこれらのメソッドも、List 自身が持っていれば処理の効率化ができる可能性は出てきます。(List 自身が持っていなければ絶対に不可能、だけど持っているからそうではない、という意味です。)

> C#(.NET)を使っていて、疑問に思ったのですが、なぜ List クラスは
> インスタンスのメンバーと> して Sort メソッドを持っているのでしょうか？

逆に質問ですが、JavaではなぜListクラスではなく、
CollectionsクラスにSortメソッドがあるのでしょう？
あるオブジェクトが持っている属性に対する操作をしたいはずなのに、
なぜ他のオブジェクトにやらせるのでしょうか？
・・・という逆の視点を持ってみると何か見えてくるかもしれません。

どちらが合理的かは一概に判断できません。
設計思想の違い、何を重視するかの違い、歴史的な背景の違い、
複合的な要因によってそうなったのでしょう。

設計者ではないので想像ですが、
一番の理由は(アプリケーションを開発する側の人の)ユーザビリティじゃないでしょうか。

■ListがSortメソッドを持つ場合。
◇Sortメソッドに辿り着くにはどんな段取りを踏むか。
　★アプローチ1
　　・List<T> list = new List<T>()でインスタンスを作成するコードを書く。
　　・list.と打ってインテリセンスに表示されるメンバを眺める。
　　・Sortメソッドを見つけて使う。

　★アプローチ2
　　・Sortをしたいので、List<T>のメンバをヘルプで調べる。
　　・List<T>のヘルプでSortメソッドを見つける。

◇Sortメソッドを使用するコードはどんな感じになるか。
　★コードのイメージ → 1つのクラスで完結する。
　　List<T> list = new List<T>();
　　listをいろいろ設定。
　　list.Sort();

■ListがSortメソッドを持たない場合。
◇Sortメソッドに辿り着くにはどんな段取りを踏むか。
　★アプローチ1
　　・List<T> list = new List<T>()でインスタンスを作成するコードを書く。
　 (・list.と打ってインテリセンスに表示されるメンバを眺める。)
　　・Sortメソッドを見つかりません。この場合に以下のような行動が考えられる。
　　　case1)さらっとヘルプなどを調べてみて、見つけれらなかったので自前でソートする。
　　　case2)ソートしなくてよいアプローチを探す。(要件を曲げる)
　　　case3)ヘルプなどをきちんと調べた結果、Collections.Sortを見つる。

◇Sortメソッドを使用するコードはどんな感じになるか。
　★コードのイメージ → 2つのクラスで完結する。
　　List<T> list = new List<T>();
　　listをいろいろ設定。
　　Collections.Sort(list);

他にもあるかもしれませんが、思いつくそれぞれのメリットをまとめると
以下のような感じになるかなと思います。(デメリットはその逆)

■ListにSortメソッド
・開発者がSortメソッドにすぐに辿りつける
・使用クラスは1つで済む(複雑度の軽減)
・各クラスが内部知識＆内部データを使ってソートできるためパフォーマンス上の無駄がない

■別クラスにSortメソッド
・Sortメソッドを1箇所の記述で済ませられる(ライブラリ作成者的に無駄がない)

先の私の投稿No3.に補足。

> ■別クラスにSortメソッド
> ・Sortメソッドを1箇所の記述で済ませられる(ライブラリ作成者的に無駄がない)
・Listクラス側がシンプルになる

1点漏れてましたm(_ _)m

補足ついでに、私が「ユーザビリティ」が理由じゃないか？と挙げた理由は、
以下の書籍です。List<T>について特に書いていたわけではないですが、
.NET Frameworkの設計者たちが何を考え、何に悩み、どんな指針で設計したのかが書かれた一冊です。(翻訳が残念な感じですが、実際の設計者のコメントが多数掲載されているので参考になりました)

.NETのクラスライブラリ設計 開発チーム直伝の設計原則、コーディング標準、パターン

重要な違いとして、.NETのListはジェネリックな具象クラスであるのに対して、javaのListはインタフェースであるということがあります。
インタフェースには具体的な実装を伴ったソートメソッドを作成することはできないので、Listにソートメソッドを持たせたければ、インタフェースにメソッドの定義を宣言し、その実装をAbstractListで与えることになります。たとえば、List.indexOfはそのように提供されています。

この方法（インタフェースでメソッドを定義する方法）には一つ制限があります。
つまり、「一度広く公開されたインタフェースにはメソッドの追加はできない」ということです（追加すれば多数のプログラムのコンパイルができなくなる）。
そのため、Javaの場合は、ごく基本的な操作（indexOfやisEmptyなど）以外はCollectionsクラスに分離して提供しているのだと考えられます。

sawat

よねＫＥＮさん

逆に質問ですが、JavaではなぜListクラスではなく、
CollectionsクラスにSortメソッドがあるのでしょう？
あるオブジェクトが持っている属性に対する操作をしたいはずなのに、
なぜ他のオブジェクトにやらせるのでしょうか？
・・・という逆の視点を持ってみると何か見えてくるかもしれません。

Java になぜ Collections.sort があるかというと、昔はこの方式が普通だったからかな、と思います。たとえば、私は使ったことはありませんが、C++ でも STL の sort も Java 方式だと思います。
Java や C++ より新しい .NET(C#) だと、前述したように、機能を自身のメソッドに持たせる傾向が強いような感じがします。これは List 以外の他のクラスを見てもそう感じます。

「なぜ他のオブジェクトにやらせるのか・やらせないのか」という観点で言えば、List 自身のオブジェクトがやる必要性が薄い処理だから、すなわち、他のオブジェクトにやらせても良い処理だからだと考えます。List が要素単位の setter/getter を持っている以上、ソート処理はその setter/getter を介して swap 処理を外部でおこなえば実現できます。(もしも List が setter/getter を持たず、カプセル化していれば別ですが、そうはなっていません。)

コーディング時の利便性については、たしかに私も、あまり良く知らないクラスを使うときにはインスタンス変数名をキーボードで打ち込んでから、ピリオドを押して、どんなメンバーが使えるかを見たりします。ただ、これだけのためにメソッドを備えるというのは、やりすぎのような気がします。

折衷案として思い付いたのですが、たとえば、

public class List<T> : ～
{
[Obsolete("ソートしたいときは Collections.Sort(List<T>) を使ってください。")]
public void Sort();

のようになっていれば、
「List に Sort メソッドを付けても良かったんだけど、代わりにCollections クラスを使ってください。」
ということをライブラリー使用者に伝えることもできると思います。

List.Sort() メソッドを用意してそれに ObsoleteAttribute をつけるような手間をかけられるなら、同じ手間で static Array.Sort() を呼んであげるように List.Sort() を実装できると思います。
で、実際そうなっているのが .NET Framework なのではないかな…と。

sawatさん

そのため、Javaの場合は、ごく基本的な操作（indexOfやisEmptyなど）以外はCollectionsクラスに分離して提供しているのだと考えられます。

そういえば、.NET にも IList インターフェースがあり、これは Java の List と同程度の簡素さですね。

.NET の List クラスは IList を実装したクラスですが、ふと思ったのですが、これはもはや基礎的なクラスという位置づけではなく、アプリケーションに近いクラスと考えたほうが良いのかもしれません。.NET の List クラスは、典型的なアプリケーションで使う際に便利なように、十徳ナイフのように機能満載のリストとして提供されているものであり、これにシンプルさを求めるのは違うのかな、とも思えてきました。

でも、もしそうだとしたら IList を引数とした Collections.sort のようなものは標準で用意してほしいと思います。今現在、IList を実装したリストクラスを自前で作って、それをソートしたい場合は、ソートのアルゴリズムを自分で作るしかないのでしょうか。Array.Sort というクラスとメソッドは存在しますが、これは配列を対象としたものであり、かならず配列にコピーしないと使えないですよね。

rainさん

List.Sort() メソッドを用意してそれに ObsoleteAttribute をつけるような手間をかけられるなら、同じ手間で static Array.Sort() を呼んであげるように List.Sort() を実装できると思います。

私は、メソッドを増やすと、シンプルさが失われて拡張性に影響するのではないかと思っています。また、Array.Sort を使うと、上述のように配列へのコピーが必要なので、必要とするメモリー量が2倍になります。(もっとも、たかだか2倍ですが。)
たとえば、私は Java の List インターフェースを実装したリストクラスを自分で作ることならば、容易にできます。しかし .NET の List クラスと同等のものを自分で作ることは、それの何倍も難しいと感じます。

やはり、.NET の List クラスは、もう出来上がってしまったアプリケーションレベルのクラスだと捉えたほうが良いのでしょうかね。

>でも、もしそうだとしたら IList を引数とした Collections.sort のようなものは標準で用意してほしいと思います。

System.Linq.Enumerable.OrderBy() じゃダメなんですか？

# IList じゃなくて IEnumerable を受け取りますが、むしろその方がより汎用的だと思います。

.NET の List クラスは IList を実装したクラスですが、ふと思ったのですが、
これはもはや基礎的なクラスという位置づけではなく、
アプリケーションに近いクラスと考えたほうが良いのかもしれません。.

unibonさんのおっしゃる「基礎的なクラス」というのが
派生元になるクラスという意味なら、List<T>はそういうためのクラスではありません。
List<T>はアプリケーション内部で使用することを目的とした具象クラスで、
ばりばりにアプリケーションで使うためのクラスです。

ちなみにList<T>は、
・継承元として使用することは推奨されていません。
・publicなクラスの戻り値やパラメータとしての使用も推奨されていません。

でも、もしそうだとしたら IList を引数とした Collections.sort のようなものは標準で用意してほしいと思います。
今現在、IList を実装したリストクラスを自前で作って、それをソートしたい場合は、
ソートのアルゴリズムを自分で作るしかないのでしょうか。Array.Sort というクラスとメソッドは存在しますが、
これは配列を対象としたものであり、かならず配列にコピーしないと使えないですよね。

unibonさんがCollections.Sortのやり方に拘る理由が正直よくわからなかったのですが、
自前でコレクションクラスを実装する場合に、
Sortメソッドを自前で用意しないといけないの？というところに端を発していたのですね。

そもそも自前のコレクションクラスを作る必要があるのでしょうか？
あるとして、それはSortの機能が必要なのでしょうか？
たいていのことはList<T>で事足ります。また、独自にコレクションクラスを実装するなら、
内部データ保管用に配列やList<T>を使うのではないでしょうか。
その場合、Sortメソッドは内部の配列やList<T>に委譲すればいいと思います。

しかし .NET の List クラスと同等のものを自分で作ることは、それの何倍も難しいと感じます。

.NETの場合、コレクションクラスを実装する場合、派生元として、
Collection<T>、ReadOnlyCollection<T>の使用が推奨されています。
この推奨事項に従う場合、これらにはSort機能がないので自前で実装が必要になります。
(System.Linq.Enumerable.OrderBy()を使えない/使いたくない場合)

Sort機能を用意したいなら、先にも書いた通り、
内部実装としてList<T>を使えば簡単に実装できます。
この場合は、作成する独自コレクションクラスで必要に応じて
IList<T>、ICollection<T>を実装することになるので少しだけ面倒ですが、
機械的な作業なので自動生成するのも手です。

渋木宏明(ひどり)さん

System.Linq.Enumerable.OrderBy() じゃダメなんですか？

# IList じゃなくて IEnumerable を受け取りますが、むしろその方がより汎用的だと思います。

ありがとうございます。このメソッドの存在は知りませんでした。
(これは、
http://msdn.microsoft.com/ja-jp/library/system.linq.enumerable.orderby.aspx
ですよね。)

私は LINQ はぜんぜん使ったことがないのすが、このメソッドが引数として IEnumerable を受け取るということは、インデックスを指定して直接要素にアクセスはできないと思うので、メソッド内部で一旦配列などにコピーをして、その配列上でソートをおこなっているのだろうと推測します。したがって Array.Sort と同様にメモリーを2倍使うことになると思います。(たかだか2倍なのですが、一般にソート関連の話ではコピーを作るか作らないかに関心があることが多いので、私もこの点をある程度気にします。)

よねＫＥＮさん

ちなみにList<T>は、
・継承元として使用することは推奨されていません。
・publicなクラスの戻り値やパラメータとしての使用も推奨されていません。

今までこれは意識していませんでした。自分で作ったプログラムでは、継承は使っていませんが、戻り値やパラメーターには使っていました。まずはこれを IList<T> に変更してみます。
なお私の言う「基礎的なクラス」とは、漠然とした低レベル(低層)なもの、という意味です。(継承元という意味も含んでないわけではありません。)

よねＫＥＮさん

unibonさんがCollections.Sortのやり方に拘る理由が正直よくわからなかったのですが、
自前でコレクションクラスを実装する場合に、
Sortメソッドを自前で用意しないといけないの？というところに端を発していたのですね。

そうですね。そういう疑問だと思います。
Java だと ArrayList と Collections.sort が List インターフェースという分界点で疎に結合しています。したがって自前で ArrayList の代替クラスを作ったり、Collections.sort の代替クラスを作ることが、それぞれ独立しておこなえます。これは拡張性に優れた設計だと私は考えます。
一方、.NET だと List クラスとその sort メソッドが密に結合していて、自分で 作ろうとするとリストの機能とソートの機能をまとめて面倒見ないといけなくなり、考えなければならない範囲が増えて複雑だと感じます。

「自前のコレクションクラス」を作る必要があるか、という点については、たいていのアプリケーションをコーディングする際は、それほど必要はないと思います(必要性はまた別途考えてみたいと思います)。コレクションクラスの設計思想を知るための例題という意味合いも大きいです。先日ご紹介いただいた書籍はすぐには読めませんが、後日機会があればぜひ読みたいと思います。
(ちなみにソートのアルゴリズム自体ならば、私は理解しています。たとえば自前でソートのコードを書くとしても、さほど困難ではなく、数十行程度で書けるものだということも知っています。)

>したがって Array.Sort と同様にメモリーを2倍使うことになると思います。(たかだか2倍なのですが、一般にソート関連の話ではコピーを作るか作らないかに関心があることが多いので、私もこの点をある程度気にします。)

結果セットを返すためにメモリが消費されるのは確かですが、ソート対象が参照型のコレクションである場合、コレクションの要素の分も含めた「まるまる２倍」のメモリが消費されるわけではありません。

コレクションのすべての要素の参照を納めるの必要なメモリ（＋α）だけが使用されます。

ソート対象のコレクションはそのままの状態で保持したまま、別途ソート済みの結果セットを得たい場合もあるので、Enumerable.OrderBy() にも十分に利用価値はあると思いますよ。

>一方、.NET だと List クラスとその sort メソッドが密に結合していて、自分で 作ろうとするとリストの機能とソートの機能をまとめて面倒見ないといけなくなり、考えなければならない範囲が増えて複雑だと感じます。

懸案自体は至極当然のことと思いますが、出発点が少しズレています。

.NET では、「T 型の要素を格納するリスト（＝インデックスによって個別にアクセスできるオブジェクトのコレクション）」の定義は IList<T> で与えられます。

ですが、IList<T> は Sort() を含んでいません。

標準ライブラリに含まれているとはいえ、List<T> はあくまで「IList<T> の典型的な１実装」でしかありません。

そのため、List<T> の設計者は、おそらくは利用者の利便性を考えて（そして LINQ 登場前の実装であるため）、List<T> に Sort() メソッドを実装したのだろうと思います。

また、既にコメントがついていますが、.NET では、コレクションの基底クラスとしては Collection<T> や ReadOnlyCollection<T> の使用が推奨されています。

これらのクラスは ICollection<T> や IList<T> の基本実装であり、Sort() メソッドを備えていません。

なので、これらのクラスを出発点として独自コレクションの実装を考えれば、Sort() の実装については、それが本当に必要となるまで考える必要はありません。

渋木宏明(ひどり)さん

また、既にコメントがついていますが、.NET では、コレクションの基底クラスとしては Collection<T> や ReadOnlyCollection<T> の使用が推奨されています。

今、試しに、自分が今作っているプログラムの List 型の変数を IList や ICollection の型に代えようとしているのですが、つぎの疑問が出てきました。List は IList に代えれば良いのですが、HashSet をなにに代えれば良いのかが分かりません。

たとえば、

というコードの
HashSet<string> x = new HashSet<string>();
を
ICollection<string> x = new HashSet<string>();
に代えると、Add メソッドの戻り値の型が HashSet は bool なのに ICollection は void なので、コンパイルが通らなくなります。かといって ISet というインターフェースなどは存在しないようです。
すなわち、HashSet のインスタンスを「セット」という特徴を持ったまま使おうとすると、変数は HashSet のままにしなければならないようです。一方、「リスト」は Sort などの機能を使わず、インデックスでアクセスするという機能を使うだけの場合は IList が使えます。

しかし、HashSet は HashSet のままで、List は IList にしたほうが良い、というのはなんだか違和感があります。IList にせずに List のまま使ったほうが良いのではないか、すなわち、.NET のコレクションフレームワークというものは、やはりあまり練られたものではないのではないか、という懸念を抱いてしまいます。どなたか私のこの懸念を払しょくしてください。

>自分が今作っているプログラムの List 型の変数を IList や ICollection の型に代えようとしているのですが

すみません、僕や他の方のこれまでの発言と、そのようなコード変更がどこでどーつながるのか、僕には理解できませんでした。

>.NET では、「T 型の要素を格納するリスト（＝インデックスによって個別にアクセスできるオブジェクトのコレクション）」の定義は IList<T> で与えられます。

は、「T 型の要素を格納するリストの定義」がナニによって与えられているのか、を説明しただけです。

「List<T> の参照は IList<T> 型の変数で受け取るものだ」という意味は含まれていません。

List<T> の参照を IList<T> で受け取ったら、IList<T> に含まれていない、List<T> 固有の実装を（無意味にキャストでも使わない限り）利用することが出来ません。

HaseSet<T> についても同様です。

HashSet<T> 固有の実装を利用したいなら、HashSet<T> は HashSet<T> のまま使ってください。