Un vector în C# are lungimea fixată la creare. Totuși, List<T> primește oricâte elemente. Construiești singur o listă care face același lucru, ca să vezi exact ce se întâmplă pe dedesubt.
ListaMea, în terminal
9 7 10 8 6
5 din 8
10
Lista ta pornește cu loc pentru 4 note. Când vine a cincea, își face singură loc pentru 8. Prima linie vine dintr-un foreach, ultima din note[2], exact ca la o listă adevărată.
să faci un vector să „crească”, copiindu-l într-unul mai mare
să scrii o clasă generică, ListaMea<T>, bună pentru orice tip
să accesezi elementele cu lista[i], printr-un indexer care verifică limitele
să parcurgi lista cu foreach, cu ajutorul lui yield return
Pasul 2 din 5
Momentul în care lista crește
Inima listei e funcția Adauga. Vectorul are deja 2 elemente din 2 posibile, iar acum adaugi al treilea. Apasă „Linia următoare” și urmărește ce se întâmplă cu vectorul.
Program.cs
int[] date = { 5, 8 };int count = 2;Adauga(3);Console.WriteLine($"{count} din {date.Length}");voidAdauga(int x){if (count == date.Length) {int n = date.Length * 2;int[] nou = newint[n]; Array.Copy(date, nou, count); date = nou; } date[count] = x; count++;}
Variabile
Ce apare pe ecran
Linia 1. Vectorul date are lungimea 2, fixă. date.Length e capacitatea: câte elemente încap.
Linia 2.count ține câte elemente sunt folosite cu adevărat. Deocamdată, toate cele 2.
Linia 4. Apelul Adauga(3) sare în funcție, iar parametrul x primește 3.
Linia 10. 2 == 2: vectorul e plin. Nu există loc pentru al treilea element, deci intrăm în bloc.
Linia 12. Noua capacitate e dublul celei vechi: 4.
Linia 13. Se creează un vector nou, gol, de lungime 4. Elementele lui pornesc de la 0, valoarea implicită pentru int.
Linia 14.Array.Copy copiază primele count elemente din vectorul vechi în cel nou.
Linia 15.date trece să arate spre vectorul nou. Cel vechi nu mai e folosit de nimeni, iar colectorul de gunoi îl va elibera.
Linia 17. Acum e loc: 3 intră pe poziția count, adică 2, prima liberă.
Linia 18.count crește la 3. Funcția s-a terminat, iar x, n și nou dispar.
Linia 5. Se afișează câte elemente sunt folosite și câte încap: „3 din 4”.
Gata. Un loc a rămas liber. Următorul Adauga va fi rapid, fără nicio copiere.
Prezice ieșirea
După linia 4 mai scrii Adauga(1); și Adauga(4);. Ce afișează acum linia 5?
Răspuns: „5 din 8”.
Adauga(1) ocupă ultimul loc liber: 4 din 4. La Adauga(4) vectorul e iar plin, deci capacitatea se dublează din nou, la 8, și abia apoi intră elementul.
Pasul 3 din 5
De la funcție la colecție
Mutăm ideea într-o clasă reutilizabilă, apoi construim o stivă. La final, două capcane pe care le are orice colecție scrisă de mână.
1
O clasă generică
Program.cs
var note = new ListaMea<double>();note.Adauga(9.5);note.Adauga(7);note.Adauga(10);Console.WriteLine(note.Count);Console.WriteLine(note[1]);Console.WriteLine(note.Capacitate);classListaMea<T>{private T[] _date = new T[2];publicint Count { get; privateset; }publicint Capacitate => _date.Length;publicvoidAdauga(T x) {if (Count == _date.Length) {var nou = new T[_date.Length * 2]; Array.Copy(_date, nou, Count); _date = nou; } _date[Count] = x; Count++; }public T this[int i] => _date[i];}
Ce apare pe ecran
3
7
4
T e un loc gol pentru tip. La new ListaMea<double>(), compilatorul pune double peste tot unde scrie T. Aceeași clasă merge și pentru string sau pentru clasele tale.
Câmpul _date e private: din afară se vede doar ce alegi tu. Count se poate citi de oriunde, dar se schimbă doar din interior, datorită lui private set. Linia this[int i] e un indexer: îți permite să scrii note[1], ca la un vector.
2
De ce dublăm, nu creștem cu 1
Fiecare creștere copiază tot vectorul. Dacă ai crește cu câte un loc, la 1.000 de adăugări ai face aproape 1.000 de copieri, tot mai lungi.
Cu dublarea, capacitatea trece prin 4, 8, 16… 1.024: doar 8 copieri pentru 1.000 de elemente. În medie, o adăugare costă un timp constant. Exact așa crește și List<T> din .NET, iar proprietatea ei Capacity îți arată capacitatea.
Prețul plătit: memorie nefolosită. După 513 elemente, ai rezervat loc pentru 1.024.
3
O stivă: ultimul intrat, primul ieșit
Program.cs
var pagini = new Stiva<string>();pagini.Push("acasă");pagini.Push("cursuri");pagini.Push("curs C#");Console.WriteLine(pagini.Pop());Console.WriteLine(pagini.Peek());Console.WriteLine(pagini.Count);classStiva<T>{privatereadonly List<T> _el = new();publicint Count => _el.Count;publicvoidPush(T x) => _el.Add(x);public T Peek() => _el[^1];public T Pop() { T varf = _el[^1]; _el.RemoveAt(_el.Count - 1);return varf; }}
Ce apare pe ecran
curs C#
cursuri
2
O stivă e ca butonul „Înapoi” din browser: ultima pagină deschisă e prima la care te întorci. Push pune deasupra, Pop scoate de deasupra, Peek doar se uită.
Stiva e construită peste o listă, iar vârful e ultimul element. _el[^1] înseamnă „primul de la coadă”. Adăugarea și scoaterea la capăt sunt rapide, pentru că nu mută nimic.
Capcană: indexul trece de Count, dar nu de capacitate
Vectorul are 4 locuri, dar doar 3 sunt folosite. Fără verificare, note[3] nu dă nicio eroare: întoarce valoarea implicită 0, o notă care nu există.
Program.cs
var note = new ListaMea<int>();note.Adauga(9);note.Adauga(7);note.Adauga(10);Console.WriteLine(note[3]);classListaMea<T>{private T[] _date = new T[4];publicint Count { get; privateset; }publicvoidAdauga(T x) => _date[Count++] = x;public T this[int i] => _date[i];}
Ce apare pe ecran
0
Repară comparând indexul cu Count, nu cu lungimea vectorului. Acum greșeala se vede imediat:
Program.cs
var note = new ListaMea<int>();note.Adauga(9);note.Adauga(7);note.Adauga(10);Console.WriteLine(note[3]);classListaMea<T>{private T[] _date = new T[4];publicint Count { get; privateset; }publicvoidAdauga(T x) => _date[Count++] = x;public T this[int i] {get {if (i < 0 || i >= Count)thrownewArgumentOutOfRangeException(nameof(i));return _date[i]; } }}
Unhandled exception. System.ArgumentOutOfRangeException: Specified argument was out of the range of valid values. (Parameter 'i')
at ListaMea`1.get_Item(Int32 i) in Program.cs:line 18
at Program.<Main>$(String[] args) in Program.cs:line 5
Capcană: foreach pe o clasă oarecare
foreach nu știe singur cum să-ți parcurgă clasa. Are nevoie de o metodă GetEnumerator:
Program.cs
var note = new ListaMea<int>();note.Adauga(9);foreach (int n in note) Console.WriteLine(n);classListaMea<T>{private T[] _date = new T[4];publicint Count { get; privateset; }publicvoidAdauga(T x) => _date[Count++] = x;}
Program.cs(3,19): error CS1579: foreach statement cannot operate on variables of type 'ListaMea<int>' because 'ListaMea<int>' does not contain a public instance or extension definition for 'GetEnumerator'
Repară implementând IEnumerable<T>. Cu yield return, metoda dă elementele unul câte unul, fără să construiești altă listă. Varianta completă e în pasul 5.
Pasul 4 din 5
Verifică-te
Cinci întrebări noi. După fiecare răspuns vezi imediat de ce e așa.
1 din 5 · Prezice ieșirea
Programul simulează capacitatea unei liste care pornește de la 4. Ce afișează după 9 adăugări?
Program.cs
int cap = 4;int count = 0;for (int k = 1; k <= 9; k++){if (count == cap) cap *= 2; count++;}Console.WriteLine($"{count} / {cap}");
Răspuns: „9 / 16”.
Capacitatea se dublează când lista e plină: la al cincilea element devine 8, la al nouălea devine 16. Elementele folosite sunt 9.
2 din 5 · Alege varianta
De ce o listă își dublează capacitatea în loc s-o crească cu 1?
Răspuns: ca să copieze vectorul cât mai rar.
Fiecare creștere înseamnă o copiere completă. Dublarea face copierile rare, dar consumă mai multă memorie, nu mai puțină: o parte din locuri stau libere.
3 din 5 · Prezice ieșirea
Aceeași idee, cu Stack<T> din .NET. Ce afișează programul?
Program.cs
var s = new Stack<int>();s.Push(1);s.Push(2);s.Push(3);s.Pop();Console.WriteLine(s.Peek());
Răspuns: „2”.
Vârful e mereu ultimul element pus. Pop scoate 3, iar Peek se uită la noul vârf, 2, fără să-l scoată.
4 din 5 · Alege varianta
Ce trebuie să aibă ListaMea<T> ca să meargă foreach (var n in note)?
Răspuns: o metodă GetEnumerator.
foreach cere un enumerator, care dă elementele pe rând. Count și indexerul nu ajung: fără GetEnumerator primești eroarea CS1579.
5 din 5 · Prezice ieșirea
În lista din capcana 1, cea cu verificare, ai adăugat 9, 7 și 10. Ce se întâmplă la Console.WriteLine(note[3]);?
Răspuns: programul se oprește cu ArgumentOutOfRangeException.
Indicii valizi sunt 0, 1 și 2, pentru că numărătoarea pornește de la 0. 3 >= Count, deci indexerul aruncă excepția, chiar dacă vectorul are fizic un al patrulea loc.
Pasul 5 din 5
Ce ai învățat
O listă dinamică e un vector plus un contor. Când se umple, copiezi totul într-un vector de două ori mai mare.
Capacitatea (cât încape) și Count (cât e folosit) sunt lucruri diferite. Verificările se fac față de Count.
Cu <T> scrii o singură clasă pentru orice tip, iar indexerul this[int i] îți dă sintaxa lista[i].
foreach are nevoie de GetEnumerator. Cu yield return o scrii în câteva linii.
Programul complet
Lista finală implementează IEnumerable<T>, deci merge în foreach. Pentru creștere folosește Array.Resize, care face aceeași copiere pe care ai urmărit-o la pasul 2.
Program.cs
using System.Collections;var note = new ListaMea<int>();foreach (int n innew[] { 9, 7, 10, 8, 6 }) note.Adauga(n);foreach (int n in note) Console.Write($"{n} ");Console.WriteLine();Console.WriteLine($"{note.Count} din {note.Capacitate}");Console.WriteLine(note[2]);classListaMea<T> : IEnumerable<T>{private T[] _date = new T[4];publicint Count { get; privateset; }publicint Capacitate => _date.Length;publicvoidAdauga(T x) {if (Count == _date.Length) Array.Resize(ref _date, Count * 2); _date[Count] = x; Count++; }public T this[int i] {get {if (i < 0 || i >= Count)thrownewArgumentOutOfRangeException(nameof(i));return _date[i]; } }public IEnumerator<T> GetEnumerator() {for (int poz = 0; poz < Count; poz++)yieldreturn _date[poz]; } IEnumerator IEnumerable .GetEnumerator() => GetEnumerator();}