MyCodeSchool

Pasul 1 din 5

C#

Pasul 1 din 5 · Ce construiești

  • C#
  • Mediu
  • 15 minute

Construiește-ți propria listă în C#

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ă.

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}");void Adauga(int x){    if (count == date.Length)    {        int n = date.Length * 2;        int[] nou = new int[n];        Array.Copy(date, nou, count);        date = nou;    }    date[count] = x;    count++;}

Variabile

Ce apare pe ecran


      

  1. Linia 1. Vectorul date are lungimea 2, fixă. date.Length e capacitatea: câte elemente încap.
  2. Linia 2. count ține câte elemente sunt folosite cu adevărat. Deocamdată, toate cele 2.
  3. Linia 4. Apelul Adauga(3) sare în funcție, iar parametrul x primește 3.
  4. Linia 10. 2 == 2: vectorul e plin. Nu există loc pentru al treilea element, deci intrăm în bloc.
  5. Linia 12. Noua capacitate e dublul celei vechi: 4.
  6. Linia 13. Se creează un vector nou, gol, de lungime 4. Elementele lui pornesc de la 0, valoarea implicită pentru int.
  7. Linia 14. Array.Copy copiază primele count elemente din vectorul vechi în cel nou.
  8. Linia 15. date trece să arate spre vectorul nou. Cel vechi nu mai e folosit de nimeni, iar colectorul de gunoi îl va elibera.
  9. Linia 17. Acum e loc: 3 intră pe poziția count, adică 2, prima liberă.
  10. Linia 18. count crește la 3. Funcția s-a terminat, iar x, n și nou dispar.
  11. Linia 5. Se afișează câte elemente sunt folosite și câte încap: „3 din 4”.
  12. 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ă.

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);class ListaMea<T>{    private T[] _date = new T[2];    public int Count { get; private set; }    public int Capacitate => _date.Length;    public void Adauga(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.

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.

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);class Stiva<T>{    private readonly List<T> _el = new();    public int Count => _el.Count;    public void Push(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]);class ListaMea<T>{    private T[] _date = new T[4];    public int Count { get; private set; }    public void Adauga(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]);class ListaMea<T>{    private T[] _date = new T[4];    public int Count { get; private set; }    public void Adauga(T x)        => _date[Count++] = x;    public T this[int i]    {        get        {            if (i < 0 || i >= Count)                throw new                    ArgumentOutOfRangeException(                        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);class ListaMea<T>{    private T[] _date = new T[4];    public int Count { get; private set; }    public void Adauga(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

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 in new[] { 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]);class ListaMea<T> : IEnumerable<T>{    private T[] _date = new T[4];    public int Count { get; private set; }    public int Capacitate => _date.Length;    public void Adauga(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)                throw new                    ArgumentOutOfRangeException(                        nameof(i));            return _date[i];        }    }    public IEnumerator<T> GetEnumerator()    {        for (int poz = 0; poz < Count; poz++)            yield return _date[poz];    }    IEnumerator IEnumerable        .GetEnumerator() => GetEnumerator();}

Ce apare pe ecran

9 7 10 8 6
5 din 8
10

Continuă cu