Kolekcje

Wcześniejszy wpis będący wprowadzeniem do kolekcji ograniczał się do opisania klasy List<T>. W tej notatce znajdziesz informacje dotyczące najróżniejszych kolekcji udostępnionych przez .NET Framework.

Wróćmy na moment do opisanej klasy List<T>, która udostępnia spore możliwości zarządzania kolekcją, lecz brakuje jej możliwości poinformowania o wprowadzanych zmianach. Twórcy wyszli z założenia, że będzie to nasza klasa, używana wewnętrznie. W sytuacji, gdy potrzebujemy monitorować wprowadzane zmiany, lepiej skorzystać z klasy Collection<T>, która została zaprojektowana jako bazowa kolekcja, na potrzeby dostępu publicznego. Wykorzystanie mechanizmu powiadomień wymaga przysłonięcia metod wirtualnych: InsertItem, SetItem, RemoveItem oraz ClearItems. W przeciwieństwie do List<T> nie został zapewniony rozbudowany mechanizm sortowania czy wyszukiwania, możliwość wyszukiwania ogranicza się do metody IndexOf. Klasa implementuje zarówno interfejs IList jak i IList<T>, a zatem oba mogą zostać udostępnione jako właściwość tworzonej kolekcji. Przykład poniżej nawiązuje do wcześniejszych przykładów bazujących na klasie ConfigFiles. Zachęcam do przygotowania kodu, tak aby podpiąć się pod zdarzenie Changed, a następnie przeprowadzić kilka operacji na kolekcji.

public class ConfigFiles : Collection<string>
{
    public event EventHandler<ChangedEventArgs> Changed;

    public ConfigFiles()
    {
        this.Add("web.config");
        this.Add("app.config");
        this.Add("nLog.config");
    }

    protected override void ClearItems()
    {
        base.ClearItems();
                
        if (Changed != null)
            Changed(this, new ChangedEventArgs(ChangeType.Clear, null, null));
    }

    protected override void InsertItem(int index, string item)
    {
        base.InsertItem(index, item);

        if (Changed != null)
            Changed(this, new ChangedEventArgs(ChangeType.Add, item, null));
    }

    protected override void SetItem(int index, string item)
    {
        string replaced = Items[index];
        base.SetItem(index, item);

        if (Changed != null)
            Changed(this, new ChangedEventArgs(ChangeType.Set, item, replaced));
    }

    protected override void RemoveItem(int index)
    {
        string item = Items[index];
        base.RemoveItem(index);
                
        if (Changed != null)
            Changed(this, new ChangedEventArgs(ChangeType.Remove, null, item));
    }
}

public class ChangedEventArgs : EventArgs
{
    public ChangedEventArgs(ChangeType change, string newValue, string oldValue)
    {
        ChangeType = change;
        NewValue = newValue;
        OldValue = oldValue;
    }

    public ChangeType ChangeType { get; private set; }
    public string NewValue { get; private set; }
    public string OldValue { get; private set; }
}

public enum ChangeType
{
    Add,
    Remove,
    Set,
    Clear
};

Poniżej zamieszczam fragment kodu korzystającego z klasy ConfigFiles.

Pokaż rozwiązanie

static void Main(string[] args)
{
    var configFiles = new ConfigFiles();
    configFiles.Changed += new EventHandler<ChangedEventArgs>(ConfigFiles_Changed);

    configFiles.Remove("nLog.config");
    configFiles.Add("connections.config");
    configFiles[2] = "database.config";

    foreach (var file in configFiles)
        Console.WriteLine(file);

    Console.ReadLine();
}

private static void ConfigFiles_Changed(object sender, ChangedEventArgs e)
{
    switch (e.ChangeType)
    {
        case ChangeType.Add:
            Console.WriteLine("Add: {0}", e.NewValue);
            break;

        case ChangeType.Remove:
            Console.WriteLine("Remove: {0}", e.OldValue);
            break;

        case ChangeType.Set:
            Console.WriteLine("Set: {0} => {1}", e.OldValue, e.NewValue);
            break;

        case ChangeType.Clear:
            Console.WriteLine("Clear");
            break;
    }
}

