09/02/21 21:59:10
>766
「拡張メソッド」の訳をさぼったっぽい。
System.Linq.Enumerableクラスの一連のメソッドは第一引数が
this IEnumerable foo
ってなっていて、実際にはIEnumerableを実装しているクラスノインスタンスメソッドのように
使える。C++のSTLで言う「アルゴリズム」みたいなもの。IEnumerableを実装していればみんな
同じ事ができる。ただし、内部的にIEnumeratorを使った列挙にまで落とし込まれるので、
>>767
に書いたみたいに順序付けられて先頭と末尾を持つコンテナの特性は活かされない。
>>768
SortedListはインデックスがある分、要素の追加がO(n)かかる。
実は、本当の意味での二分木ってないんだよね。
SortedDictionary:内部構造は二分木なのにバイナリサーチがない(あれば先頭、末尾を
取得するメソッドがなくても最悪O(logN)で先頭、末尾に辿り着ける)
List, SortedList:バイナリサーチあり。ただしインデックスを持っているので追加、削除
にO(N)かかる。
orz
俺は、スキップリストを自分で実装して二分木の代わりに使っている。確率的アルゴリズムで
もって局所的な操作を行っても平衡二分木状である事が保障され続けるナイスなデータ構造。