Witam. Ostatnimi czasy na forum pojawiło się parę tematów dotyczących switcha, który może przyjmować wartości typu string (a dokładniej literal string). Ze względu na sposób działania mechanizmu switcha taka operacja jest niemożliwa do wykonania, gdyż możemy korzystać jedynie z liczb całkowitych (np. 1, -8, 'a').
W C++11 (-std=C++11) specyfikator constexpr umożliwia nam wykonywanie pewnych operacji jeszcze w trakcie kompilacji i jego użycie będzie tutaj kluczowe. Przykładowe działanie:
// kod
constexpr int x = 4;
int y = x;
// w rzeczywistości będzie dla kompilatora wyglądał tak
int y = 4;
Można więc rzec, że constexpr jest aliasem dla pewnych stałych wartości - literałów (w tym wypadku dla 4). Dzięki temu możliwe jest napisanie takiego kodu (wynik działania oczywisty):
constexpr int _1 = 1;
constexpr int _2 = 2;
int x = 2;
switch(x)
{
case _1: std::cout<<"To jest jeden"; break;
case _2: std::cout<<"To jest dwa"; break;
}
Bez specyfikatora constexpr otrzymamy następujące błędy:
error: the value of '_1' is not usable in a constant expression
note: 'int _1' is not const
A więc mając odpowiednią funkcję przerabiającą literał stringa na postać liczbową, bez problemu możemy otrzymać pseudo switch od stringów. Tak prezentuje się przykładowy kod (u64 jest typedefem od unsigned long long):
std::string Str = "Ala ma kota";
u64 ID = HashStr(Str);
switch(ID)
{
case_str("Ala ma kota"): /* kod */ break;
case_str("Ala nie ma kota"): /* kod */ break;
case_str("To jednak dziala :D"): /* kod */ break;
}
Przejdźmy teraz do samej funkcji, twierdząc po nazwie, hashującej. W moim przypadku opiera się ona na algorytmie FNV-1a (Fowler–Noll–Vo), którego opis można znaleźć bez problemu na Wikipedii. Wyjaśniając w skrócie działanie algorytmu - dla każdego bajtu ciągu znaków wykonujemy operację XORa logicznego oraz mnożenia z wykorzystaniem dwóch liczb pierwszych.
hash = FNV_offset_basis
for each byte_of_data to be hashed
hash = hash XOR byte_of_data
hash = hash × FNV_prime
return hash
Po zaimplementowaniu tego algorytmu w postaci rekurencyjnej (ze względu na restrykcyjne wymagania specyfikatora constexpr) ma on postać następującą:
constexpr u64 HashStr(const char* Src, u64 Value = 0xcbf29ce484222325ull)
{
return (*Src) ? HashStr(Src+1,((*Src)^Value)*0x100000001b3ull) : Value;
}
// plus wersja dla std::string dla ułatwienia zapisu (NIE jest ona constexpr)
inline u64 HashStr(const std::string& Str)
{
return HashStr(Str.data());
}
// plus makro dla uładnienia konstrukcji switcha
#define case_str(x) case HashStr(x)
Istnieje teoretyczna możliwość kolizji dwóch wartości hashowych, lecz osobiście się z takową nie spotkałem i nie sądzę żeby była ona dotkliwa. W razie doraźnych problemów można zastosować inny algorytm hashujący.
Co do sensu stosowania tego zabiegu:
- szybkość przy większej ilości case'ów i dłuższych stringach
- wygoda stosowania (wiemy dokładnie od jakiej wartości przełączamy)
- satysfakcja ze zrobienia czegoś dość zaawansowanego
- zrozumienie constexpr oraz pojęcie jego możliwości optymalizacyjnych
Przykłady użycia:
- wszelkiego rodzaju skrypty (wykonywanie funkcji w zależności od danego ciagu znaków)
- ONP (jak wyżej)
- tworzenie aliasów
- enum E { _1 = Global["WindowX"] } // gdzie Global to zmienna constexpr
- co tylko Wam do głowy przyjdzie : )
Pytania, oceny, opinie, komentarze i ewentualne prośby o inne poradniki proszę zamieszczać niżej.
Mam nadzieję, że komuś poradnik się przyda. Dziękuję za uwagę i życzę miłego kodowania ^^
Linki:
http://en.cppreference.com/w/cpp/language/constexpr
https://pl.wikipedia.org/wiki/Funkcja_skr%C3%B3tu
https://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo_hash_function
