编写List<；T>；使用IEnumerable<；T>；从零开始

本文关键字：gt lt 从零开始 IEnumerable 使用 编写 List | 更新日期: 2023-09-27 18:29:11

出于无聊，我决定使用IEnumerable从头开始编写List的实现。我遇到了一些我真的不知道如何解决的问题：

  1. 当索引为null或设置为默认值（T）时，如何调整泛型数组（T[]）的大小
  2. 既然不能将T设为null，那么如何克服默认值为0的数字基元问题
  3. 如果对#2无能为力，如何在使用数值数据类型时阻止GetEnumerator（）方法返回0

最后但并非最不重要的是，缩小阵列规模的标准做法是什么？我确信，放大的最佳解决方案之一是将电流长度增加2的幂；如果何时裁员？按Remove/RemoveAt还是按当前使用的长度%2？

以下是我迄今为止所做的：

public class List<T> : IEnumerable<T>
{
    T[] list = new T[32];
    int current;
    public void Add(T item)
    {
        if (current + 1 > list.Length)
        {
            T[] temp = new T[list.Length * 2];
            Array.Copy(list, temp, list.Length);
            list = temp;
        }
        list[current] = item;
        current++;
    }
    public void Remove(T item)
    {
        for (int i = 0; i < list.Length; i++)
            if (list[i].Equals(item))
                list[i] = default(T);
    }
    public void RemoveAt(int index)
    {
        list[index] = default(T);
    }
    public IEnumerator<T> GetEnumerator()
    {
        foreach (T item in list)
            if (item != null && !item.Equals(default(T)))
                yield return item;
    }
    System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
    {
        foreach (T item in list)
            if (item != null && !item.Equals(default(T)))
                yield return item;
    }
}

提前谢谢。

编写List<；T>；使用IEnumerable<；T>；从零开始

首先，Remove和RemoveAt方法实现的行为与List<T>不同。List<T>的大小将减少1，而您的List的大小将保持不变。您应该将较高索引的值从删除的对象移到较低的索引。

此外，无论值是多少，GetEnumerator都会迭代数组中的所有项

我相信这将解决你所有的问题。如果有人将default(T)添加到列表中，那么default(T)就是他们将再次返回的内容，而不管T是int，因此是0，还是类类型，因此是null。

最后，关于缩小规模：一些可增长的阵列实现合理地认为，如果阵列曾经变得如此大，那么它更有可能再次变得如此大。因此，他们特别避免裁员。

您遇到的关键问题是维护内部数组以及remove的作用。List<T>内部不支持部分数组。这并不意味着你不能，但这样做要复杂得多。为了精确地模拟List<T>，您需要保留一个数组和一个字段，用于表示数组中实际使用的元素数量（列表长度，等于或小于数组长度）。

添加很容易，你可以像以前一样在末尾添加一个元素。

移除更为复杂。如果要从末尾删除元素，请将末尾元素设置为default(T)并更改列表长度。如果要从开头或中间删除元素，则需要移动数组的内容，并将最后一个设置为default(T)。我们将最后一个元素设置为default(T)的原因是为了清除引用，而不是为了判断它是否"正在使用"。根据数组中的位置和存储的列表长度，我们知道它是否"正在使用"。

实现的另一个关键是枚举器。您希望循环浏览第一个元素，直到达到列表长度。不要跳过null。

这不是一个完整的实现，但应该是您启动的方法的正确实现。

顺便说一句，我不同意

我确信，放大的最佳解决方案是将电流长度增加2 的幂

这是List<T>的默认行为，但并不是所有情况下的最佳解决方案。这正是List<T>允许您指定容量的原因。如果您从源加载列表，并且知道要添加的项目数量，则可以预先初始化列表的容量以减少副本数量。同样，如果您正在创建数百或数千个大于默认大小或可能更大的列表，则将列表预初始化为相同大小对内存利用率有好处。这样，它们分配和释放的内存将是相同的连续块，并且可以更有效地重复分配和释放。例如，我们有一个报告计算引擎，它为每次运行创建大约300000个列表，每秒运行多次。我们知道每个列表总是几百个项目，所以我们将它们全部预初始化为1024个容量。这超出了大多数人的需求，但由于它们的长度都相同，而且创建和处理速度也很快，因此可以有效地重用内存。

    public class MyList<T> : IEnumerable<T>
    {
        T[] list = new T[32];
        int listLength;
        public void Add(T item)
        {
            if (listLength + 1 > list.Length)
            {
                T[] temp = new T[list.Length * 2];
                Array.Copy(list, temp, list.Length);
                list = temp;
            }
            list[listLength] = item;
            listLength++;
        }
        public void Remove(T item)
        {
            for (int i = 0; i < list.Length; i++)
                if (list[i].Equals(item))
                {
                    RemoveAt(i);
                    return;
                }
        }
        public void RemoveAt(int index)
        {
            if (index < 0 || index >= listLength)
            {
                throw new ArgumentException("'index' must be between 0 and list length.");
            }
            if (index == listLength - 1)
            {
                list[index] = default(T);
                listLength = index;
                return;
            }
            // need to shift the list
            Array.Copy(list, index + 1, list, index, listLength - index + 1);
            listLength--;
            list[listLength] = default(T);
        }
        public IEnumerator<T> GetEnumerator()
        {                
            for (int i = 0; i < listLength; i++)
            {
                yield return list[i];
            }
        }
        IEnumerator IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }
    }
相关文章：