IDictionary介面 - 二元搜尋與 SortedList 類別

當集合中的鍵值已經過排序,二元搜尋是一種效率很好的搜尋方法,它的原理是將集合中的元素切成兩個部份,一開始將目標元素與中間值比較,若是大於中間值,則繼續比較後半段的中間值,否則比較前半段的中間值,也就是將有可能落在中間的部份持續平分,直到符合搜尋條件的結果。

SortList 類別是另外一種實作 IDictionary 的字典型類別,除了與 HashTable 同樣可以經由 key 搜尋集合中的物件,它同時支援類似陣列集合的的索引存取操作,你可以將其當作 Hashtable 與 Array 的混合類別,利用其類別建構式,可以建立一個初始容量為 16 的空集合,或是你也可以利用以下的建構式,指定集合物件建立時的初始容量大小:
public SortedList(int capacity)
其中的 capacity 用以指定集合的初始容量。

建立 SortList 類別的集合物件之後,透過 Item 屬性,GetByIndex 或是 SetByIndex 這兩個方法,可以針對集合中的物件元素進行存取。

方法 GetByIndex 取得 SortedList 集合中特定索引元素的值,其中 index 指定所要存取的索引,定義如下:
object GetByIndex(int index);
另外一個方法 SetByIndex ,則是將特定物件加入到集合中指定的索引位置,定義如下:
public virtual void SetByIndex(int index,object obj)
index 是集合中指定的索引,obj則為加入此索引位置的物件。

由於 SortList 類別實作了Idictionary、ICollection、 IEnumerable 以及ICloneable這幾個介面,因此同時亦實作這些介面所定義的方法成員,具備了通用的方法成員定義。

SortList 基本上使用二元搜尋法完成索引搜尋,因此使用 SortList 搜尋集合中排序過的物件,將會非常的有效率。
// SortedListDemo
class Program
{
    public static void Main(string[] args)
    {
        SortedList sortedList = new SortedList();
        for (int i = 0; i < 10; i++)
        {
            sortedList.Add("key" + i, "value" + i);
        }
        WriteList(sortedList);
        Console.ReadLine();
    }
    public static void WriteList(SortedList list)
    {
        Console.WriteLine("\n以下為集合中所包含的物件元素key/value !!\n");
        for (int i = 0; i < 10; i++)
        {
            Console.WriteLine("mySortedList[{0}] 的值為: {1} ",
             list.GetKey(i), list["key" + i]);
        }
        Console.WriteLine("\n以下使用索引一一取出集合中的物件元素!!\n");
        for (int i = 0; i < 10; i++)
        {
            Console.WriteLine(" 索引{0} 的值為: {1} ", i,
              list.GetByIndex(i).ToString());
        }
        Console.WriteLine();
    }
}
主程式一開始的 for 迴圈,引用 SortedList 類別定義的方法 GetKey 逐步取得參數索引值對應的 key ,另外使用 [ ] 運算子存取其中 key 對應的物件將其輸出。 第二段迴圈引用實體方法 GetByIndex 傳入代表集合物件元素的索引值,GetByIndex 根據這個參數值取得集合中的物件,將其轉換成字串輸出。
以下為集合中所包含的物件元素 key/value !!

mySortedList[key0] 的值為 : value0
mySortedList[key1] 的值為 : value1
mySortedList[key2] 的值為 : value2
mySortedList[key3] 的值為 : value3
mySortedList[key4] 的值為 : value4
mySortedList[key5] 的值為 : value5
mySortedList[key6] 的值為 : value6
mySortedList[key7] 的值為 : value7
mySortedList[key8] 的值為 : value8
mySortedList[key9] 的值為 : value9

以下使用索引一一取出集合中的物件元素 !!

 索引 0 的值為 : value0
 索引 1 的值為 : value1
 索引 2 的值為 : value2
 索引 3 的值為 : value3
 索引 4 的值為 : value4
 索引 5 的值為 : value5
 索引 6 的值為 : value6
 索引 7 的值為 : value7
 索引 8 的值為 : value8
 索引 9 的值為 : value9
執行結果首先列舉集合中所有物件的索引鍵以及對應的值,然後再由 0 開始,根據索引列出每個物件元素的值。

沒有留言: