¿Qué contenedor STL debe realizar la eliminación de elementos intermedios?

Question

necesito para recoger un contenedor para contener punteros a un tipo I definida (Particle). Estoy usando una partícula preasignados Object Pool (que contienen objetos preasignados en un std :: vector).

Mis emisores de partículas piden a la piscina de partículas para las partículas cuando tienen que emitir, (a fin de evitar la asignación de partículas en el juego). Cuando una partícula caduca, se devuelve al grupo de objetos de partículas.

Como puede ver, mientras recorro mi Contenedor de referencia de partículas (necesito elegir uno) para actualizarlo, tendré que comprobar qué partículas han expirado (lifetime <= 0.0) y devolverlas al grupo de partículas, las partículas expiradas podrían estar en cualquier posición en el contenedor.

He estado pensando acerca del uso de std::list, he aquí por qué:

una lista (que yo sepa) proporciona la inserción constante de tiempo al principio, y la eliminación constante de tiempo en cualquier punto (suponiendo que ha reiterado a ese punto).

Cualquier sugerencia o mejoras a mi sistema con el fin de acomodar mejor sus sugerencias contenedores son bienvenidos.

EDITAR:

de explicarme un poco mejor:

El tiempo de vida de las partículas en un emisor es no exactamente lo mismo, depende de una serie, por ejemplo, 5,0 segundos + - (0.0 a 0.5). Esto es para dar a las partículas un elemento de aleatoriedad, y se ve bastante mejor que todo en tiempo fijo.

código Pseudo Algoritmo:

// Assume typedef std::container_type<Particle *> ParticleContainer 

void update(float delta) 
{ 
    ParticleContainer::iterator particle = m_particles.begin(); 

    for(; particle != m_particles.end(); ++particle) 
    { 
     updateParticle(*particle, delta);   //Update the particle 

     if ((*particle)->lifeTime <= 0.0) 
     { 
      ParticlePool.markAsFree(*particle); //Mark Particle as free in the object Pool 
      m_particles.remove(*particle);  //Remove the Particle from my own ParticleContainer 
     } 
    } 
} 

Answer 1

No sigo completamente su algoritmo, pero std::vector es necesario para proporcionar el tiempo constante amortizado push_back. También puede tener una mejor localidad de referencia cuando itera.

Si el orden no importa, la eliminación de cualquier artículo es también una operación de tiempo constante:

template <typename T> 
void remove(std::vector<T> &v, size_t i) 
{ 
    std::swap(v[i], v.back()); 
    v.pop_back(); 
} 

Answer 2

Suponiendo que usted no necesita la indexación directa (operator[]) y sólo está normalmente interactuando sobre los contenedores, list suena muy bien. Incluso puede utilizar splice para mover los nodos de lista en tiempo constante sin asignación de memoria o cancelación de asignación.

Answer 3

Suena como std::list es el camino a seguir. Esto supone que definitivamente desea iterar sobre la lista mientras elimina objetos del medio. Tenga en cuenta que la mayoría de los demás contenedores invalidarán los iteradores cuando los elimine del centro; std::list no. sugerencias adicionales:

• Si se preocupan por el espacio (mucho), puede intentar Boost.Intrusive
• Si usted está dispuesto a utilizar un contenedor estándar, dar slist (lista enlazada; gcc) apoya esta intentarlo - ahorrará espacio, le ahorrará algún costo de tiempo de ejecución (pequeño) al eliminar elementos, ya que está reduciendo el número de punteros que deben actualizarse.Esto se compara con un std::list, que está doblemente vinculado.

Answer 4

¿Por qué no utilizar un priority queue? De esta forma, no tendrá que iterar sobre todas las partículas activas.

edición: pensándolo bien: no estoy tan seguro de que esto funcionaría realmente, dependiendo de su algoritmo (que ciertamente no entendía por completo.) Si va a cambiar esa vida-valor, mientras que las entradas son en el contenedor, una cola podría no funcionar en absoluto.

Si, sin embargo, no cambia ese valor (por ejemplo, establece el tiempo de expiración de las partículas cuando las inserta, y luego solo comprueba la primera entrada contra la hora actual), sigo pensando que esta es su mejor opción. (Tenga en cuenta que la cola de prioridad es solo un adaptador que usa std::vector internamente de manera predeterminada.)

edit2: referente a su edición. Yo sugeriría que no se almacene un valor de "vida útil" con cada partícula (que se reduce constantemente hasta que ya no sea positivo), sino que se almacene una marca de tiempo que represente cuándo se debe eliminar la partícula. Al inicializar la partícula, simplemente calcule cuándo expira la partícula (agregando su "vida" aleatoria a la hora actual). Este valor no cambiaría durante la vida de su partícula. Al determinar si eliminar una partícula, simplemente verifique si la hora actual es más grande que la fecha y hora de vencimiento.

Answer 5

No lo entiendo del todo, pero;

• un conjunto de punteros de partículas podría ser digno de la tarea también. registro de inserción (n) registro de remoción (n)

• si la iteración es mayoritariamente la localidad puede tener un gran impacto (no estoy seguro de cuán eficientes son las listas stl al respecto, pero los vectores stl son ciertamente mejores en esto) y podría valer la pena marcar en lugar de eliminar