Запись реализации для списка <T> с использованием IEnumerable <T> с нуля

Question

Из-за скуки я решил написать реализацию List с нуля, используя IEnumerable. Я столкнулся несколько вопросов, которые я честно не знаю, как решить:

1. Как бы вы изменить размер общего массива (T []), когда индекс обнуляется или устанавливается по умолчанию (T)?
2. Поскольку вы не можете указать N, как вы преодолеваете числовую примитивную проблему с их значениями, равными 0 по умолчанию?
3. Если ничего не может быть сделано относительно №2, как вы остановите метод GetEnumerator() из yield, возвращающего 0 при использовании числового типа данных?

И последнее, но не менее важное: какова стандартная практика сокращения массива? Я точно знаю, что одним из лучших решений для увеличения является увеличение текущей длины на мощность 2; если и когда вы уменьшаете размер? Per 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; 
    } 
} 

Спасибо заранее.

Answer 1

Ключевой проблемой, с которой вы работаете, является сохранение внутреннего массива и удаление. List<T> не поддерживает частичные массивы внутри. Это не значит, что вы не можете, но сделать это гораздо сложнее. Чтобы точно имитировать List<T>, вы хотите сохранить массив и поле для количества элементов в массиве, которые фактически используются (длина списка равна или меньше длины массива).

Добавить легко, вы добавляете элемент в конец, как и вы.

Удалить сложнее. Если вы удаляете элемент с конца, установите конечный элемент на default(T) и измените длину списка. Если вы удаляете элемент и начинаете с начала или середины, вам нужно сместить содержимое массива и установить последнее значение в default(T). Причина, по которой мы устанавливаем последний элемент: default(T), - это очистить ссылку, а не так, мы можем сказать, действительно ли она «используется». Мы знаем, что он «используется» на основе позиции в массиве и нашей сохраненной длины списка.

Другим ключом к реализации является перечислитель. Вы хотите пропустить первые элементы, пока не нажмете длину списка. Не пропускайте нули.

Это не полная реализация, но должна быть правильная реализация методов, которые вы начали.

Кстати, я не согласен с

Я знаю наверняка, что лучшим решением для Upsizing является увеличение тока длины по мощности 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(); 
     } 
    } 

Answer 2

Ну, для начала, ваши Remove и RemoveAt методы не реализуют то же поведение, что и List<T>. List<T> уменьшится на 1, тогда как ваш List останется неизменным по размеру. Вы должны смещать значения более высокого индекса с удаленного объекта на один более низкий индекс.

Кроме того, GetEnumerator будет перебирать все элементы в массиве независимо от значения.

Я считаю, что это решит все проблемы, которые у вас есть. Если кто-то добавит default(T) в список, то default(T) - это то, что они снова получат обратно, независимо от того, T - это int и, следовательно, 0 или тип класса и, следовательно, null.

Наконец, при сокращении: некоторые реалистичные реализации массивов рационализируют, что, если массив когда-либо становился таким большим, тогда более вероятно, что он снова станет таким большим. По этой причине они специально избегают сокращения.