List <T>中使用哪种算法来动态分配内存？

Question

现在我有一个动态分配数组内存的算法:

• 如果数组已满,我创建一个大小为两倍的新数组,并复制项目.
• 如果数组是四分之一满,我创建一个大小一半的新数组,并复制项目.

这是用于动态内存分配的相当快的算法,尽管将元素复制到新分配的数组的额外开销.

1. 什么是更快,List<T>或基于阵列的这种算法？你会建议使用什么？

2. 确实List<T>使用简单数组作为内部数据结构？

Answer 1

回答你的问题:

确实,C#的List<T>实现使用了一个内部数组

1. 序列化
2. 线程安全
3. 实现IEnumerable<T>(这意味着它可以是LINQ查询,foreach编辑等)
4. 二进制搜索

等等

因此,我会要求您使用List<T>而不是自己的列表.

哦,顺便说一句,如果你想要微软的源代码List<T>,那么就在这里

List.cs

编辑

EnsureCapacityin 的源代码List<T>是:

    // Ensures that the capacity of this list is at least the given minimum
    // value. If the currect capacity of the list is less than min, the
    // capacity is increased to twice the current capacity or to min,
    // whichever is larger.
    private void EnsureCapacity(int min) {
        if (_items.Length < min) {
            int newCapacity = _items.Length == 0? _defaultCapacity : _items.Length * 2;
            if (newCapacity < min) newCapacity = min;
            Capacity = newCapacity;
        }
    }

Answer 2

除非你有特别的理由相信,否则使用C#附带提供的库几乎是一个好主意.这些实现已经很好地实现,经过良好调试并且经过了充分测试.

您描述的数据结构是动态数组数据结构的标准实现,大多数语言都将此作为默认列表实现.查看文档List<T>,似乎List<T>使用此实现,因为它的文档引用了内部容量,并且只要大小小于容量,就保证O(1)追加.

简而言之,除非必须,否则请避免重新发明轮子.

希望这可以帮助!