Las pruebas son estructuras de datos muy rápidas. Buscar una palabra toma el tiempo O (sizeofword), mientras que std::map s son árboles autoacabados. ¿Por qué no se implementan las plantillas estándar de mapas C++ con los intentos? ¿Hay alguna razón específica? ¿Hay alguna compensación de usar un trie en lugar de un árbol de auto-equilibrio?¿Por qué no se implementan los mapas C++ como intentos?
Tries solo se puede utilizar cuando las claves que se almacenarán se pueden procesar dígito por dígito o carácter por carácter. Los C++ std::map y std::set están diseñados para funcionar con cualquier elemento comparable como clave, y por lo tanto no pueden implementarse de manera que procesen las teclas carácter por carácter. En su lugar (normalmente) utilizan árboles de búsqueda binaria equilibrada, que no necesitan introspección en las claves y, en su lugar, pueden usar un comparador para realizar búsquedas rápidas.
Si está seguro de que ciertas propiedades se conservan para sus llaves, en algunos casos puede incluso ser mejor que intentarlo (vea el ejemplo van Emde Boas tree). Sin embargo, los diseñadores de bibliotecas tienen que diseñar para muchos casos de uso y, por lo tanto, pueden necesitar elegir opciones que son más lentas que la mejor opción, ya que necesitan manejar la mayor cantidad de opciones posibles.
Además, es perfectamente posible que una implementación conforme a C++ contenga una especialización de std::map o std::set que utiliza un trie cuando las claves son cadenas. No creo que haga nada, pero en teoría es posible.
Espero que esto ayude!
Para conjuntos de datos más pequeños, el árbol equilibrado es probablemente más eficiente que las implementaciones de trie más comunes. Encuentro que el trie realmente solo se vuelve eficiente con conjuntos de datos más grandes. –
¿Cómo utilizarías un trie para almacenar algo que no sea una cadena (o al menos similar a un hilo)? –
¿Cómo se obtiene la complejidad de O (n) para trie? – n0rd
@ n0rd: O (n)! = O (sizeofword) ... –