Kolejną liniową kolekcją udostępnioną przez .NET Framework jest ReadOnlyCollection<T>. Jest to kolekcja tylko do odczytu. Nie tylko nie można dodawać czy usuwać, ale również nie można zastępować wartości. Klasa implementuje interfejs IList<T>, jednak próba zapisania powoduje zgłoszenie wyjątku. Oczywiście w przypadku typów referencyjnych po uzyskaniu referencji nic nie stoi na przeszkodzie, aby zmodyfikować czy zastąpić obiekt. Klasy ReadOnlyCollection<T> można używać jako opakowania dla istniejącej listy (posiada wyłącznie konstruktor pozwalający na przekazanie obiektu typu IList<T>), lub utworzyć klasę pochodną na jej podstawie. Poniżej przykład zastosowania klasy.

public class ConfigFiles : ReadOnlyCollection<string>
{
    public ConfigFiles() : this(new[] { "web.config", "app.config", "nLog.config" })  
    { 
    }

    public ConfigFiles(IList<string> list) : base(list)
    {
    }
}

Przed przejściem do następnej kolekcji, warto zwrócić uwagę na klasę List<T>, a dokładniej na jej metodę AsReadOnly, która to za nas tworzy opakowanie na kolekcję wyłącznie do odczytu.

ReadOnlyCollection<string> configFiles = new List<string> { "web.config", "app.config", "nLog.config"}.AsReadOnly();

.NET Framework udostępnia klasę Dictionary<TKey, TValue> będącą kolekcją słownikową oraz jak się można domyśleć interfejs IDictionary<TKey, TValue>. Od wersji 4.5 dostępna jest kolekcja ReadOnlyDictionary<TKey, TValue> przeznaczona tylko do odczytu. Kolekcja słownikowa reprezentuje parę klucz - wartość. Pierwszy z argumentów typu TKey reprezentuje klucz i jest wykorzystywany do wyszukiwania. Natomiast TValue jest typem wartości skojarzonym z kluczem. Największą zaletą takiej kolekcji jest dostęp do wartości na podstawie klucza. Jak zastosować taką tablicę w praktyce? Załóżmy, że mamy przygotować klasę CacheUser odpowiedzialną za pobieranie oraz przechowywanie informacji o operatorach systemu. Klasa ma udostępniać metodę GetUser, która zwraca obiekt typu User. Najważniejszym elementem będzie kolekcja słownikowa Dictionary<int, User>, gdzie kluczem będzie identyfikator operatora, natomiast wartość reprezentuje klasa User. Kolekcja udostępnia indeksatory, dzięki czemu wartość można pobrać przekazując klucz _CacheUsers[userID]. Niemniej, w sytuacji gdy klucz nie będzie dostępny w słowniku, zgłoszony zostanie wyjątek KeyNotFoundException. Metoda ContainsKey umożliwia weryfikację czy podany klucz znajduje się w słowniku.

public class CacheUser
{
    private Dictionary<int, User> _CacheUsers = new Dictionary<int, User>();

    public User GetUser(int userID)
    {
        if (!_CacheUsers.ContainsKey(userID))
            _CacheUsers.Add(userID, LoadUser(userID));

        return _CacheUsers[userID];
    }

    private User LoadUser(int userID)
    {
        return User.Generate(); // Load from database
    }
}

public class User
{
    public string Firstname { get; set; }

    ///
    /// Properties 
    ///

    public static User Generate()
    {
        var user = new User();
        user.Firstname = Guid.NewGuid().ToString();

        return user;
    }
}

Przykład powyżej korzysta z indeksatora do pobrania wartości skojarzonej z kluczem. Ta sama składnia umożliwia dodanie elementu słownika.

_CacheUsers[userID] = LoadUser(userID);

Zastosowana metoda Add, jednoznacznie oznajmia, że nie spodziewamy się, aby podany klucz istniał w słowniku. O ile indeksator "milcząco" podmienia wartość, o tyle metoda Add zgłosi wyjątek.

Powyższy przykład działa, ale można zrobić to efektywniej. Metoda GetUser rozpoczyna od sprawdzenia, czy klucz znajduje się w słowniku, w razie potrzeby dodaje element do słownika. Następnie ponownie wyszukuje element, po to, aby go zwrócić. Metoda TryGetValue wyszukuje element słownika skojarzonego z kluczem, zwracając wynik typu bool oraz wartość słownika poprzez drugi parametr metody.

public User GetUser(int userID)
{
    User user = null;
    if (!_CacheUsers.TryGetValue(userID, out user))
        _CacheUsers.Add(userID, user = LoadUser(userID));

    return user;
}

