固定索引数组

• 下载源代码 - 2.69 MB

引言

FixIndexArray 类的想法来源于我在寻找一种数组结构，它能够

• 像 List<T> 一样通过索引直接访问项目。
• 像 Dictionary<int,T> (类似于数据库主键) 一样，在删除项目时保证相同的索引。
• 比 Dictionary<int,T> 删除/添加项目具有更高的性能。

因此，我开发了 FixIndexArray 类。最终的性能结果如图所示，证明它满足了以上所有要求。

使用代码

使用类 cFixIndexArr 非常简单，API 与 List<T> 非常相似。

//
// This code demonstrates how to use Enumerator  
//
private void PrintArr(cFixIndexArr<int> arr) {
    Console.Write("Array : "); 
    foreach(int val in arr) {
        Console.Write(string.Format("{0}, ", val));
    }
}
//
// This code demonstrates the most common use cases  
// 
[Test]
public void UseCase() {
    Console.WriteLine(
      "Create the FixIndexArr of integers with default capacity 10"
    );  
    cFixIndexArr<int> arr = new cFixIndexArr<int>(10);
    Console.WriteLine("Load array: {0,10,20,...90}");
    for(int i=0; i<10; i++) {
        arr.Add(i*10); 
    }
    this.PrintArr(arr);
    Console.WriteLine("\r\n\r\nDelete elements 1, 3, 5, 7, 9"); 
    arr.Remove(1); 
    arr.Remove(3); 
    arr.Remove(5);
    arr.Remove(7);
    arr.Remove(9);
    this.PrintArr(arr);
    Console.WriteLine(
       "\r\n\r\nAdd element '11', '22', '33', '44', '55', '66','77'"
    );
    arr.Add(11);
    arr.Add(22);
    int index33 = arr.Add(33);
    arr.Add(44);
    arr.Add(55);
    arr.Add(66);
    arr.Add(77);
    this.PrintArr(arr);
    Console.WriteLine("\r\n\r\nReplacing element 33 by 3333");
    arr[index33] = 3333;
    this.PrintArr(arr);
    Console.WriteLine(
       "\r\n\r\nDelete element 3333 and use it for element 4444"
    );
    arr.Remove(index33);
    arr[index33] = 4444;
    this.PrintArr(arr);
}

这段代码产生以下结果

它是如何工作的？

其背后的思想很简单：类 FixIndexArr<T> 使用一个类型为 List<T> 的数组 valArr 来存储元素本身，并使用一个类型为 List<cItem> 的辅助数组 deletedIndexArr 来跟踪已删除的索引。结构体 cItem 是一个辅助结构，包含有关已删除索引的信息，采用双向链表的方式。