W jaki sposób lista <T> działa dynamicznie, mimo że wewnętrznie używa tablicy (która jest stała)?

Question

Już wiem na temat generycznych i tablicowych w C# (wiem o dynamicznej tablicy przy użyciu wskaźników w C++), również wiem, że tablice są stałe rozmiar, więc nie możemy zmienić jego rozmiar po inicjalizacji, musimy przydzielić nowy następnie skopiuj ......

Ostatnio użyłem ILspy do wyświetlenia kodu źródłowego zespołów .net i odkryłem, że lista wewnętrznie polega na prywatnej tablicy, ale nie mogłem zrozumieć, jak to działa , więc zastanawiałem się, jak technicznie to rośnie, czy też zmienia się w pamięci, kiedy go przesadzam?

Answer 1

Przyrząd List<T> przydziela pewną wielkość tablicę o rozmiarze T[] i używa jej jako pamięci dla swoich elementów, dopóki tablica nie wypełni się. Kiedy nowy element wymaga dodania po tym czasie, lista przydziela nową, większą tablicę i kopiuje wszystkie elementy ze starej tablicy do nowej. Nowy element można następnie dodać bez problemu.

Wskutek tego zachowania, dołączanie elementów do List jest opisany jako amortized O (1) Operacja: większość Dokleja podejmie stałą czasu, ponieważ nie ma wolnego miejsca w tablicy podkładu, ale niektóre Dokleja wyzwoli ponowne przydzielenie tablicy i zajmuje dużo więcej czasu.

Sposób realizacji wynika również z publicznego interfejsu List: jest nieruchomość Capacity które kontroluje ile przedmiotów lista może pomieścić bez zmiany rozmiaru, a także constructor który pozwala zarezerwować trochę określonej pojemności przodu (przydatne do unikaj niepotrzebnych operacji zmiany rozmiaru, gdy wiesz od razu, że lista będzie przynajmniej w pewnym rozmiarze).