Interfejs IDictionary<TKey, TValue> wymaga implementacji ICollection<KeyValuePair<TKey, TValue>> oraz IEnumerable<KeyValuePair<TKey, TValue>>. Wszystkie wymienione interfejsy korzystają ze struktury KeyValuePair<TKey, TValue> będącej kontenerem składającym się z klucza oraz wartości, dzięki czemu możliwe jest przejście przez elementy korzystając z pętli foreach. Kolekcja słownikowa udostępnia również składnię inicjalizatora kolekcji, wygląda ona nieco inaczej niżeli w przypadku list. Dodatkowo konstruktor słownika umożliwia przekazanie implementacji typu IEqualityComparer. W przykładzie poniżej zastosowana została klasa StringComparer (link do dokumentacji) oferująca różny sposób porównywania łańcuchów znaków.

var dayOfWeek = new Dictionary<string, int>(StringComparer.CurrentCultureIgnoreCase) {
    { "Sunday", 0 },
    { "Friday", 5 },
    { "Saturday", 6 },
};

Oprócz opisanych kolekcji słownikowych udostępnione zostały słowniki posortowane SortedDictionary<TKey, TValue> oraz SortedList<TKey, TValue>. W przypadku słownika SortedList<TKey, TValue> nazwa jest myląca, gdyż nie implementuje IList<T>, a IDictionary<TKey, TValue>. W przeciwieństwa do kolekcji Dictionary<TKey, TValue> oraz IDictionary<TKey, TValue> nie działają w oparciu o kody mieszające, przez co wyszukiwanie elementu jest wolniejsze. Obie klasy pozwalają na określenie własnej logiki sortowania. Klasa SortedDictionary<TKey, TValue> zapewnia porządek sortowania podczas korzystania z jej enumeracji, np. w pętli foreach. Natomiast klasa SortedList<TKey, TValue> dodatkowo zapewnia możliwość pobierania kluczy i wartości przy użyciu indeksów liczbowych. Kolekcja udostępnia właściwości Keys, oraz Values w formie obiektów IList<TKey> oraz IList<TValue> posortowanych rosnąco.

Kolejnym typem kolekcji są zbiory (HashSet oraz SortedSet) korzystające z interfejsu ISet<T>. Jest to prosta kolekcja umożliwiająca dodawanie, usuwanie oraz sprawdzenie przy pomocy metody Contains czy dany element należy do zbioru. Zbiór nie posiada informacji o liczbie elementów. Metoda Add działa nieco inaczej. Zwraca wartość typu bool, określającą czy dodany element występował już w zbiorze. Interfejs ISet<T> udostępnia kilka metod łączących zbiory (wymagają przekazania argumentu IEnumerable<T>). Pierwsza z nich UnionWith dodaje wszystkie elementy, które nie występują w zbiorze. Metoda ExceptWith usuwa wszystkie elementy, które występują w przekazanej kolekcji. Natomiast IntersectWith usuwa wszystkie elementy które nie znajdują się w przekazanej kolekcji. Najciekawsza metoda SymmetricExceptWith usuwa ze zbioru elementy występujące w przekazanej kolekcji i jednocześnie dodaje do niej elementy, które wcześniej nie znajduowały się w zbiorze.

var dayOfWeek = new HashSet<string>(new[] { "Sunday", "Friday", "Saturday" });
dayOfWeek.SymmetricExceptWith(new[] { "Tuesday", "Friday" });

foreach (var day in dayOfWeek)
    Console.WriteLine(day);

Metody IsSubsetOf umożliwiają sprawdzenie czy zbiór zawiera wyłącznie przekazane elementy. Natomiast IsProperSubsetOf wymaga aby przynajmniej jedna z przekazanych elementów nie znajduje się w zbiorze. Metody IsSupersetOf oraz IsProperSupersetOf sprawdzają odwrotny warunek, a Overlaps porównywane kolekcje mają co najmniej jeden wspólny element.

var dayOfWeek = new HashSet<string>(new[] { "Sunday", "Friday", "Saturday" });
bool result;

result = dayOfWeek.IsSubsetOf(new[] { "Tuesday", "Friday" });
Console.WriteLine("IsSubsetOf = {0} (Tuesday, Friday)", result);

