std :: mapa con acceso eficiente a elemento n

Question

Tengo un conjunto de datos que necesito almacenar en un mapa ordenado (es decir, con inserción, eliminación y ubicación eficiente de elementos por clave), pero también necesito estar capaz de encontrar el elemento nth sin recorrer todo el mapa (a veces puede haber decenas de miles de elementos en él).

Conozco una forma de hacerlo: use un árbol rojo/negro, pero mantenga también el número total de elementos secundarios en una de las patas de cada nodo. Hace que la inserción y la eliminación sean un poco más lentas (porque debe actualizar los recuentos en cada nodo a lo largo de la ruta como lo hace), pero puede encontrar el nth elemento para cualquier n casi al mismo tiempo que encuentra una clave .

Me pregunto si existe una implementación de C++ existente que pueda usar. Puedo escribirlo yo mismo si no, pero preferiría no hacerlo.

---

EDIT: Tengo algunas aclaraciones sobre el caso de uso para ello. Lo malentendí ligeramente: después de buscar un elemento por clave, necesitan la capacidad de averiguar de manera eficiente qué índice es el elemento encontrado, para mostrar correctamente las barras de desplazamiento.

Es es una necesidad legítima, y ​​la estructura de datos que describí anteriormente aún funcionará para él, así que todavía estoy buscando una respuesta. Pero como parece que nadie ha llegado con uno todavía, voy a comenzar a codificarlo yo mismo.

Answer 1

Esta es mi respuesta a otra pregunta considerando un problema similar.

associative/random access container

supongo que esto podría aplicarse también a su pregunta.

---

He estado buscando una estructura de datos de este tipo durante mucho tiempo.

Recientemente, encontré una biblioteca bastante prometedora que tiene toda la funcionalidad que está buscando.

Vea el cntree :: conjunto con acceso aleatorio en O (log n).

aquí está el enlace. http://dl.dropbox.com/u/8437476/works/countertree/index.html

Aunque parece estar en desarrollo, veo que es bastante utilizable.

Answer 2

Si usó un Trie modificado donde los nodos no terminales registraban cuántos nodos de terminal estaban debajo de él, podía hacer una búsqueda rápida ordenada.

Answer 3

Intente utilizar una lista std :: ordenada y use std :: binary_search para buscar. Se puede implementar una lista ordenada usando std :: list e insertando nodos usando std :: lower_bound. Hay muchos ejemplos de esto en la web y en SO.

Answer 4

Nunca he usado boost::multi_index_container<>, pero parece que podría tener la capacidad de hacer lo que quiera (aunque no estoy muy seguro, es una biblioteca bastante compleja a primera vista).

Tiene un tipo de clave de acceso aleatorio, pero no estoy seguro de cómo actualizaría el índice aleatorio de una manera que mantenga sincronizado el índice del elemento insertado con el orden del otro índice. Además, observe lo siguiente de la tutorial on using a random index:

Este añadido flexibilidad tiene un precio: inserciones y deleciones en las posiciones que no sean el final del índice tienen complejidad lineal, mientras que estas operaciones son constante de tiempo para índices secuenciados. Esta situación recuerda las diferencias en el comportamiento de complejidad entre std :: list y std :: vector: en el caso de los índices de acceso aleatorio, sin embargo, las inserciones y eliminaciones nunca incluyen la copia de elementos, por lo que el rendimiento real de estas operaciones puede ser aceptable , a pesar de la desventaja teórica con respecto a los índices secuenciados.

No me queda claro si eso sería un factor decisivo para usted o no, incluso si puede sincronizar el índice aleatorio para elementos insertados de la manera que desee.

Answer 5

Una opción sería desarrollar un contenedor que se base en std :: vector, pero que también tenga la interfaz del mapa. Almacenaría un hashtable o árbol binario separado que utiliza las claves de los elementos para acceder a ellos, pero los valores reales serían punteros en el conjunto interno utilizado por el vector.

Tal monstruosidad puede parecer insustancial, propensa a errores, o un olor de diseño por algunas personas, pero tal estructura de datos tiene su lugar. He visto esto usado en el código para controladores de hardware en sistemas minoristas, donde dos usuarios de un contenedor necesitan acceder a él de diferentes maneras. Cuando se usa "porque está allí", es algo malo, pero es un salvavidas cuando se usa correctamente.

Answer 6

MS VC STL mapa respaldado por un árbol negro rojo.

No creo que sea posible tener una búsqueda eficiente (por clave) y un acceso aleatorio eficiente en la misma estructura de datos.

Si el acceso aleatorio eficiente es realmente importante, sería mejor almacenar datos en un contenedor de acceso aleatorio similar al vector. El pedido y la búsqueda de claves se pueden realizar con índices adicionales. Los RDBMS están haciendo esto.

O, si la inserción/eliminación es más importante, parece evitable administrar algo como la matriz de teclas (o el índice de número de fila) para los accesos aleatorios.

Answer 7

Tarde en la fiesta (haga clic en esta pregunta mientras busca algo relacionado), pero ¿no sería adecuado un vector ordenado para el caso de uso aquí? El tiempo de inserción es peor, a menos que haga la mayoría o todas las inserciones en un lote antes de ordenar. Después de ese tiempo de búsqueda realmente puede vencer a std :: map, y obtener el índice es trivial.