¿Cuál es la implementación más rápida del árbol de búsqueda binario? (auto-equilibrio)

Puede mejorar std :: map para que funcione mucho más rápido, simplemente, desde el exterior.

Una de las grandes penalizaciones de rendimiento de std :: map es su diseño de memoria, donde cada nodo se ubica aleatoriamente en el montón. Esta ubicación aleatoria de los nodos causa demasiados errores de caché y consecuentes accesos a la memoria, que son la parte más lenta en una CPU moderna. Otro potencial de desaceleración son las operaciones de almacenamiento dinámico.

Afortunadamente, es bastante trivial evitar la mayoría de las operaciones de almacenamiento dinámico, en su std :: map. Como notará std::map tiene un parámetro Allocator, que por defecto es std::allocator . Todo lo que tiene que hacer es escribir su propio asignador que asignará una gran parte de la memoria consecutiva, y lo dividirá en una lista de bloques más pequeños dimensionados con sizeof(Key) . Estos bloques formarán una lista libre, que administrará el asignador. Sospecho que fast_pool_allocator de Boost, como se describe en fast_pool_allocator, hace exactamente eso, por lo que no necesita implementarlo usted mismo. Desafortunadamente, la documentación de Boost es demasiado escasa y es imposible determinar qué hace exactamente y cómo puede afectar el diseño de la memoria (y no tengo tiempo para leer la implementación en este momento).

• ¿Qué hay de malo con este código C?
• En términos simples, ¿qué es la complejidad del tiempo amortizado?
• ¿Cuál es la forma más eficiente de verificar si un elemento es parte de un conjunto?
• ¿Cómo debo explicar Hashing a un niño de 4 años?
• Cómo elegir el algoritmo de selección de funciones correcto

Último comentario : asegúrese de que realmente necesita un árbol de búsqueda binario, y no una tabla hash (std :: unordered_map) y no un B-Tree, o incluso un vector (ordenado o no). En algunos casos, estos tendrán un rendimiento mucho mejor que cualquier implementación de árbol de búsqueda binaria. ¿Por qué menciono un vector sin clasificar, cuando busco en él es O (N)? Porque si tiene solo unos pocos elementos, por ejemplo, 4, escanearlos linealmente es mucho más rápido que cualquier otra alternativa.