result = dayOfWeek.IsSubsetOf(new[] { "Tuesday", "Friday", "Saturday", "Sunday" });
Console.WriteLine("IsSubsetOf = {0} (Tuesday, Friday, Saturday, Sunday)", result);

result = dayOfWeek.IsProperSubsetOf(new[] { "Friday", "Saturday", "Sunday" });
Console.WriteLine("IsProperSubsetOf = {0} (Friday, Saturday, Sunday)", result);

result = dayOfWeek.IsProperSubsetOf(new[] { "Friday", "Saturday", "Sunday", "Tuesday" });
Console.WriteLine("IsProperSubsetOf = {0} (Friday, Saturday, Sunday, Tuesday)", result);

Klasa HashSet przypomina działanie Dictionary<TKey, TValue>, w której wyszukiwanie odbywa się na podstawie kodów mieszających. Klasa SortedSet co sugeruje nazwa, przechowuje elementy w sposób posortowany.

Kolejka jest specyficzną listą (FIFO - ang. first-in, first-out), zapewniającą możliwość odczytania oraz usunięcia wyłącznie pierwszego elementu. W wielu przypadkach to ograniczenie sprawia, że kolejki są mniej użyteczne niż listy, gdzie możliwy jest odczyt, usuwanie oraz wstawianie w dowolnym miejscu. To samo ograniczenie sprawia, że klasa Queue<T> jest znacznie wydajniejsza podczas operacji odczytu, usuwania czy wstawiania elementu. Metoda Enqueue dodaje nowy element na końcu kolejki. Z kolei do usuwania pierwszego elementu korzysta się z metody Dequeue, która w odpowiedzi zwraca usunięty element. Odczyt pierwszego elementu bez jego usuwania realizujemy poprzez metodę Peek. Kolejka udostępnia również metodę Count, zwracającą liczbę elementów. Wykonanie metod: Dequeue oraz Peek w przypadku pustej kolekcji zakończy się zgłoszeniem wyjątku typu InvalidOperationException. Kolejka implementuje interfejs IEnumerable<T>, dzięki czemu możliwe jest przejście przez jej zawartość. Konstruktor umożliwia przekazanie początkowego rozmiaru lub obiektu implementującego interfejs IEnumerable<T>.

var dayOfWeek = new Queue<string>(new[] { "Sunday", "Friday", "Saturday" });
dayOfWeek.Enqueue("Tuesday");
var remove = dayOfWeek.Dequeue();

foreach (var day in dayOfWeek)
    Console.WriteLine(day);

Stos jest strukturą danych podobną do kolejki, przy czym elementy wstawiane oraz pobierane są z jej końca (LIFO - ang. last-in, first-out). Klasa Stack<T> zamiast metod: Enqueue oraz Dequeue implementuje Push, oraz Pop, metoda Peek pozostaje bez zmian.

var dayOfWeek = new Stack<string>(new[] { "Sunday", "Friday", "Saturday" });
dayOfWeek.Push("Tuesday");
var remove = dayOfWeek.Pop();

foreach (var day in dayOfWeek)
    Console.WriteLine(day);

.NET Framework udostępnia klasę LinkedList<T> stanowiącą dwukierunkową listę, w której element umieszczony jest wewnątrz LinkedListNode<T>. Każdy z elementów zawiera informację o poprzedzającym oraz następującym elemencie. Zaletą list połączonych jest wydajność podczas wstawiania czy usuwania elementów, natomiast wadami są: wysokie zużycie pamięci, obciążenie procesora oraz konieczność przejścia przez n elementów. Dostęp do pierwszego oraz ostatniego elementu realizują właściwości: First oraz Last. Nowe elementy możemy dodawać zarówno na początku poprzez metodę AddFirst jak i na końcu wykorzystując AddLast. Korzystając z metod AddBefore oraz AddAfter możliwe jest wstawienie elementu poza początkiem i końcem. W parametrach oprócz wstawianego elementu przekazujemy obiekt typu LinkedListNode<T>, będącym lokalizacją do miejsca w liście, w który wstawiony zostanie element. Klasa udostępnia kilka metod usuwających: RemoveFirst oraz RemoveLast usuwają pierwszy bądź ostatni element. Metoda Remove posiada dwa przeciążenia, które umożliwiają usunięcie pierwszego elementu o określonej wartości lub wskazanie konkretnego elementu poprzez przekazanie LinkedListNode<T>.

