Я изучал библиотеки .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?
Я знаю, что списки безопасны по типу и не требуют бокса/распаковки, но это немного смутило меня.
Класс list не является массивом. Другими словами, это не происходит из массива. Вместо этого он инкапсулирует массив, который используется реализацией для хранения элементов списка.
Так как List<T> предлагает произвольный доступ к своим элементам, и эти элементы индексируются 0..Count-1, использование массива для хранения элементов является очевидной реализацией.
Это, как правило, удивляет программистов на С++, которые знают std:: list. Связанный список, охватываемый .NET, а также класс LinkedList. И имеет те же перцепционные характеристики, O (1) для вставок и удалений.
Однако вы, однако, избегаете этого. Связанные списки плохо работают на современных процессорах. Что сильно зависит от кэшей процессора, чтобы получить разумную производительность с памятью, которая во много раз медленнее ядра выполнения. Простой массив на сегодняшний день является структурой данных, которая использует большинство преимуществ кеша. Доступ к элементу дает очень высокие шансы, что последующие элементы также присутствуют в кеше. Это не относится к связанному списку, элементы, как правило, разбросаны по всему адресному пространству, что делает вероятностью кеша. Они могут быть очень дорогими, целых 200 циклов, когда процессор ничего не делает, кроме ожидания в подсистеме памяти для подачи данных.
Но помните о характеристиках perf, добавляя или удаляя элемент, который не находится в конце списка, стоит O (n), как и массив. И большой список может генерировать много мусора, поскольку массив должен быть расширен, установка свойства Capacity вверх может помочь многим избежать этого. Подробнее об этом в этом ответе. И в противном случае то же самое относится к std::vector < > .
Да, List<T> использует внутренний массив для хранения элементов, хотя в большинстве случаев массив на самом деле больше, чем количество элементов в коллекции - в конце есть дополнительный "отступы", чтобы вы могли добавлять новые элементы без необходимости перераспределять память каждый раз. Он отслеживает фактический размер коллекции с отдельным полем (вы можете видеть this._size в сгенерированном коде). Когда вы добавляете больше элементов, чем имеет место для текущего массива, он автоматически выделяет новый более крупный массив - в два раза больше, я думаю, - и копирует все существующие элементы.
Если вы беспокоитесь о List<T>, используя больше памяти, чем необходимо, вы можете явно задать размер массива с помощью переопределения конструктора , который принимает значение capacity, если вы знаете размер заранее, или вызовите метод TrimExcess(), чтобы убедиться, что массив находится рядом с фактическим размером коллекции.
Память произвольного доступа - это массив, поэтому в этом смысле структуры данных все из связанных списков в кучи и за ее пределами, которые полагаются на случайный доступ к памяти для их поведения производительности, построены на массив, который является системной памятью. Это больше вопрос о том, сколько уровней абстракции находится между ними.
Конечно, в современной машине с виртуальной памятью системная память с произвольным доступом сама по себе является абстракцией, построенной на сложной модели виртуальной памяти многоуровневых конвейерных кэшей, не кэшированной оперативной памяти и диска.