Oto jedna z takich sytuacji. Jutro robimy w szkole pierwsze z serii spotkań zorientowanych bezpośrednio pod kątem matury z informatyki (jest nas w liceum całe pięć osób :)), więc postanowiłem, że podzielę się z resztą własną wiedzą i doświadczeniem, przy okazji samemu sobie utrwalając wszystko. Na pierwszy ogień poszło zadanie "Słowa" z poprzedniej matury, a konkretnej jeden z podpunktów, gdzie należało wczytać do pamięci listę słów i określić, ile z nich się powtarza. Nie jest to skomplikowane do wykonania, a biorąc pod uwagę fakt, że podczas egzaminu plik z danymi liczył tylko 1000 słów, było wręcz trywialne, bowiem nawet najgłupszy, acz poprawny algorytm, dawał odpowiedź niemal błyskawicznie. Najgłupszy mnie nie zadowalał, więc zwiększyłem rozmiar pliku 100 razy i zakodowałem jeszcze dwa inne sposoby obliczenia wyniku. W każdym z nich używany był STL.

Najdłużej zeszło mi z algorytmem wykorzystującym tablice haszujące do wyszukiwania elementów. Na warsztat poszła klasa hash_map z STL-a, będąca wprawdzie nieoficjalnym rozszerzeniem firmy SGI, ale szerokodostępnym. Napisawszy kod, przystępuję do próby jego kompilacji i powstaje problem, ponieważ g++ zgłasza po kilkanaście komunikatów błędów, na pół ekranu każdy. Odnalezienie czegokolwiek sensownego w tym gąszczu znaczków oraz identyfikatorów graniczyło z cudem. Stopniowo wydobywałem z tej masy numery linii i z pomocą bożą usuwałem kolejne usterki (a to niekompatybilność typów, a to brak jakiegoś parametru...). Zniknął wreszcie ostatni błąd składni, puszczam kompilację i... zgłasza się linker, tym razem nie pasuje mu coś znowu w nagłówkach hash_table. Rzecz jasna trafił mnie szlag (jakby mało było tych trzech dotychczasowych kwadransów). Okazało się, że znacznie szybciej zeszło mi z napisaniem własnej, mocno uproszczonej, ale działającej, jak trzeba, tablicy haszującej opartej o prosty std::vector.

class zyxHash
{
	public:
		zyxHash(long int buckets)
		{
			bucketNum = buckets;
			
			bucketList = new vector<slowo*>[bucketNum];
		} // end zyxHash();
 
		// zwalniania pamieci nie chcialo mi sie pisac
		// do tego zadania nie bylo to potrzebne
		
		void insert(string key, slowo *s)
		{
			unsigned long int hash = hashFunc(key);
			bucketList[hash].push_back(s);
		} // end insert();
		
		slowo *find(string key)
		{
			unsigned long int hash = hashFunc(key);
			vector<slowo*> *bt = &bucketList[hash];
			for(long int i = 0; i < bt -> size(); i++)
			{
				if(key == (*bt)[i]->word)
				{
					return (*bt)[i];
				}			
			}
			return 0;
		} // end find();
	private:
		long int hashFunc(string k)
		{
			unsigned long int hash = 0;
			long int i;
			long int key_len = k.length();
			
			for (i = 0; i < key_len; i++) {
				hash += k[i];
				hash += (hash << 10);
				hash ^= (hash >> 6);
			}
			hash += (hash << 3);
			hash ^= (hash >> 11);
			hash += (hash << 15);
 
			return hash % bucketNum;
		} // end hashFunc();
		
		long int bucketNum;
		
		vector<slowo*> *bucketList;
};

Po niecałych 10 minutach program był gotowy.

Z STL-a korzystam też w moim innym projekcie, pisanej z użyciem Turbo Vision aplikacji userist do zarządzania kontami użytkowników na serwerze wraz z ich katalogowaniem. Tam też miałem z nim nieco przebojów, lecz innej natury, mianowicie przekazywania zbiorów między poszczególnymi elementami interfejsu. Jednak mimo tych problemów bibliotekę oceniam dość pozytywnie. Nie trzeba się bawić ze strukturami danych, wszystko jest pod ręką. Jedyna wada jest taka, że gdy ktoś dopiero poznaje tajniki jej działania, czasami poziom złożoności API może człowieka zwyczajnie przerosnąć. Zastanawiam się, jak sprawdziłby się STL w interpreterze Revomera, gdzie mamy do czynienia z nietypową listą instrukcji. W sumie gdy zaczynaliśmy go pisać na warsztatach, jeden z uczestników też pukał się w czoło: po co własne struktury piszecie, skoro STL-a macie. Ale to temat na inną opowieść.

Powrót

Na Zyxist.com panuje swoboda wyrażania opinii oraz krytyki pod dowolnym adresem. Jedyny warunek: musi być ona kulturalna i rzeczowa. Na chamstwo, prostactwo lub jawne obrażanie kogokolwiek nie ma tu miejsca i takie komentarze są bardzo szybko usuwane. Jeśli zamierzasz polemizować z treścią wpisu, wpierw uważnie ją przeczytaj.