¿Hay una estructura de datos que no permite duplicados y también mantiene el orden de entrada?

Question

duplicado:Choosing a STL container with uniqueness and which keeps insertion ordering

Busco una estructura de datos que actúa como un conjunto en el que no permite duplicados para ser insertados, pero también conoce el orden en el que se insertan los artículos. Básicamente sería una combinación de un conjunto y una lista/vector.

Solo usaría una lista/vector y buscaría duplicados, pero necesitamos que la verificación duplicada sea rápida ya que el tamaño de la estructura puede ser bastante grande.

Answer 1

Eche un vistazo a Boost.MultiIndex. Puede que tenga que escribir un envoltorio sobre esto.

Answer 2

Escribir su propia clase que envuelve un vector y un conjunto parecería la solución obvia: no hay un contenedor de biblioteca estándar de C++ que haga lo que desee.

Answer 3

Solo usaría dos estructuras de datos, una para el pedido y otra para la identidad. (Uno podría señalar el otro si almacena valores, dependiendo de qué operación desea que sea el más rápido)

Answer 4

Suena como un trabajo para un OrderedDictionary.

Answer 5

La verificación duplicada que es rápida parece ser la parte crítica aquí. Usaría algún tipo de mapa/diccionario tal vez, y realizar un seguimiento de la orden de inserción usted mismo como los datos reales. Entonces, la clave son los "datos" que está introduciendo (que luego son hash, y no permite las claves duplicadas), y coloca el tamaño actual del mapa como "datos". Por supuesto, esto solo funciona si no tienes ninguna eliminación. Si lo necesita, simplemente tenga una variable externa que incremente en cada inserción, y el orden relativo le indicará cuándo se insertaron las cosas.

No necesariamente es bonito, pero tampoco es tan difícil de implementar.

Answer 6

Boost.Bimap con el orden de inserción como un índice debería funcionar (por ejemplo, boost :: bimap < size_t, Foo>). Si está eliminando objetos de la estructura de datos, necesitará rastrear el siguiente valor de orden de inserción por separado.

Answer 7

Suponiendo que usted está hablando ANSI C++ aquí, yo escribiría el mío o usaría composición y delegación para envolver un mapa para el almacenamiento de datos y un vector de las claves para el orden de inserción. Dependiendo de las características de los datos, es posible que pueda usar el índice de inserción como su clave de mapa y evitar el uso del vector.

Answer 8

Java tiene esto en forma de un conjunto ordenado. No creo que C++ tenga esto, pero no es tan difícil de implementar. Lo que hicieron los Sun chicos con la clase Java fue extender la tabla hash de modo que cada elemento se insertara simultáneamente en una tabla hash y se mantuviera en una lista de doble enlace. Hay muy poca sobrecarga en esto, especialmente si preasigna los elementos que se utilizan para construir la lista vinculada.

Si estuviera donde usted, escribiría una clase que utilizara un vector privado para almacenar los elementos o implementar una tabla hash en la clase usted mismo. Cuando se va a insertar un elemento en el conjunto, verifique si está en la tabla hash y opcionalmente reemplace el elemento si ese elemento está en él. Luego, busca el elemento anterior en la tabla hash, actualiza la lista para que apunte al elemento nuevo y listo.

Para insertar un nuevo elemento, haga lo mismo, excepto que debe usar un nuevo elemento en la lista; no puede reutilizar los anteriores.

Para eliminar un elemento, puede volver a ordenar la lista para señalarlo y liberar el elemento de la lista.

Tenga en cuenta que debe poder obtener la parte de la lista vinculada donde el elemento que le interesa es directamente del elemento para que no tenga que caminar la cadena cada vez que tenga que moverse o cambiar un elemento.

Si prevé tener muchos de estos elementos cambiados durante la ejecución del programa, es posible que desee mantener una lista de los elementos de la lista, de modo que simplemente pueda tomar el encabezado de esta lista, en lugar de asignar memoria cada vez que tiene que agregar un nuevo elemento.

Es posible que desee ver el algoritmo de enlaces de baile.