糖衣阵列（动态调整大小并随机设置任何元素）

Question

我想要我的蛋糕并吃掉它。

我喜欢 C# 中的列表在超出数组初始容量时动态扩展的方式。然而，这还不够。我希望能够做这样的事情：

int[] n = new int[];    // Note how I'm NOT defining how big the array is.
n[5] = 9

是的，速度会有所牺牲，因为在幕后，.NET 需要检查是否超出了默认容量。如果有，那么它可以将数组扩展 5 倍左右。

不幸的是，对于列表，您并不是真的要设置任意元素，虽然如果您 do this 是可能的，但仍然不可能直接设置第五个元素，而不是最初设置列表的大小，更不用说尝试时动态扩展了。

对于任何解决方案，我都希望能够保持简单的方括号语法（而不是使用相对冗长的方法调用），并且速度相对较快（最好几乎与标准数组一样快）当它不扩展数组时。

Answer 1

请注意，我并不一定主张继承List，但如果你真的想要这样：

public class MyList<T> : List<T>
{
    public T this[int i]
    {
        get { 
            while (i >= this.Count) this.Add(default(T));
            return base[i]; 
        }
        set { 
            while (i >= this.Count) this.Add(default(T));
            base[i] = value; 
        }
    }
}

我要补充一点，如果您希望 "array" 的大部分值在程序的整个生命周期内保持为空，则使用 Dictionary<int, T> 会获得更高的效率，特别是随着 collection 的大小变大。

Answer 2

您可以在 List 上定义扩展方法：

public static class ExtensionMethods {
    public static void Set<T>(this List<T> list, int index, T element) {
        if (index < list.Count) {
            list[index] = element;
        } else {
            for (int i = list.Count; i < index; i++) {
                list.Add(default(T));
            }
            list.Add(element);
        }
    }
}

如果您希望第 12 个元素为 1024，请调用 list.Set(12, 1024)。

Answer 3

这是你的圆周率

       static public List<int> AddToList(int index,int value,  List<int> input)
        {
            if (index >= input.Count)
            {
                int[] temparray = new int[index - input.Count + 1];
                input.AddRange(temparray);
            }
            return (input[index] = value);
        }

Answer 4

该问题的一个简单解决方案是从 Dictionary<TKey, TValue> 继承并仅使用值 generic:

public class MyCoolType<T> : Dictionary<int, T> { }

然后你就可以像这样使用它了：

MyCoolType<int> n = new MyCoolType<int>();
n[5] = 9;

还有关于性能的注释。

对于插入，这比列表快多，因为它不需要您调整大小或在数组中的任意位置插入元素。 List<T> 使用数组作为支持字段，当你调整它的大小时，它是昂贵的。（编辑：列表有一个默认大小，您并不总是要调整它的大小，但是当您这样做时，它的成本很高）
对于查找，这非常接近 O(1) (source)，因此与数组查找相当。列表的复杂度为 O(n)，随着包含元素数量的增加，列表会逐渐变慢。
稀疏打包比使用密集打包的列表更节省内存，因为它不需要您使用空项目来达到特定索引。

其他注意事项：

在其他解决方案中，尝试在索引 570442959 处插入一个项目，例如，您将抛出 OutOfMemoryException（在 32 位下，但即使是 64 位也有问题）。使用此解决方案，您可以使用 int 类型支持的任何可能的索引，最多 int.MaxValue.
列表不允许负索引，这会。
MyCoolType.Count相当于这里的数组Length属性。

以下是我的性能测试结果：

将 100 万个元素插入 MyList：29.4294424 秒
将 100 万个元素插入 CoolType：0.127499 秒
查找 100 万个随机元素 MyList：1.6330562 秒
查找 100 万个随机元素 CoolType：1.304348 秒

完整的测试来源：http://pastebin.com/kEdLgFaw

注意，对于运行这些测试，我必须设置为 X64 构建、调试，并且必须将以下内容添加到 app.config 文件中：

<runtime>
  <gcAllowVeryLargeObjects enabled="true" />
</runtime>

糖衣阵列（动态调整大小并随机设置任何元素）

Sugar coated arrays (dynamically resizable and set any element at random)

.net

c#

arrays

list

syntactic-sugar