Kontenery haszujące w Visual C++

W standardowej bibliotece pojemników (STL) języka C++ jest póki co poważny brak. Nie ma mianowicie kontenerów opierających się na mechanizmie haszowania (hashing), znanego też pod mniej jednoznaczną nazwą mieszania. Mówiąc zupełnie najprościej, takie pojemniki są pewnym uogólnieniem zwykłych tablic, które nie są jednak indeksowane liczbami całkowitymi, a kluczami dowolnego typu. Klucze te są jednak wpierw przepuszczane przez pewną funkcję (funkcję haszującą) i dopiero wynik używany jest do znalezienia wartości, z którą ów klucz jest związany. Istnieje też kilka metod rozwiązywania problemu kolizji, gdy kilka kluczy zostanie odwzorowanych na to samo miejsce w tablicy.
Zaletą haszowania jest szybkość: średnio dostęp do wartości związanej z danym kluczem jest wykonywanym w czasie stałym. Tak, stałym, czyli O(1). Jakkolwiek można być pesymistą i przewidywać, że przy odpowiednio złośliwym doborze kluczy czas ten urośnie do liniowego (O(n), ale w praktyce tablice haszujące zachowują się świetnie. No a to jest przecież najważniejsze :)

W STL nie ma jednak kontenerów używających haszowania. Mimo to wiele kompilatorów oferuje je we własnym zakresie. I tak nasz ulubiony Visual C++ udostępnia dwa “półstandardowe” nagłówki: hash_set i hash_map. Zawierają one klasy (multi)map oraz (multi)zbiorów, z wierzchu wyglądających właściwie identycznie jak zwykłe mapy i zbiory (std::map i std::set) z STL. Klasy te nazywają się hash_set, hash_map, itp., i celem zachowania zgodności ze standardem C++ umieszczone są nie w przestrzeni std, lecz stdext.

O istnieniu tych klas warto pamiętać, gdy tworzymy kod kluczowy pod względem wydajności. W programowaniu gier często są to na przykład przeróżne menedżery zasobów, które odwzorowują pewne identyfikatory (np. łańcuchy znaków) na obiekty w rodzaju modeli, tekstur, próbek dźwiękowych, itd. Szybkość działania przechowujących je pojemników może być ważna i warto poszukać alternatyw dla standardowej klasy map (która przecież teoretycznie “wyciąga” tylko O(logn) dla wyszukiwania). Jeśli przy okazji martwimy się przenośnością na inne kompilatory niż VC++ lub zgodnością ze standardem, to możemy spróbować przełączania między zwykłymi a haszującymi pojemnikami, np. tak:

Naturalnie ‘kod niezależny od kontenera’ to dość często utopia, ale przy korzystaniu tylko z prostych operacji typu wstawianie-usuwanie-wyszukiwanie nie powinniśmy napotkać większych problemów.

Be Sociable, Share!

• 
• 

Be Sociable, Share!

• 
• 

• Tweet
•