SortedList<TKey, TValue>辞書のように見えるa しかないのにSortedList<T>、実際には常にソートされる単なるリストであるのはなぜですか?
SortedList に関する MSDN のドキュメントによると、実際にKeyValuePair<TKey, TValue>は、常にキーによってソートされる動的サイズの配列として内部的に実装されています。同じクラスは、任意のタイプのリストとしてより便利ではないTでしょうか? その方が名前にもぴったりではないでしょうか。
が存在しない理由は誰にもわかりませんが、 がキーと値を取るSortedList<T>理由について議論することは可能です。SortedListディクショナリはキーを値にマップします。これを行う一般的な方法は、バイナリ ツリー、ハッシュ テーブル、およびリスト (配列) を使用することですが、ほとんどの操作で O(1) であるため、ハッシュ テーブルが最も一般的です。
O(1) でサポートされていない主な操作は、次のキーを順番に取得することです。それを可能にしたい場合は、通常、バイナリ ツリーを使用して、並べ替えられた辞書を提供します。
マップをリストとして実装することにした場合は、ルックアップが O(lg n) になるように要素をキーでソートしたままにして、ソートされたリストの形式で別のソートされた辞書を提供します。もちろん、その名前SortedDictionaryはすでに使用されていましたが、SortedListそうではありませんでした。SortedListDictionaryまたはと呼んでいたかもしれませSortedDictionaryListんが、名前を付けることができませんでした。
今あります:)
public class SortedList<T> : ICollection<T>
{
private List<T> m_innerList;
private Comparer<T> m_comparer;
public SortedList() : this(Comparer<T>.Default)
{
}
public SortedList(Comparer<T> comparer)
{
m_innerList = new List<T>();
m_comparer = comparer;
}
public void Add(T item)
{
int insertIndex = FindIndexForSortedInsert(m_innerList, m_comparer, item);
m_innerList.Insert(insertIndex, item);
}
public bool Contains(T item)
{
return IndexOf(item) != -1;
}
/// <summary>
/// Searches for the specified object and returns the zero-based index of the first occurrence within the entire SortedList<T>
/// </summary>
public int IndexOf(T item)
{
int insertIndex = FindIndexForSortedInsert(m_innerList, m_comparer, item);
if (insertIndex == m_innerList.Count)
{
return -1;
}
if (m_comparer.Compare(item, m_innerList[insertIndex]) == 0)
{
int index = insertIndex;
while (index > 0 && m_comparer.Compare(item, m_innerList[index - 1]) == 0)
{
index--;
}
return index;
}
return -1;
}
public bool Remove(T item)
{
int index = IndexOf(item);
if (index >= 0)
{
m_innerList.RemoveAt(index);
return true;
}
return false;
}
public void RemoveAt(int index)
{
m_innerList.RemoveAt(index);
}
public void CopyTo(T[] array)
{
m_innerList.CopyTo(array);
}
public void CopyTo(T[] array, int arrayIndex)
{
m_innerList.CopyTo(array, arrayIndex);
}
public void Clear()
{
m_innerList.Clear();
}
public T this[int index]
{
get
{
return m_innerList[index];
}
}
public IEnumerator<T> GetEnumerator()
{
return m_innerList.GetEnumerator();
}
IEnumerator IEnumerable.GetEnumerator()
{
return m_innerList.GetEnumerator();
}
public int Count
{
get
{
return m_innerList.Count;
}
}
public bool IsReadOnly
{
get
{
return false;
}
}
public static int FindIndexForSortedInsert(List<T> list, Comparer<T> comparer, T item)
{
if (list.Count == 0)
{
return 0;
}
int lowerIndex = 0;
int upperIndex = list.Count - 1;
int comparisonResult;
while (lowerIndex < upperIndex)
{
int middleIndex = (lowerIndex + upperIndex) / 2;
T middle = list[middleIndex];
comparisonResult = comparer.Compare(middle, item);
if (comparisonResult == 0)
{
return middleIndex;
}
else if (comparisonResult > 0) // middle > item
{
upperIndex = middleIndex - 1;
}
else // middle < item
{
lowerIndex = middleIndex + 1;
}
}
// At this point any entry following 'middle' is greater than 'item',
// and any entry preceding 'middle' is lesser than 'item'.
// So we either put 'item' before or after 'middle'.
comparisonResult = comparer.Compare(list[lowerIndex], item);
if (comparisonResult < 0) // middle < item
{
return lowerIndex + 1;
}
else
{
return lowerIndex;
}
}
}
List<T>その理由はおそらく、すでにBinarySearchandがあるためだと思います。Insertつまり、独自の常にソートされたリストを実装するのは簡単です。
これは、SortedList<T>クラスがフレームワークに属していないことを意味するわけではありません。必要な開発者が簡単にすばやく作成できるため、クラスの優先度はおそらくそれほど高くありませんでした。
.NET 3.5より前のものをシミュレートするために（たとえば）をHashSet<T>簡単に使用できるため、元々存在しなかったについても同じことが当てはまると思います。Dictionary<T, byte>
私は両方のケースでそれを行ったことを知っています.UniqueSet<T>クラスとクラスがあり、それぞれ aと a をAlwaysSortedList<T>ラップしただけです(そして と を使用しました)。Dictionary<T, byte>List<T>BinarySearchInsert
キーでソートされたリストです。私はただ推測していますが、要素とは別にキーを指定する機能を提供することで、要素は比較可能である必要はありません。必要なのはキーだけです。一般的なケースでは、キーはすでに比較可能な型である可能性が高いため、これにより IComparable を実装するために開発されているかなりの量のコードが節約されると思います。
RPM コメントは非常に有効です。また、Linq 拡張機能を使用すると、Sort 拡張メソッドを使用して T の任意のプロパティで並べ替えることができます。それがその背後にある主な理由かもしれないと思います。