W kilku różnych miejscach przeczytałem, że przy użyciu nowych literałów ciągów C ++ 11 może być możliwe obliczenie skrótu ciągu w czasie kompilacji. Jednak nikt nie wydaje się być gotowy, aby wyjść i powiedzieć, że będzie to możliwe i jak to się stanie.
- czy to możliwe?
- Jak wyglądałby operator?
Jestem szczególnie zainteresowany takimi przypadkami użycia.
void foo( const std::string& value )
{
switch( std::hash(value) )
{
case "one"_hash: one(); break;
case "two"_hash: two(); break;
/*many more cases*/
default: other(); break;
}
}
Uwaga: funkcja skrótu czasu kompilacji nie musi wyglądać dokładnie tak, jak ją napisałem. Zrobiłem wszystko, co w mojej mocy, aby odgadnąć, jak będzie wyglądało ostateczne rozwiązanie, ale meta_hash<"string"_meta>::value
mogło też być rozwiązaniem wykonalnym.
c++
metaprogramming
c++11
hash
deft_code
źródło
źródło
Odpowiedzi:
To trochę za późno, ale udało mi się zaimplementować funkcję CRC32 w czasie kompilacji przy użyciu
constexpr
. Problem polega na tym, że w chwili pisania tego tekstu działa tylko z GCC, a nie z kompilatorem MSVC ani Intel.Oto fragment kodu:
CrcVal01
jest równe 0x335CC04AMam nadzieję, że to ci pomoże!
źródło
constexpr
nie jest dostępny w VS2013, z wyjątkiem listopada 2013 CTP blogs.msdn.com/b/vcblog/archive/2013/11/18/ ...Przynajmniej po przeczytaniu przeze mnie § 7.1.5 / 3 i §5.19, poniższe mogą być uzasadnione:
Wydaje się, że jest to zgodne z podstawowymi zasadami w §7.1.5 / 3:
Pojawia się pytanie, czy
*input
s wiążą się z niedozwoloną konwersją lwartości na rwartość, i nie jestem pewien, czy rozumiem reguły w §5.19 / 2/6/2 1 i § 4.1 na tyle dobrze, aby być tego pewnym.Z praktycznego punktu widzenia ten kod jest akceptowany przez (na przykład) g ++, przynajmniej od g ++ 4.7.1.
Użycie byłoby takie jak:
Aby spełnić wymagania §5.19 / 2/6/2, może być konieczne wykonanie czegoś takiego:
źródło
constexpr
, 2: Nie masz warunku zatrzymania (gdzie*input == nullptr
) i jak rozumiemconstexpr
, nie możesz go mieć.(unsigned)-1
jeśli taki istnieje; i zwraca 1 dla wszystkich innych ciągów. Przepisać za pomocą trójargumentowego operatora warunkowego?Jest to próba jak najdokładniejszego rozwiązania problemu PO.
przykład na żywo .
Uwaga główną różnicę -
std::hash
nie może być stosowany, jako że nie mamy kontroli nadstd::hash
algorytmem „s, a my musi reimplement go jakoconstexpr
w celu ocenienia go w czasie kompilacji. Ponadto, nie ma "przezroczystych" hashówstd
, więc nie możesz (bez tworzeniastd::string
) hashować surowego bufora znaków jako plikustd::string
.Wsadziłem do
std::string
niestandardowego hasher (z przezroczystegoconst char*
wsparcia) domy_hash
nazw, dzięki czemu można przechowywać go wstd::unordered_map
jeśli trzeba konsystencję.Oparty na doskonałej odpowiedzi @ JerryCoffin i wątku komentarzy pod nią, ale z próbą napisania go z aktualnymi najlepszymi praktykami C ++ 11 (w przeciwieństwie do przewidywania ich!).
Zwróć uwagę, że użycie „surowego skrótu” w
switch
instrukcjicase
jest niebezpieczne. Będziesz chciał==
później przeprowadzić porównanie, aby potwierdzić, że zadziałało.źródło
Ten fragment oparty na fragmencie Clement JACOB. Ale działa też z brzękiem. I powinien być szybszy na kompilacji (ma tylko jedno wywołanie rekurencyjne, a nie dwa jak w oryginalnym poście).
Zobacz dowód słuszności koncepcji tutaj
źródło
Zwróć uwagę, że przedstawiony tutaj formularz nie został przyjęty do standardu, jak wspomniano poniżej.
Zakłada się, że przetwarzanie ciągu znaków czasu kompilacji stanie się możliwe dzięki literałom zdefiniowanym przez użytkownika, zaproponowanym w N2765 .
Jak już wspomniałem, nie znam żadnego kompilatora, który obecnie go implementuje, a bez wsparcia kompilatora można tylko zgadywać.
W §2.13.7.3 i 4 projektu mamy:
Połącz to z
constexpr
i powinniśmy mieć przetwarzanie ciągu czasu kompilacji.aktualizacja: przeoczyłem, że czytałem niewłaściwy akapit, ta forma jest dozwolona dla literałów całkowitych zdefiniowanych przez użytkownika i literałów zmiennoprzecinkowych, ale najwyraźniej nie dla literałów -string (§ 2.13.7.5).
Wydaje się, że ta część wniosku nie została przyjęta.
Biorąc to pod uwagę, z moim ograniczonym spojrzeniem na C ++ 0x, może to wyglądać mniej więcej tak (najprawdopodobniej coś mi się nie udało):
Jeśli podejście Jerrysa działa, to jednak powinny działać:
źródło
constexpr
literału zdefiniowanego przez użytkownika. Nie jestem pewien, czy można użyć literału ciągu jako parametru szablonu, czy nie mają one statycznego powiązania? (robią co najmniej w C ++ 98 i dlatego są verboten jako parametry szablonu).operator ""_hash
działa dla mnie w Xcode 5.0.2.Inne rozwiązanie oparte na rozwiązaniu Clementa JACOBa, wykorzystujące C ++ 11 constexpr (nie rozszerzony C ++ 14), ale mające tylko jedną rekursję.
Jakieś wyjaśnienie
combine_crc32
pozwala nam przechowywać wynik rekursji pod zmiennąpart
i używać jej dwukrotnie. Ta funkcja jest obejściem ograniczenia C ++ 11, które nie zezwala na deklaracje zmiennych lokalnych.ctcrc32
Funkcja oczekuje ciągiem znaków, który jest przekazywany jakoconst char (&)[len]
. W ten sposób możemy pobrać długość łańcucha jako parametr szablonu i nie musimy polegać na makrach.źródło
Następujące prace w GCC 4.6.1 i można użyć jednej
hash
lubpack
w blokach rozdzielczych.GCC pozornie (?) Nie pozwala wywołań cyklicznych gdzie przechodzimy
s+1
zes
wskaźnikiem, dlatego używamoff
zmienną.źródło
Jeśli masz kompilator C ++ 17 i string_view, staje się to trywialne, po prostu napisz normalną wersję:
źródło
crc32("mystring")
(zwykle VS to robi). Sztuczka pozwalająca obejść ten problem polega na utworzeniu zmiennej constexpr, która zależy od oceny czasu kompilacji twojego crc32. Zazwyczajconstexpr uint32_t val = crc32("mystring");
Oto kolejna implementacja C ++ 11 (oparta na odpowiedzi @ CygnusX1), która działa zarówno z tablicami constexpr char, jak i ciągami uruchomieniowymi:
Potrzebujesz,
str.size() + 1
ponieważlen
w drugim przeciążenie jeststrlen(str) + 1
spowodowane znakiem null na końcu.Nie dodałem przeciążenia for,
const char *
ponieważ miesza się z drugim przeciążeniem - możesz łatwo dodać przeciążenia dlaconst char *, size_t
lubstd::string_view
.źródło
To miłe pytanie.
Na podstawie odpowiedzi Jerry'ego Coffina stworzyłem kolejny, który jest zgodny ze std :: hash programu Visual Studio 2017.
https://github.com/manuelgustavo/cx_hash
źródło
Wciąż brakowało mi wariantu dosłownego crc32 (co nie jest możliwe w przypadku szablonów), więc oto moja sugestia oparta na CygnusX1 . Zrobiłem jakieś testy, nie wahaj się przekazać opinii.
Testet na MSVC.
PS: Nienawidzę szukać dodatkowych rzeczy gdzie indziej, więc skopiowałem tabelę CRC na dole mojej odpowiedzi.
Alternatywa z algorytmem Dana Bernsteina (djb2) (połączone odpowiedzi od Jerry'ego Coffina + Georga Fritzsche'a )
Stół CRC32:
źródło