2

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

  1. 当索引为空或设置为默认值（T）时，您将如何调整通用数组（T[]）的大小？
  2. 既然你不能为空 T，你如何克服默认值为 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;
    }
}

提前致谢。

4

2 回答 2

5

好吧，对于初学者来说，您的Remove和RemoveAt方法不会实现与List<T>. List<T>大小将减少 1，而您List的大小将保持不变。您应该将较高索引的值从已删除的对象转移到一个较低的索引。

此外，GetEnumerator将遍历数组中的所有项目，而不管值是什么。

我相信这将解决您遇到的所有问题。如果有人将 a 添加default(T)到列表中，那么 adefault(T)就是他们将再次退出的内容，无论T是 aint和因此 0 还是类类型和因此null。

最后，关于缩小规模：一些可增长的数组实现合理化了这一点，如果数组曾经变得如此之大，那么比平常更有可能再次变得那么大。出于这个原因，他们特别避免缩小规模。

于 2013-08-28T01:07:52.043 回答
4

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

添加很简单，您可以像之前那样在末尾添加一个元素。

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

实现的另一个关键是枚举器。您想遍历第一个元素，直到达到列表长度。不要跳过空值。

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

顺便说一句，我不同意

我肯定知道升迁的最佳解决方案是将当前长度增加 2 的幂

这是默认行为，List<T>但并不是所有情况下的最佳解决方案。这就是为什么List<T>允许您指定容量。如果您从源加载列表并且知道要添加多少项目，则可以预先初始化列表的容量以减少副本数量。同样，如果您要创建数百或数千个大于默认大小或可能更大的列表，则将列表预初始化为相同大小可能会提高内存利用率。这样他们分配和释放的内存将是相同的连续块，并且可以更有效地重复分配和释放。例如，我们有一个报告计算引擎，它为每次运行创建大约 300,000 个列表，每秒运行很多次。我们知道每个列表总是有几百个项目，所以我们将它们全部预初始化为 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();
        }
    }
于 2013-08-28T01:10:13.180 回答