Dłuższy czas temu popełniłem notkę o tym, że w C# (lub szerzej: w .NET) brakuje pewnych struktur danych, które niekiedy bywają przydatne. Jedną z nich jest bardzo prosty rodzaj pojemnika: zbiór.
Zbiory (w programowaniu) to kontenery, które przechowują elementy niepowtarzające się i umożliwiają szybkie sprawdzenie, czy jakaś wartość do danego zbioru należy. ‘Szybkie’ oznacza tu złożoność logarytmiczną (względem rozmiaru pojemnika) lub lepszą. Podstawowa różnica w stosunku do zbiorów matematycznych jest natomiast taka, iż te drugie mogą zawierać elementy różnych rodzajów, podczas struktura danych o tej nazwie przechowuje obiekty jednego typu.
W C++ zbiór implementuje STL-owa klasa std::set
. W C# z kolei – jak napisałem na początku – jej odpowiednika nie ma. Takowy trzeba by dopiero napisać, co w przypadku tego języka jest raczej zaskakujące :) Tym niemniej da się to zrobić w miarę prosto, używając do tego… klasy Dictionary
. Pomysł polega na tym, żeby całkowicie zignorować tę jej część, która kluczom w słowniku pozwala przypisywać wartości. Zamiast tego interesują nas wyłącznie same klucze jako elementy naszego zbioru. Zarys klasy opartej o tę ideę może wyglądać choćby tak:
Skorzystanie ze słownika (klasy Dictionary
) sprawia, że kluczowa operacja Contains
(sprawdzenie przynależności) jest bardzo szybka. MSDN podaje, że wydajność odpowiadającej jej operacji słownikowej ContainsKey
“zbliża się do O(1)”. Mamy tu też oczywiście niezbędne metody do dodawania i usuwania elementów, a także kilka innych związanych z implementowanymi interfejsami ICollection
i IEnumerable
, które pozwalają na przykład na iterowanie po zbiorze pętlą foreach
.
Można naturalnie jeszcze ulepszyć tę klasę, dodając nowe konstruktory, metody i implementując następne interfejsy (na przykład ISerializable
). Nie jest to trudne, bo polega głównie na wywoływaniu odpowiadających metod obiektu Dictionary
lub jego kolekcji kluczy. Dopiero operacje matematyczne – jak suma i iloczyn zbiorów – wymagałoby nieco większej ilości kodu.
Ale przecież dla chcącego nic trudnego :)
nie było w v2.0 :) w v3.5 jest HashSet ;)
Ha, no to najwyższy czas :) Widać od ostatniego razu, gdy potrzebowałem w C# zbioru, minęło już wystarczająco długo ;)
Właśnie chciałem napisać, że lepiej HashSet użyć, no ale mnie ubiegli ;-)
eniłej, nie można by LINQ do tego wykorzystać?