一尘不染

列表中使用哪种算法 动态分配内存?

algorithm

现在,我有了一种用于在数组上动态分配内存的算法:

  • 如果数组已满,则创建一个两倍大小的新数组,然后复制项目。
  • 如果array是完整阵列的四分之一,我将创建一个新数组,其大小减半,然后复制项目。

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

  1. 什么是更快List<T>的算法,或者这样的基于数组的算法?您会建议使用什么?

  2. List<T>使用简单的阵列作为内部数据结构?


阅读 223

收藏
2020-07-28

共1个答案

一尘不染

要回答您的问题:

没错,C#的List<T>实现使用内部数组

  1. 可序列化
  2. 线程安全
  3. 工具IEnumerable<T>(这意味着可以进行LINQ Queded,foreached等)
  4. 二进制搜索

等等

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

哦,顺便说一句,如果您想要 Microsoft源代码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;
        }
    }
2020-07-28