cola de prioridad de STL - eliminar un elemento

Quiero implementar un sistema de cola de temporizador utilizando el adaptador de contenedor C++ STL priority_queue.cola de prioridad de STL - eliminar un elemento

Mi problema es que quiero cancelar ocasionalmente un temporizador, sin embargo, no hay interfaces que me permitan eliminar fácilmente un elemento en la prioridad_que no sea el elemento superior.

¿Alguna sugerencia ?.

Gracias por su ayuda.

Fuente

2010-06-19 Mewzer

que tenían el mismo escenario exacto de una vez hizo lo siguiente:

la estructura que guardaba en std::priority_queue contenían sólo el tiempo para ordenar y un índice a una std::vector<Handler> (en mi caso Handler era boost::function, pero bien podría ser un puntero a la interfaz o la función)
al agregar un temporizador, me gustaría encontrar un índice libre en el vector de controladores y almacenar el controlador en ese índice. Almacene el índice y la hora en la prioridad_cola. Devuelva el índice al cliente como token para cancelar
para cancelar un temporizador, pase el índice recibido al agregarlo. Borre el controlador en ese índice (para boost::function llame al clear(), si usa punteros, configúrelo en cero)
cuando es hora de devolver la llamada a un temporizador, obtenga su índice de controlador de la cola de prioridad y revise el vector de controladores - si el controlador de esa posición está vacía()/NULL, el temporizador ha sido cancelado. Marque el índice del controlador como gratuito.

Para hacer la búsqueda de un índice de conexión rápida, he usado un std::stack separada de los índices. Cuando agrega un temporizador y esa pila está vacía, agregue al final del vector; de lo contrario, haga estallar el índice superior y úselo.

Aquí es el punto cuando se pulsa el índice para los índices libres apilar

Todo esto es un poco complicado y propenso a errores, especialmente si sus rutinas de temporización que añadir o cancelar temporizadores. Here's a link to my canceling timer class described above, this code is public domain

Fuente

2010-06-19 18:29:35 sbk

He hecho algo similar a esto también. Es un patrón útil. –

intrigante. Pero no puedo ver cómo manejar el caso cuando un temporizador se "cancela", pero de hecho ya se ha ejecutado. ¿Dejas todo bajo el código de llamada para borrar cualquier control de un temporizador cuando ese temporizador se dispara? –

Creo que voy a hacer que mis estructuras en cola almacenen un 'boost :: shared_ptr ' que funciona como un controlador para el temporizador. Entonces, cualquiera puede entrar en ese mango y establecer una bandera "cancelada", que se recogerá cuando el cronómetro esté listo. –

El contenedor priority_queue de STL está específicamente diseñado para que solo se pueda acceder al elemento superior, por lo que si necesita poder eliminar elementos no superiores, tendrá que buscar una clase diferente para usar.

Fuente

2010-06-19 16:14:37 Amber

Me temo que STL priority_queue no ofrece tal funcionalidad. Puede escribir su propia clase de pila (que no es tan difícil). Incluso puede utilizar las funciones de std::xxx_heap trucos sucios como esto:

delete_heap(iterator to_delete, iterator heap_begin, iterator heap_end) 
{ 
    to_delete->key = something that would compare less to everything; // make sure it gets to the top in the next step 
    std::push_heap(heap_begin, to_delete+1); 
    std::pop_heap(heap_begin, heap_end); 
}

que le llevará O(log n) elimina.

Fuente

2010-06-19 16:30:53 jpalecek

intrigante. ¿Cuántos datos copiaría la función? – Dummy00001

Mi problema es que quiero ocasionalmente cancelar un temporizador, sin embargo, no hay interfaces que me permitan eliminar fácilmente un elemento en la prioridad_que no sea el elemento superior.

Si la cancelación de un temporizador ocurre a menudo, entonces necesita usar una estructura diferente. std :: map no es tan malo también, aunque el costo de delete_min subiría.

Si la cancelación de un temporizador ocurre con poca frecuencia, marcar el elemento como eliminado (e ignorarlo durante :: pop) podría ser el truco.

Fuente

2010-06-19 17:08:54 Dummy00001

A pesar de lo que dicen otras respuestas, es posible acceder al contenedor subyacente de cualquier adaptador de contenedor estándar, incluido priority_queue, ya que el contenedor está expuesto como un miembro protegido llamado c. Puede heredar desde priority_queue y ampliar la interfaz, o utilizar trucos sucios como this para obtener acceso temporalmente a un priority_queue normal.

Fuente

2010-06-19 17:12:06

Es interesante saber que el miembro del contenedor "c" está realmente estandarizado. – sstn

Tenía el mismo requisito. Si tiene la libertad de cambiar el contenedor, el que puede resolver este problema es std::set (no se permiten duplicados) o std::multiset.

Ambos se ordenan y pueden borrar un elemento logarítmico en el tamaño del contenedor (consulte la documentación para obtener más información). Para obtener ayuda para eliminar en conjuntos múltiples, es posible que desee ver this.

Ver la diferencia std::set vs std::priority_queue antes de decidirse.

Fuente

2016-11-12 10:50:52 n00buser

cola de prioridad de STL - eliminar un elemento

Respuesta

Cuestiones relacionadas