Generyki i kolekcje w C# - List, Dictionary, ograniczenia typów

W poprzednim wpisie Programowanie obiektowe w C# zbudowałeś hierarchię pojazdów - klasy, dziedziczenie, polimorfizm i interfejsy. Teraz przechodzimy do narzędzi, których będziesz używał w każdym programie: kolekcji oraz mechanizmu, który czyni je bezpiecznymi - generyków. To moment, w którym kod przestaje operować na pojedynczych obiektach, a zaczyna zarządzać ich grupami.

W tej części zobaczysz, dlaczego generyki w ogóle powstały (to nie zawsze było oczywiste), jak działają List<T> i Dictionary<TKey, TValue> od środka oraz jak napisać własny, bezpieczny kontener z ograniczeniami where.

1. Dlaczego generyki istnieją #

Zanim w C# 2.0 pojawiły się generyki, kolekcje takie jak ArrayList przechowywały wszystko jako najbardziej ogólny typ - object. Każdy element trafiał do kolekcji “spłaszczony” do wspólnego praprzodka wszystkich typów. Wiązały się z tym dwa poważne problemy.

Problem pierwszy: brak bezpieczeństwa typów #

Skoro ArrayList przechowuje object, możesz umieścić w niej liczbę, a wiersz niżej tekst. Kompilator nie widzi w tym nic złego - przecież oba są typu object. Problem ujawnia się dopiero w trakcie działania programu:

// BEZ generyków - ArrayList przechowuje object
ArrayList lista = new ArrayList();
lista.Add(42);          // int
lista.Add("tekst");      // string - kompilator nie protestuje

int liczba = (int)lista[1];   // BŁĄD w trakcie wykonania - to był string!
// InvalidCastException pojawia się dopiero, gdy program działa już u użytkownika

Błąd, który mógł zostać wychwycony przy kompilacji, ujawnia się dopiero u użytkownika. To najgorszy rodzaj usterki - niewidoczna, dopóki nie jest za późno.

Problem drugi: boxing i unboxing #

Boxing to opakowanie typu wartościowego (np. int) w obiekt alokowany na stercie, by można było potraktować go jak typ referencyjny. Unboxing to operacja odwrotna - rozpakowanie wartości z powrotem. Skoro ArrayList trzyma object (typ referencyjny), każde dodanie int wymusza boxing, a każdy odczyt - unboxing:

ArrayList numbers = new ArrayList();
numbers.Add(5);                  // boxing: int → obiekt na stercie
int x = (int)numbers[0];         // unboxing: obiekt → int

Przy tysiącach operacji w pętli to zauważalny narzut - dodatkowe alokacje na stercie i praca dla odśmiecacza pamięci (GC). To czas, który dałoby się oszczędzić.

Rozwiązanie: parametr typu <T> #

Generyki pozwalają zdefiniować klasę, interfejs lub metodę z parametrem typu (zwykle oznaczanym T, od ang. Type). To miejsce zarezerwowane, które uzupełniasz konkretnym typem dopiero przy tworzeniu obiektu:

// Z generykami - lista wie, że trzyma WYŁĄCZNIE int
List<int> numbers = new List<int>();
numbers.Add(5);              // bez boxingu - lista trzyma int bezpośrednio
numbers.Add("tekst");        // BŁĄD KOMPILACJI - kompilator nie pozwoli

int x = numbers[0];          // bez unboxingu, bez rzutowania

Kompilator pilnuje, byś nie umieścił w List<int> niczego poza liczbami całkowitymi. Błąd typu przeniósł się z czasu wykonania do etapu kompilacji - ujawnia się, zanim w ogóle uruchomisz program.

Niuans: generyki C# nie są “udawane” #

W niektórych językach (jak Java) generyki znikają po kompilacji - to tzw. type erasure, czyli w trakcie wykonania List<int> i List<string> są tym samym surowym typem. C# działa inaczej. Generyki zachowują pełną informację o typie w środowisku uruchomieniowym: List<int> i List<string> to naprawdę różne typy, typeof(T) zwraca konkretny typ, a dla typów wartościowych CLR generuje wyspecjalizowany kod - dlatego boxing naprawdę znika, a nie jest tylko ukrywany.

2. List<T> - dynamiczna tablica #

