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

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ń ;-)