C# i zbiory

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 :)

Co może udawać obiekt w C++

Możliwości przeciążania operatorów w C++ dla własnych typów obiektów sprawiają, że mogą one (tj. te obiekty) zachowywać się w bardzo różny sposób. Mogą na przykład “udawać” pewne wbudowane konstrukcje językowe, nierzadko wykonując ich zadania lepiej i wygodniej. Przykładów na to można podać co najmniej kilka – oto one:

• Obiekt może zachowywać się jak funkcja, czyli udostępniać możliwość “wywołania” siebie z określonymi parametrami. Takie twory często nazywa się funktorami i bywają używane podczas pracy ze standardową biblioteką STL.
  Działają one przy tym w bardzo prosty sposób, zwyczajnie przeciążając operator nawiasów okrągłych (). Jest on na tyle elastyczny, że może przyjmować dowolne parametry i zwracać dowolne rezultaty, co pozwala nawet na stworzenie więcej niż jednego sposobu “wywoływania” danego obiektu. Jednym z bardziej interesujących zastosowań dla tego operatora jest implementacja w C++ brakującego mechanizmu delegatów, czyli wskaźników na metody obiektów.
• Na podobnej zasadzie obiekt może udawać tablicę – wie o tym każdy, kto choć raz używał klas STL typu vector. Wymagane jest tu przeciążenie operatora indeksowania []. Daje ono wtedy dostęp do elementów obiektu-pojemnika, który zresztą nie musi być wcale indeksowany liczbami, jak w przypadku tablic wbudowanych (dowodem jest choćby kontener map). Ograniczeniem jest jedynie to, że indeks może być (naraz) tylko jeden, bo chociaż konstrukcja typu:
  1. v[3,4] = 5;

  jest składniowo najzupełniej poprawna, to działa zupełnie inaczej niż można by było się spodziewać :)

• Obiekty mogą też przypominać wskaźniki, które wtedy określa się mianem ‘sprytnych’ (smart pointers). Dzieje się tak głównie za sprawą przeciążenia operatorów * (w wersji jednoargumentowej) i ->. Normalnie te operatory nie mają zastosowania wobec obiektów, ale można nadać im znaczenie. Wtedy też mamy obiekt, który zachowuje się jak wskaźnik, czego przykładem jest choćby auto_ptr z STL-a czy shared_ptr z Boosta.
• Wreszcie, obiekt może też działać jako flaga boolowska i być używany jako część warunków ifów i pętli. Sprytne wskaźniki zwykle to robią, a innymi wartymi wspomnienia obiektami, które też takie zachowanie wykazują, są strumienie z biblioteki standardowej. Jest to spowodowane przeciążeniem operatora logicznej negacji ! oraz konwersji na bool lub void*.

Reasumując, w C++ dzięki przeciążaniu operatorów możemy nie tylko implementować takie “oczywiste” typy danych jak struktury matematyczne (wektory, macierze, itp.), ale też tworzyć własne, nowe (i lepsze) wersje konstrukcji obecnych w języku. Szkoda tylko, że często jest to wręcz niezbędne, by w sensowny sposób w nim programować ;)

C++ i tablice asocjacyjne

Zwykłe tablice (jednowymiarowe) w “normalnych” językach programowania to po prostu ciągłe obszary pamięci, do których pierwszego elementu posiadamy odwołanie. Dostęp do kolejnych polega na korzystaniu z arytmetyki wskaźników, więc niedziwne jest, że takie tablice indeksuje się wyłącznie liczbami – i to z określonego zakresu.
Ci, którzy programowali w na przykład w Pythonie lub PHP znają jednak koncepcję tablic asocjacyjnych, dla których to ograniczenie nie obowiązuje. W C++ do ich symulowania używa się często map z STL-a:

Jest to oczywiście odpowiednie przeciążenie operatora [], a map jest rodzajem pojemnika. Skoro jednak ma to udawać tablicę, to dobrze by było, żeby narzut na obsługę dostępu do elementów nie różnił się zbytnio od tego z prawdziwych tablic. A ten, jak wiemy, jest stały.

