C++ i tablice asocjacyjne
2010-04-23 17:34Zwykł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:
- std::map<std::string, Foo*> m;
- // ...
- m["one"]->DoSomething();
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:
- m["two"] = new Foo();
- // klucz "two" nie występuje wcześniej w m
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
-
Sebas86:
April 23rd, 2010 o 19:46m[“two”] = new Foo();
Jest też sposobem zrobienia sobie kuku w przypadku gdy konstrukcja Foo się nie powiedzie, a “ufamy”, że taki kontener zawiera zawsze poprawne dane – jeśli konstruktor Foo rzuci wyjątkiem mamy piękny niezainicjowany wskaźnik lub w najlepszym przypadku obiekt, niewłaściwy inteligenty/automatyczny wskaźnik.
Fajnie wygląda taki kod, a człowiek jeszcze lepiej się bawi szukający miejsc w programie takich jak to. :)
Recent posts