Co to jest: List<T> to kolekcja przechowująca elementy tego samego typu, dostępne przez indeks, która sama rośnie w miarę dodawania danych.

Dlaczego istnieje: zwykła tablica (int[]) ma stały rozmiar. Utworzysz tablicę na 5 elementów - szóstego już nie dodasz. W praktyce rzadko wiesz z góry, ilu elementów będziesz potrzebować. List<T> rozwiązuje to, zarządzając w tle zwykłą tablicą: gdy brakuje miejsca, tworzy większą i przepisuje do niej dane.

// Lista przechowująca tylko liczby całkowite
List<int> grades = new List<int>();

grades.Add(5);                              // dodanie jednego elementu
grades.Add(3);
grades.AddRange(new int[] { 4, 2, 6 });     // dodanie wielu na raz

grades.Remove(2);        // usuwa pierwszą napotkaną dwójkę (wartość!)
grades.RemoveAt(0);      // usuwa element o indeksie 0 (pozycja!)

bool maSzostke = grades.Contains(6);        // true

foreach (int ocena in grades)
{
    Console.WriteLine($"Ocena: {ocena}");
}

Count kontra Capacity #

To dwie różne liczby, które łatwo pomylić:

• Count - ile elementów faktycznie znajduje się w liście.
• Capacity - ile elementów zmieści się w wewnętrznej tablicy bez jej powiększania.

Gdy Count zrówna się z Capacity i dodasz kolejny element, lista alokuje nową, większą tablicę i kopiuje do niej wszystko. Przy domyślnym konstruktorze pojemność rośnie według schematu:

0 → 4 → 8 → 16 → 32 → 64 ...

Lista zaczyna pusta (pojemność 0), przy pierwszym dodaniu rośnie do 4, a potem podwaja się za każdym razem, gdy zabraknie miejsca. Dzięki temu kosztowne realokacje zdarzają się rzadko - dla miliona elementów potrzeba ich zaledwie około dwudziestu.

Zasada ogólna: jeśli z góry znasz przybliżony rozmiar listy, podaj go w konstruktorze (new List<int>(1000)) - unikniesz serii realokacji.

Pułapka: koszt operacji w środku listy #

Dostęp przez indeks (grades[3]) i dodawanie na koniec (Add) są szybkie. Ale Insert i Remove w środku listy wymagają przesunięcia wszystkich kolejnych elementów - to koszt rosnący wraz z rozmiarem listy. Jeśli często wstawiasz i usuwasz w środku, List<T> może nie być najlepszym wyborem.

3. Dictionary<TKey, TValue> - mapowanie klucz na wartość #

Co to jest: Dictionary<TKey, TValue> przechowuje dane w parach klucz → wartość. Klucze muszą być unikalne, a po kluczu wyciągasz powiązaną z nim wartość.

Dlaczego istnieje: gdyby pracownika trzeba było wyszukiwać po numerze PESEL w List, program przeglądałby ją element po elemencie - im więcej danych, tym wolniej. Dictionary opiera się na tablicy mieszającej (hash table): hasz klucza wskazuje miejsce w pamięci niemal bezpośrednio. Wyszukanie jest błyskawiczne - o złożoności bliskiej O(1) - niezależnie od tego, czy słownik liczy dziesięć elementów, czy milion.

// Klucz = PESEL (string), wartość = imię i nazwisko pracownika (string)
Dictionary<string, string> employees = new Dictionary<string, string>();

// Dodawanie
employees.Add("95010112345", "Jan Kowalski");
employees["88051298765"] = "Anna Nowak";   // przez indekser - dodaje lub nadpisuje

// Pobieranie przez indekser - rzuca wyjątek, jeśli klucza nie ma!
string ktos = employees["95010112345"];

Bezpieczne pobieranie: TryGetValue #

Indekser employees["brak"] przy nieistniejącym kluczu rzuca KeyNotFoundException. Jeśli nie masz pewności, czy klucz istnieje, użyj TryGetValue - zwraca bool zamiast rzucać wyjątek:

if (employees.TryGetValue("11111111111", out string found))
{
    Console.WriteLine($"Found: {found}");
}
else
{
    Console.WriteLine("Nie ma pracownika o takim numerze PESEL");
}

