¿Qué estructura de datos sería mejor para esto?

Question

Para mi juego, cuando un objeto ingresa en un sensor, necesito agregarlo a una lista, y cuando el objeto abandona el sensor, debe ser eliminado de esa lista. También necesito encontrar rápidamente ese objeto.

Así que, esencialmente:

necesito que haga: rápida adición, eliminación rápida y de búsqueda rápida.

¿Qué tipo de estructura de datos que sería mejor para este puesto que en un momento dado, el stucture tendrá unos 10 objetos.

Gracias

Answer 1

Con 10 objetos algo va a hacer (std::vector, deque o set), y nadie puede decir cuál funciona mejor antes de perfiles.

Si no sabe qué usar, quizás encontrará que std::set tiene una sintaxis más agradable para buscar elementos. Esto es lo que usaría en esta situación, porque no me gustaría escribir std::find(v.begin(), v.end(), sensor) donde simplemente podría escribir s.find(sensor).

Sin embargo, no use std::list, como recomendación general. Necesita una razón convincente para usar listas enlazadas en C++ (el empalme de tiempo constante es uno, la ausencia de invalidación de iterador es otra). Otras estructuras de datos funcionan mejor para la mayoría de las operaciones (excepto para el empalme). Aquí, no veo ningún sentido al usar list en lugar de, por ejemplo. set.

Answer 2

rápida adición, eliminación rápida y la búsqueda rápida, que no quiere hacer mucho usted! Dado lo que dijo, diría lista vinculada, pero también depende de qué tan frecuentes sean las adiciones, las eliminaciones y los hallazgos. Si está encontrando mucho más a menudo de lo que está agregando o borrando cosas, cambie.

realmente la única manera es que probar varios diferentes opciones y el tiempo de ellos.

Answer 3

Creo que una lista vinculada sería la mejor. Dado el tamaño pequeño, el acto de cambiar los punteros no afectará el rendimiento.

Answer 4

que sugeriría std::list ya que está perfectamente adaptada para la inserción y extracción de elementos.