var nodes = new LinkedList<string>(new[] { "Sunday", "Friday", "Saturday" });
var monday = nodes.AddAfter(nodes.First, "Monday");
nodes.AddBefore(nodes.Find("Friday"), "Thursday");
            
foreach (var node in nodes)
    Console.WriteLine(node);

Typ LinkedList<T> implementuje interfejs IEnumerable<T>, dzięki czemu możliwe jest przejście przez wszystkie elementy. Dodatkowo klasa LinkedListNode<T> posiada właściwości Next, Previous oraz Value typu T, dzięki czemu możliwe jest przejście do następnego lub poprzedniego elementu. Lista połączona umożliwia przejście przez elementy od tyłu, zaczynając od właściwości Last oraz korzystając Previous. Pokazuje to przykład poniżej.

var previousDay = nodes.Last;
while(previousDay != null)
{
    Console.WriteLine(previousDay.Value);
    previousDay = previousDay.Previous;
}

Wszystkie opisane do tej pory kolekcje zostały zaprojektowane z myślą o działaniu w obrębie jednego wątku. Oczywiście możemy korzystać z dowolnej kolekcji wielowątkowo, pod warunkiem, że zastosujemy mechanizm synchronizacji, który usystematyzuje dostęp do kolekcji. Wyjątkiem jest sytuacja, w której kolekcja wykorzystywana jest przez wiele wątków o ile żaden z nich nie będzie jej modyfikował.

Klasy ConcurrentQueue<T> oraz ConcurrentStack<T> są kolekcjami współbieżnymi, przypominającymi Queue<T> oraz Stack<T> choć niezupełnie. W przypadku kolejki metody Dequeue oraz Peek zostały zastąpione przez TryDequeue oraz TryPeek. W scenariuszach wielowątkowych nie możemy założyć, że próba odczytu bądź usunięcia elementu zakończy się sukcesem. Nawet jeżeli przed wykonaniem operacji sprawdzimy czy kolejka zawiera co najmniej jeden element, może dojść do sytuacji, w której pomiędzy sprawdzeniem, a operacją inny wątek, usunie element. Chcąc mieć pewność, że operacja zakończy się sukcesem musielibyśmy zapewnić "niepodzielność" pomiędzy sprawdzeniem, a wykonaniem operacji, a to wiąże się z zablokowaniem kolekcji. Dlatego projektanci zapewnili metody, które mogą zakończyć się niepowodzeniem bez zgłoszenia wyjątku. W przypadku stosu metody Pop oraz Peek zostały zastąpione przez TryPop oraz TryPeek.

Udostępniona została klasa BlockingCollection<T>, która działa jak kolejka, o specyficznych cechach. W sytuacji gdy kolekcja będzie pusta, a nastąpi próba pobrania elementu, wątki pobierające mogą zostać zablokowane do momentu pojawienia się elementów. Możliwe jest również określenie pojemności i w przypadku gdy kolejka będzie zapełniona, blokować wątki próbujące wstawić element, aż do momentu zwolnienia miejsca.

Typ ConcurrentDictionary<TKey, TValue> również nawiązuje do swojego niewspółbieżnego odpowiednika. Przy czym udostępnione zostały dodatkowe metody zapewniające niepodzielność. Metoda TryAdd łączy w sobie sprawdzenie, czy klucz występuje w słowniku z próbą dodania. Natomiast metoda GetOrAdd wykonuje to samo, a dodatkowo zwraca istniejącą wartość, o ile taka już istnieje.

.NET Framework nie udostępnia listy działającej wielowątkowo. Powodem jest złożoność zapewnienia indeksowanych i posortowanych list w działaniu współbieżnym. Na pocieszenie dodana została klasa ConcurrentBag<T> reprezentująca nieuporządkowaną kolekcję obiektów (bezpieczną wątkowo). Oprócz działającej w sposób naturalny metody Add posiada również TryPeek zwracającą obiekt bez jego usuwania oraz TryTake która usuwa zwrócony element. Więcej informacji o tej kolekcji znajdziesz tutaj.

Zaprezentowane kolekcje zapewniają spore możliwości. W zależności od potrzeb możemy wybierać pomiędzy prostymi zbiorami, wydajnymi listami połączonymi kończąc na kolekcjach współbieżnych. Po notatkach dotyczących tablic oraz kolekcji zostały do omówienia krotki. Zapraszam do kolejnego wpisu.