// Sprawdzenie samego istnienia klucza:
if (!employees.ContainsKey("95010112345"))
{
    employees.Add("95010112345", "Ktoś Inny");
}

Iteracja po słowniku #

Przechodząc po słowniku, dostajesz pary KeyValuePair<TKey, TValue>:

foreach (KeyValuePair<string, string> para in employees)
{
    Console.WriteLine($"PESEL: {para.Key}, pracownik: {para.Value}");
}

Dwie istotne pułapki #

• Kolejność iteracji jest nieokreślona. Dokumentacja wprost ostrzega, że kolejność zwracania elementów nie jest gwarantowana. Nie pisz kodu, który zakłada, że elementy wyjdą w kolejności dodawania - jeśli kolejność ma znaczenie, potrzebujesz innej struktury.
• Klucz nie może się zmieniać. Skoro miejsce w pamięci wyznacza hasz klucza, modyfikacja klucza (a dokładnie jego GetHashCode) po dodaniu do słownika “gubi” element - słownik szuka go w innym miejscu, niż faktycznie leży. Jako kluczy używaj typów niemutowalnych, jak string czy int.

Krewniak: HashSet<T> #

Gdy potrzebujesz wyłącznie zbioru unikalnych wartości (bez powiązanych z nimi danych), użyj HashSet<T>. Działa na tej samej zasadzie haszowania, automatycznie odrzuca duplikaty, a sprawdzenie “czy element należy do zbioru” jest niemal natychmiastowe:

HashSet<int> unikalne = new HashSet<int> { 1, 2, 3, 1, 2 };
Console.WriteLine(unikalne.Count);   // 3 - duplikaty zniknęły

4. Własny typ generyczny i ograniczenia (where) #

Gdy piszesz własną klasę generyczną, np. class Warehouse<T>, kompilator domyślnie zakłada, że T może być absolutnie wszystkim - liczbą, tekstem, pojazdem, połączeniem z bazą danych. Skutek: wewnątrz klasy na obiekcie T wywołasz tylko to, co ma każdy object (ToString(), Equals(), GetHashCode()). Nic więcej - kompilator nie ma bowiem żadnej gwarancji, czym T naprawdę będzie.

Po co ograniczenia #

Aby to zmienić, stosujemy ograniczenia typów generycznych (generic constraints) słowem kluczowym where. Mówisz kompilatorowi: “pozwalam podstawić pod T dowolny typ, pod warunkiem że spełnia te wymagania”. W zamian kompilator odblokowuje składowe, które ten warunek gwarantuje.

Ograniczenie	Znaczenie
where T : class	T musi być typem referencyjnym
where T : struct	T musi być typem wartościowym (innym niż nullable)
where T : new()	T musi mieć publiczny konstruktor bezparametrowy - pozwala na new T()
where T : NameKlasy	T musi być tą klasą lub po niej dziedziczyć
where T : NameInterfejsu	T musi implementować dany interfejs
where T : notnull	T musi być typem niedopuszczającym null
where T : U	T musi być typem U lub po nim dziedziczyć (gdzie U to inny parametr typu)

Reguły kolejności ograniczeń #

Ograniczeń można nałożyć kilka na raz, ale ich kolejność nie jest dowolna:

• class, struct lub notnull - jeśli występuje, musi być pierwsze.
• new() - jeśli występuje, musi być ostatnie.
• struct implikuje new() (każdy typ wartościowy ma niejawny konstruktor bezparametrowy), więc tych dwóch nie wolno łączyć.

public class Warehouse<T> where T : class, IIdentifiable, new()
//                              └─pierwsze─┘             └─ostatnie─┘

Przykład: bezpieczny generyczny kontener #

Zbudujmy system warehouseowy. Każdy przechowywany obiekt musi mieć identyfikator. Najpierw kontrakt dla danych:

public interface IIdentifiable
{
    int Id { get; set; }
}

public class Product : IIdentifiable
{
    public int Id { get; set; }
    public string Name { get; set; }
    public double Cena { get; set; }
}

Teraz kontener z trzema ograniczeniami na raz:

// T: klasa, implementuje IIdentifiable, ma konstruktor bezparametrowy
public class Warehouse<T> where T : class, IIdentifiable, new()
{
    private readonly List<T> _items = new List<T>();

