Contenedor para una pila de elementos únicos

Lo que estoy tratando de hacer es construir una pila que contenga elementos únicos.Contenedor para una pila de elementos únicos

Y si un elemento es empujado a la que ya está en la pila el elemento no está presionado, pero el elemetn existente se debe mover a la parte superior de la pila, es decir ABCD + B> ACDB

me gustaría aquí desde usted, qué contenedor será la mejor opción para tener esta funcionalidad.

decidí adaptador de pila de usuario sobre lista, porque

lista

proporciona la constante de tiempo para el elemento de movimiento
es uno de los contenedores compatibles de forma nativa para la pila.

El inconveniente de mi elección es que tengo que verificar manualmente los elementos duplicados.

P.S. Mi compilador no es tan reciente, así que no sugiera unordered_set.

Fuente

2012-08-23 deimus

Incluso sin un compilador reciente todavía puede usar [boost :: unordered_set] (http://www.boost.org/doc/libs/release/doc/html/boost/unordered_set.html) (no es que parezca) apropiado para esta tarea). – Mankarse

Gracias por la solución de impulso pero me gustaría aquí smth desde stl – deimus

Si 'unordered_set' es una posibilidad (aparte del soporte del compilador), ¿por qué no usas un' std :: set' normal entonces? Como sea que lo mires, 'std :: list' es la peor solución posible. Ni siquiera lo consideres. 'std :: vector' va a ser mucho más eficiente. –

Básicamente debe elegir entre movimiento constante en el tiempo + búsqueda larga, o búsqueda de tiempo constante + movimiento prolongado.

Es difícil decir que sería más lento, pero considera esto:

Usted tendrá que buscar si existe el elemento de cada vez que se intenta añadir un elemento
Usted será no tiene que mover elementos cada vez, ya que obviamente en algún momento agregará elementos que son "nuevos" para el contenedor.

le sugeriría para almacenar elementos y sus posiciones pila en diferentes contenedores. Almacene elementos de forma que proporcione una búsqueda rápida, almacene posiciones de pila de forma que proporcione un movimiento rápido. Conecte ambos con punteros (para que pueda saber qué elemento está en qué posición, y qué posición retiene qué elemento < - frase desordenada, ¡lo sé!), Y ejecutará cosas bastante rápido.

Fuente

2012-08-23 10:35:48 SingerOfTheFall

¡Gracias por la respuesta! Me gusta tu solución Básicamente, el número de elementos en la pila no será más de 20, y la comparación de elementos debe ser una comparación única de ints. Así que supongo que la lista es suficiente para esto, ¿verdad? – deimus

@deimus, sí, para cantidades tan pequeñas de datos, no verá ninguna diferencia en el rendimiento, por lo que está bien. – SingerOfTheFall

@deimus: para 20 enteros, use 'std :: vector' y una búsqueda lineal. Encajará en un solo trozo de memoria (garantizado por el vector) y, por lo tanto, una sola línea de caché de la CPU. Probablemente sea la solución más rápida disponible para usted (incluso si la búsqueda es en teoría lineal). –

Según sus requisitos, me parece que la estructura que desea podría derivarse de un Max Heap.

Si en lugar de almacenar solo el elemento, almacena un par (generación, artículo), con generación proveniente de un contador que aumenta monótonamente, entonces la "raíz" del montón siempre es el último elemento visto (y los otros elementos) realmente no importa, ¿verdad?).

pop: la operación pop típica en el montón (delete-max operación)
empuje: modificar el funcionamiento, para dar cuenta de la singularidad del "elemento" dentro de la estructura
- aspecto de "elemento", si se encuentra al día su generación (increase-key operación)
- si no, insertarlo (insert operación)

Dado el número de elementos (20), crear el montón en un vector parece una opción natural.

Fuente

2012-08-23 14:19:08

Contenedor para una pila de elementos únicos

Respuesta

Cuestiones relacionadas