Jak to osiągnąć?… Przede wszystkim powinniśmy – jeśli tylko możemy – nie korzystać z kontenera map. Problem z nim polega na tym, że poświęca on dużo uwagi sortowaniu elementów według ich kluczy (“indeksów”). Gdy klucze te są złożone – bo są nimi np. łańcuchy znaków – może to zająć trochę czasu i jednocześnie nie dawać nam żadnej korzyści. Dla tablicy asocjacyjnej najważniejsze są bowiem operacje wyszukiwania wartości (“indeksowania”) i dodawania nowych elementów, względnie ich usuwania. To one muszą działać szybko; wewnętrzny porządek elementów nie jest dla nas istotny.
Dlatego też lepsza jest mapa korzystająca z dobrodziejstw mechanizmu haszowania. W Visual C++ (podobnie zresztą jak w GCC) takie cudo dostępne jest od dawna jako klasa hash_map. Długo było ono niestandardowym rozszerzeniem biblioteki STL, ale wraz z nową wersją standardu staje się ono jego częścią. Poza tym “od zawsze” istnieje też rozwiązanie z Boosta w postaci klasy unordered_map. Przyjemną cechą wszystkich tych implementacji jest niemal jednolity interfejs, tożsamy ze standardową klasą map.

Oprócz używania właściwego pojemnika powinniśmy też wiedzieć, jak go z niego korzystać – a dokładniej mówiąc, czego unikać. Felerną operacją jest próba dodania elementu poprzez zwykłe indeksowanie z przypisaniem:

Skutkuje to stworzeniem na chwilę obiektu domyślnego dla danego typu wartości, a potem jego zastąpieniem (przypisaniem) tym właściwym, który ma się w ‘tablicy’ znaleźć. W przypadkach, gdy konstruktor i operator przypisania nie są trywialne, będzie to strata na wydajności. Powinniśmy więc używać raczej metody insert do wstawiania. Może jest to niezupełnie “tablicowe”, ale cóż – albo rybka, albo akwarium ;P

Nowoczesne wyliczanie

W chyba każdy języku posiadającym pojemniki (jak wektory czy listy) istnieje koncepcja iteratorów: obiektów, które pozwalają na przeglądanie kolekcji i są uogólnieniem wskaźników. W najprostszym pozwalają one tylko na pobranie aktualnego elementu i przejście do następnego, ale jest to zupełnie wystarczające do celów wyliczania.
Z wierzchu więc wyglądają one całkiem prosto i przejrzyście – zwłaszcza, jeśli język udostępnia pętlę typu foreach, która ładnie i przezroczyście je opakowuje. Dlatego może wydawać się dziwne, czemu zazwyczaj mechanizm ten jest używany właściwie tylko dla pojemników; w teorii bowiem za pomocą iteratorów (zwanych gdzieniegdzie enumeratorami) można by było przeglądać dosłownie wszystko.
Weźmy chociażby wyszukiwanie plików na dysku – sporo programów w jakimś momencie swojego działania musi znaleźć pliki np. o danej nazwie w określonym katalogu. Wtedy zwykle zakasujemy rękawy i piszemy odpowiednią procedurę rekurencyjną lub bawimy się ze stosem czy kolejką. A czy nie fajniej byłoby, gdyby dało się to zrobić po prostu tak:

oczywiście przeszukując w ten sposób również podkatalogi bez jawnego “wchodzenia” do nich?… Według mnie to by było bardzo fajne :)