    public void Add(T element)
    {
        // Dzięki ograniczeniu IIdentifiable kompilator wie, że element ma Id
        if (_items.Exists(e => e.Id == element.Id))
        {
            Console.WriteLine($"Błąd: element o Id {element.Id} już istnieje");
            return;
        }
        _items.Add(element);
    }

    public T FindById(int id)
    {
        // Wiemy, że T to klasa, więc null jest dopuszczalny jako "nie znaleziono"
        return _items.Find(e => e.Id == id);
    }

    public T CreateNew()
    {
        // Dzięki ograniczeniu new() możemy utworzyć obiekt typu T w trakcie działania
        T nowy = new T();
        _items.Add(nowy);
        return nowy;
    }
}

Użycie wymusza typ na etapie kompilacji:

Warehouse<Product> warehouse = new Warehouse<Product>();
warehouse.Add(new Product { Id = 1, Name = "Laptop", Cena = 3500 });

// Warehouse<int> zly = new Warehouse<int>();
// BŁĄD KOMPILACJI - int nie jest klasą i nie implementuje IIdentifiable

Pułapka: operator == przy where T : class #

Mając ograniczenie where T : class, łatwo ulec pokusie porównania dwóch T operatorem ==. Uważaj: dla parametru typu operator == sprawdza tożsamość referencji, a nie równość wartości - nawet jeśli konkretny typ (np. string) przeciąża ==. Kompilator widzi w tym miejscu jedynie “typ referencyjny” i sięga po domyślne porównanie referencji. Jeśli zależy ci na równości wartości, dodaj ograniczenie where T : IEquatable<T> i porównuj metodą Equals.

Podsumowanie tematu #

W tej części kursu poznałeś:

• Dlaczego generyki - ArrayList na object oznaczała błędy typów dopiero w trakcie wykonania oraz kosztowny boxing/unboxing. <T> przenosi kontrolę do kompilatora i eliminuje boxing
• List<T> - dynamiczna tablica, różnica Count kontra Capacity, podwajanie pojemności (0→4→8→16), Remove po wartości kontra RemoveAt po indeksie
• Dictionary<TKey, TValue> - tablica mieszająca z wyszukaniem bliskim O(1), TryGetValue zamiast wyjątku, nieokreślona kolejność iteracji, klucz nie może mutować
• HashSet<T> - zbiór unikalnych wartości na tej samej zasadzie haszowania
• Ograniczenia where - odblokowują składowe typu wewnątrz klasy generycznej, mają reguły kolejności (class/struct pierwsze, new() ostatnie), struct implikuje new()

W następnym wpisie LINQ w C# zajmiemy się LINQ - warstwą zapytań, która buduje na IEnumerable i pozwala filtrować, przekształcać oraz grupować kolekcje jednym, czytelnym łańcuchem wywołań.

Najpierw quiz i zadanie poniżej. Zadanie uruchomisz na żywo - przycisk Uruchom w modalu kompiluje twój kod na codapi.org.

using System;
using System.Collections.Generic;

public interface IIdentifiable
{
    int Id { get; set; }
}

public class Product : IIdentifiable
{
    public int Id { get; set; }
    public string Name { get; set; }
}

public class Warehouse<T> where T : class, IIdentifiable, new()
{
    private readonly List<T> _items = new List<T>();

    public void Add(T element)
    {
        if (_items.Exists(e => e.Id == element.Id))
        {
            Console.WriteLine($"Error: Id {element.Id} already exists");
            return;
        }
        _items.Add(element);
        Console.WriteLine($"Added item with Id {element.Id}");
    }

    public T FindById(int id)
    {
        return _items.Find(e => e.Id == id);
    }

    public void DisplayIds()
    {
        foreach (T element in _items)
        {
            Console.WriteLine($"Warehouse ID: {element.Id}");
        }
    }
}

public class Program
{
    public static void Main()
    {
        Warehouse<Product> warehouse = new Warehouse<Product>();

        warehouse.Add(new Product { Id = 1, Name = "Laptop" });
        warehouse.Add(new Product { Id = 2, Name = "Myszka" });
        warehouse.Add(new Product { Id = 1, Name = "Klawiatura" });

        Product found = warehouse.FindById(2);
        Console.WriteLine($"Found: {found.Name}");

        warehouse.DisplayIds();
    }
}