C# i zbiory
2010-06-08 16:39
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:
- public class Set<T> : ICollection<T>, IEnumerable<T>
- {
- private Dictionary<T, object> set;
- public void Add(T item) { set.Add(item, null); }
- public void Clear() { set.Clear(); }
- public bool Contains(T item) { return set.ContainsKey(item); }
- public void CopyTo(T[] array, int arrayIndex)
- { set.Keys.CopyTo(array, arrayIndex); }
- public int Count { get { return set.Count; } }
- public bool IsReadOnly { get { return false; } }
- public bool Remove(T item) { return set.Remove(item); }
- public IEnumerator<T> GetEnumerator()
- { return set.Keys.GetEnumerator(); }
- IEnumerator IEnumerable.GetEnumerator()
- { return (set.Keys as IEnumerable).GetEnumerator(); }
- }
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 :)
-
KrystianD:
June 8th, 2010 o 19:27nie było w v2.0 :) w v3.5 jest HashSet ;)
-
Xion:
June 8th, 2010 o 20:27Ha, no to najwyższy czas :) Widać od ostatniego razu, gdy potrzebowałem w C# zbioru, minęło już wystarczająco długo ;)
-
nilphilus:
June 8th, 2010 o 22:00Właśnie chciałem napisać, że lepiej HashSet użyć, no ale mnie ubiegli ;-)
-
nilphilus:
June 8th, 2010 o 22:03eniłej, nie można by LINQ do tego wykorzystać?
Recent posts