Od razu zaznaczę więc, że wbrew pozorom taki iterator jest jak najbardziej możliwy do napisania. Problemem jest jednak to, jak należy przechowywać jego stan. Kiedy wyszukiwanie czy przeglądanie zaimplementowane jest bezpośrednio jako jedna funkcja, robi się to w zasadzie samo: w postaci zmiennych lokalnych (stos/kolejka) albo parametrów (rekurencja). Nikt specjalnie nie zwraca na ten fakt uwagi. Jednak w momencie próby “wyciągnięcia” z algorytmu operacji Next (w celu stworzenia iteratora) okazuje się nagle, że wymaga to jawnego pamiętania tych wszystkich danych, które pozwalają obliczyć następny element. Przy przeszukiwania katalogów trzeba by na przykład pamiętać jakiś systemowy uchwyt wyszukiwania dla aktualnego katalogu, poziom zagnieżdżenia oraz analogiczne uchwyty… dla każdego takiego poziomu!
Zawracanie głowy, prawda? :) Nic dziwnego, że traktowanie wyszukiwania “per iterator” nie jest popularną praktyką. Z punktu widzenia piszącego algorytm wyliczania nieporównywalnie łatwiej jest po prostu wymusić jakiś callback i wywołać go dla każdego elementu; niech się programista-klient martwi o to, jak ten callback wpasować w swój kod. A że ten byłby o wiele czytelniejszy, gdyby w grę wchodziły iteratory? No cóż, iteratorów tak łatwo pisać się nie da…

…chyba że programujemy w Pythonie. Tam bowiem “iteratory” (zwane generatorami) piszemy w zupełnie unikalny, łatwy sposób. Weźmy dla przykładu taką oto klasę drzewa binarnego (BST – Binary Search Tree):

I już – to wystarczy, by poniższa pętla:

rzeczywiście “chodziła” po krawędziach drzewa “w czasie rzeczywistym” – bez żadnego buforowania elementów na liście.

Tajemnica tkwi tutaj w instrukcji yield – działa ona jak “tymczasowe zwrócenie” elementu, który jest przetwarzany przez ciało pętli for. Gdy konieczny jest następny element, funkcja inorder podejmuje po prostu działanie począwszy od kolejnej instrukcji – i tak do następnego yielda, kolejnego cyklu pętli i dalszej pracy funkcji. yield działa więc jak callback, tyle że w obie strony. Całkiem zmyślne, czyż nie?
Aż chciałoby się zapytać, czy w innych językach – zwłaszcza kompilowanych – nie dałoby się zrobić czegoś podobnego. Teoretycznie odpowiedź jest pozytywna: przy pomocy zmyślnych sztuczek na stosie wywołań funkcji (technika zwana ‘nawijaniem stosu’ – stack winding) można uzyskać efekt “zawieszenia funkcji” po zwróceniu wyniku i mieć możliwość powrotu do niej począwszy od następnej instrukcji. Nie jestem jednak przekonany, jak taki feature mógłby współpracować z innymi elementami współczesnych języków programowania, jak choćby wyjątkami. Trudno powiedzieć, czy jest to w ogóle możliwe.

Ale skoro w Pythonie się da, to może już C++2x będzie to miał? ;-)

Usuwanie z kontenerów STL

Teoretycznie najlepszym sposobem na usuwanie elementów z pojemników STL jest posłużenie się idiomem erase–remove:

W praktyce bywa on dość kłopotliwy jeśli stosowany predykat (tutaj oznaczony jako funktor ToBeDeleted) musi być napisany specjalnie do tego celu. Zresztą gra często nie jest warta świeczki, bo implementacje algorytmów w rodzaju remove to w środku często nic innego, jak zwykłe pętle.

No a pętle możemy przecież napisać sobie sami, prawda?… Otóż nieprawda – zwłaszcza jeśli wcześniej nie pomyślimy przez chwilę. Łatwo bowiem wyprodukować coś takiego:

Z poprawnością ma to niewiele wspólnego. Jeśli bowiem natrafimy na element do usunięcia, to po dokonaniu tego (w nagłówku pętli) zinkrementujemy iterator, który na ów usunięty element wcześniej pokazywał. W ten sposób możemy pominąć element następny, bo go zwyczajnie “przeskoczymy”. Odpowiednik powyższej pętli używający zwykłego licznika i operatora [] jest zresztą obarczony identycznym problemem.
Jak więc usuwać? Umiejętnie, rzecz jasna :) Skoro po skasowaniu jednego elementu pozostałe przesuną się o jedno miejsce do tyłu, nie powinniśmy zawsze bezmyślnie przechodzić dalej. Trzeba to robić tylko wtedy, gdy dany element zostawiliśmy w spokoju:

