Является ли List <T> действительно тайным массивом в С#?

Я изучал библиотеки .NET, используя ILSpy, и нашел определение класса List<T> в пространстве имен System.Collections.Generic. Я вижу, что класс использует такие методы, как этот:

// System.Collections.Generic.List<T>
/// <summary>Removes all elements from the <see cref="T:System.Collections.Generic.List`1" />.</summary>
public void Clear()
{
    if (this._size > 0)
    {
        Array.Clear(this._items, 0, this._size);
        this._size = 0;
    }
    this._version++;
}

Итак, метод Clear() класса List<T> фактически использует метод Array.Clear. Я видел много других методов List<T>, которые используют материал Array в теле.

Означает ли это, что List<T> на самом деле скрытый массив или список использует только часть методов Array?

Я знаю, что списки безопасны по типу и не требуют бокса/распаковки, но это немного смутило меня.

Ответ 1

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

Так как List<T> предлагает произвольный доступ к своим элементам, и эти элементы индексируются 0..Count-1, использование массива для хранения элементов является очевидной реализацией.

Ответ 2

Это, как правило, удивляет программистов на С++, которые знают std:: list. Связанный список, охватываемый .NET, а также класс LinkedList. И имеет те же перцепционные характеристики, O (1) для вставок и удалений.

Однако вы, однако, избегаете этого. Связанные списки плохо работают на современных процессорах. Что сильно зависит от кэшей процессора, чтобы получить разумную производительность с памятью, которая во много раз медленнее ядра выполнения. Простой массив на сегодняшний день является структурой данных, которая использует большинство преимуществ кеша. Доступ к элементу дает очень высокие шансы, что последующие элементы также присутствуют в кеше. Это не относится к связанному списку, элементы, как правило, разбросаны по всему адресному пространству, что делает вероятностью кеша. Они могут быть очень дорогими, целых 200 циклов, когда процессор ничего не делает, кроме ожидания в подсистеме памяти для подачи данных.

Но помните о характеристиках perf, добавляя или удаляя элемент, который не находится в конце списка, стоит O (n), как и массив. И большой список может генерировать много мусора, поскольку массив должен быть расширен, установка свойства Capacity вверх может помочь многим избежать этого. Подробнее об этом в этом ответе. И в противном случае то же самое относится к std::vector < > .

Ответ 3

Да, List<T> использует внутренний массив для хранения элементов, хотя в большинстве случаев массив на самом деле больше, чем количество элементов в коллекции - в конце есть дополнительный "отступы", чтобы вы могли добавлять новые элементы без необходимости перераспределять память каждый раз. Он отслеживает фактический размер коллекции с отдельным полем (вы можете видеть this._size в сгенерированном коде). Когда вы добавляете больше элементов, чем имеет место для текущего массива, он автоматически выделяет новый более крупный массив - в два раза больше, я думаю, - и копирует все существующие элементы.

Если вы беспокоитесь о List<T>, используя больше памяти, чем необходимо, вы можете явно задать размер массива с помощью переопределения конструктора , который принимает значение capacity, если вы знаете размер заранее, или вызовите метод TrimExcess(), чтобы убедиться, что массив находится рядом с фактическим размером коллекции.

Ответ 4

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

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