string_id
2.0:3
A menudo es útil para fines de registro en aplicaciones en tiempo real como juegos para darle un nombre a cada entidad. Esto facilita el seguimiento de los errores porque encontrar entidades a través de nombres únicos es más fácil que mirar números únicos u otras formas de identificadores. Pero las cadenas son enormes y copiarlas y compararlas es lenta, por lo que a menudo no se pueden usar en el código crítico de rendimiento.
Una solución son las cadenas de hash que son solo enteros y, por lo tanto, pequeñas, rápidas de copiar y comparar. ¡Pero los hashes no permiten recuperar el valor de la cadena original, que es exactamente lo que se necesita para fines de registro y depuración! Además, existe una posibilidad de colisiones, por lo que el código hash igual no significa necesariamente cadenas iguales. Esta oportunidad es pequeña, pero una fuente de errores difíciles de encontrar.
Otra solución es la interiores de cadena. String Interning utiliza una tabla de búsqueda global donde cada cadena se almacena solo una vez y se hace referencia a través de un índice o algo similar. Copiar y comparar también es rápido, pero todavía no son perfectos: solo puedes acceder a ellos en tiempo de ejecución. No es posible obtener el valor en el tiempo de compilación, por ejemplo, un interruptor.
Entonces, por un lado, queremos identificadores rápidos y livianos, pero por otro lado, también métodos para recuperar el nombre.
Esta biblioteca de código abierto proporciona una mezcla entre las dos soluciones en forma de clase String_ID . Cada objeto almacena un valor de cadena hash y un puntero a la base de datos en la que se almacena el valor de cadena original. Esto permite recuperar el valor de la cadena cuando es necesario, al tiempo que obtiene los beneficios de rendimiento de las cadenas de hash. Además, la base de datos puede detectar colisiones que se pueden manejar a través de un controlador de colisión personalizado. Hay un literal definido por el usuario para crear un valor de cadena hash de tiempo de compilación para usarlo como una expresión constante.
La base de datos puede ser cualquier tipo definido por el usuario derivado de una determinada clase de interfaz. Hay varias bases de datos predefinidas. Esto incluye una base de datos ficticia que no almacena nada, un adaptador para otras bases de datos para que sean threadsafe y una base de datos altamente optimizada para almacenar y recuperar cuerdas eficientes. Un typedef default_database es una de esas bases de datos y se puede configurar a través de las siguientes opciones de CMake:
Foonathan_String_id_Database : si está apagado , la base de datos está deshabilitada por completo, por ejemplo, se usa la base de datos ficticia. Esto no permite recuperar cadenas o verificación de colisiones, pero no necesita tanta memoria. Está activado por defecto.
Foonathan_string_id_multithreaded : si está encendido , el acceso a la base de datos se sincronizará a través de un mutex, por ejemplo, se utilizará el adaptador seguro de subproceso. No tiene ningún efecto si la base de datos está deshabilitada. El valor predeterminado está activado .
Hay clases de generadores especiales. Tienen una interfaz similar a los generadores de números aleatorios en las bibliotecas estándar, pero generan identificadores de cadenas. Esto se utiliza para generar un montón de identificadores de manera automatizada. Los generadores también tienen cuidado de que siempre hay nuevos identificadores generados. Esto también se puede controlar a través de un controlador similar al manejo de colisiones.
Ver ejemplo/main.cpp para un ejemplo.
Actualmente utiliza un hash de 64 bits FNV-1A. Las colisiones son realmente raras, he probado 219,606 palabras en inglés (en minúsculas) mezcladas con un montón de números y no encontré una sola colisión. Dado que este es el caso de uso normal para los identificadores, la función hash es bastante buena. Además, hay una buena distribución de los valores de hash y es fácil de calcular.
La base de datos utiliza una tabla hash especializada. Las colisiones del índice de deseos se resuelven mediante encadenamiento separado con una lista vinculada única. Cada nodo contiene la cadena directamente sin asignación de memoria adicional. Los nodos en la lista vinculada se ordenan utilizando el valor hash. Esto permite una recuperación eficiente y verificación de si ya hay una cadena con el mismo valor hash almacenado. Esto lo hace muy eficiente y más rápido que el std :: unordered_map que se usó antes (al menos más rápido que la implementación de libstdc ++ que he usado para los puntos de referencia).
Esta biblioteca ha sido compilada bajo los siguientes compiladores:
Existen las opciones de compatibilidad y el reemplazo de Marcos para operadores de Constexpr, Noexcept, anulación y literal. Las funciones del controlador atómico se pueden deshabilitar opcionalmente y están apagados para GCC 4.6 de forma predeterminada, ya que no las admite.