To w sumie całkiem oczywiste, jeśli chwilę się nad tym zastanowić. Bowiem – w przeciwieństwie do dodawania – usuwanie elementów z kontenerów wymaga właśnie chwili zastanowienia :]

Prawie jak mapa

Każda porządna biblioteka pojemników posiada kontener w typie mapy lub słownika, który służy do przechowywania par klucz-wartość, czyli odwzorowywania jednych na drugie. Zwykle pojemnik taki jest zaimplementowany przy pomocy odpowiednio zarządzanej struktury drzewiastej. I tak np. w C++ mamy od tego klasę std::map, w .NET – System.Collections.Generic.Dictionary, a w Javie cały zestaw klas implementujących interfejs java.util.Map.

Czasami jednak korzystanie z tego typu rozwiązań może być strzelaniem z armaty do komara. Jeśli bowiem:

• nasze klucze nie są typami złożonymi (np. łańcuchami znaków), a raczej wartościami wyliczeniowymi
• nie jest ich zbyt dużo, zwłaszcza w stosunku do ilości pamięci, którą możemy zająć
• przypisane kluczom wartości nie są dużymi obiektami
• istnieją dla nich rozsądne ustawienia domyślne

to możemy zastosować o wiele prostsze rozwiązanie. Polega ono na użyciu typu wyliczeniowego dla kluczy:

oraz zwykłej tablicy do przechowywania wartości (tutaj typu bool):

Proste i skuteczne, a i nieco wygodniejsze składniowo niż standardowe std::map. A także wybitnie mało odkrywcze; podejrzewam, że każdy średnio zaawansowany programista miał okazję zetknąć się z podobną “sztuczką”. Co jednak nie znaczy, że nie warto o niej czasem wspomnieć i zrobić dobry uczynek w postaci propagowania dobrych i sprawdzonych rozwiązań ;-)

Rozmiar a pojemność

Od kiedy w Bibliotece Standardowej języka C++ istnieje szablon vector, nie trzeba się już martwić kłopotami z dynamiczną alokacją pamięci dla tablic o zmiennym rozmiarze. Szablon ten jest na tyle sprytny, że zapewnia wszystkie zalety zwykłych tablic – łącznie z możliwością uzyskania wskaźnika na ciągły obszar pamięci zawierający elementy. Jednocześnie sam kontroluje rozmiar tablicy oraz wykorzystanie pamięci.
W sensownej implementacji STL jest to osiągnięte poprzez strukturę samorozszerzalnej tablicy. W skrócie można to określić jako alokację większej ilości pamięci niż faktycznie potrzeba – po to, aby dodawanie nowego elementu trwało w przybliżeniu czas stały (w tzw. sensie zamortyzowanym). Całkowita ilość pamięci wykorzystywana aktualnie przez wektor to jego pojemność i jest ona możliwa do pobrania metodą capacity (zwraca ona liczbę elementów, które jeszcze się zmieszczą bez realokacji). Natomiast metoda size zwraca liczbę aktualnie zawartych w tablicy obiektów, czyli jej rozmiar.
Istotne jest, aby te dwie wartości rozróżniać. Kiedy zaś zrównają się ze sobą, następne dodanie elementu wymusi ponowną alokację bloku pamięci dla całej tablicy (zwykle dwukrotnie większego) i przekopiowanie jej zawartości w nowe miejsce.

Taka operacja jest oczywiście kosztowna (liniowa względem rozmiaru tablicy) i dlatego chcielibyśmy, żeby odbywała się jak najrzadziej. Używając metody reserve możemy naraz zaalokować pamięć na tyle elementów, ile będziemy potrzebowali – a więc zwiększyć jej pojemność (lecz nie rozmiar!), jak to widać na poniższym mało inteligentnym przykładzie:

Tworzymy tutaj kopię wektora, używając konstruktora kopiującego. Trik polega na tym, że w czasie tworzenia tej kopii zostanie przydzielona dokładnie taka ilość pamięci, jaka jest potrzebna dla elementów wektora. Potem jeszcze zamieniamy ten chwilowy wektor z oryginalnym… i już :)