¡La pequeña joya de la corona!
Esta pequeña joya se incorpora en la segunda versión del engine, ya que en la primera no estaba presente. Básicamente viene a hacer la función de contenedor especial para los objetos del engine.
Pero porque tanta historia por una estructura que podía haber sido tranquilamente un vector o una lista? Pues porque esta estructura permite el acceso directo a los objetos O(1) mediante un ‘Ticket’ y también permite la búsqueda de los objetos mediante O(log(n)), o lo que es lo mismo, el tiempo de acceso de un árbol balanceado Red-Black.
Os he puesto un trozo de papel, de los muchos que uso, para que podáis ver como se gestó la idea. La idea se basa en almacenar un objeto X y obtener a cambio un puntero no a ese objeto sino a un objeto ticket que nos permitirá acceso a ese objeto X en un futuro. Esto nos crea una capa de encapsulación al mismo tiempo que nos brinda un acceso rápido y eficiente.
La estructura almacena los objetos en un árbol Red-Black, o lo que es lo mismo, en un árbol de tipo Map de las STL. Este árbol juntamente con un vector son linkados mediante iteradores para poder viajar de forma rápida por toda la estructura. El vector en cada casilla contiene dos iteradores, uno hacia ‘abajo’ para poder linkar el árbol, y otro hacia ‘arriba’ para poder linkar la lista de ‘Tickets’.
Por último, para encapsular toda la estructura externa el acceso se hace mediante una lista que contiene tickets. Estos tickets tienen unos ID’s que son usados para acceder al vector anteriormente mencionado y finalmente de este al árbol.
Paralelamente a esto se puede hacer una búsqueda mediante una key (la que nos requiere el map) para poder buscar el objeto que queramos.
Esta estructura también está preparada para mantener una sola copia de cada elemento, al igual como hacer DirectX con sus numeraciones internas llamadas referencias.
Y lo mejor de todo, la reorganización interna de los datos, NO afecta al exterior en ningún momento, lo que nos permite hacer cargas dinámicas en cualquier momento de la ejecución al igual como descargas dinámicas.
Un saludo
