Próby są bardzo szybkimi strukturami danych. Szukanie słowa zajmuje czas O (sizeofword), podczas gdy std::map s są samowystarczalnymi drzewami. Dlaczego nie są standardowe szablony map C++ zaimplementowane z próbami. Czy istnieje jakiś szczególny powód? Czy są jakieś kompromisy w używaniu drzewka zamiast drzewa samowyrównującego?Dlaczego mapy C++ nie są implementowane jako próby?
Tries może być używany tylko wtedy, gdy klucze do zapisania mogą być przetwarzane cyfra po cyfrze lub znak po znaku. C++ i std::set są zaprojektowane do pracy z dowolnymi porównywalnymi elementami jak klucze, a zatem nie mogą być zaimplementowane w taki sposób, aby przetwarzać klawisze znak po znaku. Zamiast tego (zwykle) używają zbalansowanych drzewek binarnych, które nie muszą dokonywać introspekcji na kluczach i zamiast tego mogą po prostu używać komparatora do szybkiego wyszukiwania.
Jeśli wiesz na pewno, że niektóre właściwości zawierają klucze, możesz w niektórych przypadkach zrobić to lepiej niż spróbować (przykład: van Emde Boas tree). Jednak projektanci bibliotek muszą zaprojektować wiele przypadków użycia, a zatem mogą potrzebować wybrać opcje, które są wolniejsze od absolutnie najlepszej opcji, ponieważ muszą obsługiwać jak największą liczbę opcji.
Co więcej, jest całkiem możliwe, że zgodna implementacja C++ zawiera specjalizację std::map lub std::set, która używa klucza, gdy klucze są ciągami. Nie wierzę, że ktokolwiek to robi, ale teoretycznie jest to możliwe.
Mam nadzieję, że to pomoże!
Dla mniejszych zestawów danych zrównoważone drzewo jest prawdopodobnie bardziej wydajne niż większość powszechnych implementacji trie. Uważam, że triest naprawdę staje się skuteczny tylko w przypadku większych zestawów danych. –
Jak używać trieta do przechowywania czegoś, co nie jest łańcuchem (lub co najmniej jak stringiem)? –
Jak masz złożoność O (n) dla trie? – n0rd
@ n0rd: O (n)! = O (sizeofword) ... –